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

《语法分析-自顶向下分析.ppt》由会员分享，可在线阅读，更多相关《语法分析-自顶向下分析.ppt（70页珍藏版）》请在三一办公上搜索。

1、第四章 语法分析自顶向下分析(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）,自顶向下的分析方法就是从文法的开始符号出发，按最左推导方式向下推导，试图推导出要分析的输入串。即：开始符号 输入符号串,+,自底向上的分析方法从输入符号串开始，按最左归约方式向上归约到文法的开始符号。即：开始符号 输入符号串,归约,SaASaAaaS

3、bAaaSbbaaaabbaa,自上而下,自底向上,输入串,开始符号,图示：自上而下分析与自底向上分析,4.2 FIRST集合和FOLLOW集合（P62）,FIRST集合定义：假定是文法G的任一符号串，则：FIRST()=a|a，aVt若,则规定FIRST()。,*,*,实际上，FIRST()就是从可能推导出的所有开头终结符号或。,文法符号的FIRST集合构造方法：对于文法中的符号XV，其FIRST(X)集合可反复应用下列规则计算，直到其FIRST(X)集合不再增大为止：1)若XVt，则FIRST(X)=X。2)若XVn，且具有形如Xa的产生式(aVt)，或具有形如X的产生式，则把a或加进FI

4、RST(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)集合不再增大为止：1)若X为终结符，则将X加入FIRST(X)集合中。2)若X为非终结符，且具有形如Xa的产生式(aVt)，或具有形

5、如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()=;2)将FIRST(X1)中的一切非符号加进FIRST()；3)若FIRST(X1)，将FIRST(X2)中的一切非符号

6、加进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)=FIRST(FTE)=(，i FIRST(+TE)=+FIRST()=FIRST(E)=FIRST(+TE)FIRST()=+，FIRS

7、T(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(aABbcd)FIRST()=a=a,FIRST(A)=FIRST(ASd)FIRST()=a,d=a,d,FIRST(B)=FIRST(SAh)FIRST(eC)FIRST()=a,

8、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|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集合和FOLLOW集合,FOLLOW集合定义（P63）：假定S是文法的开始符号

9、，对于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)集合不再增大为止：1)对于文法的开始符号S，令#FOLLOW(S)2)若G中有形如AB 的产生式，且，则将FIRST()中的一切非符号加进FOLLOW(B)。3)若G中有形如AB或AB 的产生式，且FIRST()，则FOLLOW

10、(A)中的全部元素均属于FOLLOW(B)，即FOLLOW(A)FOLLOW(B)。,例 设文法GS:S:=SbA|aAA:=BcB:=Sb求此文法的每一个非终结符号的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

11、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(E)=+，)，#FOLLOW(T)=FOLLOW(T)=+，)，#FOLLOW(F)=(FIRST(T)-)FOLLOW(T)FOLLOW(T)=*，+，)，#,4.2 FIRST集合和FOLLOW集合,练习 已知文法GS:S:=AA:=BAA:=iBA|B:=CBB:=+CB|

