编译原理课程设计实战：从词法分析到解释执行的完整构建

简介面向计算机专业学生的编译原理课程设计完整方案源自南京航空航天大学课程要求聚焦词法分析、语法分析、符号表管理等核心环节适合正在准备编译原理大作业或需要完整参考实现的学生。压缩包共32个文件包含C/C源代码、头文件、可执行程序、课程设计报告Word文档、答辩PPT、测试文本等多种类型既可直接运行验证程序正确性也可对照源码理解编译前端实现细节。资源整体约961KB文件组织按词法部分、语法部分、文档报告分块存放结构清晰便于按需取用。已有749人学习下载经历过同类课程检验。整套设计经检验无BUG程序可独立运行实验报告和答辩材料齐全可作为不同版本课程设计的比照模板对快速搭建编译原理实验框架、梳理词法与语法分析流程有明显帮助。1. 编译原理课程设计到底在交什么先做一台能读源码的小机器大多数拿到编译原理课程设计题目的同学第一反应都是先去找现成源码改一改。可真正到了验收翻车的往往不是“理论看不懂”而是自己改出来的程序只能跑通自己编的那三条用例老师一换输入就崩。这门课设的实质是把词法分析、语法分析、语义分析这几段从纸面概念搬进一个命令行程序里喂给它一个文本文件它要么输出正确结果要么在准确的行列位置报错。以南京航空航天大学的编译原理课程设计为背景再加上所有学校同类课设的通用要求你要交的东西通常不是“能运行的编译器”而是一个你能讲清楚每一步为什么这么做的源码前端。它适合两种人正在为选课题和验收发愁的学生以及工作后想补一遍编译前端完整链路的人。难点不在算法多深而在你怎么把正则文法、FIRST/FOLLOW、符号表这些零散知识点串成一条能跑的流水线。这篇文章就按我实际做这类课设的拆法来讲从定语言范围到验收前对拍每一步都给出能直接抄走的东西。2. 定好语言与目录再动手先把自己的源语言缩到能掌控的规模2.1 源语言范围怎么定从教材的 Tiny 子集往回收窄课程设计最怕的事情是自己发明一门语言。语法规则越多词法、语法、语义三段的实现量就随之翻倍最后根本做不完。常见的做法是按照清华大学出版社第三版编译原理教材里的 Tiny 语言或类似微语言裁剪出一个只包含必要特征的子集作为课程设计的目标语言。我一般会把目标语言的范围收敛到这张表里类别允许出现的元素类型int、bool变量声明var x, y: int; 支持逗号分隔多变量语句赋值、if-else、while、print、begin/end 块算术表达式、-、*、/、括号、整数字面量比较表达式、、、、、!结果为 bool布尔字面量true、false注释// 行注释为什么保留这些而不是加入数组、函数调用和 for 循环因为课程设计的检查点通常落在词法正确性、语法树结构、符号表作用域、类型检查这四件事上。if 和 while 足够覆盖控制流print 足够验证运行结果数组和函数会让符号表从“一张表”变成“作用域栈加参数栈”复杂度直接翻倍但对得分点的贡献不大。下面是一份符合上述范围的测试程序后续所有模块都以它为验收基准// test1.tny var x, y: int; begin x : 10; y : 0; while x 0 do y : y x; x : x - 1 end; print y end注意这里的语法设计刻意偏向 LL(1)赋值号用:比较用语句以分号结束。这样设计不是为了好看而是为了让递归下降解析器不需要回溯每个非终结符看到当前 Token 就能决定走哪条分支。这一点会直接决定第三章的解析代码好不好写。2.2 架构拆成四个文件别一锅炖很多课程设计翻车不是算法问题而是把所有逻辑塞进一个几千行的 main 文件改一个地方崩三处。我的拆法是把程序按编译前端的天然阶段分成四个模块文件职责关键接口main.py读文件、调用各阶段、打印错误命令行入口lexer.py把源文件切分成 Token 流next_token(src, pos)parser.py把 Token 流解析成 ASTparse_program()interp.py符号表、类型检查、解释执行run(ast)调用链是固定的main 读文件lexer 出 Tokenparser 出语法树interp 一边做语义检查一边解释执行。错误在每个阶段就地抛出由 main 统一捕获并打印“第几行第几列”的信息。命令行入口我一般做成这样python mini.py test1.tny运行后要么打印55test1.tny 中 1 加到 10 的结果要么在出错时输出Error at line 3, column 5: unknown identifier zmain 里的调用逻辑非常直接不需要花哨的命令行参数库一个sys.argv[1]就够了。如果课程设计要求用 C 或 Java 提交把四个文件的边界原样迁移过去每个文件对应一个 C 源文件或 Java 类主流程完全不变。2.3 先用 Python 做行为模型再迁到 C为什么值得多花两小时如果你的提交语言被限定为 C/C我建议的做法是先用 Python 把整个流程跑通再花半天迁移到 C。这不是绕路而是给后面的调试留后悔药。Python 里调试递归下降解析器能直接打印数据结构、快速验证文法设计是否正确迁到 C 之后主要时间会花在内存管理和字符串处理上如果一边设计文法一边写 C你会同时面对文法错误和指针错误根本分不清是哪里出了问题。Python 原型的角色是“行为模型”它帮你确认文法没有歧义、符号表逻辑正确。迁移到 C 时映射关系是一一对应的。比如 Python 里的 Token 元组(ID, x)在 C 里就是typedef struct Token { int type; // TOKEN_ID / TOKEN_NUM / TOKEN_KW... char *text; // 词素文本 int line, col; // 行列号用于报错 struct Token *next; } Token;协同方式是Python 版保留为测试基准C 版每跑通一个阶段就和 Python 版结果对拍。这样你始终有一个“正确答案”可以参考不会出现改了 C 代码后连错误是预期还是非预期都分不清的局面。3. 词法与语法分析递归下降把 Token 流变成一棵可检查的树3.1 词法分析最小 Token 表和最长匹配的落点词法分析器的任务是把纯文本拆成有类型的 Token。对于上面的迷你语言Token 类型只需要这些Token 类型匹配内容ID标识符如 x、yNUM整数字面量KW关键字var begin end if then else while do print int bool true falseOP运算符: ! - * / ( ) ; , :ERR无法识别的字符EOF文件结束最小实现不需要状态机工具手写一个带双指针和跳空白逻辑的函数就够了。关键在于“最长匹配”遇到时必须继续看下一个字符是不是如果是整体切成否则单独切。这个坑在第五章还会细说。# lexer.py KEYWORDS {var, begin, end, if, then, else, while, do, print, int, bool, true, false} def next_token(src: str, pos: int): 从 pos 开始切一个 Token返回 (type, text, newpos) n len(src) while pos n and src[pos].isspace(): pos 1 if pos n: return (EOF, , pos) ch src[pos] # 标识符或关键字字母开头后续字母数字下划线 if ch.isalpha() or ch _: start pos while pos n and (src[pos].isalnum() or src[pos] _): pos 1 word src[start:pos] return (KW if word in KEYWORDS else ID, word, pos) # 整数 if ch.isdigit(): start pos while pos n and src[pos].isdigit(): pos 1 return (NUM, src[start:pos], pos) # 两字符运算符要优先于单字符判断 two src[pos:pos2] if two in (:, , !, , ): return (OP, two, pos 2) # 单字符运算符 if ch in -*/(),;:: return (OP, ch, pos 1) return (ERR, ch, pos 1)这段代码有几个参数值得注意。KEYWORDS集合决定了“var”这类单词切出来是关键字还是普通变量名顺序是先切出完整单词再查集合不能一边读一边判断。pos是双指针里的读指针每调一次 next_token 就前移若干字符外层用一个循环反复调用直到 EOF。两字符运算符的判断放在单字符之前这样才能保证:后面跟时切成一个:而不是两个 Token。词法层级的报错只需要做一件事遇到 ERR 时带上行列号。行号可以在外层扫描时同步维护每次读到\n就让 line 加 1col 归零。词法层不要尝试“猜”用户想写什么直接报错返回即可否则会把错误掩盖到语法层报错信息更难读。3.2 语法分析递归下降与左递归的处理词法分析完成后parser 拿到的是一个 Token 列表。递归下降的核心思想是为每个语法成分写一个解析函数函数之间互相调用调用关系就是文法本身。表达式解析是整棵语法树里最容易写错的部分。下面这段代码处理加减法# parser.py def parse_expr(tokens, pos): expr : term (( | -) term)* left, pos parse_term(tokens, pos) while pos len(tokens) and tokens[pos][1] in (, -): op tokens[pos][1] pos 1 right, pos parse_term(tokens, pos) left (bin, op, left, right) return left, pos关键在这里文法里expr - expr term是左递归递归下降函数如果直接按这个文法写会无限调用自己直到栈溢出。处理方法是把左递归改写成迭代循环先解析一个 term然后只要看到或-就继续解析下一个 term并把结果向左结合。这样表达式的结合性和优先级都由代码结构保证乘除在 parse_term 层加减在 parse_expr 层括号在 parse_factor 层。完整的配套函数至少还需要 parse_term、parse_factor 和 parse_stmt。其中 parse_stmt 需要处理赋值、if、while、print、begin/end 块五种情况判断依据就是当前 Token 的值def parse_stmt(tokens, pos): tok_type, tok_text tokens[pos] if tok_type ID: # 必须是赋值语句ID : expr ; ... elif tok_text if: # if cond then stmt else stmt ... elif tok_text while: # while cond do stmt ... elif tok_text print: # print expr ; ... elif tok_text begin: # begin stmt_list end ...这里 is 的一个实用参数tok_text已经由词法层分好了类关键字和运算符都能直接用文本匹配不需要再判断 Token 子类型。每个解析函数返回的是(ast_node, new_pos)new_pos 是消费完当前语法成分后 Token 流的位置。一旦某个分支发现Token对不上直接抛异常由上层统一处理。3.3 报错与错误恢复至少要能指出“第几行”语法分析阶段的常见处理是遇到第一个错误就崩还是尝试恢复继续找后面的错误课程设计里后者更占便宜因为一次运行能报出多条错误看起来更像一个“完整的编译器”。但错误恢复如果做得太激进会报出一堆假错误反而扣分。我用的策略是同步 Token 集合加异常捕获。在 parse_stmt 的入口处检查当前 Token 是否为语句起始符ID、if、while、print、begin如果不是就抛 ParseError外层捕获后跳过所有 Token 直到遇到分号、end 或 EOF 再继续解析。分号和 end 属于“语句边界”跳到这里意味着上一个语句已经结束可以安全恢复。class ParseError(Exception): def __init__(self, msg, line, col): super().__init__(msg) self.line line self.col col def sync_to_stmt_boundary(tokens, pos): 跳过错误 Token直到分号、end 或 EOF while pos len(tokens): t tokens[pos][1] if t ; or t end: return pos 1 if t ; else pos pos 1 return pos错误恢复的参数不能拍脑袋定sync_to_stmt_boundary里的停止集合是关键只设两个停止符不要加then、do这些词否则会停在语句中间导致后续解析错位。实际调试时如果发现一条错误之后连报五条优先怀疑停止集合太宽或太窄而不是解析逻辑本身。4. 语义分析与解释执行符号表、类型检查和一条龙验证4.1 作用域与符号表嵌套块怎么不悬空语法树建好之后下一步是语义分析。首先要解决的是符号表。对于只有全局变量和 begin/end 块的迷你语言作用域至少有两层全局作用域和每个 begin/end 块的作用域。嵌套块内部声明的变量在块结束后必须不可见否则后面的语句会把块内变量当成全局变量这是典型的“悬挂符号”。符号表我习惯用类加父指针实现# interp.py class Scope: def __init__(self, parentNone): self.vars {} self.parent parent def declare(self, name, typ, line): if name in self.vars: raise SemanticError(fline {line}: duplicate variable {name}) self.vars[name] typ def lookup(self, name, line): s self while s is not None: if name in s.vars: return s.vars[name] s s.parent raise SemanticError(fline {line}: unknown identifier {name})这段代码的核心参数是parent指针。lookup 从当前作用域往上回溯找到即返回declare 只在当前层操作不干扰上层同名变量。解释器每进入一个 begin/end 块就新建一个 Scope并把它的 parent 指向上一个 Scope块结束后丢弃当前 Scope回到父作用域。这样块内变量自动失效不需要手动清理。迁到 C 时这个结构可以换成链表typedef struct Sym { char *name; int type; // 0: int, 1: bool struct Sym *next; // 同层符号链表 } Sym; typedef struct Scope { Sym *head; // 当前层符号表 struct Scope *parent; } Scope;实现细节有差别但逻辑完全一致查找从当前 Scope 的链表遍历找不到就去 parent 继续找。用 Python 原型把行为验证好C 版只是把 dict 换成链表遍历而已。4.2 类型检查放在解释期还是语法期避开“边解析边检查”的诱惑很多课程设计为了省事在语法分析的同时顺手做类型检查遇到类型不匹配直接抛错。这个做法看起来高效但有一个隐蔽问题语法分析的目标是构建 AST混入类型检查后语法函数里到处都是语义逻辑一旦类型规则要调整整个 parser 都要动。而且语法错误和语义错误混在一起报调试体验很差。我把类型检查做成独立的遍历 pass先完整跑完语法分析得到 AST再对 AST 做一次类型检查最后才进入解释执行。类型检查的函数按 AST 节点类型分派def type_check(node): 返回节点类型 int 或 bool不匹配抛 SemanticError kind node[0] if kind num: return int if kind bool: return bool if kind id: return scope.lookup(node[1], node[2]) # (name, line) if kind bin: _, op, left, right node lt type_check(left) rt type_check(right) if op in (, -, *, /): if lt ! int or rt ! int: raise SemanticError(arithmetic on non-int) return int if op in (, !, , , , ): if lt ! rt: raise SemanticError(compare different types) return bool这样做的好处是AST 树上一旦出现矛盾报错位置精确到语法树节点关联的行号而不是 Token 流里某个模糊的位置。类型检查只回答“这棵子树是什么类型”不关心值是什么也不修改符号表所以它是一个纯函数式遍历写起来非常干净。4.3 用解释器跑通而不是先写代码生成少走一半弯路课程设计的验收标准通常只要求“运行结果正确”很少要求生成真实的汇编代码。如果不强制要求中间代码我建议直接写一个树遍历解释器拿到类型检查通过的 AST递归执行每个节点。这是整条流水线里代码量最少、也最容易验证的部分。# interp.py def exec_stmt(self, node): kind node[0] if kind assign: _, name, expr node val self.eval_expr(expr) self.scope.assign(name, val) # 运行时再查一次符号表 elif kind if: _, cond, then_stmt, else_stmt node if self.eval_expr(cond)[1]: self.exec_stmt(then_stmt) elif else_stmt is not None: self.exec_stmt(else_stmt) elif kind while: _, cond, body node while self.eval_expr(cond)[1]: self.exec_stmt(body) elif kind print: _, expr node val self.eval_expr(expr) print(val[1])解释器里的值我统一用二元组表示形如(int, 55)或(bool, True)。之所以要在运行时再查一次符号表是因为赋值语句需要写回变量的当前值而类型检查阶段已经保证变量存在、类型匹配运行时不需要再重复检查类型。这个分工是语义分析和解释执行的边界类型检查负责“合法吗”解释器只负责“算出什么”。如果课程设计明确要求三地址码或中间代码可以把最后这段换成“生成三元组”但整个前端的实现顺序不要变词法、语法、符号表、类型检查最后才是中间代码。先让程序完整跑通再考虑输出什么格式的中间文件否则你会在调试解释器的同时还要调试汇编生成两件事叠在一起非常难收场。5. 课程设计避坑最长匹配、左递归与报错恢复的 5 个现场5.1 把切成了两个词法没做最长匹配现象测试程序里写if x 1 then词法分析输出的 Token 序列是ID x、OP 、OP 、NUM 1。语法分析在if的条件部分期望一个比较运算符却连续看到两个等号直接报语法错误。原因词法分析器在处理单字符时直接返回没有继续向前看一个字符。这就是“最长匹配”原则没有落实匹配到后应该再尝试把、!、、整体切出来。解决在词法函数里凡遇到可能组成两字符运算符的单字符都先取src[pos:pos2]查表。查不到再退回到单字符。这个检查顺序不能反过来否则:会被切成:和。5.2 递归下降直接套左递归文法一跑就 RecursionError现象文法写成expr : expr term解析函数也照着写先调 parse_expr 再读。结果程序一运行栈溢出Python 报 RecursionErrorC 版直接段错误。原因递归下降要求每个非终结符的开头都是可预测的不能一上来就递归调用自己。左递归文法对应的递归下降函数会无限自调用永远读不到 Token。解决把左递归改写为循环也就是第三章里 parse_expr 的写法先解析一个 term然后while看到或-就继续解析下一个 term。这是递归下降里最标准的左递归消除手法不只是规避报错也是表达式结合性的正确实现方式。5.3 符号表用全局 dict块作用域结束后变量还“活着”现象begin var x: int; ... end块结束后后面的语句引用x竟然不报“未知变量”而是读到了块内残留的值。原因符号表实现成了全局唯一字典declare 和 lookup 都操作同一个 dict。块结束时没有删除块内变量或者删了但没做对按名字删除会把外层同名变量也删掉。解决符号表必须分层。进入块时压入新层出块时弹出该层。查名字时从当前层向上逐层找同层重复声明直接报错不同层同名变量互不干扰。这正是第四章 Scope 类的设计动机。5.4 错误恢复后 Token 错位一条错后面连报十条现象源文件第三行有一个语法错误程序却从第三行一路报到第十行每一行都说“解析失败”。实际上只有第一个错误是真的。原因错误恢复策略太激进。我的sync_to_stmt_boundary里停止集合除了分号和 end还加了 then、do结果恢复过程停在了一个语句中间后续解析完全不匹配语法规则制造了一连串虚假错误。解决恢复时只信任语句边界。分号和 end 是安全的停止点这样可以保证恢复后一定位于下一个语句的开头。如果恢复后仍然报错再检查是不是恢复后跳过了 end 导致块结构错乱。5.5 只测自己写的正常用例一验收就翻车现象自己测试永远是while循环正确计算、if正确分支到了验收老师输入一个不合法程序程序直接崩溃没有输出任何报错信息。原因测试集里没有负向用例。课程设计评分通常包含“错误程序能否正确报错”这一项只测合法程序等于完全没测错误路径。而且崩溃往往发生在解释器尝试访问一个不存在的变量或者 None 节点时。解决准备三份测试用例集合法程序、非法语法程序、非法类型程序。合法程序验证功能后两份验证报错的准确性和程序稳定性。每次改代码后三份用例全套跑一遍确保没有新的崩溃。6. 验收前最后两小时用例设计、AST 对拍与后悔药6.1 先把“三条正常、三条错误”的用例表填了临时想测试用例是最容易漏项的。我习惯在工程目录下建一个 tests 文件夹每个用例一个.tny文件用例表直接写在注释里形成一个能反复执行的回归集文件名输入要点期望结果test1.tny1 到 10 累加并 print输出 55test2.tnyif 的 else 分支取反输出 falsetest3.tny嵌套 begin/end 作用域隔离输出 3error1.tnyx : ;缺少表达式报语法错误不崩溃error2.tnyprint z;未声明变量报未知标识符不崩溃error3.tnyx : true;类型不匹配报类型错误不崩溃测试文件要覆盖三件事正常路径、错误路径、边界路径。边界路径至少包含空文件、只有注释的文件、单个var声明没有语句的文件。这些用例跑通验收时被临时输入打穿的概率会小很多。6.2 AST 对拍把树打出来再讲道理如果解析结果和预期不一致最有效的调试方式不是盯代码而是把 AST 打印出来看结构。我习惯给 parser 加一个 dump_ast 函数只用来调试不进最终交付代码def dump_ast(node, indent0): 按缩进打印 AST 结构tuple 和 list 都能处理 if isinstance(node, tuple): kind node[0] if kind in (num, id): print( * indent f{kind}: {node[1]}) else: print( * indent kind) for child in node[1:]: if isinstance(child, (tuple, list)): dump_ast(child, indent 1) elif isinstance(node, list): for item in node: dump_ast(item, indent)把while x 0 do解析后的树打印出来你会看到while节点下挂着一个cmp节点里面是和两个操作数。如果cmp变成了bin说明条件表达式和算术表达式共用了同一个解析函数优先级串了。这种结构性问题靠肉眼看代码很难发现但 AST 对拍一眼就能看出来。6.3 最后一个习惯所有用例必须在一个命令内跑完不要每次手动敲命令也不要只测最近新增的用例。在项目根目录放一个测试脚本每次改动后执行一次#!/bin/bash # run_tests.sh for f in tests/*.tny; do echo $f python mini.py $f || echo failed done跑完看输出凡是出现failed的用例就是刚才改动破坏的路径。这个习惯帮我避免了无数次“改好 A 却弄坏 B”的尴尬。我个人的最后一步永远是先把错误用例的期望输出写出来再动代码改完对照确认通过后再看正常用例有没有被影响。希望这个流程对你准备编译原理课程设计也有帮助动手前先把验收尺度定清楚后面每一步都是在给最终交付减风险。本文还有配套的精品资源点击获取