第6讲 LR分析法

1、1 第六讲第六讲 LR分析法分析法 LR分析概述分析概述 LR(0)分析分析 SLR(1)分析分析 LR(1)分析分析 LALR(1)分析分析 二义性文法在二义性文法在LR分析中的应用分析中的应用 2 复习：移进复习：移进- -归约分析归约分析 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 cde# 归

2、约归约(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 在步骤在步骤3中，用中，用Ab归约归约 在步骤在步骤5中，用中，用AAb归约归约 问题：何时移进？何时归约？用哪个产生问题：何时移进？何时归约？用哪个产生 式归约？式归约？ 5 3） #ab bcde# 归约

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

4、X1 . . . Sn . . . Xn SP 输出输出 a1 a2 ai # an 输入串输入串 状态栈状态栈 符号栈符号栈 LR分析表分析表 7 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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）

5、 #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 文法文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d Si:移进，并将状态移进，并将状态i进栈进栈 ri:用第用第i个产生式归约，同时状个产生式归约，同时状 态栈与符号栈退出相应个符号，态栈与符号栈退出相应个符号， 根据根据GOTO表将相应状态入栈表将相应状态入栈

6、 S8 S9 8 问题问题： 对于一个文法，状态集是如何确定的？对于一个文法，状态集是如何确定的？ LRLR分析表是如何得到的？分析表是如何得到的？ 9 可归前缀与活前缀可归前缀与活前缀 文法文法GS： (1) S aAcBe1 (2) A b2 (3) A Ab3 (4) B d4 S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 每次归约句型的每次归约句型的 前部分前部分依次为：依次为： ab2 aAb3 aAcd4 aAcBe1 规范句型的这种前部分符号串称为规范句型的这种前部分符号串称为可归前缀可归前缀 把形成可归前缀之前包括可归前缀在内的所把形成可归前缀之前

7、包括可归前缀在内的所 有规范句型的前缀都称为有规范句型的前缀都称为活前缀活前缀 ,a,ab ,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBe 10 活前缀（活前缀（Viable Prefixes） 定义：定义： S A 是文法是文法G中的一个规范推中的一个规范推 导，如果符号串导，如果符号串是是的前缀，则称的前缀，则称是是G 的一个的一个活前缀活前缀。 R * R 11 LR分析需要构造识别分析需要构造识别活前缀活前缀的的有穷自动机有穷自动机 把文法的终结符和非终结符都看成有穷自把文法的终结符和非终结符都看成有穷自 动机的输入符号，每次把一个符号进栈看

8、动机的输入符号，每次把一个符号进栈看 成已识别过了该符号，同时状态进行转换，成已识别过了该符号，同时状态进行转换， 当识别到可归前缀时，相当于在栈中形成当识别到可归前缀时，相当于在栈中形成 句柄，认为达到了识别句柄的终态。句柄，认为达到了识别句柄的终态。 12 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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# 移进移进 0235

9、7 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 * 13 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 对输入串对输

10、入串abbcde#的的LR分析过程分析过程 状态栈状态栈ACTIONGOTO 0 14 23 57 6 9 S a b Ab c Be d 8 * 14 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 对输入串对输入串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# 移进移

11、进 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 * 16 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 4） #aA bcde# 移进移进 023 S6 对输入串对输入串abbcde#的的LR分析过程分析过程 3） #ab bcde# 归约归约(Ab) 024 r2 3 状态栈状态栈ACTIONGOTO 0 1

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

13、符号串动作动作 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 状态栈状态栈ACTIONGOTO * 0 14 23 57 6 9 S a b Ab c Be d 8 19 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2

14、 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 14 23 57 6 9 S a b Ab c Be d 8 20 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #

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

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 状态栈状态栈ACTIONGOTO 0 14 23 57

17、 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) 0236 r3 3 8） # a

18、Acd 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 * 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 11） #S

19、 # 接受接受 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 * 24 如何构造识别活前缀的有限自动机如何构造识别活前缀的有限自动机 已经有了活前缀如何构造有限自动机已经有了活前缀如何构造有限自动机? ?

20、活前缀及其可归前缀的一般计算方法活前缀及其可归前缀的一般计算方法 25 文法文法GS： S S0 S aAcBe1 A b2 A Ab3 B d4 句子句子abbcdeabbcde的可归前缀如下：的可归前缀如下： S0S0 ab1ab1 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句柄识别态句柄识别态 26 10 43

