编译原理计算大题解题方法汇总#

---

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

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

根据给定的语言集合定义，设计符合要求的上下文无关文法 $G[S]$。

1. 解题通用步骤#

1. 分析语言模式与字符依赖：
   • 确定终结符集合 $V_{\text{T}}$ 与非终结符集合 $V_{\text{N}}$。
   • 寻找句子中字符个数的依赖关系。例如 $a^n b^n$ 存在等量匹配，而 $a^n b^m$ 则完全独立。
2. 提炼递归结构（递归基与递推关系）：
   • 对于成对相等的结构（如 $a^n b^n \mid n \ge 1$），递归关系为 $S \to aSb \mid ab$。若 $n \ge 0$，则递归基为 $\varepsilon$，递归关系为 $S \to aSb \mid \varepsilon$。
   • 对于独立的字符序列（如 $a^n b^m$），采用非终结符拼接法：$S \to X Y$，其中 $X$ 产生 $a^n$，$Y$ 产生 $b^m$。
3. 处理条件限制与边界：
   • 仔细审查边界情况（如“不以 $0$ 开头”、“偶数”、“首位非 $0$”）。
   • 可将多位数拆分为“首位”与“后续位”的拼接，或者使用条件分支。
4. 代入最简句子检验：
   • 用设计的文法尝试推导出最短的合法句子（如 $n=1, n=2$），并检查是否会产生非法句子（如首位为 0 的多位数）。

2. 典型例题解题套路#

• 例题：构造一个只能产生奇数（且多位数首位不为 0）的十进制数文法。
• 解法步骤：
  1. 奇数的尾数只能是 $1, 3, 5, 7, 9$。
  2. 首位不能为 0，所以多位数的首位只能是 $1, 2, \dots, 9$。
  3. 中间位可以是任意数字 $0, 1, \dots, 9$。
  4. 单个数字的奇数也是合法的，需要作为特殊情况单独包含。
  5. 构造文法： $$\begin{aligned} S &\to A \mid B C D \mid B D \\ A &\to 1 \mid 3 \mid 5 \mid 7 \mid 9 \\ B &\to A \mid 2 \mid 4 \mid 6 \mid 8 \\ C &\to C E \mid E \\ D &\to A \\ E &\to 0 \mid B \end{aligned}$$ (说明：$A$ 代表奇数码；$B$ 代表非零数码；$C$ 代表任意位数的数字串；$D$ 代表奇数尾数；$E$ 代表任意数码。)

---

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

1. 解题通用步骤#

1. 概念区分：
   • 最左推导 (Leftmost Derivation)：在推导的每一步中，只对句型中最左边的非终结符进行替换。记作 $\Rightarrow_{\text{lm}}$ 或直接使用 $\Rightarrow$ 并标明。
   • 最右推导 (Rightmost Derivation)：在推导的每一步中，只对句型中最右边的非终结符进行替换。最右推导也称为规范推导 (Canonical Derivation)。记作 $\Rightarrow_{\text{rm}}$。
2. 推导书写规范：
   • 必须从文法的开始符号（如 $E$ 或 $S$）开始。
   • 每一步只替换一个非终结符，并在右侧标记出替换所用的产生式，直至整个句型中不再包含任何非终结符。
3. 语法树绘制规则：
   • 根节点为文法开始符号。
   • 若 $A \to X_1 X_2 \dots X_n$，则在树中从 $A$ 节点分支出 $X_1, X_2, \dots, X_n$。
   • 叶节点从左到右连结，所得符号串即为推导的句子。

2. 典型例题解题套路#

