语法分析-复习习题.ppt

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

3、（1）预测分析表 （6）文法G是否是LL（1）文法 （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 | P P-bP P-P

4、c | Qc Q-aQ Q-aQ | ,First(S)=a,b First(P)=b First(P)=a,b First(Q)=a First(Q)=a, ,Follow(S)=$,b Follow(P)=$,b,c Follow(P)=$,b,c Follow(Q)=c Follow(Q)=c ,（4）求出每个非终结符的First集和Follow集,8,（5）构建LL（1）预测分析表,9,（6）文法G是否是LL（1）文法 答：构建出的LL（1）分析表不含有多重定义的条目，因此文法G是LL（1）文法。,10,（7）利用非递归预测分析程序，验证abacb是否是文法G描述的语言的句子,11,接

5、上表,12,语法分析部分回顾,例2 文法GE: E- T T- TE | F F- a | aF (1) 判断这个文法是不是LL(1)的？ (2) 消除左递归、提取左因子之后的文法G是否是LL(1)的？,13,例1 解答： 提取左因子，消除左递归后 文法变为GE: E- T T-F T T-ET | F-aF F-F | ,GS: E- T T- TE | F F- a | aF,语法分析部分回顾,14,FIRST(E) = FIRST(T) = a FIRST(T)= , FIRST(F) = a FIRST(F)= a, FOLLOW(E)=,$ FOLLOW(T)=,$ FOLLOW(T

6、)=,$ FOLLOW(F)= FOLLOW(F)=,GE: E- T T-F T T-ET | F-aF F-F | ,不是LL(1)文法！,通过提取左因子和消除左递归的方法，并不一定能够把文法改写为一个LL(1)文法,语法分析部分回顾,15,左递归的消除 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分析部分的知识点 活前缀

7、 识别活前缀的DFA 分析表 分析算法,18,语法分析内容总结,自下而上分析部分知识点 SLR的DFA的构造及分析表的构成 初始项目集合的产生（拓广文法） 能够识别同一符号的项目都转移到同一集合中 求闭包过程中每一个“.”后面的非终结符都要重新考虑是否已经在状态中列出 对产生式A- 归约，“ri”写在FOLLOW(A)集合中元素对应的位置。,19,语法分析内容总结,自下而上分析部分知识点 LR,LALR的构造方法（在SLR的基础上加上搜索符） 搜索符的求法，根据造成目前项目出现的那个父项目来求。 求闭包的过程中可能出现要添加的项目已经存在，但是搜索符不同的情况，相当于其父项目已经改变，此时需要

8、再求一遍搜索符。,20,语法分析内容总结,自下而上分析部分知识点 SLR,LR,LALR的区别及判别方法 通过构造DFA，看其中的状态是否有冲突（“移进归约” 或 “归约归约”）若有冲突则不属于该文法类型。 通过构造分析表，看其中某项是否有冲突。,21,文法类的层次图,22,语法分析部分回顾,例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 SAaS S bAe SBeS S bBa A d B d,I2 : Ad Bd,d,S

9、-AaS | bAe | BeS | bBa A-d B-d,e属于FOLLOW(A),同时也属于FOLLOW(B), I2里存在归约-归约冲突,语法分析部分回顾,24,LR(1)分析练习题目,基于LR(1)项目来构造识别G活前缀的DFA，并基于DFA构建分析表.,S V = E S E V * E V id E V,25,LR(1)分析练习解答过程,答： Step 1. 对原文法进行拓广 (添加产生式S-S),S V = E S E V * E V id E V,S S S V = E S E V * E V id E V,26,id,S S S V=E S E V *E V id E V,

10、V id ,S V =E E V ,S S ,I0,I1,I2,I5,S E ,I3,V * E E V V id V * E,I4,S,V,*,id,E,S V = E E V V *E V 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, =/$ V-id, =/$ E-V, $,I1: S-S, $,S,I2: S-V=E, $ E-V, $,V,E,I3: S-E, $,*,I4

11、: 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 S 1 S V = E 2 S E 3 V * E 4 V id 5 E V,LR(1)分析练习解答过程,29,构建分析表 Action(0,*)=s4, action