第4章语法分析

1、第四章第四章 语法分析语法分析自顶向下分析自顶向下分析 语法分析是编译过程的核心部分，它的主要任务是语法分析是编译过程的核心部分，它的主要任务是按照程序语言的语法规则，从由词法分析输出的源程序按照程序语言的语法规则，从由词法分析输出的源程序符号串中符号串中识别出各类语法成分，同时进行语法检查识别出各类语法成分，同时进行语法检查，为，为语义分析和代码生成语义分析和代码生成作准备。执行语法分析任务的程序作准备。执行语法分析任务的程序叫语法分析程序或语法分析器。叫语法分析程序或语法分析器。 语法分析程序以词法分析输出的符号串作为输入，语法分析程序以词法分析输出的符号串作为输入，在分析过程中在分析过程

2、中检查这个符号串是否为该程序语言的句子检查这个符号串是否为该程序语言的句子。若是，输出该句子的分析树若是，输出该句子的分析树；若不是，则表示源程序存若不是，则表示源程序存在语法错误在语法错误，需要，需要报告错误的性质和位置报告错误的性质和位置。例如，对于。例如，对于C程序语句程序语句“IF (aa, aVt若若=*, 则规定则规定FIRST()实际上，实际上，FIRST()就是从就是从可能推导出的所有开头终可能推导出的所有开头终结符号和可能的结符号和可能的。4.2.1 FIRST4.2.1 FIRST集合定义及构造方法集合定义及构造方法文法符号的文法符号的FIRST集合构造方法：集合构造方法：

3、对于文法中的符号对于文法中的符号XVnVt，其，其FIRST(X)(X)集合可反复集合可反复应用下列规则计算，直到应用下列规则计算，直到FIRST(X)FIRST(X)集合不再增大为止：集合不再增大为止： 1)若若XVt，则，则FIRST(X)=X2)若若XVn，且具有形如，且具有形如Xa的产生式的产生式(aVt)，或具有，或具有形如形如X的产生式，则把的产生式，则把a或或加进加进FIRST(X)。3)设设G中有形如中有形如XY1Y Y2YYk的产生式，若的产生式，若Y Y1VVn，则把，则把FIRST(YFIRST(Y1) )中的一切非中的一切非符号加进符号加进FIRST(X)FIRST(X

4、)；对于一切；对于一切2ik2ik，若，若Y Y1，Y Y2，Y Yi-1均为非终结符号，且均为非终结符号，且FIRST(YFIRST(Yj) )，1ji-11ji-1，则将，则将FIRST(YFIRST(Yi) )中的一切非中的一切非符号加进符号加进FIRST(X)FIRST(X)；但若对一切；但若对一切1ik1ik，均有，均有FIRST(YFIRST(Yi) )，则将，则将符号加进符号加进FIRST(X)FIRST(X)。 对于文法对于文法G的任一符号串的任一符号串=X1X2Xn可按下列步骤可按下列步骤构造其构造其FIRST()集合：集合：1)置置FIRST()=2)将将FIRST(X1)

5、中的一切非中的一切非符号加进符号加进FIRST()；3)若若FIRST(X1)，将，将FIRST(X2)中的一切非中的一切非符号符号加进加进FIRST()；若若FIRST(X1)和和FIRST(X2)，将，将FIRST(X3)中的一切非中的一切非符号加进符号加进FIRST()；余此类；余此类推。推。4)若对于一切若对于一切1in，FIRST(Xi i) )，则将，则将符号加符号加进进FIRST()FIRST()。 4.2.1 FIRST4.2.1 FIRST集合定义及构造方法集合定义及构造方法开始符号集合开始符号集合First( )的意义的意义 如果是任意的文法符号串，则First()是从推导

6、出的串的首终结符集合。 由于由于c First(Ap )，因此在例，因此在例2中，当有字符中，当有字符串串W=ccap，在进行自顶向下推导时，在产，在进行自顶向下推导时，在产生式生式S Ap与与S Bq中选取中选取S Ap 。4.2.1 FIRST4.2.1 FIRST集合定义及构造方法集合定义及构造方法例例4.3，有，有文法文法 ETE E+TE E TFT T*FT T F(E)|i求文法中非终求文法中非终结符号以及符结符号以及符号串的号串的FIRST集。集。解：首先求各符号的解：首先求各符号的FIRST集：该文法共有非集：该文法共有非终结符号为终结符号为E，E，T，T，FFIRST(E)

