编译原理课件 第 6 讲 LR分析法 (1)

1、1 第六讲第六讲 LR分析法分析法 vLR分析概述分析概述 vLR(0)分析分析 vSLR(1)分析分析 vLR(1)分析分析 vLALR(1)分析分析 v二义性文法在二义性文法在LR分析中的应用分析中的应用 2 v复习：移进复习：移进- -归约分析归约分析 3 文法文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d a b b c de 步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进 A 3） #ab bcde# 归约归约(Ab) 4） #aA bcde# 移进移进 A 5） #aAb

2、 cde# 归约归约(AAb) 6） #aA cde# 移进移进 7） #aAc de# 移进移进 B 8） # aAcd e# 归约归约(Bd) 9） #aAcB e# 移进移进 11） #S # 接受接受 S 10） #aAcBe # 归约归约(SaAcBe) 分析符号串abbcde是否GS的句子 对输入串abbcde#的移进-规约分析过程 SaAcBe aAcde aAbcde abbcde 4 v在步骤在步骤3中，用中，用Ab归约归约 v在步骤在步骤5中，用中，用AAb归约归约 v问题：何时移进？何时归约？用哪个产生式问题：何时移进？何时归约？用哪个产生式 归约？归约？ 5 3） #a

3、b bcde# 归约归约(Ab) 5） #aAb cde# 归约归约(AAb) 4） #aA bcde# 移进移进 6） #aA cde# 移进移进 分析：已分析过的部分在栈中的分析：已分析过的部分在栈中的前缀前缀不同，而且移进和归不同，而且移进和归 约后栈中的状态会发生变化约后栈中的状态会发生变化 我们引入一个新的我们引入一个新的状态栈状态栈来表示符号栈中的符号目前状态来表示符号栈中的符号目前状态 用用LRLR分析表分析表来表示不同状态下对于各输入符号应采取的动来表示不同状态下对于各输入符号应采取的动 作作 6 LR分析器分析器工作过程示意图工作过程示意图 总控程序总控程序 ACTION表表

4、GOTO表表 S0 S1 # X1 . . . Sn . . . Xn SP 输出输出 a1 a2 ai # an 输入串输入串 状态栈状态栈 文法符号栈文法符号栈 LR分析表分析表分析栈分析栈 7 LR分析使用两张表 u ACTION表表 告诉分析器：栈顶状态为告诉分析器：栈顶状态为S, 当前当前输入符输入符号是号是a时做时做什么什么 1. ACTIONS,a= Sj 2. ACTIONS,a= rj (第j条产生式为A) 3. ACTIONS,a= acc 4. ACTIONS,a= error u GOTO表表 GOTOS,A栈顶状态为栈顶状态为S，归约之后的非终结符为，归约之后的非终结

5、符为A时，时， 要放到栈顶的新状态要放到栈顶的新状态 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# 归约归约

6、(AAb) 0236 r3 3 8） #aAcd e# 归约归约(Bd) 02358 r4 7 10） #aAcBe # 归约归约(SaAcBe) 023579 r1 1 状态栈状态栈ACTIONGOTO 文法文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d Si:移进，并将状态移进，并将状态i进栈进栈 ri:用第用第i个产生式归约，同时状个产生式归约，同时状 态栈与符号栈退出相应个符号，态栈与符号栈退出相应个符号， 产生式左部非终结符入符号栈，产生式左部非终结符入符号栈， 根据根据GOTO表将相应状态入栈表将相应状态入栈 S8 S9 9 问题： v对于一个

7、文法，状态集是如何确定的？ vLR分析表是如何得到的？ 10 ,a,ab ,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBe 可归前缀与活前缀可归前缀与活前缀 文法文法GS： (1) S aAcBe1 (2) A b2 (3) A Ab3 (4) B d4 S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 每次归约句型的每次归约句型的 前部分前部分依次为：依次为： ab2 aAb3 aAcd4 aAcBe1 规范句型的这种前部分符号串称为规范句型的这种前部分符号串称为可归前缀可归前缀 我们把形成可归前缀之前包括可归前缀在内我们把

