第4章 语法分析—自顶向下分析

1、第第4 4章章 语法分析语法分析自顶向下分析自顶向下分析 Pursue breakthroughs in your life. 追求自我的突破。追求自我的突破。第四章第四章 语法分析语法分析自顶向下分析自顶向下分析(P61)(P61) n4.1 自顶向下分析方法自顶向下分析方法n4.2 FIRST集合和集合和FOLLOW集合集合n4.3 递归下降分析递归下降分析n4.4 LL(1)分析方法分析方法学学 习习 重重 点点 nFIRST集合和集合和FOLLOW集合的求法集合的求法n递归子程序的构造方法递归子程序的构造方法 nLL(1)文法及其分析表的构造方法文法及其分析表的构造方法 第四章第四章

2、语法分析语法分析自顶向下分析自顶向下分析 n语法语法：是指如何由语言基本符号组成程序中各个语法：是指如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则。成分（包括程序）的一组规则。n 语法分析与词法分析的区别语法分析与词法分析的区别：（1）都是对输入符号串的识别；）都是对输入符号串的识别；（2）词法分析的输入串是一个单词；）词法分析的输入串是一个单词；（3）语法分析的输入串是一个句子或者说是一个程序。）语法分析的输入串是一个句子或者说是一个程序。 n语法分析任务语法分析任务：检查源程序语法上是否正确，并生成：检查源程序语法上是否正确，并生成相应的内部表示（如分析树）供下一阶段使用。

3、相应的内部表示（如分析树）供下一阶段使用。n例例 对于对于C程序语句程序语句“if (a10) b=5；”，（1）词法分析：识别出了）词法分析：识别出了if、(、a、等单词符号；等单词符号；（2）语法分析：检查这些单词之间的搭配、结构是否正）语法分析：检查这些单词之间的搭配、结构是否正确，例如确，例如if后面是否为后面是否为(，(后面是否为正确的表达式等。后面是否为正确的表达式等。 第四章第四章 语法分析语法分析自顶向下分析自顶向下分析 n语法分析方法的分类语法分析方法的分类（分类标准是按照识别句（分类标准是按照识别句子时建立语法树的方法）：子时建立语法树的方法）： 分析法分析法分析法分析法分

4、析法算符优先分析法简单优先分析法优先分析法自底向上带回溯递归下降分析法分析法不带回溯自顶向下语法分析)1()1()1()0()(LALRLRSLRLRLRKLL4.1自顶向下的分析方法自顶向下的分析方法（P61P61） n自顶向下的分析方法自顶向下的分析方法就是从文法的开始符号出发，就是从文法的开始符号出发，按最左推导方式向下推导，试图推导出要分析的输按最左推导方式向下推导，试图推导出要分析的输入串。即：入串。即： 开始符号开始符号 输入符号串输入符号串+n自底向上的分析方法自底向上的分析方法从输入符号串开始，按最左从输入符号串开始，按最左归约方式向上归约到文法的开始符号。即：归约方式向上归约

5、到文法的开始符号。即： 开始符号开始符号 输入符号串输入符号串 归约归约SaASaAaaSbAaaSbbaaaabbaa自上而下自上而下自底向上自底向上输入串输入串开始符号开始符号图示：图示：自上而下分析与自底向上分析自上而下分析与自底向上分析4.2 FIRST集合和集合和FOLLOW集合集合（P62P62）nFIRST集合定义集合定义：假定假定是文法是文法G的任一符号串，的任一符号串，则：则： FIRST()=a | a，aVt若若 , 则规定则规定FIRST()。 *n实际上，实际上，FIRST()就是从就是从可能推导出的所有开可能推导出的所有开头终结符号或头终结符号或。n文法符号的文法符

6、号的FIRST集合构造方法集合构造方法： 对于文法中的对于文法中的符号符号XV，其，其FIRST(X)集合可反复集合可反复应用下列规则计算，直到其应用下列规则计算，直到其FIRST(X)集合不再增大为集合不再增大为止：止： 1)若若XVt，则，则FIRST(X)=X。2)若若XVn，且具有形如，且具有形如Xa的产生式的产生式(aVt)，或具，或具有形如有形如X的产生式，则把的产生式，则把a或或加进加进FIRST(X)。3)设设G中有形如中有形如XY1Y2Yk的产生式，若的产生式，若Y1Vn，则把则把FIRST(Y1)中的一切非中的一切非符号加进符号加进FIRST(X)；对于；对于一切一切2ik

