第7章LR分析法(lly)3讲述

1、第七章第七章 LR(left-right)分析法分析法考查重点：考查重点：vLR(0)LR(0)、SLR(1)SLR(1)、LR(1)LR(1)，LALR(1)LALR(1)项目集规范族的项目集规范族的构造构造，识别识别活前缀活前缀的的DFADFA的构造的构造，分析表的构造分析表的构造，及及输入串的分析输入串的分析。1.1.LR(0)LR(0)、SLR(1)SLR(1)、LR(1)LR(1)、LALR(1)LALR(1)文法及其关系和文法及其关系和区别区别文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串

2、动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进A 3） #ab bcde# 归约归约(Ab) 4） #aA bcde# 移进移进A 5） #aAb cde# 归约归约(AAb) 6） #aA cde# 移进移进 7） #aAc de# 移进移进B 8） # aAcd e# 归约归约(Bd) 9） #aAcB e# 移进移进11） #S # 接受接受S10） #aAcBe # 归约归约(SaAcBe)分析符号串abbcde是否GS的句子对输入串abbcde#的移进-规约分析过程SaAcBe aAcde aAbcde abbcdev在步骤在步骤3中，用中，用Ab归

3、约归约v在步骤在步骤5中，用中，用AAb归约归约v问题：何时移进？何时归约？用哪个产生式问题：何时移进？何时归约？用哪个产生式归约（如何找当前句柄归约）？归约（如何找当前句柄归约）？ 3） #ab bcde# 归约归约(Ab) 5） #aAb cde# 归约归约(AAb) 4） #aA bcde# 移进移进 6） #aA cde# 移进移进分析：已分析过的部分在栈中的分析：已分析过的部分在栈中的前缀前缀不同，而且移进和归不同，而且移进和归约后栈中的状态会发生变化约后栈中的状态会发生变化我们引入一个新的我们引入一个新的状态栈状态栈来表示符号栈中的符号目前状态来表示符号栈中的符号目前状态用用LRL

4、R分析表分析表来表示不同状态下对于各输入符号应采取的动来表示不同状态下对于各输入符号应采取的动作作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 S911） #S # 接受接受 01 acc对输入串abbcde#的LR分析过程 3） #ab bcde# 归约归约(Ab

5、) 024 r2 3 5） #aAb cde# 归约归约(AAb) 0236 r3 3 8） # aAcd e# 归约归约(Bd) 02358 r4 710） #aAcBe # 归约归约(SaAcBe) 023579 r1 1状态栈状态栈ACTIONGOTO文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dSi:移进，并将状态移进，并将状态i进栈进栈ri:用第用第i个产生式归约，同时状个产生式归约，同时状态栈与符号栈退出相应个符号，态栈与符号栈退出相应个符号，根据根据GOTO表将相应状态入栈表将相应状态入栈S8S9问题：v对于一个文法，状态集是如何确定的？vLR分

6、析表是如何得到的？答案答案：需要构造识别：需要构造识别可归前缀可归前缀的的有穷自动机有穷自动机可归前缀与活前缀文法文法GS：(1) S aAcBe1(2) A b2(3) A Ab3(4) B d4S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1每次归约句型的每次归约句型的前部分前部分依次为：依次为：ab2 /?aAb3aAcd4aAcBe1规范句型规范句型的这种前部分符号串称为的这种前部分符号串称为可归前缀可归前缀我们把形成可归前缀之前包括可归前缀在内我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为的所有规范句型的前缀都称为活前缀活前缀 ,a,ab

7、,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBe活前缀活前缀v定义：定义：S A 是文法是文法G中的一个中的一个规范推导规范推导，如果，如果符号串符号串是是的前缀，则称的前缀，则称是是G的一个的一个活前缀活前缀。（在在当前句型当前句型中，中，不不包含包含句柄句柄右边右边的前缀的前缀）R*RvLR分析需要构造识别分析需要构造识别可归前缀可归前缀的的有穷自动机有穷自动机把文法的把文法的终结符和非终结符终结符和非终结符都看成有穷自动机输入都看成有穷自动机输入符号，每次把一个符号进栈看成已识别过了该符符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转

