简介面向南航计算机科学与技术/物联网工程专业学生的编译原理实验包聚焦词法分析器与语法分析器设计帮助学习者把正则表达式、状态机、上下文无关文法、递归下降等理论转化为可运行的C代码。整个压缩包共7个文件含2个C源文件词法分析器与语法分析器、2个可执行的exe程序以及3个txt文本包括测试代码和说明体积仅1.01MB便于快速下载与本地实验。词法分析器演示如何将源代码拆分为Token语法分析器覆盖LL(1)、LR(0)、LALR(1)等解析方式并生成抽象语法树测试代码覆盖正常输入与非法字符、括号不匹配、语法错误等场景方便对照源码排查问题也能借此熟悉编译器错误处理机制。目前已有602人学习/下载适合正在修读编译原理、需要搭建实验环境或复习考试的学生参考。1. 南航编译原理实验到底在练什么把字符流变成可执行行为这是编译器最基础的承诺也是多数人在《编译原理》课程里第一次真正和它较劲的地方。NUAA 计算机科学与技术专业和物联网工程专业共用一套编译原理实验包差别只在个别实验的选做项和验收要求上核心路径是一样的词法分析、语法分析、语义分析与中间代码生成、目标代码生成。这套实验的难点不在“读懂龙书”而在“把理论变成可运行的代码”——文法消左递归了但 First/Follow 算错状态机写出来了但最长匹配没做三地址码生成了但临时变量命名和符号表对不上。本文按一套常见、可复现的方案把这些环节串起来附带可直接抄的代码和排错手段适合正在做南航编译实验、或者手头有一套类似课程设计想找参照的人。2. 词法分析实验从正则到状态机落地2.1 先决定手写还是生成再谈精度南航实验一般允许手写词法分析器也允许用 flex 生成 C 代码后再包装。我的建议是如果目标是理解原理手写如果目标是快速完成并保证鲁棒性用 flex。但无论哪种都绕不开三个核心概念正则表达式、NFA/DFA、最长匹配。手写方案里最简单的可靠模型是“表驱动状态机”。先把 token 按正则语义归类标识符、关键字、十进制/十六进制整数、浮点数、字符串、运算符、分隔符、注释。随后为每一类维护一个“进入条件”在读字符时判断是否可以从当前状态迁移。这里的关键不是一次把 DFA 画全而是用字符类简化转移表——数字、字母、可打印符号、引号、换行每个入口只用几类。flex 方案的优势在于它能自动处理 DFA 最小化并内置“最长匹配”语义直接规避手写时容易漏掉的边界问题。但课程验收经常要求提交“状态转换图”或“NFA 构造过程”所以手写一次对答辩更有利。2.2 表驱动状态机的核心代码下面给出一段可直接改写的核心实现语言用 Python方便你在原型阶段跑通逻辑再翻译成 C/C 交作业。它不追求覆盖全部 token而是把骨架立住。import re # 字符类编号0 字母1 数字2 空白3 运算符4 其他 def char_class(ch): if ch.isalpha() or ch _: return 0 if ch.isdigit(): return 1 if ch.isspace(): return 2 if ch in -*/,;(){}[]!: return 3 return 4 # 状态转移表状态 - 字符类 - 新状态 # -1 表示无法迁移需触发回退 trans [ # 状态0初始 {0: 1, 1: 2, 2: 0, 3: 5, 4: -1}, # 状态1标识符/关键字 {0: 1, 1: 1, 2: -1, 3: -1, 4: -1}, # 状态2数字 {0: -1, 1: 2, 2: -1, 3: -1, 4: -1}, # 状态3注释中预留 {0: 3, 1: 3, 2: 3, 3: 3, 4: 3}, # 状态4字符串中预留 {0: 4, 1: 4, 2: 4, 3: 4, 4: 4}, # 状态5单个运算符立即返回 {0: -1, 1: -1, 2: -1, 3: -1, 4: -1}, ] KEYWORDS {if, else, while, return, int, void, float} def tokenize(text): tokens [] i 0 n len(text) while i n: while i n and text[i].isspace(): i 1 if i n: break start i state 0 while i n: cls char_class(text[i]) nxt trans[state][cls] if nxt -1: break state nxt # 注释与字符串在完整代码里要单独处理 i 1 if i start: # 无法识别的字符报错后前进一位 raise ValueError(funexpected char: {text[i]!r} at {i}) lexeme text[start:i] if state 1: tok_type KEYWORD if lexeme in KEYWORDS else IDENT elif state 2: tok_type INT else: tok_type state tokens.append((tok_type, lexeme)) return tokens这个实现的要点有三个。第一char_class做字符归类把任意 ASCII 字符压缩到 5 类转移表就能用二维数组保存第二遇到nxt -1时停止读取并回退这一步就是“最长匹配”的实现基础——最后被接受的 token 是上一次有效迁移的结果而不是当前字符所在的非法状态第三KEYWORDS集合采用“先识别为标识符、再查关键字表”的策略这是编译器领域的常见做法避免为每个关键字单独画一条 DFA 路径。2.3 注释、字符串和错误恢复很多实验只要求处理//行注释和/* */块注释但验收时老师常会给含有字符串常量的测试用例里面可能夹杂着注释符号。这里推荐“优先级法”在状态机的入口处每次先看是否进入注释或字符串再走普通 token 路径。错误恢复策略直接决定鲁棒性。最简单的方案是“报错并跳过单字符”也就是当转移表无法迁移且没有已接受状态时打印一条带行列号的错误信息然后i 1继续扫描。不要一遇错就终止整个程序——实验的测试脚本经常在同一文件里放多个错误期望你全部报出来。如果你在 C 语言版本里想统计行列号可以在char_class之外维护line和col每读一个字符就更新。词法阶段的错误只影响该 token语法阶段还需要额外的同步策略但那是下一章的事。3. 语法分析实验从 LL(1) 到递归下降的选择3.1 LL(1) 的建表流程语法分析是南航编译实验里筛选度最高的一环因为它的输入是从词法分析器传过来的 token 流而老师给的测试用例经常包含“合法但反直觉”的表达式嵌套。常见要求是实现一个 LL(1) 预测分析器支持算术表达式、布尔表达式、赋值语句和 if/while 语句。LL(1) 能用的前提是文法满足两个条件无左递归、同一非终结符的各产生式首符集不相交。先把文法改写成 EBNF 或消除左递归的形式然后求每个非终结符的 First 和 Follow最后填预测分析表。下面是一个简化文法program - stmt_list stmt_list - stmt stmt_list | ε stmt - assign | if_stmt | while_stmt assign - ID expr ; expr - term expr expr - term expr | - term expr | ε term - factor term term - * factor term | / factor term | ε factor - ( expr ) | NUM | ID手动填表的检查技巧是对每个非终结符 A 的每个产生式A - α把 First(α) 里的每个终结符放到M[A, 终结符]若 α 能推导出 ε还要把 Follow(A) 里的每个终结符填进去。如果某格子里出现两个产生式就说明文法不是 LL(1)需要提取左因子。这里最常见的坑是“ε 的产生式判断错误”比如把expr的空串能力漏掉导致;或)处没有入口分析器直接报错。3.2 用内存表实现预测分析下面给出一段可运行的分析器骨架它直接使用上一节的预言分析表输入是 token 类型序列输出是匹配/错误位置。PREDICT_TABLE { # 非终结符 - { 终结符: 产生式右侧 } expr: {ID: [term, expr\]}, expr\: {: [, term, expr\], -: [-, term, expr\], ): [], ;: []}, # ε 产生式 term: {ID: [factor, term\]}, term\: {*: [*, factor, term\], /: [/, factor, term\], : [], -: [], ): [], ;: []}, factor: {ID: [ID], NUM: [NUM], (: [(, expr, )]}, } def predict_parse(tokens): stack [program, EOF] idx 0 while stack: top stack.pop() if top EOF: if idx len(tokens): return True else: raise SyntaxError(funexpected extra tokens: {tokens[idx:]}) if top in {ID, NUM, , -, *, /, (, ), ;}: if idx len(tokens) and tokens[idx] top: idx 1 else: raise SyntaxError(fexpect {top} but got {tokens[idx] if idx len(tokens) else EOF}) else: nxt tokens[idx] if idx len(tokens) else EOF if nxt not in PREDICT_TABLE[top]: raise SyntaxError(fno rule for {top} at {nxt}) prod PREDICT_TABLE[top][nxt] # 逆序入栈保证栈顶是符号串左端 for sym in reversed(prod): stack.append(sym) return idx len(tokens) # 测试 # tokens [ID, , NUM, ;, EOF]关键点有三。第一prod逆序入栈符合“栈顶对应最左待匹配符号”的算法约定第二ε产生式用空列表表示遇到后直接跳过不消费输入也不入栈这是处理expr在)和;之后必须消失的机制第三终结符出栈时与当前 token 比较匹配失败立即抛出带位置的异常。3.3 冲突发生时怎么排查当PredictTable[非终结符][终结符]出现两个产生式时肉眼检查 First 集合往往最有效。一个常见场景是if_stmt - if ( expr ) stmt | if ( expr ) stmt else stmt这种悬挂 else 会让两个产生式的 First 集合完全相同LL(1) 无法处理。南航实验的通常解法是要求你修改文法引入matched_stmt和unmatched_stmt两个非终结符来区分这是龙书里的标准做法。另一种冲突来自 First/Follow 交叠常常出现在expr这类“左递归消除后带 ε”的非终结符上。排查方法是先单独打印每个非终结符的 First 和 Follow再手动查看是否存在某个终结符同时出现在First(α)和Follow(A)中。若出现说明原来的文法在消除左递归后产生了新的二义性需要重新检查产生式的左因子。许多同学在这里卡住其实是前面词法阶段把拆成了和导致语法阶段永远匹配不到完整的关系运算。4. 语义分析与中间代码生成把语法树变成三地址码4.1 符号表与分程序结构语法分析通过后接下来是语义分析和中间代码生成。南航实验对中间代码的要求一般是三地址码或四元式形式不做强制但要求能够在静态检查阶段报告变量未声明、类型不匹配、函数参数个数不对等错误。符号表这时候要能支撑作用域嵌套——最常见的设计是用“栈 哈希表”每进入一个新的块函数体、if 分支、while 体压入一层新的作用域声明变量时在栈顶作用域插入条目查找变量时从栈顶向下逐层查找找到即返回。如果实验要求支持函数符号表需要额外保存返回值类型和参数类型列表。反例是只用一个全局哈希表这会导致不同作用域的同名变量互相覆盖在后续函数实验里极难调试。常见的简单实现是 Python 里的list[dict]或者 C 里的std::vectorstd::unordered_mapstd::string, Symbol。4.2 语法制导翻译的基本写法中间代码生成通常和语法分析合并实现这样不用单独建 AST缺点是调试时很难看清结构。另一种做法是在语法分析时建一棵语法树再对树做一次翻译。推荐后者因为语义检查的很多边界情况需要回溯父节点上下文单独的树结构更方便。下面给出用表达式求值式翻译的伪代码骨架。# 假设 ast 是 dict例如 {type: binop, op: , left: ..., right: ...} temp_index 0 code [] def new_temp(): global temp_index t ft{temp_index} temp_index 1 return t def gen_expr(node): if node[type] num: t new_temp() code.append((t, :, node[value])) return t if node[type] id: return node[name] if node[type] binop: l gen_expr(node[left]) r gen_expr(node[right]) t new_temp() code.append((t, :, l, node[op], r)) return t这段代码的核心逻辑是把a b * c转换为类似t0 : b; t1 : c; t2 : t0 * t1; t3 : a t2的三地址码。gen_expr深度优先遍历树先为每个子表达式分配一个临时变量再把运算符和左右操作数写入一条四元式。t : l op r的四元式格式虽然简单但已经能覆盖赋值的右值表达式部分。4.3 四元式的输出与类型强制南航实验要求检查类型匹配最常见的是整型与浮点型的混合运算。这里有一个快速实现路径每个符号表条目里保存type字段gen_expr在生成binop之前先检查左右子树类型不一致时根据语言语义决定是报错还是自动插入类型转换四元式。比如int float通常先生成一条t : int_to_float(int_val)再生成加法。四元式输出建议直接打印成一行一条方便和课程给的答案对照。比如输出文件每行格式为op, arg1, arg2, result其中空白操作数用_表示。这里有一个严重但隐蔽的坑临时变量命名。如果每个子表达式都新分配临时变量生成代码会很长但正确如果试图复用临时变量必须考虑活跃区间。初版建议不优化直接用递增编号后面进阶再改成简单的栈式分配。5. 目标代码生成与运行栈式虚拟机的实现5.1 指令集设计中间代码生成之后南航实验很多版本要求“模拟执行”这段代码也就是不生成真正的 x86而是写一个自定义指令集的解释器。这是最容易被低估的一章——语法分析做得再漂亮解释器执行不了、指令语义和栈状态对不上分数同样垮掉。我一般建议采用栈式虚拟机原因是栈机与前后端解耦且调试时只需要关注操作数栈和指令指针两个状态。指令集可以设计为指令含义栈效果PUSH n将字面量 n 压栈栈顶增加 nLOAD name将局部变量 name 的值压栈栈顶增加该变量的值STORE name弹出栈顶值写入 name栈顶减少一个值ADD / SUB / MUL / DIV弹出两个操作数运算回推结果栈顶减少一个值JMP addr无条件跳转无JMPF addr弹出条件值为假则跳转栈顶减少一个值HALT结束执行无这里的关键设计决策是“把等号右边算完再整体赋值”STORE直接对栈顶变量作用与 x86 里的mov类似。若你的中间代码是三地址码而不是栈式字节码可以先写一个“三地址码到栈式指令”的翻译层或者干脆让解释器直接逐条模拟四元式。两种都能交差只不过栈式指令更容易拍出栈变化图方便验收时画图讲解。5.2 解释器的执行循环下面给出一个最小但完整的解释器核心循环指令集用上述表格。class VM: def __init__(self, instructions): self.code instructions self.stack [] self.vars {} self.ip 0 def run(self, max_steps10000): step 0 while self.ip len(self.code): step 1 if step max_steps: raise RuntimeError(step limit exceeded, possible infinite loop) op, arg self.code[self.ip] self.ip 1 if op PUSH: self.stack.append(arg) elif op LOAD: self.stack.append(self.vars[arg]) elif op STORE: self.vars[arg] self.stack.pop() elif op ADD: r self.stack.pop() l self.stack.pop() self.stack.append(l r) elif op SUB: r self.stack.pop() l self.stack.pop() self.stack.append(l - r) elif op MUL: r self.stack.pop() l self.stack.pop() self.stack.append(l * r) elif op DIV: r self.stack.pop() l self.stack.pop() if r 0: raise ZeroDivisionError(division by zero) self.stack.append(l / r) elif op JMP: self.ip arg elif op JMPF: v self.stack.pop() if not v: self.ip arg elif op HALT: return self.vars return self.vars执行循环里的每一条指令都只有一个明确的职责因此调试时只需要盯住两个东西self.stack的栈顶两元素和self.ip的位置。max_steps参数建议保留后面我会展开说它的救场价值。你可以把三地址码手工翻译成栈式指令让一段简单的a 2 3先跑起来再逐步扩展循环和条件分支。5.3 中间代码和栈帧如何对应函数调用是实验里最容易崩的部分。简单方案是给每个函数一个独立的vars字典调用时新建一个帧返回时把结果压回调用方的栈。由于课程实验一般不要求递归深度很大浮点参数等细节也可简化但需要处理参数传递的顺序——常见约定是“从右到左压栈”这样函数内部取第一个参数时栈顶刚好是它。如果你的实验要求支持数组和指针栈机的结构需要增加“地址”概念。这时推荐在四元式阶段就区分“变量的值”和“变量的地址”用LOADA/STOREA这样的复合指令来规避解释器内部的隐式唯一地址。这个区分看似多此一举但对后续扩展指针算术非常关键。6. 调试技巧给编译器加日志和防死循环护栏调试编译器最痛苦的是“不知道当前停在哪、下一步该做什么”。我个人的经验是在编码早期就加入两类护栏执行步数上限和分级日志开关。步数上限对语法分析器和栈式虚拟机都适用。语法分析器的死循环通常表现为“分析栈不空但输入不前进”原因多为 ε 产生式递归设置错误虚拟机的死循环则表现为 IP 在同一段指令上反复跳转。两者都可以靠一个计数器强行终止并打印当前栈深或栈顶快照。一个实用做法是维护一个debug布尔变量打开后在每个循环里打印当前输入 token、栈状态和分析动作关闭时则完全静默不影响验收时的标准输出。另一个值得投入的技巧是构造“最小回归用例集”。不要一上来就用老师给的大样例先准备 10 个以内的语句比如a 1;、a b c * 2;、if (a) { b 1; }、while (a 10) { a a 1; }。每个用例对应一条已知正确的中间代码输出改一次代码就全量跑一遍。这个做法能在几分钟内定位是词法层的错误还是语法层的错误因为你能直接看出第一个报错出现在哪条用例上。如果某个用例在语法分析栈里走到一半停住就在那个非终结符的入口打印 First 集合和当前符号通常很快就能找到是哪条产生式没有填进预测表。最后如果中间代码已经生成但执行结果不对一个高效的验证办法是在四元式输出里手动模拟一份“期望值”。例如把t2 : t0 * t1这行在注释里写出你手工计算的 t2 值然后运行解释器比对。这个方法朴素但比单步调试更快尤其是当错误出现在类型转换时——那里通常表现为结果溢出或变成很大的负数看一眼四元式是否插入转换指令就能定位。本文还有配套的精品资源点击获取 南航编译原理实验实践指南：词法分析到目标代码生成全解析
简介面向南航计算机科学与技术/物联网工程专业学生的编译原理实验包聚焦词法分析器与语法分析器设计帮助学习者把正则表达式、状态机、上下文无关文法、递归下降等理论转化为可运行的C代码。整个压缩包共7个文件含2个C源文件词法分析器与语法分析器、2个可执行的exe程序以及3个txt文本包括测试代码和说明体积仅1.01MB便于快速下载与本地实验。词法分析器演示如何将源代码拆分为Token语法分析器覆盖LL(1)、LR(0)、LALR(1)等解析方式并生成抽象语法树测试代码覆盖正常输入与非法字符、括号不匹配、语法错误等场景方便对照源码排查问题也能借此熟悉编译器错误处理机制。目前已有602人学习/下载适合正在修读编译原理、需要搭建实验环境或复习考试的学生参考。1. 南航编译原理实验到底在练什么把字符流变成可执行行为这是编译器最基础的承诺也是多数人在《编译原理》课程里第一次真正和它较劲的地方。NUAA 计算机科学与技术专业和物联网工程专业共用一套编译原理实验包差别只在个别实验的选做项和验收要求上核心路径是一样的词法分析、语法分析、语义分析与中间代码生成、目标代码生成。这套实验的难点不在“读懂龙书”而在“把理论变成可运行的代码”——文法消左递归了但 First/Follow 算错状态机写出来了但最长匹配没做三地址码生成了但临时变量命名和符号表对不上。本文按一套常见、可复现的方案把这些环节串起来附带可直接抄的代码和排错手段适合正在做南航编译实验、或者手头有一套类似课程设计想找参照的人。2. 词法分析实验从正则到状态机落地2.1 先决定手写还是生成再谈精度南航实验一般允许手写词法分析器也允许用 flex 生成 C 代码后再包装。我的建议是如果目标是理解原理手写如果目标是快速完成并保证鲁棒性用 flex。但无论哪种都绕不开三个核心概念正则表达式、NFA/DFA、最长匹配。手写方案里最简单的可靠模型是“表驱动状态机”。先把 token 按正则语义归类标识符、关键字、十进制/十六进制整数、浮点数、字符串、运算符、分隔符、注释。随后为每一类维护一个“进入条件”在读字符时判断是否可以从当前状态迁移。这里的关键不是一次把 DFA 画全而是用字符类简化转移表——数字、字母、可打印符号、引号、换行每个入口只用几类。flex 方案的优势在于它能自动处理 DFA 最小化并内置“最长匹配”语义直接规避手写时容易漏掉的边界问题。但课程验收经常要求提交“状态转换图”或“NFA 构造过程”所以手写一次对答辩更有利。2.2 表驱动状态机的核心代码下面给出一段可直接改写的核心实现语言用 Python方便你在原型阶段跑通逻辑再翻译成 C/C 交作业。它不追求覆盖全部 token而是把骨架立住。import re # 字符类编号0 字母1 数字2 空白3 运算符4 其他 def char_class(ch): if ch.isalpha() or ch _: return 0 if ch.isdigit(): return 1 if ch.isspace(): return 2 if ch in -*/,;(){}[]!: return 3 return 4 # 状态转移表状态 - 字符类 - 新状态 # -1 表示无法迁移需触发回退 trans [ # 状态0初始 {0: 1, 1: 2, 2: 0, 3: 5, 4: -1}, # 状态1标识符/关键字 {0: 1, 1: 1, 2: -1, 3: -1, 4: -1}, # 状态2数字 {0: -1, 1: 2, 2: -1, 3: -1, 4: -1}, # 状态3注释中预留 {0: 3, 1: 3, 2: 3, 3: 3, 4: 3}, # 状态4字符串中预留 {0: 4, 1: 4, 2: 4, 3: 4, 4: 4}, # 状态5单个运算符立即返回 {0: -1, 1: -1, 2: -1, 3: -1, 4: -1}, ] KEYWORDS {if, else, while, return, int, void, float} def tokenize(text): tokens [] i 0 n len(text) while i n: while i n and text[i].isspace(): i 1 if i n: break start i state 0 while i n: cls char_class(text[i]) nxt trans[state][cls] if nxt -1: break state nxt # 注释与字符串在完整代码里要单独处理 i 1 if i start: # 无法识别的字符报错后前进一位 raise ValueError(funexpected char: {text[i]!r} at {i}) lexeme text[start:i] if state 1: tok_type KEYWORD if lexeme in KEYWORDS else IDENT elif state 2: tok_type INT else: tok_type state tokens.append((tok_type, lexeme)) return tokens这个实现的要点有三个。第一char_class做字符归类把任意 ASCII 字符压缩到 5 类转移表就能用二维数组保存第二遇到nxt -1时停止读取并回退这一步就是“最长匹配”的实现基础——最后被接受的 token 是上一次有效迁移的结果而不是当前字符所在的非法状态第三KEYWORDS集合采用“先识别为标识符、再查关键字表”的策略这是编译器领域的常见做法避免为每个关键字单独画一条 DFA 路径。2.3 注释、字符串和错误恢复很多实验只要求处理//行注释和/* */块注释但验收时老师常会给含有字符串常量的测试用例里面可能夹杂着注释符号。这里推荐“优先级法”在状态机的入口处每次先看是否进入注释或字符串再走普通 token 路径。错误恢复策略直接决定鲁棒性。最简单的方案是“报错并跳过单字符”也就是当转移表无法迁移且没有已接受状态时打印一条带行列号的错误信息然后i 1继续扫描。不要一遇错就终止整个程序——实验的测试脚本经常在同一文件里放多个错误期望你全部报出来。如果你在 C 语言版本里想统计行列号可以在char_class之外维护line和col每读一个字符就更新。词法阶段的错误只影响该 token语法阶段还需要额外的同步策略但那是下一章的事。3. 语法分析实验从 LL(1) 到递归下降的选择3.1 LL(1) 的建表流程语法分析是南航编译实验里筛选度最高的一环因为它的输入是从词法分析器传过来的 token 流而老师给的测试用例经常包含“合法但反直觉”的表达式嵌套。常见要求是实现一个 LL(1) 预测分析器支持算术表达式、布尔表达式、赋值语句和 if/while 语句。LL(1) 能用的前提是文法满足两个条件无左递归、同一非终结符的各产生式首符集不相交。先把文法改写成 EBNF 或消除左递归的形式然后求每个非终结符的 First 和 Follow最后填预测分析表。下面是一个简化文法program - stmt_list stmt_list - stmt stmt_list | ε stmt - assign | if_stmt | while_stmt assign - ID expr ; expr - term expr expr - term expr | - term expr | ε term - factor term term - * factor term | / factor term | ε factor - ( expr ) | NUM | ID手动填表的检查技巧是对每个非终结符 A 的每个产生式A - α把 First(α) 里的每个终结符放到M[A, 终结符]若 α 能推导出 ε还要把 Follow(A) 里的每个终结符填进去。如果某格子里出现两个产生式就说明文法不是 LL(1)需要提取左因子。这里最常见的坑是“ε 的产生式判断错误”比如把expr的空串能力漏掉导致;或)处没有入口分析器直接报错。3.2 用内存表实现预测分析下面给出一段可运行的分析器骨架它直接使用上一节的预言分析表输入是 token 类型序列输出是匹配/错误位置。PREDICT_TABLE { # 非终结符 - { 终结符: 产生式右侧 } expr: {ID: [term, expr\]}, expr\: {: [, term, expr\], -: [-, term, expr\], ): [], ;: []}, # ε 产生式 term: {ID: [factor, term\]}, term\: {*: [*, factor, term\], /: [/, factor, term\], : [], -: [], ): [], ;: []}, factor: {ID: [ID], NUM: [NUM], (: [(, expr, )]}, } def predict_parse(tokens): stack [program, EOF] idx 0 while stack: top stack.pop() if top EOF: if idx len(tokens): return True else: raise SyntaxError(funexpected extra tokens: {tokens[idx:]}) if top in {ID, NUM, , -, *, /, (, ), ;}: if idx len(tokens) and tokens[idx] top: idx 1 else: raise SyntaxError(fexpect {top} but got {tokens[idx] if idx len(tokens) else EOF}) else: nxt tokens[idx] if idx len(tokens) else EOF if nxt not in PREDICT_TABLE[top]: raise SyntaxError(fno rule for {top} at {nxt}) prod PREDICT_TABLE[top][nxt] # 逆序入栈保证栈顶是符号串左端 for sym in reversed(prod): stack.append(sym) return idx len(tokens) # 测试 # tokens [ID, , NUM, ;, EOF]关键点有三。第一prod逆序入栈符合“栈顶对应最左待匹配符号”的算法约定第二ε产生式用空列表表示遇到后直接跳过不消费输入也不入栈这是处理expr在)和;之后必须消失的机制第三终结符出栈时与当前 token 比较匹配失败立即抛出带位置的异常。3.3 冲突发生时怎么排查当PredictTable[非终结符][终结符]出现两个产生式时肉眼检查 First 集合往往最有效。一个常见场景是if_stmt - if ( expr ) stmt | if ( expr ) stmt else stmt这种悬挂 else 会让两个产生式的 First 集合完全相同LL(1) 无法处理。南航实验的通常解法是要求你修改文法引入matched_stmt和unmatched_stmt两个非终结符来区分这是龙书里的标准做法。另一种冲突来自 First/Follow 交叠常常出现在expr这类“左递归消除后带 ε”的非终结符上。排查方法是先单独打印每个非终结符的 First 和 Follow再手动查看是否存在某个终结符同时出现在First(α)和Follow(A)中。若出现说明原来的文法在消除左递归后产生了新的二义性需要重新检查产生式的左因子。许多同学在这里卡住其实是前面词法阶段把拆成了和导致语法阶段永远匹配不到完整的关系运算。4. 语义分析与中间代码生成把语法树变成三地址码4.1 符号表与分程序结构语法分析通过后接下来是语义分析和中间代码生成。南航实验对中间代码的要求一般是三地址码或四元式形式不做强制但要求能够在静态检查阶段报告变量未声明、类型不匹配、函数参数个数不对等错误。符号表这时候要能支撑作用域嵌套——最常见的设计是用“栈 哈希表”每进入一个新的块函数体、if 分支、while 体压入一层新的作用域声明变量时在栈顶作用域插入条目查找变量时从栈顶向下逐层查找找到即返回。如果实验要求支持函数符号表需要额外保存返回值类型和参数类型列表。反例是只用一个全局哈希表这会导致不同作用域的同名变量互相覆盖在后续函数实验里极难调试。常见的简单实现是 Python 里的list[dict]或者 C 里的std::vectorstd::unordered_mapstd::string, Symbol。4.2 语法制导翻译的基本写法中间代码生成通常和语法分析合并实现这样不用单独建 AST缺点是调试时很难看清结构。另一种做法是在语法分析时建一棵语法树再对树做一次翻译。推荐后者因为语义检查的很多边界情况需要回溯父节点上下文单独的树结构更方便。下面给出用表达式求值式翻译的伪代码骨架。# 假设 ast 是 dict例如 {type: binop, op: , left: ..., right: ...} temp_index 0 code [] def new_temp(): global temp_index t ft{temp_index} temp_index 1 return t def gen_expr(node): if node[type] num: t new_temp() code.append((t, :, node[value])) return t if node[type] id: return node[name] if node[type] binop: l gen_expr(node[left]) r gen_expr(node[right]) t new_temp() code.append((t, :, l, node[op], r)) return t这段代码的核心逻辑是把a b * c转换为类似t0 : b; t1 : c; t2 : t0 * t1; t3 : a t2的三地址码。gen_expr深度优先遍历树先为每个子表达式分配一个临时变量再把运算符和左右操作数写入一条四元式。t : l op r的四元式格式虽然简单但已经能覆盖赋值的右值表达式部分。4.3 四元式的输出与类型强制南航实验要求检查类型匹配最常见的是整型与浮点型的混合运算。这里有一个快速实现路径每个符号表条目里保存type字段gen_expr在生成binop之前先检查左右子树类型不一致时根据语言语义决定是报错还是自动插入类型转换四元式。比如int float通常先生成一条t : int_to_float(int_val)再生成加法。四元式输出建议直接打印成一行一条方便和课程给的答案对照。比如输出文件每行格式为op, arg1, arg2, result其中空白操作数用_表示。这里有一个严重但隐蔽的坑临时变量命名。如果每个子表达式都新分配临时变量生成代码会很长但正确如果试图复用临时变量必须考虑活跃区间。初版建议不优化直接用递增编号后面进阶再改成简单的栈式分配。5. 目标代码生成与运行栈式虚拟机的实现5.1 指令集设计中间代码生成之后南航实验很多版本要求“模拟执行”这段代码也就是不生成真正的 x86而是写一个自定义指令集的解释器。这是最容易被低估的一章——语法分析做得再漂亮解释器执行不了、指令语义和栈状态对不上分数同样垮掉。我一般建议采用栈式虚拟机原因是栈机与前后端解耦且调试时只需要关注操作数栈和指令指针两个状态。指令集可以设计为指令含义栈效果PUSH n将字面量 n 压栈栈顶增加 nLOAD name将局部变量 name 的值压栈栈顶增加该变量的值STORE name弹出栈顶值写入 name栈顶减少一个值ADD / SUB / MUL / DIV弹出两个操作数运算回推结果栈顶减少一个值JMP addr无条件跳转无JMPF addr弹出条件值为假则跳转栈顶减少一个值HALT结束执行无这里的关键设计决策是“把等号右边算完再整体赋值”STORE直接对栈顶变量作用与 x86 里的mov类似。若你的中间代码是三地址码而不是栈式字节码可以先写一个“三地址码到栈式指令”的翻译层或者干脆让解释器直接逐条模拟四元式。两种都能交差只不过栈式指令更容易拍出栈变化图方便验收时画图讲解。5.2 解释器的执行循环下面给出一个最小但完整的解释器核心循环指令集用上述表格。class VM: def __init__(self, instructions): self.code instructions self.stack [] self.vars {} self.ip 0 def run(self, max_steps10000): step 0 while self.ip len(self.code): step 1 if step max_steps: raise RuntimeError(step limit exceeded, possible infinite loop) op, arg self.code[self.ip] self.ip 1 if op PUSH: self.stack.append(arg) elif op LOAD: self.stack.append(self.vars[arg]) elif op STORE: self.vars[arg] self.stack.pop() elif op ADD: r self.stack.pop() l self.stack.pop() self.stack.append(l r) elif op SUB: r self.stack.pop() l self.stack.pop() self.stack.append(l - r) elif op MUL: r self.stack.pop() l self.stack.pop() self.stack.append(l * r) elif op DIV: r self.stack.pop() l self.stack.pop() if r 0: raise ZeroDivisionError(division by zero) self.stack.append(l / r) elif op JMP: self.ip arg elif op JMPF: v self.stack.pop() if not v: self.ip arg elif op HALT: return self.vars return self.vars执行循环里的每一条指令都只有一个明确的职责因此调试时只需要盯住两个东西self.stack的栈顶两元素和self.ip的位置。max_steps参数建议保留后面我会展开说它的救场价值。你可以把三地址码手工翻译成栈式指令让一段简单的a 2 3先跑起来再逐步扩展循环和条件分支。5.3 中间代码和栈帧如何对应函数调用是实验里最容易崩的部分。简单方案是给每个函数一个独立的vars字典调用时新建一个帧返回时把结果压回调用方的栈。由于课程实验一般不要求递归深度很大浮点参数等细节也可简化但需要处理参数传递的顺序——常见约定是“从右到左压栈”这样函数内部取第一个参数时栈顶刚好是它。如果你的实验要求支持数组和指针栈机的结构需要增加“地址”概念。这时推荐在四元式阶段就区分“变量的值”和“变量的地址”用LOADA/STOREA这样的复合指令来规避解释器内部的隐式唯一地址。这个区分看似多此一举但对后续扩展指针算术非常关键。6. 调试技巧给编译器加日志和防死循环护栏调试编译器最痛苦的是“不知道当前停在哪、下一步该做什么”。我个人的经验是在编码早期就加入两类护栏执行步数上限和分级日志开关。步数上限对语法分析器和栈式虚拟机都适用。语法分析器的死循环通常表现为“分析栈不空但输入不前进”原因多为 ε 产生式递归设置错误虚拟机的死循环则表现为 IP 在同一段指令上反复跳转。两者都可以靠一个计数器强行终止并打印当前栈深或栈顶快照。一个实用做法是维护一个debug布尔变量打开后在每个循环里打印当前输入 token、栈状态和分析动作关闭时则完全静默不影响验收时的标准输出。另一个值得投入的技巧是构造“最小回归用例集”。不要一上来就用老师给的大样例先准备 10 个以内的语句比如a 1;、a b c * 2;、if (a) { b 1; }、while (a 10) { a a 1; }。每个用例对应一条已知正确的中间代码输出改一次代码就全量跑一遍。这个做法能在几分钟内定位是词法层的错误还是语法层的错误因为你能直接看出第一个报错出现在哪条用例上。如果某个用例在语法分析栈里走到一半停住就在那个非终结符的入口打印 First 集合和当前符号通常很快就能找到是哪条产生式没有填进预测表。最后如果中间代码已经生成但执行结果不对一个高效的验证办法是在四元式输出里手动模拟一份“期望值”。例如把t2 : t0 * t1这行在注释里写出你手工计算的 t2 值然后运行解释器比对。这个方法朴素但比单步调试更快尤其是当错误出现在类型转换时——那里通常表现为结果溢出或变成很大的负数看一眼四元式是否插入转换指令就能定位。本文还有配套的精品资源点击获取