内容发布更新时间 : 2024/5/21 23:53:19星期一 下面是文章的全部内容请认真阅读。

编译原理作业参考答案 - 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)文法。