8、换，当识别到可归前缀（栈号，同时状态进行转换，当识别到可归前缀（栈中形成句柄）时，认为达到了识别句柄的终态。中形成句柄）时，认为达到了识别句柄的终态。注注：在在符号栈符号栈中，中，始终存放当前句型的活前缀始终存放当前句型的活前缀8014235769SabAbcBed*S8S9句子句子abbcde的的可可归前缀归前缀：ab2aAb3aAcd4aAcBe1文法文法GS：(1) S aAcBe1(2) A b2(3) A Ab3(4) B d41句子识别态i句柄识别态*如何构造识别如何构造识别可归可归前缀的有限自动机前缀的有限自动机v已经有了可归前缀如何构造有限自动机?v活前缀及其可归前缀的一般计算

9、方法文法文法GS：S S0S aAcBe1A b2A Ab3B d4句子句子abbcdeabbcde的可归前缀（的可归前缀（正规式正规式）如下：）如下：S0S0ab2ab2aAb3aAb3aAcd4aAcd4aAcBe1aAcBe1构造识别其活前缀及可归前缀的有限自动机如下构造识别其活前缀及可归前缀的有限自动机如下：104387131210182591461715161110SabaAbaAcdaAcBe*1句子识别态i句柄识别态104387131210182591461715161110SabaAbaAcdaAcBe*X加上开始状态X确定化 X13246859SabAbcBed7*识别活前缀

10、的确定的有限自动机识别活前缀的确定的有限自动机活前缀及其可归前缀的一般计算方法活前缀及其可归前缀的一般计算方法定义：文法定义：文法G，A VN,LC(A)= | S A , V*, VT *规范推导规范推导中在中在非终结符非终结符A左边所有可能出左边所有可能出现的符号串的集合现的符号串的集合(不包括句柄的活前缀不包括句柄的活前缀? )推论：若文法推论：若文法G中有产生式中有产生式B A ，则有则有LC(A) LC(B) R*文法文法GS：S S0S aAcBe1A b2A Ab3B d4由前面定义与推论知：LC(S) = LC(S) = LC(S) * LC(A) = LC(S) *a LC(

11、A) * LC(B) = LC(S) *aAc化简为：S = S = SA = Sa+A B = SaAc求解方程组可得：S = S = A = a+A B = aAcA = a|AA = a *=a这样我们求出了每个这样我们求出了每个非终结符非终结符在规范推导中用该非终结符在规范推导中用该非终结符的右部替换该非终结符之前，它的左部可能出现的的右部替换该非终结符之前，它的左部可能出现的所有前所有前缀缀，也就是在规范归约过程中用句柄归约成该非终结符之，也就是在规范归约过程中用句柄归约成该非终结符之前前不包括句柄的活前缀不包括句柄的活前缀。推论推论：若文法若文法G中有产生中有产生式式B A ，则有

12、则有LC(A) LC(B) 不包括句柄的活前缀不包括句柄的活前缀 + 句柄句柄 = ？ 可归前缀？可归前缀？ 令令 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、根据可

13、归前缀，构造识别文法活前缀的不确定有限自动机、根据可归前缀，构造识别文法活前缀的不确定有限自动机3、确定化，从而构造出识别文法活前缀的确定的有限自动机、确定化，从而构造出识别文法活前缀的确定的有限自动机参见课本参见课本P124的例子的例子LR分析器的构造分析器的构造 1、构造识别文法活前缀的确定有限自动机、构造识别文法活前缀的确定有限自动机根据文法算出其可归前缀根据文法算出其可归前缀根据可归前缀，构造识别文法活前缀的不确定有限自动机根据可归前缀，构造识别文法活前缀的不确定有限自动机确定化，从而构造出识别文法活前缀的确定的有限自动机确定化，从而构造出识别文法活前缀的确定的有限自动机2、根据该自动

14、机构造相应的分析表、根据该自动机构造相应的分析表(ACTION表、表、GOTO表表)输出输出状态与符号栈状态与符号栈总控程序总控程序Action/Goto表表输入符号串输入符号串这种方法构造识别可归前缀的有限自动机从理论的角度讲是比较严格的，但实现起来却很复杂!是否存在一种比较实用的方法？KISS准则！准则！项目（项目（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 项目圆点的左部表示分析过程的某个时刻用该产生式

