PL/0 编译器加 ELSE 实验：保留字、递归下降与跳转回填避坑

简介面向学习编译原理、需要完成PL/0教学编译程序改造实验的高校学生。资料围绕词法分析、语法分析与语义处理的修改扩充展开涉及新增ELSE、FOR、TO、DOWNTO、RETURN等保留字及、-、、--运算符将不等号#改为并实现条件语句的ELSE子句词法部分需补充符号识别语法部分需加入ELSE分支产生式语义部分则要同步调整条件跳转与代码生成适合对照实验要求理解PL/0的编译流程。压缩包共24个文件约644KB包含cpp与h源码、doc实验报告、dsp/dsw工程文件、exe可执行文件以及pdb、obj、ilk等调试与中间文件另有txt说明和测试代码便于查看工程组织、运行结果与报告结构。已有791人学习可参考现成源码、实验报告和工程配置梳理保留字扩充、运算符替换及ELSE子句改造的实现思路用于实验复现、结果核对与排错。1. 从一份 PL/0 实验包说起加 ELSE 为什么容易翻车编译原理实验里最容易被低估的一步是在 PL/0 的词法和语法里加保留字、补上 ELSE 语句。很多人以为照书上的框图改几行就能收工真跑起来才发现保留字表少一项所有带 else 的程序直接报“应为 then”跳转地址回填错一格程序就在 P-code 里原地打转。这类实验包围绕的正是这条主线——在 PL/0 的递归下降编译器上把 else 从一个普通标识符变成真正的保留字再让它落到语法结构和目标代码里。适合正在做编译原理课程设计、需要交付可运行源码和测试用例的人也适合已经跑通原始版本、想弄清回填和悬空 else 细节的人。下面按模块拆每一步都给出可复现的改动位置和验证方法。2. 拆开实验包从源程序到 P-code 的五个模块2.1 编译链路与各模块的职责边界PL/0 编译器是一个很典型的单遍递归下降实现源程序按字符读入词法分析器每次产出一个sym和附加信息标识符名id、数值num语法分析器边读边判断、边调用代码生成函数gen往code[]数组里写指令最后解释器interpret逐条执行这个数组。整个过程没有中间表示文件也没有独立的优化阶段所以任何一处改动都会立刻体现在运行结果上这也是它适合做实验的原因。各模块的职责和改动影响面可以对照下表。注意符号表模块在加 else 时基本不需要动但如果你顺手改了枚举顺序符号表里存的下标含义不会变变的只是调试输出里那些整数值这一点后面会展开。模块关键函数输入输出加 else 是否要动词法分析getsym字符流sym、id、num要加保留字映射语法分析block/statementsym序列调用gen要加 if-else 产生式符号表enter/position标识符表项下标一般不动代码生成gen指令三元组code[]不新增指令只加回填解释执行interpretcode[]运行输出多数实现不用改这里先给一个结论ELSE 语句的扩展用到的是已有的jpc和jmp两条指令不需要给虚拟机加新操作码。很多同学在解释器里翻半天找不到要加什么方向就偏了。真正需要动的是词法表、语句解析分支以及跳转地址的回填逻辑。2.2 保留字表与 sym 枚举的对应关系词法分析识别标识符之后会拿它去保留字表里比对。经典实现是两张平行数组一张存字符串一张存对应的符号枚举值两边的下标必须严格一一对应。原版通常有 13 个保留字加 else 之后变成 14 个这个数字在代码里往往是一个叫norw的常量。它的作用是控制比对循环的边界改漏了就会出现“else 明明在表里却永远匹配不上”的情况。/* 保留字字符串表顺序必须与下面的枚举数组一一对应 */ char *word[] {begin, call, const, do, end, if, odd, procedure, read, then, var, while, write, else}; /* 与 word[] 同下标的符号枚举elsesym 追加在末尾 */ enum symbol wsym[] {beginsym, callsym, constsym, dosym, endsym, ifsym, oddsym, procsym, readsym, thensym, varsym, whilesym, writesym, elsesym}; /* 保留字个数不要手写 14用 sizeof 算少踩一次改漏的坑 */ int norw sizeof(word) / sizeof(word[0]);这段代码的逻辑很直白word[i]和wsym[i]描述同一个保留字norw决定循环走多远。参数上唯一需要注意的是数组长度必须一致如果只往word[]里加了else却忘了往wsym[]里加elsesym编译能过C 语言不检查数组长度一致性但运行到第 14 个保留字时读到的是越界或者别的枚举值症状非常隐蔽。用sizeof计算norw的好处是以后再加repeat、until之类的保留字时只改两张表即可。2.3 先把原始版本跑通并留一份基准动手改之前必须先让原始版本编译通过、跑出稳定输出并把输出存成对照基准。这个步骤看着笨但它是后面所有排查的地基一旦加了 else 之后某个老用例行为变了你才能立刻判断是改动引入的回归还是原来就有的问题。常见的编译命令就是普通 C 编译带上调试符号方便定位。# 编译原始版本保留调试符号 gcc -O0 -g pl0.c -o pl0_base # 用一个最小程序验证基线 cat demo.pl0 EOF var x; begin x : 1; if x 0 then write(x) end. EOF # 把 P-code 列表和运行输出都存成基准文件 ./pl0_base demo.pl0 golden/demo.pcode 21 ./pl0_base demo.pl0 | tail -n 5 golden/demo.run这里的参数说明只有两点-O0是为了让调试器单步时变量不被优化掉-g是为了后面能在gen和interpret里下断点。至于输出不同实现可能先打印一张 P-code 指令表再解释执行也可能直接执行所以golden目录里两段输出都要留。后面每改一步都拿新输出和这两份基准 diff 一次能省掉大量“到底哪一步改坏了”的排查时间。注意基准文件不要只留最终运行结果。带 else 的改动最先影响的是指令序列P-code 列表能更早暴露回填地址的错误运行结果反而可能因为程序恰好没走到错误分支而看起来正常。3. 词法层加一个保留字else 到 elsesym 的四处联动3.1 枚举值的插入位置会带来什么连锁反应给enum symbol加elsesym时最省事的做法是追加在末尾而不是插在ifsym后面。原因是枚举值在 C 里就是整数任何插在中间的做法都会让它后面所有符号的整数值整体加一。如果你的测试脚本或调试输出里曾经按数字比对过sym比如期望第 24 号是thensym插入之后全部错位看起来就像“词法分析坏了”实际只是编号变了。enum symbol { nul, ident, number, plus, minus, times, slash, oddsym, eql, neq, lss, leq, gtr, geq, lparen, rparen, comma, semicolon, period, becomes, beginsym, endsym, ifsym, thensym, whilesym, writesym, readsym, dosym, callsym, constsym, varsym, procsym, elsesym /* 追加在末尾已有符号的整数值保持不变 */ };从工程角度看追加在末尾是一种向后兼容的改法已有代码里凡是写死数字的地方都不受影响新增的elsesym只是多了一个取值。代价是枚举顺序不再和语法书上的书写顺序一致可读性略差但实验代码里这个代价可以接受。真要追求顺序整齐就得同步改掉所有按数字比对的地方工作量远大于收益。另一个容易被忽略的点是elsesym的命名。如果原代码里已经有elssym或者else_sym之类拼写不同的符号直接搜一遍再动手避免重复定义。这类实验包往往被多届学生改过留有各种历史补丁动手前花五分钟通读枚举和保留字表比改到一半发现冲突要划算。3.2 getsym 的匹配方式与前缀陷阱保留字识别的核心逻辑在getsym的标识符分支里连续读入字母数字拼成字符串放进id然后拿它去word[]里线性查找。找到就赋对应枚举值找不到就是普通标识符。这段代码的关键在于比较方式必须是全等比较strcmp返回 0 才算命中。/* 标识符或保留字的识别分支 */ if (ch a ch z) { int k 0; do { if (k al) { a[k] ch; k; } /* al 为标识符最大长度 */ getch(); } while ((ch a ch z) || (ch 0 ch 9)); a[k] \0; strcpy(id, a); int i 0; while (i norw strcmp(id, word[i]) ! 0) i; sym (i norw) ? wsym[i] : ident; /* 全等命中才是保留字 */ }参数al是标识符长度上限常见取值是 10超长部分直接截断丢弃但不报错。这个截断逻辑和保留字加 else 之间有一个隐蔽的耦合如果有人为了省事把al调小到 4那么合法的变量名elsex会被截成else在词法层直接变成保留字后面语法分析报出一堆莫名其妙的错误。我见过把这个问题归咎于“编译器玄学”的其实只是长度上限设得太小。前缀比较是另一个重灾区。有人觉得线性strcmp慢改成逐字符比较或者按首字母分组结果end和else、if和ident之间互相干扰。最典型的是手写一串if链先判断首字符是不是e再判断第二个字符是不是n写漏一个分支就出现else被识别成endsym。保留字只有十来个线性全等比较完全够用没有必要优化。3.3 用最小用例定位词法层问题改完词法之后不要急着跑完整程序先拿三个最小用例确认sym的产出是否正确。最直接的办法是加一个编译期开关把每次getsym的结果打印出来只在调试版本里生效。#ifdef LEX_DEBUG /* 词法调试输出打印符号编号、标识符名和当前字符 */ printf(sym%2d id%-12s num%d ch%c\n, sym, id, num, ch); #endif编译时加-DLEX_DEBUG打开开关gcc -DLEX_DEBUG pl0.c -o pl0_dbg。然后分别输入只包含else、end、elsex的三段文本看输出里sym是否分别是elsesym的整数值、endsym的整数值、ident的整数值。三个都能对上词法层的改动才算闭合。第三个用例elsex是专门用来验证全等比较的它既不是保留字也不能被前缀匹配误判。如果这一步就错了说明匹配方式有问题此时不要去调语法分析先把词法改对。顺序反过来做会在语法层看到一堆连锁报错排查成本翻倍。注意调试输出不要留在最终提交的版本里。用一个宏包起来是底线否则打印语句本身会拖慢解释执行还可能让输出的 P-code 列表和基准对不上。4. 递归下降里的 if-elsestatement 改造与 cx1/cx2 回填4.1 statement 中 if 分支的完整改造PL/0 的statement函数负责所有语句的解析if 语句原来只处理then之后的一条语句。加 else 的改动集中在两处解析完 then 分支后检查当前符号是不是elsesym以及生成并回填两条跳转指令。jpc的语义是“栈顶为 0 时跳转”所以它要放在条件求值之后、then 分支之前地址先填 0等 else 位置确定再回填。/* statement 内部的 if 分支cx1/cx2 必须是局部变量 */ if (sym ifsym) { getsym(); condition(fsys, ptx); /* 生成条件求值代码结果压栈 */ if (sym thensym) getsym(); else error(16); cx1 cx; gen(jpc, 0, 0); /* 条件为假 - 待回填到 else 或 if 之后 */ statement(fsys, ptx, lev); /* then 分支体 */ if (sym elsesym) { getsym(); cx2 cx; gen(jmp, 0, 0); /* then 分支执行完跳过 else */ code[cx1].a cx; /* 假分支落到 else 体第一条 */ statement(fsys, ptx, lev); /* else 分支体 */ code[cx2].a cx; /* then 分支跳到 else 体之后 */ } else { code[cx1].a cx; /* 没有 else假分支直接落到 if 之后 */ } }逻辑上分三种情况有 else 时条件为假跳到 else 体起点then 体结束后无条件跳过 else 体没有 else 时条件为假直接跳到整个 if 语句之后。参数上要盯住code[cx1].a和code[cx2].a这两个回填动作它们写入的是code[]数组的下标不是行号也不是字节偏移。写错一格的表现是程序能编译、能启动但执行到 if 附近就跳飞。还要确认condition函数内部是不是已经生成过jpc。有些实现把条件跳转放在condition里做外面只需要回填有些实现只生成比较指令由调用方生成jpc。两种写法不能混混了就会出现“条件被判断两次”或者“栈上多压了一个值”的问题。动手前先读一遍condition的结尾看它最后一条指令是什么。4.2 全局 cx1/cx2 在嵌套 if 下的真实故障原始 PL/0 代码里cx1和cx2常常是文件作用域的全局变量因为while语句的回填也用它俩。单层 if 或者单层 while 时没问题一旦出现嵌套内层语句在解析过程中会覆盖外层的cx1等内层返回、外层再去回填时读到的是内层的地址。这个 bug 的典型表现是两层嵌套能跑三层开始随机出错输出结果和源码逻辑完全对不上。/* 错误写法全局变量嵌套时被内层覆盖 */ int cx1, cx2; /* 正确写法在 statement 函数开头声明为局部变量 */ static void statement(int *fsys, int *ptx, int lev) { int cx1, cx2; /* 每次进入 statement 都是独立的一份 */ /* ... */ }改成局部变量之后每层statement调用都有自己的回填槽位嵌套多深都不会互相踩。这个改动很小但它是 if-else 扩展里最值得强调的一处因为原始教材代码通常不覆盖嵌套场景照着抄就会留下隐患。同理如果while的回填也用了全局变量建议一并改成局部避免 else 和 while 混用时再出一次问题。4.3 解释器不用加指令但要确认地址口径if-else 生成的四段结构可以用一张表看清楚。假设 then 体的指令从cx11开始else 体从某个地址 L 开始if 结束在 M那么指令序列就是下面这样。回填的时机很关键jpc的目标地址要等 else 起点确定后才能写jmp的目标地址要等 else 体解析完才能写。位置指令a 字段含义回填时机cx1jpcelse 体首地址无 else 时为 if 之后解析完 then 体后cx11 起then 体正常语句序列不需要cx2jmpif 之后的地址解析完 else 体后L 起else 体正常语句序列不需要解释器这边要做的不是加指令而是核对jpc和jmp对a字段的解释方式。有的实现是“取指前先把 pc 加一跳转时直接赋i a”有的是“跳转时赋i a - 1再靠循环自增补回来”。两种写法都对但和回填值必须配套。判断方法很简单写一个只含jmp的最小程序单步进去看跳转后的下一条指令是不是code[a]不是就差一格。/* 解释器中两条相关指令的典型写法注意与回填口径配套 */ case jmp: i code[i].a; /* 直接跳到目标下标 */ break; case jpc: if (s[--t] 0) i code[i].a; /* 弹栈为 0 才跳 */ break;上面这段里s[--t]把“弹栈”和“取栈顶”合成了一步如果你的实现风格是先读s[t-1]再t--语义一样别混着改。至于jpc跳转之后i要不要再减一完全取决于主循环的取指顺序这一点没有统一标准必须对着自己手上的解释器看。我一般会在回填之后打印一遍code[]把每个跳转指令的目标地址和实际指令对照着看一遍比在脑子里推演可靠。5. 避坑清单五类报错与它们的真实原因5.1 所有带 else 的程序都报“应为 then”现象很统一只要源程序里出现 else编译阶段就报 16 号错误应为 then一个都不例外。原因通常有三个word[]里加了else但wsym[]没加elsesymnorw还是 13循环根本没走到第 14 项或者两张表的顺序错位else对应到了别的枚举值。这三种情况的共同点是词法层没能把 else 识别成保留字语法层看到的是一个普通标识符自然认为 then 分支该结束的地方出现了非法符号。解决办法是按表逐项核对并且把norw改成用sizeof计算。核对时不要只看代码跑一遍 3.3 节的调试输出确认sym的值确实是elsesym。如果调试输出显示识别正确但语法层仍报错那问题就不在词法去看statement里判断elsesym的位置是不是写在了statement递归调用之前。5.2 老用例突然大面积失败现象是加完 else 之后原本跑得好好的十几个测试程序集体出问题有的报标识符未定义有的运行结果全变。原因主要有两类一是elsesym插在了枚举中间导致后面所有符号的整数值偏移测试脚本如果按数字比对符号就全错二是老测试程序里恰好有变量名叫else或者以 else 开头的短标识符加保留字之后被词法层截胡。解决方式是双管齐下枚举值一律追加在末尾同时对全部测试程序做一次全文检索把else作为标识符使用的地方改名。第二点听起来离谱但在多届学生共用一套用例的实验环境里很常见有人图省事用e、el、els当变量名离保留字只有一步之遥。检索完再跑一遍基准对比能快速区分“真回归”和“用例本身要改”。5.3 嵌套三层后跳转错乱甚至死循环现象是两层 if 嵌套还能出正确结果嵌套到三层以上就开始乱跳严重时程序不结束。原因基本可以锁定为cx1/cx2是全局变量外层 if 生成的jpc地址还没回填内层 if 解析时把cx1覆盖成了自己的值外层回填时写进了一个内层地址。由于地址落在 then 体内部执行流会在两段代码之间来回跳表现出来就是死循环。解决办法就是把回填槽位改成statement函数内的局部变量如 4.2 节所示。改完之后建议专门写一个三层嵌套的用例验证比如三个条件分别取真取假跑八种组合逐一比对输出。这个用例的收益很高后面再改别的语句扩展时也能复用。5.4 then 分支被执行两次才进 else现象是带 else 的 if 语句里then 分支的write输出了两遍然后才执行 else 分支。原因是漏掉了gen(jmp, 0, 0)这条指令条件为假时jpc跳到 else 起点没问题但条件为真时 then 体执行完没有跳过 else 的机制会顺着往下把 else 体也执行一遍。如果 else 体里又有 if看起来就像 then 分支被重复执行。还有一种变体是jmp生成了但回填位置写成了cx1而不是cx2效果是 then 体执行完跳回条件判断处在条件不变的情况下形成死循环。解决方法是按 4.3 节的表格逐条核对指令序列重点看jmp是否存在、目标地址是否落在 else 体之后的第一条指令上。打印 code本文还有配套的精品资源点击获取