编译原理第7章答案
编译原理第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 S
7 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非常接近，但句子判断错误的速度要高很多。
感谢您的阅读，祝您生活愉快。