编译原理计算大题解题步骤与示例#

---

模块一：高级程序设计语言的语法描述#

题型一：文法设计 (Grammar Design)#

如何做：

1. 明确符号的含义：
   • 我们用大写字母（如 $S$, $A$, $B$）代表“中间过程代号”或“组合”。
   • 我们用小写字母、数字和符号（如 $a$, $b$, $0$, $1$）代表“最终出现在句子里的具体字符”。
   • 用箭头 $\to$ 表示代换，用竖线 $\mid$ 表示“或者”。
2. 观察字符的匹配规律：
   • 如果两个符号的数量是绑定的（例如有 $n$ 个 $a$ 就必须有 $n$ 个 $b$ 连着），那就在规则的左右两边分别写上 $a$ 和 $b$，中间写上它自己，形成一种“包夹”结构。如：$X \to aXb$。
   • 确定最简单的情况（递归结束条件）。如果数量可以是 0，最简情况就是一个空符号 $\varepsilon$（表示空无一物），如：$X \to aXb \mid \varepsilon$。
   • 如果数量必须大于等于 1，那最简情况就是 $ab$，如：$X \to aXb \mid ab$。
3. 独立部分拆开写：
   • 如果句子的前半部分（如 $a^n b^n$）和后半部分（如 $c^i$）互不干扰，数量没有绑定关系，就用两个不同的大写字母拼接，比如先写一行初始规则 $S \to X Y$，然后再分别写大写字母 $X$ 的规则和 $Y$ 的规则。

• 题目：给定语言 $L_1 = \{a^n b^n c^i \mid n \ge 1, i \ge 0\}$，构造其文法。

• 解答：

  1. 句子由两部分拼接而成：前半部分是 $a^n b^n$（数量相等，且至少有一个），后半部分是 $c^i$（可以有任意个，包括 0 个）。
  2. 我们设初始组合为大写字母 $S$，拆成前半部分组合 $X$ 和后半部分组合 $Y$： $S \to X Y$
  3. 前半部分 $X$ 产生相同数量的 $a$ 和 $b$，且至少 1 对，代换规则为： $X \to aXb \mid ab$
  4. 后半部分 $Y$ 产生任意个 $c$（包括 0 个，即空字符 $\varepsilon$），代换规则为： $Y \to cY \mid \varepsilon$
  5. 完整文法为： $$\begin{aligned} S &\to X Y \\ X &\to aXb \mid ab \\ Y &\to cY \mid \varepsilon \end{aligned}$$

• 例题 2：构造一个只能产生奇数（且多位数首位不为 0）的十进制数文法。

• 解答：

  1. 句子如果是一位数，只能是奇数：$1, 3, 5, 7, 9$，我们用非终结符 $D_{\text{odd}}$ 表示。
  2. 句子如果是多位数，首位数字不能是 0，只能是 $1$ 到 $9$，我们用非终结符 $D_{\text{head}}$ 表示；末位数字必须是奇数，即 $D_{\text{odd}}$；中间部分可以是任意长度的数字串（包含0，也可以为空），我们用非终结符 $M$ 表示。
  3. 定义单个数字非终结符 $D$，它可以是 0 或者是首位数字 $D_{\text{head}}$。
  4. 完整文法定义为： $$\begin{aligned} S &\to D_{\text{odd}} \mid D_{\text{head}} M D_{\text{odd}} \\ M &\to D M \mid \varepsilon \\ D_{\text{odd}} &\to 1 \mid 3 \mid 5 \mid 7 \mid 9 \\ D_{\text{head}} &\to 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9 \\ D &\to 0 \mid D_{\text{head}} \end{aligned}$$

---

题型二：最左/最右推导与推导过程判定#

如何做：

1. 最左推导：从初始大写字母（比如 $E$）开始。在每一步中，只在当前的符号串里找到最靠左边的那个大写字母，查规则把它代换掉，其余的大写字母和符号保持不变。重复这一步，直到符号串里没有任何大写字母。
2. 最右推导（规范推导）：同理，每一步中只找到最靠右边的那个大写字母，用规则代换掉它，其他部分不动，直到没有大写字母。
3. 画代换过程树（语法树）：
   • 把初始大写字母写在最顶端。
   • 每次代换时（如 $E \to E + T$），从这个大写字母往下分叉画出分支，依次连上它变出来的符号（如左分叉连 $E$，中间分叉连 $+$, 右分叉连 $T$）。
   • 重复这个过程，直到树的最底端全都是具体的符号（小写字母、数字或符号）。从左到右把树底部的具体符号串起来，应当刚好等于要推导的句子。

• 题目：已知代换规则为： $E \to T \mid E + T \mid E - T \ , \ T \to F \mid T * F \mid T / F \ , \ F \to (E) \mid i$ 给出句子 $i + i * i$ 的最左和最右推导，并给出语法树。

• 解答：

  • 最左推导（每次换最左边的大写字母）： $E \Rightarrow E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow i + T \Rightarrow i + T * F \Rightarrow i + F * F \Rightarrow i + i * F \Rightarrow i + i * i$
  • 最右推导（每次换最右边的大写字母）： $E \Rightarrow E + T \Rightarrow E + T * F \Rightarrow E + T * i \Rightarrow E + F * i \Rightarrow E + i * i \Rightarrow T + i * i \Rightarrow F + i * i \Rightarrow i + i * i$
  • 语法分析树：

    graph TD
        E1["E"] --> E2["E"]
        E1 --> P["+"]
        E1 --> T1["T"]
        E2 --> T2["T"]
        T2 --> F1["F"]
        F1 --> I1["i"]
        T1 --> T3["T"]
        T1 --> M["*"]
        T1 --> F2["F"]
        T3 --> F3["F"]
        F3 --> I2["i"]
        F2 --> I3["i"]

• 例题 2：对于文法 $S \to a \mid \wedge \mid (T) \ , \ T \to T, S \mid S$，给出句子 $(((a, a), \wedge, (a)), a)$ 的最左推导和最右推导。

• 解答：

  • 最左推导（每次代换最左侧的非终结符）： $$\begin{aligned} S &\Rightarrow (T) \\ &\Rightarrow (T, S) \\ &\Rightarrow (S, S) \\ &\Rightarrow ((T), S) \\ &\Rightarrow ((T, S), S) \\ &\Rightarrow ((T, S, S), S) \\ &\Rightarrow ((S, S, S), S) \\ &\Rightarrow (((T), S, S), S) \\ &\Rightarrow (((T, S), S, S), S) \\ &\Rightarrow (((S, S), S, S), S) \\ &\Rightarrow (((a, S), S, S), S) \\ &\Rightarrow (((a, a), S, S), S) \\ &\Rightarrow (((a, a), \wedge, S), S) \\ &\Rightarrow (((a, a), \wedge, (T)), S) \\ &\Rightarrow (((a, a), \wedge, (S)), S) \\ &\Rightarrow (((a, a), \wedge, (a)), S) \\ &\Rightarrow (((a, a), \wedge, (a)), a) \end{aligned}$$
  • 最右规范推导（每次代换最右侧的非终结符）： $$\begin{aligned} S &\Rightarrow (T) \\ &\Rightarrow (T, S) \\ &\Rightarrow (T, a) \\ &\Rightarrow (S, a) \\ &\Rightarrow ((T), a) \\ &\Rightarrow ((T, S), a) \\ &\Rightarrow ((T, (T)), a) \\ &\Rightarrow ((T, (S)), a) \\ &\Rightarrow ((T, (a)), a) \\ &\Rightarrow ((T, S, (a)), a) \\ &\Rightarrow ((T, \wedge, (a)), a) \\ &\Rightarrow ((S, \wedge, (a)), a) \\ &\Rightarrow (((T), \wedge, (a)), a) \\ &\Rightarrow (((T, S), \wedge, (a)), a) \\ &\Rightarrow (((T, a), \wedge, (a)), a) \\ &\Rightarrow (((S, a), \wedge, (a)), a) \\ &\Rightarrow (((a, a), \wedge, (a)), a) \end{aligned}$$

---

题型三：句型、短语、直接短语与句柄判定#

如何做：

1. 第一步，画出代换树：根据给定的符号串，从初始大写字母开始代换，画出对应的树，使树的底部叶子节点从左到右连起来刚好是给定的符号串。
2. 第二步，找短语：树里所有有分叉的代号（即大写字母）都是一个“子树根”。每一个子树根往下看，把从它身上分叉出去的所有底部叶子节点（不管是大写字母还是具体符号）从左到右串成一个子串，这个子串就是该句子的一个短语。
3. 第三步，找直接短语：寻找那些“一步就生成叶子”的大写字母（即它的分叉下面全部是树底部的叶子，没有更深的分叉了）。这些一步生成出来的子串就是直接短语。
4. 第四步，找句柄：在找出来的所有直接短语里，看哪个位置最靠左边，最左侧的那一个直接短语就是句柄。

• 题目：已知规则如下，证明 $E + T * F$ 是它的一个符号串，并指出所有短语、直接短语与句柄。 $E \to E + T \mid T \ , \ T \to T * F \mid F \ , \ F \to (E) \mid i$

• 解答：

  1. 证明是符号串：存在推导 $E \Rightarrow E + T \Rightarrow E + T * F$，故它是由初始字母推导出来的合法符号串。
  2. 画出代换树：

     graph TD
         E1["E"] --> E2["E"]
         E1 --> P["+"]
         E1 --> T1["T"]
         T1 --> T2["T"]
         T1 --> M["*"]
         T1 --> F["F"]

  3. 分析各分叉代号生成的底部叶子（找短语）：
     • 以 $T1$ 为根的子树，底部的分叉叶子是 $T$、$*$ 和 $F$，所以 $T * F$ 是短语。
     • 以 $E1$ 为根的子树（整棵树），底部的分叉叶子是 $E$、$+$、$T$、$*$ 和 $F$，所以 $E + T * F$ 是短语。
  4. 找直接短语：
     • 观察树中，只有 $T1$ 这个节点是一步分叉直接产生了叶子节点 $T$, $*$, $F$，它没有更深的分支。
     • 所以，直接短语只有 $T * F$。
  5. 确定句柄：
     • 直接短语中，最左边的就是 $T * F$。
     • 句柄是 $T * F$。

• 例题 2：已知文法 $G$ 为： $T \to t \mid \varepsilon \mid (F) \ , \ F \to T + F \mid T$ 给出句型 $((t)+T)$ 的所有短语、直接短语与句柄。