15、归约时句柄已识别的部分句柄已识别的部分，圆点右部表示待待识别的部分识别的部分。空产生式A的项目只有一个：A由文法的产生式直接构造识别活由文法的产生式直接构造识别活前缀和可归前缀的有限自动机前缀和可归前缀的有限自动机l有限自动机NFA的每一个状态由一个项目构成构造识别活前缀的构造识别活前缀的NFA：1 1、把文法的所有产生式的项目都引出，把文法的所有产生式的项目都引出，每个项目都每个项目都为为NFANFA的一个状态的一个状态2 2、确定、确定初态初态、句柄识别态句柄识别态、句子识别态句子识别态3 3、确定、确定状态之间的转换关系状态之间的转换关系若项目若项目i i为为 X X1X2.Xi-1 X

16、 X1X2.Xi-1 XiXi.Xn.Xn项目项目j j为为 X X1X2.Xi-1 X X1X2.Xi-1 XiXi Xi+1.Xn Xi+1.Xn则从状态则从状态i i到状态到状态j j连一条标记为连一条标记为XiXi的箭弧的箭弧若若i i为为X X A A ，k k为为A A ，则从状态则从状态i i画标画标记为记为 的箭弧到状态的箭弧到状态k 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

17、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 ExampleT . (E)T (.E)T (E.)T (E).(E)S E.E . T+EE T.+EE T+.EE T+E.S . EE . TE T.T int.T .int

18、T .int * TT int * T.T int *.TT int.* TETE+intint*TTNFA for Viable Prefixes in Detail (1)S . ENFA for Viable Prefixes in Detail (2)S . ES E.EE . TE . T+ENFA for Viable Prefixes in Detail (3)S E.E . T+ES . EE . TT .int * TET . (E)T .intE T.TNFA for Viable Prefixes in Detail (4)T . (E)S E.E . T+ES . EE

19、 . TE T.T .intT .int * TEE T.+ETTNFA for Viable Prefixes in Detail (5)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETNFA for Viable Prefixes in Detail (6)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ENFA for Viable Prefixes in Detail (7)T . (E)T (.E)(S E.E .

20、 T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)NFA for Viable Prefixes in Detail (8)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+NFA for Viable Prefixes in Detail (9)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E

21、+E T+E.ENFA for Viable Prefixes in Detail (10)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+E T+E.ET NFA for Viable Prefixes in Detail (11)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+E T+E.ET T int.* TintNF

22、A for Viable Prefixes in Detail (12)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+E T+E.ET T int.* TintT int *.T*NFA for Viable Prefixes in Detail (13)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+E T+E.ET T

23、int.* TintT int *.T*T int * T.T根据圆点所在的位置圆点所在的位置和圆点后是终结符还是非终圆点后是终结符还是非终结符结符把项目分为以下几种：移进移进项目，形如 A a 待约待约项目，形如 A B 归约归约项目，形如 A （句柄识别态）（句柄识别态）接受接受项目，形如 S S （句子识别态句子识别态）初态初态项目，形如 S S （初态）初态）Translation to the DFAS . EE . TE .T + ET .(E)T .int * TT .intS E .E T.E T. + ET int. * TT int.T (. E)E .TE .T + ET

24、 .(E)T .int * TT .intE T + E.E T + . EE .TE .T + ET .(E)T .int * TT .intT int * .TT .(E)T .int * TT .intT int * T.T (E.)T (E).ET(intint*)EETint (intT+(T项目集项目集NFANFA确定化为确定化为DFADFA的工作量较大，我们考虑直接构的工作量较大，我们考虑直接构造出项目集作为造出项目集作为DFADFA的状态，就可直接构造的状态，就可直接构造DFADFA构成识别一个文法活前缀的构成识别一个文法活前缀的DFA项目集（状态）项目集（状态）的全体称为这个

25、文法的的全体称为这个文法的LR(0)项目集规范族项目集规范族.如果I是文法G的一个项目集，定义和构造I的闭包CLOSURE(I)如下：a)I的项目都在CLOSURE(I)中b)若A B 属于CLOSURE(I)，则每一形如B 的项目也属于CLOSURE(I)c)重复b)直到CLOSURE(I)不再扩大闭包函数闭包函数(CLOSURE)来求来求DFA一个状态的项目集一个状态的项目集例例文法文法GS：(1) S aAcBe(2) A b(3) A Bb(4) B d求求若若I的项目集的项目集=S .aAcBe，则，则CLOSURE(I)？若若I的项目集的项目集=S a.AcBe呢？呢？v定义转换函

