编译原理通关笔记：从哈工大课堂到及格线速通

1. 编译原理速通指南从哈工大课堂到及格线编译原理这门课在计算机专业里一直是个硬骨头尤其是哈工大的编译原理课程以内容深、实验多著称。作为一个过来人我完全理解大家面对这门课时的焦虑——复杂的理论推导、抽象的概念体系还有那让人头疼的八个大实验。但别担心这篇笔记就是来帮大家解决这个问题的。我把自己在哈工大课堂上学到的精华加上备考时总结的实战技巧全部浓缩在这份及格版笔记里。我们的目标很明确用最短的时间掌握最核心的考点顺利通过考试。2. 核心概念精讲2.1 编译过程全景图编译的本质就是一个翻译过程把高级语言比如C、Java转换成机器能懂的汇编或机器语言。这个过程可以类比人类翻译外文词法分析就像查字典把句子拆成单词并标注词性语法分析分析单词如何组成短语画出语法树语义分析检查句子是否通顺收集变量和函数信息中间代码把句子意思提炼成更抽象的表示代码优化对翻译进行润色让表达更高效目标代码最终翻译成品以C语言为例完整的编译系统包含四个关键组件预处理器处理#include和#define这些指令编译器核心部分把预处理后的代码转成汇编汇编器把汇编转成机器码还是逻辑地址链接器把多个目标文件合并成可执行程序2.2 文法与语言文法就像是编程语言的语法规则说明书。它用数学方式定义了终结符最基本的符号比如变量名、运算符非终结符语法成分比如表达式、语句产生式符号之间的转换规则开始符号最大的语法单位文法的分类从0型到3型限制越来越多。编程语言主要用2型文法上下文无关文法而词法分析多用3型文法正则文法。举个实际例子定义标识符的文法只需要4条规则S → L | LTT → L | D | LT | DTL → a|b|...|zD → 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→α如果α不能推出ϵSELECTFIRST(α)否则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分相信你们会考得更好