8、形成可归前缀之前包括可归前缀在内 的所有规范句型的前缀都称为的所有规范句型的前缀都称为活前缀活前缀 1、a,aA,aAc都不只是某一个规范都不只是某一个规范 句型的前缀句型的前缀 2、活前缀表明已分析过的部分为、活前缀表明已分析过的部分为 规范句型的一个正确部分。规范句型的一个正确部分。 11 活前缀（活前缀（Viable Prefixes） 定义：定义： S A 是文法是文法G中的一个规范推导，中的一个规范推导， 如果符号串如果符号串是是的前缀，则称的前缀，则称是是G的一个的一个 活前缀活前缀。其中S是对原文法扩充(SS)增加 的非终结符. ? 为使S不出现在任何产生式的右部. 如G=(S,

9、a,SSa,Sa,S) 则拓广文法G=(S，S,a,S S, SSa,Sa,S) R * R 12 vLR分析需要构造识别分析需要构造识别活前缀活前缀的的有穷自动机有穷自动机 我们可以把文法的终结符和非终结符都看我们可以把文法的终结符和非终结符都看 成有穷自动机的输入符号，每次把一个符成有穷自动机的输入符号，每次把一个符 号进栈看成已识别过了该符号，同时状态号进栈看成已识别过了该符号，同时状态 进行转换，当识别到可归前缀时，相当于进行转换，当识别到可归前缀时，相当于 在栈中形成句柄，认为达到了识别句柄的在栈中形成句柄，认为达到了识别句柄的 终态。终态。 13 步骤步骤 符号栈符号栈 输入符号串

10、输入符号串动作动作 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

11、 7 10） #aAcBe # 归约归约(SaAcBe) 023579 r1 1 状态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 14 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 对输入串abbcde#的LR分析过程 状态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 15 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 对输入串ab

12、bcde#的LR分析过程 状态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 16 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 对输入串abbcde#的LR分析过程 3） #ab bcde# 归约归约(Ab) 024 r2 3 状态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 17 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2）

13、#a bbcde# 移进移进 02 S4 4） #aA bcde# 移进移进 023 S6 对输入串abbcde#的LR分析过程 3） #ab bcde# 归约归约(Ab) 024 r2 3 状态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 18 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 4） #aA bcde# 移进移进 023 S6 对输入串abbcde#的LR分析过程 3） #ab bcde# 归约归约(Ab) 024 r2 3

14、5） #aAb cde# 归约归约(AAb) 0236 r3 3 状态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 19 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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 状态栈状态栈

15、ACTIONGOTO * 0 14 23 57 6 9 S a b Ab c Be d 8 20 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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 * 0

16、 14 23 57 6 9 S a b Ab c Be d 8 21 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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 状

17、态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 22 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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)

18、 0236 r3 3 8） # aAcd e# 归约归约(Bd) 02358 r4 7 状态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 23 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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 b

19、cde# 归约归约(Ab) 024 r2 3 5） #aAb cde# 归约归约(AAb) 0236 r3 3 8） # aAcd e# 归约归约(Bd) 02358 r4 7 10） #aAcBe # 归约归约(SaAcBe) 023579 r1 1 状态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 24 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 4） #aA bcde# 移进移进 023 S6 6） #aA cde# 移进移进 02

20、3 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 状态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 25 如何构造识别活前缀的有限自动

21、机 v已经有了活前缀如何构造有限自动机? v活前缀及其可归前缀的一般计算方法 26 文法文法GS： S S0 S aAcBe1 A b2 A Ab3 B d4 句子句子abbcdeabbcde的可归前缀如下：的可归前缀如下： S0S0 ab2ab2 aAb3aAb3 aAcd4aAcd4 aAcBe1aAcBe1 构造识别其活前缀及可归前缀的有限自动机如下：构造识别其活前缀及可归前缀的有限自动机如下： 10 43 87 1312 1018 2 5 9 14 6 17 1516 11 10 S ab aAb aAcd a AcBe * 1 * 句子识别态 i句柄识别态 27 10 43 87 1

