第三章语法分析-复习+习题

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Monday, Sep 7,th, 2009,*,Copyright 2009, Software School,*,单击此处编辑母版标题样式,上下文无关文法,自上而下,自下而上,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）,温故知新,语法分析部分回顾,自上而下分析的知识点,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,