用Python重写PL0编译器：从词法分析到运行时栈的课设详解

简介：这份资源是南京航空航天大学编译原理课程设计的PL0编译器Python实现，主要面向正在完成编译原理课设的计算机专业学生，也适合希望通过完整项目理解编译器构建流程的自学者。资源包共8个文件，包含5个Python源文件、1个TXT文本、1个Markdown说明和1份课设报告，压缩包仅792KB。Python源码按编译流程分为词法分析器、语法分析、语义分析、语义分析测试版和后端等模块，分别对应编译器前端与后端的关键环节；TXT文件为配套测试数据，Markdown提供运行说明，课设报告则完整记录了设计思路、实现细节与测试结论。目前已有181人学习下载。通过这份资源，读者可以对照代码与报告，理解词法分析、递归下降语法分析、语义分析、中间代码生成等核心概念，并借助模块化结构快速定位问题，为完成自己的课设或扩展编译器功能提供直接参考。

1. 用 Python 重写 PL0 课设，为什么比你想的更有性价比

NUAA 编译原理课设里的 PL0，把 Pascal 教学语言压缩到只剩赋值、判断、循环和过程调用，用 Python 重写一遍，不是偷懒，而是把黑匣子打开的最佳方式。实际做完你会发现，C 版纠结的是指针和内存布局，Python 版纠结的是符号表的作用域和运行时栈的层次，而这些才是编译原理真正要考的东西。这篇笔记按一个能直接交差的路径写：先拆词法、语法、运行时三块，再给最小可跑通的代码结构和运行命令，然后把递归调用、参数传递这几个高频翻车点展开，最后用一个栈打印技巧收尾。适合正在做这个课设，或者想补一补“编译原理到底怎么落地”的同学。

2. 把 PL0 编译器拆成三块再动手：词法、语法与运行时栈

PL0 的规模决定了它不需要像真实编译器那样分十几趟扫描。词法分析、语法分析、解释执行三个模块就已经把编译原理的主干全部覆盖了，剩下的符号表和运行时栈是横跨后两个模块的公共基础设施。先把这个结构在脑子里立住，后面写代码才不会东一榔头西一棒槌。

2.1 词法分析：保留字、标识符、数字与 := 双字符符号

PL0 的保留字一共十一个：begin、end、if、then、while、do、call、const、var、procedure、odd。运算符和分隔符也就是+ - * / = # < > ( ) , ; . :=这一组。词法分析器最需要小心的不是数量，而是:=这种双字符符号，以及保留字和标识符共享同一套字符规则带来的优先级问题。

# lexer.py —— PL0 词法分析器核心 class Token: def __init__(self, type_, value, line): self.type = type_ self.value = value self.line = line class Lexer: def __init__(self, text): self.text = text self.pos = 0 self.line = 1 self.reserved = { 'begin': 'BEGIN', 'end': 'END', 'if': 'IF', 'then': 'THEN', 'while': 'WHILE', 'do': 'DO', 'call': 'CALL', 'const': 'CONST', 'var': 'VAR', 'procedure': 'PROCEDURE', 'odd': 'ODD' } self.single = { '+': 'PLUS', '-': 'MINUS', '*': 'TIMES', '/': 'SLASH', '=': 'EQUAL', '#': 'NEQ', '<': 'LESS', '>': 'GREATER', '(': 'LPAREN', ')': 'RPAREN', ',': 'COMMA', ';': 'SEMICOLON', '.': 'PERIOD' } def next_token(self): while self.pos < len(self.text) and self.text[self.pos].isspace(): if self.text[self.pos] == '\n': self.line += 1 self.pos += 1 if self.pos >= len(self.text): return Token('EOF', None, self.line) ch = self.text[self.pos] if ch.isalpha(): start = self.pos while self.pos < len(self.text) and self.text[self.pos].isalnum(): self.pos += 1 word = self.text[start:self.pos] return Token(self.reserved.get(word.lower(), 'IDENT'), word, self.line) if ch.isdigit(): start = self.pos while self.pos < len(self.text) and self.text[self.pos].isdigit(): self.pos += 1 return Token('NUMBER', int(self.text[start:self.pos]), self.line) if ch == ':': if self.pos + 1 < len(self.text) and self.text[self.pos + 1] == '=': self.pos += 2 return Token('ASSIGN', ':=', self.line) raise SyntaxError(f"line {self.line}: 孤立冒号，:= 写错了吗") if ch in self.single: self.pos += 1 return Token(self.single[ch], ch, self.line) raise SyntaxError(f"line {self.line}: 非法字符 {ch!r}")

