编译原理通关笔记：从哈工大课堂到及格线速通
1. 编译原理速通指南：从哈工大课堂到及格线
编译原理这门课在计算机专业里一直是个"硬骨头"，尤其是哈工大的编译原理课程，以内容深、实验多著称。作为一个过来人，我完全理解大家面对这门课时的焦虑——复杂的理论推导、抽象的概念体系，还有那让人头疼的八个大实验。
但别担心，这篇笔记就是来帮大家解决这个问题的。我把自己在哈工大课堂上学到的精华，加上备考时总结的实战技巧，全部浓缩在这份"及格版"笔记里。我们的目标很明确：用最短的时间掌握最核心的考点，顺利通过考试。
2. 核心概念精讲
2.1 编译过程全景图
编译的本质就是一个翻译过程，把高级语言（比如C、Java）转换成机器能懂的汇编或机器语言。这个过程可以类比人类翻译外文：
- 词法分析：就像查字典，把句子拆成单词并标注词性
- 语法分析：分析单词如何组成短语，画出语法树
- 语义分析：检查句子是否通顺，收集变量和函数信息
- 中间代码：把句子意思提炼成更抽象的表示
- 代码优化：对翻译进行润色，让表达更高效
- 目标代码：最终翻译成品
以C语言为例，完整的编译系统包含四个关键组件：
- 预处理器：处理#include和#define这些指令
- 编译器：核心部分，把预处理后的代码转成汇编
- 汇编器：把汇编转成机器码（还是逻辑地址）
- 链接器：把多个目标文件合并成可执行程序
2.2 文法与语言
文法就像是编程语言的"语法规则说明书"。它用数学方式定义了：
- 终结符：最基本的符号（比如变量名、运算符）
- 非终结符：语法成分（比如表达式、语句）
- 产生式：符号之间的转换规则
- 开始符号：最大的语法单位
文法的分类从0型到3型，限制越来越多。编程语言主要用2型文法（上下文无关文法），而词法分析多用3型文法（正则文法）。
举个实际例子：定义标识符的文法只需要4条规则：
- S → L | LT
- T → L | D | LT | DT
- L → a|b|...|z
- D → 0|1|...|9
这简单的几条规则就能描述所有可能的标识符，展现了文法"以有限定义无限"的强大能力。
3. 词法分析实战
3.1 正则表达式到DFA
词法分析的核心是把正则表达式转换成确定的有穷自动机(DFA)。这个转换分四步走：
RE→NFA：按照优先级拆解正则式
- 先处理括号内的内容
- 然后是闭包(*)
- 接着是连接(相邻)
- 最后是或运算(|)
NFA→DFA：用子集法消除不确定性
- 计算ϵ-closure消除空转移
- 对每个状态集计算Ia得到新状态
- 直到没有新状态产生
DFA最小化：用划分法合并等价状态
- 先把状态分成终态和非终态
- 检查每个子集是否可再分
- 直到所有子集都不可分为止
DFA实现：用二维表或switch-case实现
3.2 词法错误处理
当DFA卡住时，处理流程：
- 倒着检查已读入的字符
- 找到最近能匹配终态的子串
- 把这个子串作为一个token
- 从下一个字符重新开始分析
- 如果完全无法匹配，进入恐慌模式：
- 持续丢弃字符直到能继续分析
4. 语法分析精要
4.1 自顶向下分析
LL(1)文法是最常用的自顶向下分析方法，关键是要计算三个集合：
FIRST集计算（某非终结符能推出的首终结符）：
- 如果X是终结符，FIRST(X)={X}
- 对于产生式X→Y1Y2...Yn：
- 把FIRST(Y1)加入FIRST(X)
- 如果Y1能推出ϵ，继续加入FIRST(Y2)
- 以此类推
- 如果所有Yi都能推出ϵ，加入ϵ
FOLLOW集计算（某非终结符后可能出现的终结符）：
- 把$加入开始符号的FOLLOW
- 对于产生式A→αBβ：
- 把FIRST(β)-{ϵ}加入FOLLOW(B)
- 如果β能推出ϵ，把FOLLOW(A)加入FOLLOW(B)
SELECT集计算（决定使用哪个产生式）：
- 对于A→α：
- 如果α不能推出ϵ：SELECT=FIRST(α)
- 否则：SELECT=(FIRST(α)-{ϵ})∪FOLLOW(A)
4.2 自底向上分析
LR分析是更强大的自底向上方法，主要步骤：
构造LR(0)自动机：
- 从增广文法S'→S开始
- 计算项目集闭包
- 根据转移符号生成新状态
- 直到没有新状态产生
构造分析表：
- 移入项：对应ACTION表的s
- 规约项：对应ACTION表的r
- 非终结符转移：对应GOTO表
冲突处理：
- SLR：用FOLLOW集解决冲突
- LR(1)：加入展望符更精确判断
- LALR：合并LR(1)的同心状态
实际考试中，SLR就够用了。重点掌握如何用FOLLOW集解决移进-规约冲突：只有当下一个输入符号在规约产生式左部的FOLLOW集中时，才选择规约。
5. 语法制导翻译
5.1 属性文法
SDD（语法制导定义）分两类属性：
- 综合属性：自底向上计算，子节点决定父节点
- 继承属性：自顶向下传递，依赖父节点或兄弟
S-SDD只有综合属性，计算简单：
- 建立依赖图
- 按拓扑序计算属性
- 通常在规约时完成计算
5.2 翻译方案实现
对于LR文法，S-SDD的实现：
- 把语义动作放在产生式末尾
- 在分析栈中开辟空间存储属性
- 规约时执行对应的语义动作
L-SDD适合LL文法，实现方法：
- 继承属性动作放在对应符号前
- 综合属性动作放在产生式末尾
- 递归下降分析时按顺序执行动作
考试中最常考的是中间代码生成，特别是四元式。记住几个规律：
- 赋值操作：结果在第四分量
- 二元运算：两个操作数在2、3分量
- 数组访问：下标作为目标数
- 函数调用：参数在2、3分量
6. 备考策略与高频考点
根据哈工大近年考题，这些内容出现频率最高：
词法分析（25%分值）：
- 正则式到DFA的转换
- DFA最小化
- 词法错误恢复策略
语法分析（35%分值）：
- FIRST/FOLLOW/SELECT计算
- LL(1)分析表构造
- SLR冲突解决
- LR(0)项目集计算
语法制导翻译（20%分值）：
- 属性计算顺序
- S-SDD实现
- 四元式生成
综合应用题（20%分值）：
- 给一个小语言定义词法和语法
- 设计属性文法
- 生成中间代码
备考建议：
- 先掌握算法步骤，再理解原理
- 多画状态转换图和语法树
- 重点练习FIRST/FOLLOW计算
- 熟悉常见的错误恢复策略
- 考前做3-5套往年真题
我在复习时发现，很多同学卡在LR分析表的构造上。其实只要记住这个口诀："移进看ACTION，跳转看GOTO，规约看FOLLOW"，就能解决大部分问题。考试时如果时间紧张，至少要写出LR(0)的自动机，SLR的分析表部分空着也没关系，步骤分能拿大半。
最后提醒，哈工大的实验虽然多，但考试还是以理论为主。把这份笔记里的核心概念和解题方法吃透，及格绝对没问题。我当时考前三天开始看这份笔记，最后拿了78分，相信你们会考得更好！
