企业官网建设流程全解析

我第一次认真刷编译原理习题，不是期末前，而是毕业后准备面试时。那时候翻教材感觉什么都懂：正则、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 --ε--> 1，0 --ε--> 7
• 1 --a--> 2
• 2 --ε--> 3
• 3 --ε--> 4，3 --ε--> 7
• 4 --b--> 5
• 5 --ε--> 6
• 6 --ε--> 1，6 --ε--> 7
• 7 --a--> 8
• 8 --b--> 9
• 9 --b--> 10（接受状态）

很多人在这一步把(a|b)*的闭环画错了，导致后面子集构造时状态集差一两个元素。检验方法是：从初始状态 0 沿 ε 闭包和识别路径出发，能否回到子图的开头形成循环。

第二步，用子集构造法转 DFA。先求初始状态 A = ε-closure({0}) = {0,1,2,3,4,6,7}。然后分别对 a、b 求转移，得到下表：

其中 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：

最小化后，状态 1 识别若干 a、b 的混合串，状态 3 遇到 b 进入接受状态 4，之后任何字符都回到状态 2。每一步都要注意：最小化看的不是状态名，而是「在当前划分下转移是否指向同一个块」。这个题型只要完整演算三遍，基本能拿满分。

2.3 词法分析实验题的代码骨架与隐蔽深坑

除了手算题，很多学校还会布置词法分析上机实验，吉林大学和哈尔滨工业大学公开课件里都有对应的实验要求。实验的核心是写一个识别 Token 流的程序，我建议按照下面的骨架组织：

1. 维护一个全局的输入缓冲区和当前字符指针。
2. 按类别定义保留字表（如 if、else、while）、运算符表（如+、-、*、=）、界符表（如(、)、;）。
3. 主循环里跳过空白符和注释，然后进入最长匹配流程：能构成标识符的字符一路读下去，能构成数字的字符一路读下去，读到无法继续的字符时回退。
4. 查保留字表，如果在表里则输出「保留字，名字」，否则输出「标识符，名字」。
5. 运算符和界符同样按最长匹配原则处理，比如>=不能拆成>和=。

实验里最容易踩的坑有三个。第一个是「关键字识别时机」：先按标识符规则读完整的单词，再去查保留字表，而不是每读一个字符就查一次，否则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 E'
• E' → + T E' | ε
• T → F T'
• T' → * F T' | ε
• F → ( E ) | id

First 集合的最终结果如下：

计算时注意：E → T E'中 T 的 First 是{(, id}，所以 E 的 First 就是 T 的 First；T' → ε说明 ε 属于 T' 的 First，但它不能直接归入 T 的 First，因为 T' 在 T 的右部不一定推导为空。判断一个非终结符的 First 是否含 ε，需要看向右推导能否达空。

Follow 集合结果如下：

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) 中所有终结符对应的单元。

对上面那个文法，预测分析表的核心部分如下：

判 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 = R
• S → R
• L → * R
• L → id
• R → L

这个文法在 LR(0) 项目集里会出现移进-归约冲突，SLR 分析时因为 Follow(L) 包含=，导致在某些状态中遇到=时既想移进又想归约，冲突无法解决。LR(1) 通过向前看符号区分，能正确处理。这个例子我建议完整地做一遍 LR(1) 项目族，体会「向前看符号如何由产生式左侧的 Follow 集合决定」——这是最见功底的一道题。

在做 LR 习题时，我的步骤固定为：先写增广文法S' → S；然后从S' → ·S开始求闭包；每遇到一个运算符就生成新状态；最后检查每个状态是否同时含「可归约项目」和「移进项目」或「两个可归约项目」，如果有，就是冲突状态。这个流程做熟之后，LR(0)、SLR、LR(1) 之间的差异自然就清晰了。

4. 语义分析与中间代码：大题从不会缺席

4.1 逆波兰式与四元式的互相转换

语义和中间代码部分，最基础的题型是逆波兰式和四元式。逆波兰式就是后缀表达式，运算符跟在操作数后面。转换规则是用栈保存运算符，遇到操作数直接输出，遇到运算符时把栈顶优先级不低于当前运算符的运算符依次弹出。括号不输出，但控制出栈。

举个例子，中缀表达式(a+b)*c - (a+b)/e转换成逆波兰式：

1. ab+表示a+b
2. 乘以c得到ab+c*
3. 将(a+b)/e转成ab+e/
4. 相减得到ab+c*ab+e/-

转换成四元式时，每个运算都用临时变量承载结果：

这个例子里，a+b被计算了两次，在 DAG 优化章节里正好用来做对比：优化后四元式可以降到 4 条。考试中经常要求你同时写出逆波兰式、三元式、四元式，本质上考的是同一个表达式树的线性化表达，练熟一个，另外两个就是套壳。

4.2 DAG 化简与公共子表达式