这段代码有四个点值得说明。第一，Token 里带 line 字段，这是排错的基础，没有行号的词法错误在课设答辩时基本没法解释。第二，保留字判断用的是word.lower()，这样BEGIN和begin都会被识别成 BEGIN，兼容大小写混写，也避免了下文语法分析器被迫区分大小写。第三，数字直接int()转换，没做溢出检查，PL0 课设的用例数值都很小，够用；如果老师非要测大整数，再在这里补一个溢出判断就行。第四，:=必须在单字符冒号之前处理，顺序反过来就会被拆成两个 token，这是词法分析里最经典的坑。

2.2 语法分析：递归下降解析为什么比运算符优先更省事

PL0 的文法几乎每个产生式都以一个关键词或标识符开头，天然适合递归下降。运算符优先分析法处理表达式很漂亮，但一旦铺到begin...end、if...then、while...do这些结构关键字，就得额外维护一张优先级表和状态机，代码量立刻失控。递归下降的做法是每个非终结符对应一个 Python 函数，调用栈本身就是语法树路径，报错时指到哪个函数就知道文法哪里断了。

# parser.py —— 递归下降解析器，生成简单的 AST class Node: def __init__(self, kind, line, **kwargs): self.kind = kind self.line = line for k, v in kwargs.items(): setattr(self, k, v) class Parser: def __init__(self, lexer): self.lexer = lexer self.token = None self.symtab = [] def advance(self): self.token = self.lexer.next_token() return self.token def match(self, expected): if self.token.type == expected: self.advance() return True raise SyntaxError(f"line {self.token.line}: 期望 {expected}，实际 {self.token.type}") def parse_block(self): if self.token.type == 'CONST': self.match('CONST') self.match('IDENT') self.match('EQUAL') self.match('NUMBER') self.match('SEMICOLON') if self.token.type == 'VAR': self.match('VAR') self.match('IDENT') while self.token.type == 'COMMA': self.match('COMMA') self.match('IDENT') self.match('SEMICOLON') while self.token.type == 'PROCEDURE': self.match('PROCEDURE') self.match('IDENT') self.match('SEMICOLON') self.parse_block() self.match('SEMICOLON') return self.parse_statement()

很多同学第一次写 parse_block 会把常量、变量、过程声明的顺序记错，PL0 的要求是常量在前、变量次之、过程再次，最后跟语句。标准 PL0 的过程声明里没有参数表，但不少课设为了考“传地址”会扩展成带参过程，这时就要在PROCEDURE后面多解析一对括号，括号里的形参用var前缀区分变量参数和值参数。这个扩展很值得做，后面 2.3 会解释它为什么是课设的考点。

另一个常见认知偏差是 PL0 的if语句没有else分支。文法里if condition then statement就结束了，不会像 C 语言那样在 then 后面跟一个复合语句的“花括号”。想写多语句必须用begin...end包起来。第一次跑测试用例的人十有八九会在这里翻车，因为语法分析器看到一个意外的else或end，报错行号却指向很远的地方。

2.3 符号表与运行时栈：传值和传地址的差别一次讲清

符号表是 PL0 课设里最容易被低估的模块。它不只是“变量名到类型”的映射，还得记录每个符号属于哪一层、在当前帧的偏移量是多少、是常量还是变量还是过程。PL0 的嵌套过程声明意味着符号表必须支持按层查找，内层同名变量要能遮蔽外层同名变量。

class Symbol: def __init__(self, name, kind, level=0, addr=0, value=None): self.name = name # 符号名 self.kind = kind # 'const' / 'var' / 'proc' / 'param' self.level = level # 静态嵌套层数 self.addr = addr # 在当前帧中的偏移地址 self.value = value # 常量值或过程的指令入口 def lookup(self, name): for sym in reversed(self.symtab): if sym.name == name: return sym return None