22、312 1018 2 5 9 14 6 17 1516 11 10 S ab aAb aAcd a AcBe * X 加上开始状态X 确定化得DFA 0 14 23 57 6 9 S a b Ab c Be d 8 * 识别活前缀的确定的有限自动机识别活前缀的确定的有限自动机 28 活前缀及其可归前缀的一般计算方法 定义 (非终结符的左文) ：文法G，AVN, LC(A)= | S A, V*, VT * 对拓广文法的开始符号S: LC(S)= 规范推导中在非终结符A左边所有可能出现的 符号串的集合。 推论：若文法G中有产生式B A，则有 LC(A) LC(B) 因为: SB A R * R

23、* R 29 文法文法GS： S S0 S aAcBe1 A b2 A Ab3 B d4 由前面的定义与推论我们知： 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 这样我们求出了每个这样我们求出了每个非终结符非终结符在规范推导中用该非终结符在规范推导中用该非终结符 的右部替换该非终结符之前，它的左部可能出现的的右部替换

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

25、b = aAb LR(0)C(B d) = B . . d = aAcd 总结：如何构造识别文法活前缀的有限自动机？总结：如何构造识别文法活前缀的有限自动机？ 1、根据文法算出其可归前缀、根据文法算出其可归前缀 2、根据可归前缀，构造识别文法活前缀的不确定有限自动机、根据可归前缀，构造识别文法活前缀的不确定有限自动机 3、确定化，从而构造出识别文法活前缀的确定的有限自动机、确定化，从而构造出识别文法活前缀的确定的有限自动机 参见课本参见课本P129的例子的例子 31 LR分析器的构造分析器的构造 1、构造识别文法活前缀的确定有限自动机、构造识别文法活前缀的确定有限自动机 2、根据该自动机构造相

26、应的分析表、根据该自动机构造相应的分析表(ACTION表、表、GOTO表表) 总控程序总控程序 Action/Goto表表 输入符号串输入符号串 输出输出 状态与符号栈状态与符号栈 32 这种方法构造识别可归前缀的有限自 动机从理论的角度讲是比较严格的， 但实现起来却很复杂 是否存在一种比较实用的方法？ 33 项目（项目（item）：）：在每个产生式的右部适当位置在每个产生式的右部适当位置 添加一个圆点构成添加一个圆点构成项目项目 例如：产生式例如：产生式S aAcBe对应有对应有6个项目个项目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aA

27、cB e 5 S aAcBe 项目圆点的项目圆点的左部左部表示分析过程的某个时刻用该产表示分析过程的某个时刻用该产 生式归约时生式归约时句柄已识别的部分句柄已识别的部分，圆点，圆点右部右部表示表示待待 识别的部分识别的部分。 空产生式空产生式A 的项目只有一个：的项目只有一个： A 34 由文法的产生式直接构造识别活由文法的产生式直接构造识别活 前缀和可归前缀的有限自动机前缀和可归前缀的有限自动机 l有限自动机有限自动机NFA的每一个状态由一个的每一个状态由一个项目项目 构成构成 35 构造识别活前缀的NFA： 1、把文法的所有产生式的项目都列出，每个项目都为、把文法的所有产生式的项目都列出，

28、每个项目都为NFA的的 一个状态一个状态 2、确定、确定初态初态、句柄识别态句柄识别态、句子识别态句子识别态 句柄识别态句柄识别态：圆点：圆点在最后的项目在最后的项目 句子识别态句子识别态：VN仅在产生式左部出现的产生式的句柄识别态仅在产生式左部出现的产生式的句柄识别态 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画标记为画标记为 的的 箭弧

