简介这份PL/0编译器完整实验工程源自山东大学编译原理课程面向计算机专业本科生及自学编译原理的开发者可帮助理解词法分析、语法分析、语义分析及抽象语法树构建等前端核心技术。压缩包共94个文件约513KB主体为C/C源码与头文件并配有多组in/out测试样例、CMake构建配置、代码工程文件及可执行程序另有数张运行截图和一份实验报告文档便于对照结果与验证过程。资源代码结构清晰涵盖从词法扫描、递归下降解析到符号表与中间表示的主要环节同时保留测试模式与多种示例程序如素数、乘方、公约数等的运行记录既适合课程实验参考也可作为深入调试和二次开发的起点。当前已有104人学习浏览值得编译方向学习者借鉴。1. PL0-Compiler 是什么——SDU 编译原理实验的最小闭环PL0-Compiler 在编译原理课上指的不是某个开源大工程而是那个能完整跑通“源码到可执行”的最小编译器读入教学语言 PL/0 的源码依次完成词法分析、语法分析、语义分析生成 P-code 指令再交给一台栈式虚拟机解释执行。山东大学SDU的编译原理课程实验常年以 PL/0 作为主线载体要求在一个小而全的语言里把编译器的每个阶段亲手实现一遍。它小到能在一学期内写透又全到词法、语法、语义、代码生成、运行环境一个不缺所以被不少学生当成“没跑通就不算学过编译原理”的必修任务。很多人觉得 PL/0 是玩具真写完才发现对栈式指令模型、活动记录布局和静态作用域的理解与只读教材完全是两回事。下面按我做课程设计的实际顺序展开先写词法分析器再做带语义动作的递归下降语法分析器最后把 P-code 虚拟机跑起来并给出几个实验里高频出现的坑。2. 词法分析器用 Java 把 PL/0 源码切成 Token 流2.1 保留字优先还是标识符优先——先定识别策略词法分析是编译原理实验里最先落地的模块任务很简单把源文件里的字符串切成一串有类型的 Token。PL/0 的词汇量不大保留字一共十三个begin、end、if、then、while、do、call、const、var、procedure、odd、read、write。看起来容易但第一步选错策略后面改起来会很难受。常见做法有两种。一种是“标识符优先”把字母开头的串一律先当标识符读出来再查保留字表命中就改成保留字类型。另一种是逐字符硬匹配或者叫“保留字优先”在扫描时对每个保留字单独判断。我一般选第一种原因很简单PL/0 的保留字和用户标识符字符组成完全一样唯一的区分依据就是一张表。用 HashMap 存保留字一行 getOrDefault 就解决后续要给语言加 for、repeat 这类新关键字也只是往静态块里补一条 put词法模块不需要动。另一个要定的是 Token 的表示方式。我会用一个枚举列全部类型再用一个 record 或简单类保存 type、value、行号。行号属于老生常谈但调试语法错误时缺了它确实会头大。Token 类型如果设计得太粗比如把所有比较符塞进同一个类型语法分析阶段就要反复拼字符串不值得。2.2 词法核心实现一份能直接跑的 Lexer下面给出一份 Java 实现的词法分析器骨架省去异常处理和文件读取只看主逻辑public class Lexer { private final String src; private int pos 0; private static final MapString, TokenType KEYWORDS new HashMap(); static { KEYWORDS.put(begin, TokenType.BEGIN); KEYWORDS.put(end, TokenType.END); KEYWORDS.put(if, TokenType.IF); KEYWORDS.put(then, TokenType.THEN); KEYWORDS.put(while, TokenType.WHILE); KEYWORDS.put(do, TokenType.DO); KEYWORDS.put(call, TokenType.CALL); KEYWORDS.put(const, TokenType.CONST); KEYWORDS.put(var, TokenType.VAR); KEYWORDS.put(procedure, TokenType.PROCEDURE); KEYWORDS.put(odd, TokenType.ODD); KEYWORDS.put(read, TokenType.READ); KEYWORDS.put(write, TokenType.WRITE); } public Token next() { skipWhitespaceAndComments(); if (pos src.length()) return new Token(TokenType.EOF, ); char c src.charAt(pos); if (Character.isLetter(c)) return readWord(); if (Character.isDigit(c)) return readNumber(); return readSymbol(); } private Token readWord() { int start pos; while (pos src.length() Character.isLetterOrDigit(src.charAt(pos))) pos; String word src.substring(start, pos); TokenType type KEYWORDS.getOrDefault(word, TokenType.IDENT); return new Token(type, word); } private Token readNumber() { int start pos; while (pos src.length() Character.isDigit(src.charAt(pos))) pos; // 检查非法标识符例如 123abc if (pos src.length() Character.isLetter(src.charAt(pos))) { error(pos, 非法符号: 数字后不能紧跟字母); while (pos src.length() Character.isLetterOrDigit(src.charAt(pos))) pos; } return new Token(TokenType.NUMBER, src.substring(start, pos)); } private Token readSymbol() { char c1 src.charAt(pos); if (pos src.length()) { char c2 src.charAt(pos); if ((c1 : c2 ) || (c1 c2 ) || (c1 c2 ) || (c1 c2 )) { pos; return new Token(TokenType.fromSymbol( c1 c2), c1 c2); } } // 单字符运算符与分隔符 return new Token(TokenType.fromSymbol(String.valueOf(c1)), String.valueOf(c1)); } }这段代码里最重要的点是 readWord 的“先拼词、后定性”顺序先用 isLetterOrDigit 把连续的字母数字吞干净再统一查表这样就不会出现把 begin1 错认成保留字的问题。readNumber 里加的那个“数字后紧接字母”检查是很多初版词法器都漏掉的地方——12ab如果不在这里报语法分析阶段会给一条“缺少运算符”的提示位置已经偏了排查起来很绕。PL/0 只有三个双字符运算符:、、还有一个。词法上可以先读一个字符再试探第二个成对则吞掉。比较符之间的优先级在词法层不需要关心语法层的 condition 会用嵌套文法把关系运算收进去。参数说明上所有 Token 不带行号信息调试时容易失去定位能力所以我在生产版本里会给 Token 再加一个 line 字段next() 方法顺手记录换行数。2.3 词法错误处理报错位置而不是直接崩溃词法分析最常见的返工原因是“报一个错就死”。比如用户在:后面误写了一个:如果直接抛异常退出后面真正的错误全部被掩盖实验做到后期会被这种交互恶心到。我习惯在 Lexer 里维护一个 error 列表碰到非法字符时记录位置、跳过该字符、继续扫描public final ListString errors new ArrayList(); private void error(int pos, String msg) { errors.add(line line , char pos : msg); }这样做的好处是多个词法错误可以一次性暴露语法分析阶段拿到的 Token 流也相对干净。真正需要崩溃的只有输入文件不存在这一种其他都走“尽力恢复”路线。等到语法分析阶段再错误累计、统一输出实验报告里也更好写错误恢复这一节。编译原理实验里“错误报告”同样是评分点很多同学只重视主流程忽略了错误路径这其实很可惜。3. 递归下降语法分析 语义动作一边解析一边生成 P-code3.1 为什么选递归下降而不是 yacc/ANTLR语法分析器的选型常被误会成“能用工具就别手写”。但对 PL/0 来说用 yacc 或 ANTLR 反而别扭文法小到不需要处理优先级冲突工具生成的解析器还额外引入了一层中间结构。递归下降是最贴合这门实验的方案每个非终结符对应一个方法方法调用树天然就是语法树。PL/0 的文法适合手写解析核心可以压成几句话一个程序是一个 block 加一个点block 由可选的常量声明、变量声明、过程声明和一条语句组成statement 则分支到赋值、调用、begin-end 复合语句、if、while、read、write。每个非终结符对应 Java 方法所有解析器共享一个 look Token 和 next() 方法语法错误在 expect 里统一报而不是靠解析器自动恢复。从代码量看递归下降写出来大约三四百行yacc 方案虽然文法文件短但语义动作要嵌在生成代码里调试时要在生成器输出和手写代码之间反复横跳综合效率并不高。递归下降唯一的“玄学”点是左递归文法不能直接翻译好在 PL/0 的 expr 和 term 在教科书里已经改写成右循环形式问题不大。3.2 符号表与作用域const/var/procedure 声明怎么管理语义分析的核心是符号表。PL/0 的作用域规则和 Pascal 一样过程可以嵌套内层能看见外层的常量和变量外层看不见内层。实现上我维护一张“符号表 当前层级变量”将常量、变量、过程统一放进同一个表每条符号都带 kind、name、level、addr 四个字段class Symbol { enum Kind { CONST, VAR, PROC } Kind kind; String name; int level; // 声明该符号时的层级 int addr; // 常量用 value变量用帧内偏移量过程用代码入口地址 }声明时只需在当前层查找同名避免遮蔽链路上的重复定义访问时则从当前层逐层向外找找到后用level - sym.level算出层级差这个值就是后续 LOD/STO 指令的 arg1。变量地址在一个 block 内按声明顺序从 0 开始递增每个变量对应一个栈槽过程声明不占栈槽只记录它将来在代码段中的入口地址。block 的解析同时负责声明和代码生成void block() { int oldLevel level; // 常量声明: const a 1, b 2; if (look.type TokenType.CONST) { next(); do { String name expectIdent(); expect(TokenType.EQ); int val expectNumber(); declareConst(name, val); } while (look.type TokenType.COMMA); expect(TokenType.SEMICOLON); } // 变量声明: var x, y, z; if (look.type TokenType.VAR) { next(); do { String name expectIdent(); declareVar(name); } while (look.type TokenType.COMMA); expect(TokenType.SEMICOLON); } // 过程声明: procedure p; ...; procedure q; ...; while (look.type TokenType.PROCEDURE) { next(); String name expectIdent(); expect(TokenType.SEMICOLON); level; block(); // 内层 block 使用 level1 做作用域 level--; expect(TokenType.SEMICOLON); declareProc(name, code.size()); } statement(); }这段代码的精髓在过程声明处先level再递归调用 block()出来后再level--。内层 block 里声明的所有变量、嵌套过程都会带着更大的 level 序号落进符号表而 process 返回后外层 statement 继续用原来的 level恰好完成了嵌套作用域切换。符号查找时自上而下逐层扫描自然实现了“内层遮蔽外层同名变量”的语义不需要额外做遮蔽链表。declareVar 的地址分配是另一个细节每声明一个变量就让 frameSize 加 1该变量的地址就是当前 frameSize 的值。这样 block 结束时 frameSize 正好是全部局部变量槽数后面 INT 指令的参数可以直接取这个值。3.3 表达式解析与 P-code 生成并行PL/0 的代码生成可以做成“解析过程即代码生成过程”不需要先建 AST 再二次遍历。原因在于 PL/0 没有类型转换运算优先级已经由文法嵌套天然决定factor 归约后立刻发一条指令即可。表达式文法采用三级嵌套expr 处理加减term 处理乘除factor 收束到常量、变量或括号。void expr() { term(); while (look.type TokenType.PLUS || look.type TokenType.MINUS) { Token op look; next(); term(); emitOp(op.type TokenType.PLUS ? OPR_ADD : OPR_SUB); } } void term() { factor(); while (look.type TokenType.TIMES || look.type TokenType.SLASH) { Token op look; next(); factor(); emitOp(op.type TokenType.TIMES ? OPR_MUL : OPR_DIV); } } void factor() { if (look.type TokenType.NUMBER) { emit(Instruction.LIT, 0, Integer.parseInt(look.value)); next(); } else if (look.type TokenType.IDENT) { Symbol s findSymbol(look.value); emit(Instruction.LOD, level - s.level, s.addr); next(); } else if (look.type TokenType.LPAREN) { next(); expr(); expect(TokenType.RPAREN); } }1 2 * 3的执行路径是expr 调 termterm 先 factor(1)遇到*后再 factor(2)、factor(3)于是生成的指令顺序是 LIT 1、LIT 2、LIT 3、OPR 乘法、OPR 加法。注意乘法指令先发出加法指令后发出P-code 在虚拟机里运行时自然会先算乘再算加优先级就这么被文法结构保证了。这里有个容易看走眼的点emit的时机在操作数之后、下一个循环判断之前。如果不小心把加减指令发在 term() 调用前生成结果就会变成反波兰的混乱状态虚拟机一跑就翻车。另一个常被忽略的点是常量折叠实验不需要做PL/0 的常量在 factor 里直接 LIT 即可折叠属于优化阶段的事在这里做反而会让后续扩展变难。4. P-code 虚拟机让生成的指令真正跑起来4.1 指令集与活动记录布局代码生成后的产物是一段 P-code 字节码PL/0 实验的标准机型是一台栈式虚拟机。指令最少 8 条LIT 加载常量OPR 做算术与比较LOD 读取变量STO 写入变量CAL 调用过程INT 开栈空间JMP 无条件跳转JPC 条件跳转。每条指令是op, arg1, arg2三元组语义各异。我一般把 P-code 的指令布局参数化成一张表方便查指令arg1arg2语义LIT0常量值压入常量LOD层级差变量偏移从指定帧读变量压栈STO层级差变量偏移栈顶写入指定变量INT0帧大小为局部变量分配栈空间OPR0子操作码算术/比较/返回CAL层级差过程入口调用过程JMP0目标地址无条件跳转JPC0目标地址栈顶为 0 时跳转OPR 的 arg2 是子功能表返回、取负、加减乘除、奇偶判断、大小比较共用一条大指令这是 Wirth 当年为了压缩教学代码长度做的设计今天我们依旧沿用因为实现简单、实验报告省事。活动记录布局才是虚拟机真正的难点。PL/0 的过程活动记录我采用三链帧frame[0] 返回地址 frame[1] 动态链指向调用者的旧 BP frame[2] 静态链指向声明该过程的作用域帧基址 frame[3..] 局部变量槽动态链用于返回时恢复调用者环境静态链用于访问外层的局部变量。嵌套层级差越大静态链要走的跳数越多这就是 base() 函数的来由。CAL 指令实际做的事情是当前指令指针压栈作为返回地址旧 BP 压栈作为动态链再沿静态链找到目标帧基址压栈然后 BP 指向新帧起点IP 跳到过程入口。4.2 VM 主循环取指、译码、执行虚拟机的实现比编译器主体更接地气核心就是一个 while 循环根据 ip 取指令、译码、执行。为保证可读性我会把指令先扁平化存进一个 int 数组每三个整数代表一条指令public class VirtualMachine { private int[] code; // 扁平化的 P-code 指令数组 private int[] stack; // 数据栈 private int ip, sp, bp; private int base(int level) { int b bp; for (int i 0; i level; i) b stack[b 2]; return b; } public void run() { while (ip code.length) { int op code[ip]; int arg1 code[ip 1]; int arg2 code[ip 2]; ip 3; switch (op) { case LIT - stack[sp] arg2; case INT - sp arg2; case LOD - stack[sp] stack[base(arg1) arg2]; case STO - stack[base(arg1) arg2] stack[sp--]; case JMP - ip arg2; case JPC - { if (stack[sp--] 0) ip arg2; } case CAL - { stack[sp] ip; // 压入返回地址 stack[sp] bp; // 压入动态链 stack[sp] base(arg1); // 压入静态链 bp sp - 2; ip arg2; } case OPR - handleOpr(arg2); } } } private void handleOpr(int sub) { if (sub OPR_RETURN) { sp bp; ip stack[bp]; bp stack[bp 1]; return; } int v stack[sp]; // 其余算术/比较分支在此展开 } }主循环的关键点有几个。第一LOD 和 STO 都要先通过 base(arg1) 算出目标帧基址再加上变量的 arg2 偏移帧内寻址就是一次数组访问。第二CAL 压入三个链点后BP 指向sp - 2此时 frame[2] 正好落在栈顶的三元组中间读取静态链的位置得以固定。第三OPR 的返回分支里sp bp是整帧回收把栈指针拉回当前帧起点再把返回地址和动态链分别弹给 ip 和 bp调用者环境即被恢复。这里最容易出错的是“过程调用无参数”这个前提。PL/0 经典教学写法里过程确实不声明参数变量共享全靠作用域所以返回时不需要清理参数槽。如果你扩展了带参过程活动记录布局要重新设计参数区要放在返回地址之前否则 sp 回收后参数残留会污染后续计算。4.3 运行期错误处理除零、栈溢出、未初始化课程实验的虚拟机拿数组当内存栈溢出往往表现为 ArrayIndexOutOfBoundsException这类异常信息对用户极不友好。我建议在 sp 的读写处加一层边界检查压下前判sp 1 stack.length超出则打印“栈溢出检查过程调用是否存在死循环”同时 dump 当前所有过程调用的返回地址链。除零错误则要在 OPR 的除法分支里显式判断 divisor 是否为 0。PL/0 的算子都跑在同一台 OPR 大指令下加一行判断成本极低但对运行期错误报告的完整性帮助很大。未初始化变量在经典 PL/0 语义里默认值是 0不会像现代语言那样报错如果实验有额外要求可以在 LOD 指令里加一个“是否写过”的位标记变量声明时全部清 0写指令置 1读指令检查未写则报运行时警告。这个选开后作用域和初始化的边界坑也能被覆盖到。运行期错误处理还有一条不要在 JMP/JPC 跳转前不校验目标地址。回填错误是编译阶段的高频 bug如果虚拟机对非法地址零容忍直接崩溃那排错时只能看到越界异常完全不知道自己错在代码生成的那一段这属于典型的“黑匣子”痛苦。5. 避坑与常见问题排查五个高频踩坑记录5.1 ODD 被当成普通标识符词法表漏词现象if odd(x) then ...被解析成“调用变量 odd”语法报错。原因保留字表里漏掉了 odd词法分析器把它判成了 IDENT语法分析沿标识符路径走后面跟的括号就完全没法解释。解决先在 KEYWORDS 里补上 odd确认 token 类型是 ODD。同时注意 odd 在语法上不属于 factor它应该出现在 condition 的入口生成 OPR_ODD 指令而不是普通函数调用。这类问题用 dump-tokens 一行就能定位比我当年靠肉眼扫代码快得多。5.2 begin end 空语句块报错分号消费顺序现象合法程序begin end.在 begin 处报“期望语句”或者begin a : 1 end报“期望分号”。原因statement 的复合语句解析写得过死进 begin 后无条件要求先出现一条语句或每条语句后都强制消费分号导致空块和末条无分号全部失败。解决把复合语句写成循环逻辑next()之后只要 look 不是 END 就解析一条 statement之后分号出现则消费并继续遇到 END 则退出。注意循环内不能先 expect 分号再判断结尾否则末尾那个分号会被错误消费。这个坑在多层 begin 嵌套时特别磨人建议手推三四个用例再运行。5.3 内层过程访问外层变量取到错值层级差算错现象外层声明var x内层过程里读 x结果拿到的是另一帧的垃圾数据。原因LOD 指令的 arg1 层级差计算错误。符号表查找按名返回内层同名符号但声明层级可能在外层level - sym.level才是正确差。如果直接用当前 level 或者用 0 代替base() 就找不到目标帧。解决给符号表加一个 debug 方法打印每个 Symbol 的 name/kind/level/addr再给指令 dump 打印 LOD 的 arg1。两端一对照就能发现是编译器发错层级差还是虚拟机 base() 跟随静态链的逻辑写错。这个坑从符号表到虚拟机跨了三个阶段属于最难靠猜的 bug 之一。5.4 跳转回填目标偏移一个指令JPC 回填时机现象while 循环只执行一次就退出或者 if 分支走了不该走的分支。原因生成 if/while 时先用占位 emit 一条 JPC等语句结束后用code.size()回填。如果回填时机写在 statement 内部某次 emit 之前目标地址就差了数条指令机器拿到的跳转点整个错位。解决把回填点存到局部变量例如int jpc emit(JPC, 0, 0)等解析完分支体后再backpatch(jpc, code.size())。同理while 的循环头地址要在条件表达式开头保存JMP 的返回目标再回填一次。我后来养成的习惯是每次生成跳转指令都顺手打印一行 P-code 当前偏移错误一眼可见。5.5 负数除法结果与预期不符整除语义没定义现象-7 / 2在有的机器上出 -3有的出 -4测试用例对不上。原因不同语言对整除的取整方向规定不同PL/0 教学定义没细写虚拟机实现里直接复制了宿主语言的除法语义。解决在虚拟机的 OPR_DIV 分支统一“向零取整”先判断符号再按绝对值除最后恢复符号。同时把这条语义写进实验报告说明实现策略。这个坑不算代码错误算是“语义规格缺失”但课程验收时最容易因为一个边界值被问倒提前定好策略能少很多麻烦。6. 把实验做出彩三个可落地的扩展与验证方法做到这里一个能跑 PL/0 的编译器已经成型但要让实验作业真正有区分度我会再补三件事。第一扩展 repeat-until 循环。语法上给 PL/0 加两条规则词法表补 repeat、until文法加一个方法即可。生成代码时要留意条件方向repeat-until 是条件为假时继续循环所以 until 后生成的是 JPC 跳回循环头而不是 JMP。多加这一条P-code 里的跳转手法就覆盖了“前测试”和“后测试”两种模式对指令回填的理解会更深一层。第二做标准 dump 输出。编译器加两个命令行开关--dump-tokens打印 Token 流--dump-code打印带偏移量的 P-code 表。调试时看着 dump 再对照虚拟机执行回填错位、符号表越界这些问题都是秒级定位。dump 输出示例长这样0: LIT 0 10 3: LOD 0 3 6: JPC 0 21 9: LIT 0 1 12: LOD 0 3 15: OPR 0 5第三做一组回归用例。不需要多十来个文件足够常量运算、变量遮蔽、过程嵌套、while、begin-end、除零、负数除法。每改一次虚拟机或符号表把这批用例全部跑一遍如果有用例结果变了说明改动影响到了基础语义。编译原理实验越到后期越容易“改一处坏一片”回归测试是成本最低的后悔药。我在做这门实验时吃过最大的亏就是跳过了 dump 调试用肉眼在几十条指令里数回填点结果 while 嵌套加上 begin-end 之后错乱了一下午。后来把 dump 和回归用例补齐同样的错误基本能在十分钟内定位。这个习惯我后来做真实工具链时也一直在用。希望这篇 PL/0 的落地笔记能帮到你。本文还有配套的精品资源点击获取
简介这份PL/0编译器完整实验工程源自山东大学编译原理课程面向计算机专业本科生及自学编译原理的开发者可帮助理解词法分析、语法分析、语义分析及抽象语法树构建等前端核心技术。压缩包共94个文件约513KB主体为C/C源码与头文件并配有多组in/out测试样例、CMake构建配置、代码工程文件及可执行程序另有数张运行截图和一份实验报告文档便于对照结果与验证过程。资源代码结构清晰涵盖从词法扫描、递归下降解析到符号表与中间表示的主要环节同时保留测试模式与多种示例程序如素数、乘方、公约数等的运行记录既适合课程实验参考也可作为深入调试和二次开发的起点。当前已有104人学习浏览值得编译方向学习者借鉴。1. PL0-Compiler 是什么——SDU 编译原理实验的最小闭环PL0-Compiler 在编译原理课上指的不是某个开源大工程而是那个能完整跑通“源码到可执行”的最小编译器读入教学语言 PL/0 的源码依次完成词法分析、语法分析、语义分析生成 P-code 指令再交给一台栈式虚拟机解释执行。山东大学SDU的编译原理课程实验常年以 PL/0 作为主线载体要求在一个小而全的语言里把编译器的每个阶段亲手实现一遍。它小到能在一学期内写透又全到词法、语法、语义、代码生成、运行环境一个不缺所以被不少学生当成“没跑通就不算学过编译原理”的必修任务。很多人觉得 PL/0 是玩具真写完才发现对栈式指令模型、活动记录布局和静态作用域的理解与只读教材完全是两回事。下面按我做课程设计的实际顺序展开先写词法分析器再做带语义动作的递归下降语法分析器最后把 P-code 虚拟机跑起来并给出几个实验里高频出现的坑。2. 词法分析器用 Java 把 PL/0 源码切成 Token 流2.1 保留字优先还是标识符优先——先定识别策略词法分析是编译原理实验里最先落地的模块任务很简单把源文件里的字符串切成一串有类型的 Token。PL/0 的词汇量不大保留字一共十三个begin、end、if、then、while、do、call、const、var、procedure、odd、read、write。看起来容易但第一步选错策略后面改起来会很难受。常见做法有两种。一种是“标识符优先”把字母开头的串一律先当标识符读出来再查保留字表命中就改成保留字类型。另一种是逐字符硬匹配或者叫“保留字优先”在扫描时对每个保留字单独判断。我一般选第一种原因很简单PL/0 的保留字和用户标识符字符组成完全一样唯一的区分依据就是一张表。用 HashMap 存保留字一行 getOrDefault 就解决后续要给语言加 for、repeat 这类新关键字也只是往静态块里补一条 put词法模块不需要动。另一个要定的是 Token 的表示方式。我会用一个枚举列全部类型再用一个 record 或简单类保存 type、value、行号。行号属于老生常谈但调试语法错误时缺了它确实会头大。Token 类型如果设计得太粗比如把所有比较符塞进同一个类型语法分析阶段就要反复拼字符串不值得。2.2 词法核心实现一份能直接跑的 Lexer下面给出一份 Java 实现的词法分析器骨架省去异常处理和文件读取只看主逻辑public class Lexer { private final String src; private int pos 0; private static final MapString, TokenType KEYWORDS new HashMap(); static { KEYWORDS.put(begin, TokenType.BEGIN); KEYWORDS.put(end, TokenType.END); KEYWORDS.put(if, TokenType.IF); KEYWORDS.put(then, TokenType.THEN); KEYWORDS.put(while, TokenType.WHILE); KEYWORDS.put(do, TokenType.DO); KEYWORDS.put(call, TokenType.CALL); KEYWORDS.put(const, TokenType.CONST); KEYWORDS.put(var, TokenType.VAR); KEYWORDS.put(procedure, TokenType.PROCEDURE); KEYWORDS.put(odd, TokenType.ODD); KEYWORDS.put(read, TokenType.READ); KEYWORDS.put(write, TokenType.WRITE); } public Token next() { skipWhitespaceAndComments(); if (pos src.length()) return new Token(TokenType.EOF, ); char c src.charAt(pos); if (Character.isLetter(c)) return readWord(); if (Character.isDigit(c)) return readNumber(); return readSymbol(); } private Token readWord() { int start pos; while (pos src.length() Character.isLetterOrDigit(src.charAt(pos))) pos; String word src.substring(start, pos); TokenType type KEYWORDS.getOrDefault(word, TokenType.IDENT); return new Token(type, word); } private Token readNumber() { int start pos; while (pos src.length() Character.isDigit(src.charAt(pos))) pos; // 检查非法标识符例如 123abc if (pos src.length() Character.isLetter(src.charAt(pos))) { error(pos, 非法符号: 数字后不能紧跟字母); while (pos src.length() Character.isLetterOrDigit(src.charAt(pos))) pos; } return new Token(TokenType.NUMBER, src.substring(start, pos)); } private Token readSymbol() { char c1 src.charAt(pos); if (pos src.length()) { char c2 src.charAt(pos); if ((c1 : c2 ) || (c1 c2 ) || (c1 c2 ) || (c1 c2 )) { pos; return new Token(TokenType.fromSymbol( c1 c2), c1 c2); } } // 单字符运算符与分隔符 return new Token(TokenType.fromSymbol(String.valueOf(c1)), String.valueOf(c1)); } }这段代码里最重要的点是 readWord 的“先拼词、后定性”顺序先用 isLetterOrDigit 把连续的字母数字吞干净再统一查表这样就不会出现把 begin1 错认成保留字的问题。readNumber 里加的那个“数字后紧接字母”检查是很多初版词法器都漏掉的地方——12ab如果不在这里报语法分析阶段会给一条“缺少运算符”的提示位置已经偏了排查起来很绕。PL/0 只有三个双字符运算符:、、还有一个。词法上可以先读一个字符再试探第二个成对则吞掉。比较符之间的优先级在词法层不需要关心语法层的 condition 会用嵌套文法把关系运算收进去。参数说明上所有 Token 不带行号信息调试时容易失去定位能力所以我在生产版本里会给 Token 再加一个 line 字段next() 方法顺手记录换行数。2.3 词法错误处理报错位置而不是直接崩溃词法分析最常见的返工原因是“报一个错就死”。比如用户在:后面误写了一个:如果直接抛异常退出后面真正的错误全部被掩盖实验做到后期会被这种交互恶心到。我习惯在 Lexer 里维护一个 error 列表碰到非法字符时记录位置、跳过该字符、继续扫描public final ListString errors new ArrayList(); private void error(int pos, String msg) { errors.add(line line , char pos : msg); }这样做的好处是多个词法错误可以一次性暴露语法分析阶段拿到的 Token 流也相对干净。真正需要崩溃的只有输入文件不存在这一种其他都走“尽力恢复”路线。等到语法分析阶段再错误累计、统一输出实验报告里也更好写错误恢复这一节。编译原理实验里“错误报告”同样是评分点很多同学只重视主流程忽略了错误路径这其实很可惜。3. 递归下降语法分析 语义动作一边解析一边生成 P-code3.1 为什么选递归下降而不是 yacc/ANTLR语法分析器的选型常被误会成“能用工具就别手写”。但对 PL/0 来说用 yacc 或 ANTLR 反而别扭文法小到不需要处理优先级冲突工具生成的解析器还额外引入了一层中间结构。递归下降是最贴合这门实验的方案每个非终结符对应一个方法方法调用树天然就是语法树。PL/0 的文法适合手写解析核心可以压成几句话一个程序是一个 block 加一个点block 由可选的常量声明、变量声明、过程声明和一条语句组成statement 则分支到赋值、调用、begin-end 复合语句、if、while、read、write。每个非终结符对应 Java 方法所有解析器共享一个 look Token 和 next() 方法语法错误在 expect 里统一报而不是靠解析器自动恢复。从代码量看递归下降写出来大约三四百行yacc 方案虽然文法文件短但语义动作要嵌在生成代码里调试时要在生成器输出和手写代码之间反复横跳综合效率并不高。递归下降唯一的“玄学”点是左递归文法不能直接翻译好在 PL/0 的 expr 和 term 在教科书里已经改写成右循环形式问题不大。3.2 符号表与作用域const/var/procedure 声明怎么管理语义分析的核心是符号表。PL/0 的作用域规则和 Pascal 一样过程可以嵌套内层能看见外层的常量和变量外层看不见内层。实现上我维护一张“符号表 当前层级变量”将常量、变量、过程统一放进同一个表每条符号都带 kind、name、level、addr 四个字段class Symbol { enum Kind { CONST, VAR, PROC } Kind kind; String name; int level; // 声明该符号时的层级 int addr; // 常量用 value变量用帧内偏移量过程用代码入口地址 }声明时只需在当前层查找同名避免遮蔽链路上的重复定义访问时则从当前层逐层向外找找到后用level - sym.level算出层级差这个值就是后续 LOD/STO 指令的 arg1。变量地址在一个 block 内按声明顺序从 0 开始递增每个变量对应一个栈槽过程声明不占栈槽只记录它将来在代码段中的入口地址。block 的解析同时负责声明和代码生成void block() { int oldLevel level; // 常量声明: const a 1, b 2; if (look.type TokenType.CONST) { next(); do { String name expectIdent(); expect(TokenType.EQ); int val expectNumber(); declareConst(name, val); } while (look.type TokenType.COMMA); expect(TokenType.SEMICOLON); } // 变量声明: var x, y, z; if (look.type TokenType.VAR) { next(); do { String name expectIdent(); declareVar(name); } while (look.type TokenType.COMMA); expect(TokenType.SEMICOLON); } // 过程声明: procedure p; ...; procedure q; ...; while (look.type TokenType.PROCEDURE) { next(); String name expectIdent(); expect(TokenType.SEMICOLON); level; block(); // 内层 block 使用 level1 做作用域 level--; expect(TokenType.SEMICOLON); declareProc(name, code.size()); } statement(); }这段代码的精髓在过程声明处先level再递归调用 block()出来后再level--。内层 block 里声明的所有变量、嵌套过程都会带着更大的 level 序号落进符号表而 process 返回后外层 statement 继续用原来的 level恰好完成了嵌套作用域切换。符号查找时自上而下逐层扫描自然实现了“内层遮蔽外层同名变量”的语义不需要额外做遮蔽链表。declareVar 的地址分配是另一个细节每声明一个变量就让 frameSize 加 1该变量的地址就是当前 frameSize 的值。这样 block 结束时 frameSize 正好是全部局部变量槽数后面 INT 指令的参数可以直接取这个值。3.3 表达式解析与 P-code 生成并行PL/0 的代码生成可以做成“解析过程即代码生成过程”不需要先建 AST 再二次遍历。原因在于 PL/0 没有类型转换运算优先级已经由文法嵌套天然决定factor 归约后立刻发一条指令即可。表达式文法采用三级嵌套expr 处理加减term 处理乘除factor 收束到常量、变量或括号。void expr() { term(); while (look.type TokenType.PLUS || look.type TokenType.MINUS) { Token op look; next(); term(); emitOp(op.type TokenType.PLUS ? OPR_ADD : OPR_SUB); } } void term() { factor(); while (look.type TokenType.TIMES || look.type TokenType.SLASH) { Token op look; next(); factor(); emitOp(op.type TokenType.TIMES ? OPR_MUL : OPR_DIV); } } void factor() { if (look.type TokenType.NUMBER) { emit(Instruction.LIT, 0, Integer.parseInt(look.value)); next(); } else if (look.type TokenType.IDENT) { Symbol s findSymbol(look.value); emit(Instruction.LOD, level - s.level, s.addr); next(); } else if (look.type TokenType.LPAREN) { next(); expr(); expect(TokenType.RPAREN); } }1 2 * 3的执行路径是expr 调 termterm 先 factor(1)遇到*后再 factor(2)、factor(3)于是生成的指令顺序是 LIT 1、LIT 2、LIT 3、OPR 乘法、OPR 加法。注意乘法指令先发出加法指令后发出P-code 在虚拟机里运行时自然会先算乘再算加优先级就这么被文法结构保证了。这里有个容易看走眼的点emit的时机在操作数之后、下一个循环判断之前。如果不小心把加减指令发在 term() 调用前生成结果就会变成反波兰的混乱状态虚拟机一跑就翻车。另一个常被忽略的点是常量折叠实验不需要做PL/0 的常量在 factor 里直接 LIT 即可折叠属于优化阶段的事在这里做反而会让后续扩展变难。4. P-code 虚拟机让生成的指令真正跑起来4.1 指令集与活动记录布局代码生成后的产物是一段 P-code 字节码PL/0 实验的标准机型是一台栈式虚拟机。指令最少 8 条LIT 加载常量OPR 做算术与比较LOD 读取变量STO 写入变量CAL 调用过程INT 开栈空间JMP 无条件跳转JPC 条件跳转。每条指令是op, arg1, arg2三元组语义各异。我一般把 P-code 的指令布局参数化成一张表方便查指令arg1arg2语义LIT0常量值压入常量LOD层级差变量偏移从指定帧读变量压栈STO层级差变量偏移栈顶写入指定变量INT0帧大小为局部变量分配栈空间OPR0子操作码算术/比较/返回CAL层级差过程入口调用过程JMP0目标地址无条件跳转JPC0目标地址栈顶为 0 时跳转OPR 的 arg2 是子功能表返回、取负、加减乘除、奇偶判断、大小比较共用一条大指令这是 Wirth 当年为了压缩教学代码长度做的设计今天我们依旧沿用因为实现简单、实验报告省事。活动记录布局才是虚拟机真正的难点。PL/0 的过程活动记录我采用三链帧frame[0] 返回地址 frame[1] 动态链指向调用者的旧 BP frame[2] 静态链指向声明该过程的作用域帧基址 frame[3..] 局部变量槽动态链用于返回时恢复调用者环境静态链用于访问外层的局部变量。嵌套层级差越大静态链要走的跳数越多这就是 base() 函数的来由。CAL 指令实际做的事情是当前指令指针压栈作为返回地址旧 BP 压栈作为动态链再沿静态链找到目标帧基址压栈然后 BP 指向新帧起点IP 跳到过程入口。4.2 VM 主循环取指、译码、执行虚拟机的实现比编译器主体更接地气核心就是一个 while 循环根据 ip 取指令、译码、执行。为保证可读性我会把指令先扁平化存进一个 int 数组每三个整数代表一条指令public class VirtualMachine { private int[] code; // 扁平化的 P-code 指令数组 private int[] stack; // 数据栈 private int ip, sp, bp; private int base(int level) { int b bp; for (int i 0; i level; i) b stack[b 2]; return b; } public void run() { while (ip code.length) { int op code[ip]; int arg1 code[ip 1]; int arg2 code[ip 2]; ip 3; switch (op) { case LIT - stack[sp] arg2; case INT - sp arg2; case LOD - stack[sp] stack[base(arg1) arg2]; case STO - stack[base(arg1) arg2] stack[sp--]; case JMP - ip arg2; case JPC - { if (stack[sp--] 0) ip arg2; } case CAL - { stack[sp] ip; // 压入返回地址 stack[sp] bp; // 压入动态链 stack[sp] base(arg1); // 压入静态链 bp sp - 2; ip arg2; } case OPR - handleOpr(arg2); } } } private void handleOpr(int sub) { if (sub OPR_RETURN) { sp bp; ip stack[bp]; bp stack[bp 1]; return; } int v stack[sp]; // 其余算术/比较分支在此展开 } }主循环的关键点有几个。第一LOD 和 STO 都要先通过 base(arg1) 算出目标帧基址再加上变量的 arg2 偏移帧内寻址就是一次数组访问。第二CAL 压入三个链点后BP 指向sp - 2此时 frame[2] 正好落在栈顶的三元组中间读取静态链的位置得以固定。第三OPR 的返回分支里sp bp是整帧回收把栈指针拉回当前帧起点再把返回地址和动态链分别弹给 ip 和 bp调用者环境即被恢复。这里最容易出错的是“过程调用无参数”这个前提。PL/0 经典教学写法里过程确实不声明参数变量共享全靠作用域所以返回时不需要清理参数槽。如果你扩展了带参过程活动记录布局要重新设计参数区要放在返回地址之前否则 sp 回收后参数残留会污染后续计算。4.3 运行期错误处理除零、栈溢出、未初始化课程实验的虚拟机拿数组当内存栈溢出往往表现为 ArrayIndexOutOfBoundsException这类异常信息对用户极不友好。我建议在 sp 的读写处加一层边界检查压下前判sp 1 stack.length超出则打印“栈溢出检查过程调用是否存在死循环”同时 dump 当前所有过程调用的返回地址链。除零错误则要在 OPR 的除法分支里显式判断 divisor 是否为 0。PL/0 的算子都跑在同一台 OPR 大指令下加一行判断成本极低但对运行期错误报告的完整性帮助很大。未初始化变量在经典 PL/0 语义里默认值是 0不会像现代语言那样报错如果实验有额外要求可以在 LOD 指令里加一个“是否写过”的位标记变量声明时全部清 0写指令置 1读指令检查未写则报运行时警告。这个选开后作用域和初始化的边界坑也能被覆盖到。运行期错误处理还有一条不要在 JMP/JPC 跳转前不校验目标地址。回填错误是编译阶段的高频 bug如果虚拟机对非法地址零容忍直接崩溃那排错时只能看到越界异常完全不知道自己错在代码生成的那一段这属于典型的“黑匣子”痛苦。5. 避坑与常见问题排查五个高频踩坑记录5.1 ODD 被当成普通标识符词法表漏词现象if odd(x) then ...被解析成“调用变量 odd”语法报错。原因保留字表里漏掉了 odd词法分析器把它判成了 IDENT语法分析沿标识符路径走后面跟的括号就完全没法解释。解决先在 KEYWORDS 里补上 odd确认 token 类型是 ODD。同时注意 odd 在语法上不属于 factor它应该出现在 condition 的入口生成 OPR_ODD 指令而不是普通函数调用。这类问题用 dump-tokens 一行就能定位比我当年靠肉眼扫代码快得多。5.2 begin end 空语句块报错分号消费顺序现象合法程序begin end.在 begin 处报“期望语句”或者begin a : 1 end报“期望分号”。原因statement 的复合语句解析写得过死进 begin 后无条件要求先出现一条语句或每条语句后都强制消费分号导致空块和末条无分号全部失败。解决把复合语句写成循环逻辑next()之后只要 look 不是 END 就解析一条 statement之后分号出现则消费并继续遇到 END 则退出。注意循环内不能先 expect 分号再判断结尾否则末尾那个分号会被错误消费。这个坑在多层 begin 嵌套时特别磨人建议手推三四个用例再运行。5.3 内层过程访问外层变量取到错值层级差算错现象外层声明var x内层过程里读 x结果拿到的是另一帧的垃圾数据。原因LOD 指令的 arg1 层级差计算错误。符号表查找按名返回内层同名符号但声明层级可能在外层level - sym.level才是正确差。如果直接用当前 level 或者用 0 代替base() 就找不到目标帧。解决给符号表加一个 debug 方法打印每个 Symbol 的 name/kind/level/addr再给指令 dump 打印 LOD 的 arg1。两端一对照就能发现是编译器发错层级差还是虚拟机 base() 跟随静态链的逻辑写错。这个坑从符号表到虚拟机跨了三个阶段属于最难靠猜的 bug 之一。5.4 跳转回填目标偏移一个指令JPC 回填时机现象while 循环只执行一次就退出或者 if 分支走了不该走的分支。原因生成 if/while 时先用占位 emit 一条 JPC等语句结束后用code.size()回填。如果回填时机写在 statement 内部某次 emit 之前目标地址就差了数条指令机器拿到的跳转点整个错位。解决把回填点存到局部变量例如int jpc emit(JPC, 0, 0)等解析完分支体后再backpatch(jpc, code.size())。同理while 的循环头地址要在条件表达式开头保存JMP 的返回目标再回填一次。我后来养成的习惯是每次生成跳转指令都顺手打印一行 P-code 当前偏移错误一眼可见。5.5 负数除法结果与预期不符整除语义没定义现象-7 / 2在有的机器上出 -3有的出 -4测试用例对不上。原因不同语言对整除的取整方向规定不同PL/0 教学定义没细写虚拟机实现里直接复制了宿主语言的除法语义。解决在虚拟机的 OPR_DIV 分支统一“向零取整”先判断符号再按绝对值除最后恢复符号。同时把这条语义写进实验报告说明实现策略。这个坑不算代码错误算是“语义规格缺失”但课程验收时最容易因为一个边界值被问倒提前定好策略能少很多麻烦。6. 把实验做出彩三个可落地的扩展与验证方法做到这里一个能跑 PL/0 的编译器已经成型但要让实验作业真正有区分度我会再补三件事。第一扩展 repeat-until 循环。语法上给 PL/0 加两条规则词法表补 repeat、until文法加一个方法即可。生成代码时要留意条件方向repeat-until 是条件为假时继续循环所以 until 后生成的是 JPC 跳回循环头而不是 JMP。多加这一条P-code 里的跳转手法就覆盖了“前测试”和“后测试”两种模式对指令回填的理解会更深一层。第二做标准 dump 输出。编译器加两个命令行开关--dump-tokens打印 Token 流--dump-code打印带偏移量的 P-code 表。调试时看着 dump 再对照虚拟机执行回填错位、符号表越界这些问题都是秒级定位。dump 输出示例长这样0: LIT 0 10 3: LOD 0 3 6: JPC 0 21 9: LIT 0 1 12: LOD 0 3 15: OPR 0 5第三做一组回归用例。不需要多十来个文件足够常量运算、变量遮蔽、过程嵌套、while、begin-end、除零、负数除法。每改一次虚拟机或符号表把这批用例全部跑一遍如果有用例结果变了说明改动影响到了基础语义。编译原理实验越到后期越容易“改一处坏一片”回归测试是成本最低的后悔药。我在做这门实验时吃过最大的亏就是跳过了 dump 调试用肉眼在几十条指令里数回填点结果 while 嵌套加上 begin-end 之后错乱了一下午。后来把 dump 和回归用例补齐同样的错误基本能在十分钟内定位。这个习惯我后来做真实工具链时也一直在用。希望这篇 PL/0 的落地笔记能帮到你。本文还有配套的精品资源点击获取
文法与四元式：IF-ELSE翻译程序的核心实现)