• 例题：已知算术表达式文法 $G(E)$： $E \to E + T \mid T \ , \ T \to T * F \mid F \ , \ F \to (E) \mid i$ 给出句子 $i + i * i$ 的最左推导和最右推导。
• 解答：
  • 最左推导： $$\begin{aligned} E &\Rightarrow_{\text{lm}} E + T && (\text{应用 } E \to E + T) \\ &\Rightarrow_{\text{lm}} T + T && (\text{应用 } E \to T) \\ &\Rightarrow_{\text{lm}} F + T && (\text{应用 } T \to F) \\ &\Rightarrow_{\text{lm}} i + T && (\text{应用 } F \to i) \\ &\Rightarrow_{\text{lm}} i + T * F && (\text{应用 } T \to T * F) \\ &\Rightarrow_{\text{lm}} i + F * F && (\text{应用 } T \to F) \\ &\Rightarrow_{\text{lm}} i + i * F && (\text{应用 } F \to i) \\ &\Rightarrow_{\text{lm}} i + i * i && (\text{应用 } F \to i) \end{aligned}$$
  • 最右推导： $$\begin{aligned} E &\Rightarrow_{\text{rm}} E + T && (\text{应用 } E \to E + T) \\ &\Rightarrow_{\text{rm}} E + T * F && (\text{应用 } T \to T * F) \\ &\Rightarrow_{\text{rm}} E + T * i && (\text{应用 } F \to i) \\ &\Rightarrow_{\text{rm}} E + F * i && (\text{应用 } T \to F) \\ &\Rightarrow_{\text{rm}} E + i * i && (\text{应用 } F \to i) \\ &\Rightarrow_{\text{rm}} T + i * i && (\text{应用 } E \to T) \\ &\Rightarrow_{\text{rm}} F + i * i && (\text{应用 } T \to F) \\ &\Rightarrow_{\text{rm}} i + i * i && (\text{应用 } F \to i) \end{aligned}$$

---

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

1. 核心定义#

对于文法 $G[S]$ 的一个句型 $\beta$（其中 $S \Rightarrow^* \alpha A \delta$ 且 $A \Rightarrow^+ \gamma$，使得 $\beta = \alpha \gamma \delta$）：

• 短语 (Phrase)：称子串 $\gamma$ 是句型 $\beta$ 相对非终结符 $A$ 的短语。
• 直接短语 (Simple/Direct Phrase)：若有 $A \Rightarrow \gamma$（一步推导），则称 $\gamma$ 是句型 $\beta$ 相对非终结符 $A$ 的直接短语。
• 句柄 (Handle)：一个句型的最左直接短语称为该句型的句柄。

2. 基于语法分析树判定方法（极力推荐，最直观且不易出错）#

1. 步骤一：画出句型对应的语法分析树。
2. 步骤二（找短语）：找出语法树中的所有非叶子节点（即所有子树的根节点）。每一个非叶子节点所对应的子树中，所有叶子节点自左向右排列组成的符号串，就是该句型的一个短语。
3. 步骤三（找直接短语）：找出语法树中所有高度为 1 的子树（即该子树的根节点的所有孩子节点都是叶子节点，且没有更深的子树分支）。这些子树的叶节点自左向右组成的符号串，就是该句型的直接短语。
4. 步骤四（找句柄）：在所有直接短语中，定位最左边的那一个符号串，它就是该句型的句柄。

3. 典型例题解题套路#

• 例题：考虑文法 $G_1$： $E \to E + T \mid T \ , \ T \to T * F \mid F \ , \ F \to (E) \mid i$ 指出句型 $E + T * F$ 的所有短语、直接短语和句柄。
• 解答：
  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$ 是短语。
     • （注：单个变量如 $E, T, F$ 虽然也是子树叶子，但这里只讨论非单个符号的短语，或者如果包含单个符号，则 $E, T, F$ 本身也可以是相对自身的短语，但通常大题中主要列出主要子串）
  4. 找出高度为 1 的子树：
     • 只有以 $T1$ 为根的子树中，它的分支直接产生叶子节点 $T$、$*$ 和 $F$。这棵子树的高度为 1。
     • 因此，直接短语只有 $T * F$。
  5. 确定句柄：
     • 因为只有一个直接短语，所以最左直接短语就是它本身。
     • 句柄是 $T * F$。

---

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

1. 解题通用步骤#

1. 基本原理：若一个文法存在某个句子，能为它构造出两棵或两棵以上不同的语法分析树，或者能为它写出两个不同的最左推导（或最右推导），则证明该文法是二义性的。
2. 证明三步法：
   • 第一步：寻找反例句子。选择包含多个算符的极简句子，例如对于算术表达式文法选择 $i+i*i$ 或 $i+i+i$；对于悬空 else 文法选择 $iSeS$。
   • 第二步：展示两棵语法树。针对该反例句子画出两棵明显的语法分析树，展示出不同的结合性或运算优先级。
   • 第三步：书写推导或结论。分别写出这两棵树对应的最左推导过程，并下结论说明由于句子具有多于一棵的语法树，故文法是二义的。

2. 典型例题解题套路#