查找逻辑必须从符号表尾部往前扫，因为越晚插入的符号越内层，内层声明优先。实际课设里很多人写成从头往后查，结果内层过程里引用的永远是外层那个同名变量，现象非常隐蔽。

传值和传地址是 PL0 过程调用的核心区别。值参数在调用时把实参的当前值复制进新栈帧，过程内部怎么改都不影响主调方；变量参数则把实参的地址写进新栈帧，过程内部对它的读写最终作用到实参本身。落到指令层，值参数压的是一条值，变量参数压的是一条地址；解释器在取数指令里看到地址要先解引用一层，看到值就直接用。课设答辩时老师最爱问的就是“为什么过程里改了参数，外面没变”，答案就在这一层。

3. 用 Python 跑通最小可用的 PL0：目录结构、运行命令与核心代码

理论拆完就该让程序跑起来。最小可用的 PL0 解释器只需要四个文件，整个过程从读入.pl0文件到输出结果可以在十秒内跑通。这里的核心原则是：先把无参过程跑起来，再考虑扩展参数传递；先把指令列表打出来，再考虑优化和错误恢复。

3.1 三个文件的目录组织，以及从命令行读入 test.pl0

pl0/ ├─ main.py # CLI 入口，组装各模块 ├─ lexer.py # 词法分析 ├─ parser.py # 语法分析 + 指令生成 └─ interp.py # 解释执行

main.py 的职责是读文件、调 lexer 和 parser、把生成的指令列表交给 interpreter 执行。不要把所有代码堆在一个文件里，课设源码一般会要求分模块，而且分文件之后给老师讲模块划分也容易得多。

# main.py —— 命令行入口 import sys from lexer import Lexer from parser import Parser from interp import Interp def main(argv): trace = False files = [] for arg in argv: if arg == '--trace': trace = True else: files.append(arg) if not files: print("用法: python main.py [--trace] test.pl0") return 1 with open(files[0], encoding='utf-8') as f: text = f.read() lexer = Lexer(text) parser = Parser(lexer) parser.advance() ast = parser.parse_block() parser.match('PERIOD') code = parser.gen_code(ast) Interp(code, trace=trace).run() return 0

运行命令很简单：

python main.py test.pl0 python main.py --trace test.pl0

--trace开关是给答辩准备的可视化工具，后面第 6 章细讲。main.py 最后用match('PERIOD')强制要求程序以句号结束，这是 PL0 的语法规定，很多同学写成 C 风格的分号结尾导致解析失败，看到的是“期望 PERIOD，实际 EOF”这类报错，第一反应往往是代码错了，实际上只是不熟悉 PL0 的文法格式。

3.2 生成指令列表而不是直接执行 AST：让中间代码“看得见”

树解释器是很多人的第一版做法，parser 返回 AST 后边走边算，这样省掉一个生成中间代码的步骤，代码量确实小。但课设一旦要求展示“编译过程”，树解释器就露馅了——你没法跟老师说这是编译，因为根本没有生成任何目标代码。常见做法是生成一个指令列表，每条指令包含操作码、层级差、参数或跳转目标，这段指令列表既可以被解释器执行，也可以单独打印出来给老师看。

# parser.py 中的代码生成部分 class Inst: def __init__(self, op, level=0, arg=0): self.op = op self.level = level self.arg = arg def gen_expr(self, node): if node.kind == 'num': self.emit('LIT', 0, node.val) elif node.kind == 'ident': sym = self.symtab.lookup(node.name) self.emit('LOD', self.cur_level - sym.level, sym.addr) elif node.kind == 'bin': self.gen_expr(node.left) self.gen_expr(node.right) op_map = {'+': 'ADD', '-': 'SUB', '*': 'MUL', '/': 'DIV'} self.emit(op_map[node.op], 0, 0) def gen_stmt(self, node): if node.kind == 'assign': sym = self.symtab.lookup(node.name) self.gen_expr(node.expr) self.emit('STO', self.cur_level - sym.level, sym.addr) elif node.kind == 'if': self.gen_condition(node.cond) jpc = self.emit('JPC', 0, 0) self.gen_stmt(node.body) jpc.arg = len(self.code) # 回填跳转目标 elif node.kind == 'while': start = len(self.code) self.gen_condition(node.cond) jpc = self.emit('JPC', 0, 0) self.gen_stmt(node.body) self.emit('JMP', 0, start) jpc.arg = len(self.code)