7、=FIRST(T)=FIRST(F)= ( ，i FIRST(E)= + ，FIRST(T)= * ，下面求文法中各产生式右部符号串的下面求文法中各产生式右部符号串的FIRST集：集：FIRST(TE)=FIRST(T)=FIRST(F)= ( ，i FIRST(+TE)= + FIRST()=FIRST(FT)=FIRST(F)= ( ，i FIRST(*FT)= * FIRST(E)= ( FIRST(i)= i 4.2.2 FOLLOW4.2.2 FOLLOW集合定义及构造方法集合定义及构造方法 FOLLOW集合定义：假定集合定义：假定S是文法的开始符号，对于是文法的开始符号，对于G的任

8、何非的任何非终结符号终结符号A，则：，则： FOLLOW(A)= a | S=Aa, aVt 若若S=*A，则规定，则规定#FOLLOW(A)从定义可看出，从定义可看出，FOLLOW(A)就是在就是在所有句型中所有句型中出现在紧接出现在紧接A之后之后的终结符号或的终结符号或#。对于文法中的符号对于文法中的符号AVn，其，其FOLLOW(A)集合可反复应用下列规集合可反复应用下列规则计算，直到其则计算，直到其FOLLOW(A)集合不再增大为止：集合不再增大为止：1) 对于文法的开始符号，令对于文法的开始符号，令#FOLLOW(S)2) 若若G中有形如中有形如AB 的产生式，且的产生式，且 ，则将

9、，则将FIRST()中的中的一切非一切非符号加进符号加进FOLLOW(B)。3) 若若G中有形如中有形如AB或或AB 的产生式，且的产生式，且FIRST()，则，则FOLLOW(A)中的全部元素均属于中的全部元素均属于FOLLOW(B)。注意：在注意：在FOLLOW集合中无集合中无。 4.2.2 FOLLOW4.2.2 FOLLOW集合定义及构造方法集合定义及构造方法例例4.4，有，有文法文法 ETE，E+TE，E， TFT， T*FT，T，F(E)|i，求各非终结符号的求各非终结符号的FOLLOW集。集。解：首先，我们需要求出某些符号的解：首先，我们需要求出某些符号的FIRST集：集： FI

10、RST(E)=FIRST(T)=FIRST(F)= ( ，i FIRST(E)= + ，FIRST(T)= * ， 接下来，按接下来，按FOLLOW集定义求各非终结符号的集定义求各非终结符号的FOLLOW集：集： FOLLOW(E)= )，#，FOLLOW(E)= FOLLOW(E)= ) ，# FOLLOW(T)= FIRST(E) FOLLOW(E) FOLLOW(E) = + ， ) ， # FOLLOW(F)= FIRST(T) FOLLOW(T) FOLLOW(T) = +，*，) ，# FOLLOW(T)= FOLLOW(T)= + ， ) ， # 因为因为E出现在产生式的右边的出

11、现在产生式的右边的情况只有情况只有F(E)|i，不能应用，不能应用规则规则2，3，所以只能按照定，所以只能按照定义和规则义和规则1得出结果得出结果因为因为ETE，应用规，应用规则则3，此外，没有其他，此外，没有其他产生式能提供了。产生式能提供了。因为因为E+TE，E ，应用规则，应用规则2，FIRST(E)加进加进FOLLOW(T)因为因为ETE，E ，应用规则应用规则3， FOLLOW(E)加进加进FOLLOW(T)因为因为E+TE ，E ，应用规则，应用规则3， FOLLOW(E)加进加进FOLLOW(T)因为因为TFT ，T ，应用规则，应用规则2，FIRST(T)加进加进FOLLOW(

12、F)因为因为TFT ，T ，应用规则应用规则3， FOLLOW(T)加进加进FOLLOW(F)因为因为T*FT ，T ，应用规则，应用规则3， FOLLOW(T)加进加进FOLLOW(F)4.3 4.3 递归下降分析递归下降分析 4.3.1 递归下降分析的基本方法递归下降分析的基本方法递归下降分析的方法是将文法中的每一个非终结符递归下降分析的方法是将文法中的每一个非终结符U的文的文法规则看作是法规则看作是识别识别U的一个过程定义的一个过程定义，为每个，为每个非终结符号非终结符号构造一个子程序构造一个子程序，以完成该非终结符号所对应的语法成分以完成该非终结符号所对应的语法成分的分析和识别任务。如

13、果的分析和识别任务。如果U U的文法规则的右部只有一个侯的文法规则的右部只有一个侯选式，则按从左向右的顺序依次构造规则选式，则按从左向右的顺序依次构造规则U U的识别过程代的识别过程代码。如果有终结符号，判断能否与输入的符号相等，如果码。如果有终结符号，判断能否与输入的符号相等，如果相等，表示识别成功，读入指针指向下一个输入符号；如相等，表示识别成功，读入指针指向下一个输入符号；如果不等，则意味着输入串此时有语法错误。如果是非终结果不等，则意味着输入串此时有语法错误。如果是非终结符号，则调用这个非终结符号的子程序，由这个子程序完符号，则调用这个非终结符号的子程序，由这个子程序完成该非终结符号所

14、对应的语法成分的分析和识别任务。当成该非终结符号所对应的语法成分的分析和识别任务。当一条规则右部有一条规则右部有多个侯选式多个侯选式时，则根据每个侯选式的时，则根据每个侯选式的第一第一个符号个符号确定该侯选式分支。只有被调用的子程序匹配输入确定该侯选式分支。只有被调用的子程序匹配输入串成功且正确返回时，该语法成分才算真正获得识别。串成功且正确返回时，该语法成分才算真正获得识别。 例例4.5，考虑文法，考虑文法Z:=(U)|aUb ，U:=dZ|e，为其构造递，为其构造递归下降分析子程序。并对输入串归下降分析子程序。并对输入串aebaeb进行语法分析进行语法分析 。解：文法中有两个非终结符号解：

15、文法中有两个非终结符号Z和和U，那么我们需要分，那么我们需要分别编两个过程来完成别编两个过程来完成Z和和U规则的识别。对于规则规则的识别。对于规则Z:=(U)|aUb，右部有两个候选式，因此，右部有两个候选式，因此，U的识别过程的识别过程有两个分支，分别根据符号有两个分支，分别根据符号(和和a来判别。同理对规则来判别。同理对规则U:=dZ|e设计的过程也分为两个分支。见图设计的过程也分为两个分支。见图4.1(a)和和(b)所示。所示。4.3 递归下降分析递归下降分析 4.3.1 递归下降分析的基本方法递归下降分析的基本方法Z:=(U)|aUb过程过程ZINPUTSYM=下一个符号下一个符号U出

16、口出口语法错误：语法错误：输入串少输入串少)INPUTSYM =aYNNNNYY语法错误：语法错误：输入串少输入串少(、a语法错误：语法错误：输入串少输入串少bINPUTSYM =(INPUTSYM =)INPUTSYM =bINPUTSYM=下一个符号下一个符号INPUTSYM=下一个符号下一个符号UY图4.1(a) 非终结符号Z的分析程序 过程过程UINPUTSYM=下一个符号下一个符号Z出口出口INPUTSYM =eYNNY语法错误：语法错误：输入串少输入串少d、eINPUTSYM =dINPUTSYM=下一个符号下一个符号YU:=dZ|e图4.1(b) 非终结符号U的分析程序 4.3.

17、1 递归下降分析的基本方法递归下降分析的基本方法每个非终结符号的子程序设计好后，就可以对输入串进行语法分每个非终结符号的子程序设计好后，就可以对输入串进行语法分析。假设输入串为析。假设输入串为aeb,从从Z子程序开始识别，子程序开始识别，inputsym=a,由于由于INPUTSYM不等于不等于(，等于，等于a，所以选择，所以选择Z子程序的右边分支，表子程序的右边分支，表示选择了示选择了Z:=aUb规则。读下一个符号，使规则。读下一个符号，使inputsym=e，调，调U子子程序，因程序，因INPUTSYM=e，表示使用，表示使用U:=e规则，所以，读下一个规则，所以，读下一个符号，使符号，使

18、inputsym=b，并返回调用程序并返回调用程序Z子程序右边分支子程序右边分支U的下的下方，接着判断方，接着判断INPUTSYM=b，读下一个符号，应为结束符，并，读下一个符号，应为结束符，并退出退出Z，分析过程结束，从而判定输入串，分析过程结束，从而判定输入串aeb语法分析成功。这语法分析成功。这个过程相当于构造了如下推导过程：个过程相当于构造了如下推导过程： Z=aUb=aeb 4.3.2 4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法 递归下降分析存在以下递归下降分析存在以下几个问题几个问题：1) 左递归问题左递归问题，例如文法，例如文法EE+T|T，

19、如果按前面介绍，如果按前面介绍的方法为的方法为E设计分析程序，那么你会发现，这将是一个设计分析程序，那么你会发现，这将是一个无穷递归的程序。实际上，当文法含有直接或间接左递无穷递归的程序。实际上，当文法含有直接或间接左递归时，都会出现无穷递归。归时，都会出现无穷递归。2) 右部多个侯选式的第一个符号相同问题右部多个侯选式的第一个符号相同问题，即局部二义，即局部二义性问题。例如对性问题。例如对Aab|a，对，对A进行分析程序设计时，根进行分析程序设计时，根据据a无法区分应该选择哪个分支，即出现局部二义性。无法区分应该选择哪个分支，即出现局部二义性。3) 右部侯选式的第一个符号是非终结符号右部侯选

20、式的第一个符号是非终结符号，如，如A|时，时，如果如果和和均以非终结符开始，那么就很难决定何时使用均以非终结符开始，那么就很难决定何时使用A选项，何时又使用选项，何时又使用A选项。选项。如果右部某个侯选式如果右部某个侯选式为为或能推导出或能推导出，分析程序该如何设计。，分析程序该如何设计。 4.3.2 4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法 1、 左递归问题左递归问题 不同的文法可描述相同的语言，这些文法称为等价不同的文法可描述相同的语言，这些文法称为等价文法。对于左递归问题，可用等价文法来解决，即将文文法。对于左递归问题，可用等价文法来解决，即将文法

21、中的左递归去掉。消除直接左递归的方法如下：法中的左递归去掉。消除直接左递归的方法如下：对形如对形如U:=x|y|.|z|Uv的直接左递归文法规则，用扩充的直接左递归文法规则，用扩充BNF表示来改写规则，即利用元符号表示来改写规则，即利用元符号“”和和“”来改写来改写规则，将规则改写成规则，将规则改写成U:=(x|y|.|z)v。例例4.6，有文法：，有文法：E:=E+T|E-T|T ，T:=T*F|T/F|F，为，为其设计递归分析程序。其设计递归分析程序。解：先按上面介绍的方法消除左递归：解：先按上面介绍的方法消除左递归： E:=E+T|E-T|T 可改成可改成 E:=T+T| -T T:=T

22、*F|T/F|F 可改成可改成 T:=F*F| /F修改后，我们很容易为修改后，我们很容易为E和和T设计分析程序，如图设计分析程序，如图4.2所所示，注意示，注意“”和和“”括起来的内容采用循环设计。括起来的内容采用循环设计。 4.3.2 4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法E:=T|E+T|E-T E:=T+T|-TT:=F|T*F|T/F T:=F*F| /FETYN出口出口INPUTSYM=下一个符号下一个符号INPUTSYM =+INPUTSYM =-NYTFYN出口出口INPUTSYM=下一个符号下一个符号INPUTSYM =*INPUTS

23、YM =/NY对于对于直接左递归直接左递归规则的变换方法是将规则的变换方法是将不含左递归的各选不含左递归的各选式用圆括号括起来，放置在规则右部的最左端式用圆括号括起来，放置在规则右部的最左端，然后将然后将含有递归的侯选式中的左递归符号去掉，剩余部分用花含有递归的侯选式中的左递归符号去掉，剩余部分用花括号括起来放置在规则右部的最右端括号括起来放置在规则右部的最右端，这样，就可将直，这样，就可将直接左递归规则转变成用扩充接左递归规则转变成用扩充BNF表示的等价文法。表示的等价文法。4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法E:=T|E+T|E-T E:=T+T

24、|-TT:=F|T*F|T/F T:=F*F| /FU:=x|y|.|z|UvU:=(x|y|.|z)v4.3.2 4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法对于一般的对于一般的间接左递归间接左递归，首先要变成直接左递归，其消，首先要变成直接左递归，其消除左递归的算法如下：除左递归的算法如下：1) 把文法把文法G的非终结符号整理成某种顺序：的非终结符号整理成某种顺序：A1,A2,An。2) For i:=1 to n begin for j:=1 to n-1 把每个形如把每个形如Ai:=Ajr的规则用的规则用Aj的的右部右部带入，直到带入，直到变成直接左

