编译原理7-LR(0).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,编译原理,计算机学院 李金厚,第七章,LR,分析,7.1,概述,7.2 LR(0),分析,7.3 SLR(1),分析,7.4 LR(1),分析,7.5 LALR(1),分析,7.6,二义性文法在,LR,分析中的应用,重点讲解内容,LR,分析概述,能力强,几乎所有,CFG,的语言结构都能用,LR,分析,不需要对文法附加条件,难点,几乎不可能用手工编写,LR,分析器,现实,有,LR,分析器的生成器,LR,分析,属于自下而上的分析方法,移进,-,归约,可归约串及相关概念：,短语；直接短语；最左素短语；句柄；规范归,约,选择“可归约串”为句型的句柄,自下而上分析：通用模型,总控程序,output,产生式表,Input$(#),移进归约依据表,符号栈,自下而上的分析：,LR,分析器模型,总控程序,output,产生式表,Input$(#),LR,分析表,符号栈,LR,分析,L,从左到右扫描输入串,R,构造最右推导,(,最左归约,),LR,分析表主要包括,ACTION,表和,GOTO,表,这两张表的含义分别什么？,LR,分析使用两张表,ACTION,表的作用,告诉分析器在栈顶状态为,S,当前输入符号是,a,时做,什麽,(,下面是几种可能动作,),ACTIONS,a,=,S,j,ACTIONS,a,=,r,j,(,第,j,条产生式为,A,),ACTIONS,a,=acc,ACTIONS,a,=error,GOTO,表的作用,告诉分析器在,栈顶状态为,S,，归约之后的非终结符,為,A,时，要放到栈顶的新状态,自下而上语法分析：例,设有文法,GS,：,(1)S,aAcBe,(2)A b (3)A,Ab,(4)B d,对输入串,abbcde,使用移进,-,归约的方法分析它是否为上述文法的句子,先看自上而下的推导过程：,S,aAcBe,aAcde,aAbcde,abbcde,S,aAcBe,aAcde,aAbcde,abbcde,续：普通自下而上分析过程,步骤,符号栈,输入符号串,动作,(1),(2),(3),(4),(5),(6),(7)(8),(9),(10),(11),#,#a,#,ab,#,aA,#,aAb,#,aA,#,aAc,#,aAcd,#,aAcB,#,aAcBe,#S,abbcde,#,bbcde,#,bcde,#,bcde,#,cde,#,cde,#,de#,e#,e#,#,#,移进,移进,归约,(,A,b,),移进,归约,(,A,A,b,),移进,移进,归约,(,B,d,),移进,归约,(,S,aAcBe,),接受,ACTION,表和,GOTO,表,ACTION,GOTO,a,c,e,b,d,#,S,A,B,0,S,2,1,1,acc,2,S,4,3,3,S,5,S,6,4,r,2,r,2,r,2,r,2,r,2,r,2,5,S,8,7,6,r,3,r,3,r,3,r,3,r,3,r,3,7,S,9,8,r,4,r,4,r,4,r,4,r,4,r,4,9,r,1,r,1,r,1,r,1,r,1,r,1,Step,states,The rest of input,action,goto,1 0,abbcde,#s2,2 02,bbcde,#s4,3 024,bcde,#r2 goto(2,A),4 023,bcde,#s6,5 0236,cde,#r3 goto(2,A),6 023,cde,#s5,7 0235 de#s8,8 02358 e#r4 goto(5,B),9 02357 e#s9,10 023579#r1 goto(0,S),11 01#acc,续：,LR,分析过程,步骤,符号栈,输入符号串,动作,1,）,#,abbcde,#,移进,0 S,2,2,）,#a,bbcde,#,移进,02 S,4,4,）,#,aA,bcde,#,移进,023 S,6,6,）,#,aA,cde,#,移进,023 S,5,7,）,#,aAc,de#,移进,0235 S,8,9,）,#,aAcB,e#,移进,02357 S,9,11,）,#S#,接受,01 acc,对输入串,abbcde,#,的,LR,分析过程,3,）,#,a,b,bcde,#,归约,(,Ab,),024 r,2,3,5,）,#,aA,b,cde,#,归约,(,AAb,),0236 r,3,3,8,）,#,aAcd,e#,归约,(Bd)02358 r,4,7,10,）,#,aAcBe,#,归约,(,SaAcBe,)023579 r,1,1,状态栈,ACTION,GOTO,文法,GS,：,(1)S,aAcBe,(2)A b(3)A,Ab,(4)B d,S,i,:,移进，将状态,i,和,输入符,进栈,r,i,:,归约，用第,i,个产生式归约，同时状态栈与符号栈退出相应个符号，并把,GOTO,表相应状态和第,i,个产生式的,左部,非终结,符入栈。,LR,分析,ACTION,表表达如此含义，即栈顶状态为,S,当前输入符号是,a,的时候采取,什麽,动作,-?,有穷狀态自动机,特征,规范的,符号栈中的符号是规范句型的,前缀,，且不含句柄以后的任何符号,分析决策依据,栈顶状态和现行输入符号。识别规范句型特定前缀,(,就到句柄为止,),的,DFA,四种技术,LR(0)SLR(1)LR(1)LALR(1),前缀相关的几个概念,LR(0),分析表构造思想和方法是其他,LR,分析表构造的基础,先认识一下前缀问题,可归前缀,子前缀,活前缀,前缀问题,回到前例的归约过程：,S,aAcBe1,aAcd4e,aAb3cde,ab2bcde,其每次归约时句型的,前部,分别为：,ab2,所有可能,前缀,：,a,ab,aAb3,所有可能,前缀,：,a,aA,aAb,aAcd4,所有可能,前缀,：,a,aA,aAc,aAcd,aAcBe1,所有可能,前缀,：,a,aA,aAc,aAcd,aAcBe,文法的拓广,文法的开始符号可以出现在右部，也就可能作为前缀的一个部分出现。为了保证文法的开始符号只出现在产生式的左部，对原有文法进行简单的拓广,具体地，如果原有文法开始符号是,S,，则增加一个产生式,S,S,得到相应的拓广文法。显然，,S,只会出现在所有产生式的左部；拓广文法和原有文法是等价的,文法拓广：例,可以容易地将下面左边的文法拓广为右边的文法：,(1),SaAcBe,(1),S,S,(2),Ab,(2),S,aAcBe,(3),AAb,(3),Ab,(4),Bd,(4),AAb,(5),Bd,活前缀,这里把在规范句型中形成可归前缀之前包括可归前缀在内的所有前缀统称为,活前缀,，下面是有关的定义,定义：,若,S,A ,是文法,G,的拓广文法,G,的一个规范推导，如果符号串是,的前缀，则,称它是,G,的一个活前缀,也就是说，是规范句型,的前缀，但它的右端不超过该句型句柄的末端,*,R,识别活前缀的有限自动机,对于下面的可归前缀,S aAcBe1,aAcd4e,aAb3cde,ab2bcde,可构造如下相应的有限自动机：,0,1,S,*,2,4,a,3,b,识别活前缀的有限自动机,其中，带“*”的状态既为句柄识别态，又是句子识别态，它仅有惟一的一个,5,8,a,6,A,9,13,a,10,A,14,19,a,15,A,7,b,11,12,c,d,16,17,18,c,B,e,识别活前缀的有穷自动机,加一个统一的开始状态,X,，从而从上面若干有限自动机合并得到一个完整的有限自动机用于识别活前缀如下：,0,1,S,*,2,4,a,5,8,a,9,13,a,14,19,a,X,3,b,6,7,b,A,10,11,12,15,16,17,18,A,c,d,B,e,c,A,识别活前缀的有限自动机,进一步地，将上述,NFA,转换可得到下面如图所示的,DFA,：,2,5,X,4,1,6,9,8,7,3,S,a,b,A,b,c,B,e,d,识别活前缀的有限自动机,用有限自动机识别时，每当识别完句柄，则状态回退句柄串长度的状态数。例如，在前图，若已识别到状态 ，这时句柄已形成，而且句柄是,Ab,，则应用,AAb,归约，状态应退回到 ，又因左部为,A,，所以相当于在状态 时又遇到,A,，这时应转向状态,在状态 再遇到输入串的一个,b,，又转到状态 ，重复上述过程,5,2,2,4,4,5,活前缀与可归前缀的识别算法,定义：,设,G=(V,N,V,T,P,S),是一个上下文无关文,法，对,A,V,N,有,LC(A)=|S A,V*,V,T,*,其中，,S,是,G,的拓广文法,G,的开始符号,LC(A),给出了规范推导中在非终结符,A,左边出现的符号串集合。在该集合的基础上，可以找出不包含句柄的所有活前缀,LC,通俗地称为“,左文,”,*,R,活前缀与可归前缀的识别算法,结论,1,：,若文法,G,中有产生式,B,A,，,则有：,LC(A)LC(B)(),LC(),求出了规范推导过程中用一个非终结符的右部替换该非终结符之前它左部可能出现的串,在其基础上，把句柄加入则可求得包含句柄的活前缀,LR(0),活前缀计算,对,LR(0),方法来说，包含句柄的活前缀计算不复杂，只需把已求得的活前缀再加上产生式的右部即可,于是，,LR(0)CONTEXT(A,),=LR(0)C(A,),=LC(A),构造识别活前缀的有限自动机,有了“左文”或活前缀，可单独地构造识别该活前缀的有限自动机,按照前面的方法，将所有识别活前缀的有限自动机整合在一起，便得到用于活前缀识别的有限自动机，再将其确定化便可得到我们所需要,的,DFA,构造识别活前缀的有限自动机：例,设有文法,GS:,(0),S,S,(1)S a A c B e (2)A b,(3)A,Ab,(4)B d,续,对每个非终结符列出有关的方程，从而得到如下的左文方程组：,LC(S,)=,LC(S)=LC(S,),LC(A)=,LC(S),a,LC(A),LC(B)=,LC(S),aAc,简写为：,S,=,S=S,A=,Sa+A,B=,SaAc,续,求解可得：,S,=,S=,A=,a+A,B=,aAc,而,A=,a+A,，即为,A=a,或任何包含,a,的,A,，显然所求应为,A=a,按照前面已经讨论过的方法，可以构造识别这些活前缀的有限自动机，这里从略,LR(0),的项目集规范族,对一个上下文无关文法，只要能构造出它的识别可归前缀的有,限自动机,DFA,，就可以构造相应的分析表，即前面所介绍的,状态转换表,和,动作表,但,这种方法对一个实用的高级语言的文法实现起来却很复杂,，而基于项目集规范族构造的方法是较为常用的,LR(0),的项目,LR(0),项目：在文法,G,中每个产生式的右部适当位置添加一个圆点来构成项目,例如，对产生式,SaAcBe,，对应有,6,个项目,0 S,aAcBe,1,Sa,AcBe,2,SaA,cBe,3,SaAc,Be,4,SaAcB,e,5,SaAcBe,LR(0),的项目,一个产生式可对应的项目个数一般为它的右部符号串,长度加,1,注意：对空产生式,A,，仅有项目,A,每个项目的含义与圆点的位置有关：,活前缀不含有句柄的任何符号，此时期望,A,的右部所推出的符号串,对,活前缀已含有句柄的全部符号，表明产生式,A,的 右部,已出现在栈顶,活前缀只含句柄的一部分符号表明,A,1,2,的右部子串,1,已出现在栈顶，期待从输入串中看到,2,推出的符号,LR(0),的项目,项目分类：,移进项目，形如,A,a,，其中,V*,，,aV,T,此时圆点后面为终结符,a,，对应状态为移进状态，分析时把,a,移进符号栈,待约项目，形如,A,B,，其中,V*,，,B V,N,，,此时圆点后面为非终结符,B,，对应状态为归约状态，它表明所对应状态等待分析完非终结符,B,所能推出的串归约成,B,，才能继续分析,A,的右部,项目分类,归约项目，形如,A,，其中,V*,此时圆点在最右端，称为归约项目，因为产生式的右部已分析完，句柄已形成可以归约,接受项目，形如,S,，其中,V+,，,S,为拓广文法的开始符号,它是归约项目的特殊情况：对应状态为接受状态,项目集规范族及其构造,按照前面的方法构造有穷自动机较为麻烦：求解左文方程组，构造识别活前缀的,-NFA,，再转换得到相应的,DFA,不过，通过观察上述过程，可以发现其中一些规律,例如，图,7.8,是把每个子集所含状态集对应的项目写在新的项目中而得到的,哪些项目在一个状态中呢？,LR(0),项目集规范族的构造,若某个状态中包含形如,A,B,的项目，则形如,B,的项目也在此状态中,为了完整地得到一个项目集,I,中所有可能的项目，这里先给出,I,的,闭包,CLOSURE(I),的构造方法：,I,原有的项目均在,CLOSURE(I),中,若,A,B,属于,CLOSURE(I),，则每一形如,B,的项目也属于,CLOSURE(I),重复,2,直到不出现新的项目为止,LR(0),项目集规范族的构造,识别活前缀的,DFA,的每个状态是一个项目集，所以现在的问题是如何逐步构造出它们，并确定它们之间的连接关系,先构造初态的项目集,其他状态的项目集如何求？,连接箭弧上的标记为前一个状态和后一个状态对应项目圆点间的符号,例如：对初态,S,E,E,aA,E,bB,，对其第一个项目，圆点右移一个位置后变为,S,E,，箭弧标记为,E,；对其第二个项目,E,aA,，圆点右移一个位置后，项目变为,E,aA,，箭弧标记为,a,；类似地，第三个项目圆点右移一位后项目变为,E,bB,，箭弧标记为,b,此时，初态发出了三个不同标记的箭弧，因而转向了三个不同的状态,LR(0),项目集规范族的构造,圆点后为终结符或在一个产生式的最后，则不会增加新的项目,前例中的,S,E,，新状态仅含该项目,新状态的初始项目是由原有项目集中的某个项目圆点右移一个位置后得到的，称为,核,，因为可以由它发展出新的项目,转换函数,这里定义一个统一的转换函数,GO(I,X)=CLOSURE(J),其中，,I,为包含于某一项目集的状态,X,为一文法符号，,X,VNVT,J=,任何形如,A,aX,的项目,|,A,aX,属于,I,转换函数,GO,函数可以变身为两个不同的函数，即前面一直强调的,LR,分析中所使用到的,ACTION,函数和,GOTO,函数,LR(0),项目集规范族的构造：总结,利用闭包函数和转换函数，不难给出依据前面所述方法来构造文法,G,的,LR(0),项目集规范族的具体步骤,置项目,S,S,为初态集的核，求其闭包而得到初态的项目集,对初态集及后来所发展出来的项目集应用转换函数,GO(I,X)=CLOSURE(J),求出新状态,J,的项目集,重复,2,直到不出现新的项目集为止,关于识别活前缀,DFA,构造方法的小结,三种方法,根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造,NFA,，再确定化为相应的,DFA,求出文法的所有项目，按一定的规则构造识别活前缀的,NFA,再确定化为,DFA,项目集规范族法,项目集规范族构造法：例,下面是有关的拓广文法，待识别的句子是,w=,abbcde,，同前,GS,:,S,S,S ,a,A,c,B,e,A,b,A,A,b,B,d,I,0,:,S,S,S,a,A,c,B,e,I,1,:,S,S,I,2,:,S,a,A,c,B,e,A,b,A,A,b,I,3,:,S,a,A,c,B,e,A,A,b,I,4,:A,b,I,5,:,S,a,A,c,B,e,B,d,I,7,:,S,a,A,c,B,e,I,8,:,B,d,I,9,:,S,a,A,c,B,e,I,6,:,A,A,b,S,a,A,b,b,c,B,e,d,w=,ab,b,cde,ACTION,表和,GOTO,表的构造,依据前面的状态图，不难得到相应的,ACTION,表和,GOTO,表,终结符带来的转换对应,ACTION,表中的状态转换，注意，句点在后的对应的是归约状态,(,但,S,S,对应结束状态,),非终结符带来的转换对应,GOTO,表中的状态转换,ACTION,表和,GOTO,表,LR(0),分析表与,LR(0),分析,如果所构造出的,LR(0),分析表不存在多重入口，那么所得到即为,LR(0),分析表；利用,LR(0),分析表进行分析的分析器称为,LR(0),分析器；能构造,LR(0),分析表的文法称为,LR(0),文法,LR(0),分析可能面临的问题,如果一个项目集中可以包含多种不同的项目，那么不允许下列项目同时存在：,移进和归约项目同时存在,即形如,A,a,的项目同时存在,B,原因：面临输入符号,a,时不能确定该移进,a,还是把归,约为,B,归约和归约项目同时存在,即形如,A,的项目同时存在,B,原因：这时不管当前面临什么输入符号，都不能确定,该归约为,A,，还是归约为,B,问题可能的解决方式,对上述两种可能的冲突形式，如果往后多看一个符号，问题可能会得到解决,