26、数如下：定义转换函数如下：GOTO（I，X）= CLOSURE（J）其中：其中：I为包含某一项目集的状态，为包含某一项目集的状态，X为一文法符号为一文法符号 J=任何形如任何形如A X 的项目的项目| A X 属于属于Iv圆点不在产生式右部圆点不在产生式右部最左边最左边的项目称为的项目称为核核，唯一，唯一的例外是的例外是S S。思考思考：GOTO（I，X）转换函数得到的转换函数得到的J是否一定为是否一定为核核？例例文法文法GS：(1) S aAcBe(2) A b(3) A Bb(4) B d求求若若I的项目集的项目集=S .aAcBe，则，则GOTO（I，a）=？若若I的项目集的项目集=S

27、a.AcBe，GOTO（I，A）呢？呢？使用闭包函数（使用闭包函数（CLOSURECLOSURE）和转向函数和转向函数( (GOTO(I,X)GOTO(I,X)构造文法构造文法GG的的LR(0)LR(0)的项目集规范族的项目集规范族，步骤如下，步骤如下：c)重复重复b)直到不出现新的项目集为止直到不出现新的项目集为止b)对初态集或其它所构造的项目集应用转换函数对初态集或其它所构造的项目集应用转换函数GOTO(I，X)= CLOSURE(J)求出求出新状态新状态J的项目集的项目集a)置项目置项目S S为初态集的核，然后对核求闭包为初态集的核，然后对核求闭包CLOSURE（S S）得到得到初态的项

28、目集初态的项目集举例举例S . EE . TE .T + ET .(E)T .int * TT .intS E .E T.E T. + ET int. * TT int.T (. E)E .TE .T + ET .(E)T .int * TT .intE T + E.E T + . EE .TE .T + ET .(E)T .int * TT .intT int * .TT .(E)T .int * TT .intT int * T.T (E.)T (E).ET(intint*)EETint (intT+(T总结：构造识别文法活前缀DFA的三种方法一、根据形式定义求出活前缀的正规表达式，一、根

29、据形式定义求出活前缀的正规表达式，然后由此正规表达式构造然后由此正规表达式构造NFANFA再确定化为再确定化为DFADFA二、求出文法的所有项目，按一定规则构造识二、求出文法的所有项目，按一定规则构造识别活前缀的别活前缀的NFANFA再确定化为再确定化为DFADFA三、使用闭包函数（三、使用闭包函数（CLOSURECLOSURE）和转向函数和转向函数( (GOTO(I,X)GOTO(I,X)构造文法构造文法G G的的LR(0)LR(0)的的项目集规项目集规范族，再由转换函数建立状态之间的连接关范族，再由转换函数建立状态之间的连接关系得到识别活前缀的系得到识别活前缀的DFADFALRLR（0 0

30、）项目集规范族的项目类型分为如下四种：项目集规范族的项目类型分为如下四种：1 1）移进项目）移进项目 A a 2 2）待约项目待约项目 A B 3 3）归约项目归约项目 A 4 4）接受项目接受项目 S S 一个项目集可能包含多种项目一个项目集可能包含多种项目a) 移进和归约项目同时存在。移进和归约项目同时存在。移进移进-归约冲突归约冲突b) 归约和归约项目同时存在。归约和归约项目同时存在。归约归约-归约冲突归约冲突LR(0)文法：LR(0)文法：若其文法：若其LR(0)项目集规范族不存在项目集规范族不存在移进移进-归约，或归约归约，或归约-归约冲突，称为归约冲突，称为LR(0)文法文法。LR

31、(0)分析表的构造分析表的构造vLR(0)分析表相当于识别活前缀的有限自动机DFA的状态转换矩阵vLR(0)分析表的构造算法(书上p131)vLR(0)分析器的工作过程(书上p132)令包含令包含S S 的项目集的项目集Ik的下标的下标k为分析器的初态为分析器的初态LR(0)分析表的分析表的ACTION和和GOTO表的构造步骤：表的构造步骤：e) 其它填上其它填上“报错标志报错标志”d) 若项目若项目SS 属于属于Ik ，则置则置ACTIONk,# = accc) 若若GOTO (Ik,A)= Ij ，则置则置GOTOk,A=j，其中其中A为非为非终结符，终结符，j为某一状态号为某一状态号b)

32、 若项目若项目A 属于属于Ik ，则对则对a为为任何终结符或任何终结符或#，置置ACTIONk,a = rj ，j为产生式在文法为产生式在文法G中的编号中的编号a) 若项目若项目A a 属于属于Ik，且转换函数且转换函数GOTO(Ik,a)= Ij ，当当 a为终结符时，则置为终结符时，则置ACTIONk,a为为SjS . EE . TE .T + ET .(E)T .int * TT .intS E .E T.E T. + ET int. * TT int.T (. E)E .TE .T + ET .(E)T .int * TT .intE T + E.E T + . EE .TE .T +

