编译原理教案- LR分析.ppt

LR分析,自下而上语法分析算法之,复习：移进-归约分析,文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1）#abbcde#移进,2）#a bbcde#移进,4）#aA bcde#移进,6）#aA cde#移进,7）#aAc de#移进,9）#aAcB e#移进,11）#S#接受,分析符号串abbcde是否GS的句子,对输入串abbcde#的移进-规约分析过程,在步骤3中，用Ab归约在步骤5中，用AAb归约问题：何时移进？何时归约？用哪个产生式归约？,3）#ab bcde#归约(Ab),5）#aAb cde#归约(AAb),4）#aA bcde#移进,6）#aA cde#移进,分析：已分析过的部分在栈中的前缀不同，而且移进和归约后栈中的状态会发生变化我们引入一个新的状态栈来表示符号栈中的符号目前状态用LR分析表来表示不同状态下对于各输入符号应采取的动作,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,6）#aA cde#移进 023 S5,7）#aAc de#移进 0235 S8,9）#aAcB e#移进 02357 S9,11）#S#接受 01 acc,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(AAb)0236 r3 3,8）#aAcd e#归约(Bd)02358 r4 7,10）#aAcBe#归约(SaAcBe)023579 r1 1,状态栈,ACTION,GOTO,文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d,Si:移进，并将状态i进栈ri:用第i个产生式归约，同时状态栈与符号栈退出相应个符号，根据GOTO表将相应状态入栈,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,6）#aA cde#移进 023 S5,7）#aAc de#移进 0235 S8,9）#aAcB e#移进 02357 S9,11）#S#接受 01 acc,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(AAb)0236 r3 3,8）#aAcd e#归约(Bd)02358 r4 7,10）#aAcBe#归约(SaAcBe)023579 r1 1,状态栈,ACTION,GOTO,文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d,Si:移进，并将状态i进栈ri:用第i个产生式归约，同时状态栈与符号栈退出相应个符号，根据GOTO表将相应状态入栈,问题：对于一个文法，状态集是如何确定的？LR分析表是如何得到的？,可归前缀与活前缀,文法GS：(1)S aAcBe1(2)A b2(3)A Ab3(4)B d4,S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1,每次归约句型的前部分依次为：ab2aAb3aAcd4aAcBe1,规范句型的这种前部分符号串称为可归前缀我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀,a,ab,a,aA,aAb,a,aA,aAc,aAcd,a,aA,aAc,aAcB,aAcBe,活前缀（Viable Prefixes）,viable:adjcapable of growing and developingcapable of being put into practice:workable定义：S A 是文法G中的一个规范推导，如果符号串是的前缀，则称是G的一个活前缀。,LR分析需要构造识别活前缀的有穷自动机我们可以文法的终结符和非终结符都看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态。,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,6）#aA cde#移进 023 S5,7）#aAc de#移进 0235 S8,9）#aAcB e#移进 02357 S9,11）#S#接受 01 acc,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(AAb)0236 r3 3,8）#aAcd e#归约(Bd)02358 r4 7,10）#aAcBe#归约(SaAcBe)023579 r1 1,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,对输入串abbcde#的LR分析过程,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,对输入串abbcde#的LR分析过程,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(AAb)0236 r3 3,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,6）#aA cde#移进 023 S5,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(AAb)0236 r3 3,状态栈,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,6）#aA cde#移进 023 S5,7）#aAc de#移进 0235 S8,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(AAb)0236 r3 3,状态栈,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,6）#aA cde#移进 023 S5,7）#aAc de#移进 0235 S8,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(AAb)0236 r3 3,8）#aAcd e#归约(Bd)02358 r4 7,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,6）#aA cde#移进 023 S5,7）#aAc de#移进 0235 S8,9）#aAcB e#移进 02357 S9,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(AAb)0236 r3 3,8）#aAcd e#归约(Bd)02358 r4 7,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,6）#aA cde#移进 023 S5,7）#aAc de#移进 0235 S8,9）#aAcB e#移进 02357 S9,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(AAb)0236 r3 3,8）#aAcd e#归约(Bd)02358 r4 7,10）#aAcBe#归约(SaAcBe)023579 r1 1,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1）#abbcde#移进 0 S2,2）#a bbcde#移进 02 S4,4）#aA bcde#移进 023 S6,6）#aA cde#移进 023 S5,7）#aAc de#移进 0235 S8,9）#aAcB e#移进 02357 S9,11）#S#接受 01 acc,对输入串abbcde#的LR分析过程,3）#ab bcde#归约(Ab)024 r2 3,5）#aAb cde#归约(AAb)0236 r3 3,8）#aAcd e#归约(Bd)02358 r4 7,10）#aAcBe#归约(SaAcBe)023579 r1 1,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,如何构造识别活前缀的有限自动机,已经有了活前缀如何构造有限自动机?活前缀及其可归前缀的一般计算方法,文法GS：S S0S aAcBe1A b2A Ab3B d4,句子abbcde的可归前缀如下：S0ab1aAb3aAcd4aAcBe1,构造识别其活前缀及可归前缀的有限自动机如下：,1,0,4,3,8,7,13,12,10,18,2,5,9,14,6,17,15,16,11,10,S,a,b,a,A,b,a,A,c,d,a,A,c,B,e,*,1,*,句子识别态,i,句柄识别态,1,0,4,3,8,7,13,12,10,18,2,5,9,14,6,17,15,16,11,10,S,a,b,a,A,b,a,A,c,d,a,A,c,B,e,*,X,加上开始状态X,确定化,X,1,3,2,4,6,8,5,9,S,a,b,A,b,c,B,e,d,7,*,识别活前缀的确定的有限自动机,活前缀及其可归前缀的一般计算方法,定义：文法G，AVN,LC(A)=|S A,V*,VT*规范推导中在非终结符A左边所有可能出现的符号串的集合推论：若文法G中有产生式BA，则有LC(A)LC(B)*,文法GS：S S0S aAcBe1A b2A Ab3B d4,由前面的定义与推论我们知：LC(S)=LC(S)=LC(S)*LC(A)=LC(S)*a LC(A)*LC(B)=LC(S)*aAc,化简为：S=S=SA=Sa+A B=SaAc,求解方程组可得：S=S=A=a+A B=aAc,A=a|A,A=a*=a,这样我们求出了每个非终结符在规范推导中用该非终结符的右部替换该非终结符之前，它的左部可能出现的所有前缀，也就是在规范归约过程中用句柄归约成该非终结符之前不包括句柄的活前缀。,不包括句柄的活前缀+句柄=？,可归前缀？,令 LR(0)C(A)=LC(A)*,文法G的可归前缀有：LR(0)C(S S)=S*S=S LR(0)C(S aAcBe)=S*aAcBe=aAcBe LR(0)C(A b)=A*b=ab LR(0)C(A Ab)=A*Ab=aAb LR(0)C(B d)=B*d=aAcd,总结：如何构造识别文法活前缀的有限自动机？,1、根据文法算出其可归前缀2、根据可归前缀，构造识别文法活前缀的不确定有限自动机3、确定化，从而构造出识别文法活前缀的确定的有限自动机,参见课本P124的例子,LR分析器的构造,1、构造识别文法活前缀的确定有限自动机2、根据该自动机构造相应的分析表(ACTION表、GOTO表),总控程序,Action/Goto表,输入符号串,输出,状态与符号栈,这种方法构造识别可归前缀的有限自动机从理论的角度讲是比较严格的，但实现起来却很复杂是否存在一种比较实用的方法？,由文法的产生式直接构造识别活前缀和可归前缀的有限自动机项目（item）：在每个产生式的右部适当位置添加一个圆点构成项目例如：产生式S aAcBe对应有6个项目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aAcB e 5 S aAcBe 有限自动机的每一个状态由一个项目构成,项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分，圆点右部表示待识别的部分。构造识别活前缀的NFA：1、把文法的所有产生式的项目都引出，每个项目都为NFA的一个状态2、确定初态、句柄识别态、句子识别态3、确定状态之间的转换关系*若项目i为 X X1X2.Xi-1 Xi.Xn项目j为 X X1X2.Xi-1 Xi Xi+1.Xn则从状态i到状态j连一条标记为Xi的箭弧*若i为X A，k为A，则从状态i画标记为 的箭弧到状态k,文法G：S EE T+E E TT int*T T int T(E),文法的项目有：1、S E2、S E 3、E T+E4、E T+E5、E T+E6、E T+E 7、E T8、E T 9、T int*T10、T int*T11、T int*T12、T int*T,13、T int 14、T int 15、T(E)16、T(E)17、T(E)18、T(E),NFA for Viable Prefixes of the Example,T.(E),T(.E),T(E.),T(E).,(,E,),S E.,E.T+E,E T.+E,E T+.E,E T+E.,S.E,E.T,E T.,T int.,T.int,T.int*T,T int*T.,T int*.T,T int.*T,e,e,e,e,E,e,T,e,e,e,E,+,e,int,int,*,T,e,e,e,e,e,T,e,NFA for Viable Prefixes in Detail(1),S.E,NFA for Viable Prefixes in Detail(2),S.E,NFA for Viable Prefixes in Detail(3),S E.,E.T+E,S.E,E.T,e,E,e,NFA for Viable Prefixes in Detail(4),T.(E),S E.,E.T+E,S.E,E.T,E T.,T.int,T.int*T,e,e,E,e,e,e,T,NFA for Viable Prefixes in Detail(5),T.(E),S E.,E.T+E,S.E,E.T,E T.,T.int,T.int*T,e,e,E,e,e,e,e,e,e,T,NFA for Viable Prefixes in Detail(6),T.(E),T(.E),(,S E.,E.T+E,S.E,E.T,E T.,T.int,T.int*T,e,e,E,e,e,e,e,e,e,T,NFA for Viable Prefixes in Detail(7),T.(E),T(.E),(,S E.,E.T+E,S.E,E.T,E T.,T.int,T.int*T,e,e,e,e,E,e,e,e,e,e,e,T,T(E.),E,NFA for Viable Prefixes in Detail(8),T.(E),T(.E),(,S E.,E.T+E,S.E,E.T,E T.,T.int,T.int*T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T(E.),E,T(E).,),NFA for Viable Prefixes in Detail(9),T.(E),T(.E),(,S E.,E.T+E,S.E,E.T,E T.,T.int,T.int*T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T(E.),E,T(E).,),E T+.E,+,NFA for Viable Prefixes in Detail(10),T.(E),T(.E),(,S E.,E.T+E,S.E,E.T,E T.,T.int,T.int*T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T(E.),E,T(E).,),E T+.E,+,e,e,E T+E.,E,NFA for Viable Prefixes in Detail(11),T.(E),T(.E),(,S E.,E.T+E,S.E,E.T,E T.,T.int,T.int*T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T(E.),E,T(E).,),E T+.E,+,e,e,E T+E.,E,T int.,int,NFA for Viable Prefixes in Detail(12),T.(E),T(.E),(,S E.,E.T+E,S.E,E.T,E T.,T.int,T.int*T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T(E.),E,T(E).,),E T+.E,+,e,e,E T+E.,E,T int.,int,T int.*T,int,T int*.T,*,NFA for Viable Prefixes in Detail(13),T.(E),T(.E),(,S E.,E.T+E,S.E,E.T,E T.,T.int,T.int*T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T(E.),E,T(E).,),E T+.E,+,e,e,E T+E.,E,T int.,int,T int.*T,int,T int*.T,*,根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种：移进项目，形如 A a待约项目，形如 A B归约项目，形如 A 接受项目，形如 S S,Translation to the DFA,S.EE.TE.T+ET.(E)T.int*TT.int,S E.,E T.E T.+E,T int.*TT int.,T(.E)E.TE.T+ET.(E)T.int*TT.int,E T+E.,E T+.EE.TE.T+ET.(E)T.int*TT.int,T int*.TT.(E)T.int*TT.int,T int*T.,T(E.),T(E).,E,T,(,int,int,*,),E,E,T,int,(,(,int,T,+,(,T,项目集,构成识别一个文法活前缀的DFA项目集（状态）的全体称为这个文法的LR(0)项目集规范族NFA确定化为DFA的工作量较大，我们考虑直接构造出项目集作为DFA的状态，就可直接构造DFA通过闭包函数(CLOSURE)来求DFA一个状态的项目集,如果I是文法G的一个项目集，定义和构造I的闭包CLOSURE(I)如下：a)I的项目都在CLOSURE(I)中b)若A B属于CLOSURE(I)，则每一形如B 的项目也属于CLOSURE(I)c)重复b)直到CLOSURE(I)不再扩大定义转换函数如下：GOTO（I，X）=CLOSURE（J）其中：I为包含某一项目集的状态，X为一文法符号 J=任何形如AX 的项目|A X 属于I,圆点不在产生式右部最左边的项目称为核，唯一的例外是S S。因此用GOTO（I，X）转换函数得到的J为转向后状态所含项目集的核使用闭包函数（CLOSURE）和转向函数(GOTO(I,X)构造文法G的LR(0)的项目集规范族，步骤如下：a)置项目S S为初态集的核，然后对核求闭包CLOSURE（S S）得到初态的项目集b)对初态集或其它所构造的项目集应用转换函数GOTO(I，X)=CLOSURE(J)求出新状态J的项目集c)重复b)直到不出现新的项目集为止,S.EE.TE.T+ET.(E)T.int*TT.int,S E.,E T.E T.+E,T int.*TT int.,T(.E)E.TE.T+ET.(E)T.int*TT.int,E T+E.,E T+.EE.TE.T+ET.(E)T.int*TT.int,T int*.TT.(E)T.int*TT.int,T int*T.,T(E.),T(E).,E,T,(,int,int,*,),E,E,T,int,(,(,int,T,+,(,T,总结：构造识别文法活前缀DFA的三种方法,一、根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造NFA再确定化为DFA二、求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA三、使用闭包函数（CLOSURE）和转向函数(GOTO(I,X)构造文法G的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA,LR（0）项目集规范族的项目类型分为如下四种：1）移进项目 A a2）待约项目 A B3）归约项目 A 4）接受项目 S S 一个项目集可能包含多种项目a)移进和归约项目同时存在。移进-归约冲突b)归约和归约项目同时存在。归约-归约冲突LR(0)文法：若其LR(0)项目集规范族不存在移进-归约，或归约-归约冲突，称为LR(0)文法。,LR(0)分析表的构造,LR(0)分析表相当于识别活前缀的有限自动机DAF的状态转换矩阵LR(0)分析表的构造算法书上p130,倒数4行，A 改为 A aLR(0)分析器的工作过程,令包含S S 的项目集Ik的下标k为分析器的初态LR(0)分析表的ACTION和GOTO表的构造步骤如下：a)若项目A a属于Ik，且转换函数GO(Ik,a)=Ij，当a为终结符时，则置ACTIONk,a为Sjb)若项目A 属于Ik，则对a为任何终结符或#，置ACTIONk,a=rj，j为产生式在文法G中的编号c)若GO(Ik,A)=Ij，则置GOTOk,A=j，其中A为非终结符，j为某一状态号d)若项目SS 属于Ik，则置ACTIONk,#=acce)其它填上“报错标志”,S.EE.TE.T+ET.(E)T.int*TT.int,S E.,E T.E T.+E,T int.*TT int.,T(.E)E.TE.T+ET.(E)T.int*TT.int,E T+E.,E T+.EE.TE.T+ET.(E)T.int*TT.int,T int*.TT.(E)T.int*TT.int,T int*T.,T(E.),T(E).,E,T,(,int,int,*,),E,E,T,int,(,(,int,T,+,(,1,2,3,4,5,6,7,8,9,10,11,SLR(1)分析,大多数适用的程序设计语言的文法不能满足LR(0)文法的条件，即其规范族中会有含有冲突的项目集（状态）如果解决这种冲突？直觉：对于有冲突的状态，向前查看一个符号，以确定采用的动作,文法G：(0)S S(1)S rD(2)D D,i(3)D i,I0:S SS rD,I2:S rDD D,iD i,I3:S rD D D,i,I4:D i,I5:D D,i,I1:S S,I6:D D,i,S,r,i,D,i,LR(0)分析表,I3:S rD D D,i,向前查看一个符号，看其是否是S的后跟符号（FOLLOW(S)）,若否则移进，是则归约。,SLR(1)分析表,一个LR(0)规范族中含有如下的项目集（状态）II=X b,A,B 若有：FOLLOW(A)FOLLOW(B)=FOLLOW(A)b=FOLLOW(B)b=状态I面临某输入符号a1)若a=b，则移进2)若aFOLLOW(A),则用产生式 A 进行归约3)若aFOLLOW(B),则用产生式 B 进行归约4)此外，报错若一个文法的LR(0)分析表中所含有的动作冲突都能用上述方法解决，则称这个文法是SLR(1)文法,“改进的”SLR(1)分析：对所有非终结符都求出其FOLLOW集合，这样只有归约项目仅对面临输入符号包含在该归约项目左部非终结符的FOLLOW集合中，才采取用该产生式归约的动作。改进的SLR(1)分析表的ACTION表和GOTO表的构造步骤：a)若项目A a属于Ik，且转换函数GO(Ik,a)=Ij，当a为终结符时，则置ACTIONk,a为Sjb)若项目A 属于Ik，则对a为任何终结符或#，且满足aFOLLOW(A)时，置ACTIONk,a=rj，j为产生式在文法G中的编号c)若GO(Ik,A)=Ij，则置GOTOk,A=j，其中A为非终结符，j为某一状态号d)若项目SS 属于Ik，则置ACTIONk,#=acce)其它填上“报错标志”,仍有许多文法构造的LR(0)项目集规范族存在的动作冲突不能用SLR(1)方法解决,LR(1)分析,若项目集AB属于I时，则B也属于I把FIRST()作为用产生式归约的搜索符（称为向前搜索符），作为用产生式B归约时查看的符号集合（用以代替SLR(1)分析中的FOLLOW集），并把此搜索符号的集合也放在相应项目的后面，这种处理方法即为LR(1)方法,LR(1)项目集族的构造：针对初始项目SS,#求闭包后再用转换函数逐步求出整个文法的LR(1)项目集族。1）构造LR（1）项目集的闭包函数a)I的项目都在CLOSURE(I)中b)若A B，a属于CLOSURE(I)，B 是文法的产生式，V*，bFIRST(a),则B,b也属于CLOSURE(I)c)重复b)直到CLOSURE(I)不再扩大2)转换函数的构造GOTO（I，X）=CLOSURE（J）其中：I为LR(1)的项目集，X为一文法符号 J=任何形如AX,a的项目|A X,a属于I,I0:S S,#S aAd,#S bAc,#S aec,#S bed,#,文法G：(0)S S(1)S aAd(2)S bAc(3)S aec(4)S bed(5)A e,I1:S S,#,I2:S a Ad,#S a ec,#A e,d,I3:S b Ac,#S b ed,#A e,c,I4:S aA d,#,I5:S ae c,#A e,d,I6:S bA c,#,I7:S be d,#A e,c,I8:S aAd,#,I9:S ae c,#,I10:S bAc,#,I11:S bed,#,查看I5，I7中的冲突，体会LR(1)如何解决,LR(1)分析表的构造,1)若项目A a,b属于Ik，且转换函数GO(Ik,a)=Ij，当a为终结符时，则置ACTIONk,a为Sj2)若项目A,a属于Ik，则对a为任何终结符或#，置ACTIONk,a=rj，j为产生式在文法G中的编号3)若GO(Ik,A)=Ij，则置GOTOk,A=j，其中A为非终结符，j为某一状态号4)若项目SS,#属于Ik，则置ACTIONk,#=acc5)其它填上“报错标志”,LR(1)项目集的构造对某些同心集的分裂可能使状态数目剧烈的增长,文法G：(0)S S(1)B aB(2)S BB(3)B b,I0:S S,#S BB,#B aB,a/bB b,a/b,I1:S S,#,I2:S B B,#B a B,#B b,#,I5:S B B,#,I6:S a B,#B aB,#B b,#,I9:B a B,#,I4:B b,a/b,I3:B a B,a/bB aB,a/bB b,a/b,I8:B a B,a/b,I7:B b,#,S,B,b,b,B,b,b,a,a,a,a,B,B,LR(1)项目集和转换函数,分析可发现I3和I6，I4和I7，I8和I9分别为同心集,I3:B a B,a/bB aB,a/bB b,a/b,I6:S a B,#B aB,#B b,#,I4:B b,a/b,I7:B b,#,I8:B a B,a/b,I9:B a B,#,I3,6:S a B,a/b/#B aB,a/b/#B b,a/b/#,I4,7:B b,a/b/#,I8,9:B a B,a/b/#,合并为,合并为,合并为,LALR(1)分析,对LR(1)项目集规范族合并同心集，若合并同心集后不产生新的冲突，则为LALR(1)项目集。,合并同心集的几点说明,同心集合并后心仍相同，只是超前搜索符集合为各同心集超前搜索符的和集合并同心集后转换函数自动合并LR(1)文法合并同心集后也只可能出现归约-归约冲突，而没有移进-归约冲突合并同心集后可能会推迟发现错误的时间，但错误出现的位置仍是准确的,合并同心集后,二义性文法在LR分析中的应用,对于某些二义文法，可以人为地给出优先性和结合性的规定，从而可以构造出比相应非二义性文法更优越的LR分析器,LR(0),SLR(1),LR(1),LR(k),LALR(1),LR(0)SLR(1):生成的LR(0)项目集如有冲突，则根据非终结符的FOLLOW集决定LR(1)、LR(k):项由 心与向前搜索符组成，搜索符长度为1或kLALR(1):对LR(1)项目集规范族合并同心集,作业,p152,第6,11,18题,