简介本资源是南开大学编译原理课程期末复习的权威知识点精要总结面向计算机专业本科生及考研备考学生系统解决编译原理核心概念理解难、知识碎片化、考点覆盖不全等痛点。全文34页Word文档.docx格式完整涵盖词法分析正则表达式建模、Thompson构造法、NFA/DFA转换、语法分析LL(1)预测分析表构建、FIRST/FOLLOW集计算、SLR/LALR冲突辨析、语法制导翻译、中间代码生成及运行时刻环境等六大核心章节内容严格对标高校教学大纲与期末高频考点。资源包仅含1个高质量可编辑文档大小5.94MB结构清晰、公式规范、图示丰富便于打印背诵与电子标注。已有1744人学习下载特别适合考前冲刺梳理知识脉络、快速掌握有限状态机建模、上下文无关文法判定、移进-归约冲突解决等关键能力。1. 这份南开大学编译原理期末复习资料不是“背多分”的清单而是帮你把龙书《编译原理》龙书第三版里分散在第2、3、4、6、7章的抽象概念拧成一条可调试、可验证、可画图的逻辑链很多同学拿到“知识点总结”就直接开背词法分析器正则表达式DFA语法分析器LL(1)/LR(0)/SLR(1)中间代码三地址码……结果一到考场上看到“请画出输入ab*c的语法树并生成四元式序列”脑子瞬间空白——因为没真正跑过一个词法分析器没见过DFA状态跳转时输入缓冲区的真实指针位置也没手动推导过FIRST/FOLLOW集如何影响预测分析表的填空。这份2020年南开大学课堂实际使用的复习材料核心价值在于它把编译前端的每个环节都锚定在可执行、可观察、可反向验证的操作点上用Flex手写一个能识别int x 3 4 * 5;的词法分析器用Yacc/Bison构造一个支持左递归消除的算术表达式语法分析器用Python脚本模拟语法制导翻译过程实时输出四元式。它面向的是需要在期末前72小时快速建立编译流程直觉的计算机专业本科生尤其适合已学完龙书前三章但对“语法分析器到底怎么调用词法分析器”仍模糊的同学。2. 用Flex手写词法分析器从正则定义到可执行的.c文件关键在状态机与保留字优先级编译原理期末复习中词法分析绝不是默写正则式那么简单。南开大学2020年期末考题明确要求考生根据给定的C语言子集含int/float/if/else/运算符/标识符/数字字面量写出Flex规范文件并说明为何if必须在identifier规则之前。这背后是词法分析器的核心机制最长匹配原则 规则书写顺序决定优先级。2.1 Flex规范文件结构与南开考题适配要点Flex规范文件分为三部分定义段%{...%}、规则段正则式动作、用户代码段%%之后。南开复习强调必须掌握以下三点保留字必须前置if、else等关键字的正则式必须写在[a-zA-Z][a-zA-Z0-9]*标识符之前否则所有关键字都会被识别为标识符浮点数需处理.123和123.两种形式不能只写[0-9]\.[0-9]而要覆盖[0-9]*\.[0-9]和[0-9]\.[0-9]*注释需跳过而非返回TOKEN/*[^*]*\*([^/*][^*]*\*)*/应执行yyless(yylen-2);回退并忽略而非返回COMMENTtoken。%{ #include stdio.h #include string.h extern int yylval; %} %% if { printf(IF: %s\n, yytext); return IF; } else { printf(ELSE: %s\n, yytext); return ELSE; } int { printf(INT: %s\n, yytext); return INT; } float { printf(FLOAT: %s\n, yytext); return FLOAT; } [a-zA-Z][a-zA-Z0-9]* { printf(ID: %s\n, yytext); yylval strdup(yytext); return IDENTIFIER; } [0-9]\.?[0-9]* { printf(NUM: %s\n, yytext); yylval strdup(yytext); return NUMBER; } [\\-\*\/\\;\(\)\{\}] { printf(OP/SEP: %s\n, yytext); return *yytext; } [ \t\n] ; /* 忽略空白 */ . { printf(ERROR: %s\n, yytext); } %% int yywrap() { return 1; }提示南开期末实验题常要求修改此文件以支持、--自增运算符。正确做法是添加和--规则并置于、-单字符规则之前否则会被拆成两个token。2.2 生成可执行分析器的完整命令链与调试技巧仅写.l文件不够必须完成编译-链接-运行闭环。南开课程实验环境为Ubuntu 18.04 gcc 7.5命令如下# 1. 生成lex.yy.c注意-d参数开启调试会打印每次匹配的token flex -d -o lex.yy.c lexer.l # 2. 编译需链接Flex库-lfl是关键 gcc -o lexer lex.yy.c -lfl # 3. 运行并输入测试串CtrlD结束 ./lexer int x 3 4 * 5;输出示例INT: int ID: x OP/SEP: NUM: 3 OP/SEP: NUM: 4 OP/SEP: * NUM: 5 OP/SEP: ;注意若出现undefined reference to yywrap错误说明未提供yywrap()实现。南开标准解法是在%%后添加int yywrap() { return 1; }而非使用-lfl链接库中的默认实现——因考试环境禁用动态链接必须显式定义。2.3 状态机可视化用flex -v生成状态转移表并人工验证Flex内部将正则式编译为DFA。南开复习强调理解DFA而非死记状态数。执行flex -v lexer.l会输出状态统计如12 states, 45 transitions但更重要的是通过-v生成的.tab.c文件中yy_nxt[]数组反推状态跳转。例如当输入if时初始状态0读入i→ 跳转到状态1状态1读入f→ 跳转到状态2接受态若状态1读入g则跳转到失败状态触发回退匹配标识符规则。这种逐字符跟踪能力是应对“给出输入串inta说明词法分析器如何识别”的考题的关键。3. 构建LL(1)语法分析器从文法改写到预测分析表手工填空南开考题必考FIRST/FOLLOW集推导南开大学编译原理期末试卷中“构造LL(1)分析表”是固定大题15分且明确要求写出完整的FIRST集、FOLLOW集推导过程。这不是套公式而是检验你是否理解非终结符的可达性与终结符的上下文约束。以龙书P102习题4.2的文法为例E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | id3.1 FIRST集推导抓住“ε-产生式传播”这一南开高频陷阱FIRST集计算有三条规则南开考题常设坑在第三条若A→B₁B₂…Bₖ且B₁…Bᵢ₋₁均可推出ε则FIRST(A)包含FIRST(Bᵢ)∪…∪FIRST(Bₖ)若所有Bⱼ都可推出ε则FIRST(A)包含ε。以E为例E → T E⇒ FIRST(E) ⊇ FIRST() {}E → ε⇒ FIRST(E) ⊇ {ε}因此FIRST(E) {, ε}但学生易错在TT → * F T⇒ FIRST(T) ⊇ {*}T → ε⇒ FIRST(T) ⊇ {ε}错误答案{} ∪ {ε} {, ε} —— 正确常见误答{*} —— 忘记ε产生式提示南开阅卷标准中漏写ε扣3分FIRST集错1个元素扣1分推导步骤缺失扣2分。3.2 FOLLOW集推导紧扣“句柄右边界”与“父产生式左部FOLLOW传播”FOLLOW集本质是问当某非终结符A出现在某个产生式右部时其后可能出现什么终结符南开强调三个传播路径S → S⇒$∈ FOLLOW(S)A → αBβ⇒ FIRST(β) \ {ε} ⊆ FOLLOW(B)A → αB或A → αBβ 且 ε ∈ FIRST(β)⇒ FOLLOW(A) ⊆ FOLLOW(B)以E为例E → T E⇒ FOLLOW(E) ⊇ FOLLOW(E) {$}因E是开始符号E → T E⇒ FOLLOW(E) ⊇ FOLLOW(E)自循环无新信息故FOLLOW(E) {$}而TT → F T⇒ FOLLOW(T) ⊇ FOLLOW(T)T → * F T⇒ FOLLOW(T) ⊇ FOLLOW(T)E → T E⇒ T后是E且ε ∈ FIRST(E) ⇒ FOLLOW(T) ⊇ FOLLOW(E) {$}所以FOLLOW(T) {$, }3.3 预测分析表手工填空用南开标准表格格式与冲突检测南开期末要求用固定格式填表行非终结符列终结符含$单元格产生式编号或error。以E行为例$EE→TEE→ε填表规则若a ∈ FIRST(α)则M[A,a] A→α若ε ∈ FIRST(α) 且 b ∈ FOLLOW(A)则M[A,b] A→α其余填error冲突检测是南开重点若同一单元格填入多个产生式即为LL(1)文法不成立。例如若E→ε和E→TE同时填入M[E,]则冲突。南开考题常给出含左递归文法要求先消除左递归再判断是否LL(1)。4. 语法制导翻译实战用Python模拟属性计算生成四元式并验证ab*c的运算优先级南开2020期末最后一道大题20分“对输入x a b * c画出抽象语法树AST并写出按深度优先遍历顺序生成的四元式序列”。这题考察的不是记忆四元式格式而是如何让语法分析过程携带语义动作。龙书第5章讲属性文法但南开复习用Python脚本实现简化版让学生亲手看到*节点如何比节点先生成四元式。4.1 AST节点设计与四元式生成规则南开标准四元式格式为(op, arg1, arg2, result)其中op为、*、等arg1/arg2为标识符或临时变量result为左值。关键规则二元运算先递归生成左右子树的四元式再生成当前运算的四元式result为新临时变量如t1赋值运算右子树生成所有四元式后最后生成(, right_result, _, left_id)。Python模拟代码简化版class Node: def __init__(self, op, leftNone, rightNone, valueNone): self.op op # , *, , id, num self.left left self.right right self.value value # for id/num def gen_quads(node, temp_counter[0]): if node.op id or node.op num: return [], node.value # 叶子节点不生成四元式返回自身值 quads [] if node.op in [, *]: # 先生成左右子树四元式 left_quads, left_res gen_quads(node.left, temp_counter) right_quads, right_res gen_quads(node.right, temp_counter) quads.extend(left_quads) quads.extend(right_quads) # 生成当前运算四元式 temp_counter[0] 1 temp ft{temp_counter[0]} quads.append((node.op, left_res, right_res, temp)) return quads, temp if node.op : # 右子树生成所有四元式 right_quads, right_res gen_quads(node.right, temp_counter) quads.extend(right_quads) # 最后生成赋值四元式 quads.append((, right_res, _, node.left.value)) return quads, node.left.value # 构建 x a b * c 的AST c Node(id, valuec) b Node(id, valueb) a Node(id, valuea) x Node(id, valuex) mult Node(*, b, c) # b * c add Node(, a, mult) # a (b * c) assign Node(, x, add) # x (a (b * c)) quads, _ gen_quads(assign) for q in quads: print(q)输出(*, b, c, t1) (, a, t1, t2) (, t2, _, x)逻辑说明mult节点先生成(*, b, c, t1)add节点再生成(, a, t1, t2)最后assign生成(, t2, _, x)。这严格体现了*优先于的语义且*的四元式必然在之前——因为AST中*是的右子节点深度优先遍历先访问右子树。4.2 南开考题验证如何用四元式反推AST结构期末考题常反向出题“给定四元式序列画出对应AST”。解法是从后往前逆向构建最后一条四元式(, t2, _, x)⇒ 根节点为左孩子为x右孩子待定倒数第二条(, a, t1, t2)⇒t2是的结果故节点右孩子指向x的父节点第一条(*, b, c, t1)⇒t1是*的结果而的右操作数是t1故*是的右孩子。此逆向思维训练正是南开强调的“从代码到结构”的编译器视角。5. 期末冲刺技巧用3个真题验证法快速定位知识盲区避开南开高频扣分点南开编译原理期末阅卷有明确扣分项与其盲目刷题不如用真题验证法精准打击。以下是2020年试卷中暴露的三大高频失分场景及对应的自查方法。5.1 “词法分析器无法识别123.”——检查浮点数正则式的覆盖完整性南开考题曾给出输入float y 123.;要求写出词法分析器输出。近40%学生漏掉.123和123.形式只写[0-9]\.[0-9]。自查方法手写三个测试串——0.5、.7、3.运行你的Flex程序观察是否全部识别为NUM。若.7被识别为ERROR说明正则式缺少[0-9]*\.分支。5.2 “LL(1)分析表填错M[E, $]”——用FOLLOW集定义反推而非死记学生常机械记忆“FOLLOW(E) {$}”但不知为何。自查方法拿出一张纸只写E → T E这一条产生式问自己“E后面可能跟什么”答案只能是$因为E是开始符号句型结束或若E后接则来自E → T E但此时属于E的FIRST集不是FOLLOW。因此FOLLOW(E) {$}。此法比背结论可靠十倍。5.3 “四元式生成顺序颠倒”——用AST后序遍历口诀强制校验南开标准答案要求四元式按“左子树→右子树→根”顺序生成。自查口诀“先算儿子再算爹”。对a b * c*是的儿子所以*的四元式必须在之前。若你写的四元式是(, a, b, t1)在前(*, t1, c, t2)在后立刻重画AST——说明你把当成了根而*当成了右孩子但实际*应是的右孩子的右孩子。提示南开期末允许使用铅笔在试卷上画小AST草图阅卷老师认可草图辅助推理。不要怕画错画比不画得分高。最后打开你的Flex文件输入123.拿出草稿纸推导T的FOLLOW集再手写x a b * c的AST。这三个动作做完你就已经站在了及格线之上。本文还有配套的精品资源点击获取