语法分析-复习习题.ppt

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

1、1,上下文无关文法,自上而下,自下而上,LL(1)文法,2个函数,递归下降预测分析,非递归的预测分析,最左推导,最右推导,！,LR文法,移进-归约分析,归约,移进-归约冲突,规约-归约冲突,句柄,活前缀,右句型的前缀，该前缀不超过最右句柄的右端,1。句柄与某个产生式的右部符号串相同2。句柄是句型的一个子串3。把句柄归约成非终结符代表了最右推导逆过程的一步,简单的LR方法（SLR）规范的LR方法向前看的LR方法(LALR）,温故知新,2,语法分析部分回顾,自上而下分析的知识点 LL(1)文法的判定 FIRST、FOLLOW集的计算（重点）LL(1)文法判定方法 LL(1)分析的实现方法 递归函数

2、实现 非递归的预测分析实现先求FIRST、FOLLOW集画预测分析表,3,语法分析部分回顾,应用LL(1)分析方法的步骤判定文法是否是LL(1)文法如果不是，则改写文法 消除左递归 提取左因子如果改写后的文法是LL(1)的，那么进行LL(1)分析构造LL(1)分析算法可以采用递归函数实现，也可以采用非递归的栈式分析方法实现,4,文法G:S-aSb|P P-bPc|bQc Q-Qa|a（1）它是chomsky哪一型文法？（2）它生成的语言是什么？（3）给出提取左因子、消除左递归之后的文法（4）求出每个非终结符的First集和Follow集（5）构建LL（1）预测分析表（6）文法G是否是LL（1）

3、文法（7）利用非递归预测分析程序，验证abacb是否是文法G描述的语言的句子,5,文法G:S-aSb|P P-bPc|bQc Q-Qa|a（1）它是chomsky哪一型文法？答：它是2型文法，即上下文无关文法。（2）它生成的语言是什么？答：aibjakcjbi|i=0;j,k=1,6,文法G:S-aSb|P P-bPc|bQc Q-Qa|a（3）给出提取左因子、消除左递归之后的文法答：S-aSb|P P-bP P-Pc|Qc Q-aQ Q-aQ|,7,S-aSb|PP-bPP-Pc|QcQ-aQQ-aQ|,First(S)=a,bFirst(P)=bFirst(P)=a,bFirst(Q)=a

4、First(Q)=a,Follow(S)=$,bFollow(P)=$,b,cFollow(P)=$,b,cFollow(Q)=cFollow(Q)=c,（4）求出每个非终结符的First集和Follow集,8,（5）构建LL（1）预测分析表,9,（6）文法G是否是LL（1）文法答：构建出的LL（1）分析表不含有多重定义的条目，因此文法G是LL（1）文法。,10,（7）利用非递归预测分析程序，验证abacb是否是文法G描述的语言的句子,11,接上表,12,语法分析部分回顾,例2 文法GE:E-T T-TE|F F-a|aF(1)判断这个文法是不是LL(1)的？(2)消除左递归、提取左因子之后的

5、文法G是否是LL(1)的？,13,例1 解答：提取左因子，消除左递归后 文法变为GE:E-T T-F T T-ET|F-aF F-F|,GS:E-TT-TE|F F-a|aF,语法分析部分回顾,14,FIRST(E)=FIRST(T)=aFIRST(T)=,FIRST(F)=aFIRST(F)=a,FOLLOW(E)=,$FOLLOW(T)=,$FOLLOW(T)=,$FOLLOW(F)=FOLLOW(F)=,GE:E-T T-F T T-ET|F-aF F-F|,不是LL(1)文法！,通过提取左因子和消除左递归的方法，并不一定能够把文法改写为一个LL(1)文法,语法分析部分回顾,15,左递归

6、的消除 GS:S-Qc|c Q-Sa|a这是一类间接左递归 S-Sac|ac|c Q-Sa|a,语法分析部分回顾,16,左递归的消除 GS:S-Qc|c Q-Sa|a这是一类间接左递归 S-acS|cS S-acS|Q-Sa|a,语法分析部分回顾,S-Sac|ac|c Q-Sa|a,17,语法分析部分回顾,LR分析部分的知识点 活前缀 识别活前缀的DFA 分析表 分析算法,18,语法分析内容总结,自下而上分析部分知识点 SLR的DFA的构造及分析表的构成初始项目集合的产生（拓广文法）能够识别同一符号的项目都转移到同一集合中求闭包过程中每一个“.”后面的非终结符都要重新考虑是否已经在状态中列出对

7、产生式A-归约，“ri”写在FOLLOW(A)集合中元素对应的位置。,19,语法分析内容总结,自下而上分析部分知识点 LR,LALR的构造方法（在SLR的基础上加上搜索符）搜索符的求法，根据造成目前项目出现的那个父项目来求。求闭包的过程中可能出现要添加的项目已经存在，但是搜索符不同的情况，相当于其父项目已经改变，此时需要再求一遍搜索符。,20,语法分析内容总结,自下而上分析部分知识点 SLR,LR,LALR的区别及判别方法通过构造DFA，看其中的状态是否有冲突（“移进归约”或“归约归约”）若有冲突则不属于该文法类型。通过构造分析表，看其中某项是否有冲突。,21,文法类的层次图,22,语法分析部

8、分回顾,例2 文法GS:S-AaS|bAe|BeS|bBa A-d B-d 判断这个文法是SLR(1)的，还是LR(1)的，抑或是LALR(1)的,23,例2 解答:I2=goto(I0,d),I0:SS SAaSS bAe SBeSS bBa A d B d,I2:AdBd,d,S-AaS|bAe|BeS|bBaA-dB-d,e属于FOLLOW(A),同时也属于FOLLOW(B),I2里存在归约-归约冲突,语法分析部分回顾,24,LR(1)分析练习题目,基于LR(1)项目来构造识别G活前缀的DFA，并基于DFA构建分析表.,S V=ES E V*EV id E V,25,LR(1)分析练习解

9、答过程,答：Step 1.对原文法进行拓广(添加产生式S-S),S V=ES E V*EV id E V,S SS V=ES E V*EV id E V,26,id,S SS V=ES EV*EV idE V,V id,S V=EE V,S S,I0,I1,I2,I5,S E,I3,V*EE VV idV*E,I4,S,V,*,id,E,S V=EE VV*EV id,I6,=,E,S V=E,E V,V,V,I8,id,I3,*,*,V*E,E,I7,I9,识别产生式文法活前缀的DFA,27,Step 2:构建识别（拓广）文法活前缀的DFA,I0:S-S,$S-V=E,$S-E,$V-*E,

10、=/$V-id,=/$E-V,$,I1:S-S,$,S,I2:S-V=E,$E-V,$,V,E,I3:S-E,$,*,I4:V-*E,=/$E-V,=/$V-*E,=/$V-id,=/$,id,I5:V-id,=/$,=,I6:S-V=E,$E-V,$V-*E,$V-id,$,E,I8:S-*E,=/$,V,I9:E-V,=/$,*,id,指向I5,E,I10:S-V=E,$,*,I12:V-*E,$E-V,$V-*E,$V-id,$,I7:E-V,$,V,指向I7,id,I11:V-id,$,E,I13:S-*E,$,V,指向I7,*,id,指向I11,LR(1)分析练习解答过程,28,构建分析表首先，为表达式编号然后，计算action表和goto表,0 S S1 S V=E2 S E 3 V*E4 V id 5 E V,LR(1)分析练习解答过程,29,构建分析表Action(0,*)=s4,action(0,id)=s5Goto(0,S)=1,goto(0,V)=2,goto(0,E)=3Action(1,$)=accAction(2,=)=s6Goto(2,V)=7Action(3,$)=r2Action(4,*)=s4,action(4,id)=s5Goto(4,E)=8,goto(4,V)=9,LR(1)分析练习解答过程,