• 解答：

  1. 最右推导过程： $T \Rightarrow (F) \Rightarrow (T+F) \Rightarrow (T+T) \Rightarrow ((F)+T) \Rightarrow ((T)+T) \Rightarrow ((t)+T)$
  2. 画出语法树：

     graph TD
         T1["T"] --> LP1["("]
         T1 --> F1["F"]
         T1 --> RP1[")"]
         F1 --> T2["T"]
         F1 --> P["+"]
         F1 --> F2["F"]
         F2 --> T3["T (叶)"]
         T2 --> LP2["("]
         T2 --> F3["F"]
         T2 --> RP2[")"]
         F3 --> T4["T"]
         T4 --> t["t"]

     (注意：右侧的非终结符 $T$ 未展开，作为叶子节点直接出现在句型中)
  3. 寻找短语： 根据语法树，找每一个有子树的非终结符节点，其所有叶子子节点组合成的符号串为短语：
     • 以 $T_4$ 为根的子树，叶节点为 t，故 $t$ 是短语。
     • 以 $F_3$ 为根的子树，叶节点为 $T_4$（推导为 t），故 $t$ 是短语。
     • 以 $T_2$ 为根的子树，叶节点为 (, $F_3$（推导为 t）, )，故 $(t)$ 是短语。
     • 以 $T_3$ 为根的子树，叶节点为 $T$ 本身，故 $T$ 是短语。
     • 以 $F_2$ 为根的子树，叶节点为 $T_3$（即 $T$），故 $T$ 是短语。
     • 以 $F_1$ 为根的子树，叶节点为 $T_2, +, F_2$，推导为 $(t)+T$，故 $(t)+T$ 是短语。
     • 以 $T_1$（根节点）为根的子树，叶节点为所有，即 $((t)+T)$，故 $((t)+T)$ 是短语。 去重后，短语集合为：$\{ t, T, (t), (t)+T, ((t)+T) \}$。
  4. 寻找直接短语： 找出高度为 2 的子树（即一步推导就全变成叶节点的非终结符）：
     • $T_4 \to t$ 是一步推导，所以 $t$ 是直接短语。
     • $F_2 \to T$ 是一步推导（因为 $T_3$ 作为叶子节点不再展开），所以 $T$ 是直接短语。 直接短语集合为：$\{ t, T \}$。
  5. 确定句柄： 句柄是最左边的直接短语。在句型 $((t)+T)$ 中，直接短语 $t$ 的位置比 $T$ 更靠左，因此句柄是 $t$。

---

题型四：文法二义性证明#

如何做：

1. 二义性的含义：一个句子用同一套规则，可以画出两棵不同形状的树（或者写出两个不同的最左代换过程）。
2. 证明步骤：
   • 挑一个尽可能简单的例子句子，比如带有连加或加乘混合的句子（如 $i + i * i$）。
   • 第一种画法：按照“先加后乘”的代换逻辑画一棵树。
   • 第二种画法：按照“先乘后加”的代换逻辑画另一棵树。
   • 展示这两个推导并说明它们不同，即可完成证明。

• 题目：证明规则 $E \to E + E \mid E * E \mid (E) \mid i$ 是二义的。

• 解答：

  1. 选择测试句子：$i + i * i$。
  2. 我们可以写出两种不同的最左代换过程：
     • 推导方式 1（先算乘法）： $E \Rightarrow E + E \Rightarrow i + E \Rightarrow i + E * E \Rightarrow i + i * E \Rightarrow i + i * i$
     • 推导方式 2（先算加法）： $E \Rightarrow E * E \Rightarrow E + E * E \Rightarrow i + E * E \Rightarrow i + i * E \Rightarrow i + i * i$
  3. 推导方式 1 对应的树中，乘法位于加法的下方（乘法优先）；推导方式 2 对应的树中，加法位于乘法的下方（加法优先）。同一个句子可以生成两棵不同的语法树，因此该规则是二义的。

• 例题 2：证明文法 $S \to iSeS \mid iS \mid i$（经典的 Dangling-Else 悬挂else文法）是二义的。

• 解答：

  1. 选择测试句子：$i i i e i$ （代表 if C1 then if C2 then S1 else S2）。
  2. 我们给出该句子对应的两个不同的最左推导：
     • 推导方式 1（else 与最外层的第一个 if 结合）： $$\begin{aligned} S &\Rightarrow i S e S \\ &\Rightarrow i i S e S \\ &\Rightarrow i i i e S \\ &\Rightarrow i i i e i \end{aligned}$$
     • 推导方式 2（else 与内层的第二个 if 结合）： $$\begin{aligned} S &\Rightarrow i S \\ &\Rightarrow i i S e S \\ &\Rightarrow i i i e S \\ &\Rightarrow i i i e i \end{aligned}$$
  3. 由于同一个句子 $i i i e i$ 存在两个不同的最左推导（可画出两棵不同结构的语法分析树），因此该文法是二义的。

---

模块二：词法分析与正规式#

题型五：正规式的代数性质与等价性证明#

如何做：

1. 星号 $*$：代表“可以重复 0 次或任意多次”。
2. 括号和竖线 $\mid$：代表选择（或者）。
3. 等价化简公式：
   • $A(B \mid C) = AB \mid AC$ （分配律，把前面的 $A$ 分别乘进去）
   • $(A^*)^* = A^*$ （多次重复还是任意次重复）
   • $A^* = \varepsilon \mid A A^*$ （任意次重复等于“什么都没有”或者“先写一个 $A$，后面再接任意次重复”）
4. Arden代换公式：如果你得到了一个关于大写字母 $X$ 的等式，形状像 $X = A X \mid B$（表示 $X$ 等于 $A$ 后面接 $X$，或者等于 $B$），那么 $X$ 的唯一解就是 $X = A^* B$（表示先重复任意次 $A$，最后接上 $B$）。

• 题目：利用代数规律证明方程 $A = b \mid aA$ 的唯一解是 $A = a^*b$。

• 解答：

  1. 我们把 $A = aA \mid b$ 顺着定义逐步展开代入： $$\begin{aligned} A &= aA \mid b \\ &= a(aA \mid b) \mid b = aaA \mid ab \mid b \\ &= aaaA \mid aab \mid ab \mid b \\ &= a^k A \mid (a^{k-1}b \mid \dots \mid ab \mid b) \end{aligned}$$
  2. 当我们无限展开下去，前面的 $a$ 可以重复任意多次（记作 $a^*$），最后接上尾巴 $b$。
  3. 根据 Arden 引理，方程 $X = A X \mid B$ 的唯一解就是 $X = A^* B$。这里令 $X = A, A = a, B = b$，直接得出唯一解为 $A = a^* b$。

• 例题 2：利用正规式的恒等式规律，证明恒等式 $(AB)^*A = A(BA)^*$ 成立。

• 解答：

  1. 方法一：展开法（直观理解）：
     • 左边 $(AB)^*A$ 展开： $(AB)^*A = (\varepsilon \mid AB \mid ABAB \mid ABABAB \mid \dots)A = A \mid ABA \mid ABABA \mid ABABABA \mid \dots$
     • 右边 $A(BA)^*$ 展开： $A(BA)^* = A(\varepsilon \mid BA \mid BABA \mid BABABA \mid \dots) = A \mid ABA \mid ABABA \mid ABABABA \mid \dots$
     • 展开后的集合形式完全一致，故等式成立。
  2. 方法二：代数推导法（利用恒等律 $U^* = \varepsilon \mid U U^*$ 或 $U^* = \varepsilon \mid U^* U$）：
     • 利用分配律及展开性质： $$\begin{aligned} (AB)^*A &= (\varepsilon \mid AB(AB)^*)A \\ &= A \mid AB(AB)^*A \end{aligned}$$ 设 $X = (AB)^*A$，那么上式可以写为 $X = A \mid AB X$。
     • 根据 Arden 引理（若 $X = U X \mid V$，则其唯一解为 $X = U^* V$）：
       • 这里令 $U = AB$，$V = A$。因此该方程的唯一解是 $X = (AB)^*A$。
     • 另一方面，我们将右边 $Y = A(BA)^*$ 带入上述方程检验： $$\begin{aligned} A \mid AB Y &= A \mid AB(A(BA)^*) \\ &= A \mid A(BA)(BA)^* \\ &= A(\varepsilon \mid (BA)(BA)^*) \\ &= A(BA)^* = Y \end{aligned}$$ 发现 $Y = A(BA)^*$ 也是该方程的解。
     • 由于解是唯一的，所以必有 $X = Y$，即 $(AB)^*A = A(BA)^*$。得证。

---

题型六：构造特定语言的正规式#

如何做：

1. 明确要匹配的具体字符。例如二进制只有 0 和 1。
2. 任意个 0 和 1 的组合写成：$(0 \mid 1)^*$。
3. 根据限制进行拼接：
   • 如果说“以 01 结尾”，说明前面是任意组合，最后强制加 01，写成：$(0 \mid 1)^* 01$。
   • 如果说“必须包含 01”，说明 01 前面和后面都可以是任意组合，写成：$(0 \mid 1)^* 01 (0 \mid 1)^*$。

• 题目：给出能被 $5$ 整除的十进制正整数的正规式（不含前导零）。

• 解答：

  1. 一个十进制正整数能被 5 整除，它的个位数只能是 0 或 5。
  2. 如果是个位数，只有 5 这一种可能（0 不是正整数，若包含 0 可单独列出）。
  3. 如果是多位数，首位数字不能是 0，只能是 1 到 9 的其中一个，记为：$(1 \mid 2 \mid \dots \mid 9)$。
  4. 中间的位数可以是任意数字 0 到 9 的组合，记为：$(0 \mid 1 \mid \dots \mid 9)^*$。
  5. 多位数的个位数必须是 0 或 5，记为：$(0 \mid 5)$。
  6. 组合起来，“个位数”或者“多位数”表示为： $5 \mid (1 \mid 2 \mid \dots \mid 9)(0 \mid 1 \mid \dots \mid 9)^*(0 \mid 5)$

• 例题 2：给出二进制数中包含奇数个 1 或奇数个 0 的二进制数串的正规式。

• 解答：

  1. 第一步：构造包含奇数个 1 的正规式：
     • 包含偶数个 1 的正规式（中间可以有任意个 0）：$(0 \mid 10^*1)^*$.
     • 奇数个 1，相当于偶数个 1 后面再跟一个 1，以及任意个 0： $R_1 = (0 \mid 10^*1)^*10^*$
  2. 第二步：同理构造包含奇数个 0 的正规式：
     • 偶数个 0 的正规式：$(1 \mid 01^*0)^*$.
     • 奇数个 0，相当于偶数个 0 后面再跟一个 0，以及任意个 1： $R_2 = (1 \mid 01^*0)^*01^*$
  3. 第三步：求“或”关系（并集）：
     • 将两者用选择符 | 连接即可： $R = (0 \mid 10^*1)^*10^* \mid (1 \mid 01^*0)^*01^*$

