第七章LR分析法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二层,第三层,第四层,第五层,*,第7章,LR,分析法,学习目标：,掌握：,LR（0）,分析，,SLR（1）,分析,理解：活前缀，可归前缀,了解：,LR(1)、LALR(1),分析思想,7.1,LR,分析概述,7.2,LR(0),分析,7.3,SLR(1),分析,7.4,LR(1)、LALR(1),分析思想,回顾：自底向上分析实现的基本思想,“移进归约”方法,(,1),SaAcBe,(2),Ab,(3),AAb,(4),Bd,判断输入串,abbcde,#,是否为该文法的句子,归约（,SaAcBe,）,#,#,aAcBe,10）,接受,#,S,11）,移进,e,e#,#,aAcB,9）,归约（,Bd,）,e#,#,aAc,d,8）,移进,d,de#,#,aAc,7）,归约（,AAb,）,cde,#,#,a,Ab,5）,移进,c,cde,#,#,aA,6）,移进,b,bcde,#,#,aA,4）,归约（,Ab,）,bcde,#,#,a,b,3）,移进,b,bbcde,#,#,a,2）,移进,a,abbcde,#,#,1）,动作,输入符号串,符号栈,步骤,LR,分析法,：,根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的,K,个（,K=0）,符号就可唯一地确定句柄。,LR(K),的含义：,L,表示从左到右扫描输入串,R,表示最左规约（即最右推导的逆过程）,K,表示向右查看输入串符号的个数,当,K=1,时，能满足当前绝大多数高级语言编译程序的需要，所以着重介绍,LR(0),SLR(1),LR(1),LALR(1),方法,7.1,LR,分析概述,LR,分析的特点：,是规范归约,适用范围广，适用于大多数上下文无关文法描述的语言,分析速度快，能准确定位错误,缺点：,LR,分析器的构造工作量大,LR,分析器的组成,总控程序：所有,LR,分析器总控程序相同。,分析表：,不同文法有不同的分析表,同一文法采用的,LR,分析器不同，分析表也不同,分析表分为,ACTION,表,（动作表）和,GOTO,表,（状态转换表）。分析栈：,包括,状态栈,S,和,文法符号栈,X,。,分析表是,LR,分析器的核心,LR,分析表：,列标题为状态，行标题为文法符号,GOTO,表示当前状态面临文法符号时应转向的下一个状态。,ACTION,表示当前状态面临输入符号时应采取的动作,ACTION,GOTO,a,c,e,b,d,#,a,c,e,b,d,#,S,A,B,0,S,2,1,1,acc,2,S,S,1,3,3,r2,r2,r2,r2,r2,r2,为了节省空间，将,ACTION,和,GOTO,中关于终结符号的各列合并起来,ACTION,GOTO,a,c,e,b,d,#,a,c,e,b,d,#,S,A,B,0,S,2,1,1,acc,2,S,S,1,3,3,r2,r2,r2,r2,r2,r2,ACTION,GOTO,a,c,e,b,d,#,S,A,B,0,S2,1,1,acc,2,S1,S3,3,r2,r2,r2,r2,r2,r2,ACTION,表中的动作有4种：,移进(,S,k,)：,把状态,k,移入状态栈，若当前状态是,i，,且,k=,GOTOi,a,，,把,a,移入符号栈,归约(,r,k,)：,用第,k,条产生式进行归约，此时栈顶形成了句柄,，,文法中第,k,条产生式为,A-，,且|,|=r，,归约时从,状态栈,和,符号栈,中弹出,r,个符号，把,A,移入符号栈，,j=,GOTOi,A,移入状态栈，其中状态,i,为修改指针后的栈顶状态,接受(,acc)：,当符号栈只剩文法开始符,S，,并且当前输入符为，则分析成功,报错：,当状态栈顶的状态遇到了不应该出现的文法符号，则报错，说明输入串不是该文法的句子,LR,分析器的工作过程示意图,输入串,a,1,a,2,a,n,#,总 控 程 序,ACTION,表,GOTO,表,n,X,n,。,。,1,0,X,1,#,SP,输出,状态栈,文法符号栈,栈指针,LR,分析器：,在分析的每一步，通用的,总控程序,按照,状态栈,栈顶状态,i,和当前输入符号,a,查,LR,分析表,，并执行其中,ACTION,和,GOTO,规定的操作。,LR,分析例（,LR(0),分析）,文法,GS：(1)S-,aAcBe,(2)A-b(3)A-,Ab,(4)B-d,对输入串,abbede,进行,LR,分析,ACTION,GOTO,a,c,e,b,d,#,S,A,B,0,S2,1,1,acc,2,S4,3,3,S5,S6,4,r2,r2,r2,r2,r2,r2,5,S8,7,6,r3,r3,r3,r3,r3,r3,7,S9,8,r4,r4,r4,r4,r4,r4,9,r1,r1,r1,r1,r1,r1,LR(0),分析表为：,对输入串,abbcde,#,的分析过程,(1)S-,aAcBe,(2)A-b(3)A-,Ab,(4)B-d,acc,#,#,0,11,R1,#,#,aAcBe,023579,10,S9,e#,#,aAc,0235,9,R4,e#,#,aAc,d,02358,8,S8,de#,#,aAc,0235,7,S5,cde,#,#,a,02,6,R3,cde,#,#,a,Ab,0236,5,S6,bcde,#,#,a,02,4,R2,bcde,#,#,a,b,024,3,S4,bbcde,#,#,a,02,2,S2,abbcde,#,#,0,1,GOTO,ACTION,输入串,符号栈,状态栈,步骤,A,3,3,3,A,3,7,B,7,1,S,1,7.2,LR(0),分析,使用,LR(0),分析表的,LR,分析器称为,LR(0),分析器。,LR(0),分析器在分析的过程中只根据符号栈的内容就能确定句柄，不需要向右查看输入符号,对文法的限制较大，对绝大多数高级语言的语法分析器不适用,构造,LR(0),分析表的思想和方法是构造其他,LR,分析表的基础。,例,文法：(,1),SaAcBe,(2),Ab,(3),AAb,(4),Bd,判断输入串,abbcde,#,是否为该文法的句子,归约（,SaAcBe,）,#,#,aAcBe,10）,接受,#,#,S,11）,移进,e,e#,#,aAcB,9）,归约（,Bd,）,e#,#,aAc,d,8）,移进,d,de#,#,aAc,7）,归约（,AAb,）,cde,#,#,a,Ab,5）,移进,c,cde,#,#,aA6）,移进,b,bcde,#,#,aA,4）,归约（,Ab,）,bcde,#,#,a,b,3）,移进,b,bbcde,#,#,a,2）,移进,a,abbcde,#,#,1）,动作,输入符号串,符号栈,步骤,LR(k,),分析法通过,活前缀,来帮助确定句柄,规范句型的可归约前缀和活前缀(7.2.1),构造文法的识别活前缀及可归前缀的,DFA(7.2.2，7.2.3),按,DFA,构造相应分析表状态转换表和动作表(7.2.4),按分析表进行,LR(k,),分析(7.2.5),7.2.1 规范句型的可归约前缀和活前缀,什么是可归前缀？,什么是活前缀？,可归前缀和活前缀在,LR,分析中起什么作用？,前缀,如果,Z=,xy,是一符号串，则,x,是,Z,的前缀，其中,x,y,为任意符号串（包括空串,）,例：,abc,的前缀有,，a，ab，abc,。,可归前缀,规范句型中,句柄之前,包括,句柄在内,的串称为可归前缀。,例：文法,GS，,其中产生式后,i,是其编号,SaAcBe1Ab2AAb3Bd4,输入串,abbcde,的最右推导（规范推导）过程：,S,=,aAc,B,e,1=a,A,c,d,4e1=a,A,b,3cd4e1,=a,b,2b3cd4e1,最左归约(规范归约)过程：,a,b2,b3cd4e1,用产生式2归约,a,A,b3,cd4e1,用产生式3归约,a,A,c,d4,e1,用产生式4归约,aAc,B,e1,用产生式1归约,S,可归前缀有：,ab2，aAb3，aAcd4，aAcBe1,活前缀,定义：,形成,可归前缀,之前(包括可归前缀在内)的所有规范句型（符号栈内部分）的,前缀,称为,活前缀,。即规范句型的不含句柄右边符号的前缀称为活前缀。,例：规范句型,a,Ab,cde,(,下划线为句柄)的可归前缀为,aAb,，,活前缀为：,，a，aA，aAb,可归前缀和活前缀在,LR,分析中的作用,在,LR,分析过程中，实际上是把,活前缀,列出放在符号栈中，,一旦在栈中出现,可归前缀,，即,句柄,已经形成，就用相应的产生式进行归约，,在分析的过程中，只要符号栈中的符号串是一个,活前缀,，就可保证已被分析过的部分是该文法规范句型的正确部分。,归约（,SaAcBe,）,#,#,aAcBe,10）,接受,#,#,S,11）,移进,e,e#,#,aAcB,9）,归约（,Bd,）,e#,#,aAc,d,8）,移进,d,de#,#,aAc,7）,归约（,AAb,）,cde,#,#,a,Ab,5）,移进,c,cde,#,#,aA,6）,移进,b,bcde,#,#,aA,4）,归约（,Ab,）,bcde,#,#,a,b,3）,移进,b,bbcde,#,#,a,2）,移进,a,abbcde,#,#,1）,动作,输入符号串,符号栈,步骤,7.2.2 识别活前缀的有穷自动机,回顾：有穷自动机一种识别装置,分,DFA,和,NFA,0,X,1,3,1,0,4,Y,1,5,1,识别1(0|1)*101的,NFA,用有穷自动机来识别活前缀和可归前缀,有穷自动机如何构造？,一个特例：构造识别活前缀和可归前缀的有穷自动机,由文法的产生式构造识别,活前缀和,可归前缀的有穷自动机的方法,用有穷自动机来识别活前缀和可归前缀,(,规则,),有穷自动机的输入字符：终结符和非终结符,状态转换：每把一个符号进栈，就看成识别过了该符号，进行状态转换。因为,LR,分析时栈中始终保持是活前缀，所以有穷自动机识别过的符号串也是活前缀。,终态：当识别到可归约前缀（表明在栈中形成句柄），认为到达了识别句柄的终态，执行归约,例如：识别可归前缀,aAcBe,的有穷自动机,1,2,a,A,3,c,4,6,B,5,e,构造识别活前缀和可归约前缀的有穷自动机的一个例子：,由句子规范推导的逆过程直观的看出它的活前缀和可归前缀,按活前缀和可归前缀构造识别它们的有穷自动机,例,文法,G：SaAcBe1Ab2,AAb3Bd4,拓广文法为：,S-S0SaAcBe1,Ab2AAb3Bd4,拓广原因：文法开始符,S,可能出现在产生式的右部，在归约过程中，不能判断是归约到文法的最初开始符，还是归约到在产生式右部出现的开始符，,S,只在产生式左部出现，确保不会混淆。,S-S0SaAcBe1,Ab2AAb3Bd4,输入串,abbcde,的最右推导过程：,S,=,S,0=,aAc,B,e,1=a,A,c,d,4e1,=a,A,b,3cd4e1=a,b,2b3cd4e1,可归前缀有：,ab2，aAb3，aAcd4，aAcBe1，S0,输入串,abbcde,的可归前缀有：,S0，ab2，aAb3，aAcd4，aAcBe1,识别其活前缀和可归前缀的,NFA,为：,X,0,2,5,9,14,1,S,*,3,a,4,b,6,a,A,7,8,b,10,a,A,11,c,12,13,d,15,a,A,16,c,17,19,B,18,e,识别活前缀和可归前缀的,NFA,所有的状态都是活前缀的识别状态,终态是句柄的识别态,带“*”号的状态既是句柄识别态又是句子识别态，句子识别态仅有一个,符号栈,输入串,动作,#,abbcde,#,移进,a,#,a,bbcde,#,移进,b,#,ab,bcde,#,归约(,A-b),#,aA,bcde,#,移进,b,#,aAb,cde,#,归约(,A-,Ab,),#,aA,cde,#,移进,c,#,aAc,de#,移进,d,#,aAcd,e#,归约(,B-d),#,aAcB,e#,移进,e,#,aAcBe,#,归约(,S-,aAcBe,),#,S,#,接受,X,2,a,1,*,S,A,4,5,b,3,b,6,c,7,d,B,8,9,e,识别活前缀和可归前缀的,DFA,理解识别活前缀和可归前缀的,DFA,和分析过程的对应,将,NFA,确定化得到：,S0，ab2，aAb3，aAcd4，aAcBe1,ACTION,GOTO,a,c,e,b,d,#,S,A,B,X,S2,1,1,acc,2,S3,4,3,r2,r2,r2,r2,r2,r2,4,S6,S5,5,r3,r3,r3,r3,r3,r3,6,S7,8,7,r4,r4,r4,r4,r4,r4,8,S9,9,r1,r1,r1,r1,r1,r1,对任何一个上下文无关文法只要构造出它的识别活前缀和可归前缀的有穷自动机，就可以构造其相应的分析表（,ACTION,表和,GOTO,表），进行,LR,分析,S0，ab2，aAb3，aAcd4，aAcBe1,X,2,a,1,*,S,A,4,5,b,3,b,6,c,7,d,B,8,9,e,识别活前缀和可归前缀的,DFA,以上示例中构造,DFA,的方法是通过一个句子的归约过程确定可归前缀，但是：,对于一个复杂的文法，其可归前缀不是如此简单就能计算出来,示例中用一个句子归约过程的所有活前缀和可归前缀构造出的,DFA，,恰好也是识别整个文法的活前缀和可归前缀的,DFA，,这仅是一个特殊情况。,对一个上下文无关文法需要求出它的所有活前缀和可归前缀后才能构造其识别该文法活前缀的,DFA,由文法的产生式构造识别活前缀和可归前缀的,DFA,的方法,1.,LR(0),项目,文法的识别活前缀的有穷自动机以“项目”作为它的状态,在文法,G,中每个产生式的右部适当位置添加一个圆点构成项目,例：产生式,UXYZ,对应有4个项目,0,U XYZ1 UX YZ,2 UXY Z3 UXYZ,产生式,A,只有一个项目,A,项目的含义：,圆点在最左部（,U XYZ,）表示希望用产生式的右部归约,圆点的左部（,UX YZ,）表示分析过程中已识别过的部分,圆点的右部（,UX YZ,）表示待识别部分,圆点达到最右边（,UXYZ,）表示句柄已形成，可以进行归约。,LR(0),项目分类,移进项目：,形如,A,的项目，其中,V,T,V*。,即圆点后面为,终结符,的项目。,分析时把,移进符号栈。,待约项目：,形如,AB,的项目，其中,BV,N,V*。,即圆点后面为,非终结符,的项目。,表明用产生式,A,的右部归约时，首先要将,B,的产生式右部归约为,B，,对,A,的右部才能继续进行分析。也就是期待着继续分析过程中首先能归约得到,B,归约项目：,形如,A,的项目，,V,*,=,对应的项目为,A-,即圆点在最右端的项目。,表明该产生式的右部已分析完，句柄已形成，可以把,归约为,A。,接受项目：,当归约项目为,SS,，其中,S,是文法开始符,即对文法开始符的归约项目。,表明输入串可归约为文法开始符，分析结束。,开始项目：,形如,SS,的项目，其中,S,是文法开始符。,即拓广文法开始符的产生式圆点在最左边的项目。,2.构造识别活前缀的有穷自动机,构造识别活前缀的,NFA,拓广文法,GS,为,GS，,即加入产生式,SS,以,GS,的每个项目为,NFA,的一个状态，,SS,为初态，其余每个状态都为活前缀的识别态，所有归约项目为终态(句柄识别态)，,SS,为接受态,确定状态转换关系：,若有项目,i：AX,，,项目,j：AX,，,则从状态,i,到状态,j,连一条标记为,X,的箭弧。,若,XV,N,，,对于,X,的所有产生式圆点在最左边的状态,k:Xr,，,都从状态,i,到状态,k,连一条标记为,的箭弧。,用子集法把,NFA,确定化为,DFA,例 文法,G：,EaA,|,bB,AcA,|d,BcB,|d,拓广文法,G：SE,EaA,|,bB,AcA|d,BcB,|d,G,的所有,LR(0),项目为：,1,SE2SE 3EaA,4EaA 5EaA6AcA,7AcA8AcA9Ad,10.,Ad,11.,EbB,12.,EbB,13.,EbB,14.,BcB,15.,BcB,16.,BcB,17.,Bd,18.,Bd,识别,G,活前缀的,NFA,*,d,c,d,d,a,B,B,A,A,E,1,11,12,3,2,4,5,14,15,17,6,9,7,8,10,18,16,13,c,G,的所有,LR(0),项目为：,1,SE2SE 3EaA,4EaA 5EaA6AcA,7AcA8AcA9Ad,10.,Ad,11.,EbB12.,EbB,EbB,14.,BcB,15.,BcB,BcB,Bd,Bd,识别,G,活前缀的,DFA,c,b,a,I,0,：SE,EaA,EbB,I,4,：AcA,AcA,Ad,I,2,：EaA,AcA,Ad,I,3,：EbB,BcB,Bd,I,5,：BcB,BcB,Bd,I,1,：S E,I,8,：A,cA,I,10,：A d,I,6,：E,aA,I,7,：E,bB,I,11,：B d,I,9,：B,cB,E,c,c,B,d,d,B,A,d,d,A,c,通过列出拓广文法的,所有项目,，进而构造识别活前缀的,NFA,，,再确定化为,DFA,的方法，工作量较大，不实用,实用的方法是直接构造以项目集,为,状态,的识别活前缀的,DFA,7.2.3 构造以,LR(0),项目集为状态的识别活前缀的,DFA,LR(0),项目集规范族,识别一个文法活前缀的,DFA,的每个状态都是一个项目集，项目集(状态)的全体称为这个文法的,LR(0),项目集规范族。,识别活前缀的,DFA,的构造,如何构造,DFA,的一个状态（项目集,）,如何由,DFA,的一个状态求其他状态,1 项目集,I,的闭包,CLOSURE(I),如果,I,是文法,G,的一个项目集，定义和构造,I,的闭包,CLOSURE(I),如下：,I,的项目均在,CLOSURE(I),中；,若,AB,属于,CLOSURE(I)，B,V,N,，则,每一形如,Br,的项目也属于,CLOSURE(I),重复,b）,直到,CLOSURE(I),不再扩大为止。,说明：圆点后为终结符或在一个产生式的最后，求闭包时不会增加新的项目,例,SE,EaA,|,bB,AcA|d,BcB,|d,I=SE,则,CLOSURE(I)=,SE，EaA，EbB,CLOSURE(I),作为,DAF,的一个状态,2.状态转换函数,GO(I,X),由,DFA,的一个状态求其他状态通过,状态转换函数,设,I,为文法,G,的某一项目集(状态)，,X,V,N,V,T,则,GO(I,X)=CLOSURE(J),其中,J=,任何形如,AX,的项目,A,XI,称,J,为“核”,例,SE,EaA,|,bB,AcA|d,BcB,|d,I=,SE，EaA，EbB,，,则,GO(I,E)=CLOSURE(SE)=SE,GO(I,a,)=,CLOSURE(EaA,)=,EaA,AcA,Ad,GO(I,b)=CLOSURE(,EbB,)=,EbB,BcB,Bd,3.构造以,LR(0),项目集为状态的,DFA,构造初始状态,IS,0,=CLOSURE(SS)，,并且它是未被标记的。,从已经构造的,DFA,部分图中选择一个未被标记的状态,IS,i,，,标记,IS,i,，,若项目集,IS,i,中含有项目,U-,xRy(R,V,x,y,为任一符号串,)，且,GO(IS,i,R,)=,IS,j,，,若,IS,j,不在,DFA,中，则将,IS,j,作为未被标记的加入,DFA,中，且从,IS,i,出发引一条标记为,R,的弧到,IS,j,，,重复,b),直到没有未被标记的状态为止。,例 拓广文法,G：SE,EaA,|,bB,AcA|d,BcB,|d,构造以,LR(0),项目集为状态的,DFA,SE,SE,EaA,a,EbB,E,b,EaA,AcA,c,A,Ad,EbB,BcB,c,Bd,AcA,A,BcB,B,d,c,d,d,B,c,d,EaA,EbB,I,0,I,1,I,2,I,3,I,4,I,5,I,6,I,7,I,8,I,9,I,10,I,11,AcAAd,BcBBd,AcAAd,BcBBd,7.2.4,LR(0),分析表的构造,分析表的组成：,动作表(,ACTION),：,表示当前状态下面临,输入符,应做的动作是移进、归约、接受或出错，面临的输入符只包含,终结符,和,转换表(,GOTO)：,表示在当前状态下面临,文法符号,时应转向的下一个状态,为了节省存储空间，把关于,终结符,部分的,GOTO,表和,ACTION,表重叠，也就是把当前状态下面临,终结符,应做的移进归约动作和转向动作表示在一起,LR(0),分析表的构造算法,设已构造出,LR(0),项目集规范族,为,C=I,0,，I,1,，I,n,，,令项目集,I,k,对应的状态为,k，,含,SS,项目的项目集对应的状态为初始状态,分析表的,ACTION,表和,GOTO,表构造步骤为：,若项目,AaI,k,，aV,T,，,且,GO(I,k,a,)=,I,j,，,则置,ACTIONk,a,=,S,j,若项目,ABI,k,，BV,N,，,且,GO(I,k,B,)=,I,j,，,则置,GOTOk,B,=j,若项目,AI,k,，,且产生式,A,的编号为,j，,则对任何,a（,终结符和#），置,ACTIONk,a,=,r,j,若项目,SSI,k,，,则置,ACTIONk,#=acc,不能用上述方法填入的分析表的元素均应填上“报错标志”。,拓广文法,G：,(0)SE(1),Ea,A,(2),EbB,(3),Ac,A4),Ad,(5),BcB,(6),Bd,识别活前缀的,DFA：,SE,SE,EaA,a,EbB,E,b,EaA,AcA,c,A,Ad,EbB,BcB,c,Bd,AcA,A,BcB,B,d,c,d,d,B,c,d,EaA,EbB,I,0,I,1,I,2,I,3,I,4,I,5,I,6,I,7,I,8,I,9,I,10,I,11,AcAAd,BcBBd,AcAAd,BcBBd,10,a,ACTION,b,c,d,#,E,GOTO,A,状态,11,9,8,7,6,5,4,3,2,1,0,B,LR(0),分析表,1,S,2,S,3,acc,4,S,5,S,6,7,S,8,S,9,r,1,r,1,r,1,r,1,r,1,10,S,5,S,6,r,4,r,4,r,4,r,4,r,4,r,2,r,2,r,2,r,2,r,2,11,S,9,S,8,r,6,r,6,r,6,r,6,r,6,r,3,r,3,r,3,r,3,r,3,r,5,r,5,r,5,r,5,r,5,7.2.5,LR(0),分析器的工作过程,工作过程：,根据,分析栈的栈顶状态,和,输入串的当前符号,查,分析表,确定应采取的动作（移进、归约、接受或报错），对,状态栈,和,符号栈,进行相应的操作。,具体说明如下：,若,ACTIONS,a,=,Sj，a,为终结符，,则把,a,移入符号栈，,j,移入状态栈；,若,ACTIONS,a,=rj，a,为终结符或，,则用第,j,个产生式（,A-,）,归约，将两个栈弹出,k,个元素，其中,k,为第,j,个产生式右部符号串长度，这时当前面临符号为第,j,个产生式左部的非终结符（,A）；,若状态栈当前的栈顶状态为,S,k,，,且,GOTOS,k,A,=j，,则非终结符,A,移入符号栈，,j,移入状态栈；,若,ACTIONS,a,=,acc,a,为，,则为接受，表明分析成功；,若,ACTIONS,a,=,空白，则转向出错处理。,(0)SE(1),Ea,(2),EbB,(3),Ac,(4),Ad,(5),BcB,(6),Bd,输入串,bccd,的分析过程,步骤,状态栈,符号栈,输入串,ACTION,GOTO,1,2,3,4,5,6,7,8,9,0,#,bccd,#,S,3,03,#,b,ccd,#,S,8,038,#,bc,cd,#,S,8,0388,#,bcc,d#,S,9,03889,#,bccd,#,#,#,#,#,r,6,11,0388,#,bcc,r,5,11,038,#,bc,r,5,7,03,#,b,r,2,1,0,#,acc,B,(11),B,(11),B,7,E,1,7.3,SLR(1),分析,项目集中的冲突,一个项目集中存在下列情况称为项目冲突：,移进归约冲突,移进项目,Aa,和归约项目,Br,同在一个项目集中，当面临输入符,a,时，不能确定移进,a,还是把r,归约为,B；,归约归约冲突,归约项目,A,和归约项目,Br,同在一个项目集中，不管面临什么输入符都不能确定把,归约为,A,还是把,r,归约为,B。,一个文法的,LR(0),项目集规范族,中的,项目集,不存在,移进归约,冲突，也不存在,归约归约,冲突时，称该文法为,LR(0),文法,。,例：文法,G,(0)SS(1),SrD,(2),DD,i,(3),Di,识别文法活前缀的,DFA,：,SS,SS,SrD,r,S,SrD,DD,i,D,Di,DD,i,i,SrD,I,0,I,1,I,2,I,3,I,4,I,5,DD,i,Di,DD,i,i,I,6,在项目集,I,3,中,SrD,为归约项目，DD,i,为移进项目，,存在移进归约冲突，该文法不是,LR(0),文法,2.解决冲突的,SLR(1),方法,基本思想：,对于,LR(0),有,冲突,的,项目集,用,向前查看,输入符号串的一个符号的办法加以解决,解决方法：,对归约项目,Ar,只有当输入符号,aFOLLOW(A,),才进行归约，缩小归约范围，有可能解决冲突。,例：文法,G,(0)SS(1),SrD,(2),DD,i,(3),Di,识别文法活前缀的,DFA,：,SS,SS,SrD,r,S,SrD,DD,i,D,Di,DD,i,i,SrD,I,0,I,1,I,2,I,3,I,4,I,5,DD,i,Di,DD,i,i,I,6,Follow,集,S,#,S,#,D,#,对项目集,I,3,，,若当前输入符为#时，进行归约，若当前输入符为,，进行移进操作，冲突得以解决,SLR(1),的处理方法,(,算法,),：,例：一个,LR(0),规范族中项目集,I,含有冲突项目,I=,Xbr,其中,bV,T,，,如果,FOLLOW(A),和,FOLLOW(B),互不相交，且不含,b，,则当状态,I,面临某输入符,a,时，可采用下列动作：,若,a=b，,则移进；,若,aFOLLOW(A,)，,则用产生式,Ar,归约；,若,aFOLLOW(B,)，,则用产生式,B,归约；,此外，报错。,一般地，一个,LR(0),规范族中的项目集,I,有,m,个移进项目：,A,1,1,a,1,1,，,A,2,2,a,2,2,，,A,m,m,a,m,m,n,个归约项目：,B,1,r,1,，B,2,r,2,，,B,n,r,n,，,若移进符号集,a,1,，a,2,，a,m,和,FOLLOW(B,1,)，FOLLOW(B,2,)，,FOLLOW(B,n,),两两交集为空，,则当状态,I,面临某输入符,a,时，可采用以下动作：,若,aa,1,，a,2,，a,m,，,则移进；,若,aFOLLOW(B,i,)，i,=1,2,n，,则用,B,i,r,i,归约；,此外，报错。,上述解决项目集(状态)中冲突的方法称为,SLR(1),方法（,Simple,因为只对有,冲突的状态才向前查看一个符号，以确定动作）,如果一个文法的,LR(0),项目集规范族,中某些,项目集,所含有的,动作冲突都,能用,SLR(1),方法解决，则称这个文法为,SLR(1),文法,SLR(1),分析表的构造算法,与,LR(0),分析表的构造类似，仅在,含有冲突,的项目集中分别进行处理。,改进,的,SLR(1),方法：,对,所有,的归约项目仅对,当前输入符号,包含在该,归约项目,左部,非终结符,的,FOLLOW,集中,，才采取归约动作。,改进,的,SLR(1),分析表的构造方法,：,设已构造出,LR(0),项目集规范族为,C=I,0,，I,1,，I,n,，,令项目集,I,k,对应的状态为k，,含,SS,项目的项目集为初态，分析表的,ACTION,表和,GOTO,表构造步骤为：,若项目,AaI,k,，,aV,T,，,且,GO(I,k,a,)=,I,j,，,则置,ACTIONk,a,=,S,j,；,若项目,ABI,k,，,BV,N,，,且,GO(I,k,B,)=,I,j,，,则置,GOTOk,B,=j；,若项目,AI,k,，,且产生式,A,的编号为,j，,则对任何,a(,终结符和#)，,且,aFOLLOW(A,),，,置,ACTIONk,a,=,r,j,；,若项目,SSI,k,，,则置,ACTIONk,#=acc；,不能用上述方法填入的分析表元素均应填上“报错标志”。,例 文法G：(0)SS(1),SrD,(2)DD,i(3),Di,FOLLOW(S)=#FOLLOW(S)=#FOLLOW(D)=#，,SS,SS,SrD,r,S,SrD,DD,i,Di,DD,i,i,SrD,I,0,I,1,I,2,I,3,I,4,I,5,DD,i,Di,DD,i,i,I,6,D,状态,ACTION,GOTO,r,i,#,S,D,0,S,2,1,1,acc,2,S,4,3,3,S,5,r,1,4,r,3,r,3,5,S,6,6,r,2,r,2,7.4,LR(1)、LALR(1),分析思想,仍有许多文法构造的,LR(0),项目集规范族存在的动作冲突不能用,SLR(1),方法解决,例如文法,G:,(0)S S(1)S L=R(2)S R(3)L*R(4)L i(5)R L,识别文法活前缀的,DFA,I,0,:,S,S,S,L=R,S,R,L *R,L,i,R,L,I,5,:L i,I,2,:,SL =R,R L,I,3,:,S R,I,4,:L*R,R L,L *R,L i,I,1,:,S,S,I,6,:S L=R,R L,R L,L i,L *R,I,7,:,L*R,I,8,:,R L,I,9,:S L=R,S,L,R,*,i,=,R,L,*,i,R,L,i,*,I,6,:S L=R,R L,R L,L i,L *R,Follow(R,)=#,=,与移进符号集*,i,交集为空，可用,SLR(1),方法解决冲突,I,2,:,S-L =R,R-L,Follow(R,)=#,=,与移进符号集=,交集不为空，,SLR(1),方法不能解决冲突，,该文法不是,SLR(1),文法。,S S,S L=R|R,L*R|i,R L,Follow,S,#,S,#,L,=，#,R,#，=,SLR(1),用,FOLLOW,信息作为展望信息（只对属于,FOLLOW,集的输入符号归约），缩小了归约范围，消除了一些无效归约，解决了项目集中的一些简单的冲突。,尽管,FOLLOW(A),中包含了所有含,A,的句型中,A,后的可能终结符，但,并不是每个含有,A,的句型中，,A,的后面都可以出现,Follow(A,),中的每一个符号,，所以,SLR(1),未能从根本上消除所有无效归约。,S SS L=R|R L*R|i R L,S,S,L,=,R,*,R,L,在句型,*L=R,中，,L,可以被归约为,R，,此时,L,后只能是=，而不能是,Follow(R,)=#,=,中的,S,S,L,1,=,R,L,2,在句型,L,1,=L,2,中，,L,2,可以被归约为,R，,此时,L,2,后只能是#，而不能是,Follow(R,)=#,=,中的=,LR(1),方法正是要解决,SLR(1),方法在某些情况下存在的无效归约问题。,7.4.1,LR(1),分析思想,LR(1),分析的基本思想,LR(1)方法按每个具体的句型设置展望信息。,例：如果存在如下的一些句型,Aa,，,Ab,，,Ac,，,则,FOLLOW(A)=,a,b,c,处理到句型,A,，,只当输入符号为,a,时归约；,处理到句型,A,，,只当输入符号为,b,时归约；,处理到句型,A,，,只当输入符号为,c,时归约；,LR(1),分析,若,A,B,属于项目集,I,时，则,B,也属于,I，,把,FIRST(,),作为用产生式,B,归约的搜索符（用以代替,SLR(1),分析中的,FOLLOW(B),），并把此搜索符号的集合也放在相应项目的后面，这种处理方法即为,LR(1),方法,I,0,:,S,S,#,S,BB,#,B,aB,a/bB,b,a/b,I,1,:,S,S,#,I,2,:,S,B,B,#,B,a B,#,B,b,#,I,5,:,S,B B,#,I,6,:,B,a,B,#,B,aB,#,B,b,#,I,9,:,B,a B,#,I,4,:,B b,a/b,I,3,:,B a,B,a/b,B,aB,a/b,B,b,a/b,I,8,:,B a B,a/b,I,7,:,B b,#,S,B,b,b,B,b,b,a,a,a,B,B,a,文法,G：(0)S,S (1)B,aB,(2)S BB (3)B b,LR(1),项目集和转换函数,心,向前搜索符集合,LR(1),的优缺点：,优点：,LR(1),分析对搜索符的计算方法比较确切，没有无效归约，适应的文法更广,缺点：,LR(1),分析表的状态数目庞大。,7.4.2,LALR(1),分析思想,LALR(1),方法是介于,SLR(1),和,LR(1),之间的一种方法，即其功能比,SLR(1),强，比,LR(1),弱。,它具有,SLR(1),的状态数少的优点和,LR(1),的适用范围广的优点。,LALR(1),分析,对,LR(1),项目集规范族,合并,同心集,，若合并同心集后不产生新的冲突，则为,LALR(1),项目集,LALR(1),分析大大减少项目集（状态）的数目。,分析可发现,I,3,和,I,6,，,I,4,和,I,7,，,I,8,和,I,9,分别为同心集,I,3B a,B,a/b,B,aB,a/b,B,b,a/b,I,6,:,B,a,B,#,B,aB,#,B,b,#,I,4,:,B b,a/b,I,7,:,B b,#,I,8,:,B a B,a/b,I,9,:,B,a B,#,I,3,6,:,B,a,B,a/b/#,B,aB,a/b/#,B,b,a/b/#,合并为,I,4,7,:,B b,a/b/#,合并为,I,8,9,:,B,a B,a/b/#,合并为,同心集合并后不包含冲突，是,LALR(1),项目集,本章小结,LR(0)、SLR(1)、LR(1)、LALR(1),方法比较,实际上不同,LR,方法之间的主要区别就在于,归约的判定方法,上：,LR(0),是不看展望符判定归约；,SLR(1),是看展望符，但把所有,B,的展望符集均定义为,Follow(B,),。,即把符号栈顶上的句柄,归约为,B,的条件是：展望符为,Follow(B,),中的元素。换句话说，归约任何位置上的,B,，,都用统一的展望符集；,LR(1),也是看展望符，但归约不同位置上的,B,时，采用不同的展望符集。每个,项由心与向前搜索符组成，搜索符长度为1。,由于,LR(1),方法对于归约条件的判定比,SLR(1),更精确，可大大减少移入,/,归约冲突；,LALR(1):,对,LR(1),项目集规范族合并同心集,LR(0)、SLR(1)、LR(1)、LALR(1),分析表比较,LR(0),分析表局限性大，但其构造方法是其他构造方法的基础；,SLR,分析表虽然不是对所有文法都存在，但这种分析表较易实现又极有使用价值；,LR,分析表的分析能力最强，能适用于一大类文法，但是，实现代价过高（表过大）；,LALR,分析表的能力介于,SLR,和,LR,之间，实现效率较高。,语法分析,语法分析器的功能,识别输入字符串的合法性和语法结构，检查程序是否有语法上的错误,语法分析器的输入,如果词法分析作为独立的一遍，那么语法分析器的输入是词法分析后的结果,Token,序列,如果词法分析不是独立的一遍，那么词法分析是语法分析器的一个子程序，每调用一次词法分析就读出一个单词，并将其