7、，若，若Y1，Y2，Yi-1均为非终结符号，且均为非终结符号，且FIRST(Yj)，1ji-1，则将，则将FIRST(Yi)中的一切非中的一切非符符号加进号加进FIRST(X)；但若对一切；但若对一切1ik，均有，均有FIRST(Yi)，则将，则将符号加进符号加进FIRST(X)。 n文法符号的文法符号的FIRST集合构造方法集合构造方法： 对于文法中的对于文法中的符号符号XV，其，其FIRST(X)集合可反复集合可反复应用下列规则计算，直到其应用下列规则计算，直到其FIRST(X)集合不再增大为集合不再增大为止：止： 1)若若X为终结符为终结符，则将，则将X加入加入FIRST(X)集合中。集

8、合中。2)若若X为非终结符为非终结符，且具有形如，且具有形如Xa的产生式的产生式(aVt)，或具有形如或具有形如X的产生式，则把的产生式，则把a或或加进加进FIRST(X)。3)设设X为非终结符为非终结符且有形如且有形如XY1Y2Yk的产生式，若的产生式，若Y1Vn，则把，则把FIRST(Y1)中的一切非中的一切非符号加进符号加进FIRST(X)；对于一切对于一切2ik，若，若Y1，Y2，Yi-1均为非终结符号，且均为非终结符号，且FIRST(Yj)，1ji-1，则将，则将FIRST(Yi)中的一切非中的一切非符号加符号加进进FIRST(X)；但若对一切；但若对一切1ik，均有，均有FIRST

9、(Yi)，则将，则将符号加进符号加进FIRST(X)。 n对于文法对于文法G的任一的任一符号串符号串=X1X2Xn可按下列步可按下列步骤构造其骤构造其FIRST()集合：集合：1)置置FIRST()=;2)将将FIRST(X1)中的一切非中的一切非符号加进符号加进FIRST()；3)若若FIRST(X1)，将，将FIRST(X2)中的一切非中的一切非符符号加进号加进FIRST()；若若FIRST(X1)和和FIRST(X2)，将将FIRST(X3)中的一切非中的一切非符号加进符号加进FIRST()；其余；其余类推。类推。4)若对于一切若对于一切1in，FIRST(Xi)，则将，则将符号加符号加