---

题型七：NFA 确定化与 DFA 最小化#

如何做：

1. 确定化（合并含空箭头的状态）：
   • 顺着“空字箭头”（无标记的箭头，通常用 $\varepsilon$ 表示）一路走到底，能走到的所有状态合并起来，称为一个“状态包”。
   • 从初始状态开始，先把初始状态和它走空箭头能走到的状态打包（比如 $\{0\}$ 走空箭头能到 $\{0, 1\}$，打包为 $A$）。
   • 对每个状态包，看它整体读入字符 $a$ 后能跳到哪些状态，再加上这些新状态能走空箭头到达的状态，打包成新包 $B$。
   • 重复这个过程，列出转移表。
2. 最小化（化简状态）：
   • 把所有状态分成两大家族：第一家族是“双圈接受状态”，第二家族是“普通状态”。
   • 拿出一个家族，看里面的状态在读入字符 $a$ 后，跳去的状态是否都在同一个家族里。如果在读入 $a$ 时，有的跳去第一家族，有的跳去第二家族，说明它们“心不齐”，必须把它们分裂成不同的小组。
   • 重复这个分裂过程，直到每个小组内的状态读入相同字符后，去往的都是同一个小组。最后，把同一个小组内的状态合并成一个状态。

• 例题 1 (NFA 确定化 —— 子集构造法)：对如下含有空弧的 NFA 进行确定化（DFA化）：
  • 状态集：$\{0, 1, 2, 3\}$，初态为 $0$，终态（接受状态）为 $3$。
  • 转移弧关系：
    • $\delta(0, a) = \{0, 1\}$，$\delta(0, b) = \{0\}$
    • $\delta(1, \varepsilon) = \{2\}$ （空转换）
    • $\delta(2, b) = \{3\}$
  • 其 NFA 状态图如下：

    stateDiagram-v2
        [*] --> 0
        0 --> 0 : a, b
        0 --> 1 : a
        1 --> 2 : ε
        2 --> 3 : b
        classDef accept fill:#f9f,stroke:#333,stroke-width:2px;
        class 3 accept;

• 解答：

  1. 基础概念：

     • $\varepsilon$-closure($S$)：从状态集 $S$ 中的任何状态出发，仅通过空转换（$\varepsilon$-弧）所能到达的所有状态的集合（包含 $S$ 本身）。
     • $\text{move}(S, x)$：从状态集 $S$ 中的任何状态出发，通过输入字符 $x$ 所能到达的所有状态的集合。

  2. 逐步计算子集转移：

     • 初态子集 $A$： $A = \varepsilon\text{-closure}(\{0\}) = \{0\}$ (由于 $3 \notin A$，非接受状态)
     • 计算 $A$ 遇到 $a$ 的转移：
       • $\text{move}(A, a) = \delta(0, a) = \{0, 1\}$
       • $B = \varepsilon\text{-closure}(\{0, 1\}) = \varepsilon\text{-closure}(\{0\}) \cup \varepsilon\text{-closure}(\{1\}) = \{0\} \cup \{1, 2\} = \{0, 1, 2\}$
       • 得到新子集 $B = \{0, 1, 2\}$
     • 计算 $A$ 遇到 $b$ 的转移：
       • $\text{move}(A, b) = \delta(0, b) = \{0\}$
       • $\varepsilon\text{-closure}(\{0\}) = \{0\} = A$
     • 计算子集 $B = \{0, 1, 2\}$ 遇到 $a$ 的转移：
       • $\text{move}(B, a) = \delta(0, a) \cup \delta(1, a) \cup \delta(2, a) = \{0, 1\} \cup \emptyset \cup \emptyset = \{0, 1\}$
       • $\varepsilon\text{-closure}(\{0, 1\}) = \{0, 1, 2\} = B$
     • 计算子集 $B = \{0, 1, 2\}$ 遇到 $b$ 的转移：
       • $\text{move}(B, b) = \delta(0, b) \cup \delta(1, b) \cup \delta(2, b) = \{0\} \cup \emptyset \cup \{3\} = \{0, 3\}$
       • $C = \varepsilon\text{-closure}(\{0, 3\}) = \varepsilon\text{-closure}(\{0\}) \cup \varepsilon\text{-closure}(\{3\}) = \{0, 3\}$
       • 得到新子集 $C = \{0, 3\}$ (由于包含终态 $3$，为接受状态)
     • 计算子集 $C = \{0, 3\}$ 遇到 $a$ 的转移：
       • $\text{move}(C, a) = \delta(0, a) \cup \delta(3, a) = \{0, 1\} \cup \emptyset = \{0, 1\}$
       • $\varepsilon\text{-closure}(\{0, 1\}) = \{0, 1, 2\} = B$
     • 计算子集 $C = \{0, 3\}$ 遇到 $b$ 的转移：
       • $\text{move}(C, b) = \delta(0, b) \cup \delta(3, b) = \{0\} \cup \emptyset = \{0\}$
       • $\varepsilon\text{-closure}(\{0\}) = \{0\} = A$
     • 子集已经完全闭合，不再产生新子集。

  3. 整理得到 DFA 状态转移表：

     DFA 状态	对应 NFA 状态子集	输入 $a$	输入 $b$	是否为接受状态
     $A$ (初态)	$\{0\}$	$B$	$A$	否
     $B$	$\{0, 1, 2\}$	$B$	$C$	否
     $C$ (终态)	$\{0, 3\}$	$B$	$A$	是

  4. 画出确定化后的 DFA 状态图：

     stateDiagram-v2
         [*] --> A
         A --> B : a
         A --> A : b
         B --> B : a
         B --> C : b
         C --> B : a
         C --> A : b
         classDef accept fill:#f9f,stroke:#333,stroke-width:2px;
         class C accept;

---

• 例题 2 (DFA 最小化 —— 分割法)：将如下 DFA 最小化：
  • 接受状态：$0, 1$；非接受状态：$2, 3, 4, 5$。
  • 转移关系：状态 0 读 $a \to 1$, 读 $b \to 2$；状态 1 读 $a \to 1$, 读 $b \to 4$；状态 2 读 $a \to 1$, 读 $b \to 3$；状态 3 读 $a \to 3$, 读 $b \to 2$；状态 4 读 $a \to 0$, 读 $b \to 5$；状态 5 读 $a \to 5$, 读 $b \to 4$。
• 解答：
  1. 第一步：初始划分：
     • 接受状态组：$G_1 = \{0, 1\}$
     • 非接受状态组：$G_2 = \{2, 3, 4, 5\}$
  2. 第二步：测试 $G_1 = \{0, 1\}$ 是否需要拆分：
     • 状态 0 和 1 读入 $a$ 后跳到 $\{1\}$（都在 $G_1$ 内）。
     • 状态 0 读入 $b$ 跳到 2（在 $G_2$ 内），状态 1 读入 $b$ 跳到 4（在 $G_2$ 内）。
     • 它们的行为完全一样（都跳到同组状态），所以 $\{0, 1\}$ 不用拆分，记为状态 $A$。
  3. 第三步：测试 $G_2 = \{2, 3, 4, 5\}$ 是否需要拆分：
     • 读入 $a$ 时：
       • 2 读 $a \to 1 \in G_1$
       • 3 读 $a \to 3 \in G_2$
       • 4 读 $a \to 0 \in G_1$
       • 5 读 $a \to 5 \in G_2$
     • 发现 2 和 4 跳去 $G_1$，而 3 和 5 跳去 $G_2$。所以必须拆分为两组：$G_{2A} = \{2, 4\}$ 和 $G_{2B} = \{3, 5\}$。
  4. 第四步：测试 $\{2, 4\}$ 是否需要拆分：
     • 2 和 4 读 $a$ 都跳去 $G_1$。
     • 2 读 $b \to 3 \in G_{2B}$，4 读 $b \to 5 \in G_{2B}$。
     • 行为一致，不用拆分，记为状态 $B$。
  5. 第五步：测试 $\{3, 5\}$ 是否需要拆分：
     • 3 和 5 读 $a$ 都跳去 $G_{2B}$。
     • 3 读 $b \to 2 \in G_{2A}$，5 读 $b \to 4 \in G_{2A}$。
     • 行为一致，不用拆分，记为状态 $C$。
  6. 合并结论：化简后的 DFA 只有三个状态：$A(0,1)$、$B(2,4)$ 和 $C(3,5)$。

---

模块三：自顶向下语法分析#

题型八：消除左递归与提取左公因子#

如何做：

1. 消除自己推导自己开头的规则（直接左递归）：
   • 如果一条规则长得像：$A \to A\alpha \mid \beta$（大写字母 $A$ 指向的串里，有的又以 $A$ 开头，比如 $A\alpha$；有的不以 $A$ 开头，比如 $\beta$）。这会导致代换时无限循环。
   • 我们引入一个带撇的新字母 $A'$，把规则改成两行：
     • 第一行把不以 $A$ 开头的放在前面，后面强行加上新符号：$A \to \beta A'$。
     • 第二行用新符号去接多出来的尾巴，并在最后加上空符号 $\varepsilon$：$A' \to \alpha A' \mid \varepsilon$。
2. 提取公因子（解决开头重合的问题）：
   • 如果大写字母有几个分支，开头都长得一模一样，例如 $A \to abC \mid abD$。这会导致我们在读到 $ab$ 时不知道该选哪条分支。
   • 我们把相同的开头 $ab$ 提出来，后面接上一个新字母 $A'$：$A \to abA'$。
   • 然后给新字母写一条规则，把后面不同的部分放进去：$A' \to C \mid D$。

• 题目：消除规则 $S \to a \mid \wedge \mid (T) \ , \ T \to T, S \mid S$ 的左递归。

• 解答：

  1. 观察发现，$S$ 的规则没有左递归。
  2. $T$ 的规则中，第一个分支 $T, S$ 是以 $T$ 本身开头的（直接左递归）。其中，$\alpha$ 部分是 , S，非左递归的分支 $\beta$ 是 $S$。
  3. 我们套用公式，引入新符号 $T'$：
     • 第一步，写出不以 $T$ 开头的分支，并接上 $T'$： $T \to S T'$
     • 第二步，让 $T'$ 变出尾巴 , S 并接上 $T'$ 自己，或者变为空： $T' \to , S T' \mid \varepsilon$
  4. 消除左递归后的完整规则为： $$\begin{aligned} S &\to a \mid \wedge \mid (T) \\ T &\to S T' \\ T' &\to , S T' \mid \varepsilon \end{aligned}$$

