语法分析—自顶向下分析.ppt

1、第4章 语法分析自顶向下分析,Pursue breakthroughs in your life. 追求自我的突破,第四章 语法分析自顶向下分析(P61,4.1 自顶向下分析方法 4.2 FIRST集合和FOLLOW集合 4.3 递归下降分析 4.4 LL(1)分析方法,学 习 重 点,FIRST集合和FOLLOW集合的求法 递归子程序的构造方法 LL(1)文法及其分析表的构造方法,第四章 语法分析自顶向下分析,语法：是指如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则,语法分析与词法分析的区别： 语法分析和词法分析都是对输入符号串的识别，但词法分析的输入符号串是一个单词，而语法

2、分析的输入符号串是一个句子或者说是一个程序,语法分析任务：检查源程序语法上是否正确，并生成相应的内部表示（如分析树）供下一阶段使用,例 对于C程序语句“if (a10) b=5；”，词法分析识别出了if、(、a、等单词符号，而语法分析则要检查这些单词之间的搭配、结构是否正确，例如if后面是否为(，(后面是否为正确的表达式等等,第四章 语法分析自顶向下分析,语法分析方法的分类（分类标准是按照识别句子时建立语法树的方法,回溯示例,4.1自顶向下的分析方法（P61,自顶向下的分析方法就是从文法的开始符号出发，按最左推导方式向下推导，试图推导出要分析的输入串。即： 开始符号 输入符号串,自底向上的分析

3、方法从输入符号串开始，按最左归约方式向上归约到文法的开始符号。即： 开始符号 输入符号串,归约,SaASaAaaSbAaaSbbaaaabbaa,自上而下,自底向上,输入串,开始符号,图示：自上而下分析与自底向上分析,4.2 FIRST集合和FOLLOW集合（P62,FIRST集合定义： 假定是文法G的任一符号串，则： FIRST()=a | a，aVt 若 , 则规定FIRST(,实际上，FIRST()就是从可能推导出的所有开头终结符号或,文法符号的FIRST集合构造方法： 对于文法中的符号XV，其FIRST(X)集合可反复应用下列规则计算，直到其FIRST(X)集合不再增大为止： 1)若X

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

5、止： 1)若X为终结符，则将X加入FIRST(X)集合中。 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(Yi)，则将符号加进FIRST(X,对于文法G的任一符号串=X1X2Xn可按下列步骤构造其FIRST()集合： 1)置FIRST()

6、=; 2)将FIRST(X1)中的一切非符号加进FIRST()； 3)若FIRST(X1)，将FIRST(X2)中的一切非符号加进FIRST()；若FIRST(X1)和FIRST(X2)，将FIRST(X3)中的一切非符号加进FIRST()；其余类推。 4)若对于一切1in，FIRST(Xi)，则将符号加进FIRST(,4.2 FIRST集合和FOLLOW集合,例4-1(P62) 有文法： ETE E+TE E TFT T*FT T F(E)|i 求文法中非终结符号以及各产生式右部符号串的FIRST集,解：该文法的非终结符号有E、E、T、T和F。 FIRST(E)=FIRST(TE) =FIR

7、ST(FTE)= ( ，i FIRST(+TE)= + FIRST()= FIRST(E)=FIRST(+TE) FIRST()=+ ， FIRST(T)=FIRST(FT)= ( ，i FIRST(*FT)= * FIRST(T)=FIRST(*FT) FIRST()=* ， FIRST(E)= ( FIRST(i)= i FIRST(F) =FIRST(E) FIRST(i)=( ，i,4.2 FIRST集合和FOLLOW集合,例 S:=aABbcd| A:=ASd| B:=SAh|eC| C:=Sf|Cg| 求此文法的每一个非终结符号的FIRST集,解： FIRST(S)=FIRST(a

8、ABbcd)FIRST() =a=a, FIRST(A)=FIRST(ASd)FIRST() =a,d=a,d, FIRST(B)=FIRST(SAh)FIRST(eC) FIRST() =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集合,练习 S:=aAcB|Bd A:=AaB|c B:=bBcA|b| 求此文法的每一个非终结符号的FIRST集,解： FIRST(S)=FIRST(aAcB)FIRST(Bd) =ab,d =a,b,d FIRST(A)=FIRST(

9、AaB)FIRST(c) =cc =c FIRST(B)=FIRST(bBcA)FIRST(b) FIRST() =bb =b,4.2 FIRST集合和FOLLOW集合,FOLLOW集合定义（P63）： 假定S是文法的开始符号，对于G的任何非终结符号A，则： FOLLOW(A)= a | S Aa， aVt 若S A，则规定#FOLLOW(A,从定义可看出，FOLLOW(A)就是在所有句型中出现在紧接A之后的终结符号或#。注意：在FOLLOW集合中无,4.2 FIRST集合和FOLLOW集合,对于文法中的符号AVn，其FOLLOW(A)集合可反复应用下列规则计算，直到其FOLLOW(A)集合不

10、再增大为止： 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|aA A:=Bc B:=Sb 求此文法的每一个非终结符号的FOLLOW集,解：1. 因为S为文法的开始符号，所以#FOLLOW(S); 由S:=SbA，有FIRST(bA)=bFOLLOW(S); 由B:=Sb，有FIRST(b)=bFOLLOW

11、(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集合,例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

12、(E)= + ， ) ， # FOLLOW(T)= FOLLOW(T)= + ， ) ， # FOLLOW(F)=(FIRST(T)-) FOLLOW(T) FOLLOW(T) = *，+，) ，,4.2 FIRST集合和FOLLOW集合,练习 已知文法GS: S:=A A:=BA A:=iBA| B:=CB B:=+CB| C:=)A*|( 求FOLLOW(C,解： FOLLOW(C)=(FIRST(B)-) FOLLOW(B)FOLLOW(B) =+,i,*,自顶向下语法分析遇到的问题,1)左递归问题 当文法中出现左递归时（存在非终结符号U，对于它有U:=U（直接左递归），或U U（间接左

13、递归），它会使分析过程陷入无限循环,2)回溯问题 如果对于同一个非终结符号，存在若干个产生式右部(如U:=x1|x2|xn)时，要对U展开，那么按哪一个产生式右部展开呢？即如何确定替换U的xi。如果选择错误，将导致回溯,回溯示例,自顶向下语法分析问题的解决方法,1)消除左递归 消除直接左递归 方法1：采用扩充BNF范式 设有文法产生式 U:=Ux|y 可改写为: U:=yx 方法2：引进新的非终结符号 设有文法产生式 U:= Ux1|Ux2|Uxm|y1|y2|yn 其中，yi(i=1,2,n)均不以符号U为首，引进一个新的非 终结符号U, 将上述产生式等价变换为: U:= y1U|y2U|y

14、nU U:= x1U|x2U|xmU,自顶向下语法分析问题的解决方法,例4-4(P65) 有文法：E:=E+T|E-T|T ，T:=T*F|T/F|F，为其设计递归分析程序,方法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,解：先消除文法中的直接左递归,自顶向下语法分析问题的解决方法,2)避免回溯 为了避免回溯，对于文法中的任一非终结符号U，

15、若U:=x1|x2|xn，要求满足以下两个条件： 相对于x1,x2,xn的各符号串的终结首符号集总是两两互不相交的，即 FIRST(xi)FIRST(xj)= (ij) 因为每一个xi推出的第一个终结符号均不相同，它能保证只会选择惟一的一个xi来替换U,例 设文法GA：A:=aB|aC，B:=b，C:=c FIRST(aB)FIRST(aC) =aa=a 采用自顶向下的语法分析时会引起回溯，例如推导句子ac将导致回溯,自顶向下语法分析问题的解决方法,2)避免回溯 如果xj ，则有可能选择此xj来替换U,而让句型中U后面的第一个终结符号与当前输入符号匹配，这样有可能回溯。若规定文法不含规则 ，则

16、对文法的要求太高，因此用 FIRST(xi)FOLLOW(U)= 来限制文法，保证只会选择惟一的一个xi来替换U,例 设文法为：S:=bAB，A:=aC| ，B:=aB| ,C:=c FIRST(aC)FOLLOW(A) =aa,# =a 采用自顶向下的语法分析时会引起回溯，例如推导句子baa将导致回溯,自顶向下语法分析问题的解决方法,2)避免回溯 以上避免回溯的两个条件等价于： SELECT(U:=xi)SELECT(U:=xj) = (ij) 其中：SELECT(U:= xk)定义为,i,j,k=1,2,n,SELECT(U:=xk,自顶向下语法分析问题的解决方法,消除文法回溯的方法： 消

17、除文法的左递归； 提公共因子； 例如U:=xy|xz，则提公共因子，有U:=x(y|z),再引进新的非终结符号V，U:= xy|xz可改写为：U:=xV，V:=y|z。 根据文法的具体情况进行等价变换,采用自顶向下语法分析法对文法的要求,采用自顶向下语法分析法要求文法满足压缩、无左递归、无回溯这三个条件，称满足这三个条件的文法为LL(1)文法,证明：因为是左递归文法，所以必存在左递归的非终结符A及形如A:=A|（可为 ）。由于SELECT(A:=A)SELECT(A:=) ，所以左递归文法不满足LL(1)文法条件,推论1：任何左递归文法均不是LL(1)文法,采用自顶向下语法分析法对文法的要求,

18、推论2：任何LL(1)文法均为无二义性文法,证明：LL(1)文法在分析句子过程的每一步，永远只有惟一的分析动作可进行。现在，假设文法G是二义性文法，则存在句子，它有两棵不同的语法树，即存在着两个不同的最左推导。从而可知，用LL(1)方法对句子进行分析的某步，存在两种不同的产生式可用于推导，且均能正确进行语法分析，即LL(1)分析动作存在不确定性。这与LL(1)的性质相矛盾。所以，文法G不是LL(1)文法,采用自顶向下语法分析法对文法的要求,例 验证下列文法是否为LL(1)文法。 GS: S:=AB|CDa A:=ab|c B:=dD| C:=eC| D:=fD|f,解：显然，文法G已压缩且无左

19、递归。下面判断其是否有回溯。 由D:=fD|f，有： SELECT(D:=fD)SELECT(D:=f) =FIRST(fD)FIRST(f) =ff =f 该文法不是LL(1)文法,采用自顶向下语法分析法对文法的要求,练习（见P77习题4的第2小题） 有文法GA： A:=aABe| B:=Bb|b 判断该文法是LL(1)文法吗,解： 文法中存在左递归B:=Bb 该文法不是LL(1)文法,4.3 递归下降分析(P64,递归下降分析(或递归子程序分析)的基本方法 其思路极为简单：为每个非终结符号构造一个子程序，以完成该非终结符号所对应的语法成分的分析和识别,1. 若U的右部只有一个候选式，则按从

20、左向右的顺序构造U的识别过程代码。 （1）若有终结符号，则判断与输入符号是否匹配，如果相同，继续读入下一符号，否则就意味着有语法错误； （2）若有非终结符号，则调用该符号的子程序。 2. 若U的右部有多个候选式，则根据每个候选式的第一个符号确定该候选式分支。 3. 只有输入串的每一个符号全部匹配成功，且正确返回时，该语法成分才算真正获得识别,4.3 递归下降分析,总控程序可描述如下： begin READ(ch); if P(文法的开始符号) then if 当前符号=# then write(valid) else write(invalid) endif else write(invali

21、d) endif end,递归下降分析算法 它由一个总控程序和若干个非终结符号的分析子程序P(U)构成。其中若有n个非终结符号就有n个分析子程序,4.3 递归下降分析,对满足条件的文法按如下方法构造相应的语法分析子程序,对于产生式U:=1|2|n, iV ，P(U)按如 下方法构造： if chFIRST(1) then P(1) else if chFIRST(2) then P(2) else if chFIRST(3) then P(3) else if chFIRST(n) then P(n) else error 其中，ch(课本用INPUTSYM)是一个全局变量，用于存放输入符号串

22、的当前要处理的输入符号; error是出错处理程序；P(i)见后面的说明,对于每个非终结符号U,编写一个相应的子程序P(U,4.3 递归下降分析,对于产生式U:=1|2|n|，P(U)按如下方法构造： if chFIRST(1) then P(1) else if chFIRST(2) then P(2) else if chFIRST(3) then P(3) else if chFIRST(n) then P(n) else if chFOLLOW(U) then return else error,4.3 递归下降分析,对于产生式U:=12n，P(U) 按如下方法构造： begin P(

23、1); P(2); ; P(n) end,说明：如果iVn，则P(i)就代表调用处理i的子程序；如果iVt，则P(i)为形如下述语句的一段程序： if ch=i then READ(ch) else error 即如果当前文法中的符号与输入符号匹配，则继续读入输入符号串的下一个符号到ch中，否则出错,例 设文法GS: S:=(A)|aAb A:=eA|dSA A:=dA| 试构造该文 法的递归子程序 (或递归下降分析 程序,解：由S:=(A)|aAb,则P(S)为,c,h,R,E,A,D,c,h,c,h,a,Y,N,P,A,c,h,R,E,A,D,c,h,Y,N,e,r,r,o,r,R,E,A

24、,D,c,h,Y,N,e,r,r,o,r,P,A,c,h,b,R,E,A,D,c,h,Y,N,e,r,r,o,r,4.3 递归下降分析,由A:=eA|dSA, 则P(A)为,例 设文法GS: S:=(A)|aAb A:=eA|dSA A:=dA| 试构造该文 法的递归子程序 (或递归下降分析 程序,c,h,e,R,E,A,D,c,h,c,h,d,Y,N,R,E,A,D,c,h,Y,N,e,r,r,o,r,P,S,P,A,4.3 递归下降分析,由A:=dA| ， 则P(A)为,例 设文法GS: S:=(A)|aAb A:=eA|dSA A:=dA| 试构造该文 法的递归子程序 (或递归下降分析

25、程序,c,h,d,R,E,A,D,c,h,c,h,F,O,L,L,O,W,A,Y,N,Y,N,e,r,r,o,r,P,A,4.3 递归下降分析,例4-3(P64) 考虑文法Z:=(U)|aUb ，U:=dZ|e，为其构造递归下降分析子程序。并对输入串aeb进行语法分析,解：文法中有两个非终结符号Z和U，那么我们需要分别编两个过程来完成Z和U规则的识别。 对于规则Z:=(U)|aUb，右部有两个候选式，因此，U的识别过程有两个分支，分别根据符号(和a来判别。 同理对规则U:=dZ|e设计的过程也分为两个分支,Z:=(U)|aUb,非终结符号Z的分析程序,U:=dZ|e,非终结符号U的分析程序,Z

26、:=(U)|aUb U:=dZ|e,输入串为aeb，分析过程为： ZaUbaeb,a,e,e,b,b,4.3 递归下降分析,例4-3(P64) 考虑文法Z:=(U)|aUb ，U:=dZ|e，为其构造递归下降分析子程序。并对输入串aeb进行语法分析,aeb递归下降分析过程,aeb的语法树,4.3 递归下降分析,例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|F 可改成 T:=F*F| /F 注意“”和“”括起来的内容采用循环设计,

27、E:=T|E+T|E-T改成E:=T+T|-T T:=F|T*F|T/F改成T:=F*F| /F,E的分析程序,T的分析程序,4.3 递归下降分析,递归子程序分析法的优缺点 主要优点：可以根据文法规则直接写出相应的识别程序，各子程序的流程图几乎就是文法规则的图解描述，简单明了，易于掌握。 主要缺点：大量的相互嵌套的递归子程序的频繁调用，使分析器的运行速度相当慢,4.4 LL(1)分析方法(P70,LL(1)分析法的含义： 第一个L表示自左向右顺序扫描输入符号串 第二个L表示分析过程产生一个句子的最左推导 括号中的1表示每进行一步推导，只需要向前查看1个输入符号，便能确定当前所应选用的规则,LL

28、(k)分析法的含义： 两个L的含义同上，括号中的k表示每进行一步推导，需要向前查看k个输入符号才能唯一确定当前应选择的规则,4.4 LL(1)分析方法,LL(1)分析程序的结构 LL(1)分析器由一个总控程序、一张分析表和一个分析栈组成,是一个二维表，可用一个二维数组MA，a来表示，它概括了文法的全部信息，指出了分析器应采取的动作,4.4 LL(1)分析方法,输入符号串：指要分析的输入符号串。为了分析算法的统一，我们需要在输入串的末尾放置一个特殊符号#，这个符号不属于终结符号集,分析表M：是一个二维表，可用一个二维数组MA，a来表示，它概括了文法的全部信息，指出了分析器应采取的动作。分析表中的

29、每一行与文法中的一个非终结符号、终结符号或#关联，即A可以是文法中的一个非终结符号、终结符号或#；而每一列则与文法的一个终结符号或#关联，即a是文法的一个终结符号或#。分析表的列数是终结符号的个数加1，行数是文法中的非终结符号和终结符号的数目加1,4.4 LL(1)分析方法,分析栈（或符号栈）：用来存放一系列文法符号。分析开始时，先将#入栈，然后再将文法的开始符号入栈,总控程序：分析器对输入串的分析靠总控程序完成。根据分析栈的栈顶符号和当前的输入符号，总控程序按照分析表的指示来决定分析器的动作。工作过程如下,输出流：分析过程中使用的产生式序列,1) 分析开始时，首先将符号#及文法的开始符号S依

30、次置于分析栈的底部，并把各指示器调整至起始位置。然后，反复执行第二步的操作,输入符号串,an,a2,a1,分析栈,S,分析开始时状况,2) 假设分析的某一步，分析栈及余留的符号串，则根据栈顶的符号Xm，采取下列动作,X1X2Xm-1Xm,分析进行中的状况,4.4 LL(1)分析方法,1)若XmVn，则查分析表的Xm所在行和ai所在列，假设MXm,ai为POP,PUSH（WVU），则将Xm出栈，并将WVU入栈，这意味着使用了规则XmUVW；MXm,ai为POP，则将Xm出栈，这意味着使用了规则Xm ；若MXm，ai为空或ERROR，则出错,XmUVW,2)若Xm=ai#，表示栈顶与扫描的符号匹配

31、，则查分析表为POP，NEXTSYM，则栈顶符号Xm出栈，输入指针指向下一个符号,3 ) 若Xm=ai= #，表示输入串完全匹配，分析成功,X1X2Xm-1WVU,X1X2Xm-1Xm,X1X2Xm-1,Xm,例(P72) 算术表达式文法ETE，E+TE，E，TFT,T*FT,T,F(E)|i，该文法的LL(1)分析表为,LL(1)分析表中元素的说明： POP为过程，功能是将栈顶元素从栈内弹出。 PUSH()为过程，其中V+ ,功能是将压栈。 NEXTSYM为读符号过程，将读符号指针指向下一个符号。 ACCEPT表示分析成功，输入符号串语法正确。 表中空白处表示错误入口，应该调用错误处理程序,

32、4.4 LL(1)分析方法,例4-7(P73) 根据表4-1，对符号串i+i*i进行分析,符号串i+i*i的分析过程,i+i*i的最左推导：ETE FTE iTE iE i+TE i+FTE i+iTE i+i*FTE i+i*iTE i+i*iE i+i*i,4.4 LL(1)分析方法,对文法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为终

33、结符或#)，置MA,b= “POP”或MA,b=“A” 。 3)把M中的所有Ma,a置为“POP，NEXTSYM”， aVt ，置M#,#=“ ACCEPT”。（该项可以不要） 4)把M中所有不按上述规则定义的元素均置为空或“ERROR,4.4 LL(1)分析方法,例有文法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(+TE)=+，在符号E行符号+列对应的位置填入“POP,PUSH(ET+)”

34、 ，见表4-1的E行。 对规则E：因为FIRST()，FOLLOW(E)=)，#，所以在符号E行符号)和#列对应的位置填入“POP”，见表4-1的E行。 其它规则处理方法相同（略,对于一个文法，若按上述方法构造的分析表M不含多重定义，则称它是一个LL(1)文法,4.4 LL(1)分析方法,观察表4-1的LL(1)分析表及表4-2的分析过程，会发现当压栈的最后一个符号是终结符时，那么下一步的分析动作肯定是这个终结符号出栈，因此，我们可以对分析表进行简化。方法是当压栈的最后一个符号是终结符时，那么，这个终结符不入栈，并加入读下一个符号，这样，分析表中所有的终结符行都可以去掉,对表4-1的分析表简化

35、后的分析表如下表所示,E +TE,T *FT,ETE,ETE,E,E,TFT,TFT,T,T,T,Fi,F(E,例 有文法GS: S:=A，A:=BA，A:=iBA|，B:=CB，B:=+CB|，C:=)A*|(，请构造文法G的LL(1)分析表,4.4 LL(1)分析方法,练习 已知文法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) =