29、到状态箭弧到状态k。（。（ X = A = ） ij Xi ik 36 文法文法G： S E E T + E E T T int * T T int T (E) 文法的项目有：文法的项目有： 1、 S E 2、 S E 3、 E T + E 4、 E T + E 5、 E T + E 6、 E T + E 7、 E T 8、 E T 9、T int * T 10、T int * T 11、T int * T 12、T int * T 13、 T int 14、 T int 15、 T (E) 16、 T ( E) 17、 T (E ) 18、 T (E) 37 NFA for Viable P

30、refixes 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 T E + int int * T T 38 根据圆点所在的位置圆点所在的位置和圆点后是终结符终结符还是非终非终 结符结符把项目分为以下几种： 移进项目，形如 A a 待约项目，形如 A B 归约项目，形如 A 接受项目，形如 S S 39 Translation to

31、the DFA S . E E . T E .T + E T .(E) T .int * T T .int S E . E T. E T. + E T int. * T T int. T (. E) E .T E .T + E T .(E) T .int * T T .int E T + E. E T + . E E .T E .T + E T .(E) T .int * T T .int T int * .T T .(E) T .int * T T .int T int * T. T (E.) T (E). E T ( int int * ) E E T int ( ( int T + (

32、T 项目集项目集 40 NFANFA确定化为确定化为DFADFA的工作量较大，我们考虑直接构的工作量较大，我们考虑直接构 造出项目集作为造出项目集作为DFADFA的状态，就可直接构造的状态，就可直接构造DFADFA 构成识别一个文法活前缀的构成识别一个文法活前缀的DFA项目集（状态）项目集（状态） 的全体称为这个文法的的全体称为这个文法的LR(0)项目集规范族项目集规范族. 41 如果如果I I是文法是文法GG的一个项目集，定义和构造的一个项目集，定义和构造I I的闭的闭 包包CLOSURE(I)CLOSURE(I)如下：如下： a)Ia)I的项目都在的项目都在CLOSURE(I)CLOSUR

33、E(I)中中 b)b)若若A A B 属于属于CLOSURE(I)CLOSURE(I)，则每一形如，则每一形如B B 的的 项目也属于项目也属于CLOSURE(I)CLOSURE(I) c)c)重复重复b)b)直到直到CLOSURE(I)CLOSURE(I)不再扩大不再扩大 通过通过闭包函数闭包函数(CLOSURE)来求来求DFA一个状态的一个状态的 项目集项目集 何时不再扩大？何时不再扩大？ 圆点后为圆点后为VT或在产生式的最后，不会增加新项目或在产生式的最后，不会增加新项目 42 v定义转换函数如下：定义转换函数如下： GO（I，X）= CLOSURE（J） 其中：其中：I为包含某一项目集

34、的状态，为包含某一项目集的状态， X为一文法符号，为一文法符号，XVNVT J=任何形如任何形如A X 的项目的项目| A X 属于属于I v圆点不在产生式右部圆点不在产生式右部最左边最左边的项目称为的项目称为核核，唯一，唯一 的例外是的例外是S S。因此用。因此用GO（I，X）转换函数）转换函数 得到的得到的J为转向后状态所含项目集的为转向后状态所含项目集的核核 43 使用闭包函数（使用闭包函数（CLOSURECLOSURE）和）和 转向函数转向函数 （GO(I,X)GO(I,X)）构造文法）构造文法GG的的LR(0)LR(0)的的项目集项目集 规范族规范族，步骤如下，步骤如下： c)重复重

35、复b)直到不出现新的项目集为止直到不出现新的项目集为止 b)对初态集或其它所构造的项目集应用转换函数对初态集或其它所构造的项目集应用转换函数 GO (I，X)= CLOSURE(J)求出新状态求出新状态J的项目集的项目集 a)置项目置项目S S为初态集的核，然后对核求闭包为初态集的核，然后对核求闭包 CLOSURE（S S）得到初态的项目集）得到初态的项目集 44 S . E E . T E .T + E T .(E) T .int * T T .int S E . E T. E T. + E T int. * T T int. T (. E) E .T E .T + E T .(E) T .