• 例题 2：考虑文法 $G[S]$： $S \to (L) \mid aS \mid a \ , \ L \to L, S \mid S$ 消去所有的左因子与左递归。

• 解答：

  1. 第一步：提取左公因子（消除回溯）：
     • 观察非终结符 $S$ 的产生式，$S \to aS \mid a$ 具有公共左因子 $a$。
     • 我们把 $a$ 提出来，引入新状态符号 $S'$，将产生式改写为： $$\begin{aligned} S &\to (L) \mid aS' \\ S' &\to S \mid \varepsilon \end{aligned}$$
  2. 第二步：消除直接左递归：
     • 观察非终结符 $L$ 的产生式，$L \to L, S \mid S$ 含有直接左递归。其中 $\alpha$ 是 , S，$\beta$ 是 $S$。
     • 套用消除左递归公式，引入新非终结符 $L'$，改写为： $$\begin{aligned} L &\to S L' \\ L' &\to , S L' \mid \varepsilon \end{aligned}$$
  3. 第三步：合并得到最终文法： $$\begin{aligned} S &\to (L) \mid aS' \\ S' &\to S \mid \varepsilon \\ L &\to S L' \\ L' &\to , S L' \mid \varepsilon \end{aligned}$$

---

题型九：编写递归下降分析程序#

如何做：

1. 一个代号写一个函数：为规则中的每个大写字母写一个同名的处理函数/过程（比如 procedure S()）。
2. 看字做选择：在过程内部，使用 if 条件去判断当前读到的字符（用变量 lookahead 表示）。如果当前字符符合某条规则的开头，就进入那个分支。
3. 遇到符号就匹配，遇到代号就调用：
   • 如果规则右边是具体符号（如小写字母、括号等），我们就写 match('该符号')。
   • 如果规则右边是大写字母（代号），我们就直接写这个大写字母的同名函数调用，例如 T()。
4. 匹配函数 match 的作用：核对当前读到的字符是否就是我们期望的字符。如果是，就读入下一个字符；如果不是，就说明句子写错了，报错退出。

• 题目：对于产生式 $S \to a \mid \wedge \mid (T), T \to S T', T' \to , S T' \mid \varepsilon$，写出递归下降分析程序。

• 解答：

  // 匹配并读取下一个字符的辅助函数
  procedure match(t: char);
  begin
      if lookahead = t then
          lookahead := nextToken()
      else
          error();
  end;
  
  // 大写字母 S 的处理函数
  procedure S();
  begin
      if lookahead = 'a' then
          match('a')
      else if lookahead = '^' then
          match('^')
      else if lookahead = '(' then
          begin
              match('(');
              T();
              match(')');
          end
      else
          error();
  end;
  
  // 大写字母 T 的处理函数
  procedure T();
  begin
      S();
      Tprime();
  end;
  
  // 大写字母 T' 的处理函数
  procedure Tprime();
  begin
      if lookahead = ',' then
          begin
              match(',');
              S();
              Tprime();
          end
      // 如果不是 ','，因为 T' 可以变为空（epsilon），
      // 只要当前字符是随后的合法字符（如右括号或结束符），就直接返回，什么都不用做
      else if (lookahead = ')') or (lookahead = '$') then
          exit
      else
          error();
  end;

• 例题 2：已知文法如下，写出其递归下降分析程序：

  $$\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}$$

• 解答： 为每个非终结符（$E, E', T, T', F, F', P$）分别编写分析过程，采用 Pascal/类 Pascal 伪代码实现：

  // 辅助匹配过程
  procedure match(t: char);
  begin
      if lookahead = t then
          lookahead := nextToken()
      else
          error();
  end;
  
  procedure E();
  begin
      T();
      Eprime();
  end;
  
  procedure Eprime();
  begin
      if lookahead = '+' then
          begin
              match('+');
              E();
          end
      // 当面临 FIRST(E') 以外的符号时，若该符号属于 FOLLOW(E') = { ) , $ }，可选择 epsilon 产生式归约并返回
      else if (lookahead = ')') or (lookahead = '$') then
          exit
      else
          error();
  end;
  
  procedure T();
  begin
      F();
      Tprime();
  end;
  
  procedure Tprime();
  begin
      // T' -> T | \varepsilon
      // FIRST(T) = { ( , a , b , ^ }
      if (lookahead = '(') or (lookahead = 'a') or (lookahead = 'b') or (lookahead = '^') then
          T()
      // FOLLOW(T') = FOLLOW(T) = { + , ) , $ }
      else if (lookahead = '+') or (lookahead = ')') or (lookahead = '$') then
          exit
      else
          error();
  end;
  
  procedure F();
  begin
      P();
      Fprime();
  end;
  
  procedure Fprime();
  begin
      if lookahead = '*' then
          begin
              match('*');
              Fprime();
          end
      // FOLLOW(F') = FOLLOW(F) = { ( , a , b , ^ , + , ) , $ }
      else if (lookahead = '(') or (lookahead = 'a') or (lookahead = 'b') or (lookahead = '^') or (lookahead = '+') or (lookahead = ')') or (lookahead = '$') then
          exit
      else
          error();
  end;
  
  procedure P();
  begin
      if lookahead = '(' then
          begin
              match('(');
              E();
              match(')');
          end
      else if lookahead = 'a' then
          match('a')
      else if lookahead = 'b' then
          match('b')
      else if lookahead = '^' then
          match('^')
      else
          error();
  end;

---

题型十：FIRST/FOLLOW集计算与预测分析表构造#

如何做：

1. FIRST集（首字符集合）：对一个大写字母，看它顺着规则代换下去，第一个可能变出来的具体字符有哪些。
   • 例如 $A \to aB \mid \varepsilon$，那么 $A$ 的首字符集合就是 $\{ a, \varepsilon \}$。
   • 如果 $A \to B C$，就要看 $B$ 的首字符。如果 $B$ 能变为空，还要把 $C$ 的首字符也算进来。
2. FOLLOW集（后跟字符集合）：在所有规则的右边寻找某个大写字母（比如 $A$），看哪些具体字符有可能紧跟在 $A$ 的后面出现。
   • 初始的大写字母（如 $S$）后面默认能放结束标记符 $$$。
   • 如果有规则 $S \to a A b$，那么 $b$ 就在 $A$ 的后面，把 $b$ 加入 $A$ 的后跟集。
   • 如果有规则 $S \to a A$ （后面没东西了），或者后面的大写字母能变为空，那么 $S$ 的后跟字符也都可以跟在 $A$ 的后面，把 $S$ 的后跟集并入 $A$ 的后跟集。
3. 填表规则：
   • 表的行写大写字母，列写所有具体字符。
   • 看一个大写字母的分支规则，它开头的具体字符有哪些，就把这条规则填到大写字母与那些字符对应的格子里。
   • 如果该规则能变为空（$\varepsilon$），就把这条变为空的规则填到该大写字母的后跟字符（FOLLOW集里所有字符）对应的格子里。

• 题目：对以下规则，计算每个代号的 FIRST 和 FOLLOW 集合，并构造预测分析表： $S \to (L) \mid aS' \ , \ S' \to S \mid \varepsilon \ , \ L \to S L' \ , \ L' \to , S L' \mid \varepsilon$

