编译原理-第四章 语法分析

编译原理CompilerPrinciples徐小龙[e-mail]南京邮电大学.计算机学院第四章语法分析comPilingrunningProgramming教材：《编译技术原理及其实现方法》王汝传编著第四章语法分析本章内容§4.1引言一、语法分析任务二、语法分析方法§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法二、递归子程序分析法（递归下降分析法）三、LL（1）分析法§4.3自底向上语法分析一、简单优先文法分析法二、算符优先分析法三、优先函数及其构造四、LR分析法五、二义性文法的应用§4.4语法分析程序的自动生成一、分析器的生成器YACC二、用YACC处理二义性文法§4.1引言本节内容一、语法分析任务1.语法检查2.根据语法符号进行一定处理加工二、语法分析方法1.自顶向下语法分析方法2.自底向上语法分析方法§4.1引言一、语法分析任务词法分析阶段，主要介绍了单词符号的结构、识别（用状态转换图），描述（通过正规式）以及有限自动机DFA和NFA。在一个编译程序对某个源程序完成了词法工作以后,就进入了语法分析阶段。由词法分析程序所产生的单词符号流，作为语法分析程序的输入串，按文法规则分析检查是否构成了合法的句子。§4.1引言一、语法分析任务1、语法检查根据语法规则对各种语法成分进行分析；确定它们的语法关系以检查语法上的正确和错误；指出错误的性质和出错位置。如：IfBthenS1elseS2正确若写成IfBthenelseS2错误then后少一个S1§4.1引言一、语法分析任务2、根据语法符号进行一定语义处理加工假如语法分析过程得到一个合法的句子时，往往同时进行必要的语义分析等如：当处理表达式a+b*c时，若该表达式语法关系正确，就可以进行语义处理加工，可将该表达式变成中间语言，以便以后生成目标程序§4.1引言本节内容一、语法分析任务1.语法检查2.根据语法符号进行一定处理加工二、语法分析方法1.自顶向下语法分析方法2.自底向上语法分析方法§4.1引言二、语法分析方法语法分析方法很多，但能够产生计算机程序并能得到广泛应用的主要有两大类，按照生成语法树的顺序：1.自顶向下语法分析方法2.自底向上语法分析方法§4.1引言二、语法分析方法1、自顶向下语法分析方法（1）带回溯分析方法（2）不带回溯分析方法（3）递归子程序法（4）状态矩阵法（5）LL（1）分析法§4.1引言二、语法分析方法2、自底向上语法分析方法（1）简单优先分析法（2）算符优先分析法（3）LR分析法（4）SLR分析法（5）LALR分析法第四章语法分析本章内容§4.1引言一、语法分析任务二、语法分析方法§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法二、递归子程序分析法（递归下降分析法）三、LL（1）分析法§4.3自底向上语法分析一、简单优先文法分析法二、算符优先分析法三、优先函数及其构造四、LR分析法五、二义性文法的应用§4.4语法分析程序的自动生成一、分析器的生成器YACC二、用YACC处理二义性文法§4.2自顶向下语法分析本节内容一、自顶向下分析方法的问题及其解决办法1.消除回溯2.消除左递归二、递归子程序分析法（递归下降分析法）1.递归子程序定义2.递归调用子程序的处理3.分析实例4.递归子程序特点三、LL（1）分析法1.定义2.LL（1）分析方法3.构造分析表4.LL（1）文法§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法对于自顶向下语法分析来说，对于某些文法，可能会遇到“回溯”和“左递归”的问题；为了能有效地运用这种语法分析方法，应使文法不含左递归及避免回溯。§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（1）回溯分析方法定义在进行自顶向下语法分析时，对于文法规则中具有同一左部而右部有不同规则时，在分析时按顺序一个个试探，若能分析下去则成，否则在退回到出错点换另一规则重新试探。这种方法称回溯分析方法，实质就是使用不同规则反复试探。§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（1）回溯分析方法定义举例如：S∷＝cAdA∷＝ab|a要判断“cad”是否为该文法的句子，可以分别用A∷＝ab和A∷＝a代入第一个产生式中试探ScdA§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（1）回溯分析方法定义举例如：S∷＝cAdA∷＝ab|a要判断“cad”是否为该文法的句子，可以分别用A∷＝ab和A∷＝a代入第一个产生式中试探ScdAab§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（1）回溯分析方法定义举例如：S∷＝cAdA∷＝ab|a要判断“cad”是否为该文法的句子，可以分别用A∷＝ab和A∷＝a代入第一个产生式中试探ScdAa§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（2）回溯问题的解决1）路标法定义：设有规则U∷＝a1V1|a2V2|…|anVn若ai为互不相同的终结符时，将ai作为路标，当被分析符号串为ai时，便可按规则U∷＝aiVi往下分析，这样可以消除回溯。§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（2）回溯问题的解决1）路标法举例：语句∷＝变量：＝表达式|If布尔表达式then语句当分析语句：IfABthenA:=B，我们可以根据第二个产生式以If开始直接选用它作判断。If在这里就是路标§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（2）回溯问题的解决1）路标法无回溯文法设计准则：我们在设计程序设计语言时，要考虑语法规则各选择项开始符互不相同§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（2）回溯问题的解决1）路标法无回溯文法设计准则：一般地，设U为文法Ｇ的任意非终结符号，若UU∷＝α１｜α2｜…｜αnαi∈Ｖ+若定义任一个选择αi的所有可能推出终结符号串的首符号集FIRST（αi）FIRST（αi）＝｛a｜αi*a…，a∈ＶT｝显然FIRST（αi）ＶT§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（2）回溯问题的解决1）路标法无回溯文法设计准则：为了避免回溯，FIRST(αi）∩FIRST(αj）＝（i≠j）即对文法中的任意一个非终结符号，其规则右部有多个选择时，若由各个选择所推出的终结符号串首符号集合要两两不相交。这样就可能根据当时读进的符号是属于哪个选择的FIRST（αi），来唯一地确定该选用哪个选择来匹配输入串。如：当前输入符号为b(b∈ＶT)，如果b∈FIRST(αi），则可选择第i个产生式去匹配输入串。§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（2）回溯问题的解决2）提取左公因子法一般地说，U∷＝aβ１｜aβ2｜…｜aβn｜γU∷＝aU'｜γU'∷＝β１｜β2｜…｜βn其中a称为左公因子，经过反复提取公因子即可将每个非终结符的所有选择首符号集变成两两不相交。§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（2）回溯问题的解决2）提取左公因子法注意：U∷＝xy|x可写成U∷＝x(y|)当分析符号串遇到时，认为总能匹配，可以一直分析下去。U∷＝xy|x也可写成U∷＝x[y]表示y不出现或出现一次。§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（2）回溯问题的解决2）提取左公因子法举例：显然存在回溯。为避免分析时回溯，可以将文法改写成：S∷＝xAy,A∷＝*（*|）进一步改写成S∷＝xAy,A∷＝*B，B∷＝*|文法S∷＝xAy,A∷＝**|*要分析x*y§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法1、消除回溯（2）回溯问题的解决2）提取左公因子法举例：改写后文法S∷＝xAyA∷＝*BB∷＝*|为分析符号串X*Y，可以从开始符号出发，SxAyx*Byx*y（即x*y,匹配成功）没出现回溯现象。SxyA*A1§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（1）问题由来在自顶向下分析过程中，假定现在轮到要用非终结符U去匹配输入串，U∷＝U…它是一条直接左递归规则，这种左递归文法将使上述自顶向下的分析过程陷入无限循环，即：当试图用U去匹配输入串时会发现，在没有吃进任何输入符号的情况下，又得重新要求U去匹配，如此循环下去而无终止。若文法具有间接左递归，U＋U…那么，也会发生上述问题。§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（1）问题由来举例：其分析过程如下：SABbBBbSbBbABbBbbBBbB(得第二个字符与输入串不匹配）SABbBBbSbBbABbBbAaBbB(只能用A∷＝Aa推导，又遇A，出现了死循环）由于文法规则中有左递归A∷＝Aa，所以无法分析下去文法G[S]：S∷＝ABA∷＝bB|AaB∷＝Sb|a分析符号串baabaab是否是文法G的句子。§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（2）消除左递归方法1）用重复表示法（扩充的BNF表示法）改写语法规则Ａ∷＝Ａα｜β其中α非空，β不以Ａ开头，Ａ∷＝β｛α｝§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（2）消除左递归方法1）用重复表示法（扩充的BNF表示法）改写语法规则例如，E∷＝E＋T｜TE∷＝T｛＋T｝EET＋ET＋ET＋T等价ET+T+T+TT+T+T+T§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（2）消除左递归方法1）用重复表示法（扩充的BNF表示法）改写语法规则再例如，T∷＝T*Ｆ｜T可改写为T∷＝T（*Ｆ｜／Ｆ）｜ＦT∷＝Ｆ｛*Ｆ｜／Ｆ｝这样，改写后的文法消除了直接左递归。且改写前后的文法是等价的。§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（2）消除左递归方法2）消除直接左递归文法规则Ａ∷＝Ａα｜β1对Ａ引入一个新的非终结符Ａ'2将Ａ∷＝Ａα｜βＡ∷＝βＡ'Ａ'∷＝αＡ'｜ε由于β不以Ａ开头，α不以Ａ'开头，因此改写后两条规则不是直接左递归。同样可以证明这种形式和原来形式是等价的。§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（2）消除左递归方法2）消除直接左递归Ａ∷＝Ａα｜βＡ∷＝βＡ'Ａ'∷＝αＡ'｜εAAαβAαAαβααα等价AβA’αA’αA’αA’εβααα等价§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（2）消除左递归方法2）消除直接左递归－》一般性方法描述Ａ∷＝Ａα１｜Ａα2｜…｜Ａαn｜β１｜β2｜…｜βn这时可改写成如下形式：Ａ∷＝A(α１｜α2｜…｜αn)｜β１｜β2｜…｜βn由消除直接左递归方法，得Ａ∷＝(β１｜β2｜…｜βn)Ａ'Ａ'∷＝(α１｜α2｜…｜αn)Ａ'｜ε§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（2）消除左递归方法2）消除直接左递归－》例子例如：A∷＝Ac|Aad|bd|e等价于：A∷＝A（c|ad）|bd|e所以可以改写成：A∷＝（bd|e）A’（即A∷＝bdA’|eA’）A’∷＝（c|ad）A’|ε（即A’∷＝cA’|adA’|ε）§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（2）消除左递归方法2）消除直接左递归－》例子E∷＝E＋T｜TT∷＝T*Ｆ∷＝（E）｜iE∷＝TE'E'∷＝＋TE'｜εT∷＝ＦT'，T'∷＝*ＦT'｜εＦ∷＝（E）｜i§4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法2、消除左递归（2）消除左递归方法注意上述两种方法可消除任意直接左递归但不能消