简介这份NUAA编译原理课设资料包以PL0教学语言为对象用Python实现了一个可运行的完整编译器适合计算机专业学生、编译原理初学者以及需要完成类似课程设计的开发者参考。压缩包共8个文件包含5个Python源码词法分析器、语法分析、语义分析及后端代码生成、1篇编译原理课设报告doc、1份README说明和1个article文本整体仅792KB目录结构清晰便于按模块查阅。源码覆盖了编译器的前端与后端完整流程详细实现了词法分析、语法分析、语义分析、中间代码生成及目标代码生成等环节并附有可运行的测试版本方便读者对照理解递归下降分析、抽象语法树、上下文无关文法等重点概念也能帮助处理标识符分类、嵌套结构解析和代码优化等实际问题。已有181人学习下载适合用来搭建自己的编译实践框架也可作为课程设计、实验报告和答辩准备的高质量参考资料。1. 把南航PL0课设换成Python重写是我做过最值的决定每个选编译原理课设的人都会遇到PL0这是教学编译器里最经典的“麻雀”。南航课设的要求通常是用某种语言实现一个PL0编译器输出的目标是P-code虚拟机指令。当年我用C写过一个版本函数指针、内存管理、指针悬挂把我折磨得够呛。后来组里换用Python版_Compile_Principle.zip的思路来重写整个实现周期缩短了将近一半。Python对栈式架构的表达天然友好符号表可以用字典写得非常直白递归下降语法分析也顺手。这篇笔记的目标很明确帮你在一个周内把课设从“跑不通”推到“有亮点”。新手可以按步骤把代码写出来熟手能直接看到架构取舍和边界坑。我们不讲官话只聊怎么把PL0在Python里落地。2. PL0语言与P-code先搞清楚你要实现的究竟是哪台机器2.1 PL0的语言规模一个能塞进几百行代码里的迷你语言PL0是Niklaus Wirth在《Algorithms Data Structures Programs》里设计的教学语言。它只有整数类型、常量定义、变量定义、过程定义可以嵌套以及五个基本语句赋值、调用、读、写、条件/循环控制。核心语法元素一只手数得过来语句begin ... end、if t then s、while t do s、call p、read(x)、write(x)、赋值x : exp表达式 - * /、括号、odd判断取模判断奇偶关系运算符、#不等于、、、、常量定义const a 5, b 10;变量定义var x, y, z;过程定义procedure p; ... ; call p;没有数组、没有字符串、没有浮点数、没有结构化类型。这个语言规模是刻意为之的——编译器里最复杂的部分藏在语义层面而不是语法层面比如嵌套过程的静态作用域、按值传递的参数栈帧、跳转地址的回填。Python版的优势在于你不需要为符号表单独设计一套哈希结构字典加列表就能模拟完整的嵌套作用域链。2.2 P-code指令集一个栈式虚拟机如何把程序跑起来P-code不是PL0目标机器唯一的选择但教学课设里最常见。它是一套栈式零地址指令运算从栈顶取操作数结果压回栈顶。核心指令集大概这些指令操作数语义lit整数常量把常量压栈opr运算编号在栈顶完成算术或关系运算lod层差、偏移按静态作用域取变量值压栈sto层差、偏移将栈顶值存入变量cal层差、入口地址过程调用建立新栈帧int栈帧大小调整栈指针预留局部变量空间jmp目标地址无条件跳转jpc目标地址条件跳转栈顶为假时跳red/wrt无读入/输出栈顶值sio无程序结束这里有个关键点层差level difference不是物理层数而是当前作用域与目标定义之间的嵌套深度差。解释器里维护一个display表每个下标对应一层活动的过程基址。lod 2, 3的含义是沿display链回溯2层取第3个槽位的值。Python里实现display表就是维护一个list当作栈帧底地址表非常顺。2.3 三步流水线词法、语法、代码生成如何衔接整个编译器的工作切分为三段这也是我在Python版里最坚定的架构选择第一段做词法扫描。输入是PL0源代码的字符串流输出是一串(类型, 值, 行号)元组。这步不需要引入第三方库手写一个状态机比正则更容易控制错误定位。第二段做语法分析。用递归下降法每个非终结符写一个函数函数之间通过调用关系表达文法。这段同时完成语义动作——查表、生成P-code、回填跳转地址。没有中间AST因为PL0足够小而简单边分析边生成指令完全可行。第三段做解释执行。读出生成的指令数组用一个模拟栈逐条执行。所有变量、活动记录、display链都在这个阶段显式管理这也是调试时最容易暴露思想不清晰的地方。3. 项目结构设计与Python实现的关键选型3.1 模块划分代码文件各管哪一段我建议用六个文件组织整个项目每个文件只有一个职责千万不要把几千行塞进main.py里文件职责token.py定义token类型枚举和token结构体命名元组lexer.py词法分析器从源码文件读到token流parser.py递归下降语法分析输出指令列表symbol.py符号表条目与符号表管理codegen.py指令类定义与跳转回填工具可与parser合并vm.pyP-code虚拟机加载指令并执行main.py命令行入口串起整个流水线所有文件之间是单向依赖main调用lexer和parserparser调用symbol和codegenvm只依赖codegen定义的指令数据结构。这么拆分的好处是你可以单独测试词法产出token流不用等语法分析写完虚拟机也可以单独喂一段手工构造的指令来验证栈帧逻辑。对于课设答辩老师问“你这块怎么测的”你直接说“单元测过lexer集成测过parser”说服力完全不一样。3.2 符号表设计字典套字典还是字典加属性对象PL0的符号表条目需要记录名字、种类常量/变量/过程、类型是否参数、值和偏移量。C语言课设里常用结构体数组在Python里最自然的做法是用dataclass定义一个Symbol类然后用字典做符号表。关键是作用域问题from dataclasses import dataclass from enum import Enum, auto class SymKind(Enum): CONSTANT auto() VARIABLE auto() PROCEDURE auto() dataclass class Symbol: name: str kind: SymKind level: int # 静态嵌套深度 offset: int # 在栈帧中的偏移量 value: int 0 # 常量值 / 过程入口地址这个Symbol对象是整个符号表的核心。它把名字、层级、偏移和值封装在一起比四个平行字典清晰得多。我用字典dict[str, Symbol]作为当前作用域的表用列表list[dict[str, Symbol]]作为作用域栈——每当进入一个过程体就压一个新的空字典退出时弹掉它。这样静态作用域天然成立查找变量时从栈顶往下逐层找自然只能看到外层定义。3.3 直接生成指令还是先建AST取舍的关键数据很多教学代码喜欢先建AST再遍历生成目标代码结构优雅但代码量大。Python版PL0我选择边分析边生成的原因有三个数字可以说明PL0文法一共只有十几个产生式指令类型不超过二十种一个正常课设程序生成的指令数量级在几百条。这个规模下AST带来的可读性收益远小于多写一倍的访问者代码成本。直接生成指令有一个已知的麻烦点是回填。if和while语句需要先把跳转指令的占位地址写为0等分析完分支体之后再回来修改。C语言里要维护一个待回填地址列表Python里直接维护一个list[int]生成指令时记住索引条件体分析完后再赋值代码非常直白。4. 把三段式编译流水线跑通核心代码剖析4.1 词法分析器从字符流到Token流的最小实现from token import Token, TokenType class Lexer: def __init__(self, source: str): self.src source self.pos 0 # 当前扫描位置 self.line 1 self.length len(source) def next_token(self): while self.pos self.length: ch self.src[self.pos] if ch \n: self.line 1 self.pos 1 elif ch.isspace(): self.pos 1 elif ch.isalpha(): return self._scan_ident() elif ch.isdigit(): return self._scan_number() else: return self._scan_symbol() return Token(TokenType.EOF, , self.line) def _scan_ident(self): start self.pos while self.pos self.length and self.src[self.pos].isalnum(): self.pos 1 word self.src[start:self.pos] # 保留字映射普通标识符 if word in (const, var, procedure, begin, end, if, then, while, do, call, read, write, odd): return Token(TokenType.KEYWORD, word, self.line) return Token(TokenType.IDENT, word, self.line)这段代码的逻辑说明next_token是词法分析器的主入口用while跳过空白和换行然后根据首字符分派到标识符扫描或数字扫描。_scan_ident用指针方式截取连续字母数字串再查保留字表把关键字和普通标识符区分开。参数上要注意pos和line是核心状态任何token扫描函数都只能向后移动pos不能回退这样才能保证线性扫描一遍源码。函数_scan_number同理但需要检查isdigit并返回TokenType.NUMBER。这里的坑是PL0的标识符长度约定Wirth原著里限制为10个字符以内课设一般不做限制但你排错时要知道有些同学写的变量名超长可能导致符号表输出对不齐。def _scan_symbol(self): ch self.src[self.pos] self.pos 1 two ch (self.src[self.pos] if self.pos self.length else ) if two in (:, , ): self.pos 1 return Token(TokenType.OPERATOR, two, self.line) if ch : return Token(TokenType.EQ, ch, self.line) if ch #: return Token(TokenType.OPERATOR, ch, self.line) if ch in -*/(),;.:: return Token(TokenType.SYMBOL, ch, self.line) raise SyntaxError(f第{self.line}行出现非法字符: {ch})双字符操作符是词法层面最常见的坑。:不能拆成冒号和等号不能拆成小于号和等号。实现时先检查一个字符能不能和后面一个组成双字符操作符如果能就一次性吃掉两个否则退回单字符。检查顺序必须是:、、这三个先判避免把单独匹配掉。4.2 递归下降语法分析每个文法规则就是一个同名函数class Parser: def __init__(self, tokens, symbol_table): self.tokens tokens self.pos 0 self.current tokens[0] self.symbols symbol_table def advance(self): self.pos 1 if self.pos len(self.tokens): self.current self.tokens[self.pos] def check_type(self, ttype): return self.current.type is ttype def match(self, value): if self.current.value value: self.advance() else: raise SyntaxError( f第{self.current.line}行: 期望 {value}, f但读到 {self.current.value})Parser是递归下降法的核心框架。advance每调用一次就把token游标后移一位match负责消费期望的具体字符并把位置推进。这套模式写起来四行一个函数但要严格遵守“每个非终结符函数只处理自己首字符能决定的产生式”原则。比如factor函数要先判断是数字、标识符还是左括号term先判断是否是乘除号expression先判断加减号。一旦首字符分派混乱递归下降就会产生歧义。重中之重的语句分析函数长这样def parse_statement(self): if self.check_type(TokenType.KEYWORD): kw self.current.value if kw begin: self.advance() self.parse_statement() while self.current.value ;: self.advance() self.parse_statement() self.match(end) elif kw if: self.advance() self.parse_expression() self.gen_if_jump() # 生成条件跳转暂填地址 self.match(then) self.parse_statement() self.backpatch_if_jump() # 回填 elif kw while: self.advance() cond_start self.code_index() self.parse_expression() self.gen_while_jump() self.match(do) self.parse_statement() self.backpatch_while_jump(cond_start) elif kw call: self.advance() name self.current.value proc self.symbols.lookup(name) if not proc: raise NameError(f第{self.current.line}行: 过程 {name} 未定义) self.emit(cal, proc.level, proc.address) self.advance()这段代码是递归下降法里最有教学价值的部分之一。begin...end块用循环吃分号天然支持空语句if的处理分成两步先解析条件表达式生成一段求值指令此时栈顶留下条件真假值然后生成jpc 0作为占位解析完then语句后再把实际跳转目标回填。while必须记录条件开始地址以便回跳。call需要查符号表拿到被调过程的层差和入口地址。4.3 代码生成与P-code虚拟机的最终执行dataclass class Instruction: opcode: str arg1: int 0 arg2: int 0指令类用dataclass是能让后续代码最短的选择。每个字段的语义由操作码决定lit只填arg1作为常量值lod的arg1是层差、arg2是槽位偏移jmp和jpc只填arg1作为目标地址。其余操作码的两个参数默认置0保证构建指令时不需要考虑多余参数。虚拟机执行部分是这个项目的收尾环节class VM: def __init__(self, code: list[Instruction], debugFalse): self.code code self.pc 0 # 程序计数器 self.stack [0] * 2000 # 数据栈 self.sp 0 # 栈顶指针 self.bp 0 # 当前帧基址 self.display [0] * 20 # 嵌套深度索引 self.debug debug def run(self): while self.pc len(self.code): ins self.code[self.pc] if self.debug: print(fpc{self.pc:4d} {ins.opcode} {ins.arg1} {ins.arg2}) if ins.opcode lit: self.sp 1 self.stack[self.sp] ins.arg1 elif ins.opcode lod: base self.display[ins.arg1] self.sp 1 self.stack[self.sp] self.stack[base ins.arg2] elif ins.opcode sto: base self.display[ins.arg1] self.stack[base ins.arg2] self.stack[self.sp] self.sp - 1 elif ins.opcode int: self.sp ins.arg1 elif ins.opcode cal: self.stack[self.sp 1] self.bp self.stack[self.sp 2] self.pc 1 self.stack[self.sp 3] self.display[ins.arg1] self.display[ins.arg1] self.sp 1 self.bp self.sp 1 self.pc ins.arg2cal的执行是栈式虚拟机里最容易写错的一行代码它要连续压入三个现场值调用者基址、返回地址、调用者的display槽位然后更新当前层的display槽为新帧基址最后跳转。注意顺序不能乱压入现场值和更新display是两件事必须严格分开。对应的opr 0返回指令要反向恢复这三个值恢复的顺序不能反否则回到调用者时栈顶全部错乱。5. 课设避坑指南这些坑我踩过你也躲不过5.1 现象嵌套过程的call进入死循环原因过程调用时cal里的层差算错了。很多同学只看当前过程名出现的物理位置忘了层差是“当前词法级与目标过程定义级之间的距离”而不是过程在源码里的先后顺序。Python版虽然不用手动管理指针但display表的更新逻辑如果只做了一半内部过程调用外部过程时取错基址拿到的变量值完全错位甚至sp会倒退回爆栈。解决在VM里加上栈深度上限检查当sp超过len(self.stack) - 10时打印当前pc和最近10条指令立刻就能定位是哪个cal导致失控。另外写一个测试程序专门三层嵌套过程互相调用并读取外层全局变量。5.2 现象if条件永远走then分支原因jpc的回填地址忘了算偏移量。if语句生成跳转指令时jpc占位在第k条指令then语句从第k1条开始真正的回填值应该是当前指令计数而不是k1或k2。这个问题在我经手的Python版里发生过三次全是因为生成条件表达式后多插了一条调试指令导致计数偏移。解决所有回填不要用绝对数字硬编码封装一个emit_jump_placeholder()得到地址再封装backpatch(index, target)负责改值。5.3 现象while循环只执行一次原因循环结束后的回跳地址取错了。while在生成条件表达式之前要记录当前位置这是循环体的回跳目标循环体结束处要生成jmp 起始位置而不是回跳到条件表达式生成后的位置。如果顺序弄反循环体执行一次后就跳到条件表达式之后看起来就像“只循环一次”。解决在parser里用一个栈保存循环起点嵌套while也互不干扰。5.4 现象Python虚拟机的递归注释错误地把参数显示成局部变量原因int指令分配的栈帧空间覆盖了传入参数区。PL0过程调用时实参压栈发生在cal之前int指令调整sp时应该跳过参数区。很多人在虚拟机里把int的实现简单写成sp arg这会覆盖已压栈的调用参数。解决严格按照课程约定实参在调用者栈帧里压好被调过程的int只扩展局部变量区参数访问用lod 0, -参数序号的偏移方式负偏移指向调用者栈帧尾部的参数区。5.5 现象版本差异导致浮点除法结果不对原因PL0要求整数除法但有的同学在Python 3里直接用/得到浮点结果后传给后续整数运算。Python 2时代/是整数除法Python 3改为真实除法这导致迁移到Python 3环境的代码在7 / 2时输出3.5而不是3。编译原理课设里绝大多数运算都该用//。解决在opr运算分支里对除法统一使用//并取整同时打印警告防止学生把浮点值写进变量表。5.6 现象语法分析器对错误输入的报错信息完全没用原因match函数只报“期望X但读到Y”没给出行号和已读进buffer的上下文。课设验收时老师会故意输入错误程序如果你报错行号错位或直接崩溃会被认为“没有错误恢复能力”。解决在advance()中保存前一个token的类型和值SyntaxError里打印前三个token的定位链让用户一眼看出问题在哪一行哪个token附近。6. 从及格冲到优秀测试策略与三个值得投入的扩展方向先聊测试策略。别只拿“hello world”的PL0程序验证。我习惯每实现一个功能模块就建一个对应样例test_const.pl0、test_nested_proc.pl0、test_while.pl0、test_recursive.pl0。递归求阶乘是最高性价比的测试——它能同时检验参数传递、栈帧恢复、层差寻址和值传递四条链路样例如下var n, f, r; procedure fact; var p; begin if n 0 then begin p : n; n : n - 1; call fact; r : r * p end else r : 1 end; begin n : 5; call fact; write(r) end.这段程序能跑通且输出120你的栈帧管理基本就稳了。在此基础上做opr指令跟踪打印比对每一步栈顶变化是否符合预期是查错最实的验证方式。扩展方向上最推荐的是把P-code翻译成MIPS汇编或LLVM IR。这时你已经在做“编译器后端”了课设深度直接从“解释器”跳到“真实编译器”。第二个方向是给PL0加布尔表达式短路求值在opr的运算子集里新增and、or指令同时实现对和||的语义配布。第三个方向是做静态类型推断虽然PL0只有整型但可以仿照真实编译器的类型检查框架给符号表增加类型字段并做表达式类型传播。如果这三条都做完了再往符号表里加行号作用域缓存让变量查找复杂度从O(嵌套深度)降到O(1)这就是可以写进答辩PPT的工程优化。我每次带总组都会强调别躺在“能跑”上拿一个样例程序跑通后立刻做异常输入测试拿三个内部样例做回归再写一个对比报告。做完这套流程课设的上限就取决于你愿不愿意多花一个晚上把测试语料补齐。每次写PL0的Python版我都会换一种方式组织符号表或栈帧这次的教训是display表更新一定不能放在分支里做统一在每个cal执行前固定三步压栈。你写的时候照着这段代码推一遍递归过程的栈帧布局心里有底就不会翻车。希望帮到你。本文还有配套的精品资源点击获取