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

《编译原理教案-LR分析.pptx》由会员分享，可在线阅读，更多相关《编译原理教案-LR分析.pptx（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、LR分析自下而上语法分析算法之 复习：移进-归约分析文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 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

2、# 归约归约(SaAcBe)分析符号串abbcde是否GS的句子对输入串abbcde#的移进-规约分析过程SaAcBe aAcde aAbcde abbcde 在步骤在步骤3中，用中，用Ab归约归约 在步骤在步骤5中，用中，用AAb归约归约 问题：何时移进？何时归约？用哪个产问题：何时移进？何时归约？用哪个产生式归约？生式归约？ 3） #ab bcde# 归约归约(Ab) 5） #aAb cde# 归约归约(AAb) 4） #aA bcde# 移进移进 6） #aA cde# 移进移进分析：已分析过的部分在栈中的分析：已分析过的部分在栈中的前缀前缀不同，而且移进和归不同，而且移进和归约后栈中的

3、状态会发生变化约后栈中的状态会发生变化我们引入一个新的我们引入一个新的状态栈状态栈来表示符号栈中的符号目前状态来表示符号栈中的符号目前状态用用LRLR分析表分析表来表示不同状态下对于各输入符号应采取的动来表示不同状态下对于各输入符号应采取的动作作步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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）

4、#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 710） #aAcBe # 归约归约(SaAcBe) 023579 r1 1ACTIO NGO TOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r2576r3r3r3r3r3r378r4r4r4r4r4r49r1r1r1r1r1r1状态栈状态栈ACTIONGOTO文法文法GS：(1) S aAcBe(2) A

5、 b(3) A Ab(4) B dSi:移进，并将状态移进，并将状态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 S911） #S #

6、 接受接受 01 acc对输入串abbcde#的LR分析过程 3） #ab bcde# 归约归约(Ab) 024 r2 3 5） #aAb cde# 归约归约(AAb) 0236 r3 3 8） # aAcd e# 归约归约(Bd) 02358 r4 710） #aAcBe # 归约归约(SaAcBe) 023579 r1 1ACTIO NGO TOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r2576r3r3r3r3r3r378r4r4r4r4r4r49r1r1r1r1r1r1状态栈状态栈ACTIONGOTO文法文法GS：(1) S aAcBe(2) A b(3

7、) A Ab(4) B dSi:移进，并将状态移进，并将状态i进栈进栈ri:用第用第i个产生式归约，同时状个产生式归约，同时状态栈与符号栈退出相应个符号，态栈与符号栈退出相应个符号，根据根据GOTO表将相应状态入栈表将相应状态入栈问题： 对于一个文法，状态集是如何确定的？ LR分析表是如何得到的？可归前缀与活前缀文法文法GS：(1) S aAcBe1(2) A b2(3) A Ab3(4) B d4S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1每次归约句型的每次归约句型的前部分前部分依次为：依次为：ab2aAb3aAcd4aAcBe1规范句型的这种前部分符号串称为规

8、范句型的这种前部分符号串称为可归前缀可归前缀我们把形成可归前缀之前包括可归前缀在内我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为的所有规范句型的前缀都称为活前缀活前缀 ,a,ab ,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBe活前缀（Viable Prefixes） viable:adj capable of growing and developing capable of being put into practice : workable 定义： S A 是文法G中的一个规范推导，如果符号串是的前缀，则称是G的一个活前缀。R*

9、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 # 接受接受

10、 01 acc对输入串abbcde#的LR分析过程 3） #ab bcde# 归约归约(Ab) 024 r2 3 5） #aAb cde# 归约归约(AAb) 0236 r3 3 8） # aAcd e# 归约归约(Bd) 02358 r4 710） #aAcBe # 归约归约(SaAcBe) 023579 r1 1状态栈状态栈ACTIONGOTO014235769SabAbcBed8*步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2对输入串abbcde#的LR分析过程状态栈状态栈ACTIONGOTO014235769SabAbcBed8*步骤