25、递归变成直接左递归假设假设Aj:= 1|2| k 带入带入Ai中，得中，得Ai:= 1r|2r| kr 消去消去Ai的直接左递归的直接左递归 end3) 去掉多余规则。去掉多余规则。 4.3.2 4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法例例4.7，有文法有文法GS：S:=Qc|c ，Q:=Rb|b ，R:=Sa|a，消除左递归。消除左递归。解：该文法表面上看，没有直接左递归，但因为解：该文法表面上看，没有直接左递归，但因为S=Qc=Rbc =Sabc，说明存在间接左递归。，说明存在间接左递归。首先把首先把R:=Sa|a代入代入Q:=Rb|b中得：中得：Q

26、:=Sab|ab|b再把再把Q:=Sab|ab|b代入代入S:=Qc|c中得直接左递归规则：中得直接左递归规则： S:=Sabc|abc|bc|c按消除直接左递归方法，最后得到的按消除直接左递归方法，最后得到的S规则为：规则为： S:=(abc|bc|c)abcS规则中不再含有符号规则中不再含有符号Q和和R，所以，所以，Q和和R规则为多余规则为多余规则，应删除。规则，应删除。注意：对非终结符号的注意：对非终结符号的排序排序不同，最后不同，最后得到的文法在形式上可能不同，但它们都是等价文法。得到的文法在形式上可能不同，但它们都是等价文法。消去左递归过程中，要注意保证文法的消去左递归过程中，要注意

