编译原理第7章答案

译原理习题解答 页1/1

第七章 LR分析法

1．已知文法 A?aAd|aAb|ε

判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。

/

解：增加一个非终结符S后，产生原文法的增广文法有：

/

S?A

A?aAd|aAb|ε

下面构造它的LR(0)项目集规范族为：

状 态 当 前 符号 a I2： A?a?Ad A?a?Ab A??aAd A??aAb A?? I2 b d # A I1： /S?A? I0： /S??A A??aAd A??aAb A?? I1： /S?A? I2： A?a?Ad A?a?Ab A??aAd A??aAb A?? I3： A?aA?d A?aA?b I4： A?aAb? I5： A?aAd? acc I3： A?aA?d A?aA?b I4： A?aAb? I5： A?aAd?

从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。 对于I0来说有

FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ

所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。 对于I2来说有也有与I0完全相同的结论。

这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。其他SLR(1)分析表为： 下面构造它的SLR(1)项目集规范族为：

表7.1.1 文法的SLR(1)分析表 ACTION 状态 0 1 2 3 4 5 a S2 S2 r2 r1 b r1 r1 S4 r2 r1 d r2 r2 S5 r2 r1 # r3 acc r3 r2 r1 GOTO A 1 3 译原理习题解答 页2/2 对输入串ab#给出分析过程为： 步骤 1 2 3 4 5 状态栈 0 02 023 0234 01 符号栈 # #a #aA #aAb #A 输入串 ab# b# b# # # ACTION S2 r3 S4 r2 acc GOTO 3 1 15．已知文法为： S?a|^|(T) T?T,S|S

(1) 构造它的LR(0),LALR(1),LR(1)分析表。 (2) 给出对输入符号串(a#和(a,a#的分析过程。

(3) 说明(1)中三种分析表发现错误的时刻和输入串的出错位置有何区别。 解：

/

(1)加入非终结符S，方法的增广文法为：

/

S?S S?a S?^ S?(T) T?T,S T?S

下面构造它的LR(0)项目集规范族为：

状 态 当 前 符号 a I2: S?a? ^ I3: S?^? ( I4: S?(?T) T??T,S T??S S??a S??^ S??(T) I4 ) , # /S I1: S?S? T I0: /S??S S??a S??^ S??(T) I1 I2 I3 I4: S?(?T) T??T,S T??S S??a S??^ S??(T) I5: S?(T?) T?T?,S I2 I3 acc I6: T?S? I5: S?(T?) T?T?,S I7: S?(T)? I8: T?T,?S S??a S??^ S??(T) I6 I7: I8: T?T,?S S??a S??^ S??(T) I9 I2 I3 I4 I9 T?T,S? 从上表可看出,不存在移进-归约冲突以及归约归约冲突，该文法是LR(0)文法。从而有下面的LR(0)分析表： 表7.15.1 文法的LR(0)分析表

译原理习题解答 页3/3

ACTION 状态 0 1 2 3 4 5 6 7 8 9 a S2 r1 r2 S2 r5 r3 S2 r4 ^ S3 r1 r2 S3 r5 r3 S3 r4 ( S4 r1 r2 S4 r5 r3 S4 r4 ) r1 r2 S7 r5 r3 r4 , r1 r2 S8 r5 r3 r4 # acc r1 r2 r5 r3 r4 S 1 6 9 GOTO T 5 下面构造它的LR(1)项目集规范族为： I0: /S??S,# S??a,# S??^,# S??(T),# a I2: S?a?,# ^ I3: S?^?,# ( ) , # S I1: /S?S?,# T I4: S?(?T),# T??T,S,)， T??S,)， S??a,)， S??^,)， S??(T),)， I1 I2 I3 I4: I7: I8: I9: S?(?T),# S?a?,)， S?^?,)， S?(?T),)， T??T,S,)， T??T,S,)， T??S,)， T??S,)， S??a,)， S??a,)， S??^,)， S??^,)， S??(T),)， S??(T),)， I5: S?(T?),# T?T?,S,)， acc I6: T?S?,)， I5: S?(T?),# T?T?,S,)， I10: S?(T)?,# I11: T?T,?S,)， S??a,)， S??^,)， S??(T),)， I6 I7: I8 I8 I9 I6 I12: S?(T?),)， T?T?,S,)， I9: I7 S?(?T),)， T??T,S,)， T??S,)， S??a,)， S??^,)， S??(T),)， I10 I11: I7 T?T,?S,)， S??a,)， S??^,)， S??(T),)， I8 I9 I13： T?T,S?,)， 译原理习题解答 页4/4

I12: S?(T?),)， T?T?,S,)， I13 I14 I14: I11 S?(T)?,)， 从上表可看出,不存在移进-归约冲突以及归约归约冲突，所以该文法是LR(1)文法。从而有下面的LR(1)分析表： 译原理习题解答 页5/5

表7.15.2 文法的LR(1)分析表 ACTION 状态 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 GOTO ) , S11 r5 r1 r2 S11 r4 r3 # acc r1 r2 r3 S 1 6 6 13 GOTO ) , r1 r2 S11 r5 r3 r4 # acc r1 r2 r3 S 1 6 13 T 5 T 5 12 a S2 S7 S7 S7 ^ S3 S8 S8 S8 ( S4 S9 S9 S9 S10 r5 r1 r2 S14 r4 r3 ACTION 由上图可知I2与I7，I3与I8，I4与I9，I5与I12，I10与I14是同心集。现在合并同心集有文法的LALR(1)分析表： 状态 0 1 2 3 4 5 6 10 11 13 a S2 S2 S2 ^ S3 S3 S3 ( S4 S4 S4 r1 r2 S10 r5 r3 r4 将状态10,11,13分别重新命名为7,8,9有： 表7.15.3 文法的LALR(1)分析表 ACTION 状态 a ^ ( ) , # S 1 6 9 GOTO T 5 0 S2 S3 S4 1 acc 2 r1 r1 r1 3 r2 r2 r2 4 S2 S3 S4 5 S7 S8 6 r5 r5 7 r3 r3 r3 8 S2 S3 S4 9 r4 r4 可以看出，表7.15.3与 表7.15.1非常接近，但句子判断错误的速度要高很多。

本文来源：https://www.bwwdw.com/article/z8p5.html