• 解答：

  1. 计算 FIRST 集合：
     • $S$ 只能由第一个分支产生 ( 或第二个分支产生 a，所以：$\text{FIRST}(S) = \{ (, a \}$
     • $S'$ 可以变成 $S$（即有 (, a），或者变为空 $\varepsilon$，所以：$\text{FIRST}(S') = \{ (, a, \varepsilon \}$
     • $L$ 变成 $S L'$，以 $S$ 开头，所以：$\text{FIRST}(L) = \text{FIRST}(S) = \{ (, a \}$
     • $L'$ 可以变成 ,，或者变为空 $\varepsilon$，所以：$\text{FIRST}(L') = \{ ,, \varepsilon \}$
  2. 计算 FOLLOW 集合：
     • $S$ 是起始代号，先把 \$$ 加入 \text{FOLLOW}(S)$。
     • 观察所有规则右侧含 $S$ 的地方：
       • 在 $S' \to S$ 中，右侧最末尾是 $S$，故将 $\text{FOLLOW}(S')$ 放入 $\text{FOLLOW}(S)$。
       • 在 $L \to S L'$ 中，后面紧跟 $L'$，故将 $\text{FIRST}(L') \setminus \{\varepsilon\}$（即 ,）放入 $\text{FOLLOW}(S)$。因为 $L'$ 可变为空，所以要把 $\text{FOLLOW}(L)$ 也放入。
       • 在 $L' \to , S L'$ 中，同理。
     • 综合计算后，各集合为：
       • \text{FOLLOW}(S) = \{ \, ), , }$ （包括结束符、右括号、逗号）
       • \text{FOLLOW}(S') = \text{FOLLOW}(S) = \{ \, ), , }$
       • $\text{FOLLOW}(L) = \{ ) \}$ （在 $S \to (L)$ 中，$L$ 后面是右括号）
       • $\text{FOLLOW}(L') = \text{FOLLOW}(L) = \{ ) \}$
  3. 构造预测分析表：

     代号	a	(	)	,	$
     $S$	$S \to aS'$	$S \to (L)$
     $S'$	$S' \to S$	$S' \to S$	$S' \to \varepsilon$	$S' \to \varepsilon$	$S' \to \varepsilon$
     $L$	$L \to S L'$	$L \to S L'$
     $L'$			$L' \to \varepsilon$	$L' \to , S L'$

• 例题 2：考虑如下改写后的表达式文法：

  $$\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{FIRST}$ 与 $\text{FOLLOW}$。
  2. 构造 $\text{LL}(1)$ 预测分析表。
  3. 给出输入句子 id - - id ( ( id ) ) 对应的详细移进与预测分析栈步骤表（以 # 作为栈底）。

• 解答：

  1. 计算 FIRST 和 FOLLOW 集合：

     • $\text{FIRST}(\textit{Expr}) = \{ -, (, \textit{id} \}$
     • $\text{FIRST}(\textit{ExprTail}) = \{ -, \varepsilon \}$
     • $\text{FIRST}(\textit{Var}) = \{ \textit{id} \}$
     • $\text{FIRST}(\textit{VarTail}) = \{ (, \varepsilon \}$
     • \text{FOLLOW}(\textit{Expr}) = \{ \, ) }$
     • \text{FOLLOW}(\textit{ExprTail}) = \text{FOLLOW}(\textit{Expr}) = \{ \, ) }$
     • \text{FOLLOW}(\textit{Var}) = (\text{FIRST}(\textit{ExprTail}) \setminus \{\varepsilon\}) \cup \text{FOLLOW}(\textit{Expr}) = \{ -, \, ) }$
     • \text{FOLLOW}(\textit{VarTail}) = \text{FOLLOW}(\textit{Var}) = \{ -, \, ) }$

  2. 构造预测分析表：

     非终结符	id	-	(	)	$
     $\textit{Expr}$	$\textit{Expr} \to \textit{Var} \ \textit{ExprTail}$	$\textit{Expr} \to -\textit{Expr}$	$\textit{Expr} \to (\textit{Expr})$
     $\textit{ExprTail}$		$\textit{ExprTail} \to -\textit{Expr}$		$\textit{ExprTail} \to \varepsilon$	$\textit{ExprTail} \to \varepsilon$
     $\textit{Var}$	$\textit{Var} \to \textit{id} \ \textit{VarTail}$
     $\textit{VarTail}$		$\textit{VarTail} \to \varepsilon$	$\textit{VarTail} \to (\textit{Expr})$	$\textit{VarTail} \to \varepsilon$	$\textit{VarTail} \to \varepsilon$

  3. 句子 id - - id ( ( id ) ) 的预测分析控制步骤表（使用分析栈与输入串配对，#为栈底）：

     步骤	符号栈 (从右至左压栈)	剩余输入串	所用产生式 / 动作
     1	# $\textit{Expr}$	id - - id ( ( id ) ) #	$\textit{Expr} \to \textit{Var} \ \textit{ExprTail}$
     2	# $\textit{ExprTail}$ $\textit{Var}$	id - - id ( ( id ) ) #	$\textit{Var} \to \textit{id} \ \textit{VarTail}$
     3	# $\textit{ExprTail}$ $\textit{VarTail}$ id	id - - id ( ( id ) ) #	匹配终结符 id (移进并消耗输入)
     4	# $\textit{ExprTail}$ $\textit{VarTail}$	- - id ( ( id ) ) #	$\textit{VarTail} \to \varepsilon$ (因 - $\in$ $\text{FOLLOW}(\textit{VarTail})$)
     5	# $\textit{ExprTail}$	- - id ( ( id ) ) #	$\textit{ExprTail} \to -\textit{Expr}$
     6	# $\textit{Expr}$ -	- - id ( ( id ) ) #	匹配终结符 - (移进)
     7	# $\textit{Expr}$	- id ( ( id ) ) #	$\textit{Expr} \to -\textit{Expr}$
     8	# $\textit{Expr}$ -	- id ( ( id ) ) #	匹配终结符 - (移进)
     9	# $\textit{Expr}$	id ( ( id ) ) #	$\textit{Expr} \to \textit{Var} \ \textit{ExprTail}$
     10	# $\textit{ExprTail}$ $\textit{Var}$	id ( ( id ) ) #	$\textit{Var} \to \textit{id} \ \textit{VarTail}$
     11	# $\textit{ExprTail}$ $\textit{VarTail}$ id	id ( ( id ) ) #	匹配终结符 id (移进)
     12	# $\textit{ExprTail}$ $\textit{VarTail}$	( ( id ) ) #	$\textit{VarTail} \to (\textit{Expr})$ (因 ( $\in$ $\text{FIRST}((\textit{Expr}))$)
     13	# $\textit{ExprTail}$ ) $\textit{Expr}$ (	( ( id ) ) #	匹配终结符 ( (移进)
     14	# $\textit{ExprTail}$ ) $\textit{Expr}$	( id ) ) #	$\textit{Expr} \to (\textit{Expr})$
     15	# $\textit{ExprTail}$ ) ) $\textit{Expr}$ (	( id ) ) #	匹配终结符 ( (移进)
     16	# $\textit{ExprTail}$ ) ) $\textit{Expr}$	id ) ) #	$\textit{Expr} \to \textit{Var} \ \textit{ExprTail}$
     17	# $\textit{ExprTail}$ ) ) $\textit{ExprTail}$ $\textit{Var}$	id ) ) #	$\textit{Var} \to \textit{id} \ \textit{VarTail}$
     18	# $\textit{ExprTail}$ ) ) $\textit{ExprTail}$ $\textit{VarTail}$ id	id ) ) #	匹配终结符 id (移进)
     19	# $\textit{ExprTail}$ ) ) $\textit{ExprTail}$ $\textit{VarTail}$	) ) #	$\textit{VarTail} \to \varepsilon$ (因 ) $\in$ $\text{FOLLOW}(\textit{VarTail})$)
     20	# $\textit{ExprTail}$ ) ) $\textit{ExprTail}$	) ) #	$\textit{ExprTail} \to \varepsilon$ (因 ) $\in$ $\text{FOLLOW}(\textit{ExprTail})$)
     21	# $\textit{ExprTail}$ ) )	) ) #	匹配终结符 ) (移进)
     22	# $\textit{ExprTail}$ )	) #	匹配终结符 ) (移进)
     23	# $\textit{ExprTail}$	#	$\textit{ExprTail} \to \varepsilon$ (因 # $\in$ $\text{FOLLOW}(\textit{ExprTail})$)
     24	#	#	分析成功结束，句子被接受

---

模块四：自底向上语法分析#

题型十一：项目集规范族、DFA 与分析表构造 (LR 家族)#

如何做：

1. 初始规则拓广：在所有规则的最前面，强行加一条规则 $S' \to S$（把初始大写字母用一个带撇的字母包起来），作为整套规则的新起点。
2. 加圆点表示进度：在规则右侧的字符间塞入一个圆点 .，点在哪就表示我们读到了哪里。比如 $E \to a \cdot A$ 表示我们刚刚读完了具体符号 $a$，接下来准备读代号 $A$。
3. 求状态的扩展（闭包）：
   • 如果圆点后面紧跟着一个大写字母，比如 $A$，那就要把所有以 $A$ 开头的规则全部写进这个状态里。
   • 并且，写出来的这些新规则，它们的圆点必须放在最左边（例如 $A \to \cdot cd$）。
4. 状态转移：
   • 看圆点后面紧贴的是什么符号（不管大写还是小写）。把圆点往右移过这个符号，得到一个新规则，作为新状态的起点，再重复第 3 步扩展它。
5. 填分析驱动表：
   • 如果圆点在最右边（如 $A \to cd\cdot$），说明这一支读完了，可以进行“归约”（即把读到的具体符号往回合并成代号 $A$），在表里填入 r加上规则编号。
   • 如果圆点后面是具体符号（如小写字母 $x$），且移位后去了状态 $j$，就在表里填 s j。
   • 如果圆点后面是大写字母（如 $A$），且移位后去了状态 $j$，就在跳转表（GOTO栏）里填数字 j。

• 题目：考虑规则 $S' \to E, E \to aA, A \to cA \mid d$，构造 LR(0) 项目集规范族及识别活前缀的 DFA，并构造 LR(0) 分析表。