27、保证文法的识别符号识别符号不变不变。 4.3.2 4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法2、解决局部二义性问题、解决局部二义性问题对于局部二义性问题，即右部多个侯选式的第一个符对于局部二义性问题，即右部多个侯选式的第一个符号相同时，可通过号相同时，可通过提取公因子、加入新的非终结符号提取公因子、加入新的非终结符号来实现。来实现。假设文法中有规则为：假设文法中有规则为：U:=xV|xW ，解决办法如下：，解决办法如下：1) 提取公因子，将规则变成：提取公因子，将规则变成：U:=x(V|W)2）加入一个新的非终结符号加入一个新的非终结符号A，令，令A=V|

28、W，则将规，则将规则改为：则改为： U:=xA ，A:=V|W 4.3.2 4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法3、右部侯选式的第一个符号是非终结符号、右部侯选式的第一个符号是非终结符号对于这种问题，首先要求出每个侯选式的对于这种问题，首先要求出每个侯选式的首符号集首符号集，然后根据，然后根据各侯选式的首符号集内容来选择侯选式。各侯选式的首符号集内容来选择侯选式。设文法设文法G没有左递归，规则形式为：没有左递归，规则形式为： U =|，先求出每个侯选，先求出每个侯选式的式的FIRST()和和FIRST()，为保证在设计子程序时能明确选择，为保证在设计

