企业官网建设流程全解析

简介：《哈工大编译原理期末复习》是一份面向高校计算机专业学生与编译原理初学者的完整期末复习资料，针对哈工大课程考核重点与难点进行系统梳理，可帮助读者在考前快速搭建知识框架、查漏补缺。内容以PDF文档形式打包整理，共1个文件，压缩包大小31.14MB，覆盖编译系统整体结构、语言与文法、词法分析、语法分析、语义分析、中间代码生成、目标代码生成及代码优化等全部核心模块。具体知识点包括DFA与NFA的构造与转换、正则表达式与有穷自动机的关系、文法分类、CFG分析树、三地址码与四元式等，并配有章节式复习要点与图示，适合按模块分块学习。截至目前，已有2311人学习下载，尤其适合考前冲刺、系统回顾编译原理知识体系的学习者使用。

1. 编译原理期末复习：为什么背定义的人最容易翻车

编译原理这门课，期末复习最容易翻车的地方不是知识点多，而是脑子里只有孤立定义。文法、推导、句柄、活前缀、属性文法、三地址码……单看每个词都眼熟，一拿到综合大题就不知道第几步该画图、第几步该填表。这篇复习笔记按编译器从词法分析到目标代码生成的完整流水线来组织，把每段的输入输出讲清，再配上期末最高频的构造题步骤和常见坑。适合正在备考期末的本科生，也适合考研复试前想快速捡起编译基础的人。先摆一句话：这课能拿到分的题，90%落在你能不能闭卷画出状态图、填出分析表、写出四元式。

2. 词法分析复习：正则式、自动机和扫描器的三条主线

词法分析在期末试卷里占的分量不算最大，但它是最“机械”——也是最容易拿满分的部分。所有考题都绕着同一条链子转：给定正则式，构造 NFA，再把 NFA 确定化成 DFA，最后做最小化。这条链子走顺了，你已经把词法分析的大题拿下一多半。

2.1 正则式转 NFA：Thompson 构造法与四步检查

词法分析第一个高频大题是“给定正则式，构造等价的 NFA”，多数教材要求用 Thompson 构造法。原因不只是考试：词法工具 flex 内部做的就是这件事，先生成 NFA 再确定化成 DFA。所以这道题不掌握，后面的子集构造和最小化也做不下去。

Thompson 的核心规则很简单：每个基本字符 a 构成一个只有两个状态的子 NFA，开始状态有一条 a 边到接受状态。然后按三种组合方式拼接。连接 R1R2 时，把 R1 的接受态用 ε 边连到 R2 的开始态；选择 R1|R2 时，新增一个开始态和接受态，用 ε 边把两条分支接进去；闭包 R* 时，在 R 外面套两个状态，加一条从新开始态进 R 的 ε 边，再加一条从 R 的接受态回到 R 开始态的 ε 边，同时留一条直接跳过 R 的 ε 边。

画完 NFA 之后别急着去确定化，先做四步检查：每个基本字符是否都有独立的开始态和接受态；选择的两条分支是否都用 ε 边并回同一个终点；闭包的回头边是否落在闭包子 NFA 的开始态上；从总开始状态沿空串能不能走到接受状态。最后一条很多人漏，ε 边画少一条，NFA 接收的语言就错了，后面全白做。

我一般用a(b|c)*这个式子练手，先做 a 和 b、c 两个原子，再做选择，最后包星号。练两遍之后，(a|b)*abb就不会在状态编号上纠结了。这种构造题状态编号不唯一，只要连接关系对，阅卷都放行。

2.2 子集构造与最小化：DFA 状态表填到哪一步才算完

由 NFA 到 DFA 的子集构造法是期末另一道白给分题，关键动作只有三步：先算初始状态集合，即 NFA 初态的 ε-closure；然后对每个尚未处理的状态集合，逐个字符求 move 之后再求一次 ε-closure，得到后继状态集合；最后，新集合就是新状态，重复上一步直到没有新集合出现。

这里最容易丢分的是“每走一步都要重新闭包”。不少同学只做 move 不重新闭包，结果少算一整类字符。可以把 ε-closure 理解成“站在当前状态，不读任何字符能到达的所有地方”。每算一个新集合，立刻给它编号并补一行表格，这样边算边扩表，不会漏状态。

最小化用分划法就够了：先把所有状态按“接受态 / 非接受态”分成两组；然后检查每组内各状态读入每个字符后落到哪个组，如果同一组内两个状态读同一个字符落到的组不同，就把它们拆开；反复拆到不能再拆为止。

