语法分析-复习习题

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,上下文无关文法,自上而下,自下而上,LL(1),文法,2,个函数,递归下降预测分析,非递归的预测分析,最左推导,最右推导,！,LR,文法,输入,LR,分析程序,输出,栈,LR,分析器的模型,action,goto,s,m,X,m,s,m,-1,X,m,-1,s,0,a,1,a,i,a,n,$,移进,-,归约分析,归约,移进,-,归约冲突,规约,-,归约冲突,句柄,活前缀,右句型的前缀，该前缀不超过最右句柄的右端,1,。句柄与某个产生式的右部符号串相同,2,。句柄是句型的一个子串,3,。把句柄归约成非终结符代表了最右推导逆过程的一步,简单的,LR,方法（,SLR）,规范的,LR,方法,向前看的,LR,方法,(LALR）,温故知新,1,语法分析部分回顾,自上而下分析的知识点,LL(1),文法的判定,FIRST,、,FOLLOW,集的计算,（重点）,LL(1),文法判定方法,LL(1),分析的实现方法,递归函数实现,非递归的预测分析实现,先求,FIRST,、,FOLLOW,集,画预测分析表,2,语法分析部分回顾,应用,LL(1),分析方法的步骤,判定文法是否是,LL(1),文法,如果不是，则改写文法,消除左递归,提取左因子,如果改写后的文法是,LL(1),的，那么进行,LL(1),分析,构造,LL(1),分析算法,可以采用递归函数实现，也可以采用非递归的栈式分析方法实现,3,文法,G:S-aSb|P,P-bPc|bQc,Q-Qa|a,（,1,）它是,chomsky,哪一型文法？,（,2,）它生成的语言是什么？,（,3,）给出提取左因子、消除左递归之后的文法,（,4,）求出每个非终结符的,First,集和,Follow,集,（,5,）构建,LL,（,1,）预测分析表,（,6,）文法,G,是否是,LL,（,1,）文法,（,7,）利用非递归预测分析程序，验证,abacb,是否是文法,G,描述的语言的句子,4,文法,G:S-aSb|P,P-bPc|bQc,Q-Qa|a,（,1,）它是,chomsky,哪一型文法？,答：它是,2,型文法，即上下文无关文法。,（,2,）它生成的语言是什么？,答：,a,i,b,j,a,k,c,j,b,i,|i=0;j,k=1,5,文法,G:S-aSb|P,P-bPc|bQc,Q-Qa|a,（,3,）给出提取左因子、消除左递归之后的文法,答：,S-aSb|P,P-bP,P-Pc|Qc,Q-aQ,Q-aQ|,6,S-aSb|P,P-bP,P-Pc|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,集,7,（,5,）构建,LL,（,1,）预测分析表,输入符号,非终结符,a,b,c,$,S,S-aSb,S-P,P,P-bP,P,P-Qc,P-Pc,Q,Q-aQ,Q,Q-aQ,Q-,8,（,6,）文法,G,是否是,LL,（,1,）文法,答：构建出的,LL,（,1,）分析表不含有多重定义的条目，因此文法,G,是,LL,（,1,）文法。,9,（,7,）利用非递归预测分析程序，验证,abacb,是否是文法,G,描述的语言的句子,栈,输入,输出,$S,abacb$,$bSa,abacb$,S-aSb,$bS,bacb$,$bP,bacb$,S-P,$bPb,bacb$,P-bP,$bP,acb$,10,栈,输入,输出,$bcQ,acb$,P-Qc,$bcQa,acb$,Q-aQ,$bcQ,cb$,$bc,cb$,Q-,$b,b$,$,$,接上表,11,语法分析部分回顾,例,2,文法,GE:,E-T,T-TE|F,F-a|aF,(1),判断这个文法是不是,LL(1),的？,(2),消除左递归、提取左因子之后的文法,G,是否是,LL(1),的？,12,例,1,解答：,提取左因子，消除左递归后,文法变为,GE:,E-T,T-F T,T-ET|,F-aF,F-F|,GS:,E-T,T-TE|F,F-a|aF,语法分析部分回顾,13,FIRST(E)=,FIRST(T)=a,FIRST(T)=,FIRST(F)=a,FIRST(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),文法,语法分析部分回顾,14,左递归的消除,GS:,S-Qc|c,Q-Sa|a,这是一类间接左递归,S-Sac|ac|c,Q-Sa|a,语法分析部分回顾,15,左递归的消除,GS:,S-Qc|c,Q-Sa|a,这是一类间接左递归,S-acS|cS,S-acS|,Q-Sa|a,语法分析部分回顾,S-Sac|ac|c,Q-Sa|a,16,语法分析部分回顾,LR,分析部分的知识点,活前缀,识别活前缀的,DFA,分析表,分析算法,17,语法分析内容总结,自下而上分析部分知识点,SLR,的,DFA,的构造及分析表的构成,初始项目集合的产生（拓广文法）,能够识别同一符号的项目都转移到同一集合中,求闭包过程中每一个“,.”,后面的非终结符都要重新考虑是否已经在状态中列出,对产生式,A-,归约，,“r,i,”,写在,FOLLOW(A),集合中元素对应的位置。,18,语法分析内容总结,自下而上分析部分知识点,LR,LALR,的构造方法（在,SLR,的基础上加上搜索符）,搜索符的求法，根据造成目前项目出现的那个父项目来求。,求闭包的过程中可能出现要添加的项目已经存在，但是搜索符不同的情况，相当于其父项目已经改变，此时需要再求一遍搜索符。,19,语法分析内容总结,自下而上分析部分知识点,SLR,LR,LALR,的区别及判别方法,通过构造,DFA,，看其中的状态是否有冲突（“移进,归约”或“归约,归约”）若有冲突则不属于该文法类型。,通过构造分析表，看其中某项是否有冲突。,20,文法类的层次图,21,语法分析部分回顾,例,2,文法,GS:,S-AaS|bAe|BeS|bBa,A-d,B-d,判断这个文法是,SLR(1),的，还是,LR(1),的，抑或是,LALR(1),的,22,例,2,解答,:,I,2,=goto(I,0,d),I,0,:,S,S,S,AaS,S,bAe,S,BeS,S,bBa,A,d,B,d,I,2,:,A,d,B,d,d,S-AaS|bAe|BeS|bBa,A-d,B-d,e,属于,FOLLOW(A),同时也属于,FOLLOW(B),I2,里存在归约,-,归约冲突,语法分析部分回顾,23,LR(1),分析练习题目,基于,LR(1),项目来构造识别,G,活前缀的,DFA,，并基于,DFA,构建分析表,.,S,V,=,E,S,E,V,*,E,V,id,E,V,24,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,25,id,S,S,S V=E,S E,V *E,V id,E V,V id,S V=E,E V,S,S,I,0,I,1,I,2,I,5,S E,I,3,V *E,E V,V id,V *E,I,4,S,V,*,id,E,S V=E,E V,V *E,V id,I,6,=,E,S V=E,E V,V,V,I,8,id,I,3,*,*,V *E,E,I,7,I,9,识别产生式文法活前缀的,DFA,26,Step 2:,构建识别（拓广）文法活前缀的,DFA,I,0,:,S-S,$,S-V=E,$,S-E,$,V-*E,=/$,V-id,=/$,E-V,$,I,1,:,S-S,$,S,I,2,:,S-V=E,$,E-V,$,V,E,I,3,:,S-E,$,*,I,4,:,V-*E,=/$,E-V,=/$,V-*E,=/$,V-id,=/$,id,I,5,:,V-id,=/$,=,I,6,:,S-V=E,$,E-V,$,V-*E,$,V-id,$,E,I,8,:,S-*E,=/$,V,I,9,:,E-V,=/$,*,id,指向,I,5,E,I,10,:,S-V=E,$,*,I,12,:,V-*E,$,E-V,$,V-*E,$,V-id,$,I,7,:,E-V,$,V,指向,I,7,id,I,11,:,V-id,$,E,I,13,:,S-*E,$,V,指向,I,7,*,id,指向,I,11,LR(1),分析练习解答过程,27,构建分析表,首先，为表达式编号,然后，计算,action,表和,goto,表,0,S,S,1,S,V,=,E,2,S,E,3,V,*,E,4,V,id,5,E,V,LR(1),分析练习解答过程,28,构建分析表,Action(0,*)=s4,action(0,id)=s5,Goto(0,S)=1,goto(0,V)=2,goto(0,E)=3,Action(1,$)=acc,Action(2,=)=s6,Goto(2,V)=7,Action(3,$)=r2,Action(4,*)=s4,action(4,id)=s5,Goto(4,E)=8,goto(4,V)=9,LR(1),分析练习解答过程,29,