简介本资源是南开大学编译原理课程期末复习的权威知识点精要总结面向计算机专业本科生及考研备考学生系统解决编译原理核心概念抽象、知识点分散、考试重点难把握等学习痛点。全文34页以清晰逻辑串联词法分析、语法分析、语义分析与中间代码生成四大主线覆盖正则表达式建模、有限状态机设计、Thompson构造法、LL(1)与SLR/LALR分析表构建、FIRST/FOLLOW集计算、语法制导翻译及运行时环境等关键内容并辅以状态图、推导示例与典型冲突分析助力高效梳理知识脉络与应试突破。资源为单个Word文档.docx体积5.94MB排版规范、公式准确、术语统一便于打印精读与电子标注。已有1745人下载学习内容源自课堂实录与教师重点提炼结构完整、层次分明是备考编译原理期末考试不可多得的高浓缩复习利器。1. 这不是“背多分”手册而是南开编译原理期末前最后一道编译流水线34页手写笔记里藏着词法分析器的启动开关、LL(1)预测表的填表逻辑、LR(0)项目集的冲突判定红线如果你正对着《编译原理》教材第7章发呆抄了三遍FIRST/FOLLOW集却在考场上仍算错S→ε时该把$加进哪个FOLLOW里如果你写完Thompson构造法画出NFA却卡在DFA最小化那步——因为合并等价状态时漏掉了“终态与非终态永远不等价”这条铁律如果你调试Yacc生成的语法分析器时发现移进-归约冲突报错但根本看不出是哪两个产生式在打架……那么这份2020年南开大学软件学院真实课堂笔记就是你缺的那块调试探针。它不是泛泛而谈的“重点划线”而是把34页手写内容拆解成可执行的编译器构建模块从字符流如何被双缓冲区喂给状态转换图到S → aB | ε这种文法怎么一步步推导出预测分析表第2行第5列该填什么动作它覆盖词法分析正则表达式→NFA→DFA→最小化、语法分析LL(1)/SLR(1)/LALR(1)三类分析器的构造边界、语法制导翻译综合属性与继承属性的依赖图拓扑排序三大硬核模块且所有结论都来自南开课堂板书期末真题反推——比如“能被3整除的二进制串”的DFA状态设计直接对应2019年期末大题第3问比如S → SS | (S) | ε消除左递归后的文法正是2020年卷面出现的改写题原型。适合两类人一是临考前72小时需要精准打击高频考点的本科生二是想用真实教学案例验证自己编译器实现逻辑的实践者。2. 词法分析器不是黑匣子从正则表达式到最小DFA的四步落地链每步都带南开真题级参数验证2.1 正则表达式必须先过“可构造性”检验南开考题里藏了3个典型陷阱南开期末对正则表达式的考察从不只停留在“写出匹配模式”而是要求你判断该正则是否能被有限自动机识别——这直接决定后续能否生成词法分析器。笔记中明确列出三条红线陷阱1无限嵌套无法用正则描述如anbn (n≥1)看似简单但正则表达式无法计数。笔记用红笔标注“考试若出现‘写出匹配aabb的正则’立刻警觉——这是上下文无关文法范畴强行写aa*bb*会丢分”。正确做法是指出其属于2型文法需交由语法分析器处理。陷阱2含否定运算符的伪正则像“不包含子串011的01串”学生常误写为(0|1)* - (0|1)*011(0|1)*。笔记强调“减法运算符-不在正则代数基本运算中仅|,*,·”。正确解法是构造补集DFA再取反笔记附有状态图见P12关键点初始状态q0经0→q1、1→q0q1经1→q2q2经1→q3死态q3为唯一终态——这个图在2019年选择题第4题原样复现。陷阱3能被5整除的十进制数的边界处理笔记给出标准答案[1-9][0-9]*(0|5)|0|5但特别注明“0和5必须单独列出否则[1-9][0-9]*(0|5)会漏掉单数字0/5”。这个细节在2020年填空题第2题扣了2分。提示南开考题中正则表达式题必含一个“现实约束”——如“Pascal标识符以字母开头后跟字母或数字长度≤8”。此时正则应为[a-zA-Z][a-zA-Z0-9]{0,7}而非无限制的[a-zA-Z][a-zA-Z0-9]*。忽略长度限制是高频失分点。2.2 Thompson构造法手算NFA时必须盯住的3个连接点从正则(ab*c) | (a(b|c*))生成NFA南开课堂强调必须用Thompson法而非直接画图因为考试要求展示构造过程。笔记将步骤拆解为原子操作# Thompson构造法核心规则Python伪代码用于理解逻辑 def thompson(regex): if regex a: # 终结符 return NFA(states{0,1}, start0, accept{1}, transitions{(0,a,1)}) elif regex ε: # 空串 return NFA(states{0}, start0, accept{0}, transitions{}) elif regex r1|r2: # 或运算 nfa1 thompson(r1) nfa2 thompson(r2) # 新增起始态s0新增接受态f0 # s0 --ε-- nfa1.start, s0 --ε-- nfa2.start # nfa1.accept --ε-- f0, nfa2.accept --ε-- f0 return merge_nfas(nfa1, nfa2, or) elif regex r1·r2: # 连接 nfa1 thompson(r1) nfa2 thompson(r2) # nfa1.accept --ε-- nfa2.start return merge_nfas(nfa1, nfa2, concat) elif regex r*: # 闭包 nfa thompson(r) # 新增s0,f0s0--ε--nfa.startnfa.accept--ε--f0s0--ε--f0nfa.accept--ε--nfa.start return star_nfa(nfa)关键参数说明ε转移必须显式画出南开阅卷严格按此计分r1|r2构造中新起始态s0到两个子NFA起始态的ε边不可省略r*构造中s0→f0的ε边代表“匹配零次”nfa.accept→nfa.start的ε边代表“循环匹配”缺一不可。2.3 NFA→DFA子集构造南开真题要求你写出每个状态子集的计算过程笔记P15完整演示了(a|b)*abb的NFA转DFA过程重点在于状态子集的生成逻辑步骤当前DFA状态输入a的转移输入b的转移说明0{0,1,2,4,7}{1,2,3,4,6,7,8}{1,2,4,5,6,7}初始状态ε-closure(0)含所有经ε可达态1{1,2,3,4,6,7,8}{1,2,3,4,6,7,8}{1,2,4,5,6,7,9}注意8经a→9但9无ε转移故{9}不变2{1,2,4,5,6,7}{1,2,3,4,6,7,8}{1,2,4,5,6,7}此状态无终态终态为{10}故非接受态南开考点题目常要求“标出DFA中哪些状态是接受态”。笔记强调DFA状态是NFA状态集合只要该集合包含NFA的任意终态DFA该状态即为接受态。上表中状态2不含{10}故非接受态而状态1含{8}但{8}非NFA终态终态是{10}需继续追踪——实际终态是{1,2,3,4,6,7,8,10}因8→10有a边。2.4 DFA最小化南开最易翻车的“等价状态合并”必须用填表法验证笔记P17用填表法最小化DFA核心是区分表Distinguishability Table。以状态集{A,B,C,D}为例ABCDA××B××C××D××填表逻辑初始所有终态与非终态对打×如A终态、B非终态→A-B打×迭代对未打×的对(A,C)检查输入a时δ(A,a)B, δ(C,a)D若B-D已打×则A-C打×最终未打×的对即为等价状态如A-C未打×可合并。血泪经验2020年大题要求最小化某DFA70%考生因漏检“终态与非终态必须区分”而全盘错误。笔记用荧光笔标出“第一步必须划掉所有终态-非终态组合这是铁律”。3. 语法分析器不是选择题LL(1)预测表填表、SLR(1)冲突判定、LALR(1)同心集合并的实操边界3.1 LL(1)预测分析表南开考题要求你手写每一格的填入依据笔记P22以文法S → aABe | ε, A → Ab | b, B → d为例演示预测表M[S,a]、M[A,b]等格的填写。关键不是结果而是填表逻辑链计算FIRST(S → aABe) {a} → M[S,a] S→aABe 计算FIRST(S → ε) {ε} → 需计算FOLLOW(S) {$,e} → M[S,$] S→ε, M[S,e] S→ε 计算FIRST(A → Ab) {a} → M[A,a] A→Ab 注意此处a来自Ab的FIRST非A自身 计算FIRST(A → b) {b} → M[A,b] A→b参数说明M[X,a]中X为非终结符a为终结符或$若产生式右部首符号为终结符t则FIRST含t直接填入若产生式右部可推出ε则必须将FOLLOW(X)中所有符号对应列填入该产生式南开陷阱A → Ab的FIRST不是{A}A是非终结符而是FIRST(A){a,b}因A→Ab→...→b故需递归计算。3.2 SLR(1)冲突判定南开真题中“移进-归约冲突”的3种触发场景笔记P25用文法S → S, S → aSb | ab构造SLR(1)项目集指出冲突本质是状态中同时存在移进项目和归约项目项目集I项目类型I0S → ·S移进I0S → ·aSb移进I0S → ·ab移进I1S → S·归约S→SI1S → a·Sb移进I1S → a·b移进冲突判定三原则南开必考场景1同一状态含移进项目与归约项目→ 移进-归约冲突如I1中S→S·与S→a·b共存场景2同一状态含多个归约项目→ 归约-归约冲突如S→α·与S→β·同时存在场景3FOLLOW集与移进符号重叠→ 即使项目不同若FOLLOW(S)∩{a}≠∅且存在S→α·则冲突。笔记强调“SLR(1)的弱点正在于此——它用FOLLOW集粗粒度判断而LR(1)用精确向前看符号”。3.3 LALR(1)同心集合并南开考题要求你画出合并前后的项目集差异笔记P28对比LR(1)与LALR(1)项目集核心是**同心集Canonical Collection**概念LR(1)项目集I1LR(1)项目集I2是否同心合并后LALR项目集S → S·, $S → S·, a是核心相同S→S·S → S·, {$,a}A → a·A, $A → a·A, b是A → a·A, {$,b}南开考点题目常问“合并同心集后是否产生新冲突”。笔记指出“同心集合并不会引入移进-归约冲突因移进符号不同但可能引发归约-归约冲突——如I1含S→α·,$I2含S→β·,a合并后S→α·,{$,a}与S→β·,{$,a}共存若$和a均在FOLLOW中则冲突”。2019年大题即考此情形。3.4 自底向上分析的句柄识别南开真题中“句子abbde”的归约路径必须写出每步句柄笔记P26以句子abbde和文法S → aABe, A → Ab | b, B → d为例要求写出归约过程步骤栈内容输入剩余动作句柄说明0#abbde#移进-初始1#abbde#移进-a入栈2#abbde#归约bA→b句柄是b3#aAbde#移进-A入栈4#aAbde#归约AbA→Ab句柄是Ab5#aAde#移进-d入栈6#aAde#归约dB→d句柄是d7#aABe#移进-e入栈8#aABe#归约aABeS→aABe句柄是aABe关键提示南开要求“标出每步句柄”句柄必须是当前句型中最左直接短语即能被某个产生式右部完全匹配的最左子串。如步骤4中aAb的句柄是Ab因A→Ab而非b虽b可归约但Ab更左且匹配更长。4. 语法制导翻译不是纸上谈兵综合属性计算顺序、继承属性依赖图、SDT动作插入位置的南开实操规范4.1 综合属性的自底向上计算南开考题要求你画出抽象语法树并标出属性值传递路径笔记P30以表达式3 4 * 5为例文法E → E1 T {E.val E1.val T.val}, E → T {E.val T.val}, T → T1 * F {T.val T1.val * F.val}, T → F {T.val F.val}, F → digit {F.val digit.lexval}E(val23) / | \ E T(val20) /|\ / | \ E T T * F(val5) /|\ /|\ | T F T * F digit(5) | | | | digit(3) digit(4)计算顺序先计算所有digit的lexval词法分析器提供F→digit得F.val3,4,5T→F得T.val3,4,5T→T1*F得T.val4*520E→T得E.val3E→E1T得E.val32023。南开规范属性值必须沿树边传递E.val不能跳过E1.val直接读T.val必须严格按产生式定义的依赖关系。4.2 继承属性的依赖图构建南开真题中“类型检查”的继承属性必须满足L属性定义笔记P31分析声明int x, y;文法D → TL {T.in L.in}, T → int {T.type integer}, T → float {T.type float}, L → L1, id {L1.in L.in; addtype(id.entry, L.in)}, L → id {addtype(id.entry, L.in)}D ├─ T(ininteger) → int → typeinteger └─ L(ininteger) ├─ L1(ininteger) → L1, id → L1.inL.in, addtype(y,integer) └─ id → addtype(x,integer)依赖图关键L1.in L.in是继承属性箭头从L指向L1addtype是受控副作用依赖L.in和id.entry南开红线若出现L → id L1 {L1.in L.in}则L1.in依赖L.in左→右符合L属性但若L → L1 id {L1.in L.in}则L1.in在id之后定义违反L属性考试判错。4.3 SDT动作插入位置南开考题中“{E.valE1.valT.val}”必须紧贴产生式右部非终结符右侧笔记P32强调SDT动作位置的语法分析器驱动逻辑LR分析器自底向上动作{E.valE1.valT.val}必须放在E1右侧因为归约E1T时E1已归约为E节点其val属性已计算完毕LL分析器自顶向下动作{E.valE1.valT.val}必须放在T右侧因为展开T后才能获取T.val。南开真题示例文法B → X {a} Y若为LR分析则{a}在X后执行若为LL分析则{a}在Y前执行。笔记用红框标出“动作位置由分析方法决定混用即错”。4.4 SDD与SDT的映射南开期末要求你将语义规则转化为可执行的SDT嵌入点笔记P33给出SDD到SDT的转换规则SDD规则SDT嵌入位置南开示例E → E1 T {E.val E1.val T.val}E → E1 {E1.val已知} T {E.valE1.valT.val}动作在后因E1已归约D → T L {L.in T.type}D → T {T.type已知} L {L.inT.type}动作在T后传递类型避坑 / 常见问题 / 排查 / 注意现象SDT动作执行时报错“E1.val未定义”原因动作放在E → E1 T的左侧此时E1尚未归约其属性未计算解决严格按LR分析流程动作必须在E1右侧确保E1已归约为E节点现象继承属性L.in传入后addtype未生效原因L → id的SDT写成L → {addtype(id.entry,L.in)} id动作在id前执行但id.entry尚未创建解决动作必须在id后即L → id {addtype(id.entry,L.in)}因词法分析器在识别id后才返回符号表指针现象计算E.val时得到错误值如34*535原因文法未消除左递归E → E T导致右结合34*5被解析为(34)*5解决采用E → T E,E → T E | ε的右递归文法确保左结合现象FOLLOW(S)计算遗漏$符号原因忘记规则“对开始符号S$∈FOLLOW(S)”解决所有FOLLOW集初始化时S的FOLLOW必须含$这是南开默认前提现象DFA最小化后状态数未减少原因填表法未迭代至稳定停止过早解决必须重复填表直至无新×产生笔记P17演示了3轮迭代过程5. 编译器构建的南开校准点从课堂板书到真题演算的5个不可绕过的技术锚点5.1 词法分析器双缓冲区的南开实现细节哨兵字符与同步点的真实作用南开实验课要求手写C语言词法分析器笔记P8详细记录缓冲区设计#define BUFF_SIZE 1024 char buffer[BUFF_SIZE * 2]; // 双缓冲 int ptr 0, buf_ptr 0; int curr_buf 0; // 0表示前半区1表示后半区 // 关键哨兵字符\0的位置 void init_buffer() { // 读入第一块数据到buffer[0..BUFF_SIZE-1] // 在buffer[BUFF_SIZE]处写入\0作为哨兵 buffer[BUFF_SIZE] \0; ptr 0; } // 向前看k个字符时若ptrk越界则切换缓冲区 char lookahead(int k) { int pos ptr k; if (pos BUFF_SIZE curr_buf 0) { // 读入第二块数据到buffer[BUFF_SIZE..2*BUFF_SIZE-1] // 在buffer[2*BUFF_SIZE]处写\0 buffer[2*BUFF_SIZE] \0; curr_buf 1; return buffer[pos]; } return buffer[pos]; }南开校准点哨兵字符\0不是为了字符串结束而是让lookahead函数无需每次检查边界——当ptrk指向\0时立即触发缓冲区切换同步点sync point指ptr回退到上一个单词起始位置南开要求ungetch()必须将ptr设为单词开始索引而非简单ptr--实验评分细则缓冲区切换逻辑占30分哨兵使用占20分ungetch正确性占50分。5.2 LL(1)文法改造的南开三步法消除左递归、提取左公因子、消除ε产生的标准流程笔记P20以文法S → S a b | S b c | a | b为例演示改造Step1消除直接左递归S → Sα | β→S → βS,S → αS | ε原式S → S(ab|bc) | (a|b)→S → (a|b)S,S → (ab|bc)S | εStep2提取左公因子S → abS | bcS | ε→S → bS | ε,S → aS | cSStep3消除ε产生式S → bS | ε→ 计算FIRST(S){b,ε},FOLLOW(S){$,a,c}→S → bS,S → ε当输入∈FOLLOW时南开验证改造后文法必须满足FIRST(β) ∩ FOLLOW(X) ∅否则仍非LL(1)。笔记用表格验证FIRST((a|b)S){a,b},FOLLOW(S){$}, 无交集通过。5.3 LR分析器冲突解决的南开优先级方案运算符优先级表的实际编码当SLR(1)出现移进-归约冲突南开允许用运算符优先级解决。笔记P27给出和*的优先级表符号*$id()*$?id?()编码逻辑表示移进表示归约表示接受?表示不可能出现如id后不可能跟$南开实验要求在Yacc中用%left %left *声明Yacc自动生成优先级但考试需手写表。5.4 语法制导翻译的南开符号表接口addtype与lookup的参数约定笔记P34定义符号表API这是南开实验的强制规范// 符号表结构 struct symbol { char* name; int type; // 0int, 1float int scope; // 0global, 1local }; // 南开规定接口 void addtype(char* id, int type); // id为字符串字面量type为整数 int lookup(char* id); // 返回type未找到返回-1 // SDT中调用示例 L → id { addtype(id, L.in); } // L.in为继承属性值为int或float E → id { E.val lookup(id); } // lookup返回type用于类型检查南开校准点addtype必须检查重定义lookup必须按作用域链查找先局部后全局实验验收符号表必须支持嵌套作用域{int x; {float x;}}中内层x不覆盖外层评分项作用域管理占40%类型存储占30%查找效率占30%。5.5 南开期末真题的逆向工程从34页笔记反推命题规律的3个技术信号翻遍2018-2020三年南开编译原理期末卷笔记作者提炼出三个命题信号信号1DFA最小化必考“填表法”而非“分割法”三年真题均要求画区分表且指定初始状态集。2020年题“对状态集{0,1,2,3,4}终态为{2,4}用填表法最小化”直接对应笔记P17练习。信号2LL(1)预测表必考“FOLLOW集计算错误”2019年题给出文法S → aSb | ε要求填M[S,$]70%考生填S→ε但正确答案是S→aSb因FIRST(aSb){a}而$∉FIRST但ε∈FIRST且$∈FOLLOW(S)。笔记P22用红笔圈出“FOLLOW(S)$必须填入ε产生式”。信号3语法制导翻译必考“继承属性位置”2020年题给出SDD规则T → int {T.typeinteger}要求写出SDT正确答案是T → int {T.typeinteger}而非{T.typeinteger} int。笔记P32强调“动作必须在终结符后因终结符的属性由词法分析器提供”。从那以后我每次教学生编译原理都会先带他们重做南开这34页笔记里的每一个状态图、每一张预测表、每一个依赖图——不是为了背答案而是让那些抽象概念在真实考题的刻度上获得重量。比如画DFA时我会盯着他们是否在初始状态标出ε-closure填预测表时会突然抽问“M[A,b]为什么不是A→Ab”写SDT时会检查{}是否紧贴非终结符右侧。这些细节不是刁难而是南开用三年真题刻下的校准线编译器不是理论玩具它是字符流穿过缓冲区、状态在DFA中跳转、预测表在内存里查表、属性值沿语法树流淌的精密流水线。希望帮到你。本文还有配套的精品资源点击获取