给你一个验证数据：正则式(a|b)*abb的最小 DFA 恰好是 5 个状态。你画完自检一下，abb、aabb、ababb、babb 应该全部被接受，abab 应该被拒绝。如果你画出 6 个以上状态，先检查是不是把 ε 闭包里的临时状态当成独立状态了。如果课程要求按 Hopcroft 算法写，期末答题用分划法也能得到同样结果，阅卷通常认可。

2.3 手写扫描器还是 flex：实验课给期末考喂了什么分

实验课用 flex 生成器写词法分析很快，但期末手写题不允许用工具。最好的走法是：实验能 flex 就 flex，但你至少要亲手手写一次极简扫描器。

下面这段是手写扫描器最核心的骨架，识别标识符、整数和赋值号，关键逻辑就这么几行：

int next_token() { while (isspace(ch)) ch = getchar(); // 跳过空白 if (isalpha(ch)) { // 标识符或关键字开头 char buf[64]; int i = 0; while (isalnum(ch)) { buf[i++] = ch; ch = getchar(); } buf[i] = '\0'; return is_keyword(buf) ? KEYWORD : IDENT; } if (isdigit(ch)) { // 无符号整数 int val = 0; while (isdigit(ch)) { val = val * 10 + ch - '0'; ch = getchar(); } return NUM; } if (ch == '=') { // 区分赋值号和相等判断 ch = getchar(); return (ch == '=') ? EQ : ASSIGN; } return ERROR; }

这段代码体现的是最长匹配原则。比如读入>=，必须读到>时再往后看一眼，不能读一个字符就立刻返回，否则>=会被拆成两个 token。代码里的ch = getchar()配合后面的判断，就是“往前多看一位”的典型实现。用 Java 写实现也很常见，语言不影响原理，核心是一样的 token 定义和状态转移。

实验课对期末最大的反哺就在这：你手写一遍这个骨架之后，期末考试里“识别标识符、整数、关系运算符”这类题基本就是默写。如果你只用了 flex 而没手写过，考前一定要补一次，哪怕只写这个极简版，也足够帮你理解状态表是怎么来的。

3. 语法分析复习：LL 与 LR 家族的构造题都在考同一件事

语法分析是期末复习的重头戏。题型说白了只有两簇：自顶向下（LL、递归下降）和自底向上（LR、SLR、LALR）。两簇的公分母是集合计算——FIRST、FOLLOW。所有语法分析题，不管表面问法是什么，最终都会落到“集合算对没有、表格填对没有”这两件事上。

3.1 FIRST、FOLLOW 与 FIRSTVT：先把集合算对，后面全是顺的

所有 LL(1) 题都从求 FIRST 和 FOLLOW 开始。求 FIRST 的迭代做法：对每个产生式右部从左往右看，遇到终结符直接加入 FIRST；遇到非终结符 X，把 FIRST(X) 去掉 ε 后加入，如果 X 能推出 ε 就继续看下一个符号，直到某个符号确定不能为空就停下；如果产生式本身是 A→ε，就把 ε 加入 FIRST(A)。整个循环重复到所有集合不再变大为止。

求 FOLLOW 的迭代做法更集中两条规则：对产生式 A→αBβ，把 FIRST(β) 去掉 ε 后加入 FOLLOW(B)；如果 β 能推出 ε，或者 β 根本不存在，就把 FOLLOW(A) 整体加入 FOLLOW(B)。同样重复到不再变化。

拿期末考试出场率最高的经典表达式文法来练：

E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id

求完之后你得到两组集合：

核对方法有一条：所有非终结符的 FOLLOW 最终都该通过开始符号染上 #。如果你算完发现某个能出现在句子末尾的非终结符 FOLLOW 里没有 #，十有八九是漏了“若 β 可空则并入 FOLLOW(A)”这一步。有些同学到处找清华大学出版社第三版第二章答案对着背，其实自己按迭代法算一遍，比背答案可靠得多。

3.2 LL(1) 判定与预测分析表：消除左递归后别忘了验证

LL(1) 的大题通常两问：判断是不是 LL(1)，构造预测分析表。判定条件三条：同一非终结符的各个右部 FIRST 集两两不相交；若某个右部可空，则 ε 属于 FIRST(A) 时，FOLLOW(A) 与其它右部的 FIRST 集不相交；文法本身没有左递归和公共左因子。

消除直接左递归的公式只有一个：A→Aα|β 变成 A→βA'，A'→αA'|ε。注意这只对直接左递归有效，间接左递归要先排序再逐步代入，具体的坑放到后面避坑章节再展开。

填预测分析表也只有两步。第一步，对每个产生式 A→α，把所有终结符 a∈FIRST(α) 的位置 M[A,a] 填入这个产生式。第二步，如果 ε∈FIRST(α)，那么对所有 b∈FOLLOW(A)，把产生式填入 M[A,b]。填表时还带出另一重功能：填入过程中如果你发现某个格子有两个产生式，说明文法不是 LL(1)。

继续用上面那个经典文法，预测分析表应该长这样：

拿到一张空白表，你直接按这两步往里填，判定的活顺便就干完了。考试时可以在一张表上同时完成两问，省时间还能互相印证。

3.3 LR 家族对比：从 LR(0) 到 LALR 的状态数与冲突差异

LR 分析家族是期末最劝退的一块，但它也就围着两个概念转：项目集规范族和冲突消解。构造 LR(0) 自动机的步骤是：给文法加一个增广产生式 S'→S；初始项目集是 S'→·S 的闭包；对每个项目集中的每个文法符号做 goto，生成新项目集；重复到最后不再有新项目集为止。

闭包的规则一句话：点号后面是非终结符 B，就把 B 的全部产生式以 B→·γ 的形式加进当前项目集，循环到不能再加。这句几乎是每年必考，要么填空要么选择。

LR 家族四个成员的区别，期末最爱考的就是这张对比：

关于 LR(1) 闭包有一个必须背下来的结论：对项目 [A→α·Bβ, a] 做闭包时，新增项目 [B→·γ, b] 的向前看符号 b 来自 FIRST(βa)。这里 a 是当前项目的向前看符号，不是固定的 #，很多人在这里丢分。

LALR 还有一条高频结论：合并同心项目集不可能产生新的移进-归约冲突，但可能产生新的归约-归约冲突。理由是移进动作由项目核心决定，向前看符号只参与归约判断。这条结论在选择填空里出现率极高。

3.4 递归下降代码题：背下骨架比临场推理快十倍

递归下降和 LL(1) 预测分析表是同一件事的两种表达。每个非终结符对应一个函数，每个产生式对应一段 if 分支。期末如果考手写代码题，基本就是让你补全下面这种骨架：

void E() { T(); E_prime(); } void E_prime() { if (lookahead == '+') { match('+'); T(); E_prime(); } // 没有匹配到 '+' 就直接返回，相当于选择 ε 产生式 }

配套的 match 函数长这样：

void match(int token) { if (lookahead == token) { lookahead = next_token(); // 读入下一个 token } else { error("unexpected token"); } }

函数名就是非终结符，if 分支就是该非终结符的一个候选产生式，函数自然返回等于选择了 ε 产生式。这跟预测分析表 M[A,a] 的格子是一一对应的。实验课如果让你写表达式计算器，把语义动作直接塞进E_prime函数的match('+')之后——在匹配完+时立刻生成一条三地址码——语法分析和中间代码生成就一起练完了。

注意 error() 至少要打印当前行号。很多同学写递归下降不写错误处理，遇到非法输入就一直递归到栈爆掉也查不出原因。留个行号输出，问题定位快十倍。

4. 语义分析、中间代码与优化：从属性文法到四元式怎么连

语法分析拿到的是“这句话合不合语法”，语义分析回答的是“这句话是什么意思”。期末考到这一章，题型从画图变成了写属性、填符号表、翻译三地址码。这块内容表面琐碎，实际上有一条链子：属性文法把类型、值等信息挂到语法树上，语义动作把语法树变成三地址码，符号表和运行时存储为变量和过程调用提供地址基础。

4.1 综合属性与继承属性：依赖图能帮你避开赋值顺序的坑

属性文法里最常考的就是判断属性类型。综合属性的特点是：只需看子节点和自己的属性就能算出来。继承属性正好相反：必须从父节点、兄弟节点或者更外层环境传入。判断技巧是反过来问：这个属性能不能只从语法树的子树内部得到？能，就是综合的；不能，就是继承的。

最经典的例子是D → T id。T.type 是综合属性，它从 T 子节点的词法值综合而来；而 id.type 是继承属性，它从左边兄弟 T.type 继承。数组元素的偏移量也是典型继承属性——不知道数组声明里的每维长度，你根本算不出某个元素在内存里的位置。

如果考到求值顺序，用依赖图最稳。每个属性画成一个节点，每条属性计算规则画一条有向边，属性之间如果有依赖关系，就从被依赖者指向依赖者。图建完之后做一次拓扑排序，排序结果就是安全的求值顺序。只凭感觉“先子后父”应对综合属性没问题，但一掺进继承属性就容易顺序颠倒。

4.2 三地址码与回填：声明翻译和数组下标按统一模板写

三地址码是期末手写题的大头，常见形式有四元式、三元式和间接三元式。考试最常写四元式：把 操作符、左操作数、右操作数、结果 四个字段一次性写出来。指令类型不多，一张表能收住：

while (a < b) a = a + 1;的标准翻译长这样：

(1) if a < b goto (3) (2) goto (5) (3) t1 = a + 1 (4) a = t1 (5) goto (1)

你能看到，第 (2) 行跳到 (5) 是为了绕过循环体，第 (5) 行跳回 (1) 是回到循环判断。翻译过程中目标地址不是一开始就能确定的，需要先留空、等知道跳哪了再回头填，这就是回填。期末考里最常见的问法就是“补全跳转目标”。

数组下标翻译也常考，x = a[i][j]假设每行 n 个元素、每个元素 w 字节，翻译结果应该是：

t1 = i * n t1 = t1 + j t2 = t1 * w t3 = a_base + t2 x = t3

多维度数组的地址计算公式就是行优先的线性化：先算行偏移，再算列偏移，最后乘元素宽度。第一次写会容易漏了乘宽度那步，考前一晚值得单独过一遍。

4.3 符号表与运行时存储：一张活动记录图能串起半章考点

符号表这一节期末经常以画结构的形式出题：给你一段嵌套的 C 或 Pascal 风格程序，要求画出符号表以及作用域链。基本规则是查符号从内层往外层找，内层作用域里可以重新定义外层同名变量，符号表条目要有名字、类型、作用域指针和存储偏移量。

运行时存储里最实用的考点是活动记录布局。每个函数调用都会在栈上压入一个活动记录，典型布局从栈底到栈顶是这样：

考试常挖的坑是：问返回地址在局部变量的哪一侧，或者问动态链指向谁。动态链永远指向调用者的活动记录底部，不是指向栈底。如果课程讲过嵌套过程，这里还会补一个访问链或 display 表的概念——访问链指向定义该过程的词法外层过程的最新活动记录，一句话带过即可。

4.4 优化与目标代码生成：期末常考的六种优化识别特征

优化部分期末以选择、填空为主，认得出就够了。最常出现的六种优化：常量折叠、常量传播、复写传播、死代码删除、公共子表达式消除、循环不变式外提。每种都有一个识别特征：常量折叠是2*3直接写成6；常量传播是把恒为常量的变量替换成常量；复写传播是x=y之后遇到 x 直接用 y；死代码删除是删掉结果不被任何语句使用的计算；公共子表达式消除是两次a+b只算一次；循环不变式外提是把循环体内不随迭代变化的运算搬到循环前。

如果考大题，多半给你一个基本块，要你画 DAG 图。DAG 的构造要点：叶子是变量和常量，内部节点是运算符，两个相同运算节点值相同且子节点顺序相同就可以合并。一张 DAG 画完，公共子表达式消除和死代码删除的答案就同时出来了。

5. 期末复习避坑：五个高频失分点的现象与排查

以下五个坑是我每年都会被问一遍的高频失分点，每条都按“现象、原因、解决”写清楚。考前对照排查，比自己闷头刷题效率高得多。

5.1 求 FOLLOW 时漏掉可空符号的传递

现象：算经典文法E→TE'、E'→+TE'|ε这类题，最后得出 FOLLOW(T)={+)}，丢了#和)的传递，整道 LL(1) 判断题的 FOLLOW 全错。

原因：只执行了“把 FIRST(E') 去掉 ε 加入 FOLLOW(T)”这一步，没有继续判断 E' 可空时，还要把 FOLLOW(E) 整体并入 FOLLOW(T)。

解决：求 FOLLOW 时严格按两条规则操作。右部形如 A→αBβ 时，先做 FIRST(β)-{ε}；再检查 β 能否推出 ε，如果能，就追加 FOLLOW(A) 整体并入 FOLLOW(B)。每次扫完所有产生式之后循环一遍，集合不再变化才停手。检查答案时用前面那张经典表达式的表对着核，少一个符号都能立刻发现。

5.2 消除间接左递归只做了一半

现象：给定文法S→Aa|b、A→Sc|d，有人直接把 S 或 A 套用消除直接左递归的公式，结果越消越乱。

原因：S 通过 A 间接左递归，即 S⇒Aa⇒Sca，直接套公式时根本没有直接左递归可消，必须先代入再处理。

解决：按三步走。第一步给非终结符排个序；第二步把间接左递归变成直接左递归，具体到这个例子，把 S 的产生式代入 A：

A → Sc|d => A → (Aa|b)c|d => A → Ac|bc|d

此时 A 有了直接左递归。第三步套公式：

A → bcA' | dA' A' → cA' | ε

最后把新 A 代回 S 的产生式：

S → bcA'a | dA'a | b

试卷上如果给了多个非终结符互相间接左递归，先编号再从头到尾代入，一步都不能跳。

5.3 LR 项目集规范族画到一半就停手

现象：画 LR(0) 自动机时，画了三四个项目集，觉得“剩下的看起来差不多”，结果 GOTO 表少了转移边，后面 SLR 分析表跟着错。

原因：closure 没有做彻底。点号后面是非终结符 B，B 的所有产生式都必须加进来，而且要一直加到不能再加。很多人只展开了一层，少加了一个产生式，状态就少了一个。

解决：采用“表格法”代替凭感觉画图。把每个项目集编号，单独登记三列：当前状态编号、输入符号、跳转目标编号。每个状态都先把闭包算完整，再对每一个文法符号做 goto，所有结果先写进表里，最后再根据这张表去画自动机。表里任何一格填了重复目标编号，说明状态合并有问题，一眼就能抓到。

5.4 递归下降的 lookahead 与 match 顺序写反

现象：递归下降函数跑起来死循环，或者把明明合法的输入判成语法错误。

原因：常见写法是先lookahead = next_token()再调用 match，等于跳过了当前 token 的判断。正确的 match 必须“先比后读”：比较的是当前 lookahead，读完新 token 后更新 lookahead。写反了，第一次判断就拿不到正确输入。

解决：统一按这个模式写：函数开头只检查全局变量 lookahead；匹配成功后才更新 lookahead；任何分支都不写“先读 token 再判断”。调试时在 error() 里打印当前 lookahead 和行号，马上能看出是读过头还是判断漏了分支。

5.5 三地址码回填时目标标号不统一

现象：翻译 while 或 if-else 时，goto 的目标写到别的地方去，或者同一个标号被两段代码复用，翻译结果逻辑错乱。

原因：手写标号时靠眼睛记，边翻边编，前后不一致。代码一长，编号就乱了。

解决：用一个计数器维护标号，每生成一个 Lx 就自增，同时按语句模板翻译。while 语句的模板是固定的：

L1: 条件跳转 L2 goto L3 L2: 循环体 goto L1 L3: 出口

if-else 也有固定模板。考试时先写模板、再填内容，标号就不会乱。填空或补全题里，看到不完整的跳转，先把模板框架列出来再对号入座，正确率明显更高。

6. 考前两周的验证方法：把整条流水线画成一幅图

考前两周最该做的事，是把知识从“名词解释”改成“带输入输出的处理过程”。我自己的习惯是找一张 A4 白纸，从上到下画一条完整流水线：源程序字符流 → token 流 → 语法树 → 带属性的语法树 → 三地址码 → 优化后的中间代码 → 目标代码。每段中间，在右侧写一行这个阶段最常考的题型。

画完之后用五个问题来自检：能否十分钟内不看书求出一个给定文法的 FIRST/FOLLOW；能否闭卷画出(a|b)*abb对应的五状态 DFA 并标出终态；能否说清 SLR、LR(1)、LALR 的状态数关系和冲突差异；能否把while(a<b) a=a+1写成标准四元式并说明回填位置；能否手写出一个表达式文法的递归下降骨架并带错误处理。五个问题里任何一个答不上来，就回到对应章节重做一两道大题，而不是去背名词解释。

有一次我考前画这条流水线，在“中间代码生成”处卡住了——发现自己从来没把符号表里的偏移量和三地址码的下标翻译连起来。第二天专门把数组元素寻址算了一遍，结果那年的实验题恰好考到这一段。这个习惯后来保持到了工作里：接手一个编译器项目时，第一件事就是先画出全流程的输入输出，而不是急着翻代码。考前再把这张图过一遍，比翻十遍笔记都有用。希望帮到你。

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