33、 ET .(E)T .int * TT .intT int * .TT .(E)T .int * TT .intT int * T.T (E.)T (E).ET(intint*)EETint(intT+(1234567891011SLR(1)分析分析v大多数适用的程序设计语言的文法不能满足LR(0)文法的条件，即其规范族中会有含有冲突的项目集（状态）v如果解决这种冲突？v直觉：对于有冲突的状态，向前查看一个符号，以确定采用的动作文法文法G：(0) S S(1) S rD (2) D D,i(3) D iLR(0)LR(0)分析表分析表思考思考: S,存在此句型？存在此句型？思考思考:1 1）为

34、什么引入）为什么引入FOLLOWFOLLOW2 2）I I3 3中冲突如何解决的？中冲突如何解决的？3 3）若有）若有S S S,rS,r 如何如何 ? ?一个LR(0)规范族中含有如下的项目集（状态）IkIk = X b , A , B 若一个文法的LR(0)分析表中所含有的动作冲突都能用上述方法解决，则称这个文法是SLR(1)文法文法,所构造的分析表为SLR(1)分析表分析表，使用SLR(1)分析表的分析器为SLR(1)分析器分析器。状态状态k k面临某输入符号面临某输入符号x x1) 1) 若若x x=b=b，则移进则移进2) 2) 若若x x FOLLOW(A), FOLLOW(A),

35、 则用产生式则用产生式 A A 进行归约进行归约3 3) ) 若若x x FOLLOW(B), FOLLOW(B), 则用产生式则用产生式 B B 进行归约进行归约4) 4) 此外，报错此外，报错若有：FOLLOW(A) FOLLOW(B) = FOLLOW(A) b = FOLLOW(B) b = “改进的改进的”SLR(1)分析：分析：对所有所有非终结符都求出其FOLLOW集合，这样只有归约项目归约项目仅对面临输入符号包含在该归约项目左部非终结符的FOLLOW集合中，才采取用该产生式归约的动作。FOLLOW(SFOLLOW(S）= # = # SLR(1)SLR(1)分析表分析表文法文法G

36、：(0) S S(1) S rD (2) D D,i(3) D iFOLLOW(DFOLLOW(D）= #= #， LR(0)LR(0)分析表分析表1) 若项目A a 属于Ik，且转换函数GOTO(Ik,a)= Ij ，当a为终结符时，则置ACTIONk,a为Sj2) 若项目A 属于Ik ，则对a FOLLOW(A)时，置ACTIONk,a = rj ，j为产生式在文法G中的编号3) 若GOTO (Ik,A)= Ij ，则置GOTOk,A=j，其中A为非终结符，j为某一状态号4) 若项目SS 属于Ik ，则置ACTIONk,# = acc5) 其它填上“报错标志”改进的改进的SLR(1)分析表

37、的分析表的ACTION表和表和GOTO表的构造步骤：表的构造步骤：v仍有许多文法构造的仍有许多文法构造的LR(0)LR(0)项目集规范族存在项目集规范族存在的动作冲突不能用的动作冲突不能用SLR(1)SLR(1)方法解决方法解决LR(1)分析分析v若项目集若项目集 A A B B 属于属于I I时，则时，则 B B 也属于也属于I Iv把把FIRST(FIRST( ) )作为用产生式归约的搜索符（称为作为用产生式归约的搜索符（称为向前搜向前搜索符索符），作为用产生式），作为用产生式B B 归约时查看的符号集合（用归约时查看的符号集合（用以代替以代替SLR(1)SLR(1)分析中的分析中的FOL

38、LOWFOLLOW（B B）集），并把此集），并把此搜索搜索符号的集合也放在相应项目的后面符号的集合也放在相应项目的后面，这种处理方法即为，这种处理方法即为LR(1)LR(1)方法方法说明说明：为什么引入为什么引入FIRST(FIRST( ) )？FIRST(FIRST( ) )与与FOLLOWFOLLOW（B B）的关系）的关系LR(1)LR(1)项目项目与与LR(0)LR(0)项目的不同？项目的不同？ 心，展望字符集心，展望字符集? ? 思考思考：1 1） S S S S， ? ? 2 2）若）若 A A B B ，a a ，则，则 A A B B ，？ 3 3）若）若 A A BbBb，

39、a a ，则，则 B B ，？ 4 4）若）若 A A B B，a a ，则，则 B B ，？ 5 5）若）若 A A B B ，a a ，则，则 B B ，？ LR(1)项目集族的构造：项目集族的构造：(1)针对初始项目针对初始项目SS,#求闭包求闭包(2)再用转换函数逐步求出整个文法的再用转换函数逐步求出整个文法的LR(1)项目集族。项目集族。构造构造LR（1）项目集的项目集的闭包函数闭包函数a)Ia)I的项目都在的项目都在CLOSURE(I)CLOSURE(I)中中b)b)若若AA B B ，aa属于属于CLOSURE(I)CLOSURE(I)， B B 是文法的产生是文法的产生式，式，

40、 V V* *，b b FIRST(FIRST( a),a),则则BB ,b,b也属于也属于CLOSURE(I)CLOSURE(I)c)c)重复重复b)b)直到直到CLOSURE(I)CLOSURE(I)不再扩大不再扩大转换函数转换函数的构造的构造 GOTOGOTO（I I，X X）= CLOSURE= CLOSURE（J J） 其中：其中：I I为为LR(1)LR(1)的项目集的项目集，X X为一文法符号为一文法符号 J=J=任何形如任何形如AA X X , ,a a 的项目的项目| | AA X X ,a,a 属于属于II文法文法G：(0) S S (1) S aAd (2) S bAc