注意if和while的跳转目标用的是“回填”技巧：先发射一条空跳转指令，等后面的语句代码生成完，再把当前位置写进这条指令的 arg 字段。很多第一次做课设的人在这里卡住，因为他们试图在解析 condition 的时候就计算出跳转目标，这不可能做到，因为 then 分支的代码长度还没生成。回填是解决这类问题的标准手段，答辩时提一句“这里用了回填法处理跳转地址”会非常加分。

3.3 LIT / LOD / STO / CAL 四条核心指令的模拟器怎么写

解释器是最后一块拼图。PL0 的指令集很小，核心就是 LIT（压常量）、LOD（取局部变量）、STO（存局部变量）、CAL（调用过程）这四条，加上 ADD/SUB/MUL/DIV 算术指令和 JMP/JPC 跳转指令就足以覆盖整门语言。

# interp.py —— 运行时栈与指令模拟器 class Interp: def __init__(self, code, trace=False): self.code = code self.pc = 0 self.stack = [] self.frames = [] # 每个元素是一个活动帧 {"name", "vars", "ret"} self.trace = trace def run(self): # 主程序的活动帧先入栈 self.frames.append({'name': 'main', 'vars': [], 'ret': -1}) while 0 <= self.pc < len(self.code): inst = self.code[self.pc] self.pc += 1 if self.trace: self.show(inst) if inst.op == 'LIT': self.stack.append(inst.arg) elif inst.op == 'LOD': frame = self.frames[-1 - inst.level] self.stack.append(frame['vars'][inst.arg]) elif inst.op == 'STO': frame = self.frames[-1 - inst.level] frame['vars'][inst.arg] = self.stack.pop() elif inst.op == 'CAL': args = [self.stack.pop() for _ in range(inst.argc)][::-1] self.frames.append({'name': inst.name, 'vars': args, 'ret': self.pc}) self.pc = inst.entry elif inst.op == 'RTN': frame = self.frames.pop() self.pc = frame['ret'] elif inst.op == 'JMP': self.pc = inst.arg elif inst.op == 'JPC': cond = self.stack.pop() if cond == 0: self.pc = inst.arg elif inst.op in ('ADD', 'SUB', 'MUL', 'DIV'): right = self.stack.pop() left = self.stack.pop() if inst.op == 'ADD': self.stack.append(left + right) elif inst.op == 'SUB': self.stack.append(left - right) elif inst.op == 'MUL': self.stack.append(left * right) else: self.stack.append(left // right)

这里的设计可以看作 PL0 虚拟机的一个教学简化版，没有完整复刻经典 PL0 的 display 表，而是用 frames 列表直接表示静态嵌套层次。LOD 指令里的 level 不是绝对层号，而是向上找几层帧，这正好对应代码生成阶段算出来的cur_level - sym.level。CAL 指令执行时，实参已经从栈顶弹出并逆序放进了新帧的 vars 数组，逆序这一步是因为实参压栈是正序压的，弹出时栈顶是最后一个实参，不反转顺序参数就全错位了。

4. PL0 课设的常见问题排查：从递归调用到符号表覆盖的 5 个坑

这一章的每条记录都是我做课设辅导时真实见过的翻车现场，按“现象 → 原因 → 解决”写，可以直接对照排查。

4.1 递归过程一调用就崩，或调用深度上不去

现象：写一个递归求斐波那契数的 PL0 程序，跑几个数就报 IndexError 或者直接卡死。

原因：最典型的是运行时栈用定长数组stack = [0] * 512，PL0 的递归每次调用都会在栈上分配新帧，深度一旦超过预设上限就会越界。另一个原因是 RTN 返回指令没写对，返回后 pc 没有恢复到调用点的下一条指令，于是递归看起来在无限增长。

