第五章 LR(0)方法.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章 自底向上的语法分析,5.1,自底向上的语法分析方法概述,5.2 LR(0),分析的有限自动机,5.3 LR(0),分析,5.4 SLR(1),分析,5.5 LR(1),分析,5.6 LALR(1),分析,5.7 LALR(1),语法分析器的自动生成器,(YACC),内容回顾,自底向上的分析过程,LR,分析机制,LR,分析的关键问题,自底向上语法分析的例子,P:,Z,ABb,(2)A a,(3)A,b,(4)B,b,(5)B,c,(6)B,bB,a b c b,输入,符号栈,动作,abcb,移入,abcb,归约,(2),A,bcb,移入,Ab,cb,移入,Ab,c,b,归约,(5),Ab,B,b,归约,(6),AB,b,移入,归约,(1),ABb,Z,成功,自底向上分析过程是从所给,输入串,出发，对其进行,最左归约,的过程。,LR,分析机制,分析栈,输入,#,a,LR,驱动程序,:,-shift(,移入,):,移入型规范活前缀,-reduce(,归约,):,可归约规范活前缀,LR,分析表,规范活前缀,LR,分析的关键问题,如何判定规范活前缀,?,如何判定移入型规范活前缀,?,如何判定归约规范活前缀以及用哪一个产生式归约,?,如何判定分析结束,?,LR(k),自动机可以解决这些问题,!,5.2,LR(0),分析的有限自动机,构造,LR(0),自动机的依据,-,派生定理,应用派生定理的例子,LR(0),自动机,LR(0)item(,项,),LR(0)automata,构造,LR(0),自动机的过程,构造,LR(0),自动机的依据,-,派生定理,派生定理,:,给出了对任意一个,CFG,构造归约规范活前缀的方法,1*,把,CFG,扩展为增广文法,Z,S,;,2,文法开始符,Z,或,S,是归约规范活前缀,;,3,如果,A,是一个,归约规范活前缀,且有产生式,A,那么,也是一个,归约规范活前缀,;,(,和是由终极符和非终极符构成的符号串,也可以是空串,),4,任何一个归约规范活前缀都是按照,3,方式派生出来的,;,(,证明略,),派生定理应用例,1,1 S,2 S,和,S aAc,产生,aAc,3 aAc,和,A Abb,产生,aAbb,4 aAc,和,A b,产生,ab,5 aAbb,和,A Abb,产生,aAbb,6 aAbb,和,A b,产生,ab,7,最后,合起来得到,S,aAc,aAbb,ab,V,T,=a,b,c,V,N,=,S,A,S=S,P:,S aAc,A Abb,A b,派生定理应用例,2,1 S,2 S,和,S aAc,产生,aAc,3 aAc,和,A ABb,产生,aABb,4 aAc,和,A a,产生,aa,5 aABb,和,B bB,产生,aAbB,6 aABb,和,B b,产生,aAb,7 aAbB,和,B bB,产生,aAbbB,8 aAbB,和,B b,产生,aAbb,V,T,=a,b,c,V,N,=,S,A,B,S=S,P:,S aAc,A ABb,A a,B bB,B b,LR(0),自动机,LR(0),项目,:,带圆点的产生式,圆点只能出现在产生式的右部符号串的任意位置,;,产生式,SaAc,，,LR(0),项目：,S,aAc,S a,Ac,S a A,c,S a Ac,特别地，空产生式,:S ,对应,LR(0),项目,S,LR(0),自动机,LR(0),项目集合,IS,关于符合,X,的投影,IS,是一个,LR(0),项目的集合,;,X,是一个符号,(,终极符或非终极符,);,IS,(X),表示项目集,IS,关于符号,X,的投影,:,IS,(X),=,S,X,|,S X IS,X,V,T,V,N,IS(x),只对,IS,中圆点后面是,X,的项目起作用，所起的作用就是将圆点从,X,的前面移到,X,的后面,IS=,A A,B,b,B a,B b,B,Z cB,X=B,IS,(B),=,A AB,b,B bB,LR(0),自动机,LR(0),项目集合的闭包,IS,是,LR(0),项目的集合,;,CLOSURE(IS),也是一个,LR(0),项目集合,按照下面的步骤计算,:,1,初始,CLOSURE(IS)=IS,2,对于,CLOSURE(IS),中没有处理的,LR(0),项目,如果该项目的圆点后面是一个非终极符,A,而且,A,的全部产生式是,A,1,A,n,则增加如下,LR(0),项目到,CLOSURE(IS),A,1,A,n,3,重复,2,直到,CLOSURE(IS),收敛,;,LR(0),自动机,V,T,=a,b,c,V,N,=,S,A,B,S=S,P:,S aAc,A ABb,A Ba,B b,IS=,S aAc,CLOSURE(IS)=,S aAc,IS=,S aAc,CLOSURE(IS),=,S aAc,A ABb,A Ba,B b,LR(0),自动机,goto,函数,IS,是,LR(0),项目集合,;,X,是一个符号,(V,T,or V,N,终极符或非终极符,);,goto(IS,X)=CLOSURE(IS,(x),),LR(0),自动机,CFG G=V,T,V,N,S,P,的,LR(0),自动机,(,，,SS,，,S0,，,TS,，,),是否需要 增广产生式,Z S,？,=,V,T,V,N,#,S0=CLOSURE(Z,S,),SS,TS,构造,LR(0),自动机的过程中逐步生成的。,构造,LR(0),自动机的过程,1,增广产生式,Z S,2=,V,T,V,N,#,3S0=CLOSURE(Z,S,),4SS=S0,5,对于,SS,中的每一个项目,IS,和每个符号,X,计算,ISgoto(IS,X),如果,IS,不为空,则 建立,IS IS,如果,IS,不为空且,IS,不属于,SS,则把,IS,加入,SS;,6,重复,5,直到,SS,收敛,;,7,终止状态,:,包含形如,A,项目的项目集合,;,X,构造,LR(0),自动机的过程,V,T,=a,b,c,V,N,=,S,A,B,S=S,P:,S aAc,A ABb,A Ba,B b,Z,S,S,aAc,Z,S,S,a,S,aAc,A ABb A Ba,B b,A,S,aAc,A ABb,B b,b,B,A,Ba,a,A,Ba,B,b,S,aAc,c,B,A,ABb,b,A,ABb,b,0,*,*,*,*,*,构造,LR自动机的过程,V,T,=a,b,c,V,N,=,S,A,B,S=S,P:,S aAc,A ABb,A Ba,B ,Z,S,S,aAc,Z,S,S,a,S,aAc,A ABb A Ba,B ,A,S,aAc,A ABb,B ,B,A,Bb,b,A,Bb,S,aAc,c,B,A,ABb,A,ABb,b,0,*,*,*,*,*,*,1 S,2 S,和,S aAc,产生,aAc,3 aAc,和,A Abb,产生,aAbb,4 aAc,和,A b,产生,ab,5 aAbb,和,A Abb,产生,aAbb,6 aAbb,和,A b,产生,ab,7,最后,合起来得到,S,aAc,aAbb,ab,V,T,=a,b,c,V,N,=,S,A,S=S,P:,S aAc,A Abb,A b,V,T,=a,b,c,V,N,=,S,A,S=S,P:,S aAc,A Abb,A b,Z,S,S,aAc,S,Z,S,a,S,a,Ac,A,Abb,A b,A,S,aAc,A,Abb,b,A,b,c,S,aAc,b,A,Ab,b,b,A,Abb,LR(0),自动机接受的语言恰好是归约规范活前缀的集合：,S,aAc,aAbb,ab,V,T,=a,b,c,V,N,=,S,A,B,S=S,P:,S aAc,A ABb,A a,B bB,B b,1 S,2 S,和,S aAc,产生,aAc,3 aAc,和,A ABb,产生aABb,4 aAc,和,A a,产生,aa,5 aABb,和,B bB,产生,aAbB,6 aABb,和,B b,产生,aAb,7 aAbB,和,B bB,产生,aAbbB,8 aAbB,和,B b,产生,aAbb,S,aAc,aa,aABb,aAb,+,B,aAb,+,V,T,=a,b,c,V,N,=,S,A,B,S=S,P:,S aAc,A ABb,A a,B bB,B b,Z,S,S,aAc,S,Z,S,a,S,a,Ac,A,ABb,A a,A,S,aAc,A ABb,B bB,B,b,a,A,a,c,S,aAc,b,B,b,B,B,b,B bB,B b,B,B,bB,B,A,AB,b,b,A,ABb,b,结论,:,一个,CFG,的,LR(0),自动机接受的是该,CFG,的所有,LR0,归约规范活前缀,;,第五章 自底向上的语法分析,5.1,自底向上的语法分析方法概述,5.2 LR(0),分析的有限自动机,5.3 LR(0),分析,5.4 SLR(1),分析,5.5 LR(1),分析,5.6 LALR(1),分析,5.7 LALR(1),语法分析器的自动生成器,(YACC),5.3 LR(0),分析,LR(0),自动机的相关概念,LR(0),文法,LR(0),语法分析方法,LR(0),分析表,LR(0),分析的驱动程序,LR(0),分析过程,LR(0),自动机的相关概念,移入项目,:A,a,aV,T,归约项目,:A,接受项目,:Z,S,(Z,S,是增广产生式,),移入状态,:,包含移入项目的状态,归约状态,:,包含归约项目的状态,冲突状态,(,同一个状态中,):,包含不同的归约项目，则称该状态存在,归约,-,归约冲突,；,既包含移入项目，又包含归约项目，则称该状态存在,移入,-,归约冲突,LR(0),文法,给定一个上下文无关文法,G,LR,0,是,G,的,LR(0),自动机,如果,LR,0,的任意一个状态都不存在冲突,(,归约,-,归约冲突、移入,-,归约冲突,),则,G,称为,LR(0),文法,;,可以推知：在,LR(0),文法中，,任意状态或者是移入状态,或者是归约状态,如果是归约状态,一定存在一个,唯一,的归约项目,该归约项目对应一个产生式,p,因此,该归约状态称为,p-,归约状态,LR(0),分析方法,Stack,Input,#,a,LR,驱动程序,:,-shift(,移入,):,移入型规范活前缀,-reduce(,归约,):,归约规范活前缀,LR,分析表,规范活前缀,状态栈,action,表,goto,表,LR(0),驱动程序,LR(0),文法,V,T,=a,b,c,V,N,=,S,A,B,S=S,P:,(1)S aAc,(2)A ABb,(3)A Ba,(4)B b,Z,S,S,aAc,Z,S,S,a,S,aAc,A ABb A Ba,B b,A,S,aAc,A ABb,B b,b,B,A,Ba,a,A,Ba,B,b,S,aAc,c,B,A,ABb,b,A,ABb,b,0,1,2,3,5,6,7,8,9,4,LR(0),分析的例子,P:,(0)Z,S,(1)S aAc,(2)A ABb,(3)A Ba,(4)B b,a b a c,符号栈,输入流,分析动作,abac#,移入,a,bac#,移入,ab,ac#,归约,(4),aB,ac#,移入,aBa,c#,归约,(3),aA,c#,移入,aAc,#,归约,(,1),S,#,归约,(0),Z,#,接受,LR(0),分析的例子,状态栈,符号栈,输入流,分析动作,0,abac#,移入,02,a,bac#,移入,027,ab,ac#,归约,(4),025,aB,ac#,移入,0256,aBa,c#,归约,(3),023,aA,c#,移入,0234,aAc,#,归约,(1),01,S,#,归约,(0),01,Z,#,接受,P:,(0)Z,S,(1)S aAc,(2)A ABb,(3)A Ba,(4)B b,a b a c,LR(0),分析表,action,表,goto,表,LR(0),分析表,action,表,终极符,状 态,a,1,#,S,1,S,n,action(S,i,a)=S,j,如果,S,i,到,S,j,有,a,输出边,action(S,i,c)=R,p,如果,Si,是,p-,归约状态,c,Vt#,action(S,i,#)=accept,如果,S,i,是接受状态,action(S,i,a)=error,其他情形,LR(0),分析表,goto,表,非终极符,状 态,A,1,S,1,S,n,goto(S,i,A)=S,j,如果,S,i,到,S,j,有,A,输出边,goto(S,i,A)=error,如果,S,i,没有,A,输出边,LR(0),分析表的例子,V,T,=a,b,c,V,N,=,S,A,B,S=S,P:,(1)S aAc,(2)A ABb,(3)A Ba,(4)B b,Z,S,S,aAc,Z,S,S,a,S,aAc,A ABb A Ba,B b,A,S,aAc,A ABb,B b,b,B,A,Ba,a,A,Ba,B,b,S,aAc,c,B,A,ABb,b,A,ABb,b,0,1,2,3,5,6,7,8,9,4,action,表,goto,表,a,b,c,#,S,A,B,0,S2,1,1,accept,2,S7,3,5,3,S7,S4,8,4,R1,R1,R1,R1,5,S6,6,R3,R3,R3,R3,7,R4,R4,R4,R4,8,S9,9,R2,R2,R2,R2,LR(0),分析驱动程序,符号约定：,S0:,开始状态,Stack:,状态栈,Stack(top):,栈顶元素,P:,产生式,|P|:,产生式,P,右部符号个数,;,P,A,:,产生式,P,左部非终极符,;,Push(S):,把状态,S,压入,stack;,Pop(n):,从,stack,弹出,n,个栈顶元素,;,LR(0),分析驱动程序,初始化,:push(S0);a=readOne();,L:Switch,action,(stack(top),a),Case,error,:error();,Case,accept,:return true;,Case,Si,:push(Si),a=readOne();goto L;,Case,R,P,:pop(|P|);,push(,goto,(stack(top),P,A,);,goto L;,LR(0),分析过程,状态栈,输入流,分析动作,0,abac#,S2,02,bac#,S7,027,ac#,R4,Goto(3,B)=5,025,ac#,S6,0256,c#,R3,Goto(3,A)=3,023,c#,S4,0234,#,R1,Goto(0,S)=1,01,#,Accept,P:,(0)Z,S,(1)S aAc,(2)A ABb,(3)A Ba,(4)B b,a b a c,