29、子程序时能明确选择某个侯选式，需要满足以下两点：某个侯选式，需要满足以下两点：1.FIRST()FIRST()=即各侯选式的首符号集互不相交。即各侯选式的首符号集互不相交。2.若若 FIRST()，那么，那么，FIRST()FOLLOW(U)=。 求出首符号集后，若满足上述两条件，那么对于规则求出首符号集后，若满足上述两条件，那么对于规则U =|，可，可以根据下列规则来选择侯选式：以根据下列规则来选择侯选式： 设当前的输入符号是设当前的输入符号是a ，aVt 若若aFIRST() 或或FIRST()且且aFOLLOW(U)，则用，则用侯侯选式。选式。 若若aFIRST() 或或FIRST()且

30、且aFOLLOW(U)，则用，则用侯侯选式。选式。1. 若若aFIRST() 且且aFIRST() ，则语法错，转出错处理。，则语法错，转出错处理。 4.8. 由于相同左部的产生式的右部FIRST集交集不为空引起回溯。例.文法GS ：SxAy Aab|a输入串为输入串为w=xay，分析过程如下：，分析过程如下：Sx A ySx A ya bSx A ya试探试探回溯回溯试探试探First(ab) First(a) 4.9. 由于相同左部非终结符的右部能 且该非终结符FOLLOW集中含有其右部FIRST集的元素。 例. 设文法GS : SaAS AbAS| Sb*Sa A SSa A Sb A

31、SSa A S b试探试探试探试探输入串为输入串为w= ab# ，分析过程如下：，分析过程如下：回溯回溯 FIRST(), FIRST(bAS)FOLLOW(A) 4.10. 由于文法含有左递归而引起回溯。例. 已知文法GS: SSa SbSbSS aSS abSS aS aSS aS ab输入串为输入串为w= baa# ，分析过程如下：，分析过程如下：4.3.2 4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法如果文法中的某条规则，其侯选式的首符号集有相交时，如果文法中的某条规则，其侯选式的首符号集有相交时，可通过可通过改写文法改写文法使其满足条件。方法是使其

32、满足条件。方法是通过规则带入使通过规则带入使侯选式的第一个符号相同，然后提取公因子侯选式的第一个符号相同，然后提取公因子，并对剩余并对剩余部分用新非终结符号代替部分用新非终结符号代替。这一过程可能需要反复进行，。这一过程可能需要反复进行，直到规则的各侯选式的首符号集不相交。但并不是所有直到规则的各侯选式的首符号集不相交。但并不是所有的规则都能用这种方法解决首符号集相交问题，的规则都能用这种方法解决首符号集相交问题，所以，所以，不是所有的文法都可以采用递归下降分析方法进行分析不是所有的文法都可以采用递归下降分析方法进行分析。要实现要实现没有回溯（确定）没有回溯（确定）的自顶向下分析，文法必须满的

33、自顶向下分析，文法必须满足两个条件（足两个条件（但还不一定能够保证是没有回溯的但还不一定能够保证是没有回溯的）：）：文法是非左递归的。文法是非左递归的。1.对文法的任一非终结符号，若其规则右部有多项选择，对文法的任一非终结符号，若其规则右部有多项选择，那么各选项所推出的终结符号串的头符号集合要两两不那么各选项所推出的终结符号串的头符号集合要两两不相交相交 4.3.2 4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法例例4.11，有文法，有文法GZ： Z:=AcB|Bd A:=AaB|c B:=aA|a设计递归下降分析程设计递归下降分析程序。序。解解:首先将左递归

34、去掉，首先将左递归去掉，将规则将规则 A:=AaB|c 改成改成 A:=caB 提取公因子，提取公因子，将规则将规则 B := aA|a 改成改成 B := a(A|) 对于规则对于规则Z := AcB|Bd，为了设计分析程序，要求出每个选项的头，为了设计分析程序，要求出每个选项的头符号集，即符号集，即FIRST(AcB)=c ，FIRST(Bd)=a ，分析程序如图，分析程序如图4.3(a)所示。所示。 改后的文法为：改后的文法为：Z := AcB|Bd , A := caB , B := a(A|)INPUTSYM=bAINPUTSYM=cINPUTSYM=下一个符号下一个符号INPUTS

