编译原理 第6章-LR分析-小结

1、Compiler Construction Principles LRLR分析法分析法 大多数用上下文无关文法描述的语言大多数用上下文无关文法描述的语言 都可以用相应的都可以用相应的LRLR分析器予以识别。分析器予以识别。 1. LR1. LR分析法是一种规范归约分析法，分析法是一种规范归约分析法， Compiler Construction Principles 2. 从给定的上下文无关文法构造从给定的上下文无关文法构造LRLR 分析表的方法是分析表的方法是： 对对LR(1)LR(1)或或 LALR(1)LALR(1)分析表，构造分析表，构造 LR(1)LR(1)项目集规范族。项目集规范族。

2、 (1)(1)对对LR(0)LR(0)或或 SLR(1)SLR(1)分析表，构造分析表，构造 LR(0)LR(0)项目集规范族项目集规范族; ; Compiler Construction Principles (2)(2)构造识别文法规范句型活前缀的构造识别文法规范句型活前缀的DFA。 (3)(3)将将DFA转换成相应的转换成相应的LR分析表。分析表。 注意文法一定要拓广。注意文法一定要拓广。 四种分析表的构造基本相同，仅对含四种分析表的构造基本相同，仅对含 归约项目的项目集构造分析表元素不同。归约项目的项目集构造分析表元素不同。 3. 3. 四种四种LRLR文法的判别方法文法的判别方法 (

3、1) (1)任何的二义性文法都不是任何的二义性文法都不是LRLR类文法。类文法。 Compiler Construction Principles SLR(1)文法是文法是LR(0)项目集中所有项目集中所有 含冲突的项目集都能用含冲突的项目集都能用SLR规则解决冲规则解决冲 突。突。 (或或SLR(1)分析表中不含多重定义分析表中不含多重定义) (2) (2)根据项目集中是否含冲突项目或根据项目集中是否含冲突项目或 相应分析表中是否含多重定义元素进行相应分析表中是否含多重定义元素进行 判断：判断： LR(0)文法是所有的文法是所有的LR(0)项目集中项目集中 没有移进一归约冲突或归约一归约冲突

4、。没有移进一归约冲突或归约一归约冲突。 (或或LR(0)分析表中不含多重定义分析表中不含多重定义) Compiler Construction Principles SLR规则：规则： I: A .b B 1 1. B2 2. b FOLLOW(B1)= FOLLOW(B1)FOLLOW(B2)= b FOLLOW(B2)= a b 移进移进 a FOLLOW(B1) 用用B 1 1 归约归约 a FOLLOW(B2) 用用B2 2 归约归约 Compiler Construction Principles LR(1)项目集中无移进一归约冲突项目集中无移进一归约冲突 或归约一归约冲突。（或或归