10、进进FIRST()。 4.2 FIRST集合和集合和FOLLOW集合集合n例例4-1(P62) 有有文法：文法： ETE E+TE E TFT T*FT T F(E)|i 求文法中非求文法中非终结符号以及终结符号以及各各产生式右部产生式右部符号符号串的串的FIRST集。集。解：该文法的非终结符号有解：该文法的非终结符号有E、E、T、T和和F。FIRST(E)=FIRST(TE) =FIRST(FTE)= ( ，i FIRST(+TE)= + FIRST()=FIRST(E)=FIRST(+TE) FIRST()=+ ，FIRST(T)=FIRST(FT)= ( ，i FIRST(*FT)= *

11、 FIRST(T)=FIRST(*FT) FIRST()=* ，FIRST(E)= ( FIRST(i)= i FIRST(F) =FIRST(E) FIRST(i)=( ，i4.2 FIRST集合和集合和FOLLOW集合集合n例例S:=aABbcd|A:=ASd|B:=SAh|eC|C:=Sf|Cg| 求此文法的求此文法的每一个非终结符每一个非终结符号的号的FIRST集。集。解：解：FIRST(S)=FIRST(aABbcd)FIRST() =a=a,FIRST(A)=FIRST(ASd)FIRST() =a,d=a,d, FIRST(B)=FIRST(SAh)FIRST(eC) FIRST

12、() =a,d,he=a,d,h,e,FIRST(C)=FIRST(Sf)FIRST(Cg) FIRST() =a,fa,f,g=a,f,g,4.2 FIRST集合和集合和FOLLOW集合集合n练习练习 S:=aAcB|BdA:=AaB|cB:=bBcA|b| 求此文法的求此文法的每一个非终结符每一个非终结符号的号的FIRST集。集。解：解：FIRST(S)=FIRST(aAcB)FIRST(Bd)=ab,d=a,b,dFIRST(A)=FIRST(AaB)FIRST(c)=cc=cFIRST(B)=FIRST(bBcA)FIRST(b) FIRST()=bb=b, 4.2 FIRST集合和集

13、合和FOLLOW集合集合nFOLLOW集合定义集合定义（P63）：）： 假定假定S是文法的开始符号，对于是文法的开始符号，对于G的任何非的任何非终结符号终结符号A，则：，则： FOLLOW(A)= a | S Aa， aVt 若若S A，则规定，则规定#FOLLOW(A)。 *n从定义可看出，从定义可看出，FOLLOW(A)就是在所有句型就是在所有句型中出现在紧接中出现在紧接A之后的之后的终结符号或终结符号或#。注意：在。注意：在FOLLOW集合中无集合中无。 4.2 FIRST集合和集合和FOLLOW集合集合n对于文法中的符号对于文法中的符号AVn，其，其FOLLOW(A)集合集合可反复应用

14、下列规则计算，直到其可反复应用下列规则计算，直到其FOLLOW(A)集集合不再增大为止：合不再增大为止：1) 对于文法的对于文法的开始符号开始符号S，令，令#FOLLOW(S)2) 若若G中有形如中有形如BA 的产生式，且的产生式，且 ，则，则将将FIRST()中的一切非中的一切非符号加进符号加进FOLLOW(A)。3) 若若G中有形如中有形如BA或或BA 的产生式，且的产生式，且FIRST()，则，则FOLLOW(B)中的全部元素均属中的全部元素均属于于FOLLOW(A)，即即FOLLOW(B) FOLLOW(A) 。例例 设文法设文法GS:S:=SbA|aAA:=BcB:=Sb求此文法的每

15、一个非终结符号的求此文法的每一个非终结符号的FOLLOW集。集。解：解：1. 因为因为S为文法的开始符号，所以为文法的开始符号，所以#FOLLOW(S);由由S:=SbA，有，有FIRST(bA)=bFOLLOW(S); 由由B:=Sb，有，有FIRST(b)=bFOLLOW(S);因此，因此，FOLLOW(S)=b,#。2. 由由S:=SbA或或S:=aA，有，有FOLLOW(S) FOLLOW(A)。因此，。因此，FOLLOW(A)=b,#。3. 由由A:=Bc，有，有FIRST(c)=cFOLLOW(B)。因此，。因此，FOLLOW(B)=c。 4.2 FIRST集合和集合和FOLLOW

16、集合集合n例例4-2（P63） 有有文法文法 ETE，E+TE，E，TFT， T*FT，T，F(E)|i，求各非终结，求各非终结符号的符号的FOLLOW集。集。解：解：FOLLOW(E)=#FIRST()=) ， #FOLLOW(E)= FOLLOW(E)=) ，# FOLLOW(T)= (FIRST(E)-) FOLLOW(E) FOLLOW(E)= + ， ) ， # FOLLOW(T)= FOLLOW(T)= + ， ) ， # FOLLOW(F)=(FIRST(T)-) FOLLOW(T) FOLLOW(T) = *，+，) ，# 4.2 FIRST集合和集合和FOLLOW集合集合n练

17、习练习 已知文法已知文法GS: S:=AA:=BAA:=iBA| B:=CBB:=+CB| C:=)A*|(求求FOLLOW(C)。解：解：FOLLOW(C)=(FIRST(B)-)FOLLOW(B)FOLLOW(B) =+,i,*,#自顶向下语法分析遇到的问题自顶向下语法分析遇到的问题n (1)左递归问题左递归问题 当文法中出现左递归时（存在非终结符号当文法中出现左递归时（存在非终结符号U，对于它有对于它有U:=U（直接左递归），或（直接左递归），或U U（间（间接左递归），它会使分析过程陷入无限循环。接左递归），它会使分析过程陷入无限循环。 n (2)回溯问题回溯问题 如果对于同一个非终结

18、符号，存在若干个产生如果对于同一个非终结符号，存在若干个产生式右部式右部(如如U:=x1|x2|xn)时，要对时，要对U展开，那么按展开，那么按哪一个产生式右部展开呢？即如何确定替换哪一个产生式右部展开呢？即如何确定替换U的的xi。如果选择错误，将导致回溯。如果选择错误，将导致回溯。+回溯示例回溯示例n例例 设文法设文法GA:A:=aB|aCB:=bC:=c推导句子推导句子ac将导致回溯。将导致回溯。AaBab AaCac 回溯示例回溯示例自顶向下语法分析问题的解决方法自顶向下语法分析问题的解决方法n (1)消除消除左递归左递归 消除直接左递归消除直接左递归方法方法1：采用扩充：采用扩充BNF

19、范式范式 设有文法产生式设有文法产生式 U:=Ux|y 可改写为可改写为: U:=yx方法方法2：引进新的非终结符号：引进新的非终结符号 设有文法产生式设有文法产生式 U:= Ux1|Ux2|Uxm|y1|y2|yn其中，其中，yi(i=1,2,n)均不以符号均不以符号U为首，引进一个新的非为首，引进一个新的非终结符号终结符号U, 将上述产生式等价变换为将上述产生式等价变换为: U:= y1U|y2U|ynU U:= x1U|x2U|xmU|自顶向下语法分析问题的解决方法自顶向下语法分析问题的解决方法n例例4-4(P65) 有文法：有文法：E:=E+T|E-T|T ，T:=T*F|T/F|F，

20、为其设计递归分析程序。，为其设计递归分析程序。方法方法1：采用扩充：采用扩充BNF范式范式 E:=E+T|E-T|T 可改成可改成 E:=T+T| -T T:=T*F|T/F|F 可改成可改成 T:=F*F| /F方法方法2：引进新的非终结符号：引进新的非终结符号E:=E+T|E-T|T 可改成可改成 E:=TE，E:=+TE|-TE|T:=T*F|T/F|F 可改成可改成 T:=FT，T:=*FT|/FT| 解：先消除文法中的直接左递归。解：先消除文法中的直接左递归。自顶向下语法分析问题的解决方法自顶向下语法分析问题的解决方法n (2)避免回溯避免回溯 为了避免回溯，对于文法中的为了避免回溯

21、，对于文法中的任一非终结符号任一非终结符号U，若若U:=x1|x2|xn，要求满足以下两个条件，要求满足以下两个条件： 相对于相对于x1,x2,xn的各符号串的终结首符号集总是的各符号串的终结首符号集总是两两互不相交的，即两两互不相交的，即 FIRST(xi)FIRST(xj)= (ij) 因为每一个因为每一个xi推出的第一个终结符号均不相同，推出的第一个终结符号均不相同，它能保证只会选择惟一的一个它能保证只会选择惟一的一个xi来替换来替换U。n例例 设文法设文法GA：A:=aB|aC，B:=b，C:=cFIRST(aB)FIRST(aC)=aa=a 采用自顶向下的语法分析时会引起回溯，例如推

22、导句采用自顶向下的语法分析时会引起回溯，例如推导句子子ac将导致回溯。将导致回溯。自顶向下语法分析问题的解决方法自顶向下语法分析问题的解决方法n (2)避免回溯避免回溯 如果如果xj ，则有可能选择此，则有可能选择此xj来替换来替换U,而让句型而让句型中中U后面的第一个终结符号与当前输入符号匹配，这样后面的第一个终结符号与当前输入符号匹配，这样有可能回溯。若规定文法不含有可能回溯。若规定文法不含规则规则 ，则对文法的要求，则对文法的要求太高，因此用太高，因此用 FIRST(xi)FOLLOW(U)= 来限制文法，保证只会选择惟一的一个来限制文法，保证只会选择惟一的一个xi来替换来替换U。 *Z

23、U xiaZU xj a (1 )(2 )n例例 设文法为：设文法为：S:=bAB，A:=aC| ，B:=aB| ,C:=cFIRST(aC)FOLLOW(A)=aa,#=a采用自顶向下的语法分析时会引起回溯，例如推导句子采用自顶向下的语法分析时会引起回溯，例如推导句子baa将导致回溯。将导致回溯。 SB(1 )(2 )bAaCcSBbAaBaB 自顶向下语法分析问题的解决方法自顶向下语法分析问题的解决方法n (2)避免回溯避免回溯以上避免回溯的两个条件等价于：以上避免回溯的两个条件等价于： SELECT(U:=xi)SELECT(U:=xj) = (ij)其中：其中：SELECT(U:= x

24、k)定义为：定义为：(i,j,k=1,2,n)SELECT(U:=xk)自顶向下语法分析问题的解决方法自顶向下语法分析问题的解决方法n 消除文法回溯的方法：消除文法回溯的方法： 消除文法的左递归；消除文法的左递归； 提公共因子；提公共因子； 例如例如U:=xy|xz，则提公共因子，有，则提公共因子，有U:=x(y|z),再再引进新的非终结符号引进新的非终结符号V，U:= xy|xz可改写为：可改写为：U:=xV，V:=y|z。 根据文法的具体情况进行等价变换。根据文法的具体情况进行等价变换。采用自顶向下语法分析法对文法的要求采用自顶向下语法分析法对文法的要求n 采用自顶向下语法分析法要求文法满

25、足采用自顶向下语法分析法要求文法满足压缩、无压缩、无左递归、无回溯左递归、无回溯这三个条件，称满足这三个条件这三个条件，称满足这三个条件的文法为的文法为LL(1)文法文法。证明：因为是左递归文法，所以必存在左递归的非证明：因为是左递归文法，所以必存在左递归的非终结符终结符A及形如及形如A:=A|（可为可为 ）。由于）。由于SELECT(A:=A)SELECT(A:=) ，所以左递，所以左递归文法不满足归文法不满足LL(1)文法条件。文法条件。推论推论1：任何左递归文法均不是：任何左递归文法均不是LL(1)文法。文法。采用自顶向下语法分析法对文法的要求采用自顶向下语法分析法对文法的要求 推论推论

26、2：任何：任何LL(1)文法均为无二义性文法。文法均为无二义性文法。证明：证明：LL(1)文法在分析句子过程的每一步，永远文法在分析句子过程的每一步，永远只有惟一的分析动作可进行。现在，假设文法只有惟一的分析动作可进行。现在，假设文法G是是二义性文法，则存在句子二义性文法，则存在句子，它有两棵不同的语法，它有两棵不同的语法树，即存在着两个不同的最左推导。从而可知，用树，即存在着两个不同的最左推导。从而可知，用LL(1)方法对句子方法对句子进行分析的某步，存在两种不同进行分析的某步，存在两种不同的产生式可用于推导，且均能正确进行语法分析，的产生式可用于推导，且均能正确进行语法分析，即即LL(1)

27、分析动作存在不确定性。这与分析动作存在不确定性。这与LL(1)的性质的性质相矛盾。所以，文法相矛盾。所以，文法G不是不是LL(1)文法。文法。采用自顶向下语法分析法对文法的要求采用自顶向下语法分析法对文法的要求n 例例 验证下列文法是否为验证下列文法是否为LL(1)文法。文法。GS: S:=AB|CDa A:=ab|c B:=dD| C:=eC| D:=fD|f解：显然，文法解：显然，文法G已压缩且无左递已压缩且无左递归。下面判断其是否有回溯。归。下面判断其是否有回溯。由由D:=fD|f，有：，有：SELECT(D:=fD)SELECT(D:=f)=FIRST(fD)FIRST(f)=ff=f

28、 该文法不是该文法不是LL(1)文法。文法。采用自顶向下语法分析法对文法的要求采用自顶向下语法分析法对文法的要求n 练习练习（见（见P77习题习题4的第的第2小题）小题） 有文法有文法GA： A:=aABe| B:=Bb|b判断该文法是判断该文法是LL(1)文法吗？文法吗？ 解：解：文法中存在左递归文法中存在左递归B:=Bb该文法不是该文法不是LL(1)文法。文法。4.3 递归下降分析递归下降分析(P64)(P64)n 递归下降分析递归下降分析(或或递归子程序分析递归子程序分析)的基本方法的基本方法 其思路极为简单：其思路极为简单：为每个非终结符号构造一个子程为每个非终结符号构造一个子程序，以

29、完成该非终结符号所对应的语法成分的分析和序，以完成该非终结符号所对应的语法成分的分析和识别。识别。1. 若若U的右部的右部只有一个候选式只有一个候选式，则按从左向右的顺序构造，则按从左向右的顺序构造U的识别过程代码。的识别过程代码。 （1 1）若有终结符号，则判断与输入符号是否匹配，如果）若有终结符号，则判断与输入符号是否匹配，如果相同，继续读入下一符号，否则就意味着有语法错误；相同，继续读入下一符号，否则就意味着有语法错误； （2 2）若有非终结符号，则调用该符号的子程序。）若有非终结符号，则调用该符号的子程序。2. 若若U的右部的右部有多个候选式有多个候选式，则根据每个候选式的第一个符，则

30、根据每个候选式的第一个符号确定该候选式分支。号确定该候选式分支。3. 只有输入串的每一个符号全部匹配成功，且正确返回时，只有输入串的每一个符号全部匹配成功，且正确返回时，该语法成分才算真正获得识别。该语法成分才算真正获得识别。4.3 递归下降分析递归下降分析n例例4-3(P64) 考虑文法考虑文法Z:=(U)|aUb ，U:=dZ|e，为其构造递，为其构造递归下降分析子程序。归下降分析子程序。并对输入串并对输入串aebaeb进行语进行语法分析法分析 。解：文法中有两个非终结符号解：文法中有两个非终结符号Z和和U，那么我们需要分别编，那么我们需要分别编两个过程来完成两个过程来完成Z和和U规则的规

31、则的识别。识别。 对于规则对于规则Z:=(U)|aUb，右部有两个候选式，因此，右部有两个候选式，因此，U的识别过程有两个分支，分别的识别过程有两个分支，分别根据符号根据符号(和和a来判别。来判别。 同理对规则同理对规则U:=dZ|e设计设计的过程也分为两个分支。的过程也分为两个分支。Z:=(U)|aUb非终结符号非终结符号Z的分析程序的分析程序 U:=dZ|e非终结符号非终结符号U的分析程序的分析程序 Z:=(U)|aUbU:=dZ|e输入串为输入串为aeb，分析过程为：，分析过程为： ZaUbaeb aeeb#b4.3 递归下降分析递归下降分析n例例4-3(P64) 考考虑文法虑文法Z:=

32、(U)|aUb ，U:=dZ|e，为其，为其构造递归下降构造递归下降分析子程序。分析子程序。并对输入串并对输入串aebaeb进行语法分析进行语法分析 。总 控 程 序P(Z ) # validabP(U )eP(Z )abP(U )eaeb递归下降分析过程递归下降分析过程aeb的语法树的语法树n 例例 设文法设文法GS:S:=(A)|aAbA:=eA|dSAA:=dA| 试构造该文试构造该文法的递归子程序法的递归子程序(或递归下降分析或递归下降分析程序程序)。解：由解：由S:=(A)|aAb,则则P(S)为：为：ch = (?R E A D (ch ) ch = a?YNP (A )ch =

33、)?R E A D (ch )YN errorR E A D (ch )YNerrorP (A )ch = b ?R E A D (ch )YN error4.3 递归下降分析递归下降分析由由A:=eA|dSA,则则P(A)为：为：n 例例 设文法设文法GS:S:=(A)|aAbA:=eA|dSAA:=dA| 试构造该文试构造该文法的递归子程序法的递归子程序(或递归下降分析或递归下降分析程序程序)。c h = e ?R E A D (c h ) c h = d ?YNR E A D (c h )YNe r r o rP (S )P (A ) )4.3 递归下降分析递归下降分析由由A:=dA|

34、，则则P(A)为：为：n 例例 设文法设文法GS:S:=(A)|aAbA:=eA|dSAA:=dA| 试构造该文试构造该文法的递归子程序法的递归子程序(或递归下降分析或递归下降分析程序程序)。ch=d?READ(ch) ch FOLLOW (A) )?YNYNerrorP(A) )4.3 递归下降分析递归下降分析n例例4-4(P65) 有文法：有文法：E:=E+T|E-T|T ，T:=T*F|T/F|F，为其设计递归分析程序。，为其设计递归分析程序。解：先消除文法中的直接左递归：解：先消除文法中的直接左递归： E:=E+T|E-T|T 可改成可改成 E:=T+T| -T T:=T*F|T/F|