12、C:=)A*|(求FOLLOW(C)。,解：FOLLOW(C)=(FIRST(B)-)FOLLOW(B)FOLLOW(B)=+,i,*,#,自顶向下语法分析遇到的问题,(1)左递归问题 当文法中出现左递归时（存在非终结符号U，对于它有U:=U（直接左递归），或U U（间接左递归），它会使分析过程陷入无限循环。,(2)回溯问题 如果对于同一个非终结符号，存在若干个产生式右部(如U:=x1|x2|xn)时，要对U展开，那么按哪一个产生式右部展开呢？即如何确定替换U的xi。如果选择错误，将导致回溯。,+,回溯示例,自顶向下语法分析问题的解决方法,(1)消除左递归消除直接左递归方法1：采用扩充BNF范

13、式 设有文法产生式 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|,自顶向下语法分析问题的解决方法,例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：引进新的非终结符号

14、E:=E+T|E-T|T 可改成 E:=TE，E:=+TE|-TE|T:=T*F|T/F|F 可改成 T:=FT，T:=*FT|/FT|,解：先消除文法中的直接左递归。,自顶向下语法分析问题的解决方法,(2)避免回溯 为了避免回溯，对于文法中的任一非终结符号U，若U:=x1|x2|xn，要求满足以下两个条件：相对于x1,x2,xn的各符号串的终结首符号集总是两两互不相交的，即 FIRST(xi)FIRST(xj)=(ij)因为每一个xi推出的第一个终结符号均不相同，它能保证只会选择惟一的一个xi来替换U。,例 设文法GA：A:=aB|aC，B:=b，C:=cFIRST(aB)FIRST(aC)

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

16、以上避免回溯的两个条件等价于：SELECT(U:=xi)SELECT(U:=xj)=(ij)其中：SELECT(U:=xk)定义为：,(i,j,k=1,2,n),SELECT(U:=xk),自顶向下语法分析问题的解决方法,消除文法回溯的方法：消除文法的左递归；提公共因子；例如U:=xy|xz，则提公共因子，有U:=x(y|z),再引进新的非终结符号V，U:=xy|xz可改写为：U:=xV，V:=y|z。根据文法的具体情况进行等价变换。,采用自顶向下语法分析法对文法的要求,采用自顶向下语法分析法要求文法满足压缩、无左递归、无回溯这三个条件，称满足这三个条件的文法为LL(1)文法。,证明：因为是左

17、递归文法，所以必存在左递归的非终结符A及形如A:=A|（可为）。由于SELECT(A:=A)SELECT(A:=)，所以左递归文法不满足LL(1)文法条件。,推论1：任何左递归文法均不是LL(1)文法。,采用自顶向下语法分析法对文法的要求,推论2：任何LL(1)文法均为无二义性文法。,证明：LL(1)文法在分析句子过程的每一步，永远只有惟一的分析动作可进行。现在，假设文法G是二义性文法，则存在句子，它有两棵不同的语法树，即存在着两个不同的最左推导。从而可知，用LL(1)方法对句子进行分析的某步，存在两种不同的产生式可用于推导，且均能正确进行语法分析，即LL(1)分析动作存在不确定性。这与LL(

18、1)的性质相矛盾。所以，文法G不是LL(1)文法。,采用自顶向下语法分析法对文法的要求,例 验证下列文法是否为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 该文法不是LL(1)文法。,采用自顶向下语法分析法对文法的要求,练习（见P77习题4的第2小题）有文法GA：A:=aABe|B:=Bb|b判断该文法是LL(1)文法吗？,解：文法中存在左递归B:=Bb该文法不是LL(

19、1)文法。,4.3 递归下降分析(P64),递归下降分析(或递归子程序分析)的基本方法 其思路极为简单：为每个非终结符号构造一个子程序，以完成该非终结符号所对应的语法成分的分析和识别。,1.若U的右部只有一个候选式，则按从左向右的顺序构造U的识别过程代码。（1）若有终结符号，则判断与输入符号是否匹配，如果相同，继续读入下一符号，否则就意味着有语法错误；（2）若有非终结符号，则调用该符号的子程序。2.若U的右部有多个候选式，则根据每个候选式的第一个符号确定该候选式分支。3.只有输入串的每一个符号全部匹配成功，且正确返回时，该语法成分才算真正获得识别。,4.3 递归下降分析,总控程序可描述如下：b

20、egin READ(ch);if P(文法的开始符号)then if 当前符号=#then write(valid)else write(invalid)endif else write(invalid)endifend,递归下降分析算法 它由一个总控程序和若干个非终结符号的分析子程序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 chFI

21、RST(3)then P(3)else if chFIRST(n)then P(n)else error 其中，ch(课本用INPUTSYM)是一个全局变量，用于存放输入符号串的当前要处理的输入符号;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

22、 chFOLLOW(U)then return else error,4.3 递归下降分析,对于产生式U:=12n，P(U)按如下方法构造：begin P(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)|aAbA:=eA|dSAA:=dA|试构造该文法的递归子程序(或递归下降分析程序)。,解：由S:=(A)|aAb,则P(S)为

23、：,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,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)|aAbA:=eA|dSAA:=dA|试构造该文法的递归子程序(或递归下降分析程序)。,c,h,=,e,?,R,E,A,D,(,c,h,),c,h,=,d,?,Y,N,R,E,