36、int * T T .int E T + E. E T + . E E .T E .T + E T .(E) T .int * T T .int T int * .T T .(E) T .int * T T .int T int * T. T (E.) T (E). E T ( int int * ) E E T int ( ( int T + ( T 文法文法G： S ET int * T E T + E T int E T T (E) I0： I1： I2： I3： I4： I5： I6： I7： I8： I9： I10： 45 总结：构造识别文法活前缀总结：构造识别文法活前缀DFADFA

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

38、间的连接关系 得到识别活前缀的得到识别活前缀的DFADFA 46 LRLR（0 0）项目集规范族的项目类型分为如下四种：）项目集规范族的项目类型分为如下四种： 1 1）移进项目）移进项目 A a 2 2）待约项目）待约项目 A B 3 3）归约项目）归约项目 A 4 4）接受项目）接受项目 S S 一个项目集可能包含多种项目一个项目集可能包含多种项目 a) 移进和归约项目同时存在。移进和归约项目同时存在。移进移进-归约冲突归约冲突 b) 归约和归约项目同时存在。归约和归约项目同时存在。归约归约-归约冲突归约冲突 47 LR(0)文法：文法： LR(0)文法：若其文法：若其LR(0)项目集规范族

39、不存在项目集规范族不存在 移进移进-归约，或归约归约，或归约-归约冲突，称为归约冲突，称为LR(0)文法文法。 48 LR(0)分析表的构造 vLR(0)分析表相当于识别活前缀的有限自动机 DFA的状态转换矩阵 vLR(0)分析表的构造算法(书上p135) vLR(0)分析器的工作过程(书上p136) 49 令包含令包含S S 的项目集的项目集Ik的下标的下标k为分析器的初态为分析器的初态 LR(0)分析表的分析表的ACTION和和GOTO表的表的构造步骤如下构造步骤如下： e) 其它填上其它填上“报错标志报错标志” d) 若项目若项目SS 属于属于Ik ，则置，则置ACTIONk,# = a

40、cc c) 若若GO(Ik,A)= Ij ，则置，则置GOTOk,A=j，其中，其中A为非终结为非终结 符，符，j为某一状态号为某一状态号 b) 若项目若项目A 属于属于Ik ，则对任何终结符，则对任何终结符a或或#，置，置 ACTIONk,a = rj ，j为产生式在文法为产生式在文法G中的编号（中的编号（0+） a) 若项目若项目A a 属于属于Ik，且转换函数，且转换函数GO(Ik,a)= Ij ， 当当 a为终结符时，则置为终结符时，则置ACTIONk,a为为Sj 假设已构造出假设已构造出LR(0)项目集规范族为：项目集规范族为： C=I0,I1,In 50 S . E E . T E

41、 .T + E T .(E) T .int * T T .int S E . E T. E T. + E T int. * T T int. T (. E) E .T E .T + E T .(E) T .int * T T .int E T + E. E T + . E E .T E .T + E T .(E) T .int * T T .int T int * .T T .(E) T .int * T T .int T int * T. T (E.) T (E). E T ( int int * ) E E T int ( ( int T + ( I0： I1： I2： I3： I4： I

42、5： I6： T I7： I8： I9： I10： 文法文法G： (1)S E(4)T int * T (2)E T + E (5)T int (3)E T (6)T (E) 51 SLR(1)分析 v大多数适用的程序设计语言的文法不能满足大多数适用的程序设计语言的文法不能满足 LR(0)文法的条件，即其规范族中会有含有冲文法的条件，即其规范族中会有含有冲 突的项目集（状态）突的项目集（状态） v如果解决这种冲突？如果解决这种冲突？ v直觉：对于有冲突的状态，向前查看直觉：对于有冲突的状态，向前查看一个一个符符 号，以确定采用的动作号，以确定采用的动作 52 P137文法文法G： (0) S

43、S (1) S rD (2) D D,i (3) D i ACTIONGOTO 状状态态 r,i#SD 0S21 1acc 2S43 3r1r1,S5r1r1 4r3r3r3r3 5S6 6r2r2r2r2 I0: S S S rD I2: S rD D D,i D i I3: S rD D D ,i I4: D i I5: D D,i I1: S S I6: D D,i S ri D , i LR(0)LR(0)分析表分析表 53 假定一个假定一个LR(0)规范族中含有如下的项目集（状态）规范族中含有如下的项目集（状态）I I = X b , A , B 若有：若有：FOLLOW(A) FO

44、LLOW(B) = FOLLOW(A) b = FOLLOW(B) b = 若一个文法的若一个文法的LR(0)分析表中所含有的动作冲突都能用上述方分析表中所含有的动作冲突都能用上述方 法解决，则称这个文法是法解决，则称这个文法是SLR(1)文法文法,所构造的分析表为所构造的分析表为 SLR(1)分析表，分析表，使用使用SLR(1)分析表的分析器为分析表的分析器为SLR(1)分析分析 器。器。 状态状态I面临某输入符号面临某输入符号a 1) 若若a=b，则移进，则移进 2) 若若a FOLLOW(A), 则用产生式则用产生式 A 进行归约进行归约 3) 若若a FOLLOW(B), 则用产生式则

