简介这份资源是北京交通大学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 | ABcA→aA | εB→aBb | ε。很多人一上来就从 S 开始硬推推几层就乱了。正确顺序是先看哪些非终结符能推出空串再分层求语言。A→aA | ε 生成的是 a*B→aBb | ε 生成的是 aⁿbⁿn≥0。ABc 拼起来就是 a* aⁿbⁿ c即 aᵐbⁿcm≥n≥0。但 S 还有 S→Sef 这条右递归它会在已有串后面不断追加 ef所以最终语言是 (aᵐbⁿc)(ef)*其中 m≥n≥0。化简形式就写这个不要保留 S 的递归写法。第二个 G[S]S→aSb | Pb | PdQP→bPc | bQcQ→Qa | a。这题两问。第一问判断句型 abPcdQb 是否规范句型。规范句型要求能从 S 出发通过最右推导得到。先看 abPcdQb 里 P 和 Q 的位置S→PdQ 可以产生 P 后跟 dQ但这里 P 后面是 c 不是 d所以它更可能来自 S→Pb 这条路径的中间形态。手推时把最右推导序列写出来看每一步是否替换最右非终结符是则为规范句型否则不是。第二问画 abQacbb 的语法树找可归前缀和活前缀。可归前缀是某个句柄的右端活前缀是规范句型前缀且不包含句柄右侧符号。画树时从根 S 往下标出每个叶子然后自底向上找句柄。常见翻车点是活前缀和可归前缀混为一谈——可归前缀一定是活前缀反之不成立。2.2 第二题左线性正则文法转正则表达式联立方程组的写法有讲究左线性文法 S→Sa | Sb | AbA→Aa | Bb | bB→Bb | b。要求用联立方程组求正则表达式。左线性对应的是“从右往左”推导所以设 S、A、B 分别表示从该非终结符能推出的串集合方程写成S S·a S·b A·b A A·a B·b b B B·b b这里 表示并· 表示连接。解 BB b·b* bb*。代入 AA A·a bb*·b b A·a bbb b。用 Arden 引理A (bbb b)·a*。再代入 SS S·(ab) A·b所以 S A·b·(ab)*。把 A 展开即可。参数上注意左线性方程组的递归项在“左边”右线性在“右边”写反了结果会差一个方向。第二问画状态转换图并转右线性文法。左线性文法转状态图时产生式 A→aB 对应从 A 到 B 的弧标 aA→a 对应从 A 到终态的弧标 a。画完后把终态当开始、开始当终态反向读就得到右线性文法。第三问转 DFA 并最小化用子集构造法初始状态是开始状态的 ε-闭包这里没有 ε直接是开始状态然后按输入符号 a、b 逐步扩展。最小化用划分法先按终态/非终态分两组再检查每组内不同状态在相同输入下是否落到同一组不是则继续拆。常见坑是子集构造时漏掉空集状态或者最小化时忘记把不可达状态先删掉。2.3 第三题消除左递归与回溯排序不能乱G[S]S→Sd | AaA→Sb | BeB→cA | c。要求按 A1S、A2A、A3B 的顺序消除左递归。S 有直接左递归 S→Sd用标准公式S→AaSS→dS | ε。然后代入 AA→AaSb | Be。此时 A 也有直接左递归继续消除A→BeAA→aSbA | ε。B→cA | c 有公共左因子 c提取后 B→cBB→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→aAbA→TcA | TT→S | d。要求计算每个非终结符的 FIRSTVT 和 LASTVT并给出 FIRSTVT 的求解过程。FIRSTVT(P) 的定义是从 P 出发能推导出的以终结符开头、后面可能跟非终结符的串的首终结符集合。迭代规则三条若有 P→a… 或 P→Qa…则 a ∈ FIRSTVT(P)。若有 P→Q…则 FIRSTVT(Q) ⊆ FIRSTVT(P)。重复直到不再增大。手推时先列初始S→aAb 给 aA→TcA 和 A→T 暂时没有直接终结符开头T→S 和 T→d 给 d。然后按规则 2 传播T 的 FIRSTVT 传给 AA 的传给 S。迭代两到三轮后得到非终结符FIRSTVTLASTVTS{a, d}{b, d}A{a, d}{b, d}T{a, d}{b, d}LASTVT 对称求规则类似看产生式右部最后一个符号。第二问构造算符优先关系矩阵含 #。三条规则P→…ab… 或 P→…aQb… 给 a ≖ bP→…aQ… 给 a ≺ FIRSTVT(Q)P→…Qb… 给 LASTVT(Q) ≻ b。把矩阵画出来检查是否有冲突同一格既有 ≺ 又有 ≻无冲突则是算符优先文法。常见坑是忘记 # 与开始符号的关系# ≺ FIRSTVT(S)LASTVT(S) ≻ #。3.2 第五题LR(0) 项目集规范族与 SLR(1) 分析表拓广文法 G[S]S→SS→SaA | AA→Ab | d。产生式编号题目已给1.S→S2.S→SaA3.S→A4.A→Ab5.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 xxy else while b0 do bb-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 b0 do bb-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 可占 R0T4 可占 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 分配 R0T2 分配 R1T3 复用 R0 但先保存 T1 或调整顺序。题目说 T1~T5 不活跃意味着出基本块后不引用但块内仍要正确。更稳妥的分配是T1→R0T2→R1T3→R0此时 T1 已不再被后续使用检查 (5) 用 T2、T3不用 T1所以 T1 在 (3) 后死R0 可复用给 T3。生成的目标代码要逐条写并标注每条指令后的寄存器状态。DAG 重构把每个四元式看成节点公共子表达式合并。这里 T1 ABT2 CT1T3 D/T1T4 EFT5 T2/T3H T5T4。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→AaSS→dS | ε有人写成 S→AaS | ε。解决对照标准公式消除后检查新文法能否推出原文法的所有串至少手推两个短串验证。6. 把这张卷子用成“活页错题本”我的二刷方法和一个具体技巧第一遍手推时我建议按题型限时第一、二题各 15 分钟第三、四题各 20 分钟第五题 25 分钟第六、七题各 25 分钟。推完不对答案先自己标记“卡住的地方”——是 FIRSTVT 迭代不熟还是拉链回填地址对不上。第二遍只推卡住的题并且强制写出每一步的依据比如“因为 P→Qa…所以 a ∈ FIRSTVT(P)”。第三遍把七道题的知识点映射到教材章节比如第五题对应 LR 分析第七题对应代码优化然后找同类型题加练。一个具体技巧用表格管理 FIRSTVT/LASTVT 和 FOLLOW 集。每次手推前先画一张空表列非终结符行写迭代轮次每轮只填新增元素。这样能直观看到集合是否收敛也能在考场上快速检查。我一般还会在表格旁边写“规则 1/2/3”的编号每填一个元素标出来源回查时不用重新推。另一个技巧是四元式拉链回填时用“地址占位符”。比如先写 (3) (j, -, -, _)下划线表示待回填所有待回填的四元式编号记在草稿纸角落最后统一替换。这样比边生成边改地址更不容易乱。DAG 重构时先画节点图再写四元式节点图里用圆圈标变量、方框标运算公共子表达式用双线连接一眼能看出哪些节点被多次引用。从那以后我每次做编译原理大题都强制先画集合表和活跃变量表再动笔写推导。这个习惯让我在考场上少丢了很多“过程分”。希望帮到你。本文还有配套的精品资源点击获取