解决：把所有栈结构改成 Python list 动态增长，不要预设上限。然后单独验证 CAL/RTN：写一个不递归的简单过程，跟踪 pc 在执行 CAL 前后的变化，确认返回地址是对的。更隐蔽的情况是解析器本身的递归深度——如果你在语法分析里用了递归下降处理超深嵌套的begin...end，Python 默认递归深度限制约 1000 也会触发，这时可以在 main.py 开头sys.setrecursionlimit(10000)，但这不是长久之计，更好的办法是避免让 parser 无谓地递归处理长语句序列。

4.2 内层同名变量把外层变量“吃掉”，查表顺序出问题

现象：内外两层过程都声明了变量x，内层过程修改x后，外层x也被改了，或反过来内层读到的总是外层值。

原因：符号表查找写成了从头往后遍历，先命中外层符号；或者命中了但没校验 level，把不匹配层级的符号当作当前变量用了。

解决：查找改成从表尾向前遍历，并优先返回最后一个命中的符号。PL0 的作用域规则就是内层遮蔽外层，后插入的符号一定比先插入的优先级高。改完之后补一个用例：内层循环里声明与外层同名变量，打印内外两个值，确认互不干扰。

4.3 VAR 参数当成值参数传，过程内部改了不生效

现象：过程声明了var x形参，调用时把实参传进去，过程内部给x赋了新值，返回后实参还是原值。

原因：调用点的指令生成逻辑对值参数和变量参数没有区分，统一用 LIT 把实参的当前值压栈了，过程内部拿到的是一个副本，怎么改都写不回实参。

解决：VAR 参数在调用点压的不是值而是地址。实现上可以在压栈前检查形参表的类型，值参数走gen_expr，变量参数走一条专门的“传地址”指令，解释器在 LOD/STO 时发现栈顶元素是地址类型就先解引用一层。这个改动只涉及参数处理，不影响已经写好的普通指令执行。

4.4 表达式优先级错乱：a+b*c先算了加法

现象：3+4*2算出 14，而正确答案是 11，乘法优先级失效了。

原因：parse_expression 里的代码直接return parse_expression()处理加减，把减法做成了右结合，同时让加减和乘除处于同一优先级层次。本质是文法层级丢失，expression 没有先经过 term 这一层。

解决：严格按expression -> term {(+|-) term}、term -> factor {(*|/) factor}、factor -> ident | number | ( expression )三层递归写。加减号的循环必须用 while 而不是递归返回，否则a-b-c会算成a-(b-c)，差一个符号就差出十万八千里。

4.5 语法错误一次性报出一大片，没法定位

现象：源文件某行少了一个分号，结果报错信息从漏分号的位置一路崩到文件末尾，几十行红色错误根本看不出根因。

原因：match 函数一旦失败就直接抛异常终止整个编译过程，或者反过来的极端——每次失败都只推进一个 token，导致对同一个错误反复报告。

解决：给 parser 加错误恢复。match 失败时记录一条错误，然后做 panic 模式同步，跳过当前语句直到分号或 END 再继续解析。这样漏一个分号只会报一次错，后面的代码还能继续检查，一处错误恢复的设计能避免无数次调试时的痛苦。

5. 从能跑到能答辩：测试用例、错误恢复与课设报告的组织

课设评分不会只看“最后那个用例能不能跑”，过程文档、边界测试、错误处理都会影响分数。这一章解决的是把程序从“自己觉得能跑”变成“老师面前经得起演示”。

5.1 测试用例怎么搭：阶乘、递归、边界输入一张表说清

最好的测试矩阵不是随机找程序，而是每个用例针对一个语法点或一个容易出错的语义点。我建议至少准备下面五类用例，运行结果要逐条记录。

阶乘是 PL0 的经典入口用例，它把赋值、while、复合语句全部串了一遍，而且预期结果一目了然。递归用例则专门盯着参数传递和过程调用栈，建议用两个参数的过程，一个值参数一个变量参数，实测变量参数是否写回实参。边界输入不要只测正确程序，错误用例同样要留存输出结果，报告里写“本程序能对缺分号给出定位准确的一条错误”和“本程序跑通所有正确用例”一样有价值。