45、用产生式 B 进行归约进行归约 4) 此外，报错此外，报错 54 “改进的改进的”SLR(1)分析：分析： 对所有非终结符都求出其对所有非终结符都求出其FOLLOW集合集合，这样只，这样只 有归约项目仅对面临输入符号包含在该归约项目有归约项目仅对面临输入符号包含在该归约项目 左部非终结符的左部非终结符的FOLLOW集合中，才采取用该产集合中，才采取用该产 生式归约的动作。生式归约的动作。 55 1) 若项目若项目A a 属于属于Ik，且转换函数，且转换函数GO(Ik,a)= Ij ，当，当a为终结符时，为终结符时， 则置则置ACTIONk,a为为Sj 2) 若项目若项目A 属于属于Ik ，则对

46、，则对a FOLLOW(A)时时，置，置ACTIONk,a = rj ，j为产生式在文法为产生式在文法G中的编号中的编号 3) 若若GO(Ik,A)= Ij ，则置，则置GOTOk,A=j，其中，其中A为非终结符，为非终结符，j为某一状为某一状 态号态号 4) 若项目若项目SS 属于属于Ik ，则置，则置ACTIONk,# = acc 5) 其它填上其它填上“报错标志报错标志” 改进的改进的SLR(1)分析表的分析表的ACTION表和表和GOTO表的构造步骤：表的构造步骤： 56 文法文法G： (0) S S (1) S rD (2) D D,i (3) D i 状状态态 GOTO函函数数 核

47、核集集合合 闭闭包包增增加加项项目目 项项目目集集 I0 S S S rD S S S rD I1 GOTO（I0，S） S S S S I2 GOTO（I0，r） S r D D D,i D i S r D D D,i D i I3 GOTO（I2，D） S rD D D ,i S rD D D ,i I4 GOTO（I2，i） D i D i I5 GOTO（I3， ， ） D D, i D D, i I6 GOTO（I5，i） D D,i D D,i ACTION GOTO 状状态态 r , i # S D 0 S2 1 1 acc 2 S4 3 3 S5 r1 4 r3 r3 5 S6

48、 6 r2 r2 SLR(1)SLR(1)分析表分析表 FOLLOW(S) = # FOLLOW(D) = #, , 57 v仍有许多文法构造的仍有许多文法构造的LR(0)LR(0)项目集规范族存在项目集规范族存在 的动作冲突不能用的动作冲突不能用SLR(1)SLR(1)方法解决方法解决 58 LR(1)分析 v若项目集若项目集A B 属于属于I时，则时，则B 也属于也属于I v把把FIRST( )作为用产生式归约的搜索符（称为向作为用产生式归约的搜索符（称为向 前搜索符），作为用产生式前搜索符），作为用产生式B 归约时查看的符号归约时查看的符号 集合（用以代替集合（用以代替SLR(1)分析中