5、约一归约冲突。（或LR(1)分析表分析表 中不含多重定义）中不含多重定义） LALR(1)项目集中无归约一归约项目集中无归约一归约 冲突。冲突。(或或LALR(1) 分析表中不含多分析表中不含多 重定义）重定义） 4.4.四种四种LR类文法之间的关系类文法之间的关系 注意展望符只对归约项目起作用。注意展望符只对归约项目起作用。 Compiler Construction Principles 例例1 设有文法设有文法GS: S (S) | 试判断该文法是否试判断该文法是否SLR(1)文法，若文法，若 不是，请说明理由；若是，请构造不是，请说明理由；若是，请构造 SLR(1)分析表。分析表。 解

6、：首先将文法拓广，并给出每条规则编号解：首先将文法拓广，并给出每条规则编号 0. SS0. SS 1. S 1. S (S) 2. S 2. S Compiler Construction Principles I0:SSSS S S (S) S S I3: S (S) 构造该文法的构造该文法的LR(0)项目集族和转换函项目集族和转换函 数如下图所示。数如下图所示。 该文法不是该文法不是LR(0)文法。因为文法。因为I0，I2中中 含有移进含有移进归约的冲突。归约的冲突。 I1: SS. I2:S S (S) S S (S) S S I4: S (S) S (S ( ) 0. S S 1. S

7、 (S) 2. S 见表见表 Compiler Construction Principles 但是但是I0，I2中的移进中的移进归约的冲突可以用归约的冲突可以用 SLR(1)方法解决：方法解决： FOLLOW(S)=), #(= 所以该文法是所以该文法是SLR(1)文法。文法。 其其SLR(1)分析表如下表：分析表如下表： Compiler Construction Principles ACTIONGOTO ( ) # S O O 1 1 2 2 3 3 4 4 S S2 2 r r2 2 r r2 2 accacc 1 1 S S2 2 r r2 2 r r2 2 3 3 S S4 4

8、r r1 1 r r1 1 文法文法GSGS的的SLR(1)SLR(1)分析表分析表 0. S S 1. S (S) 2. S 见图见图 Compiler Construction Principles 例例2 设有文法设有文法GS: 试证明该文法是试证明该文法是SLR(1)文法，但不是文法，但不是 LR(0)文法。文法。 解：首先将文法拓广，并对规则进行编号解：首先将文法拓广，并对规则进行编号 直接构造直接构造LR(0)项目集如下：项目集如下： S aSb | aSd | 0. S S 1. S aSb1. S aSb 2. S aSd2. S aSd 3. S 3. S Compiler

9、Construction Principles I I0 0: :S S S aSbS aSb S aSdS aSd S S I I1 1: :SSSS I I2 2: :S aSbS aSb S aSdS aSd S aSbS aSb S aSdS aSd S S I I3 3: :S aSbS aSb S aSdS aSd I I4 4: :S aSbS aSb I I5 5: :S aSdS aSd 0. S S 2. S aSb 1. S aSd 3. S Compiler Construction Principles 检查每个项目集可知，项目集检查每个项目集可知，项目集I0和和I2

10、中有中有 移进一归约冲突，因此该文法不是移进一归约冲突，因此该文法不是LR(0)文文 法。法。 又因为又因为 所以项目集所以项目集I0和和I2中移进一归约冲突可中移进一归约冲突可 以用以用SLR(1)方法解决。因此该文法是方法解决。因此该文法是 SLR(1)文法，但不是文法，但不是LR(0)文法。文法。 FOLLOW(S)=b,d,#a= Compiler Construction Principles 例例3 设有文法设有文法GS: 2.试判断该文法是否试判断该文法是否SLR(1)文法文法, 若若 不是不是, 请说明理由；若是，请构造出请说明理由；若是，请构造出 SLR(1)分析表分析表,

11、并给出符号串并给出符号串( )#的的 分析过程。分析过程。 1.构造识别文法规范句型活前缀的构造识别文法规范句型活前缀的 DFA( LR(0)项目集族和项目集族和GO函数函数 )。 S S(S) | Compiler Construction Principles 3. 试判断该文法是否试判断该文法是否LR(1)文法，文法， 若不是，请说明理由；若是，请构若不是，请说明理由；若是，请构 造造LR(1)分析表。分析表。 Compiler Construction Principles 分析分析 首先将文法拓广，并对规则编首先将文法拓广，并对规则编 号号: 0. SS S S(S) 1. S 构造

12、构造LR(0)项目集规范项目集规范族和转换函数族和转换函数 如下图所示如下图所示: : Compiler Construction Principles S S(S.) S S.(S) I0:SS S S(S) S I1: SS. I2: I4: S S(S) S ( S ( ) 0. SS S S(S) 1. S S S.(S) S S(S) S S S(.S) I3: Compiler Construction Principles S S(S) S S(S) I0:SS S S(S) S I1: SS I2: I4: S S(S) S ( S ( ) 0. SS S S(S) 1. S

13、S S(S) S S(S) S S S(S) I3: I1中的移进中的移进归约的冲突可以用归约的冲突可以用SLR(1)方法方法 解决：解决：FOLLOW(S)=#(= 所以该文法是所以该文法是SLR(1)文法。文法。 Compiler Construction Principles 其其SLR(1)分析表如下表：分析表如下表： ACTIONGOTO ( ) # S O O 1 1 2 2 3 3 4 4 r r2 2 r r2 2 r r2 2 accacc 1 1 r r2 2 r r2 2 r r2 2 3 3 S S4 4 r r1 1 r r1 1 r r1 1 S S2 2 S S2

14、 2 FOLLOW(S) = #, (, ) Compiler Construction Principles 501232#S(S()# 用第用第2条规则条规则S 归约归约 40123#S(S( )#S2 3012#S( )# 用第用第2条规则条规则S 归约归约 201#S( )#S2 步骤步骤栈中状态栈中状态栈中符号栈中符号输入串输入串分析动作分析动作 10#( )# 用第用第2条规则条规则S 归约归约 1001#S#accacc 用第用第1条规则条规则SS(S)归归约约#S(S) 012349 80123#S(S)#S4 用第用第1条规则条规则SS(S)归归约约 )#S(S(S)0123

15、2347 6012323#S(S(S)#S4 Compiler Construction Principles 0. SS S S(S) 1. S 构造构造LR(1)项目集规范项目集规范族和转换函数族和转换函数 如下图所示如下图所示: : Compiler Construction Principles I0:SS, # SS(S), #/( S , #/( I1: SS , # I2: S ( S ( ) 0. SS S S(S) 1. S SS.SS.(S), #/( SS(S), )/( S , )/( SS(S), #/( I3: SS(S.), #/( S S.(S), )/( I5: SS(S), )/( S , )/( SS(S), )/( I6: SS(S), )/( S S(S), )/( S I7:SS(S), )/ ( ) I4:SS(S),#/ ( Compiler Construction Principles 所有的所有的LR(1)项目集中没有移进项目集中没有移进归约归约 的冲突的冲突,所以该文法为所以该文法为LR(1)文法文法 或该文法为或该文法为SLR(1)文法文法, 任何任何SLR(1)文文 法都是法都