• 例题：证明算术表达式文法 $E \to E + E \mid E * E \mid (E) \mid i$ 是二义的。
• 解答：
  1. 选择句子：$i + i * i$。
  2. 构造语法树 1（先算乘法）：

     graph TD
         E1["E"] --> E2["E"]
         E1 --> P["+"]
         E1 --> E3["E"]
         E2 --> I1["i"]
         E3 --> E4["E"]
         E3 --> M["*"]
         E3 --> E5["E"]
         E4 --> I2["i"]
         E5 --> I3["i"]

  3. 构造语法树 2（先算加法）：

     graph TD
         E1["E"] --> E2["E"]
         E1 --> M["*"]
         E1 --> E3["E"]
         E2 --> E4["E"]
         E2 --> P["+"]
         E2 --> E5["E"]
         E4 --> I1["i"]
         E5 --> I2["i"]
         E3 --> I3["i"]

  4. 结论：针对同一个句子 $i + i * i$，文法能够生成两棵不同的语法树。根据定义，该文法是二义的。

---

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

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

1. 核心代数恒等律#

在证明两个正规式等价时，经常用到如下恒等式（设 $U, V, W$ 为正规式）：

• 交换律：$U \mid V = V \mid U$
• 结合律：$U \mid (V \mid W) = (U \mid V) \mid W \ , \ U(VW) = (UV)W$
• 分配律：$U(V \mid W) = UV \mid UW \ , \ (U \mid V)W = UW \mid VW$
• 特殊元：$\varepsilon U = U \varepsilon = U \ , \ \emptyset U = U \emptyset = \emptyset \ , \ \emptyset \mid U = U$
• 闭包律：
  • $U^* = \varepsilon \mid U U^* = \varepsilon \mid U^* U$
  • $(U^*)^* = A^*$
  • $(U \mid V)^* = (U^* V^*)^* = (U^* \mid V^*)^*$
  • $U(VU)^* = (UV)^*U$

2. Arden 引理（Arden’s Lemma）#

• 内容：若 $A$ 和 $B$ 是两个正规式，且 $\varepsilon \notin L(A)$，则关于 $X$ 的代数方程： $X = A X \mid B$ 有唯一解： $X = A^* B$ 同理，若方程为 $X = X A \mid B$，其唯一解为 $X = B A^*$。

3. 典型例题解题套路#

• 例题：证明恒等式：$(AB)^*A = A(BA)^*$。
• 证明步骤： 利用闭包性质展开： 根据闭包的定义：$U^* = \varepsilon \mid U^* U = \varepsilon \mid U U^*$ 左边展开： $$\begin{aligned} (AB)^*A &= (\varepsilon \mid A B (A B)^*) A && (\text{展开 } (AB)^*) \\ &= A \mid A B (A B)^* A && (\text{乘法分配律}) \end{aligned}$$ 右边展开： $$\begin{aligned} A(BA)^* &= A (\varepsilon \mid (B A) (B A)^*) && (\text{展开 } (BA)^*) \\ &= A \mid A B A (B A)^* && (\text{乘法分配律}) \end{aligned}$$ 根据左边与右边的相似性，利用 $U(VU)^* = (UV)^*U$（这里令 $U=A, V=B$，则有 $A(BA)^* = (AB)^*A$），两边直接等值。 或者，我们可以设 $X = A(BA)^*$，我们有： $X = A(\varepsilon \mid BA(BA)^*) = A \mid AB A(BA)^* = A \mid AB X$ 根据 Arden 引理，方程 $X = AB X \mid A$ 的唯一解为 $X = (AB)^* A$。 由于 $A(BA)^*$ 是方程的解，因此 $A(BA)^* = (AB)^* A$ 得证。

---

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

1. 拆分与构造原则#

1. 翻译物理限制：
   • “以某串结尾” $\to \dots \text{pattern}$，例如以 01 结尾：$(0 \mid 1)^* 01$。
   • “不包含某模式” $\to$ 构造状态机或利用基本闭包避开该模式。
2. 常见构造块：
   • 任意二进制串：$(0 \mid 1)^*$
   • 偶数个 0 的串：$(1 \mid 0 1^* 0)^*$ （每个 0 必须成对出现，中间可夹杂任意个 1）
   • 奇数个 1 的串：$0^* 1 0^* (1 0^* 1 0^*)^*$（先放一个 1，后面接偶数个 1）
3. 前导零限制：
   • 不允许有前导零的十进制数：$0 \mid (1 \mid 2 \mid \dots \mid 9)(0 \mid 1 \mid \dots \mid 9)^*$

