第六七章 作业与习题参考答案

编译原理作业参考答案 - 1 -

第七章 LR分析法

第1题 已知文法 A→aAd|aAb|ε

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

文法： A→aAd|aAb|ε

拓广文法为G′，增加产生式S′→A 若产生式排序为： 0 S' →A 1 A →aAd 2 A →aAb 3 A →ε 由产生式知： First (S' ) = {ε,a} First (A ) = {ε,a} Follow(S' ) = {#} Follow(A ) = {d,b,#}

G′的LR(0)项目集族及识别活前缀的DFA如下图所示：

在I0中：

A →.aAd和A →.aAb为移进项目，A →.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。 在I0、I2中：

Follow(A) ∩{a}= {d，b，#} ∩{a}=构造的SLR(1)分析表如下： 题目1的SLR(1)分析表

所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。

- 2 - ：编译原理作业参考答案

状态（State） 0 1 2 3 4 5 题目1对输入串ab#的分析过程

文法符号栈 剩余输入串 （input left） ab#.... S2 b#.... r3(A →ε) b#.... S5 #.... r2(A →aAb) #.... acc Goto Action a d b # S2 r3 r3 r3 acc S2 r3 r3 r3 S4 S5 r1 r1 r1 r2 r2 r2 Goto A 1 . 3 状态栈（state stack） 0 0 2 0 2 3 0 2 35 0 1 动作（action） 3 1 # #a #aA #aAb #A 分析成功，说明输入串ab是题目1文法的句子

第2题若有定义二进制数的文法如下： S→L.L|L L→LB|B B→0|1

(1) 试为该文法构造LR分析表，并说明属哪类LR分析表。 (2) 给出输入串101.110的分析过程。

解：文法： S→L.L|L L→LB|B B→0|1

拓广文法为G′，增加产生式S′→S 若产生式排序为： 0 S' →S 1 S →L.L 2 S →L 3 L →LB

编译原理作业参考答案 4 L →B 5 B →0 6 B →1 由产生式知： First (S' ) = {0,1} First (S ) = {0,1} First (L ) = {0,1} First (B ) = {0,1} Follow(S' ) = {#} Follow(S ) = {#} Follow(L ) = {.,0,1,#} Follow(B ) = {.,0,1,#}

G′的LR(0)项目集族及识别活前缀的DFA如下图所示：

- 3 -

在I2中：

B →.0和 B →.1为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。 在I2、I8中：

Follow(s) ∩{0，1}= { #} ∩{0，1}=构造的SLR(1)分析表如下： 题目2的SLR(1)分析表

状态（State） 0 1 2 Action · 0 1 # S4 S5 acc S6 S4 S5 r2 Goto S L B 1 2 3 . 7

所以在I2 、I8中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。

- 4 - ：编译原理作业参考答案

3 4 5 6 7 8 题目2对输入串101.110#的分析过程

剩余输入串 （input left） 101.110#.... Shift 01.110#.... Reduce by :B →1 01.110#.... Reduce by :S →LB 01.110#.... Shift 1.110#.... Reduce by :B →0 1.110#.... Reduce by :S →LB 1.110#.... Shift .110#.... Reduce by :B →1 .110#.... Reduce by :S →LB .110#.... Shift 110#.... Shift 10#.... Reduce by :B →1 10#.... Reduce by :S →B 10#.... Shift 0#.... Reduce by :B →1 0#.... Reduce by :S →LB 0#.... Shift #.... Reduce by :B →0 #.... Reduce by :S →L.L #.... r4 r4 r4 r4 r5 r5 r5 r5 r6 r6 r6 r6 S4 S5 r3 r3 r3 r3 S4 S5 r1 . . . 8 3 . 7 状态栈（state stack） 0 0 5 0 3 0 2 0 2 4 0 2 7 0 2 0 2 5 0 2 7 0 2 0 2 6 0 2 6 5 0 2 6 3 0 2 6 8 0 2 6 8 5 0 2 6 8 7 0 2 6 8 0 2 6 8 4 0 2 6 8 7 0 1 文法符号栈 # #1 #B #L #L0 #LB #L #L1 #LB #L #L. #L.1 #L.B #L.L #L.L1 #L.LB #L.L #L.L0 #L.LB #S 动作（action） 分析成功，说明输入串101.110是题目2文法的句子。

3．考虑文法：S?AS|b A?SA|a (1) 列出该文法所有的LR（0）项目。

（2） 按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA的所有状态全体构成这个文法的LR（0）规范族。 （3） 此文法是SLR（1）的吗？，若是，构造他的SLR分析表 （4） 这个文法是LALR或LR（1）的吗？

编译原理作业参考答案 - 5 -

解：

(1) 构造增广文法，S’?S

文法的LR(0)项目有：

1. S’?.S 2. S’?S. 3. S?.AS 4. S?A.S

5. S?AS. 6. S?.b 7. S?b. 8. A?.SA 9. A?S.A 10. A?SA. 11. A?.a 12. A?a. （2）所产生的NFA略。

由规则构造所需的DFA: I5:A?S.A I1:S’?S. A?.SA S A ?S.A S A A?.SA A?a. A?.a S?.AS S?b. b S ?.AS a S?.b a A I7:A?SA. a a I0:SI2:A?a. S?A.S ’?.S S ?.AS b S?.AS S b ?.b S?.b I3:S ?b. S AA?.SA ?.SA A A?.a ?.a b A I4:S?A.S I6:S?AS. a .AS b A?S.A S? A .b S A?.SA A S? S A?.SA A?.a A?.a S?.AS S?.b 则LR(0)项目集规范族为：

C＝｛I0,I1,I2,I3,I4,I5,I6,I7｝ （3）可以看到I1,I6,I7存在着移进－归约的冲突。

冲突是不能用SLR(1)的方法来解决。比如I6: 对于状态S?AS. 和S?.b

Follow(S)={#,a,b}与{b}相交不为空。 所以以上文法不是SLR(1)文法。

（4）为验证该文法是否为LALR或LR(1)的，构造LR(1)项目集。

对于I5,产生了移进－归约矛盾，所以这个文法不是LR(1)文法。于是也不是LALR文法。

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