35、F 可改成可改成 T:=F*F| /F注意注意“”和和“”括起来的内容采用循环设计。括起来的内容采用循环设计。 E:=T|E+T|E-T改成改成E:=T+T|-TT:=F|T*F|T/F改成改成T:=F*F| /F E的分析程序的分析程序 T的分析程序的分析程序 4.3 递归下降分析递归下降分析n递归子程序分析法的优缺点递归子程序分析法的优缺点主要优点主要优点：可以根据文法规则直接写出相应的可以根据文法规则直接写出相应的识别程序，各子程序的流程图几乎就是文法规则识别程序，各子程序的流程图几乎就是文法规则的图解描述，简单明了，易于掌握。的图解描述，简单明了，易于掌握。主要缺点主要缺点：大量的相互

36、嵌套的递归子程序的频大量的相互嵌套的递归子程序的频繁调用，使分析器的运行速度相当慢。繁调用，使分析器的运行速度相当慢。 4.4 LL(1)分析方法分析方法(P70)(P70) nLL(1)分析法的含义分析法的含义：第一个第一个L表示自左向右顺序扫描输入符号串表示自左向右顺序扫描输入符号串第二个第二个L表示分析过程产生一个句子的最左推导表示分析过程产生一个句子的最左推导括号中的括号中的1表示每进行一步推导，只需要表示每进行一步推导，只需要向前查向前查看看1个输入符号个输入符号，便能确定当前所应选用的规则，便能确定当前所应选用的规则 nLL(k)分析法的含义分析法的含义： 两个两个L的含义同上，括