---

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

1. NFA 确定化（子集构造法 Subset Construction）#

• 核心定义：
  • $\varepsilon\text{-closure}(S)$：从状态集 $S$ 中的状态出发，仅通过 $\varepsilon$ 弧所能到达的状态集合。
  • $\text{move}(I, a)$：从状态集 $I$ 中的状态出发，经过一条标有 $a$ 的弧所到达的状态集合。
• 解题步骤：
  1. 计算初态：计算 $I_0 = \varepsilon\text{-closure}(s_0)$，将其作为 DFA 的起始状态，放入未标记状态集列表中。
  2. 循环构造：对列表中每一个未标记的状态集 $I$：
     • 标记 $I$。
     • 对字母表中的每一个输入符号 $a$，计算新状态集： $J = \varepsilon\text{-closure}(\text{move}(I, a))$
     • 若 $J$ 为非空且不在列表中，则将 $J$ 作为新状态加入列表（未标记）。
     • 记录转移关系 $\delta(I, a) = J$。
  3. 确定终态：任何包含原 NFA 接受状态的子集，都是 DFA 的接受状态。
  4. 绘制状态转移表。

2. DFA 最小化（分割法 / Hopcroft 算法）#

• 解题步骤：
  1. 初始划分：将 DFA 状态集 $S$ 划分为两个子集：接受状态集 $S_{\text{acc}}$ 和非接受状态集 $S_{\text{non-acc}}$。此时划分 $P = \{ S_{\text{acc}}, S_{\text{non-acc}} \}$。
  2. 尝试分裂：对于 $P$ 中的每一个状态子集 $G$，以及字母表中的每一个输入符号 $a$：
     • 计算 $\delta(G, a)$。如果 $G$ 中的状态在输入 $a$ 后，转移到的状态不属于同一个子集，则需要对 $G$ 进行分裂。
     • 例如，若 $s_1, s_2 \in G$，且 $\delta(s_1, a) \in G_1$，而 $\delta(s_2, a) \in G_2$（$G_1, G_2$ 是当前 $P$ 中的不同子集），则把 $G$ 分裂为 $G' = \{s \in G \mid \delta(s, a) \in G_1\}$ 和 $G'' = G \setminus G'$。
  3. 迭代更新：重复步骤 2，直到当前的划分 $P$ 不再发生任何改变。
  4. 合并并重建：将最终属于同一子集的状态合并为一个新的代表状态。删除死状态（无法到达终态的状态），整理出最小化 DFA 的状态转移表和状态图。

3. 典型例题解题套路#

• 例题：将如下 DFA 最小化。状态集为 $\{0, 1, 2, 3, 4, 5\}$，初态为 $0$，接受状态为 $0, 1$。
  • 转移关系：$\delta(0,a)=1, \delta(0,b)=2$; $\delta(1,a)=1, \delta(1,b)=4$; $\delta(2,a)=1, \delta(2,b)=3$; $\delta(3,a)=3, \delta(3,b)=2$; $\delta(4,a)=0, \delta(4,b)=5$; $\delta(5,a)=5, \delta(5,b)=4$。