• 解答：

  1. 编号规则：(1) $E \to aA$, (2) $A \to cA$, (3) $A \to d$。
  2. 构造状态集（圆点移位与闭包扩展）：
     • 状态 0（初始）： 先放起点的项目：$S' \to \cdot E$。因为点后面是 $E$，所以引入以 $E$ 开头的规则，点放最左：$E \to \cdot aA$。 即状态 0 为：$\{ S' \to \cdot E, E \to \cdot aA \}$。
     • 状态 1（状态 0 读 $E$）：点往右移： $\{ S' \to E \cdot \}$。 (这是接受状态 acc)
     • 状态 2（状态 0 读 $a$）：点往右移： $E \to a \cdot A$。因为点后面是大写字母 $A$，所以引入 $A$ 开头的规则： $A \to \cdot cA$, $A \to \cdot d$。 即状态 2 为：$\{ E \to a \cdot A, A \to \cdot cA, A \to \cdot d \}$。
     • 状态 3（状态 2 读 $A$）：点往右移： $\{ E \to aA \cdot \}$。 (读完了，按第 (1) 条规则归约)
     • 状态 4（状态 2 读 $c$）：点往右移： $A \to c \cdot A$。点后面是 $A$，引入 $A$ 的规则： $A \to \cdot cA$, $A \to \cdot d$。 即状态 4 为：$\{ A \to c \cdot A, A \to \cdot cA, A \to \cdot d \}$。
     • 状态 5（状态 2 读 $d$）：点往右移： $\{ A \to d \cdot \}$。 (读完了，按第 (3) 条规则归约)
     • 状态 6（状态 4 读 $A$）：点往右移： $\{ A \to cA \cdot \}$。 (读完了，按第 (2) 条规则归约)
  3. LR(0) 分析驱动表：

     状态	a	c	d	$	E	A
     0	s2				1
     1				acc
     2		s4	s5			3
     3	r1	r1	r1	r1
     4		s4	s5			6
     5	r3	r3	r3	r3
     6	r2	r2	r2	r2

• 题目 2 (SLR(1) 证明与表构造)：证明文法 $G$：$S \to Ab \mid aAc \ , \ A \to a$ 不是 $\text{LR}(0)$ 文法而是 $\text{SLR}(1)$ 文法，并给出 $\text{SLR}(1)$ 分析表。

• 解答：

  1. 第一步：拓广文法并编号：

     • (0) $S' \to S$
     • (1) $S \to Ab$
     • (2) $S \to aAc$
     • (3) $A \to a$

  2. 第二步：构造带圆点的项目状态集：

     • 状态 0： $S' \to \cdot S$ (点后面是 $S$，引出 $S$ 的规则) $S \to \cdot Ab$, $S \to \cdot aAc$ (点后面是大写字母 $A$ 和小写字母 $a$) $A \to \cdot a$ (引入以 $A$ 开头的规则) 即状态 0 为：$\{ S' \to \cdot S, S \to \cdot Ab, S \to \cdot aAc, A \to \cdot a \}$
     • 状态 1 (状态 0 读 $S$)：$\{ S' \to S \cdot \}$ (接受态)
     • 状态 2 (状态 0 读 $A$)：$\{ S \to A \cdot b \}$
     • 状态 3 (状态 0 读 $a$)： 点移位：$S \to a \cdot Ac$ 且 $A \to a \cdot$。由于点后面有大写字母 $A$，需引入以 $A$ 开头的规则且点放最左：$A \to \cdot a$。 即状态 3 为：$\{ S \to a \cdot Ac, A \to \cdot a, A \to a \cdot \}$
     • 状态 4 (状态 2 读 $b$)：$\{ S \to Ab \cdot \}$ (按规则 1 归约)
     • 状态 5 (状态 3 读 $A$)：$\{ S \to aA \cdot c \}$
     • 状态 6 (状态 3 读 $a$ 或状态 0 读 $a$ 后归入) —— 点移过 $a$：$\{ A \to a \cdot \}$ (按规则 3 归约)
     • 状态 7 (状态 5 读 $c$)：$\{ S \to aAc \cdot \}$ (按规则 2 归约)

  3. 第三步：指出 LR(0) 冲突并判断不是 LR(0)：

     • 观察状态 3，它同时包含了：
       • 移进项目：$A \to \cdot a$ （当读到具体字符 $a$ 时，要把圆点右移）
       • 归约项目：$A \to a \cdot$ （读到了最右侧，要按规则 3 归约）
     • 在同一个状态里，对于输入字符 $a$，既可以移进，又可以归约，这产生了移进-归约冲突。
     • 结论：因为存在冲突，所以该文法不是 $\text{LR}(0)$ 文法。

  4. 第四步：利用 FOLLOW 集消解冲突，证明是 SLR(1)：

     • 我们求大写字母 $A$ 后面可能紧跟的具体字符集合 $\text{FOLLOW}(A)$：
       • 在规则 $S \to Ab$ 中，$A$ 后面是具体符号 $b$。
       • 在规则 $S \to aAc$ 中，$A$ 后面是具体符号 $c$。
       • 所以，$\text{FOLLOW}(A) = \{ b, c \}$。
     • 冲突发生时，移进的字符是 $a$。由于 $a$ 不在 $\text{FOLLOW}(A)$ 集合中，说明当面临输入字符 $a$ 时，我们绝对不可能把当前栈顶内容归约为 $A$（因为如果归约成 $A$，后面就不可能合法地接上 $a$）。
     • 因此，在面临输入 $a$ 时，我们只能选择移进；只有在面临输入 $b$ 或 $c$ 时，我们才选择归约。
     • 结论：移进-归约冲突被成功解决，文法是 $\text{SLR}(1)$ 文法。

  5. 第五步：构造 SLR(1) 分析表：

     • 对于归约项目 $A \to a \cdot$（状态 3 和状态 6），我们只在属于 $\text{FOLLOW}(A) = \{b, c\}$ 的列中填入归约动作 r3。

     SLR(1) 分析表：

     状态	a	b	c	$	S	A
     0	s3				1	2
     1				acc
     2		s4
     3	s6	r3	r3			5
     4				r1
     5			s7
     6		r3	r3
     7				r2

• 例题 3 (SLR(1)/LR(1)/LALR(1) 冲突判定进阶)： 考虑文法 $S \to AS \mid b \ , \ A \to SA \mid a$：

  1. 列出该文法的所有 $\text{LR}(0)$ 项目。
  2. 构造 $\text{LR}(0)$ 项目集规范族及识别活前缀的 DFA。
  3. 判定该文法是否是 $\text{SLR}(1)$ 文法，若是，构造其预测分析表；若不是，说明理由。
  4. 该文法是 $\text{LALR}(1)$ 或 $\text{LR}(1)$ 的吗？说明理由。

• 解答：

  1. 拓广文法并写出所有 LR(0) 项目： 拓广文法引入 $S' \to S$。共 12 个项目： (1) $S' \to \cdot S$ (2) $S' \to S \cdot$ (3) $S \to \cdot AS$ (4) $S \to A \cdot S$ (5) $S \to AS \cdot$ (6) $S \to \cdot b$ (7) $S \to b \cdot$ (8) $A \to \cdot SA$ (9) $A \to S \cdot A$ (10) $A \to SA \cdot$ (11) $A \to \cdot a$ (12) $A \to a \cdot$

  2. 构造项目集规范族与 DFA 转移关系：

     • $I_0 = \{ S' \to \cdot S, S \to \cdot AS, S \to \cdot b, A \to \cdot SA, A \to \cdot a \}$
     • $I_1 = \text{GO}(I_0, S) = \{ S' \to S \cdot, A \to S \cdot A, S \to \cdot AS, S \to \cdot b, A \to \cdot SA, A \to \cdot a \}$
     • $I_2 = \text{GO}(I_0, A) = \{ S \to A \cdot S, S \to \cdot AS, S \to \cdot b, A \to \cdot SA, A \to \cdot a \}$
     • $I_3 = \text{GO}(I_0, a) = \{ A \to a \cdot \}$
     • $I_4 = \text{GO}(I_0, b) = \{ S \to b \cdot \}$
     • $I_5 = \text{GO}(I_1, A) = \{ A \to SA \cdot, S \to A \cdot S, S \to \cdot AS, S \to \cdot b, A \to \cdot SA, A \to \cdot a \}$
     • $I_6 = \text{GO}(I_1, S) = \{ A \to S \cdot A, S \to \cdot AS, S \to \cdot b, A \to \cdot SA, A \to \cdot a \}$
     • $I_7 = \text{GO}(I_2, S) = \{ S \to AS \cdot, A \to S \cdot A, S \to \cdot AS, S \to \cdot b, A \to \cdot SA, A \to \cdot a \}$

     DFA 状态转移表：

     状态	接收 $S$	接收 $A$	接收 $a$	接收 $b$
     $I_0$	$I_1$	$I_2$	$I_3$	$I_4$
     $I_1$	$I_6$	$I_5$	$I_3$	$I_4$
     $I_2$	$I_7$	$I_2$	$I_3$	$I_4$
     $I_3$	-	-	-	-
     $I_4$	-	-	-	-
     $I_5$	$I_7$	$I_2$	$I_3$	$I_4$
     $I_6$	$I_6$	$I_5$	$I_3$	$I_4$
     $I_7$	$I_6$	$I_5$	$I_3$	$I_4$

  3. 判定是否是 SLR(1)：

     • 计算非终结符的 FOLLOW 集：
       • \text{FOLLOW}(S) = \{ \, a, b }$
       • $\text{FOLLOW}(A) = \{ a, b \}$
     • 观察项目集 $I_5$，其中包含：
       • 归约项目：$A \to SA \cdot$（当面临输入属于 $\text{FOLLOW}(A) = \{a, b\}$ 时归约）
       • 移进项目：在 $I_5$ 下，读入终结符 $a$ 移进到 $I_3$，读入 $b$ 移进到 $I_4$。
     • 因为 $\text{FOLLOW}(A) \cap \{a, b\} = \{a, b\} \neq \emptyset$，所以在面临输入字符 $a$ 或 $b$ 时，分析器既可以移进，又可以归约，存在移进-归约冲突。
     • 结论：因为存在冲突，所以该文法不是 $\text{SLR}(1)$ 文法。

  4. 判定是否是 LALR(1) / LR(1)：

     • 结论：它既不是 $\text{LALR}(1)$ 文法，也不是 $\text{LR}(1)$ 文法。
     • 原因证明：该文法是一个二义性文法。对于同一个句子（例如 abab），可以构造出两棵不同的语法树：
       • 树 1：$S \to AS \to a (AS) \to a (SAS) \to a (baS) \to abab$
       • 树 2：$S \to AS \to (SA)S \to (ASA)S \to (abA)b \to abab$ 由于二义性文法在 LR 类分析器中必然存在无法消解的移进-归约或归约-归约冲突，因此该文法绝不可能是 $\text{LR}(1)$ 或 $\text{LALR}(1)$ 文法。

• 例题 4 (LR(1) 与 LALR(1) 状态合并机制讲解)： 考虑经典的非 SLR(1) 文法 $G[S]$： $S \to L=R \mid R \ , \ L \to *R \mid \text{id} \ , \ R \to L$ 解释为何 SLR(1) 会产生冲突，以及 LR(1) 和 LALR(1) 如何利用向前看搜索符消解该冲突。

• 解答：

  1. SLR(1) 冲突原因：
     • 计算其 $\text{FOLLOW}$ 集有 \text{FOLLOW}(R) = \{ \, = }$。
     • 在 LR(0) 状态集构建中，会产生一个状态 $I_2 = \{ S \to L \cdot = R \ , \ R \to L \cdot \}$。
     • 当输入为 = 时，在 $I_2$ 下：
       • 根据移进项目 $S \to L \cdot = R$，应当移进。
       • 根据归约项目 $R \to L \cdot$，因为 $= \in \text{FOLLOW}(R)$，在 SLR(1) 规则下应当归约。
       • 这在 = 处产生了移进-归约冲突，故文法不是 $\text{SLR}(1)$。
  2. LR(1) 的消解机制：
     • LR(1) 项目的形式为 $[A \to \alpha \cdot \beta, a]$，其中 $a$ 是向前看搜索符（由逆向分析 $\text{FIRST}$ 集而来）。
     • 在 LR(1) 中，初始状态 $I_0$ 为：
       • [S' \to \cdot S, \]$
       • [S \to \cdot L = R, \]$
       • [S \to \cdot R, \]$
       • [L \to \cdot *R, = / \]$（因为$L$后面是$=R$或继承$$$）
       • [L \to \cdot \text{id}, = / \]$
       • [R \to \cdot L, \]$（因为$R$后面是继承$$$）
     • 当从 $I_0$ 读入 $L$ 转移到 $I_2$ 时，得到项目集：
       • [S \to L \cdot = R, \]$
       • [R \to L \cdot, \]$
     • 消解效果：观察归约项目 [R \to L \cdot, \]$，其向前看搜索符**仅仅是$$$**，而不包含 =。
     • 此时，若面临输入 =，分析器只能选择移进（因为移进 = 属于项目 [S \to L \cdot = R, \]$的动作）；若面临输入$$$，才选择归约。移进-归约冲突被成功消解！
  3. LALR(1) 的合并同心集：
     • LR(1) 状态机往往有几百个状态，有很多状态的 LR(0) 核心相同，只有搜索符不同（同心集）。
     • LALR(1) 将这些同心状态进行合并，例如将 [R \to L \cdot, \]$和$[R \to L \cdot, =]$合并为$[R \to L \cdot, = / $]$。
     • 合并搜索符后，LALR(1) 状态数与 LR(0) 一致，在此文法中合并后依然没有冲突，成功证明该文法是 LALR(1) 的。

---

题型十二：移进-归约过程追踪#

如何做：

1. 准备四列：状态栈（里面只存状态数字，刚开始是 0）、符号栈（存读到的符号，刚开始是 $）、输入串（待处理的句子，末尾加 $）、动作。
2. 查表走步：
   • 看状态栈最顶上的那个数字（例如当前栈顶是 2），和输入串最左边的第一个字符（例如当前是 c）。
   • 去刚才做好的分析表里查对应的格子（交叉点 [2, c]）。
   • 如果格子里写着 s4：
     • 把当前字符 c 从输入串里删掉，塞入符号栈。
     • 把数字 4 塞入状态栈。
     • 动作记为“移进”。
   • 如果格子里写着 r3（说明要用第 3 条规则归约，假设第 3 条规则是 $A \to d$）：
     • 规则右边有几个符号（这里只有 1 个符号 $d$），就从符号栈和状态栈的顶部各弹出几个元素（这里各弹出 1 个）。
     • 把规则左边的大写字母（这里是 $A$）塞入符号栈。
     • 此时看一眼状态栈顶剩下的数字（假设是 2），查分析表里的 GOTO 栏（格子 [2, A]，假设填的是 3）。把这个数字 3 塞入状态栈。
     • 动作记为“用规则 3 归约”。
3. 重复执行，直到动作出现 acc（接受），说明句子完全符合规则。

• 题目 1：利用上题构造的分析表，给出句子 accd 的移进-归约分析详细步骤。

• 解答：

  步骤	状态栈	符号栈	输入串	动作
  1	0	$	accd$	读入首字符 a，查表 [0, a] 得到 s2，移进
  2	0 2	$a	ccd$	读入 c，查表 [2, c] 得到 s4，移进
  3	0 2 4	$ac	cd$	读入 c，查表 [4, c] 得到 s4，移进
  4	0 2 4 4	$acc	d$	读入 d，查表 [4, d] 得到 s5，移进
  5	0 2 4 4 5	$accd	$	查表 [5, $] 得到 r3（第3条规则是 $A \to d$）。右边长为1，两栈各弹1个元素。符号栈压 $A$，查 [4, A] 得到 6，状态栈压 6。用 $A \to d$ 归约
  6	0 2 4 4 6	$accA	$	查表 [6, $] 得到 r2（第2条规则是 $A \to cA$）。右边长为2，两栈各弹2个元素。符号栈压 $A$，查 [4, A] 得到 6，状态栈压 6。用 $A \to cA$ 归约
  7	0 2 4 6	$acA	$	查表 [6, $] 得到 r2（第2条规则是 $A \to cA$）。右边长为2，两栈各弹2个元素。符号栈压 $A$，查 [2, A] 得到 3，状态栈压 3。用 $A \to cA$ 归约
  8	0 2 3	$aA	$	查表 [3, $] 得到 r1（第1条规则是 $E \to aA$）。右边长为2，两栈各弹2个元素。符号栈压 $E$，查 [0, E] 得到 1，状态栈压 1。用 $E \to aA$ 归约
  9	0 1	$E	$	查表 [1, $] 得到 acc。分析成功

• 例题 2：对于文法 $S \to a \mid \wedge \mid (T) \ , \ T \to T, S \mid S$，给出句子 $(((a, a), \wedge, (a)), a)$ 的规范归约过程（最右推导的逆过程，每一步写出当前句型及归约句柄）。

• 解答： 规范归约就是每次找到句型中最左侧的直接短语（即句柄），查规则将其归约为左边的非终结符。 详细步骤如下：

  1. 当前句型为：(((a, a), ∧, (a)), a)。最左侧的直接短语是第一个 a，使用 $S \to a$ 归约。
     • 句型：(((S, a), ∧, (a)), a)，句柄为：a
  2. 接下来最左侧直接短语是第二个 a，使用 $S \to a$ 归约。
     • 句型：(((S, S), ∧, (a)), a)，句柄为：a
  3. 接下来最左侧直接短语是第一个 S，使用 $T \to S$ 归约。
     • 句型：(((T, S), ∧, (a)), a)，句柄为：S
  4. 接着 T, S 一步归约为 $T$。
     • 句型：(((T), ∧, (a)), a)，句柄为：T, S
  5. 接着最左直接短语是 (T)，使用 $S \to (T)$ 归约。
     • 句型：((S, ∧, (a)), a)，句柄为：(T)
  6. 接着最左直接短语是第一个 S，使用 $T \to S$ 归约。
     • 句型：((T, ∧, (a)), a)，句柄为：S
  7. 接着最左直接短语是 ∧，使用 $S \to \wedge$ 归约。
     • 句型：((T, S, (a)), a)，句柄为：∧
  8. 接着 T, S 一步归约为 $T$。
     • 句型：((T, (a)), a)，句柄为：T, S
  9. 接着最左直接短语是括号里的 a，使用 $S \to a$ 归约。
     • 句型：((T, (S)), a)，句柄为：a
  10. 接着最左直接短语是 S，使用 $T \to S$ 归约。
      • 句型：((T, (T)), a)，句柄为：S
  11. 接着最左直接短语是 (T)，使用 $S \to (T)$ 归约。
      • 句型：((T, S), a)，句柄为：(T)
  12. 接着 T, S 一步归约为 $T$。
      • 句型：((T), a)，句柄为：T, S
  13. 接着最左直接短语是 (T)，使用 $S \to (T)$ 归约。
      • 句型：(S, a)，句柄为：(T)
  14. 接着最左直接短语是 S，使用 $T \to S$ 归约。
      • 句型：(T, a)，句柄为：S
  15. 接着最左直接短语是最后一个 a，使用 $S \to a$ 归约。
      • 句型：(T, S)，句柄为：a
  16. 接着 T, S 一步归约为 $T$。
      • 句型：(T)，句柄为：T, S
  17. 最终 (T) 一步归约为开始符号 $S$。
      • 句型：S，句柄为：(T)
      • 归约成功！

---

模块五：语义分析、语法制导翻译与中间代码#

题型十三：语法制导定义（SDD）与属性计算#

如何做：

1. 理解属性：属性就是挂在代号（大写字母）身上的值，比如计算出来的长度、结果数值等。
2. 综合属性（自底向上计算）：如果一个代号的属性值，是直接根据它底下的分支子节点的属性值算出来的。
   • 计算顺序：先算出底层叶子的值，再一层层往上加，最后算出树顶（根部）的值。
3. 属性计算步骤：
   • 画出句子的代换树。
   • 从树的最底层开始，按照给定的数学公式算出每一个节点属性的值。
   • 顺着树枝往上代入，直到算出最顶上那个字母的属性。

• 题目：代换规则如下，其语义规则定义了长度计算 $S.\text{len} = A.\text{len} + 2, A.\text{len} = A'.\text{len} + 2, A'.\text{len} = 0$。求句子 a bbcc b（对应结构为 $S \to aAb$, $A \to bA'c$, $A' \to \varepsilon$）的属性计算步骤。

• 解答：

  1. 画出该句子的代换树结构：
     • $S$ 节点分支出 $a$, $A$, $b$。
     • $A$ 节点分支出 $b$, $A'$, $c$。
     • $A'$ 节点分支出 $\varepsilon$。
  2. 根据语义规则，自底向上代入计算：
     • 最底层 $A'$：其属性 $A'.\text{len} = 0$。
     • 中间层 $A$：根据公式 $A.\text{len} = A'.\text{len} + 2$，代入得 $A.\text{len} = 0 + 2 = 2$。
     • 最顶层 $S$：根据公式 $S.\text{len} = A.\text{len} + 2$，代入得 $S.\text{len} = 2 + 2 = 4$。
  3. 最终计算结果为 $S.\text{len} = 4$。

• 例题 2 (S-属性文法设计与属性计算)： 设计一个全综合属性的 S-属性文法，能够自底向上计算二进制小数（例如 101.101）对应的十进制数值，给出产生式和对应的语义规则，并写出计算 101.101 值的详细步骤。

• 解答：

  1. 设计属性：

     • 为单个二进制位 $B$ 引入属性 $B.val$（对应值 0 或 1）。
     • 为二进制串 $L$ 引入属性 $L.val$（对应部分计算出的十进制数值）以及 $L.len$（对应的二进制位串长度，用于计算小数时的权重移动）。
     • 为开始符号 $S$ 引入属性 $S.val$（最终十进制数值）。

  2. 构造 S-属性语法制导定义 (SDD)：

     产生式	语义规则
     $S \to L_1 . L_2$	$S.val = L_1.val + L_2.val \times 2^{-L_2.len}$
     $S \to L$	$S.val = L.val$
     $L \to L_1 B$	$L.val = L_1.val \times 2 + B.val$ $L.len = L_1.len + 1$
     $L \to B$	$L.val = B.val$ $L.len = 1$
     $B \to 0$	$B.val = 0$
     $B \to 1$	$B.val = 1$

  3. 计算 101.101 的具体步骤（自底向上）：

     • 整数部分 $L_1 = 101$：
       • 最左边位 $B_1 \to 1 \Rightarrow B_1.val = 1$。
       • 归约为单字符串 $L_a \to B_1 \Rightarrow L_a.val = B_1.val = 1, L_a.len = 1$。
       • 第二位 $B_2 \to 0 \Rightarrow B_2.val = 0$。
       • 归约为两位串 $L_b \to L_a B_2 \Rightarrow L_b.val = L_a.val \times 2 + B_2.val = 1 \times 2 + 0 = 2, L_b.len = L_a.len + 1 = 2$。
       • 第三位 $B_3 \to 1 \Rightarrow B_3.val = 1$。
       • 归约为三位串 $L_1 \to L_b B_3 \Rightarrow L_1.val = L_b.val \times 2 + B_3.val = 2 \times 2 + 1 = 5, L_1.len = L_b.len + 1 = 3$。
     • 小数部分 $L_2 = 101$（运算规则与整数部分相同）：
       • 经过同样的推导，计算出 $L_2.val = 5, L_2.len = 3$。
     • 整句归约 $S \to L_1 . L_2$：
       • 根据定义：$S.val = L_1.val + L_2.val \times 2^{-L_2.len}$。
       • 代入数据：$S.val = 5 + 5 \times 2^{-3} = 5 + 5 \times 0.125 = 5.625$。
       • 最终十进制结果为 $5.625$。

---

题型十四：逆波兰式（后缀式）与三地址代码转换#

如何做：

1. 逆波兰式（后缀表达式）：
   • 平时我们写的算式是“运算符在中间”，如 $a + b$。逆波兰式要求把“运算符移到后面”，变成 $a b +$。
   • 遇到括号时，先算括号里面的。括号本身在最后的结果里不写出来。
   • 复杂的式子可以先画成一棵运算树（运算符在交叉点上，数字在树叶上），然后按照“左分叉、右分叉、最后运算符”的顺序把它们写下来。
2. 三地址四元式：
   • 把复杂的长算式拆成一步步只包含两个运算数的简短式子，每一步算完的值存入一个临时变量（如 $T_1$, $T_2$）。
   • 每一行写成四个位置的格式：(操作符, 第一个运算数, 第二个运算数, 结果临时变量)。如果是一元运算（如单目减法 $-C$），没有第二个运算数，就在第三个位置写下划线 _。

• 题目 1：给出赋值语句 $A := B * ( - C + D )$ 生成的四元式序列。

• 解答：

  1. 观察优先级，最先计算括号内的单目减法 $-C$。写成四元式，存入临时变量 $T_1$： (-, C, _, T1) (注意：单目减没有第二个操作数，用下划线占位)
  2. 接着计算 $T_1 + D$，存入 $T_2$： (+, T1, D, T2)
  3. 接着计算括号外面的乘法，即 $B * T_2$，存入 $T_3$： (*, B, T2, T3)
  4. 最后把乘出来的结果 $T_3$ 赋值给变量 $A$： (:=, T3, _, A)

• 例题 2 (算术/布尔表达式后缀式转换)： 写出以下两个表达式的逆波兰（后缀）表示形式：

  1. $a * ( - b + c )$ (特别注意单目减号处理)
  2. $\text{not } A \text{ or not } ( C \text{ or not } D )$

• 解答：

  1. 对于 $a * ( - b + c )$：
     • 单目减号 - 在这里只对 $b$ 起作用，可以用特殊的单目负操作符 uminus（或 @）表示。
     • 运算树的根节点是 *，其左子树为 a，右子树为括号内的 ( -b + c )（根节点为 +，左子树为 -b，右子树为 c）。
     • 后缀式按照“左儿子、右儿子、根”的深度遍历：
       • 首先遍历 a。
       • 然后遍历右侧，先写 b 和单目负 uminus 得到 b uminus；再写右子树 c；最后写运算 +。得到 b uminus c +。
       • 最后输出根操作符 *。
     • 最终逆波兰式： $a \ b \ \text{uminus} \ c \ + \ *$ (注：考试中若不特别要求单目负表示，也可简化写为：$a \ b \ - \ c \ + \ *$)
  2. 对于 $\text{not } A \text{ or not } ( C \text{ or not } D )$：
     • 根据算符优先级，单目操作符 not 的优先级高于双目操作符 or。
     • 逐步转换后缀式：
       • 第一个项 $\text{not } A$ 转换为：A not。
       • 括号内的 $C \text{ or not } D$ 转换为：C D not or。
       • 括号外的 $\text{not } ( \dots )$ 作用于其上，转换为：C D not or not。
       • 最后将前半截和后半截使用根部的 or 连接。
     • 最终逆波兰式： $A \ \text{not} \ C \ D \ \text{not} \ \text{or} \ \text{not} \ \text{or}$

---

题型十五：控制流语句的四元式序列生成#

如何做：

1. 短路计算：
   • $B_1 \text{ or } B_2$：如果前面的条件 $B_1$ 成立，就不用看后面的条件 $B_2$ 了，直接跳去真目标。
   • $B_1 \text{ and } B_2$：如果前面的条件 $B_1$ 不成立，直接判定为假，不用看 $B_2$，跳去假目标。
2. 跳转四元式的写法：
   • 条件跳转：比如“若 $a < b$ 则跳到第 103 行”，写成：(j<, a, b, 103)。如果不满足，就直接顺着执行下一行。
   • 无条件跳转：直接跳到某一行，写成：(j, _, _, 106)。
3. 行号规划：
   • 假设从指定的行号（如 100）开始写，每写一行行号加 1。
   • 遇到需要跳转的目标行号，如果还没写到那一行，可以先空着，等写到目标行后再把行号倒回去填上（回填）。

• 题目 1：把程序段 while a < b do if c < d then x := y + z 翻译成四元式代码，假设起始行号为 100，采用短路计算。

• 解答：

  1. 100行：这是 while 循环判定条件的开始。我们先测试条件 $a < b$，如果满足，就跳进循环体内（假设跳到 102 行开始判断 if 条件）；如果不满足，循环结束，直接跳出循环（跳到最后一行的下一行，假设是 107 行）： 100: (j<, a, b, 102) 101: (j, _, _, 107)
  2. 102行：开始判断 if c < d 条件。如果满足，执行 then 后面的赋值（假设是 104 行）；如果不满足，if 结束，无操作，继续下一次循环（回到 100 行）： 102: (j<, c, d, 104) 103: (j, _, _, 100)
  3. 104行：执行加法赋值 x := y + z。算完之后，因为是循环体，必须无条件跳回最开始的 100 行进行下一次判定： 104: (+, y, z, T1) 105: (:=, T1, _, x) 106: (j, _, _, 100)
  4. 检查发现，循环结束的出口行应该在 106 行之后，即 107 行。回填 101 行的假跳转目标为 107：
     • 完整四元式序列：

       100: (j<, a, b, 102)
       101: (j, _, _, 107)
       102: (j<, c, d, 104)
       103: (j, _, _, 100)
       104: (+, y, z, T1)
       105: (:=, T1, _, x)
       106: (j, _, _, 100)
       107: (nop)

• 例题 2 (复杂嵌套控制流与短路计算四元式生成)： 将如下带有嵌套 while 循环和 and 逻辑运算的控制流语句翻译为四元式序列。假设起始行号为 100，布尔表达式采用短路计算：

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

• 解答：

  1. 设计分析逻辑（带回填机制）：

     • 行 100：开始评估外层 while 的第一个条件 A < C。如果为真，跳转到 102 行评估第二个条件；如果为假，说明条件短路失败，跳出整个外层循环（跳转目标待定为出口行 114）。
     • 行 102：评估外层 while 的第二个条件 B < D。如果为真，说明整个 and 条件成立，跳入循环体（即 104 行的 if 判断）；如果为假，退出循环（跳到 114 行）。
     • 行 104：外层循环体内，评估 if A = 1。若为真，跳转到 then 分支的计算（106 行）；若为假，跳转到 else 分支（即内层 while 循环起始的 109 行）。
     • 行 106-107：then 分支，计算 C := C + 1。计算完后，代表外层循环的一轮体结束，必须无条件跳转回 100 行。
     • 行 109：else 分支，开始评估内层 while 条件 A <= D。如果为真，跳入内层循环体（111 行）；如果为假，退出内层循环，因为外层循环体在此也结束了，所以直接跳回 100 行。
     • 行 111-112：内层循环体内，计算 A := A + 2。计算完后，无条件跳转回内层条件评估点（109 行）。
     • 行 114：外层循环出口。

  2. 生成完整四元式序列：

     序号	操作符	运算数 1	运算数 2	结果 (跳转目标 / 临时变量)	说明
     100	j<	$A$	$C$	$102$	判断条件 $A < C$（真则看下一个）
     101	j	_	_	$114$	条件不满足，退出外层循环
     102	j<	$B$	$D$	$104$	判断条件 $B < D$（真则入循环体）
     103	j	_	_	$114$	条件不满足，退出外层循环
     104	j=	$A$	$1$	$106$	外层循环体首：判断 $A = 1$（真则去 then）
     105	j	_	_	$109$	假则去 else 分支（内层循环）
     106	+	$C$	$1$	$T_1$	then 分支：$T_1 = C + 1$
     107	:=	$T_1$	_	$C$	赋值给 $C$
     108	j	_	_	$100$	结束后跳转回外层循环开头
     109	j<=	$A$	$D$	$111$	else/内层循环开始：判断 $A \le D$
     110	j	_	_	$100$	内层循环结束，返回外层循环开头
     111	+	$A$	$2$	$T_2$	内层循环体：$T_2 = A + 2$
     112	:=	$T_2$	_	$A$	赋值给 $A$
     113	j	_	_	$109$	结束后跳转回内层循环开头
     114	nop	_	_	_	外层循环退出点

---

模块六：代码优化#

题型十六：基本块划分与控制流图 (CFG) 构造#

如何做：

1. 基本块（一气呵成执行的代码段）：
   • 基本块的特点是“一旦从入口进去，就必须一气呵成地执行到出口，中间不能跳走，也不能从别的路插进来”。
2. 第一步，找到所有块的入口语句（也叫 Leader）：
   • 规则一：第一行语句是一个入口。
   • 规则二：任何跳转语句（有条件或无条件跳转）的目标语句是一个入口。
   • 规则三：紧跟在跳转语句后面的那一行语句是一个入口。
3. 第二步，切分基本块：
   • 从每一个入口语句开始往下数，一直到下一个入口语句的前一行，切开，这就是一个独立的基本块。
4. 第三步，画连接图 (CFG)：
   • 把每一个块画成一个方框。
   • 画带箭头的连线：如果执行完块 1，有可能顺着走到块 2，或者通过块 1 末尾的跳转跳到块 2，就画一条从块 1 指向块 2 的箭头。

• 题目：对下面的程序，划分基本块，并画出其控制流图：

  (1) A := 0
  (2) B := 1
  (3) L1: A := A + B
  (4) if B >= C goto L2
  (5) B := B + 1
  (6) goto L1
  (7) L2: write A
  (8) halt

• 解答：
  1. 寻找入口语句 (Leader)：
     • 根据规则一：语句 (1) 是第一行，故 (1) 是入口。
     • 根据规则二：
       • 语句 (4) 中的跳转目标是 L2，即语句 (7)，故 (7) 是入口。
       • 语句 (6) 中的跳转目标是 L1，即语句 (3)，故 (3) 是入口。
     • 根据规则三：
       • 语句 (4) 是条件跳转，紧跟其后的是语句 (5)，故 (5) 是入口。
       • 语句 (6) 是跳转，紧跟其后的是语句 (7)（已是入口）。
     • 所有的入口语句为：(1), (3), (5), (7)。
  2. 切分基本块：
     • 基本块 B1（从入口 (1) 到下一个入口 (3) 之前）：包含 (1), (2)。
     • 基本块 B2（从入口 (3) 到下一个入口 (5) 之前）：包含 (3), (4)。
     • 基本块 B3（从入口 (5) 到下一个入口 (7) 之前）：包含 (5), (6)。
     • 基本块 B4（从入口 (7) 到结尾）：包含 (7), (8)。
  3. 画控制流图 (CFG)：
     • 块 B1 执行完后，直接顺着走到块 B2。连线：B1 -> B2。
     • 块 B2 结尾的条件跳转，若满足跳去 L2（即块 B4）；若不满足，直接顺着走到块 B3。连线：B2 -> B3，B2 -> B4。
     • 块 B3 结尾无条件跳转去 L1（即块 B2）。连线：B3 -> B2。
     • 连成的控制流图为：

       graph TD
           B1["基本块 B1<br>(1)-(2)"] --> B2["基本块 B2<br>(3)-(4)"]
           B2 -->|不满足跳转| B3["基本块 B3<br>(5)-(6)"]
           B2 -->|满足跳转| B4["基本块 B4<br>(7)-(8)"]
           B3 --> B2