内容发布更新时间 : 2024/11/17 6:40:33星期一 下面是文章的全部内容请认真阅读。

第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}=?

所以在I0、I2 中的移进-归约冲突可以由Follow 集解决，所以G 是SLR(1)文法。 构造的SLR(1)分析表如下：

1

对输入串ab#的分析过程:

第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

2

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 如下图所示：

在I2 中：

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

在I2、I8 中：Follow(s) ∩{0，1}= { #} ∩{0，1}=

所以在I2 、I8 中的移进-归约冲突可以由Follow 集解决，所以G 是SLR(1)文法。 构造的SLR(1)分析表如下：

3