• 解法步骤：
  1. 第一步：初始划分： $P_0 = \{ G_1, G_2 \} \ , \ G_1 = \{0, 1\} (\text{接受}) \ , \ G_2 = \{2, 3, 4, 5\} (\text{非接受})$
  2. 第二步：考察 $G_1 = \{0, 1\}$：
     • 输入 $a$：$\delta(0, a) = 1 \in G_1$；$\delta(1, a) = 1 \in G_1$。
     • 输入 $b$：$\delta(0, b) = 2 \in G_2$；$\delta(1, b) = 4 \in G_2$。
     • 行为完全一致，故 $\{0, 1\}$ 无法分割，暂记为状态组 $(01)$。
  3. 第三步：考察 $G_2 = \{2, 3, 4, 5\}$：
     • 输入 $a$：
       • $\delta(2, a) = 1 \in G_1$
       • $\delta(3, a) = 3 \in G_2$
       • $\delta(4, a) = 0 \in G_1$
       • $\delta(5, a) = 5 \in G_2$
     • 发现 $\{2, 4\}$ 转移至 $G_1$，而 $\{3, 5\}$ 转移至 $G_2$。因此 $G_2$ 必须分裂为两组：$G_{2A} = \{2, 4\}$ 和 $G_{2B} = \{3, 5\}$。
     • 当前划分 $P_1 = \{ \{0, 1\}, \{2, 4\}, \{3, 5\} \}$。
  4. 第四步：重新考察 $G_{2A} = \{2, 4\}$：
     • 输入 $a$：$\delta(2, a) = 1 \in G_1$，$\delta(4, a) = 0 \in G_1$。
     • 输入 $b$：$\delta(2, b) = 3 \in G_{2B}$，$\delta(4, b) = 5 \in G_{2B}$。
     • 行为一致，无法分割。
  5. 第五步：重新考察 $G_{2B} = \{3, 5\}$：
     • 输入 $a$：$\delta(3, a) = 3 \in G_{2B}$，$\delta(5, a) = 5 \in G_{2B}$。
     • 输入 $b$：$\delta(3, b) = 2 \in G_{2A}$，$\delta(5, b) = 4 \in G_{2A}$。
     • 行为一致，无法分割。
  6. 第六步：合并状态：
     • 合并后状态为：$A = \{0, 1\}$，$B = \{2, 4\}$，$C = \{3, 5\}$。
     • 最小化转移表：

       状态	输入 $a$	输入 $b$	是否接受
       $A$ (初)	$A$	$B$	是
       $B$	$A$	$C$	否
       $C$	$C$	$B$	否

---

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

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

1. 消除直接左递归#

对于包含直接左递归的产生式： $A \to A\alpha_1 \mid A\alpha_2 \mid \dots \mid A\alpha_m \mid \beta_1 \mid \beta_2 \mid \dots \mid \beta_n$ （其中 $\beta_i$ 不以 $A$ 开头） 改写为无左递归的右递归形式：

$$\begin{aligned} A &\to \beta_1 A' \mid \beta_2 A' \mid \dots \mid \beta_n A' \\ A' &\to \alpha_1 A' \mid \alpha_2 A' \mid \dots \mid \alpha_m A' \mid \varepsilon \end{aligned}$$

2. 消除间接左递归#

1. 排序：将文法中所有的非终结符按某种顺序排列为 $A_1, A_2, \dots, A_n$。
2. 代入消元：

   for i := 1 to n do
     for j := 1 to i - 1 do
       begin
         将产生式中形如 Ai -> Aj r 的 Aj 用其所有产生式右部代替;
       end;
     消除 Ai 产生式中的直接左递归;

3. 化简：删除从开始符号无法到达的非终结符。

3. 提取左公因子#

若有产生式 $A \to \alpha\beta_1 \mid \alpha\beta_2 \mid \gamma$，提取公因子 $\alpha$：

$$\begin{aligned} A &\to \alpha A' \mid \gamma \\ A' &\to \beta_1 \mid \beta_2 \end{aligned}$$

---

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

1. 核心映射法则#

对于每个非终结符 $A$，为其编写一个对应的同名函数/过程 A()：

1. 获取前看符号：使用全局变量 lookahead 保存当前输入的 Token。
2. 分支判定：根据非终结符 $A$ 的候选产生式右部的 FIRST 集合来决定进入哪一个分支。
3. 程序执行：
   • 若遇到终结符 $a$，调用 match(a) 进行匹配。
   • 若遇到非终结符 $B$，直接调用过程 B()。
   • 若存在产生式 $A \to \varepsilon$，当 lookahead 属于 $\text{FOLLOW}(A)$ 时，直接返回（即不执行任何匹配）；若不属于，则报错。
4. match 函数的标准定义：

   procedure match(t: token);
   begin
       if lookahead = t then
           lookahead := nextToken()
       else
           error(); // 语法错误处理
   end;

2. 典型伪代码模板#

对于产生式 $S \to a \mid \wedge \mid (T)$，其递归下降程序为：

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;

---

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

1. FIRST 集合计算法则#

1. 若 $X$ 是终结符，则 $\text{FIRST}(X) = \{ X \}$。
2. 若有产生式 $X \to \varepsilon$，将 $\varepsilon$ 放入 $\text{FIRST}(X)$。
3. 若有产生式 $X \to Y_1 Y_2 \dots Y_k$：
   • 把 $\text{FIRST}(Y_1) \setminus \{\varepsilon\}$ 放入 $\text{FIRST}(X)$。
   • 若 $\varepsilon \in \text{FIRST}(Y_1)$，则把 $\text{FIRST}(Y_2) \setminus \{\varepsilon\}$ 放入，以此类推。
   • 若所有的 $Y_i$ 的 FIRST 集都含有 $\varepsilon$，则将 $\varepsilon$ 放入 $\text{FIRST}(X)$。

