编译原理第7章答案

第七章 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非常接近，但句子判断错误的速度要高很多。 译原理习题解答 页6/6

17．若包含条件语句的语句文法可缩写为：

SiSeS|iS|S;S|a

其中：i代表if,e代表else,a代表某一语句。若规定： (1) else与其左边最近的if结合 (2) ;服从左结合

试给出文法中i,e,; 的优先关系，然后构造出无二义性的LR分析表，并对输入串iiaea#给出分析过程。

解：加入S/S产生式构造出增广文法如下： [0] S/S [1] SiSeS

[2] SiS [3] SS;S [4] Sa

该文法的LR(0)项目集及状态转换矩阵是： I0: S/•S S•iSeS S•iS S•S;S S•a i I2: Si•SeS Si•S S•iSeS S•iS S•S;S S•a e ; I3: a Sa• # S I1: S/S• SS•;S I1: S/S• SS•;S I4: SS;•S S•iSeS S•iS S•S;S S•a acc I2: Si•SeS Si•S S•iSeS S•iS S•S;S S•a I3: Sa• I4: SS;•S S•iSeS S•iS S•S;S S•a I2 I3 I5: SiS•eS SiS• SS•;S I2 I3 I6: SS;S• SS•;S I5: SiS•eS SiS• SS•;S I7: SiSe•S S•iSeS S•iS S•S;S S•a I4 I6: SS;S• SS•;S I2 I4 I3 I8: SiSeS• SS•;S I7: SiSe•S S•iSeS S•iS S•S;S S•a I4 I8: SiSeS• SS•;S 译原理习题解答 页7/7 由习惯可知，定义文法中i,e,;,a4个算符的优先关系为：a>e>i>;。并且i与;的结合方向均为自左至右。

由上述状态项目集可见：

a. 状态I1存在移进-归约冲突，由于FOLLOW(S/)∩{;}={#}∩{;}=Φ,所以面临#号时应acc，面临;号时

应移进。

b. 状态I5存在移进-归约冲突，由于FOLLOW(S)={e,;,#}与{;}或{e}交集不空，所以不是SLR(1)文法，

根据优先级与结合性有，如果面临#号应该归约到S。如果面临e，由于e优先于i，应移进；如果面临;，由于i优先于;，应归约。

c. 状态I6存在移进-归约冲突，由于FOLLOW(S)={e,;,#}与{;}交集不空，根据优先级与结合性有，

如果面临#或e号应该归约到S。如果面临;，由于;服从左结合，应归约到S。

d. 状态I8存在移进-归约冲突，由于FOLLOW(S)={e,;,#}与{;}交集不空，根据优先级与结合性有，

如果面临#或e号应该归约到S。如果面临;，由于e优先于;，应归约到S；

由上述分析得到该文法的无二义性的LR分析表如下：

表7.17.1 二义性文法的LR分析表 ACTION GOTO 状态 i e ; a # S 0 S2 S3 1 1 S4 acc 2 S2 S3 5 3 r4 r4 r4 4 S2 S3 6 5 S7 r2 r2 6 r3 r3 r3 7 S2 S3 8 8 r1 r1 r1 下面对输入串iiaea#给出分析过程: 步骤 状态栈 符号栈 输入串 ACTION GOTO 1 2 3 4 5 6 7 8 9 10 0 02 022 0223 0225 02257 022573 022578 025 01 # #i #ii #iia #iiS #iiSe #iiSea #iiSeS #iS #S iiaea# iaea# aea# ea# ea# a# # # # # S2 S2 S3 r4 S7 S3 r4 r1 r2 acc 5 8 5 1