11、步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 对输入串abbcde#的LR分析过程状态栈状态栈ACTIONGOTO014235769SabAbcBed8*步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 对输入串abbcde#的LR分析过程 3） #ab bcde# 归约归约(Ab) 024 r2 3状态栈状态栈ACTIONGOTO014235769SabAbcBed8*步骤步骤 符号栈符号栈 输入符

12、号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 4） #aA bcde# 移进移进 023 S6对输入串abbcde#的LR分析过程 3） #ab bcde# 归约归约(Ab) 024 r2 3状态栈状态栈ACTIONGOTO014235769SabAbcBed8*步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 4） #aA bcde# 移进移进 023 S6对输入串abbcde#的LR分析过程 3） #ab bcde# 归约

13、归约(Ab) 024 r2 3 5） #aAb cde# 归约归约(AAb) 0236 r3 3状态栈状态栈ACTIONGOTO014235769SabAbcBed8*步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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

14、GOTO*014235769SabAbcBed8步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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状态栈状态栈ACTIONGOTO*014235769SabAbcBed8步骤步骤 符号栈符号栈

15、 输入符号串输入符号串动作动作 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状态栈状态栈ACTIONGOTO014235769SabAbcBed8*步骤步骤 符号栈符号栈 输

16、入符号串输入符号串动作动作 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状态栈状态栈ACTIONGOTO014235769

17、SabAbcBed8*步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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 71

18、0） #aAcBe # 归约归约(SaAcBe) 023579 r1 1状态栈状态栈ACTIONGOTO014235769SabAbcBed8*步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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# 归约归

19、约(Ab) 024 r2 3 5） #aAb cde# 归约归约(AAb) 0236 r3 3 8） # aAcd e# 归约归约(Bd) 02358 r4 710） #aAcBe # 归约归约(SaAcBe) 023579 r1 1状态栈状态栈ACTIONGOTO014235769SabAbcBed8*如何构造识别活前缀的有限自动机 已经有了活前缀如何构造有限自动机? 活前缀及其可归前缀的一般计算方法文法文法GS：S S0S aAcBe1A b2A Ab3B d4句子句子abbcdeabbcde的可归前缀如下：的可归前缀如下：S0S0ab1ab1aAb3aAb3aAcd4aAcd4aAcBe

20、1aAcBe1构造识别其活前缀及可归前缀的有限自动机如下：构造识别其活前缀及可归前缀的有限自动机如下：104387131210182591461715161110SabaAbaAcdaAcBe*1*句子识别态i句柄识别态104387131210182591461715161110SabaAbaAcdaAcBe*X加上开始状态X确定化 X13246859SabAbcBed7*识别活前缀的确定的有限自动机识别活前缀的确定的有限自动机活前缀及其可归前缀的一般计算方法定义：文法G，AVN,LC(A)= | S A, V*, VT *规范推导中在非终结符A左边所有可能出现的符号串的集合推论：若文法G中有

21、产生式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(A) * LC(B) = LC(S) *aAc化简为：S = S = SA = Sa+A B = SaAc求解方程组可得：S = S = A = a+A B = aAcA = a|AA = a *=a这样我们求出了每个这样我们求出了每个非终结符非终结符在规范推导中用该非终结符在规范推导中用该非终结符的右部替换该非终结符之前，它的左部可能出现的的右部替换该非终结符之前，它的

22、左部可能出现的所有前所有前缀缀，也就是在规范归约过程中用句柄归约成该非终结符之，也就是在规范归约过程中用句柄归约成该非终结符之前前不包括句柄的活前缀不包括句柄的活前缀。不包括句柄的活前缀不包括句柄的活前缀 + 句柄句柄 = ？ 可归前缀？可归前缀？ 令令 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总结：

23、如何构造识别文法活前缀的有限自动机？总结：如何构造识别文法活前缀的有限自动机？ 1、根据文法算出其可归前缀、根据文法算出其可归前缀2、根据可归前缀，构造识别文法活前缀的不确定有限自动机、根据可归前缀，构造识别文法活前缀的不确定有限自动机3、确定化，从而构造出识别文法活前缀的确定的有限自动机、确定化，从而构造出识别文法活前缀的确定的有限自动机参见课本参见课本P124的例子的例子LR分析器的构造分析器的构造 1、构造识别文法活前缀的确定有限自动机、构造识别文法活前缀的确定有限自动机2、根据该自动机构造相应的分析表、根据该自动机构造相应的分析表(ACTION表、表、GOTO表表)总控程序总控程序Ac