2. FOLLOW 集合计算法则#

1. 设 $S$ 为文法的开始符号，将输入流结束符 \$$ 放入 \text{FOLLOW}(S)$。
2. 扫描所有产生式右部，寻找非终结符 $A$的位置：
   • 若存在 $B \to \alpha A \beta$，将 $\text{FIRST}(\beta) \setminus \{\varepsilon\}$ 放入 $\text{FOLLOW}(A)$。
   • 若存在 $B \to \alpha A$ 或 $B \to \alpha A \beta$（且 $\varepsilon \in \text{FIRST}(\beta)$），则将 $\text{FOLLOW}(B)$ 中的所有元素放入 $\text{FOLLOW}(A)$。

3. LL(1) 文法的判定条件#

一个文法是 LL(1) 文法，当且仅当对于其任意非终结符 $A$ 的两个不同候选产生式 $A \to \alpha \mid \beta$：

1. $\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \emptyset$（首符集互斥）。
2. 若 $\beta \Rightarrow^* \varepsilon$（即 $\varepsilon \in \text{FIRST}(\beta)$），则 $\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \emptyset$（空转情况下，首符集与后跟符集互斥）。

4. 预测分析表 M 构造规则#

• 行代表非终结符，列代表终结符（包括结束符 $$$）。
• 对文法中的每一个产生式 $A \to \alpha$：
  • 对每个终结符 $a \in \text{FIRST}(\alpha)$，将产生式 $A \to \alpha$ 填入 $M[A, a]$。
  • 若 $\varepsilon \in \text{FIRST}(\alpha)$，对每个终结符 $b \in \text{FOLLOW}(A)$（包括 \$$），将产生式 A \to \alpha$填入$M[A, b]$。
• 空白项代表语法错误。

5. 预测分析控制程序执行追踪#

分析栈初始化为 [$, S]，输入串为 句子$。

• 设栈顶符号为 $X$，当前输入符为 $a$：
  • 若 $X = a = $$，分析成功并结束。
  • 若 X = a \neq \$$，弹出 X$，输入指针前移。
  • 若 $X$ 是非终结符，查表 $M[X, a]$：
    • 若 $M[X, a] = X \to Y_1 Y_2 \dots Y_k$，弹出 $X$，将右部符号逆序压入栈中（先压入 $Y_k$，最后压入 $Y_1$）。
    • 若为空项，报错。

---

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

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

1. 拓广文法与项目分类#

• 拓广文法：引入新符号 $S'$ 并增加产生式 $S' \to S$，以确保只有一个接受点。
• 项目定义：在产生式右部的任何位置标有圆点“$\cdot$”的产生式。
  • 移进项目：$A \to \alpha \cdot a \beta$（圆点后为终结符）
  • 待约项目：$A \to \alpha \cdot B \beta$（圆点后为非终结符）
  • 归约项目：$A \to \alpha \cdot$（圆点在产生式最右侧）
  • 接受项目：$S' \to S \cdot$

2. CLOSURE 与 GOTO 算法#

• $\text{CLOSURE}(I)$：
  1. 将项目集 $I$ 中的所有项目加入 $\text{CLOSURE}(I)$。
  2. 若项目 $[A \to \alpha \cdot B \beta, a] \in \text{CLOSURE}(I)$ 且 $B$ 是非终结符，则对 $B$ 的每个产生式 $B \to \gamma$，将 $[B \to \cdot \gamma, b]$ 加入其中。
     • 对于 LR(0) 和 SLR(1)：无展望符，加入 $B \to \cdot \gamma$ 即可。
     • 对于 LR(1)：展望符 $b \in \text{FIRST}(\beta a)$。
  3. 重复上述步骤直至不再增大。
• $\text{GOTO}(I, X)$：
  • 收集所有形如 $[A \to \alpha \cdot X \beta, a] \in I$ 的项目，将圆点后移一位得到新项目集 $J = \{ [A \to \alpha X \cdot \beta, a] \}$。
  • 计算并返回 $\text{CLOSURE}(J)$。

3. 冲突判定与文法归属#

在项目集规范族的某状态 $I_i$ 中：