5.2 三层次错误恢复：词法、语法、语义分别怎么兜底

错误处理是课设里最容易被省略但最显功力的部分。词法层错误最简单，遇到非法字符直接记录“第几行遇到非法字符”然后跳过该字符继续扫描，保证一次能查出所有词法错误。语法层用 panic 模式，match 失败后跳过当前语句到分号或 END。

def match(self, expected): if self.token.type == expected: self.advance() return True self.errors.append(f"line {self.token.line}: 期望 {expected}") while self.token.type not in ('SEMICOLON', 'END', 'EOF'): self.advance() if self.token.type == 'SEMICOLON': self.advance() return False

这段代码的原理是“吞掉所有 token 直到遇到可信赖的同步点”，分号和 END 就是这样的同步点，因为它们一般是语句边界的固定标志。缺点是可能会连带丢掉一些合法代码，但对课设场景来说，一条语句报一次错比满屏红色错误实用得多。语义层错误（比如变量未声明）处理方法是：lookup 返回 None 时记录错误，同时往符号表里塞一个占位符，让后面的生成代码不崩，解析继续往下走。三层的共同原则是“一次编译尽量报出全部问题”，而不是碰壁就退出，这在答辩时很加分。

5.3 课设报告写哪些内容：从总体设计到测试分析

一份能过审的课设报告通常会按六个部分组织：题目与需求说明、总体设计、详细设计、测试与分析、运行环境与使用说明、总结。这里最容易犯的错是把报告写成代码注释的堆砌，整页贴源码。正确做法是在详细设计部分只贴核心数据结构（Token、Symbol、Inst）和关键流程（生成器如何处理 if 回填），其余用文字描述。

测试与分析部分是拉开分差的地方，别只贴“运行成功”截图。把 5.1 的测试表放进去，每条标注预期输出与实际输出，错误用例则贴出错误恢复后的编译信息，分析为什么这条报错定位到了正确的行。总体设计里的模块图可以用文字加箭头描述，我一般会画一个“源程序 → Lexer → Token 流 → Parser → 中间指令列表 → Interp → 输出”的数据流，再配上四个文件的职责一句话说明，老师扫一眼就知道你理解了编译过程的全貌。

6. 给 PL0 运行时加一个 TRACE 开关：答辩时一眼看穿执行过程

6.1 在解释器循环里打印每条指令和运行时栈

程序跑通只是第一步，答辩时老师最常问的问题是“这条 LOD 指令为什么取到这个值”。如果对着代码现想，很容易卡壳。我习惯在解释器里内置一个 TRACE 开关，每条指令执行前打印指令本身、当前栈的内容、以及当前活动帧的名称，执行轨迹一目了然。

def show(self, inst): frame_names = [f['name'] for f in self.frames] print(f"pc={self.pc - 1:4d} {inst.op:5s} level={inst.level} arg={inst.arg} " f"stack={self.stack[-10:]} frames={frame_names}")

有了这段输出，跑一个递归求阶乘的用例，可以看到 CAL 执行时 frames 列表里依次出现 main、fact、fact、fact，每层返回时 frames 又逐个变短。这个画面比任何文字解释都直观。我自己当年第一次写 PL0 用的 C++，一个 display 数组的 level 错位查了三个晚上没头绪，后来用 Python 重构，加了这个 trace 之后二十分钟就定位到是返回地址没有正确恢复。所以如果你也卡在某个奇怪的结果上，不要对着源码发呆，先把栈打出来看，这是最直接的排错路径。希望帮到你。

6.2 答辩演示顺序的建议

演示时不要一上来就跑复杂程序。先跑一个简单的赋值与算术用例，用 trace 展示 LIT、ADD、STO 三条指令如何协作；再跑阶乘，展示 JMP/JPC 控制流和 while 循环；最后跑递归用例，展示 CAL/RTN 的帧切换。按这个顺序讲，等于把词法、语法、运行时三个模块在老师面前重演了一遍，既展示了代码能力，又展示了理解深度。做课设时保留这个 trace 习惯，以后不管做什么解释器都会受用。

本文还有配套的精品资源，点击获取