企业官网建设流程全解析

简介：这份资源是北京交通大学2021—2022学年第二学期《编译原理》期末试卷（A卷）的PDF电子版，面向正在备考该课程的高校学生与需要复习编译核心知识的自学者。试卷覆盖文法分析、正则表达式与有限自动机、消除左递归与回溯、算符优先文法、LR(0)与SLR(1)分析、语法制导翻译及四元式序列优化等模块，题型从简答到综合计算层层递进，适合用于期末冲刺、章节自测与考点梳理。资源包共1个文件，为PDF格式，大小约396KB，轻量便于打印与移动端查阅。目前已有355人浏览学习，说明其在校内复习场景中具有一定参考价值。读者可借助完整原题还原考试难度与命题风格，对照FIRSTVT/LASTVT集合求解、LR项目集规范族构造、拉链-回填与DAG重构等典型题目检验掌握程度，并据此定位薄弱环节，为编译器设计相关课程与后续系统级编程打下基础。

1. 一份能当“错题本”用的编译原理期末卷：从文法推导到 DAG 重构的完整链路

如果你正在准备编译原理的期末、考研复试，或者刚入职需要补编译器前端的基础，这份北京交通大学 2021—2022 学年第二学期《编译原理》A 卷（课程编号 80L158Q，计算机学院课程组出题）值得打印出来手推一遍。它没有选择题和填空题，七道大题全部要求写求解过程，覆盖文法语言求解、左线性正则文法转正则表达式、消除左递归与回溯、FIRSTVT/LASTVT 与算符优先矩阵、LR(0) 与 SLR(1) 判定、布尔表达式四元式拉链回填、寄存器分配与 DAG 重构。换句话说，一张卷子把“词法—语法—语义—优化—目标代码”这条前端主线串完了。适合谁？适合已经听过课但一到手推就卡壳的人，也适合想拿它当模拟卷检验自己能不能在规定时间内把过程写全的人。下面我按“这题考什么—怎么下手—参数怎么定—哪里容易翻车”拆开讲，你可以对着卷子同步推。

2. 文法语言求解与正则文法转换：从 G[S] 到 DFA 最小化的手推路径

2.1 第一题：求语言并化简，别急着展开产生式

第一题给了两个文法。第一个 G[S]：S→Sef | ABc，A→aA | ε，B→aBb | ε。很多人一上来就从 S 开始硬推，推几层就乱了。正确顺序是先看哪些非终结符能推出空串，再分层求语言。

A→aA | ε 生成的是 a*，B→aBb | ε 生成的是 aⁿbⁿ（n≥0）。ABc 拼起来就是 a* aⁿbⁿ c，即 aᵐbⁿc（m≥n≥0）。但 S 还有 S→Sef 这条右递归，它会在已有串后面不断追加 ef，所以最终语言是 (aᵐbⁿc)(ef)*，其中 m≥n≥0。化简形式就写这个，不要保留 S 的递归写法。

第二个 G[S]：S→aSb | Pb | PdQ，P→bPc | bQc，Q→Qa | a。这题两问。第一问判断句型 abPcdQb 是否规范句型。规范句型要求能从 S 出发通过最右推导得到。先看 abPcdQb 里 P 和 Q 的位置：S→PdQ 可以产生 P 后跟 dQ，但这里 P 后面是 c 不是 d，所以它更可能来自 S→Pb 这条路径的中间形态。手推时把最右推导序列写出来，看每一步是否替换最右非终结符，是则为规范句型，否则不是。第二问画 abQacbb 的语法树，找可归前缀和活前缀。可归前缀是某个句柄的右端，活前缀是规范句型前缀且不包含句柄右侧符号。画树时从根 S 往下，标出每个叶子，然后自底向上找句柄。常见翻车点是活前缀和可归前缀混为一谈——可归前缀一定是活前缀，反之不成立。

2.2 第二题：左线性正则文法转正则表达式，联立方程组的写法有讲究

左线性文法 S→Sa | Sb | Ab，A→Aa | Bb | b，B→Bb | b。要求用联立方程组求正则表达式。左线性对应的是“从右往左”推导，所以设 S、A、B 分别表示从该非终结符能推出的串集合，方程写成：

S = S·a + S·b + A·b A = A·a + B·b + b B = B·b + b