• 移进-归约冲突：存在 $[A \to \alpha \cdot a \beta]$ 与 $[B \to \gamma \cdot]$。
• 归约-归约冲突：存在 $[A \to \alpha \cdot]$ 与 $[B \to \beta \cdot]$。

文法类别	冲突消解准则
LR(0)	状态中不能含有任何冲突项目。
SLR(1)	出现移进-归约冲突时，要求 $a \notin \text{FOLLOW}(B)$；出现归约-归约冲突时，要求 $\text{FOLLOW}(A) \cap \text{FOLLOW}(B) = \emptyset$。
LR(1)	仅当输入字符属于归约项目的展望符集合时才归约。即若有归约 $[A \to \alpha \cdot, a]$，当且仅当输入为 $a$ 时归约。要求移进的输入符与归约展望符互斥。
LALR(1)	合并 LR(1) 中具有相同“核心”（即忽略展望符后完全相同）的状态。合并后不会产生新的移进-归约冲突，但可能引入新的归约-归约冲突。

4. 证明“不是 LR(0) 而是 SLR(1)”的判定步骤#

1. 写出拓广文法与项目集规范族：
   • 添加 $S' \to S$。
   • 逐步计算 $\text{CLOSURE}$ 和 $\text{GOTO}$，画出识别活前缀的 DFA 状态图。
2. 指出 LR(0) 冲突：
   • 仔细审查每一个状态集，寻找冲突状态（例如状态 $I_i$）。
   • 写出具体的冲突项目：形如 $A \to \alpha \cdot a \beta$（移进项目）与 $B \to \gamma \cdot$（归约项目）在同一个状态中，称为移进-归约冲突；或者存在两个归约项目，称为归约-归约冲突。
   • 下结论：因为项目集规范族中存在冲突项目，所以文法不是 $\text{LR}(0)$ 文法。
3. 计算非终结符的 $\text{FOLLOW}$ 集合：
   • 计算发生冲突的归约项目左部符号（例如 $B$ 和 $A$）的 $\text{FOLLOW}$ 集合。
4. 证明 SLR(1) 冲突已消解：
   • 移进-归约冲突消解：检查移进的输入字符 $a$ 是否不属于归约符号的 $\text{FOLLOW}$ 集，即证明 $a \notin \text{FOLLOW}(B)$。
   • 归约-归约冲突消解：检查两个归约符号的后跟字符集是否互斥，即证明 $\text{FOLLOW}(A) \cap \text{FOLLOW}(B) = \emptyset$。
   • 下结论：由于冲突可以通过向后看一个输入符号解决，故文法是 $\text{SLR}(1)$ 文法。

5. SLR(1) 分析表构造规则#