21、87 1312 1018 2 5 9 14 6 17 1516 11 10 S ab aAb aAcd a AcBe * X 加上开始状态加上开始状态X 确定化确定化 X 13 24 68 5 9 S a b Ab c Be d 7 * 识别活前缀的确定的有限自动机识别活前缀的确定的有限自动机 27 项目（项目（item）：）：在每个产生式的右部适当位置在每个产生式的右部适当位置 添加一个圆点构成添加一个圆点构成项目项目 例如：产生式例如：产生式S aAcBe对应有对应有6个项目个项目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aAcB e

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

23、每个项目 都为都为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 30 文法文法G： S E E T + E E T T int * T T int T (E) 文法的项目有：文法的项目有： 1、 S E

24、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) 31 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

25、T. T int. T .int T .int * T T int * T. T int *.T T int.* T E T E + int int * T T 32 Translation to 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 in

26、t * .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 项目集项目集 33 NFANFA确定化为确定化为DFADFA的工作量较大，我们考虑直接构的工作量较大，我们考虑直接构 造出项目集作为造出项目集作为DFADFA的状态，就可直接构造的状态，就可直接构造DFADFA 构成识别一个文法活前缀的构成识别一个文法活前缀的DFA项目集（状态）项目集（状态） 的全体称为这个文法的的全体称为这个文法的LR(0)项目集规范族项目集规范族. 34 如果如果I I是文

27、法是文法GG的一个项目集，定义和构造的一个项目集，定义和构造I I的闭的闭 包包CLOSURE(I)CLOSURE(I)如下：如下： a)Ia)I的项目都在的项目都在CLOSURE(I)CLOSURE(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一个状态的一个状态的 项目集项目集 35 定义转换函数如下：定义转换函数

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

29、规项目集规 范族范族，步骤如下，步骤如下： c)重复重复b)直到不出现新的项目集为止直到不出现新的项目集为止 b)对初态集或其它所构造的项目集应用转换函数对初态集或其它所构造的项目集应用转换函数 GO(I，X)= CLOSURE(J)求出新状态求出新状态J的项目集的项目集 a)置项目置项目S S为初态集的核，然后对核求闭包为初态集的核，然后对核求闭包 CLOSURE（S S）得到初态的项目集得到初态的项目集 37 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)

30、 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 + ( T 文法文法G： S E E T + E E T T int * T T int T (E) 38 总结：构造识别文法活前缀总结：构造识别文法活前缀DFADFA的三种方法的三种方法 一、根据形式定义

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

32、前缀的DFADFA 39 根据根据圆点所在的位置圆点所在的位置和和圆点后是终结符还是非终圆点后是终结符还是非终 结符结符把把LRLR（0 0）项目集规范族的项目类型分为以项目集规范族的项目类型分为以 下几种：下几种： 移进项目，形如移进项目，形如 A a 待约项目，形如待约项目，形如 A B 归约项目，形如归约项目，形如 A 接受项目，形如接受项目，形如 S S 一个项目集可能包含多种项目一个项目集可能包含多种项目 a) 移进和归约项目同时存在。移进和归约项目同时存在。移进移进-归约冲突归约冲突 b) 归约和归约项目同时存在。归约和归约项目同时存在。归约归约-归约冲突归约冲突 40 S . E

33、 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 + ( T 文法文法G： S E

34、E T + E E T T int * T T int T (E) 41 LR(0)文法：文法： LR(0)文法：若其文法：若其LR(0)项目集规范族不存在项目集规范族不存在 移进移进-归约，或归约归约，或归约-归约冲突，称为归约冲突，称为LR(0)文法文法。 42 LR(0)分析表的构造 LR(0)分析表相当于识别活前缀的有限自动机分析表相当于识别活前缀的有限自动机 DFA的状态转换矩阵的状态转换矩阵 LR(0)分析表的构造算法分析表的构造算法(书上书上p135) LR(0)分析器的工作过程分析器的工作过程(书上书上p136) 43 令包含令包含S S 的项目集的项目集Ik的下标的下标k为分

35、析器的初态为分析器的初态 LR(0)分析表的分析表的ACTION和和GOTO表的表的构造步骤如下构造步骤如下： e) 其它填上其它填上“报错标志报错标志” d) 若项目若项目SS 属于属于Ik ，则置则置ACTIONk,# = acc c) 若若GO(Ik,A)= Ij ，则置则置GOTOk,A=j，其中其中A为非终结为非终结 符，符，j为某一状态号为某一状态号 b) 若项目若项目A 属于属于Ik ，则对任何终结符则对任何终结符a或或#，置置 ACTIONk,a = rj ，j为产生式在文法为产生式在文法G中的编号中的编号 a) 若项目若项目A a 属于属于Ik，且转换函数且转换函数GO(Ik