37、号中的的含义同上，括号中的k表示每进行一表示每进行一步推导，步推导，需要向前查看需要向前查看k个输入符号个输入符号才能唯一确才能唯一确定当前应选择的规则。定当前应选择的规则。 4.4 LL(1)分析方法分析方法 nLL(1)分析程序的结构分析程序的结构 LL(1)分析器由一个总控程序、一张分析表和一个分析栈组成。分析器由一个总控程序、一张分析表和一个分析栈组成。 是一个二维表，它概是一个二维表，它概括了文法的全部信息，括了文法的全部信息，指出了分析器应采取指出了分析器应采取的动作。的动作。存放一系列存放一系列文法符号。文法符号。分析开始时，分析开始时，先将先将# #入栈，入栈，然后再将文然后再

38、将文法的开始符法的开始符号入栈。号入栈。分析过程中使用分析过程中使用的产生式序列。的产生式序列。要分析的输入符号串。串的末尾放置一个要分析的输入符号串。串的末尾放置一个特殊符号特殊符号# #，表示结束。，表示结束。# #不是终结符号。不是终结符号。根据栈顶符根据栈顶符号和当前的号和当前的输入符号，输入符号，按照分析表按照分析表的指示来完的指示来完成分析过程。成分析过程。4.4 LL(1)分析方法分析方法分析表分析表M：是一个二维表，可用一个二维数组是一个二维表，可用一个二维数组MA，a来表示，来表示，它指出了分析器应采取的动作。它指出了分析器应采取的动作。分析表中的每分析表中的每一行是文法中一

