编译原理课后作业集#

---

第一章 引论#

题 1#

什么是编译程序？

题 2#

计算机执行用高级语言编写的程序有哪些方式？它们之间的主要区别是什么？

题 3#

编译过程通常分为哪几个阶段？请给出编译程序总框图。

---

第二章 高级程序设计语言的语法描述#

题 2#

令文法 $G(N)$ 为：

$$\begin{aligned} N &\to D \mid ND \\ D &\to 0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9 \end{aligned}$$

(1) $G(N)$ 的语言 $L(G(N))$ 是什么？ (2) 给出句子 0731 和 863 的最左推导和最右推导。

题 4#

写一个文法，使其语言是偶数集，且每个偶数不以 $0$ 开头。

题 5#

给出下面语言的相应文法：

1. $L_1 = \{a^n b^n c^i \mid n \ge 1, i \ge 0\}$
2. $L_2 = \{a^i b^n c^n \mid n \ge 1, i \ge 0\}$
3. $L_3 = \{a^n b^n a^m b^m \mid n, m \ge 0\}$
4. $L_4 = \{1^n 0^m 1^m 0^n \mid n, m \ge 0\}$

题 7#

令文法 $G(E)$ 为：

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

(1) 给出 $i+i*i$、$i*(i+i)$ 的最左推导和最右推导。 (2) 给出 $i+i+i$、$i+i*i$ 和 $i-i-i$ 的语法树。

题 10#

证明下面的文法是二义的：

$$S \to iSeS \mid iS \mid i$$

---

第三章 词法分析#

题 6#

令 $A$、$B$ 和 $C$ 是任意正规式，证明以下关系成立： (1) $A \mid A = A$ (2) $(A^*)^* = A^*$ (3) $A^* = \varepsilon \mid A A^*$ (4) $(AB)^*A = A(BA)^*$ (5) $A = b \mid aA$ 当且仅当 $A = a^*b$

题 7#

构造下列正规式相应的 DFA： (1) $1(0 \mid 1)^*101$ (2) $0^*10^*10^*10^*$

题 8#

给出下面正规表达式： (1) 以 01 结尾的二进制数串。 (2) 能被 $5$ 整除的十进制整数。 (3) 包含奇数个 $1$ 或奇数个 $0$ 的二进制数串。

题 9#

对下面情况给出 DFA 及正规表达式： (1) $\{0,1\}$ 上含子串 010 的所有串。

题 12#

将下面的有限自动机分别确定化和最小化。

(a) 需确定化的有限自动机：

• 初始状态/接受状态：$0$
• 状态转移：
  • 状态 $0$：接收 $a$ 转移到 $0$；接收 $a, b$ 转移到 $1$。
  • 状态 $1$：接收 $a$ 转移到 $0$。

(b) 需最小化的有限自动机：

• 初始状态：$0$
• 接受状态：$0, 1$
• 状态转移：
  • 状态 $0$：接收 $a$ 转移到 $1$；接收 $b$ 转移到 $2$。
  • 状态 $1$：接收 $a$ 转移到 $1$；接收 $b$ 转移到 $4$。
  • 状态 $2$：接收 $a$ 转移到 $1$；接收 $b$ 转移到 $3$。
  • 状态 $3$：接收 $a$ 转移到 $3$；接收 $b$ 转移到 $2$。
  • 状态 $4$：接收 $a$ 转移到 $0$；接收 $b$ 转移到 $5$。
  • 状态 $5$：接收 $a$ 转移到 $5$；接收 $b$ 转移到 $4$。

---

第四章 语法分析#

题 5#

考虑下面文法 $G_1$：

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

(1) 消去 $G_1$ 的左递归。然后，对每个非终结符，写出不带回溯的递归子程序。 (2) 经改写后的文法是否是 $\text{LL}(1)$ 的？给出它的预测分析表。

题 6#

对下面的文法 $G$：

$$\begin{aligned} E &\to T E' \\ E' &\to +E \mid \varepsilon \\ T &\to F T' \\ T' &\to T \mid \varepsilon \\ F &\to P F' \\ F' &\to *F' \mid \varepsilon \\ P &\to (E) \mid a \mid b \mid \wedge \end{aligned}$$

(1) 构造这个文法的每个非终结符的 $\text{FIRST}$ 和 $\text{FOLLOW}$ 集合。 (2) 证明这个文法是 $\text{LL}(1)$ 的。 (3) 构造它的预测分析表。 (4) 构造它的递归下降分析程序。

题 7#

对下面文法：

$$\begin{aligned} \textit{Expr} &\to -\textit{Expr} \mid (\textit{Expr}) \mid \textit{Var} \ \textit{ExprTail} \\ \textit{ExprTail} &\to -\textit{Expr} \mid \varepsilon \\ \textit{Var} &\to \textit{id} \ \textit{VarTail} \\ \textit{VarTail} &\to (\textit{Expr}) \mid \varepsilon \end{aligned}$$

(1) 构造 $\text{LL}(1)$ 分析表。 (2) 给出对句子 $id--id((id))$ 的分析过程。

题 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#

考虑文法：

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

(1) 列出这个文法的所有 $\text{LR}(0)$ 项目。 (2) 构造这个文法的 $\text{LR}(0)$ 项目集规范族及识别活前缀的 DFA。 (3) 这个文法是 $\text{SLR}$ 的吗？若是，构造出它的 $\text{SLR}$ 分析表。 (4) 这个文法是 $\text{LALR}$ 或 $\text{LR}(1)$ 的吗？

题 17#

证明下面文法是 $\text{SLR}(1)$ 的但不是 $\text{LR}(0)$ 的。

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