35、YM=dERRINPUTSYM=aERRINPUTSYM=下一个符号下一个符号z出口出口BBNYYYYNNN图图4.3(a)Z分析程序分析程序 对于规则对于规则A := caB , 分析程序如图分析程序如图4.3(b)所示。所示。 对于规则对于规则B := a(A|) , FIRST(A)=c，分析程序如图所示。，分析程序如图所示。4.3.2 4.3.2 递归下降分析中存在的问题及解决方法递归下降分析中存在的问题及解决方法INPUTSYM=bINPUTSYM=aINPUTSYM=下一个符号下一个符号ERRINPUTSYM=下一个符号下一个符号A出口出口BYYNNINPUTSYM=aINPUTS

36、YM=bERRINPUTSYM=下一个符号下一个符号B出口出口AYYNN图图4.3(c)B分析程序分析程序 图图4.3(b)A分析程序分析程序 4.4 LL(1)4.4 LL(1)分析方法分析方法 LL(1)分析方法是常见的自顶向下分析，分析方法是常见的自顶向下分析，LL(1)分析使用一个分析使用一个下推下推栈栈而不是递归调用来完成分析。名称中而不是递归调用来完成分析。名称中第一个第一个L L表示表示自左向右顺序自左向右顺序扫描输入符号串，扫描输入符号串，第二个第二个L L表示表示分析过程产生一个句子的最左推导。分析过程产生一个句子的最左推导。括号中的括号中的1 1表示表示每进行一步推导，只需

37、要向前查看一个输入符号，每进行一步推导，只需要向前查看一个输入符号，便能确定当前所应选用的规则。便能确定当前所应选用的规则。 4.4.1 LL(1)分析的基本方法分析的基本方法LL(1)分析器由一个分析器由一个总控程序、一张分析表和一个分析栈总控程序、一张分析表和一个分析栈组成，组成，如图如图4.4所示。所示。 输入符号串：输入符号串： 分析栈分析栈a1a2an# XZS#LL（1）总控程序总控程序分析表分析表输出流输出流图图4.4 LL(1)分析器模型分析器模型 4.4.1 LL(1)4.4.1 LL(1)分析的基本方法分析的基本方法 输入符号串输入符号串:指指要分析的输入符号串要分析的输入

38、符号串。为了分析算法的统一，。为了分析算法的统一，我们需要在输入串的末尾放置一个特殊符号我们需要在输入串的末尾放置一个特殊符号#，这个符号不属于，这个符号不属于终结符号集。终结符号集。 分析表分析表M:是一个二维表，可用一个二维数组是一个二维表，可用一个二维数组MA，a来表示，来表示，它它概括了文法的全部信息概括了文法的全部信息。分析表中的每一行与文法中的一个非。分析表中的每一行与文法中的一个非终结符号、终结符号或终结符号、终结符号或#关联，即关联，即A可以是文法中的一个非终结可以是文法中的一个非终结符号、终结符号或符号、终结符号或#；而每一列则与文法的一个终结符号或；而每一列则与文法的一个终

39、结符号或#关联，关联，即即a是文法的一个终结符号或是文法的一个终结符号或#。分析表的列数是终结符号的个数分析表的列数是终结符号的个数加加1，行数是文法中的非终结符号和终结符号的数目加，行数是文法中的非终结符号和终结符号的数目加1；分析表分析表元素元素MA，a，指出了分析器应采取的动作。，指出了分析器应采取的动作。 分析栈分析栈：用来存放一系列文法符号用来存放一系列文法符号。分析开始时，先将。分析开始时，先将#入栈，入栈，然后再将文法的然后再将文法的开始符号开始符号入栈。入栈。 输出流输出流：分析过程中使用的产生式序列分析过程中使用的产生式序列。 总控程序总控程序：分析器对输入串的分析靠总控程序

40、完成。根据分析器对输入串的分析靠总控程序完成。根据分分析栈的栈顶符号析栈的栈顶符号X X和和当前的输入符号当前的输入符号，总控程序按照，总控程序按照分析表的指分析表的指示示来来决定分析器的动作决定分析器的动作。工作过程如下：。工作过程如下： 1) 分析开始时，首先将符号分析开始时，首先将符号#及文法的开始符号及文法的开始符号S依次置于分析栈依次置于分析栈的底部，并把各指示器调整至起始位置，如图的底部，并把各指示器调整至起始位置，如图4.5所示。然后，反所示。然后，反复执行第二步的操作。复执行第二步的操作。 输入符号串：输入符号串： a1a2an#分析栈：分析栈： S#图图4.5分析开始时状况分

41、析开始时状况 2) 假设分析的某一步，分析栈及余留的符号串如图假设分析的某一步，分析栈及余留的符号串如图4.6，则根据，则根据栈顶的符号栈顶的符号Xm，采取下列动作：，采取下列动作： aiai+1 an#X1X2Xm-1Xm 图图4.6分析进行中的状况分析进行中的状况 4.4.1 LL(1)4.4.1 LL(1)分析的基本方法分析的基本方法(1)若若XmVn，则查分析表的，则查分析表的Xm行行a ai i列，假设列，假设MXmMXm，a ai i 为为POPPOP，PUSHPUSH（WVUWVU），则将），则将XmXm出栈，并将出栈，并将WVUWVU反序反序入栈，这意味着使用入栈，这意味着使用

