PL/0运算符扩充实战：从词法分析到栈机解释的完整改造

简介面向编译原理课程设计的完整 PL/0 编译器修改扩充实现资料适合本科计算机专业学生在运算符扩展、语法分析、目标代码生成与课设答辩阶段使用。资源以运算符扩展为主线完成 、-、、-- 以及 FOR TO/DOWNTO 循环语句并实现一维数组类型字符、实数、有返回值和有参数函数等选做部分保持未完成状态便于对照题目要求理清已做与未做的技术边界。压缩包共 42 个文件约 1.25MB包含 7 个 PL0 源程序、6 个 COD 目标代码、CBuilder/Delphi 工程文件、测试程序与课程设计文档源码、可执行程序和测试用例齐全方便直接运行观察修改效果也适合按文件对应关系复盘词法、语法与代码生成扩展中的实现思路。bpl、obj、opt 等编译辅助文件可帮助梳理工程环境。已有 1052 人学习使用对 PL/0 教学编译器二次开发有较好的参考价值。1. 编译原理课程设计改 PL/0 的运算符才算真正摸到词法分析的调用链PL/0 是 Wirth 设计给教学用的迷你编译器词法、语法、代码生成、栈机解释四段齐全代码量又小编译原理课程设计十有八九拿它当底子。最常见的题目就是「对 PL/0 作出修改扩充」而扩充里最常被选中的是运算符原版只有 - * / 和几个关系符取模、逻辑与或、复合赋值、自增自减都得自己加。别看只是多了几个符号它会牵动符号表、EBNF 产生式、P-code 指令和栈机解释器四处改完这一轮才算真正理解词法分析到语义子程序的调用链。这篇把我拆过的一份运算符扩充资源从头讲透每处改动落在哪个函数、优先级怎么排、测试怎么验、哪里最容易翻车。适合正在做课程设计的学生也适合带实验课要快速评估方案的助教。2. PL/0 原始骨架拆解词法、语法、语义、栈机四段调用链2.1 单遍编译器的四段结构从 getsym 到 interpret 的主循环PL/0 是单遍编译器读一个符号、分析一个结构、当场生成目标代码不回头。主线就几条函数我按 C 工程最常见的写法拆int main(void) { init(); // 清符号表、清指令区、初始化保留字 getsym(); // 预读第一个符号sym 里就是首个 token block(0, tx, lev); // 从主程序的 block 开始递归下降 if (sym ! PERIOD) // 结尾必须是 . error(5); gen(OPR, 0, 0); // 主程序收尾生成 return 指令 interpret(); // 栈机逐条执行 code 数组里的 P-code return 0; }逻辑说明getsym 是词法分析入口每次调用把字符流里拼出一个 token 放进全局 symblock 是语法分析的主结构负责声明和语句内部递归调用 statement → expression → term → factorgen 把一条 P-code 追加进 code 数组它是全工程唯一的代码生成出口interpret 最后用栈机解释执行。整个过程不生成中间代码文件表达式一边分析一边发指令所以叫单遍。参数说明lev 是当前过程嵌套层tx 是符号表指针都以指针传参block 返回时会清掉本层符号表项。block 开头会生成一条 JMP 占位等函数体分析完再回填跳转地址这是 PL/0 标准做法你手里的版本可能是把回填放在 block 尾部不影响后文。原版指令集是理解改动的关键先列一张表指令含义操作数说明LIT 0 a常量 a 压栈a 是立即数LOD l a把第 l 层偏移 a 的变量压栈l 是静态层a 是偏移STO l a弹栈写入第 l 层偏移 a 的变量与 LOD 同寻址CAL l a调用第 l 层地址 a 的过程a 是过程入口INT 0 a栈顶指针加 a分配栈帧局部变量区JMP 0 a无条件跳到 a控制流JPC 0 a弹栈为 0 则跳到 a条件跳转OPR 0 op栈顶算术/逻辑运算op 是子功能号OPR 的子功能号原版只编到 130 返回、1 取负、2 加、3 减、4 乘、5 除、6 判奇数、8 相等、9 不等、10 小于、11 小于等于、12 大于、13 大于等于。注意 7 空着。这个表记熟后面扩运算符就是在 op 号 14 往后自己定义。我一般建议课程设计选运算符而不是数组或函数理由是改动面最收敛词法、语法、代码生成三处是增量修改解释器只新增几个 case 分支不碰符号表和寻址体系但优先级文法、短路求值、左右值这几个编译原理考点全都能踩到性价比最高。2.2 符号表与静态链寻址改运算符之前要读懂的第二个黑匣子符号表存名字和它的编译期属性。PL/0 的符号项通常长这样#define AL 10 // 标识符长度上限 #define TXMAX 100 // 符号表容量 struct symbol { char name[AL]; int kind; // 0 常量1 变量2 过程 int level; // 所在层 int addr; // 常量值或变量偏移 } table[TXMAX];逻辑说明block 每遇到一个声明就填一项标识符引用按名字线性查表。运算符扩充里取模和逻辑与或不需要动符号表操作数在栈上OPR 弹进弹出即可但自增和复合赋值要按名字回写变量必须用查表拿到的 level 和 addr 生成 LOD/STO符号表查错了这里就全乱。栈机寻址是另一处容易踩坑的地方PL/0 用静态链而非动态链回溯int base(int l) { int b 1; while (l-- 0) // 沿静态链往上找第 l 层的过程基地址 b stack[b 1]; return b; }逻辑说明每次过程调用栈帧里依次放静态链、动态链、返回地址然后才是局部变量区。LOD l a 执行时先取 base(l)再取 base(l)a 就是变量地址。l 是定义层不是当前调用层很多学生在这里迷糊。改运算符时记住一条规则就够LOD/STO 里的 l 来自符号表里查到的 level不是当前 lev。查表用线性查找就行课程设计的规模不值得上哈希。还有一个前置认知原版的条件语句要求condition :: expression(关系符)expression关系运算的结果只活在 condition 里。一旦要给 IF 条件写(a b) (b 3)就得把关系比较挪进表达式层让比较结果变成 0/1 压栈再供 和 || 组合。这一步不做逻辑运算符在条件里根本落不了地。3. 运算符扩充全链路从 token 枚举到 OPR 子功能号的四层改造3.1 词法层从单字符加号到 、、 的多字符识别词法改动是所有扩充的起点。原版 getsym 里加号就是一个case : sym plus; return;要支持 和 必须向前看一个字符case : getch(); // 先吃进下一个字符 if (ch ) { getch(); // 再吃一个保持预读状态 sym INC; // 自增运算符 return; } if (ch ) { getch(); sym PLUSASSIGN; // 复合赋值 return; } sym PLUS; // 普通加号 return;逻辑说明getsym 的契约是「调用结束时ch 里是当前符号之后的下一个字符」。识别到双字符运算符时第二个字符也要被消费并且必须再 getch 一次让 ch 指向更后面的字符。少一次 getch代价就是下个符号的首字符丢失这是后面避坑章里第一个翻车点。参数说明token 枚举要同步加。我在工程里把 sym 定成枚举enum symbol { nul, ident, number, plus, minus, times, slash, percent, // 算术percent 是新增 eql, neq, lss, leq, gtr, geq, // 原版 # 表示不等 andsym, orsym, notsym, // 新增逻辑运算符 inc, dec, plusassign, // 新增自增/复合赋值 lparen, rparen, comma, semicolon, period, becomes, beginsym, endsym, ifsym, thensym, whilesym, dosym, callsym, constsym, varsym, procsym };逻辑说明枚举顺序无所谓但每新增一个就必须全工程重新编译别改漏。% 放在乘除后面因为文法里它跟乘除同层 和 || 会放进下面的 andexpr 和 orexpr 层。原版用 # 表示不等于这是 Wirth 的记号习惯课程设计里保留 # 属于保守改法不扣分但要在报告里说明设计选择。3.2 语法层优先级文法怎么改成 C 风格的四层递归原版表达式文法只有两层expression :: [ | - ] term { ( | - ) term } term :: factor { ( * | / ) factor } factor :: ident | number | ( expression )逻辑说明这个文法没有 和 || 的位置而且条件里的关系比较是独立在 expression 之外的。要扩逻辑运算符优先级必须重新排。我一般按 C 的表达习惯拆成几层从低到高|| → → 关系比较 → 加减 → 乘除取模单目 ! 和 /-- 放最高层expression :: orexpr orexpr :: andexpr { ( || ) andexpr } andexpr :: rel_expr { ( ) rel_expr } rel_expr :: additive [ ( | # | | | | ) additive ] additive :: term { ( | - ) term } term :: unary { ( * | / | % ) unary } unary :: [ | - | ! ] unary | factor factor :: ident | number | ( expression ) | ident | ident对应到递归下降每一层只消化自己的运算符集合void expression(void) { // orexpr 层 andexpr(); while (sym ORSYM) { getsym(); andexpr(); gen(OPR, 0, 16); // 逻辑或 } } void andexpr(void) { // andexpr 层 rel_expr(); while (sym ANDSYM) { getsym(); rel_expr(); gen(OPR, 0, 15); // 逻辑与 } } void rel_expr(void) { // 关系比较层结果为 0/1 additive(); if (sym EQL || sym NEQ || sym LSS || sym LEQ || sym GTR || sym GEQ) { int op sym; getsym(); additive(); switch (op) { case EQL: gen(OPR, 0, 8); break; case NEQ: gen(OPR, 0, 9); break; case LSS: gen(OPR, 0, 10); break; case LEQ: gen(OPR, 0, 11); break; case GTR: gen(OPR, 0, 12); break; case GEQ: gen(OPR, 0, 13); break; } } } void additive(void) { // 加减层 term(); while (sym PLUS || sym MINUS) { int op sym; // 先存运算符getsym 后 sym 就变了 getsym(); term(); gen(OPR, 0, op PLUS ? 2 : 3); } } void term(void) { // 乘除取模层 unary(); while (sym TIMES || sym SLASH || sym PERCENT) { int op sym; getsym(); unary(); gen(OPR, 0, op TIMES ? 4 : (op SLASH ? 5 : 14)); } } void unary(void) { // 单目层 if (sym PLUS) { // 一元正语义上是空操作 getsym(); unary(); } else if (sym MINUS) { getsym(); unary(); gen(OPR, 0, 1); // 取负 } else if (sym NOTSYM) { getsym(); unary(); gen(OPR, 0, 17); // 逻辑非 } else { factor(); } }逻辑说明每层函数只在命中自己的运算符时才发一条 OPR优先级靠「谁先被调用」保证orexpr 最晚生成指令运行时反而最内层的因子先算。初学最容易搞反的是这里——文法里越靠后的产生式运行时优先级越高。另外int op sym这一行不能省getsym 之后 sym 已经变成下一个 token 了拿不到刚才那个运算符。参数说明%固定在 term 层跟 * / 平级a % b * c从左到右结合符合 C 习惯。如果想做成取模比乘除低就得单独拆一层不建议放到 additive 层会让-7 % 3的语义很难解释。关系比较从 condition 里挪进 rel_expr 后IF/WHILE 的条件文法可以直接改成condition :: expression解释时栈顶非零即真这一步在 block 的 if 分支里只改几行。3.3 语义与代码生成OPR 子功能号 14 到 17 怎么下发和解释语法层 gen 发出的指令最终落在 interpret 的 switch 里执行。以取模为例a % b在 term 层先递归算左操作数、再算右操作数两个结果都在栈上然后 OPR 14 弹两个数算余数case 14: // 取模 b stack[top--]; a stack[top]; if (b 0) { // 模零直接报错别硬算 printf(error: 取模除零\n); return; } stack[top] a % b; break; case 15: // b stack[top--]; a stack[top]; stack[top] (a ! 0 b ! 0) ? 1 : 0; break; case 16: // || b stack[top--]; a stack[top]; stack[top] (a ! 0 || b ! 0) ? 1 : 0; break; case 17: // ! stack[top] (stack[top] 0) ? 1 : 0; break;逻辑说明栈机里所有双目运算都是「先压左、再压右」OPR 弹出时先拿到的 b 是右操作数a 才是左操作数。加减乘除原版就是这么写的取模想当然按 a pop、b pop 写结果就是全错而且只错在部分用例上特别隐蔽。逻辑与或我把结果归一成 0/1这样 condition 的「非零即真」可以直接复用。参数说明这个实现是全求值不短路。a b即使 a 为 0 也会算 b所以(k ! 0) (10 / k 2)会先除零报错。要短路得在语法层生成 JPC/JMP 指令对属于加分项设计文档里要主动写清楚你选的是全求值还是短路。复合赋值 的生成在 statement 层做。解析到 ident 后面跟的是 PLUSASSIGN 时不能像普通赋值那样直接expression(); gen(STO...)顺序反了就错// 处理 i e等价于 i : i e sym get_ident(); // 读 id查符号表拿 level 和 addr getsym(); // 越过 gen(LOD, i.level, i.addr);// 先把 i 原值压栈 expression(); // 再算 e栈顶是 e 的值 gen(OPR, 0, 2); // 弹出相加结果压栈 gen(STO, i.level, i.addr);// 弹栈写回 i逻辑说明先压原值、再压右值、ADD 弹两个数把和压回、STO 弹栈写变量。如果先算 expression 再 LOD执行顺序就变成「先算右边、再临时取 i」取到的 i 是哪一刻的值全看运气这种错在单侧里很隐蔽边界用例才炸出来。3.4 编译驱动与测试样例一条命令看到改动效果四层串起来给一份能跑通的扩充版 PL/0 程序VAR a, b, c; BEGIN a : 10; b : 3; c : a % b; { c 1 } IF (a b) (b 3) THEN a : a b; { a 13 } a 5; { a 18 } b : 2; IF (a % 2 1) || (b 2) THEN b : 99; { 左边假右边真b 99 } END.编译运行gcc -o pl0 main.c lex.c syn.c codegen.c interp.c ./pl0 test.pas逻辑说明工程按模块拆时词法、语法、生成、解释各一个文件符号表需要跨文件共享最省事是照原版单文件结构往里面加函数调试通过再拆开。参数说明我建议 interpret 结束前把非过程变量的最终值全打出来课程设计报告贴这张表最直观。对照期望值c1、a18、b99全对说明词法、文法、解释器三处联动没问题。4. 常见避坑PL/0 扩充运算符最容易翻车的五个细节4.1 现象1 2 3 1结果不对逻辑与好像没生效原因把 直接写进 expression 的 while 里等于把 || 和 都并进了加减层。栈机上先算123再算311最后 拿 3 和 1 当操作数结果碰巧也是 1但换一组数就露馅。这是文法层没有按优先级拆层的典型症状。解决按 3.2 的四层文法重排。检验方法很直接把 code 数组的指令序列打出来1 2 3 1应该先出现关系比较的 OPR 8/9再出现 OPR 15顺序反了就是优先级层没建对。我每次改完都先看指令序列再看执行结果两步都对了才往下走。4.2 现象a b编译到 b 时报「未定义标识符」但单独写b又没问题原因词法层 case 里读到第一个 后 getch 到第二个 直接返回 ANDSYM没再 getch 一次。b 的首字符被留在 ch 里当成已消费下一次 getsym 从错误位置开始拼 token。解决双字符运算符识别完必须再 getch 一次补回预读。检查规则就一条getsym 的每个分支 return 前ch 都必须指向下一个未消费字符这是词法分析器的不变量。改完词法把这个规则当成 check 清单过一遍单字符、双字符、保留字三个分支分别验证。4.3 现象(-7) % 3结果一会是 1 一会是 -1模零还直接崩原因不同语言对余数符号的定义不同C 和 Python 就不一致原版除法的 OPR 5 没有零检查取模照抄就崩。解决interpret 里 OPR 14 先判 b 0 报错返回别让 invalid 值流到后面的指令。结果符号按被除数决定C/Java 风格a % b的符号跟 a 走这点要在代码注释和报告里写明约定评审老师必问。4.4 现象x : i执行完 x 和 i 都是新值后缀自增丢了旧值原因factor 里把 简单翻成 LOD、LIT 1、ADD、STO后缀语义要求先把旧值保存再自增。栈机没有 DUP 指令没临时变量就丢值。解决最省事是文法只支持前缀 ident不给后缀。要支持后缀在符号表里预留一个临时变量 tmp生成四段指令// 后缀 i 的指令序列tmp 是预留的临时变量 gen(LOD, l, a); // 旧值压栈 gen(STO, 0, tmp); // 旧值暂存 tmp gen(LOD, l, a); // 再取一次 i gen(LIT, 0, 1); gen(OPR, 0, 2); // i 1 gen(STO, l, a); // 写回 i gen(LOD, 0, tmp); // 旧值压栈作为表达式结果逻辑说明重点在最后一条 LOD它把暂存的旧值再压回栈这样x : i的 x 拿到旧值、i 变成新值。如果想支持i i这种连续副作用两个 会抢同一个 tmp必须约定求值顺序或改成栈上倒腾课程设计里通常直接禁掉连续自增。4.5 现象输入非法字符比如单个 后错误刷屏程序不退出原因getsym 的 default 分支只报错不消费字符主循环 getsym → block → statement → getsym 原地打转。解决缺省分支必须 getch() 推进再返回并且错误码表要预留一个「非法字符」码。任何非法情形都要让输入前进词法分析器永不回头这是死循环的唯一解药。我一般在 default 里写error(23); getch(); return;报错一次就往前走一个字符。5. 验证与边界参数指令序列、栈深与回归测试方案5.1 回归测试原始样例跑绿再验新特性改词法最怕「新功能好了旧功能坏了」。我一般把原版自带的素数样例、阶乘样例和新增运算符样例一起放进 tests/ 目录写个两行脚本批量跑mkdir -p out for f in tests/*.pl0; do ./pl0 $f out/$(basename $f).log 21 if grep -q 正常结束 out/$(basename $f).log; then echo PASS $f else echo FAIL $f - out/$(basename $f).log fi done逻辑说明interpret 结束时打印「正常结束」和最终变量表脚本按关键字判定。原始样例全部 PASS 再测新样例能快速定位改动是不是波及了 LOD/STO 寻址。变量表打印只输出 kind 1 的变量过程项的 addr 是入口地址不是偏移一起打印会误导排错。光跑结果还不够抽查指令序列更早暴露问题。给a % b c加一行调试输出期望序列是LOD 0 0 ; a LOD 0 1 ; b OPR 0 14 ; a % b LOD 0 2 ; c OPR 0 15 ; (a%b) c逻辑说明任何一次逻辑组合层的改动都先看这一条序列对不对再谈执行结果。序列错但碰巧结果对的概率不低只看结果容易把 bug 带进最终版。5.2 边界参数指令号、栈深、标识符长度怎么配宏/常量原版典型值扩充后建议值说明STACKSIZE5001024 或 2048递归深了栈溢出现象是变量值变乱TXMAX100200符号表满会报「符号表溢出」AL1010 或 16标识符长度上限运算符不受影响NMAX1414数字位数一般不用动OPR 子功能号规划0-13 原版已占用14 取模、15 与、16 或、17 非后面还想扩移位 接着 18、19 往下排。别复用 7原版留空给 undefined不同版本可能拿它当特殊错误码重名了就是玄学报错。边界用例用一张表列清楚跑一遍比口头验收硬气得多用例期望结果验证点a % 0报错不崩溃零检查(1) (0)0逻辑真值表! ! (a 0)0双重否定a a文档约定或报错副作用顺序a 3 * 2a 加 6复合赋值与表达式嵌套6. 从运算符到数组与函数一条可复用的扩充路线图6.1 数组把 LOD/STO 的偏移从常量改成表达式数组是运算符之后最常见的第二个扩充点。factor 里加一条ident [ expression ]难点不在语法在寻址——栈机没有变址寻址。常见做法是给栈机加两条指令LDA 把变量基址压栈再用一条 OPR 子功能把「基址 下标」算成元素地址。写代码时你只需要记住第 3 章反复强调的那条纪律先压下标、再压基址和「先压左操作数」是同一个习惯。语法层的修改跟运算符那轮几乎一样照着 rel_expr 的模板改 factor 就行。6.2 函数调用参数压栈顺序与栈帧分配函数/过程在本底子上本来就有 CAL 和 INT加参数只是在调用点把实参依次压栈被调过程用 INT 分配局部区。压参顺序必须和 block 的声明顺序一致否则取参数的位置全错。你可以把运算符扩充时养成的「先画指令序列再写代码」习惯直接用在这里先手写push arg1; push arg2; CAL; INT再对着 gen 输出逐条核对比闷头调试快得多。我自己的教训是第一次做 PL/0 扩充时我直接动手改 getsym改完才发现语法层三个函数的调用顺序没对齐优先级错得一塌糊涂debug 花了两个晚上。从那以后我每次做课程设计扩充都强制自己先写一份「最小样例 期望指令序列」的清单再动任何一行代码改完词法先跑旧样例再跑新样例全绿才继续往下做。这套流程放在任何扩充需求上都管用希望帮到你。本文还有配套的精品资源点击获取