39、行是文法中的一个非终结的一个非终结符号、终结符符号、终结符号或号或#；分析表每一列分析表每一列是文法的一个是文法的一个终结符号或终结符号或#。因此，分析表的列数是因此，分析表的列数是终结符号的个数加终结符号的个数加1；行数是行数是非终结符号和终结符号的数目加非终结符号和终结符号的数目加1。p1) 分析开始时，首先将符号分析开始时，首先将符号#及文法的开始符号及文法的开始符号S依次置于依次置于分析栈的底部，并把各指示器调整至起始位置。然后，反复分析栈的底部，并把各指示器调整至起始位置。然后，反复执行第二步的操作。执行第二步的操作。 输入符号串：输入符号串： #ana2a1分析栈：分析栈：#S 分

40、析开始时状况分析开始时状况 p2) 假设分析的某一步，分析栈及余留的符号串，则根据假设分析的某一步，分析栈及余留的符号串，则根据栈顶的符号栈顶的符号Xm，采取下列动作：，采取下列动作： aiai+1 an#X1X2Xm-1Xm 分析进行中的状况分析进行中的状况 4.4 LL(1)分析方法分析方法-工作过程工作过程(1)若若XmVn，则查分析表的，则查分析表的Xm所在行和所在行和ai所在列，假所在列，假设设MXm,ai为为POP,PUSH（WVU），则将，则将Xm出栈，并将出栈，并将WVU入栈，这意味着入栈，这意味着使用了规则使用了规则XmUVW；MXm,ai为为POP，则将，则将Xm出栈，这意

