编译原理习题解答 页26/26 ACTION 状态 0 1 2 3 4 5 6 7 8 9 GOTO ) r1 r2 S7 r5 r3 r4 , r1 r2 S8 r5 r3 r4 # acc r1 r2 r5 r3 r4 S 1 6 9 T 5 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 编译原理习题解答 页27/27 下面构造它的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),)， I12: S?(T?),)， T?T?,S,)， I13 I14 I8 I9 I13： T?T,S?,)， I14: I11 S?(T)?,)， 从上表可看出,不存在移进-归约冲突以及归约归约冲突，所以该文法是LR(1)文法。从而有下面的LR(1)分析表： 编译原理习题解答 页28/28
表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非常接近，但句子判断错误的速度要高很多。 编译原理习题解答 页29/29
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 编译原理习题解答 页30/30 由习惯可知，定义文法中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