42、了规则了规则XmUVWXmUVW；若；若MXmMXm，a ai i 为空或为空或ERRORERROR，则出错。，则出错。 aiai+1 an#X1X2Xm-1WUV 图图4.7 UVW反序入栈反序入栈 (2)若若Xm=ai#，表示栈顶与扫描的符号匹配，则查分析表为，表示栈顶与扫描的符号匹配，则查分析表为POP，NEXTSYM，则栈顶符号，则栈顶符号Xm出栈，输入指针指向下一个符出栈，输入指针指向下一个符号。号。 ( 3 ) 若若Xm=a ai=#=#，表示输入串完全匹配，分析成功。，表示输入串完全匹配，分析成功。 考虑算术表达式文法考虑算术表达式文法ETE，E+TE，E，TFT，TT* *FT

43、FT，T T，F(E)|iF(E)|i，该文法的分析表如表，该文法的分析表如表4.14.1所示。所示。4.4.1 LL(1)4.4.1 LL(1)分析的基本方法分析的基本方法表4.1 算术表达式分析表 符符号号 输入符号输入符号 i+*()#E POP,PUSH(ET) POP,PUSH(ET) E POP,PUSH(ET+) POP POP T POP,PUSH(TF)POP,PUSH(TF)T POP POP,PUSH( TF* ) POP POP F POP,PUSH( i ) POP,PUSH( )E( ) i POP,NEXTSYM +POP,NEXTSYM * POP,NEXTSY

44、M (POP,NEXTSYM)POP,NEXTSYMSYM #ACCEPT 表4.1 算术表达式分析表 表中元素表中元素POP为过程，功能是将栈顶元素从栈内弹出。为过程，功能是将栈顶元素从栈内弹出。PUSH()为过程，其中为过程，其中V+ ,功能功能是将是将压栈。压栈。NEXTSYM为读符号过程，将读符号指针指向下一个符号。为读符号过程，将读符号指针指向下一个符号。ACCEPT表示分表示分析成功，输入符号串语法正确。表中空白处表示错误入口，调用错误处理程序。析成功，输入符号串语法正确。表中空白处表示错误入口，调用错误处理程序。 4.4.1 LL(1)4.4.1 LL(1)分析的基本方法分析的基

45、本方法例例4.7，根据表，根据表4.1给出的给出的分析表，对符号串分析表，对符号串i+i*i进进行分析。行分析。解：根据分析表以及解：根据分析表以及LL(1)的工作过程，对符的工作过程，对符号串号串i+i*i的分析过程在表的分析过程在表4.2中列出。中列出。表表4.2 符号串符号串i+i*i的分析过程的分析过程步步骤骤分析栈分析栈余留输余留输入串入串分析表元素分析表元素所用产生所用产生式式1234567891011121314151617 #E#ET#ETF#ETi#ET#E#ET+#ET#ETF#ETi#ET#ETF*#ETF#ETi#ET#E# i+i*i#i+i*i#i+i*i#i+i*

46、i#+i*i#+i*i#+i*i#i*i#i*i#i*i#*i#*i#i#i# # POP,PUSH(ET)POP,PUSH(TF)POP,PUSH(i)POP,NEXTSYMPOPPOP,PUSH(ET+)POP,NEXTSYMPOP,PUSH(TF)POP,PUSH(i)POP ,NEXTSYMPOP,PUSH(TF*)POP ,NEXTSYMPOP,PUSH(i)POP ,NEXTSYMPOPPOPaccept ETETFTFi TE+TE TFTFi T*FT Fi TE表表4.2中输出的产生式序中输出的产生式序列构成对输入符号串的列构成对输入符号串的最左推导。按此产生式最左推导。按此

47、产生式序列构造输入符号串序列构造输入符号串i+i*i的最左推导过程如下：的最左推导过程如下：E E = = TETE = = FTE FTE = = iTEiTE = = iEiE = = i+TEi+TE = = i+FTEi+FTE= = i+iTEi+iTE = = i+ii+i* *FTEFTE = = i+ii+i* *iTE iTE = = i+ii+i* *iEiE = = i+ii+i* *i i 4.4.1 LL(1)4.4.1 LL(1)分析的基本方法分析的基本方法4.4.2 LL(1)4.4.2 LL(1)分析表的构造方法分析表的构造方法 对于不同的对于不同的LL(1)文

48、法，文法，LL(1)的分析算法是相同的，不的分析算法是相同的，不同的仅仅是分析表。显然，如何根据文法来构造分析表同的仅仅是分析表。显然，如何根据文法来构造分析表是是LL(1)分析的关键。分析的关键。 对于任意给定的已化简的文法对于任意给定的已化简的文法G，为了构造分析表，首，为了构造分析表，首先要求出每个非终结符号的先要求出每个非终结符号的FOLLOW集合和每个后选式集合和每个后选式的的FIRST集合。然后对文法集合。然后对文法G中的每个产生式中的每个产生式A，按，按下列规则确定分析表中的元素下列规则确定分析表中的元素M： 1) 对对FIRST()中的每个终结符中的每个终结符a，置，置MA，a