41、味着出栈，这意味着使用了规则使用了规则Xm ；若；若MXm，ai为空或为空或ERROR，则出错。，则出错。 aiai+1 an#XmUVW(2)若若Xm=ai#，表示栈顶与扫描的符号匹配，则查分析，表示栈顶与扫描的符号匹配，则查分析表为表为POP，NEXTSYM，则栈顶符号，则栈顶符号Xm出栈，输入指针出栈，输入指针指向下一个符号。指向下一个符号。( 3 ) 若若Xm=ai= #，表示输入串完全匹配，分析成功。，表示输入串完全匹配，分析成功。 #X1X2Xm-1WVU #X1X2Xm-1Xm #X1X2Xm-1 Xmn例例(P72) 算术表达式文法算术表达式文法ETE，E+TE，E，TFT,T

42、*FT,T,F(E)|i，该文法的，该文法的LL(1)分析表为分析表为:POP：将栈顶元将栈顶元素从栈内弹出。素从栈内弹出。PUSH：将括将括号内的符号串号内的符号串压入栈。压入栈。NEXTSYM：将读：将读符号指针指向下符号指针指向下一个符号。一个符号。ACCEPT：分析成功分析成功分析表的动作含义：分析表的动作含义：n例例4-7(P73) 根据表根据表4-1，对符号串对符号串i+i*i进行分析。进行分析。符号串符号串i+i*i的分析过程的分析过程i+i*i的最左推的最左推导：导：ETEFTE iTEiEi+TEi+FTEi+iTEi+i*FTEi+i*iTE i+i*iE i+i*i 4.