DAG（有向无环图）的题目主要考两个能力：一是根据运算序列构造 DAG，二是从 DAG 还原优化后的代码。它的核心思想是共享公共子表达式，只算一次。

看这样一个代码序列：

• t1 = b * c
• t2 = b * c + d
• t3 = b * c + f

对应的 DAG 中，b * c是一个节点，t2、t3分别在这个节点上做加法。优化后得到：

• t1 = b * c
• t2 = t1 + d
• t3 = t1 + f

做这类题要注意：当某个变量被重新赋值后，它原本对应的叶子节点就不能继续复用了，必须新建叶子节点。这是 DAG 的隐藏考点，题目常在这里设计陷阱。比如a = b + c; b = b - d; c = c + d; a = b + c中，第一行和第四行的b + c在逻辑上不是同一个b和c，因为中间发生了重定义，不能直接复用。考试时如果题目没有特殊说明，默认按「赋值产生新值」处理，别因为复用而丢分。

4.3 属性文法与回填：实验题的隐藏考点

属性文法题的核心是两类属性：综合属性和继承属性。综合属性由子节点的属性计算而来，自底向上传播；继承属性由父节点或兄弟节点的属性传下来，自顶向下传播。典型考题是给一个文法，让你写语法制导定义。

比如表达式文法：

• E → E1 + T，E.val = E1.val + T.val
• E → T，E.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时，生成的三地址码可能是：

• 100：if a < b goto 103
• 101：if c < d goto 103
• 102：goto 106
• 103：t1 := y + 1
• 104：x := t1
• 105：goto 107
• 106：t2 := y - 1
• 107：x := 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 = 12；if (0) { ... }整段删除；多个循环内不变的计算提到循环外。面试时不需要背诵《编译原理》第三版答案里全部优化列表，但每个优化都能用自己的话解释清楚，是很明显的加分项。

6. 刷题路线、资料选择和时间分配

6.1 教材、答案和高校课件怎么搭配

市面上的核心教材主要看龙书（《编译原理》）和虎书（《现代编译原理》）。龙书偏体系化，习题也难，适合按章节刷；虎书更接近真实工程，语言实现细节多，适合做实验和面试准备。本科教材如果学校里指定了，就以指定教材为准，课后题必须做一遍，因为期末考试经常改动课后题的数字和文法符号。

这里说明一下很多人问过的「第三版答案」。我的态度是：可以用，但必须先自己完整推演再对答案，不要做一题看一题。我见过不少同学对着答案刷题，结果考试时 Load 的是「答案的样子」，而不是「算法的过程」，一换数字就不会做了。答案的真正价值不是告诉你这个题选什么，而是帮你发现自己是在哪一步跳了逻辑。另外要注意，部分课后题答案因为版本不同可能有疏漏，如果发现自己的结果和答案不一致，先别急着改，自己重新演算一遍，确认自己是不是有道理。

高校课件的使用思路不同，像吉林大学、哈尔滨工业大学公开的课件，通常把知识点压缩成「考试题型」导向，常考的细节会反复强调。我的用法是：先把课件里的例题做一遍，再看课件里强调的「易错点」，最后如果发现某个知识点课件和教材讲法不一致，以教材的算法流程为准，因为考试判卷通常按教材的思路。

6.2 我验证过的刷题节奏与自测方法

如果你离考试还有一个月，我建议按三周刷题、一周冲刺的节奏来。第一周集中解决词法分析和实验题，重点是(a|b)*abb这类经典题，要求能在 15 分钟内完整手算出最小化 DFA。第二周主攻语法分析，First、Follow、预测分析表、LR 项目集各找三道配套题，一定要亲手画分析表，不能只在脑子里过。第三周处理语义分析和中间代码，逆波兰式、四元式、DAG、属性文法各做几题，再做一次综合实验。

冲刺周的核心是「默写」：合上书本，在一张白纸上从头写出 First/Follow 算法的每一步、LR 项目集闭包的构造规则、四元式的生成过程。如果哪个地方卡住超过两分钟，就说明还没真正掌握，需要回到教材补漏。

这里分享一个我实际测过很有效的方法：找一位同学，你给他讲题，把他当作完全不懂的人。每次讲题讲到讲不下去、或者对方一问「为什么这里要这样处理」你就愣住了，这个点就是你最薄弱的环节。这比盲目刷十道题都管用，因为编译原理的题目考察的是「能否完整推导」，而讲题正好把推导过程外显了出来。

我刷了大概两百多道题之后，最大的感悟是：编译原理的题目从来不是靠聪明，而是靠「每一步都有依据」。这个依据可能是优先级、可能是闭包定义、可能是 Follow 集合的传递规则，只要每步都写清楚为什么，就不会错得离谱。期末、考研、面试，考察的重点始终是这些基础推演能力。那些一开始觉得玄乎的 NFA、LR 状态机，多演算几遍之后，其实就像解方程一样自然了。