24、tion/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 有限自动机的每一个状态由一个项目构成项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分，圆点右部表示待识别的部

25、分。构造识别活前缀的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

26、 + 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 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 .intT .int * TT int * T.T int *.TT int.* TETE+intint*TTNF

27、A 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 . TE T.T .intT .int * TEE T.+ETTNFA for Viable Prefi

28、xes 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 . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (

29、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+E T+E.ENFA for Viable Prefixes in Detail (10)T . (E)

30、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 int.intNFA 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 int.intT int.* TintNFA for Viable Prefixes in Detail (12)T . (E)T (.E)(S E

31、.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+E T+E.ET int.intT 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 int.intT int.* TintT int *.T*T int * T.T根据圆点所在的位置和圆点后是终结符还是非终结

32、符把项目分为以下几种：移进项目，形如 A a 待约项目，形如 A B 归约项目，形如 A 接受项目，形如 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 .(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

33、(intint*)EETint (intT+(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)不再扩大定义转换函数如下：定义转换函数如下：GOTOGOTO（I I，X

34、 X）= CLOSURE= CLOSURE（J J）其中：其中：I I为包含某一项目集的状态，为包含某一项目集的状态，X X为一文法符号为一文法符号 J=J=任何形如任何形如A A X 的项目的项目| A A X 属于属于II圆点不在产生式右部圆点不在产生式右部最左边最左边的项目称为的项目称为核核，唯一的，唯一的例外是例外是S S。因此用因此用GOTOGOTO（I I，X X）转换函数转换函数得得到的到的J J为转向后状态所含项目集的为转向后状态所含项目集的核核使用闭包函数（使用闭包函数（CLOSURECLOSURE）和转向函数和转向函数(GOTO(I,X)(GOTO(I,X)构造文法构造文法

35、GG的的LR(0)LR(0)的的项目集规范族项目集规范族，步骤如下：，步骤如下：a)a)置项目置项目SS S为初态集的核，然后对核求闭包为初态集的核，然后对核求闭包CLOSURECLOSURE（SS S ）得到初态的得到初态的项目集项目集b)b)对初态集或其它所构造的项目集应用转换函数对初态集或其它所构造的项目集应用转换函数GOTO(IGOTO(I，X)= CLOSURE(J)X)= CLOSURE(J)求出新状态求出新状态J J的项目集的项目集c)c)重复重复b)b)直到不出现新的项目集为止直到不出现新的项目集为止S . EE . TE .T + ET .(E)T .int * TT .in

36、tS 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总结：构造识别文法活前缀总结：构造识别文法活前缀DFADFA的三种方法的三种方法一、根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造NFA再确定化为DFA二、求出文法的所有项目，

37、按一定规则构造识别活前缀的NFA再确定化为DFA三、使用闭包函数（使用闭包函数（CLOSURECLOSURE）和转向函数和转向函数(GOTO(I,X)(GOTO(I,X)构造文法构造文法GG的的LR(0)LR(0)的的项目集规项目集规范族，再由转换函数建立状态之间的连接关系范族，再由转换函数建立状态之间的连接关系得到识别活前缀的得到识别活前缀的DFADFALRLR（0 0）项目集规范族的项目类型分为如下四种：项目集规范族的项目类型分为如下四种：1 1）移进项目）移进项目 A a 2 2）待约项目待约项目 A B 3 3）归约项目归约项目 A 4 4）接受项目接受项目 S S 一个项目集可能包含

38、多种项目一个项目集可能包含多种项目a) 移进和归约项目同时存在。移进和归约项目同时存在。移进移进-归约冲突归约冲突b) 归约和归约项目同时存在。归约和归约项目同时存在。归约归约-归约冲突归约冲突LR(0)文法：若其文法：若其LR(0)项目集规范族不存在移进项目集规范族不存在移进-归约，或归约归约，或归约-归约冲突，称为归约冲突，称为LR(0)文法文法。LR(0)分析表的构造 LR(0)分析表相当于识别活前缀的有限自动机DAF的状态转换矩阵 LR(0)分析表的构造算法 书上p130, 倒数4行， A 改为改为 A a LR(0)分析器的工作过程令包含S S 的项目集Ik的下标k为分析器的初态LR