49、=“POP，PUSH()”，其中，其中为为的倒置。的倒置。2) 若若FIRST()，则对属于，则对属于FOLLOW(A)的每个符号的每个符号b(b为终结符或为终结符或#)，置，置MA，b=“POP”。3) 把把M中的所有中的所有Ma，a置为置为“POP，NEXTSYM”。4) 把把M中所有不按规则中所有不按规则1、2定义的元素均置为空或定义的元素均置为空或“ERROR”。 4.4.2 LL(1)4.4.2 LL(1)分析表的构造方法分析表的构造方法 例如，有文法例如，有文法ETE，E+TE，E，TFT，T*FT，T，F(E)|i，对规则对规则ETE：FIRST(TE)= (，i)，那么在分析表

50、的，那么在分析表的符号符号E所在的行、符号所在的行、符号(和和i所在的列对应的位置分别填入所在的列对应的位置分别填入“POP,PUSH(ET)”,见表见表4.1的的E行。行。对规则对规则E+TE：FIRST(+TE)=+，在符号，在符号E行符号行符号+列对应的位置填入列对应的位置填入“POP,PUSH(ET+)” ，见表，见表4.1的的E行。行。对规则对规则E：因为：因为FIRST()，FOLLOW(E)=，#，所以在符号所以在符号E行符号行符号)和和#列对应的位置填入列对应的位置填入“POP”，见，见表表4.1的的E行。行。对于一个文法，若按上述方法构造的分析表对于一个文法，若按上述方法构造

51、的分析表M不含多重不含多重定义，则称它是一个定义，则称它是一个LL(1)文法。文法。 4.2.3 LL(1)4.2.3 LL(1)分析的主要问题及解决方法分析的主要问题及解决方法 1、左递转成右递归、左递转成右递归 LL(1)分析不能处理左递归文法，必须将左递归文法变成右递归分析不能处理左递归文法，必须将左递归文法变成右递归文法，其变换方法如下：文法，其变换方法如下：1） 对形如对形如U:=x|y|z|Uv的直接左递归文法规则，增加一个新的的直接左递归文法规则，增加一个新的非终结符号非终结符号U，令，令U为左递归规则中的不含左递归符号的部分加为左递归规则中的不含左递归符号的部分加上新的非终结符

52、号上新的非终结符号U，即，即U:= (x|y|.|z )U。2） 新的非终结符号新的非终结符号U有两个侯选式，一为含左递归符号的部分有两个侯选式，一为含左递归符号的部分去掉含左递归符号，再加上新的非终结符号去掉含左递归符号，再加上新的非终结符号U，即，即U:=vU。另。另一个为一个为，即，即U:=。按上面的两步，我们就可将左递归规则改成等价的右递归规则。按上面的两步，我们就可将左递归规则改成等价的右递归规则。 例如，对左递归规则例如，对左递归规则EE+T|T，如果像递归下降分析那样改成，如果像递归下降分析那样改成 ET+T无法形成逆序入栈，但可改成右递归：令无法形成逆序入栈，但可改成右递归：令

53、E为新的非终为新的非终结符号，则等价的右递归规则为：结符号，则等价的右递归规则为：ETE，E+TE| 实际上，在递归下降分析方法中，也可将左递归规则改成右递归实际上，在递归下降分析方法中，也可将左递归规则改成右递归进行处理。进行处理。 2、解决分析表多重定义问题、解决分析表多重定义问题若一个若一个LL(1)文法的分析表不出现多重定义，当且仅当对于文文法的分析表不出现多重定义，当且仅当对于文法法G的每个非终结符的每个非终结符A的任何两条不同规则的任何两条不同规则A| ，下面条件，下面条件成立：成立：FIRST()FIRST()= 即头符号集不相交。即头符号集不相交。假若假若=*，那么，那么，FI

54、RST()FOLLOW(A)=，即，即所能推所能推出的符号串的头符号集中的元素不能出现在出的符号串的头符号集中的元素不能出现在FOLLOW(A)中。中。如果出现了相交的情况，那么分析表必然有多重定义。这个问如果出现了相交的情况，那么分析表必然有多重定义。这个问题有时可通过提取公因子，增加新的非终结符号来解决题有时可通过提取公因子，增加新的非终结符号来解决(见递见递归下降的问题解决方法归下降的问题解决方法)。 4.2.3 LL(1)4.2.3 LL(1)分析的主要问题及解决方法分析的主要问题及解决方法 例如，规则：例如，规则：T(E)|a(E)|a T(E)|a(E)|a 可改成：可改成：T(E)|aTT(E)|aT，T(E)|T(E)| 4.2.3 LL(1)4.2.3 LL(1)分析的主要问题及解决方法分析的主要问题及解决方法 但并非所有的文法都可用此法解决分析表的多重定义