49、的分析中的FOLLOW集），集）， 并把此搜索符号的集合也放在相应项目的后面，这并把此搜索符号的集合也放在相应项目的后面，这 种处理方法即为种处理方法即为LR(1)方法方法 59 LR(1)项目集族的构造：项目集族的构造： (1)针对初始项目针对初始项目SS,#求闭包求闭包 (2)再用转换函数逐步求出整个文法的再用转换函数逐步求出整个文法的LR(1) 项目集族。项目集族。 60 v1）构造）构造LR（1）项目集的闭包函数）项目集的闭包函数 a) I的项目都在的项目都在CLOSURE(I)中中 b) 若若A B , a CLOSURE(I)，B 是文法的产生式，是文法的产生式，V*，b FIRS

50、T( a),则则 B ,b也属于也属于CLOSURE(I) c) 重复重复b)直到直到CLOSURE(I)不再扩大不再扩大 61 v2)转换函数的构造转换函数的构造 GO（I，X）= CLOSURE（J） 其中：其中：I为为LR(1)的项目集，的项目集，X为一文法符号为一文法符号 J = 任何形如任何形如A X ,a的项目的项目 | A X ,a属于属于I 62 文法G：(0) S S (1) S aAd (2) S bAc (3) S aec (4) S bed (5) A e I0= S S, #,S aAd, #,S bAc, #,S aec, #,S bed, # I1 = GO(I0

51、,S) = S S , # I2 = GO(I0,a) = S a Ad, #, S a ec, #, A e, d I3 = GO(I0,b) = S b Ac, #, S b ed, #, A e, c I4 = GO(I2,A) = S aA d, # I5 = GO(I2,e) = S ae c, #, A e , d I6 = GO(I3,A) = S bA c, # 查看查看I5 ， ，I7中的冲突，体会 中的冲突，体会LR(1)如何解决如何解决 I11 = GO(I7,d) = S bed , # I10 = GO(I6,c) = S bAc , # I9 = GO(I5,c)

52、= S ae c , # I8 = GO(I4,d) = S aAd , # I7 = GO(I3,e) = S be d, #, A e , c 63 LR(1)分析表的构造分析表的构造 1) 若项目若项目A a ,b属于属于Ik，且转换函数，且转换函数 GO(Ik,a)= Ij ，当，当a为终结符时，则置为终结符时，则置 ACTIONk,a为为Sj 2) 若项目若项目A ,a属于属于Ik ，则置，则置ACTIONk,a = rj ，j为产生式在文法为产生式在文法G中的编号中的编号 3) 若若GO(Ik,A)= Ij ，则置，则置GOTOk,A=j，其中，其中A为为 非终结符，非终结符，j为

53、某一状态号为某一状态号 4) 若项目若项目SS ,#属于属于Ik ，则置，则置ACTIONk,# = acc 5) 其它填上其它填上“报错标志报错标志” 64 vLR(1)LR(1)项目集可看成由两个部分组成：项目集可看成由两个部分组成： 心心 ，向前搜索符向前搜索符 v多数情况下，同一文法的多数情况下，同一文法的LR(1)LR(1)项目集的个数项目集的个数 比比LR(0)LR(0)项目集个数多。这是由于项目集个数多。这是由于LR(1)LR(1)项目项目 集的构造对某些同心集的分裂，可能使状态集的构造对某些同心集的分裂，可能使状态 数目剧烈的增长。数目剧烈的增长。 65 文法G： (0) S

54、S (1) B aB (2) S BB (3) B b I0: S S, # S BB, # B aB, a/b B b, a/b I4: B b , a/b I3: B a B, a/b B aB, a/b B b, a/b I8: B a B , a/b I7: B b , # I1: S S , # S I2: S B B, # B a B, # B b, # B b b B b b a a I6: B a B, # B aB, # B b, # a a I5: S B B , # B I9: B a B , # B LR(1)项目集和转换函数 即使不考查搜索即使不考查搜索 符，任何项目