39、(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 .intS E .E T.E T. + ET int. * TT i

40、nt.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+(1234567891011SLR(1)分析 大多数适用的程序设计语言的文法不能满足LR(0)文法的条件，即其规范族中会有含有冲突的项目集（状态） 如果解决这种冲突？ 直觉：对于有冲突的状态，向前查看一个符号，以确定采用的动作文法文法G：(0) S S(1

41、) S rD (2) D D,i(3) D i状态状态核集合核集合闭包增加项目闭包增加项目项目集项目集I0S SS rDS SS rDI1S S S S I2S r DD D,iD iS r DD D,iD iI3S rD D D ,iS rD D D ,iI4D i D i I5D D, iD D, iI6D D,i D D,i ACTIONGOTO状状态态r,i#SD0S211acc2S433r1r1,S5r1r14r3r3r3r35S66r2r2r2r2I0:S SS rDI2: S rDD D,iD iI3: S rD D D ,iI4: D i I5: D D,iI1: S S I6

42、: D D,i SriD,iLR(0)LR(0)分析表分析表I3: S rD D D ,iACTIONGOTO状状态态r,i#SD0S211acc2S433r1r1,S5r1r14r3r3r3r35S66r2r2r2r2向前查看一个符号，看其是否是S的后跟符号（FOLLOW(S)）,若否则移进，是则归约。SLR(1)SLR(1)分析表分析表ACTIONGOTO状状态态r,i#SD0S211acc2S433S5r14r3r3r3r35S66r2r2r2r2一个LR(0)规范族中含有如下的项目集（状态）II = X b , A , B 若有：FOLLOW(A) FOLLOW(B) = FOLLOW

43、(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(

44、Ik,a)= Ij ，当a为终结符时，则置ACTIONk,a为Sjb) 若项目A 属于Ik ，则对a为任何终结符或#，且满足a FOLLOW(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)分析 若项目集A B 属于I时，则B 也属于I 把FIRST( )作为用产生式归约的搜索符（称为向前搜索符），作为用

45、产生式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)2)转换函数的构造转换函数的构造GOTOGOTO（I I，X X）= CLOSURE= CLO

46、SURE（J J）其中：其中：I I为为LR(1)LR(1)的项目集的项目集，X X为一文法符号为一文法符号 J=J=任何形如任何形如A A X ,a的项目的项目| A A X ,a属于属于III0: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 eI1:S S , #I2:S a Ad, #S a ec, #A e, dI3:S b Ac, #S b ed, #A e, cI4:S aA d, #I5:S ae c, #A e , dI6:S bA c, #

47、I7:S be d, #A e , cI8: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,# = ac

48、c5) 其它填上“报错标志” LR(1)项目集的构造对某些同心集的分裂可能使状态数目剧烈的增长文法G：(0) S S(1) B aB (2) S BB(3) 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:S 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

49、 ， I4和I7 ， I8和I9分别为同心集I3:B a B, a/bB aB, a/bB b, a/bI6:S a B, #B aB, #B b, #I4:B b , a/bI7:B b , #I8:B a B , a/bI9: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)项目集。合并同心集的几点说明 同心集合并后心仍相同，只是超前搜索符集

50、合为各同心集超前搜索符的和集 合并同心集后转换函数自动合并 LR(1)文法合并同心集后也只可能出现归约-归约冲突，而没有移进-归约冲突 合并同心集后可能会推迟发现错误的时间，但错误出现的位置仍是准确的ACTIONGOTO状态状态ab#SB0S3,6S4,7121acc2S3,6S753,6S3,6S48,94,7r3r3r35r18,9r2r2r2ACTIONGOTO状态状态ab#SB0S3S4121acc2S6S753S3S484r3r35r16S6S797r38r2r29r2合并同心集后合并同心集后二义性文法在LR分析中的应用 对于某些二义文法，可以人为地给出优先性和结合性的规定，从而可以