编译原理作业四

1、已知文法

\[ A \rightarrow aAd | aAb | \varepsilon \]

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

解：

文法 \(A \rightarrow aAd | aAb | \varepsilon\) 的增广文法为 \(G^{'}\)，增加产生式 \(S^{'} \rightarrow A\)，若产生式排序为：

\[ \begin{split} 0 \quad &S^{'} \rightarrow A \\ 1 \quad &A \rightarrow aAd \\ 2 \quad &A \rightarrow aAb \\ 3 \quad &A \rightarrow \varepsilon \end{split} \]

由产生式知：

\[ \begin{split} &FIRST(S^{'}) = \{\varepsilon, a\} \\ &FIRST(A) = \{\varepsilon, a\} \\ &FOLLOW(S^{'}) = \{\#\} \\ &FOLLOW(A) = \{d, b, \#\} \\ \end{split} \]

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

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

在 \(I_0\)、\(I_2\) 中，

\[ FOLLOW(A) \cap \{a\} = \{d, b, \#\} \cap \{a\} = \varnothing \]

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

构造 \(SLR(1)\) 分析表如下：

对输入串 \(ab\#\) 的分析过程如下

分析成功，说明输入串 \(ab\) 是文法的句子。

3、考虑文法

\[ \begin{split} S \rightarrow AS | b \\ A \rightarrow SA | a \end{split} \]

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

解：

(1) 令增广文法 \(G^{'}\) 为

\[ \begin{split} 0 \quad &S^{'} \rightarrow S \\ 1 \quad &S \rightarrow AS \\ 2 \quad &S \rightarrow b \\ 3 \quad &A \rightarrow SA \\ 4 \quad &A \rightarrow a \end{split} \]

文法所有的 \(\text{LR}(0)\) 项目如下：