这里 + 表示并，· 表示连接。解 B：B = b·b* = bb*。代入 A：A = A·a + bb*·b + b = A·a + bbb + b。用 Arden 引理，A = (bbb + b)·a*。再代入 S：S = S·(a+b) + A·b，所以 S = A·b·(a+b)*。把 A 展开即可。参数上注意：左线性方程组的递归项在“左边”，右线性在“右边”，写反了结果会差一个方向。

第二问画状态转换图并转右线性文法。左线性文法转状态图时，产生式 A→aB 对应从 A 到 B 的弧标 a，A→a 对应从 A 到终态的弧标 a。画完后把终态当开始、开始当终态反向读，就得到右线性文法。第三问转 DFA 并最小化，用子集构造法，初始状态是开始状态的 ε-闭包（这里没有 ε，直接是开始状态），然后按输入符号 a、b 逐步扩展。最小化用划分法：先按终态/非终态分两组，再检查每组内不同状态在相同输入下是否落到同一组，不是则继续拆。常见坑是子集构造时漏掉空集状态，或者最小化时忘记把不可达状态先删掉。

2.3 第三题：消除左递归与回溯，排序不能乱

G[S]：S→Sd | Aa，A→Sb | Be，B→cA | c。要求按 A1=S、A2=A、A3=B 的顺序消除左递归。S 有直接左递归 S→Sd，用标准公式：S→AaS'，S'→dS' | ε。然后代入 A：A→AaS'b | Be。此时 A 也有直接左递归，继续消除：A→BeA'，A'→aS'bA' | ε。B→cA | c 有公共左因子 c，提取后 B→cB'，B'→A | ε。注意排序必须按题目给的 A1、A2、A3，换顺序结果不同但等价，考试时按题目要求写。

第二问判断回溯。回溯发生在同一非终结符有多个产生式且 FIRST 集相交时。消除后检查每个非终结符的候选式 FIRST 集是否两两不交，若都不交则无回溯。然后判断 LL(1)：要求无左递归、无回溯、且每个非终结符的 FIRST 集与 FOLLOW 集不相交（对于能推出 ε 的）。把 FIRST 和 FOLLOW 表列出来，逐项核对。这里容易错的是 FOLLOW 集计算时漏掉父产生式中紧跟其后的符号，或者忘记把开始符号的 FOLLOW 加上 #。

提示：消除左递归后一定要重新计算 FIRST 和 FOLLOW，不能沿用原文法的集合。

3. 算符优先与 LR 分析：FIRSTVT/LASTVT 集合和 SLR(1) 判定表怎么落地

3.1 第四题：FIRSTVT 和 LASTVT 的迭代求法

算符文法 G[S]：S→aAb，A→TcA | T，T→S | d。要求计算每个非终结符的 FIRSTVT 和 LASTVT，并给出 FIRSTVT 的求解过程。FIRSTVT(P) 的定义是：从 P 出发能推导出的以终结符开头、后面可能跟非终结符的串的首终结符集合。迭代规则三条：

1. 若有 P→a… 或 P→Qa…，则 a ∈ FIRSTVT(P)。
2. 若有 P→Q…，则 FIRSTVT(Q) ⊆ FIRSTVT(P)。
3. 重复直到不再增大。

手推时先列初始：S→aAb 给 a；A→TcA 和 A→T 暂时没有直接终结符开头；T→S 和 T→d 给 d。然后按规则 2 传播：T 的 FIRSTVT 传给 A，A 的传给 S。迭代两到三轮后得到：

LASTVT 对称求，规则类似，看产生式右部最后一个符号。第二问构造算符优先关系矩阵，含 #。三条规则：P→…ab… 或 P→…aQb… 给 a ≖ b；P→…aQ… 给 a ≺ FIRSTVT(Q)；P→…Qb… 给 LASTVT(Q) ≻ b。把矩阵画出来，检查是否有冲突（同一格既有 ≺ 又有 ≻），无冲突则是算符优先文法。常见坑是忘记 # 与开始符号的关系，# ≺ FIRSTVT(S)，LASTVT(S) ≻ #。

3.2 第五题：LR(0) 项目集规范族与 SLR(1) 分析表

