我第一次认真刷编译原理习题不是期末前而是毕业后准备面试时。那时候翻教材感觉什么都懂正则、NFA、LL(1)、LR(1)、四元式名词背得滚瓜烂熟。结果拿到题一上手要么不知道从哪步开始推要么推出一个漏洞百出的状态图差点被打击到怀疑自己。后来被逼着喂了上百道题才发现这门课真正考的不是记忆而是「在一张白纸上把每一步推演完整」的能力。这篇文章把我从期末到面试、从课后题到上机实验的高频考点整理成了一份可以直接照着刷的路线重点讲清楚每类题为什么要这样做、坑在哪里、以及怎么判断自己是真的会了。1. 为什么刷编译原理习题比看教材更管用1.1 编译原理考的不是记忆而是推演先说我观察到的一个现象很多同学看编译原理教材时觉得每个算法都看得懂。Thompson 构造不就是拼接几个状态吗子集构造法不就是求 ε-闭包吗LR 分析表不就是查表吗但一合上书做题第一问「构造 NFA」就卡住了。原因在于编译原理的算法是「过程性知识」它不像历史事件那样记住结论就行而是要求你在给定输入上完整执行一遍算法流程。这个过程一旦中间走错一步后面全盘皆错。习题的作用就是逼你把「看懂」变成「会做」把教材里省略的细节暴露出来。比如算 First 集合教材告诉你「反复迭代直到集合不再变化」。但实际做题时是先看右部第一个符号还是先把所有终结符候捕捉完遇到 ε 产生式怎么向后传递这些问题只有亲手算过两三道带陷阱的题目才会真正建立直觉。刷题不是题海战术而是在有限几类典型题上把每个细节磨到条件反射。1.2 刷题前先建好四层知识骨架我建议在刷题前先把编译过程拆成一个四层骨架这样每道题你都能立刻定位它在考哪一层。第一层是词法分析输入是字符流输出是 Token 流核心工具是正则表达式、NFA、DFA。第二层是语法分析输入是 Token 流输出是语法树核心工具是上下文无关文法、LL 分析、LR 分析。第三层是语义分析与中间代码生成输入是语法树输出是中间表示核心工具是属性文法、语法制导翻译、三地址码。第四层是优化与目标代码生成输入是中间代码输出是汇编或机器代码核心工具是基本块、DAG、寄存器分配。绝大部分考试和面试题都围绕前三层展开第一层和第二层的题量最大。我后面每个章节会对应一层来展开同时补上我在刷题时踩过的那些坑。2. 词法分析题从正则到 DFA 是一条完整的流水线2.1 正则表达式的运算符优先级是基本功词法分析题的第一个坎其实是正则表达式的读法。教材通常一笔带过但习题里经常出现类似a|bc*到底是(a|b)(c*)还是a | (bc*)的问题。正则运算符的优先级从高到低依次是括号()、闭包*?、连接、选择|。所以a|bc*实际上等价于a | (b(c*))而不是(a|b)(c*)。刷题时遇到这类易混点建议把每个待解析的正则表达式先用括号完全括起来再开始构造 NFA。这一步看似多余却能避免后面很多低级错误。还有一个小陷阱a*和(a*)*是等价的但(a|b)*与a*b*不等价前者能识别任意长度的 a、b 混合串后者只能识别若干 a 后跟若干 b。考试时很喜欢用这种等价性来设计判断题。2.2 一个经典题从(a|b)*abb到最小化 DFA 的完整演算(a|b)*abb几乎是每本教材和每套试卷都会出现的经典题它能串起 Thompson 构造、子集构造法、DFA 最小化三个考点。我带你完整走一遍同时标出最容易失分的环节。第一步用 Thompson 构造 NFA。构造(a|b)*部分时需要反复使用 ε 转移实现选择、闭包和拼接最终得到下面这个 NFA数字代表状态ε 代表团转移0 --ε-- 10 --ε-- 71 --a-- 22 --ε-- 33 --ε-- 43 --ε-- 74 --b-- 55 --ε-- 66 --ε-- 16 --ε-- 77 --a-- 88 --b-- 99 --b-- 10接受状态很多人在这一步把(a|b)*的闭环画错了导致后面子集构造时状态集差一两个元素。检验方法是从初始状态 0 沿 ε 闭包和识别路径出发能否回到子图的开头形成循环。第二步用子集构造法转 DFA。先求初始状态 A ε-closure({0}) {0,1,2,3,4,6,7}。然后分别对 a、b 求转移得到下表DFA状态输入a输入bABCBBDCBDDBGGBC其中 G 包含原 NFA 的接受状态 10所以 G 是 DFA 的接受状态。这里有个常见错误子集构造时容易忘记对每个新状态求 ε-闭包导致状态集缺项。我第一次做时就把 C 状态里漏掉了从 5 回跳的 ε 路径。第三步DFA 最小化。初始划分为终态 {G} 和非终态 {A,B,C,D}。非终态集合中D 在输入 b 时进入 G而 A、B、C 在输入 b 时进入 D 或 C因此分裂出 {D}。再对 {A,B,C} 细分B 和 C 在输入 b 时都进入 D输入 a 时都进入 B所以合并为同一状态。最终得到只有 4 个状态的 DFA状态输入a输入b1初始22223324接受422最小化后状态 1 识别若干 a、b 的混合串状态 3 遇到 b 进入接受状态 4之后任何字符都回到状态 2。每一步都要注意最小化看的不是状态名而是「在当前划分下转移是否指向同一个块」。这个题型只要完整演算三遍基本能拿满分。2.3 词法分析实验题的代码骨架与隐蔽深坑除了手算题很多学校还会布置词法分析上机实验吉林大学和哈尔滨工业大学公开课件里都有对应的实验要求。实验的核心是写一个识别 Token 流的程序我建议按照下面的骨架组织维护一个全局的输入缓冲区和当前字符指针。按类别定义保留字表如 if、else、while、运算符表如、-、*、、界符表如(、)、;。主循环里跳过空白符和注释然后进入最长匹配流程能构成标识符的字符一路读下去能构成数字的字符一路读下去读到无法继续的字符时回退。查保留字表如果在表里则输出「保留字名字」否则输出「标识符名字」。运算符和界符同样按最长匹配原则处理比如不能拆成和。实验里最容易踩的坑有三个。第一个是「关键字识别时机」先按标识符规则读完整的单词再去查保留字表而不是每读一个字符就查一次否则ifx会被误判为关键字if加标识符x。第二个是「缓冲区回退」读取超前导致多读了一个字符时必须正确回退否则下一个 Token 会错位。第三个是「注释和字符串里的特殊字符」跳过注释时要注意/*和*/的嵌套或跨行处理字符串时要考虑转义。我在实验里用了一个很笨但很有效的方法把所有待识别的语言模式写成一个正则表达式表然后基于 DFA 模拟器统一识别。虽然代码量多了一点但逻辑清晰后续加新 Token 只需要加一行正则表达式。3. 语法分析习题LL(1) 与 LR 系列是两道分水岭3.1 First 与 Follow 集合的计算顺序是丢分重灾区语法分析题的第一关永远是 First 和 Follow 集合。很多同学栽在顺序上先算 Follow 再算 First或者 Follow 只算一遍就不迭代了。正确顺序是必须先算完所有非终结符的 First再算 Follow因为 Follow 的定义依赖于 First。以一个经典文法为例E → T EE → T E | εT → F TT → * F T | εF → ( E ) | idFirst 集合的最终结果如下非终结符First 集合E{ (, id }E{ , ε }T{ (, id }T{ *, ε }F{ (, id }计算时注意E → T E中 T 的 First 是{(, id}所以 E 的 First 就是 T 的 FirstT → ε说明 ε 属于 T 的 First但它不能直接归入 T 的 First因为 T 在 T 的右部不一定推导为空。判断一个非终结符的 First 是否含 ε需要看向右推导能否达空。Follow 集合结果如下非终结符Follow 集合E{ #, ) }E{ #, ) }T{ , #, ) }T{ , #, ) }F{ *, , #, ) }Follow 计算的循环是考试丢分重灾区。我的记忆口诀是开始符号把#放进去右部里「一个非终结符后面跟着一个符号」就把这个符号的 First 加入ε 除外「后面跟着的东西能推导出 ε」就把左部非终结符的 Follow 加进去。这里要注意F → (E)让 E 的 Follow 里必须有)E → T E让 T 的 Follow 里必须有同时由于 E 可推导出 ε还要把 Follow(E) 即#)加入 Follow(T)。3.2 预测分析表判 LL(1) 文法的标准流程算出 First 和 Follow 后紧接着就是构造预测分析表和判断 LL(1) 文法。对每个产生式A → α只要α不能推导出 ε就把这个产生式填到所有 First(α) 中的终结符对应的表格单元如果α能推导出 ε就把产生式填到 Follow(A) 中所有终结符对应的单元。对上面那个文法预测分析表的核心部分如下非终结符*()id#EE→TEE→TEEE→TEE→εE→εTT→FTT→FTTT→εT→*FTT→εT→εFF→(E)F→id判 LL(1) 的标准是表格每个单元格里至多一个产生式。这个文法每个单元格都唯一所以是 LL(1) 文法。这里最容易被忽略的坑是判断 LL(1) 时不能只看有没有「冲突」还要检查同一个非终结符的两个不同产生式是否在某个终结符上都能填入。只要出现一个单元格里有两条产生式这个文法就不是 LL(1)。考试时经常这样设计文法本身是二义的或者含有左公因子导致预测分析表冲突。3.3 LR(0)、SLR 与 LR(1)冲突处理才是考察重点LR 系列的题比 LL 更抽象很多同学背了构造步骤但不知道为什么要引入那么多版本。其实只要搞清楚一件事LR(0) 能力最弱、SLR 次之、LR(1) 最强它们之间的差别在于「归约时看什么符号」。LR(0) 只看当前状态只要状态里有「圆点在最右端」的项目就归约不管下一个输入符号是什么所以冲突很多。SLR 用 Follow 集合来区分归约时机冲突少一些但 Follow 集合是「所有可能出现的位置」的并集仍然可能过宽。LR(1) 向前看符号更精确能力最强但状态数多、构造复杂。经典考题是一个容易产生 SLR 冲突的文法S → L RS → RL → * RL → idR → L这个文法在 LR(0) 项目集里会出现移进-归约冲突SLR 分析时因为 Follow(L) 包含导致在某些状态中遇到时既想移进又想归约冲突无法解决。LR(1) 通过向前看符号区分能正确处理。这个例子我建议完整地做一遍 LR(1) 项目族体会「向前看符号如何由产生式左侧的 Follow 集合决定」——这是最见功底的一道题。在做 LR 习题时我的步骤固定为先写增广文法S → S然后从S → ·S开始求闭包每遇到一个运算符就生成新状态最后检查每个状态是否同时含「可归约项目」和「移进项目」或「两个可归约项目」如果有就是冲突状态。这个流程做熟之后LR(0)、SLR、LR(1) 之间的差异自然就清晰了。4. 语义分析与中间代码大题从不会缺席4.1 逆波兰式与四元式的互相转换语义和中间代码部分最基础的题型是逆波兰式和四元式。逆波兰式就是后缀表达式运算符跟在操作数后面。转换规则是用栈保存运算符遇到操作数直接输出遇到运算符时把栈顶优先级不低于当前运算符的运算符依次弹出。括号不输出但控制出栈。举个例子中缀表达式(ab)*c - (ab)/e转换成逆波兰式ab表示ab乘以c得到abc*将(ab)/e转成abe/相减得到abc*abe/-转换成四元式时每个运算都用临时变量承载结果序号运算符参数1参数2结果1abt12*t1ct23abt34/t3et45-t2t4t5这个例子里ab被计算了两次在 DAG 优化章节里正好用来做对比优化后四元式可以降到 4 条。考试中经常要求你同时写出逆波兰式、三元式、四元式本质上考的是同一个表达式树的线性化表达练熟一个另外两个就是套壳。4.2 DAG 化简与公共子表达式DAG有向无环图的题目主要考两个能力一是根据运算序列构造 DAG二是从 DAG 还原优化后的代码。它的核心思想是共享公共子表达式只算一次。看这样一个代码序列t1 b * ct2 b * c dt3 b * c f对应的 DAG 中b * c是一个节点t2、t3分别在这个节点上做加法。优化后得到t1 b * ct2 t1 dt3 t1 f做这类题要注意当某个变量被重新赋值后它原本对应的叶子节点就不能继续复用了必须新建叶子节点。这是 DAG 的隐藏考点题目常在这里设计陷阱。比如a b c; b b - d; c c d; a b c中第一行和第四行的b c在逻辑上不是同一个b和c因为中间发生了重定义不能直接复用。考试时如果题目没有特殊说明默认按「赋值产生新值」处理别因为复用而丢分。4.3 属性文法与回填实验题的隐藏考点属性文法题的核心是两类属性综合属性和继承属性。综合属性由子节点的属性计算而来自底向上传播继承属性由父节点或兄弟节点的属性传下来自顶向下传播。典型考题是给一个文法让你写语法制导定义。比如表达式文法E → E1 TE.val E1.val T.valE → TE.val T.val这里E.val就是综合属性它由子表达式求值后逐层上传。继承属性的经典例子是声明语句D → T L其中类型属性T.type要传给L.in再由L给每个标识符登记类型。和属性文法紧密相关的是「回填」概念在三地址码生成题中非常高频。回填的意思是跳转指令的目标地址在翻译时可能还不知道先留空等跳转目标确定后再回头填上。比如翻译if a b or c d then x : y 1 else x : y - 1时生成的三地址码可能是100if a b goto 103101if c d goto 103102goto 106103t1 : y 1104x : t1105goto 107106t2 : y - 1107x : t2第 100 句和第 101 句的目标 103 是在翻译右部时才确定的这就是回填。许多同学做中间代码题时只关注表达式的四元式忽略控制流语句的跳转地址导致整段代码不完整。我在实验里做语法树到三地址码的转换时特意维护了一个「未填地址链表」等目标标签确定后再统一回填效果非常好。5. 期末简答与面试题答法也是有套路的5.1 概念辨析题的回答框架简答题是期末的重灾区因为很多人以为「大概知道」就行。但判卷是按点给分的我总结了一个固定答题框架先给定义再说动机接着配例子最后做比较。以「编译器为什么要区分词法分析和语法分析」为例定义层面词法分析把字符流识别成 Token 流语法分析把 Token 流按文法组织成语法树。动机层面有四点一是简化设计每个阶段只处理一类问题二是提高效率词法分析可以用专门的有限自动机高效扫描三是增强可移植性不同的词法规则不影响语法层四是便于工具化lex 和 yacc 分工明确。例子层面对if (a 0) b 1;词法分析先识别出if、(、a、、0、)、b、、1、;这些 Token语法分析再判断这些 Token 能否按照 if 语句的文法形成合法结构。这种「定义 动机 例子」的结构答任何概念题都能保住基础分。如果还有余力再加一句「如果合并会怎样」的反面论述分数会更高。5.2 面试里反复出现的那几个编译原理问题面试题和期末简答最大的不同是面试官喜欢从具体场景切入考察你能否把原理用白话说清楚。我整理几个高频问题。第一个是「LL(1) 和 LR(1) 的区别」。不要背教材定义可以这样答LL 是自顶向下推导扫描时从左到右读输入产生式从左到右展开向前看 1 个符号LR 是自底向上归约从左到右读输入根据状态和向前看符号决定移进还是归约。LL 更直观、写递归下降分析器很容易但文法要求高LR 能力更强、能处理更多文法但分析表构造复杂。第二个是「什么是二义性文法怎么处理」。先举经典例子if E1 then if E2 then S1 else S2中 else 可以和最近的 if 配对也可能和最远的 if 配对。处理办法是引入明确规则比如规定 else 与最近的 then 配对或者修改文法消除二义性。第三个是「编译器常用的优化有哪些」。常见回答包括常量传播、常量折叠、死代码消除、公共子表达式消除、循环不变量外提、强度削减等。最好能各配一个小例子比如x 3 * 4直接优化成x 12if (0) { ... }整段删除多个循环内不变的计算提到循环外。面试时不需要背诵《编译原理》第三版答案里全部优化列表但每个优化都能用自己的话解释清楚是很明显的加分项。6. 刷题路线、资料选择和时间分配6.1 教材、答案和高校课件怎么搭配市面上的核心教材主要看龙书《编译原理》和虎书《现代编译原理》。龙书偏体系化习题也难适合按章节刷虎书更接近真实工程语言实现细节多适合做实验和面试准备。本科教材如果学校里指定了就以指定教材为准课后题必须做一遍因为期末考试经常改动课后题的数字和文法符号。这里说明一下很多人问过的「第三版答案」。我的态度是可以用但必须先自己完整推演再对答案不要做一题看一题。我见过不少同学对着答案刷题结果考试时 Load 的是「答案的样子」而不是「算法的过程」一换数字就不会做了。答案的真正价值不是告诉你这个题选什么而是帮你发现自己是在哪一步跳了逻辑。另外要注意部分课后题答案因为版本不同可能有疏漏如果发现自己的结果和答案不一致先别急着改自己重新演算一遍确认自己是不是有道理。高校课件的使用思路不同像吉林大学、哈尔滨工业大学公开的课件通常把知识点压缩成「考试题型」导向常考的细节会反复强调。我的用法是先把课件里的例题做一遍再看课件里强调的「易错点」最后如果发现某个知识点课件和教材讲法不一致以教材的算法流程为准因为考试判卷通常按教材的思路。6.2 我验证过的刷题节奏与自测方法如果你离考试还有一个月我建议按三周刷题、一周冲刺的节奏来。第一周集中解决词法分析和实验题重点是(a|b)*abb这类经典题要求能在 15 分钟内完整手算出最小化 DFA。第二周主攻语法分析First、Follow、预测分析表、LR 项目集各找三道配套题一定要亲手画分析表不能只在脑子里过。第三周处理语义分析和中间代码逆波兰式、四元式、DAG、属性文法各做几题再做一次综合实验。冲刺周的核心是「默写」合上书本在一张白纸上从头写出 First/Follow 算法的每一步、LR 项目集闭包的构造规则、四元式的生成过程。如果哪个地方卡住超过两分钟就说明还没真正掌握需要回到教材补漏。这里分享一个我实际测过很有效的方法找一位同学你给他讲题把他当作完全不懂的人。每次讲题讲到讲不下去、或者对方一问「为什么这里要这样处理」你就愣住了这个点就是你最薄弱的环节。这比盲目刷十道题都管用因为编译原理的题目考察的是「能否完整推导」而讲题正好把推导过程外显了出来。我刷了大概两百多道题之后最大的感悟是编译原理的题目从来不是靠聪明而是靠「每一步都有依据」。这个依据可能是优先级、可能是闭包定义、可能是 Follow 集合的传递规则只要每步都写清楚为什么就不会错得离谱。期末、考研、面试考察的重点始终是这些基础推演能力。那些一开始觉得玄乎的 NFA、LR 状态机多演算几遍之后其实就像解方程一样自然了。