• 移进动作（Shift）：若有项目 $[A \to \alpha \cdot a \beta] \in I_i$，且 $\text{GOTO}(I_i, a) = I_j$，则在格 $M[i, a]$ 中填入移进项 $\text{s}_j$。
• 跳转动作（Goto）：若有项目 $[A \to \alpha \cdot B \beta] \in I_i$，且 $\text{GOTO}(I_i, B) = I_j$，则在跳转栏格 $M[i, B]$ 中填入数字 $j$。
• 归约动作（Reduce）：若有归约项目 $[A \to \alpha \cdot] \in I_i$（且 $A \neq S'$，对应的产生式编号为 $k$），则仅在所有 $a \in \text{FOLLOW}(A)$ 对应的格 $M[i, a]$ 中填入归约项 $\text{r}_k$。
• 接受动作（Accept）：若有项目 $[S' \to S \cdot] \in I_i$，则在格 M[i, \]$中填入接受项$\text{acc}$。

---

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

1. 规范表格样式#

解题时需要建立如下标准的追踪表：

步骤	状态栈	符号栈	输入串	动作 (Action)
1	0	$	accd$	移进 s2
2	0 2	$ a	ccd$	移进 s3

2. 单步操作逻辑#

设当前状态栈顶状态为 $s$，当前输入字符为 $a$：

1. 若 $M[s, a] = \text{s}j$（移进）：
   • 将 $a$ 压入符号栈。
   • 将状态 $j$ 压入状态栈。
   • 指向下一个输入字符。
2. 若 $M[s, a] = \text{r}k$（使用第 $k$ 个产生式 $A \to \beta$ 归约）：
   • 设右部 $\beta$ 的符号个数为 $L$。
   • 从符号栈弹出 $L$ 个符号，从状态栈弹出 $L$ 个状态。
   • 将非终结符 $A$ 压入符号栈。
   • 查看此时状态栈顶的状态 $s'$，计算新状态 $j' = \text{GOTO}[s', A]$，将 $j'$ 压入状态栈。
3. 若 $M[s, a] = \text{acc}$，分析成功，打印接受。

---

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

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

1. 综合属性与继承属性#

• 综合属性 (Synthesized)：节点 $N$ 上的属性值仅通过其子节点或其本身的属性决定。
• 继承属性 (Inherited)：节点 $N$ 上的属性值由其父节点、兄弟节点或其自身的其他属性决定。
• S-属性文法：只含有综合属性。可以在自底向上的分析过程中，在归约时直接计算。
• L-属性文法：可以包含综合属性，且若包含继承属性，则产生式 $A \to X_1 X_2 \dots X_n$ 右部符号 $X_i$ 的继承属性只能依赖于：
  • $A$ 的继承属性。
  • $X_i$ 左侧的兄弟符号 $X_1, \dots, X_{i-1}$ 的属性。

2. 计算步骤#

1. 画出语法树。
2. 标识依赖关系：画出属性依赖图（有向边 $b \to a$ 表示属性 $a$ 依赖于 $b$ 的值）。
3. 进行拓扑排序：找出一条合法的属性计算顺序。
4. 代入数值计算。

---

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

1. 逆波兰式构造#

• 核心思想：操作符紧跟在操作数后面。例如 $a + b \to a b +$；$a * (b + c) \to a b c + *$。
• 括号规则：后缀表达式中不出现任何括号。
• 单目减处理：一元负号为了与双目减号区分，可以记为单目运算符 $\text{minus}$ 或特定的符号（如 @）。

2. 三地址代码 (TAC) 与四元式#

三地址代码每条指令最多包含三个地址（两个操作数，一个结果）。 四元式的标准形式为：(op, arg1, arg2, result)。

• 例题：将 $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)

---

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

1. 布尔表达式的短路计算规则#

• $B_1 \text{ or } B_2$：若 $B_1$ 判定为真，直接跳至真出口，不再执行 $B_2$。
• $B_1 \text{ and } B_2$：若 $B_1$ 判定为假，直接跳至假出口，不再执行 $B_2$。

2. 翻译模板#

• If-Then-Else 模板：

  100: (j<relop>, a, b, TrueLabel)   ; 计算 E
  101: (j, _, _, FalseLabel)
  TrueLabel:                         ; S1 代码
  ...
  (j, _, _, NextLabel)               ; 绕过 else 块
  FalseLabel:                        ; S2 代码
  ...
  NextLabel:                         ; 语句后续

• While-Do 模板：

  BeginLabel:                        ; 记录循环起始位置
  (j<relop>, a, b, LoopBodyLabel)    ; 计算 E
  (j, _, _, NextLabel)
  LoopBodyLabel:                     ; S 代码
  ...
  (j, _, _, BeginLabel)              ; 跳回循环开头
  NextLabel:                         ; 循环退出

---

模块六：代码优化#

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

1. 入口语句（Leader）判定规则#

满足以下三条规则之一的三地址语句即为 Leader：

• 规则 1：三地址代码序列中的第一条语句。
• 规则 2：任何跳转语句（有条件或无条件跳转）的目标语句。
• 规则 3：紧随在跳转语句后面的那一条语句。

2. 划分基本块步骤#

1. 第一步：扫描代码，使用上述三条规则标记出所有的 Leader 语句。
2. 第二步：对每一个 Leader 语句，它的基本块包含该 Leader 本身，以及物理顺序上一直到下一个 Leader 出现之前的所有语句。
3. 第三步：将最后一个 Leader 到代码尾部的所有语句划为最后一个基本块。

3. 构造控制流图 (CFG) 步骤#

1. 每个基本块作为控制流图的一个节点。
2. 绘制有向边 $B_1 \to B_2$（表示控制流可从基本块 $B_1$ 转移到 $B_2$）：
   • 若 $B_1$ 的最后一条语句是跳转语句，且跳转的目标是 $B_2$ 的入口语句，则连一条有向边。
   • 若 $B_1$ 的最后一条语句不是无条件跳转，且在代码物理顺序上 $B_2$ 紧跟在 $B_1$ 之后，则连一条有向边。