43、4 LL(1)分析方法分析方法n对文法对文法G中的每个产生式中的每个产生式A，按下列规则确定，按下列规则确定LL(1)分析表中的元素分析表中的元素M(P74，LL(1)分析表的构造方法分析表的构造方法)： 1)对对FIRST()中的每个终结符中的每个终结符a（即（即 不是不是时）时），置，置MA,a=“POP，PUSH()”或或MA，a=“A” ，其中，其中为为的倒置。的倒置。2)若若FIRST()（即（即A），则对属于，则对属于FOLLOW(A)的每个符号的每个符号b(b为终结符或为终结符或#)，置，置MA,b=“POP”或或MA,b=“A” 。3)把把M中的所有中的所有Ma,a置为置为“P

44、OP，NEXTSYM”， aVt ，置，置M#,#=“ ACCEPT”。（该项可以不要）（该项可以不要）4)把把M中所有不按上述规则定义的元素均置为空或中所有不按上述规则定义的元素均置为空或“ERROR”。 4.4 LL(1)分析方法分析方法n例例有文法有文法ETE，E+TE，E，TFT，T*FT，T，F(E)|i 对规则对规则ETE ：FIRST(TE)= (，i)，那么在分析，那么在分析表的符号表的符号E所在的行、符号所在的行、符号(和和i所在的列对应的位置分别所在的列对应的位置分别填入填入“POP,PUSH(ET)”，见表，见表4-1的的E行。行。 对规则对规则E+TE：FIRST(+T

45、E)=+，在符号，在符号E行符行符号号+列对应的位置填入列对应的位置填入“POP,PUSH(ET+)” ，见表，见表4-1的的E行。行。 对规则对规则E：因为：因为FIRST()，FOLLOW(E)=)，#，所以在符号，所以在符号E行符号行符号)和和#列对应的位置填入列对应的位置填入“POP”，见表见表4-1的的E行。行。 其它规则处理方法相同（略）。其它规则处理方法相同（略）。n对于一个文法，若按上述方法构造的分析表对于一个文法，若按上述方法构造的分析表M不含多重不含多重定义，则称它是一个定义，则称它是一个LL(1)文法文法。 4.4 LL(1)分析方法分析方法n分析表的简化分析表的简化 当

46、压栈的最后一个符号是终结符时，那么下一步的分当压栈的最后一个符号是终结符时，那么下一步的分析动作肯定是这个终结符号出栈。析动作肯定是这个终结符号出栈。n简化方法简化方法 如果压栈的最后一个符号是终结符，那么，这个终结如果压栈的最后一个符号是终结符，那么，这个终结符不入栈，并加入读下一个符号，这样，分析表中所有的符不入栈，并加入读下一个符号，这样，分析表中所有的终结符行都可以去掉。终结符行都可以去掉。删删 除除对表对表4-1的分析表简化后的分析表如下表所示的分析表简化后的分析表如下表所示: E +TET *FTETEETEE E TFTTFT T T T FiF(E)n例例 有文法有文法GS:

47、S:=A，A:=BA，A:=iBA|，B:=CB，B:=+CB|，C:=)A*|(，请构造文法，请构造文法G的的LL(1)分析表。分析表。4.4 LL(1)分析方法分析方法n练习练习 已知文法已知文法GS: S:=(S)S|(1)该文法是该文法是LL(1)文法吗？为什么？文法吗？为什么？(2)请给出该文法的请给出该文法的LL(1)分析表。分析表。(3)若输入符号串是若输入符号串是“()”，请给出其，请给出其LL(1)语法分析语法分析过程。过程。解：解：(1) 显然，文法显然，文法G是经压缩、无左递归文法。下是经压缩、无左递归文法。下面判断它是否有回溯。面判断它是否有回溯。由由S:=(S)S| ，有：，有：SELECT(S:= (S)S)SELECT(S:=)=FIRST(S)S)(FIRST()FOLLOW(S)=(,),#=文法文法G是是LL(1)文法。文法。4.4 LL(1)4.4 LL(1)分析方法分析方法n练习练习 已知文法已知文法GS: S:=(S)S|(1)该文法是该文法是LL(1)文法吗？为什么？文法吗？为什么？(2)请给出该文法的请给出该文法的LL(1)分析表。分析表。(3)若输入符号串是若输入符号串是“()”，请给出其，请给出其LL(1)语法分析语法分析过程。过程。(2) 文法文法G的的LL(1)分析表分析表()#SS:=(S)S S:=S:=