编译原理课本大题集#

---

习题 2.7#

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

---

习题 3.7（前2个正规式）#

构造下列正规式相应的 DFA：

1. $1(0 \mid 1)^*101$
2. $1(1010^* \mid 1(010)^*1)^*0$

---

习题 3.8（前4问）#

给出下面正规表达式： （1）以 01 结尾的二进制数串； （2）能被 $5$ 整除的十进制整数； （3）包含奇数个 $1$ 或奇数个 $0$ 的二进制数串； （4）英文字母组成的所有符号串，要求符号串中的字母依照字典序排列；

---

习题 4.2 (1) (3)#

对下面的文法 $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}$。 （3）构造它的预测分析表。

---

习题 5.7#

证明下面文法是 $\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}$$

---

习题 6.7#

下列文法由开始符号 $S$ 产生一个二进制数，令综合属性 $val$ 给出该数的值：

$$\begin{aligned} S &\to L . L \mid L \\ L &\to L B \mid B \\ B &\to 0 \mid 1 \end{aligned}$$

试设计求 $S.val$ 的属性文法，其中，已知 $B$ 的综合属性 $c$，给出由 $B$ 产生的二进制位的结果值。例如，输入 $101.101$ 时，$S.val = 5.625$，其中第一个二进制位的值是 $4$，最后一个二进制位的值是 $0.125$。

---

习题 7.1（前2个表达式）#

1. 给出下面表达式的逆波兰表示（后缀式）：
   • $a * ( - b + c )$
   • $\text{not } A \text{ or not } ( C \text{ or not } D )$

---

习题 7.4#

4. 按 7.3 节所说的办法，写出下面赋值句： $A := B * ( - C + D )$ 的自下而上语法制导翻译过程。给出所产生的三地址代码。

---

习题 7.7#

7. 用 7.5.1 节的办法，把下面的语句翻译成四元式序列：

   while A < C and B < D do
     if A = 1 then C := C + 1 else
       while A <= D do A := A + 2;

---

作业 10.1#

题目：试把以下程序划分为基本块并作出其程序流图。

real C
A := 0
B := 1
L1: A := A + B
if B >= C goto L2
B := B + 1
goto L1
L2: write A
halt