24、A,D,(,c,h,),Y,N,e,r,r,o,r,P,(,S,),P,(,A,),4.3 递归下降分析,由A:=dA|，则P(A)为：,例 设文法GS:S:=(A)|aAbA:=eA|dSAA:=dA|试构造该文法的递归子程序(或递归下降分析程序)。,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，那么我们需要分

25、别编两个过程来完成Z和U规则的识别。对于规则Z:=(U)|aUb，右部有两个候选式，因此，U的识别过程有两个分支，分别根据符号(和a来判别。同理对规则U:=dZ|e设计的过程也分为两个分支。,Z:=(U)|aUb,非终结符号Z的分析程序,U:=dZ|e,非终结符号U的分析程序,Z:=(U)|aUbU:=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(

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

27、使分析器的运行速度相当慢。,4.4 LL(1)分析方法(P70),LL(1)分析法的含义：第一个L表示自左向右顺序扫描输入符号串第二个L表示分析过程产生一个句子的最左推导括号中的1表示每进行一步推导，只需要向前查看1个输入符号，便能确定当前所应选用的规则,LL(k)分析法的含义：两个L的含义同上，括号中的k表示每进行一步推导，需要向前查看k个输入符号才能唯一确定当前应选择的规则。,4.4 LL(1)分析方法,LL(1)分析程序的结构 LL(1)分析器由一个总控程序、一张分析表和一个分析栈组成。,是一个二维表，可用一个二维数组MA，a来表示，它概括了文法的全部信息，指出了分析器应采取的动作。,4

28、.4 LL(1)分析方法,输入符号串：指要分析的输入符号串。为了分析算法的统一，我们需要在输入串的末尾放置一个特殊符号#，这个符号不属于终结符号集。,分析表M：是一个二维表，可用一个二维数组MA，a来表示，它概括了文法的全部信息，指出了分析器应采取的动作。分析表中的每一行与文法中的一个非终结符号、终结符号或#关联，即A可以是文法中的一个非终结符号、终结符号或#；而每一列则与文法的一个终结符号或#关联，即a是文法的一个终结符号或#。分析表的列数是终结符号的个数加1，行数是文法中的非终结符号和终结符号的数目加1。,4.4 LL(1)分析方法,分析栈（或符号栈）：用来存放一系列文法符号。分析开始时，

29、先将#入栈，然后再将文法的开始符号入栈。,总控程序：分析器对输入串的分析靠总控程序完成。根据分析栈的栈顶符号和当前的输入符号，总控程序按照分析表的指示来决定分析器的动作。工作过程如下：,输出流：分析过程中使用的产生式序列。,1)分析开始时，首先将符号#及文法的开始符号S依次置于分析栈的底部，并把各指示器调整至起始位置。然后，反复执行第二步的操作。,输入符号串：,#,an,a2,a1,分析栈：,#,S,分析开始时状况,2)假设分析的某一步，分析栈及余留的符号串，则根据栈顶的符号Xm，采取下列动作：,#X1X2Xm-1Xm,分析进行中的状况,4.4 LL(1)分析方法,(1)若XmVn，则查分析表

30、的Xm所在行和ai所在列，假设MXm,ai为POP,PUSH（WVU），则将Xm出栈，并将WVU入栈，这意味着使用了规则XmUVW；MXm,ai为POP，则将Xm出栈，这意味着使用了规则Xm；若MXm，ai为空或ERROR，则出错。,XmUVW,(2)若Xm=ai#，表示栈顶与扫描的符号匹配，则查分析表为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，该文法的

31、LL(1)分析表为:,LL(1)分析表中元素的说明：POP为过程，功能是将栈顶元素从栈内弹出。PUSH()为过程，其中V+,功能是将压栈。NEXTSYM为读符号过程，将读符号指针指向下一个符号。ACCEPT表示分析成功，输入符号串语法正确。表中空白处表示错误入口，应该调用错误处理程序。,4.4 LL(1)分析方法,例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.4 LL(1)分析方法,对文法G中的每个产生式A，按下列规则

32、确定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置为“POP，NEXTSYM”，aVt，置M#,#=“ACCEPT”。（该项可以不要）4)把M中所有不按上述规则定义的元素均置为空或“ERROR”。,4.4 LL(1)分析方法,例有文法ETE，E+TE，E，TFT，T*FT，T，F(E)|i 对规则ET

33、E：FIRST(TE)=(，i)，那么在分析表的符号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行。其它规则处理方法相同（略）。,对于一个文法，若按上述方法构造的分析表M不含多重定义，则称它是一个LL(1)文法。,4.4 LL(1)分析方法,观察表4-1的LL(1)分析表及表4-2的分析过程，会发现

34、当压栈的最后一个符号是终结符时，那么下一步的分析动作肯定是这个终结符号出栈，因此，我们可以对分析表进行简化。方法是当压栈的最后一个符号是终结符时，那么，这个终结符不入栈，并加入读下一个符号，这样，分析表中所有的终结符行都可以去掉。,对表4-1的分析表简化后的分析表如下表所示:,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)文法吗？为什

35、么？(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)分析方法,练习 已知文法GS:S:=(S)S|(1)该文法是LL(1)文法吗？为什么？(2)请给出该文法的LL(1)分析表。(3)若输入符号串是“()”，请给出其LL(1)语法分析过程。,(2)文法G的LL(1)分析表,4.4 LL(1

36、)分析方法,文法G的LL(1)分析表,ACCEPT,#,#,6,S:=,#,#S,5,匹配),)#,#S),4,S:=,)#,#S)S,3,匹配(,()#,#S)S(,2,S:=(S)S,()#,#S,1,产生式,余留输入串,分析栈,步骤,(3)输入符号串是“()”的LL(1)语法分析过程:,小 结,语法分析方法的分类自顶向下的语法分析方法遇到的问题及其解决办法FIRST集、FOLLOW集和SELECT集的求法LL(1)文法的判断递归子程序的构造方法 LL(1)分析表的构造方法,习 题(P76),1.对下面文法，设计递归下降分析程序。SaAS|(A),AAb|c2.设有文法GZ：Z=(A),A

37、=a|Bb,B=Aab若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？3.若有文法如下，设计递归下降分析程序。|ID=；|+|-|*|/ID|NUM|(),4.有文法GA：A:=aABe|B:=Bb|b 1)求每个非终结符号的FOLLOW集。2)该文法是LL(1)文法吗？3)构造LL(1)分析表。5.若有文法A(A)A|，1)为非终结符A构造FIRST集合和FOLLOW集合。2)说明该文法是LL(1)的文法。6.利用分析表4.1识别以下算术表达式，请写出分析过程：1)i+i*i+i 2)i*(i+i+i),习 题,7.考虑下面简化了的C声明文法：；int|float|

38、char ID,|ID1）在该文法中提取左因子。2）为所得的文法的非终结符构造FIRST集合和FOLLOW集合。3）说明所得的文法是LL(1)文法。4）为所得的文法构造LL(1)分析表。5）假设有输入串为“char x,y,z;”，写出相对应的LL(1)分析过程。,习 题,8.修改语法分析程序，使该程序能分析do语句和逻辑表达式,有关文法规则如下：:=|:=do while();:=ID=|:=(&|)|!|&、|、!为逻辑运算符。,习 题,作 业 一,1、设有如下文法：V N|NEE V|V+EN i求该文法各非终结符号的FIRST集和FOLLOW集。2、设有文法：S:=aABbcd|A:=ASd|B:=SAh|eC|C:=Sf|Cg|求此文法的每一个非终结符号的FOLLOW集。,做P77习题的第3题和第7题。,作 业 二,