编译原理作业四

1、已知文法

$$A\to aAd|aAb|\epsilon$$

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

解：

文法 $A\to aAd|aAb|\epsilon$ 的增广文法为 $G^{{}^{\prime }}$，增加产生式 $S^{{}^{\prime }}\to A$，若产生式排序为：

$$\begin{array}{rl}0& S^{{}^{\prime }}\to A\\ 1& A\to aAd\\ 2& A\to aAb\\ 3& A\to \epsilon \end{array}$$

由产生式知：

$$\begin{array}{rl}& FIRST(S^{{}^{\prime }})=\{\epsilon ,a\}\\ & FIRST(A)=\{\epsilon ,a\}\\ & FOLLOW(S^{{}^{\prime }})=\{\mathrm{\#}\}\\ & FOLLOW(A)=\{d,b,\mathrm{\#}\}\end{array}$$

$G^{{}^{\prime }}$ 的 $LR(0)$ 项目集族及识别活前缀的 $\text{DFA}$ 如下图所示：

由图可知，此状态机存在移进-归约冲突，故不是 $LR(0)$ 文法。

在 $I_0$、$I_2$ 中，

$$FOLLOW(A)\cap \{a\}=\{d,b,\mathrm{\#}\}\cap \{a\}=\varnothing$$

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

构造 $$ 分析表如下：

对输入串 $$ 的分析过程如下

分析成功，说明输入串 $$ 是文法的句子。

3、考虑文法

$$

(1) 列出这个文法的所有 $$ 项目。
(2) 按 (1) 列出的项目构造识别这个文法活前缀的 $$，把这个 $$ 确定化为 $$，说明这个 $$ 的所有状态全体构成这个文法的 $$ 规范族。
(3) 这个文法是 $$ 的吗？若是，构造出它的 $$ 分析表。
(4) 这个文法是 $$ 或 $$ 的吗？

解：

(1) 令增广文法 $$ 为

$$

文法所有的 $$ 项目如下：

(2) (1) 中构造的增广文法，其 $$ 项目集规范族及其文法识别活前缀的 $$ 如下：

(3) 不是。