41、(3) S aec (4) S bed (5) A eI0=S S, #,S aAd, #,S bAc, #,S aec, #,S bed, #I1= GOTO(I I0 0,S) =S S , #I2 = GOTO(I I0,a) =S a Ad, #,S a ec, #,A e, dI3 = GOTO(I I0,b)=S b Ac, #,S b ed, #,A e, cI4 = GOTO(I I2,A)= S aA d, #I5 = GOTO(I2,e)= S ae c, #,A e , dI6 = GOTO(I3,A)=S bA c, #I7 = GOTO(I3,A)=S be d, #

42、,A e , cI8 = GOTO(I4,d)=S aAd , #I9 = GOTO(I5,c)=S ae c , #I10 = GOTO(I6,c)= S bAc , #I11 = GOTO(I7,d)=S bed , #查看查看I I5 5 ，I I7 7中的冲突，中的冲突，体会体会LR(1)LR(1)如何解决？如何解决？LR(1)项目集族项目集族=?构造构造LR(0)分析表分析表构造构造SLR(1)分析表分析表构造构造LR(1)分析表分析表LR(1)分析表的构造1) 若项目若项目A a ,b属于属于Ik，且转换函数且转换函数GO(Ik,a)= Ij ，当当a为终结符时，则置为终结符时，则

43、置ACTIONk,a为为Sj2) 若项目若项目A ,a属于属于Ik ，则则置置ACTIONk,a = rj ，j为产生式在文法为产生式在文法G中的编号中的编号3) 若若GO(Ik,A)= Ij ，则置则置GOTOk,A=j，其中其中A为为非终结符，非终结符，j为某一状态号为某一状态号4) 若项目若项目SS ,#属于属于Ik ，则置则置ACTIONk,# = acc5) 其它填上其它填上“报错标志报错标志”vLR(1)LR(1)项目集的构造对某些项目集的构造对某些同心集的分裂同心集的分裂可能可能使状态数目剧烈的增长使状态数目剧烈的增长文法G：(0) S S(1) B aB (2) S BB(3)

44、 B bI0:S S, #S BB, #B aB, a/bB b, a/bI1:S S , #I2:S B B, #B a B, #B b, #I5:S B B , #I6:B a B, #B aB, #B b, #I9:B a B , #I4:B b , a/bI3:B a B, a/bB aB, a/bB b, a/bI8:B a B , a/bI7:B b , #SBbbBbbaaaaBBLR(1)项目集和转换函数分析可发现I3和I6 ， I4和I7 ， I8和I9分别为同心集I3:B a B, a/bB aB, a/bB b, a/bI6:B a B, #B aB, #B b, #I4:B b , a/bI7:B b , #I8:B a B , a/bI9:B a B , #I3,6:B 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)分析分析v对对LR(1)项目集规范族合并同心集，若项目集规范族合并同心集，若合并同合并同心集后不产生新的冲突心集后不产生新的冲突，