拓广文法 G[S']：S'→S，S→SaA | A，A→Ab | d。产生式编号题目已给：1.S'→S，2.S→SaA，3.S→A，4.A→Ab，5.A→d。

构造 LR(0) 有效项目集规范族，从 I0 = closure({S'→·S}) 开始。closure 规则：若项目 A→α·Bβ 且 B 有产生式，则把 B→·γ 加入。然后对每个项目集按符号 X 求 GO(I, X) = closure(所有 A→αX·β)。手推时建议画表格，每行一个状态，列出项目、转移符号、目标状态。I0 包含 S'→·S、S→·SaA、S→·A、A→·Ab、A→·d。按 S 转移得到 I1 = {S'→S·, S→S·aA}，这里出现移进-归约冲突：S'→S· 是接受项，S→S·aA 要移进 a。按 A 转移得到 I2 = {S→A·, A→A·b}，也有冲突。按 d 转移得到 I3 = {A→d·}，无冲突。

判断 LR(0) 还是 SLR(1)：LR(0) 要求每个项目集无冲突，这里 I1 和 I2 都有冲突，所以不是 LR(0)。SLR(1) 用 FOLLOW 集解决冲突：I1 中 S'→S· 对应接受，FOLLOW(S') = {#}；S→S·aA 要移进 a。若 a 不在 FOLLOW(S') 中，则冲突可解。I2 中 S→A· 归约用 FOLLOW(S)，A→A·b 移进 b。计算 FOLLOW(S) 和 FOLLOW(A)，看 b 是否在 FOLLOW(S) 中。若都不冲突，则是 SLR(1)，然后按 SLR(1) 构造分析表：ACTION 表填移进、归约、接受，GOTO 表填状态转移。第三问找活前缀 SaA 的有效项目，就是在项目集中找圆点位置对应 SaA 的项目，可归前缀则要求圆点在最后。

注意：SLR(1) 判定时 FOLLOW 集算错是最常见的失分点，建议先单独把 FIRST 和 FOLLOW 表列出来再填分析表。

4. 语法制导翻译与四元式：布尔表达式拉链回填的完整推演

4.1 第六题：if-else 嵌套 while 的四元式序列

题目语句：if A∨B then if C∧¬D then x=x+y else while b>0 do b=b-1。NXQ 初值 1，优先级：算术 > 关系 > 逻辑，逻辑中 ¬ > ∧ > ∨。要求翻译成四元式并给出拉链-回填过程。

先处理布尔表达式 A∨B。按短路翻译，A∨B 的真出口和假出口分别拉链。常见做法是：

(1) (jnz, A, -, 3) // A 为真跳到 3 (2) (j, -, -, 4) // A 为假跳到 4 (3) (j, -, -, ?) // A 真，整个 A∨B 为真，回填到 then 入口 (4) (jnz, B, -, ?) // 检查 B (5) (j, -, -, ?) // B 假，整个为假

然后回填：第 3 条的目标地址填 then 部分的第一条四元式编号，第 4 条真出口也填同一地址，第 5 条假出口填 else 或 while 的入口。接着处理 C∧¬D，¬D 先翻译成 (jnz, D, -, 假出口) 和 (j, -, -, 真出口)，再与 C 做 ∧。while b>0 do b=b-1 翻译成条件跳转和循环体，最后回填所有拉链。参数上注意 NXQ 每生成一条四元式自增 1，拉链用负号或特定标记表示待回填，回填时把链上所有四元式的目标地址统一改成当前 NXQ。

4.2 第七题：寄存器分配与 DAG 重构

基本块四元式序列：

(1) (+, A, B, T1) (2) (*, C, T1, T2) (3) (/, D, T1, T3) (4) (*, E, F, T4) (5) (/, T2, T3, T5) (6) (+, T5, T4, H)

A、B、C、D、E、F、H 出基本块后活跃，T1~T5 不活跃。R0、R1 可用。寄存器分配策略：从后往前看，H 活跃，T5 和 T4 在 (6) 使用后不再活跃，所以 T5 可占 R0，T4 可占 R1。生成汇编时：

MOV R0, A ADD R0, B ; R0 = T1 MOV R1, C MUL R1, R0 ; R1 = T2 MOV R0, D DIV R0, R0 ; 注意：这里 T1 还在 R0，但 (3) 用 D/T1，需保留 T1

实际手推时要小心 (3) 用 T1，(5) 又用 T2 和 T3，所以 T1 不能过早覆盖。常见做法是给 T1 分配 R0，T2 分配 R1，T3 复用 R0 但先保存 T1 或调整顺序。题目说 T1~T5 不活跃，意味着出基本块后不引用，但块内仍要正确。更稳妥的分配是：T1→R0，T2→R1，T3→R0（此时 T1 已不再被后续使用？检查 (5) 用 T2、T3，不用 T1，所以 T1 在 (3) 后死，R0 可复用给 T3）。生成的目标代码要逐条写，并标注每条指令后的寄存器状态。

DAG 重构：把每个四元式看成节点，公共子表达式合并。这里 T1 = A+B，T2 = CT1，T3 = D/T1，T4 = EF，T5 = T2/T3，H = T5+T4。DAG 中 T1 被 (2) 和 (3) 共用，所以 T1 节点有两个父节点。重构后的四元式序列可以调整计算顺序，比如先算 T4 再算 T5，或者把 T2 和 T3 的计算提前。比较优劣：原序列中 T1 计算一次但被两次使用，DAG 重构后如果寄存器够，可以减少访存；但如果寄存器不够，重构可能增加溢出。常见坑是 DAG 重构时把不活跃临时变量也当成可消除，实际上它们仍要参与计算，只是出块后不引用。

提示：寄存器分配时先画活跃变量分析表，再决定哪个临时变量可以复用寄存器，不要凭感觉分配。

5. 避坑与排查：手推编译原理大题时最容易翻车的五个点

5.1 现象：FIRSTVT 迭代不收敛，集合越算越大

原因：规则 2 的传播方向写反，把 FIRSTVT(P) 传给 Q 而不是 Q 传给 P。解决：记住“从右往左看”，P→Q… 时 Q 的集合并入 P，不是反过来。每轮迭代后对比上一轮，不变则停。

5.2 现象：SLR(1) 分析表出现多重入口，判定为不是 SLR(1)

原因：FOLLOW 集计算时漏掉了 # 或者把 FOLLOW 和 FIRST 混用。解决：先单独列 FIRST 和 FOLLOW 表，FOLLOW(S') 一定含 #，然后逐条检查冲突格。若冲突仍存在，再考虑 LR(1) 或 LALR(1)。

5.3 现象：四元式拉链回填后地址对不上，程序跳转错位

原因：NXQ 初值没按题目设，或者回填时改了 NXQ 但没同步更新链上所有四元式。解决：每生成一条四元式 NXQ 自增 1，拉链用栈或链表记录待回填的四元式编号，回填时统一改目标地址，不要逐条手改。

5.4 现象：DAG 重构后四元式数量没减少，反而多了

原因：把不活跃临时变量当成可删除，或者合并了不该合并的节点（比如 T1 被多次使用但中间有重新定义）。解决：先做活跃变量分析，确认临时变量在块内是否被重新定义，再决定是否合并。DAG 只合并值相同的节点，不合并变量。

5.5 现象：消除左递归后文法语言变了

原因：消除直接左递归时公式用错，比如 S→Sd | Aa 应得 S→AaS'，S'→dS' | ε，有人写成 S→AaS' | ε。解决：对照标准公式，消除后检查新文法能否推出原文法的所有串，至少手推两个短串验证。

6. 把这张卷子用成“活页错题本”：我的二刷方法和一个具体技巧

第一遍手推时，我建议按题型限时：第一、二题各 15 分钟，第三、四题各 20 分钟，第五题 25 分钟，第六、七题各 25 分钟。推完不对答案，先自己标记“卡住的地方”——是 FIRSTVT 迭代不熟，还是拉链回填地址对不上。第二遍只推卡住的题，并且强制写出每一步的依据，比如“因为 P→Qa…，所以 a ∈ FIRSTVT(P)”。第三遍把七道题的知识点映射到教材章节，比如第五题对应 LR 分析，第七题对应代码优化，然后找同类型题加练。

一个具体技巧：用表格管理 FIRSTVT/LASTVT 和 FOLLOW 集。每次手推前先画一张空表，列非终结符，行写迭代轮次，每轮只填新增元素。这样能直观看到集合是否收敛，也能在考场上快速检查。我一般还会在表格旁边写“规则 1/2/3”的编号，每填一个元素标出来源，回查时不用重新推。

另一个技巧是四元式拉链回填时用“地址占位符”。比如先写 (3) (j, -, -, _)，下划线表示待回填，所有待回填的四元式编号记在草稿纸角落，最后统一替换。这样比边生成边改地址更不容易乱。DAG 重构时，先画节点图再写四元式，节点图里用圆圈标变量、方框标运算，公共子表达式用双线连接，一眼能看出哪些节点被多次引用。

从那以后我每次做编译原理大题，都强制先画集合表和活跃变量表，再动笔写推导。这个习惯让我在考场上少丢了很多“过程分”。希望帮到你。

本文还有配套的精品资源，点击获取