编译原理计算大题（主观题）题型汇总#

---

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

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

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

• 题目 1：写一个文法，使其语言是偶数集，且每个偶数不以 $0$ 开头（除了单零 $0$ 本身）。
• 题目 2：构造一个只能产生奇数（且多位数首位不为 0）的十进制数文法。
• 题目 3：给定语言 $L_1 = \{a^n b^n c^i \mid n \ge 1, i \ge 0\}$，构造其文法。
• 题目 4：给定语言 $L_2 = \{a^i b^n c^n \mid n \ge 1, i \ge 0\}$，构造其文法。
• 题目 5：给定语言 $L_3 = \{a^n b^n a^m b^m \mid n, m \ge 0\}$，构造其文法。
• 题目 6：给定语言 $L_4 = \{1^n 0^m 1^m 0^n \mid n, m \ge 0\}$，构造其文法。
• 题目 7：构造一个文法 $G$，使得 $L(G) = \{a^n b^n \mid n \ge 1\}$。

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

针对给定的文法和特定句子，给出完整的推导步骤，并画出相应的语法树。

• 题目 1：已知算术表达式文法 $G(E)$ 为： $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$ 和 $i*(i+i)$ 的最左推导和最右推导，并给出 $i+i+i$、$i+i*i$ 和 $i-i-i$ 的语法树。
• 题目 2：考虑如下表格结构文法 $G_2$： $S \to a \mid \wedge \mid (T) \ , \ T \to T, S \mid S$ 给出句子 $(a, (a, a))$ 和 $(((a, a), \wedge, (a)), a)$ 的最左和最右推导。

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

针对文法的某一特定推导句型，指出其中的短语、直接短语和句柄。

• 题目 1：考虑文法 $G_1$： $E \to E + T \mid T \ , \ T \to T * F \mid F \ , \ F \to (E) \mid i$ 证明 $E + T * F$ 是它的一个句型，并指出这个句型的所有短语、直接短语和句柄。
• 题目 2：已知文法 $G$： $T \to (F) \ , \ F \to T + F \mid T \ , \ T \to t \mid \varepsilon$ 给出句型 $((t)+T)$ 的短语、直接短语与句柄。

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

证明给定的文法是二义性文法。

• 题目 1：证明下面的文法是二义的： $S \to iSeS \mid iS \mid i$
• 题目 2：证明算术表达式文法 $E \to E + E \mid E * E \mid (E) \mid i$ 是二义的。

---

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

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

利用正规式的代数恒等律（或克林闭包定义），证明两个正规式等价。

• 题目 1：证明恒等式：$(AB)^*A = A(BA)^*$。
• 题目 2：证明恒等式：$(A^*)^* = A^*$。
• 题目 3：证明恒等式：$A^* = \varepsilon \mid A A^*$。
• 题目 4：证明：方程 $A = b \mid aA$ 当且仅当 $A = a^*b$（Arden引理）。

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

设计能够描述指定语言规则的正规表达式。

• 题目 1：给出以 01 结尾的二进制数串的正规式。
• 题目 2：给出能被 $5$ 整除的十进制整数的正规式。
• 题目 3：给出包含奇数个 $1$ 或奇数个 $0$ 的二进制数串的正规式。

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

使用子集构造法将 NFA 确定化为 DFA，或使用分割法对 DFA 进行最小化。

• 题目 1：构造正规式 $1(0 \mid 1)^*101$ 相应的 NFA，并使用子集构造法将其确定化为 DFA，给出状态转移表和状态图。
• 题目 2：将如下 NFA 确定化：初态和接受状态均为 $0$；$\delta(0, a) = \{0, 1\}$，$\delta(0, b) = \{1\}$，$\delta(1, a) = \{0\}$。
• 题目 3：将如下 DFA 进行最小化化简：
  • 初始状态：$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$。

---

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

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

改写文法，消除其中包含的直接左递归、间接左递归或提取左因子，为 LL(1) 分析做前置准备。

• 题目 1：考虑下面文法 $G_1$： $S \to a \mid \wedge \mid (T) \ , \ T \to T, S \mid S$ 消去 $G_1$ 的左递归。
• 题目 2：考虑下面文法 $G_2$： $S \to (L) \mid aS \mid a \ , \ L \to L, S \mid S$ 消去 $G_2$ 所有的左递归和回溯。

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

针对改写后无左递归的文法，为每个非终结符编写不带回溯的递归下降子程序伪代码。

• 题目 1：对于产生式 $S \to a \mid \wedge \mid (T), T \to S T', T' \to , S T' \mid \varepsilon$，写出不带回溯的递归下降子程序。
• 题目 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}$$ 写出该文法的递归下降分析程序。

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

计算文法各非终结符的 $\text{FIRST}$ 与 $\text{FOLLOW}$ 集合，证明文法为 $\text{LL}(1)$，并构造其预测分析表。

• 题目 1：计算下面改写后文法各非终结符的 $\text{FIRST}$ 与 $\text{FOLLOW}$ 集合，证明其是 $\text{LL}(1)$ 文法，并构造其预测分析表： $S \to (L) \mid aS' \ , \ S' \to S \mid \varepsilon \ , \ L \to S L' \ , \ L' \to , S L' \mid \varepsilon$
• 题目 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}$$ 构造其 $\text{LL}(1)$ 预测分析表，并给出对句子 $id--id((id))$ 的分析控制过程。

---

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

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

构造 LR 项目集规范族、活前缀识别 DFA，判定文法类别（LR(0) / SLR(1) / LALR(1) / LR(1)）并构造相应的分析驱动表。

• 题目 1：考虑文法 $S' \to E, E \to aA, A \to cA \mid d$：
  1. 列出该文法的所有 $\text{LR}(0)$ 项目。
  2. 构造 $\text{LR}(0)$ 项目集规范族及识别活前缀的 DFA。
  3. 判定该文法是否是 $\text{LR}(0)$ 文法，若是，构造它的 $\text{LR}(0)$ 分析表。
• 题目 2：证明下面文法是 $\text{SLR}(1)$ 的但不是 $\text{LR}(0)$ 的，并构造它的 $\text{SLR}$ 分析表： $S \to A \ , \ A \to Ab \mid bBa \ , \ B \to aAc \mid a \mid aAb$
• 题目 3：考虑文法 $S \to AS \mid b, A \to SA \mid a$：
  1. 构造这个文法的 $\text{LR}(0)$ 项目集规范族及识别活前缀的 DFA。
  2. 这个文法是 $\text{SLR}$ 的吗？若是，构造出它的 $\text{SLR}$ 分析表。
  3. 判定这个文法是 $\text{LALR}$ 还是 $\text{LR}(1)$ 文法。
• 题目 4：证明文法 $G$：$S \to Ab \mid aAc \ , \ A \to a$ 不是 $\text{LR}(0)$ 文法而是 $\text{SLR}(1)$ 文法，并给出 $\text{SLR}(1)$ 分析表。

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

针对给定的文法分析表，给出输入句子在分析栈上的完整移进-归约执行步骤。

• 题目 1：利用已构造的 $\text{LR}(0)$ 分析表，给出句子 accd 的移进-归约分析详细步骤表格（写出序号、状态栈、符号栈、输入串、采取的 Action 动作）。
• 题目 2：给出句子 $(((a, a), \wedge, (a)), a)$ 在文法 $S \to a \mid \wedge \mid (T), T \to T, S \mid S$ 下的规范归约过程及每一步的句柄。

---

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

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

设计 SDD 语义方程，或者画出指定句子的语法分析树并计算其属性。

• 题目 1：设计一个全综合属性的 S-属性文法，能够自底向上计算二进制小数（例如 101.101）对应的十进制数值，给出产生式和对应的语义规则。
• 题目 2：设有文法产生式：$S \to aAb \ , \ A \to bA'c \ , \ A' \to \varepsilon$。其语义规则定义了长度计算 $S.\text{len} = A.\text{len} + 2, A.\text{len} = A'.\text{len} + 2, A'.\text{len} = 0$。求句子 a bbcc b 对应的 $S.\text{len}$ 值和属性计算步骤。

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

进行算术表达式或布尔表达式的中间代码表示形式转换。

• 题目 1：写出表达式 $a * ( - b + c )$ 和 $\text{not } A \text{ or not } ( C \text{ or not } D )$ 的逆波兰（后缀）表示。
• 题目 2：给出赋值语句 $A := B * ( - C + D )$ 自底向上语法规约过程所生成的临时变量与三地址代码序列。

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

将带有条件/循环控制流的高级语言程序段翻译为等价的四元式代码序列（采用短路计算，指定起始标号）。

• 题目 1：把程序段 while a < b do if c < d then x := y + z 翻译成四元式代码，假设起始地址为 100，采用短路计算。
• 题目 2：将带有嵌套控制流的程序段：

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

  翻译成四元式序列，假设语句标号从 $100$ 开始，布尔表达式采用短路计算。

---

模块六：代码优化#

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

分析程序的 Leader 入口语句，划分基本块，并画出控制流图（CFG）。

• 题目：对下面的程序，确定所有基本块的入口语句，将程序划分为基本块，并画出其控制流图：

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