第四章 习题#

12. 句型分析#

令文法 $G_1$ 为：

$$\begin{aligned} E &\to E + T \mid T \\ T &\to T * F \mid F \\ F &\to (E) \mid i \end{aligned}$$

证明 $E + T * F$ 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

---

13. 表格结构文法#

考虑下面的表格结构文法 $G_2$：

$$\begin{aligned} S &\to a \mid \wedge \mid (T) \\ T &\to T, S \mid S \end{aligned}$$

(1) 给出 $(a, (a, a))$ 和 $(((a, a), \wedge, (a)), a)$ 的最左和最右推导。

(2) 指出 $(((a, a), \wedge, (a)), a)$ 的规范归约及每一步的句柄。根据这个规范归约，给出”移进—归约”的过程，并给出它的语法树自下而上的构造过程。

---

15. LR 分析#

考虑文法：

$$\begin{aligned} S &\to AS \mid b \\ A &\to SA \mid a \end{aligned}$$

(1) 列出这个文法的所有 LR(0) 项目。

(2) 构造这个文法的 LR(0) 项目集规范族及识别活前缀的 DFA。

(3) 这个文法是 SLR 的吗？若是，构造出它的 SLR 分析表。

(4) 这个文法是 LALR 或 LR(1) 的吗？

---

17. SLR(1) 与 LR(0)#

证明下面文法是 SLR(1) 的但不是 LR(0) 的。

$$\begin{aligned} S &\to A \\ A &\to Ab \mid bBa \\ B &\to aAc \mid a \mid aAb \end{aligned}$$