36、,a)= Ij ， 当当 a为终结符时，则置为终结符时，则置ACTIONk,a为为Sj 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 .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

37、 ( int int * ) E E T int ( ( int T + ( 1 2 3 4 5 6 7 8 9 10 11 能构造出相应的能构造出相应的 LR(0)分析表吗？分析表吗？ 45 例：对文法例：对文法GE构造出构造出LR(0)分析表：分析表： E aA | bB A cA | d B cB | d 46 SLR(1)分析 大多数适用的程序设计语言的文法不能满大多数适用的程序设计语言的文法不能满 足足LR(0)文法的条件，即其规范族中会有含文法的条件，即其规范族中会有含 有冲突的项目集（状态）有冲突的项目集（状态） 如果解决这种冲突？如果解决这种冲突？ 直觉：对于有冲突的状态，向前

38、查看直觉：对于有冲突的状态，向前查看一个一个 符号，以确定采用的动作符号，以确定采用的动作 47 文法文法G： (0) S 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)分析表分析表 48 一个一个LR(0)规范族中含有如下的项

39、目集（状态）规范族中含有如下的项目集（状态）I I = X b , A , B 若有：若有：FOLLOW(A) FOLLOW(B) = FOLLOW(A) b = FOLLOW(B) b = 若一个文法的若一个文法的LR(0)分析表中所含有的动作冲突都能用上述方分析表中所含有的动作冲突都能用上述方 法解决，则称这个文法是法解决，则称这个文法是SLR(1)文法文法,所构造的分析表为所构造的分析表为 SLR(1)分析表，分析表，使用使用SLR(1)分析表的分析器为分析表的分析器为SLR(1)分析分析 器。器。 状态状态I面临某输入符号面临某输入符号a 1) 若若a=b，则移进则移进 2) 若若a

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

41、当当a为终结符时，为终结符时， 则置则置ACTIONk,a为为Sj 2) 若项目若项目A 属于属于Ik ，则对则对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表的构造步骤：表的构造步骤： 51 文法文法G：

42、 (0) S S (1) S rD (2) D D,i (3) D i 状状态态 GOTO函函数数 核核集集合合 闭闭包包增增加加项项目目 项项目目集集 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

43、 , i # S D 0 S2 1 1 acc 2 S4 3 3 S5 r1 4 r3 r3 5 S6 6 r2 r2 SLR(1)SLR(1)分析表分析表 FOLLOW(S) = # FOLLOW(D) = #, , 52 仍有许多文法构造的仍有许多文法构造的LR(0)LR(0)项目集规范族存项目集规范族存 在的动作冲突不能用在的动作冲突不能用SLR(1)SLR(1)方法解决方法解决 53 LR(1)分析 若项目集若项目集A B 属于属于I时，则时，则B 也属于也属于I 把把FIRST( )作为用产生式归约的搜索符（称为向作为用产生式归约的搜索符（称为向 前搜索符），作为用产生式前搜索符），

44、作为用产生式B 归约时查看的符归约时查看的符 号集合（用以代替号集合（用以代替SLR(1)分析中的分析中的FOLLOW集），集）， 并把此搜索符号的集合也放在相应项目的后面，并把此搜索符号的集合也放在相应项目的后面， 这种处理方法即为这种处理方法即为LR(1)方法方法 54 LR(1)项目集族的构造：项目集族的构造： (1)针对初始项目针对初始项目SS,#求闭包求闭包 (2)再用转换函数逐步求出整个文法的再用转换函数逐步求出整个文法的LR(1) 项目集族。项目集族。 55 1）构造）构造LR（1）项目集的闭包函数项目集的闭包函数 a) I的项目都在的项目都在CLOSURE(I)中中 b) 若若

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

46、 aAd, #,S bAc, #,S aec, #,S bed, # I1 = GO(I0,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

47、, # I10 = GO(I6,c) = S bAc , # I9 = GO(I5,c) = S ae c , # I8 = GO(I4,d) = S aAd , # I7 = GO(I3,e) = S be d, #, A e , c 58 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为某一状态号为某一状态号 4) 若项目若项目SS ,#属于属于Ik ，则置则置ACTIONk,# = acc 5) 其它填上其它填上“报错标志报错标志” 59 LR(1)LR(1)项目集的构造对某些同心集的分裂可项目集的构造对某些同心集的分裂可 能使状态数目剧烈的增长能使状态数目剧烈的增长 60 文法G： (0) S S (1) B aB (2) S BB (3) B b I0: S S, # S BB, # B aB, a/b B b, a/b I4: