简介面向高校编译原理课程学习者及需要完成PL/0改造实验的读者这份广工编译原理实验包围绕教学型编译程序的词法分析、语法分析与语义处理扩充展开重点涉及ELSE、FOR、TO、DOWNTO、RETURN等保留字、-、、--等运算符以及将不等号#改为并增加条件语句ELSE子句等任务。包内共24个文件涵盖cpp/h源码、工程配置、exe/pdb可执行与调试产物、doc实验报告及txt测试文本压缩包约644KB便于对照源码、报告和测试样例梳理实现脉络。已有791人学习适合观察保留字表、符号识别与语法规则的联动修改借助测试代码验证运算符、不等号和条件分支的扩展效果也可用来复盘从源程序读入到目标代码生成的流程积累调试、错误定位与排错的相关经验尤其适合课程实验验收前查漏补缺。1. 加一条 ELSE 只要十分钟让它跳对地方要一整晚编译原理实验里最容易被低估的一步是给 PL/0 加一条 ELSE 语句。词法上加一个保留字语法上加一个分支看上去十分钟的活。真正把人卡住的是后半段条件为假时虚拟机应该跳到第几条指令。这个问题之所以值得较真是因为它把编译器的三个层次一次性摊开了——保留字识别决定了else是关键字还是普通标识符递归下降决定了这个分支归谁管目标代码回填决定了跳转地址填得对不对。前两层错了报错还算客气第三层错了程序照常编译通过运行时静默跑飞连个提示都没有。搞懂这三层怎么咬合PL/0 这个几百行的小编译器就不再是黑匣子而是一台能拆开看的机器。2.1 两套表word/wsym 与 table生命周期完全不同PL/0 的词法分析器里同时存在两套“表”很多人第一次读源码会把它们混成一件事结果改 ELSE 时改错了地方。第一套是保留字表通常写成两个平行数组一个存字符串一个存对应的符号码。它是编译期的常量编译一开始就固定运行期间不变也不占运行时空间。第二套是名字表table用来登记源程序里出现的标识符、常量和过程每个表项要记层差level、地址或值adr、大小size它会随着作用域嵌套不断增长是运行期语义的实际载体。else属于第一套。它没有地址、没有层差、不占运行时空间唯一的作用是让getsym()返回一个特定的符号码。把它塞进table是常见误解塞进去之后你会发现这个名字永远查不到定义还会干扰position()的查找。常见的实现思路是/* 保留字表严格按字典序排列 */ static const char *word[] { begin, call, const, do, else, end, if, odd, procedure, read, then, var, while, write }; /* 符号码与字符串一一对应插入位置必须完全一致 */ static const enum symbol wsym[] { beginsym, callsym, constsym, dosym, elsesym, endsym, ifsym, oddsym, procsym, readsym, thensym, varsym, whilesym, writesym }; #define NORW ((int)(sizeof(word) / sizeof(word[0])))两个数组的下标是同一个语义word[k]对应的符号码就是wsym[k]。这条不变量一旦破坏症状会非常诡异——else被识别成end或者if被识别成odd报错位置离真正的错误点十万八千里。2.2 二分查找的隐藏前提字典序与符号码的同位绑定getsym()识别出一个字母开头的串之后要在保留字表里查它是不是关键字。教科书版本用的是二分查找代码只有几行但藏了两个前提。static void getsym(void) { while (ch || ch \t || ch \n) getch(); if (isalpha(ch)) { int k 0; do { if (k AL) a[k] tolower(ch); /* 统一转小写ELSE/Else 才能命中 */ getch(); } while (isalnum(ch)); a[k] \0; int lo 0, hi NORW - 1, found -1; while (lo hi) { int mid (lo hi) / 2; int cmp strcmp(a, word[mid]); if (cmp 0) { found mid; break; } if (cmp 0) hi mid - 1; else lo mid 1; } sym (found 0) ? wsym[found] : ident; if (sym ident) { /* 不是保留字才去名字表里登记/查找 */ int i position(a); if (i 0) { /* 新标识符填入 table */ } else { /* 命中已有表项 */ } } return; } /* 数字、运算符、界符的处理略 */ }第一个前提是word[]必须严格按字典序。二分查找的循环不变式是“目标若存在必在[lo, hi]内”这个不变式完全依赖有序性。else的正确插入位置在do和end之间插到末尾或者随手插在begin后面查找就会漏掉——而且不会报“保留字表未排序”只会静默地把else判成ident。第二个前提是wsym[]必须同步。符号码不是随便排的它同时被语法分析的case分支、错误信息表的索引、甚至某些实现里打印符号名的数组引用。elsesym插在中间后面所有符号码整体后移一位任何硬编码数字的地方都会错位。血泪经验新增符号码时要么全局搜一遍所有用到符号常量的地方要么老老实实加在枚举末尾用命名而不是位置来保证正确性。顺带一个容易被忽略的细节tolower()。PL/0 原始版本只认小写字母很多实验要求支持大写写法如果你只在word[]里写了小写却忘了在a[]里转小写用户写ELSE就永远匹配不上报的错还是“then 之后缺少语句”。2.3 符号码往后传语法分析看到的是什么getsym()返回之后全局变量sym里装着当前符号码id里装着标识符名如果是identnum里装着数值如果是number。递归下降的每个子程序都基于这个“单符号前瞻”工作判断sym elsesym就消费一个否则报错。这里有个结构性约束值得说清楚PL/0 只有一符号前瞻没有回退能力。所以像if ... then ... else ...这种结构语法分析必须在读完 then 分支之后“恰好”停在else上。而 then 分支是一个完整的statement()调用它自己内部会不断getsym()退出时sym已经指向 then 分支之后的那个符号——正好是else如果有的话。这个“恰好”不是巧合是递归下降的核心约定每个语法子程序返回时都已经消费掉了自己负责的那部分并把sym推进到下一个待处理符号。理解了这条约定第 3 章的代码才能看明白判断有没有 else 分支靠的是 then 分支返回后检查sym而不是别的什么标记位。3. IF 语句的递归下降一个 jpc 为什么不够用3.1 jpc 的真实语义弹出栈顶为 0 就跳PL/0 的虚拟机指令是四元组f, l, af是操作码l是层差a是参数。条件语句用到的两条指令是指令语义对栈的影响JPC l a弹出栈顶若值为 0 则pc a否则顺序执行栈顶 -1JMP l a无条件pc a无JPC是条件跳转但它判断的是“为零则跳”不是“为真则跳”。这个方向很容易记反写反了的直接后果是 then 和 else 两个分支的行为整体对调。更重要的是它会弹栈。condition()生成的比较指令OPR 0 8到OPR 0 13分别对应、、、、、会把栈顶两个值弹出、压入一个 0/1 结果JPC紧接着把这个结果消费掉。所以一个完整的条件判断栈是平衡的净压入 0 个值。如果自己改虚拟机时忘了在JPC里做s s - 1短程序看不出来循环一跑几十次就栈溢出报的错是“栈顶指针越界”跟 if 语句完全看不出关系。3.2 单分支的原始写法回填发生在语句之后先看没加 ELSE 时的经典实现这是理解双分支的基础case ifsym: getsym(); condition(); /* 生成比较指令栈顶留下 0/1 */ if (sym ! thensym) error(16); else getsym(); int cx_then cx; /* 记下 jpc 自己的地址 */ gen(jpc, 0, 0); /* 占位条件为假时跳到哪里还不知道 */ statement(); /* then 分支 */ code[cx_then].a cx; /* 此时 cx 已是 then 分支之后第一条指令 */ break;关键在于最后一行。gen()在生成jpc的时候目标地址还没确定——then 分支有多少条指令那时候根本不知道。所以先填 0 占位等statement()返回、cx已经推进到 then 分支之后再把真实地址回写进code[cx_then].a。cx的定义是“下一条待生成指令的下标”gen()每次先写入code[cx]再cx。所以statement()返回时cx恰好指向 then 分支之后的第一条指令——这正是条件为假时应该跳到的位置。差一位就是经典 off-by-one。3.3 双分支的三次回填then 入口、then 出口、if 出口加上 ELSE 之后控制流从“一个入口、一个出口”变成“两个入口、一个出口”需要的跳转也就从一条变成两条condition | JPC ----假---- else 分支起点 | then 分支 | JMP ----------- if 之后 | else 分支 | if 之后对应到代码case ifsym: getsym(); condition(); if (sym ! thensym) error(16); else getsym(); int cx_then cx; gen(jpc, 0, 0); /* 桩 1条件为假 → else 入口 */ statement(); /* then 分支 */ if (sym elsesym) { /* statement 返回时 sym 已推进到下一个符号 */ int cx_jmp cx; gen(jmp, 0, 0); /* 桩 2then 分支执行完 → 跳过 else */ code[cx_then].a cx;/* 回填桩 1此刻 cx else 分支起点 */ getsym(); statement(); /* else 分支 */ code[cx_jmp].a cx; /* 回填桩 2此刻 cx if 之后 */ } else { code[cx_then].a cx;/* 没有 else条件为假直接落到 if 之后 */ } break;三处细节决定这段代码对不对。第一code[cx_then].a cx必须写在解析 else 分支之前。因为 else 分支的入口地址就是解析 else 分支那一刻的cx。如果写成解析完 else 分支之后再回填cx已经跑到 if 之后了结果是条件为假时直接跳过整个 elseelse里的语句永远不执行——而且编译、运行都不报错只是结果不对这种 bug 最耗时间。第二gen(jmp, 0, 0)不能省。省掉之后 then 分支执行完会“自然落入” else 分支的代码两个分支全都执行一遍。如果两个分支都在给同一个变量赋值你会看到变量值等于 else 分支的值看起来像是“条件判断失效”。第三if (sym elsesym)这个判断的时机是 then 分支statement()返回之后。这依赖 2.3 节说的约定statement()退出时已经把sym推进到 then 分支之后的符号。如果 then 分支是复合语句begin ... endend被消费后sym正好是else如果 then 分支是单语句x : 1分号或else被消费后也一样。前提是statement()内部实现没毛病。3.4 悬空 else递归下降天然就近匹配写嵌套if的时候会遇到经典的悬空 else 问题if a 0 then if b 0 then x : 1 else x : 2;这个else归谁语法上两种归属都能构造出合法的分析过程必须有个约定。主流语言统一采用“就近匹配”else属于离它最近的那个未匹配的if。有意思的是递归下降的实现根本不需要额外规则来处理这件事。内层的statement()在扫描到else时会先看到它因为它是被最内层if调用、最后返回的那个statement()。外层的if拿到控制权时else早就被内层消费掉了——栈的返回顺序自动实现了就近匹配。这也是为什么很多实验报告里写“实现了悬空 else 的正确处理”实际上一行特判代码都没写。反过来说如果你用自底向上的分析法比如 LR就得靠优先级声明或者文法改写来消歧那才是真的需要动脑筋的地方。顺带一个 PL/0 特有的坑很多实验要求里then 分支和 else 分支之间不能有分号因为 PL/0 的statement之间用分号分隔else前面多一个分号会被当成“空语句 语法错误”。如果你按 Pascal 的书写习惯在 then 分支末尾加了分号报的错会是“语句起始符非法”错误位置停在else上看起来像是else没被识别。4. 目标代码回填cx 游标与那些先用 0 占位的地址4.1 cx 是什么code[cx] 什么时候才算有效cx是代码生成器里唯一的一个游标初值为 0每gen()一次自增 1。它同时承担两个角色写入位置和“已生成指令条数”。这两个角色重合是因为 PL/0 的目标代码就是一段连续数组没有基本块、没有重定位。typedef struct { int f, l, a; } instruction; static instruction code[CXMAX]; static int cx 0; static void gen(int f, int l, int a) { if (cx CXMAX) { /* 教学实现里这是真实会踩到的边界 */ error(30); /* 目标代码区溢出 */ return; } code[cx].f f; code[cx].l l; code[cx].a a; cx; }CXMAX通常取 500 或 1000。加了 ELSE 之后每条 if 语句多生成一条JMP深嵌套的测试用例很容易顶到上限。如果gen()里没做越界检查表现出来的是内存踩踏症状随机。另一个容易忽略的点code[cx]在gen()返回之前是无效的或者说是上一条指令的残留。所以任何“先占位后回填”的写法都必须用gen()把桩打进去再拿桩的地址去回填。直接对code[cx].a赋值而不gen()写的是一条还不存在的指令后面gen()会把它覆盖掉。4.2 嵌套 if 里的回填顺序局部变量救了命设想三层嵌套的 if-elseif a 0 then if b 0 then if c 0 then x : 1 else x : 2 else x : 3 else x : 4;每个if需要记住自己的cx_then和cx_jmp。如果这两个变量定义成全局静态变量内层的if会把外层的值覆盖掉等外层回来回填时填进去的是内层的地址——跳转全部串味。正确做法就是把它们定义成case分支内的局部变量或者显式开一个栈。递归下降的调用栈天然是 LIFO与回填的嵌套结构严格同构case ifsym: { /* ... */ int cx_then cx; /* 局部变量每层 if 一份互不干扰 */ gen(jpc, 0, 0); statement(); if (sym elsesym) { int cx_jmp cx; /* 同理 */ gen(jmp, 0, 0); code[cx_then].a cx; getsym(); statement(); code[cx_jmp].a cx; } else { code[cx_then].a cx; } break; }这里有一个可以推广的结论回填的状态天然是栈结构因为待填的地址总是指向“未来”而未来地址的确定顺序是后进先出。任何“先跳出去、晚点再补地址”的编译场景——if、while、for 的break/continue、短路求值——都是同一套模式。理解了 if-else后面加break就只是多开一个回填栈的问题。另外说一下为什么这里不需要迭代到不动点。有些回填场景比如跳到跳转指令需要反复扫描直到地址稳定但 PL/0 的目标地址全部是“向前”的JPC和JMP永远跳到后面生成的指令地址单调递增。一次回填就够了不存在循环依赖。4.3 把目标代码打出来怎么手工验算一段 if-else光看代码看不出对错最有效的验证手段是把目标代码清单打印出来。写一个十几行的反汇编器static const char *mnemonic[] { LIT, LOD, STO, CAL, INT, JMP, JPC, OPR, OPR, OPR, OPR, OPR, OPR, OPR, OPR, OPR, OPR, OPR, OPR, OPR, OPR, OPR, OPR, OPR }; void listcode(int from, int to) { for (int i from; i to; i) { printf(%3d %-4s %4d %4d\n, i, mnemonic[code[i].f], code[i].l, code[i].a); } }用一段最小的测试用例if a b then x : 1 else x : 2;假设a、b、x分别在层差 1 的 3、4、5 号单元生成的代码大致如下地址指令la含义10LOD13取 a11LOD14取 b12OPR012GTR栈顶变 0/113JPC017条件为假 → 跳到 17else 入口14LIT01常量 115STO15x : 116JMP019跳过 else17LIT02常量 218STO15x : 219...if 之后手工核对的方法很简单把JPC的a和JMP的a拿去当数组下标看一眼落点对不对应“else 第一条指令”和“if 之后第一条指令”。如果 13 号的a填成了 19说明回填时机错了else分支成了死代码如果 16 号的a填成了 17说明JMP压根没生成cx_jmp记成了cx_then。再进一步可以拿虚拟机的执行轨迹对照。在解释器循环里加一行打印pc跑一遍上面的例子pc的序列应该是 10,11,12,13,(14..16 或 17..18),19。序列里出现 17 之后又回到 16或者 14 之后直接进 17就是跳转填错了。5. 排查清单ELSE 加完之后程序跑飞的五种典型现象5.1 词法层的两个坑现象一报错“then 之后缺少语句”但源码里明明写了 else。原因是else被当成了普通标识符。getsym()在保留字表里查不到它sym返回ident语法分析在statement()里找不到合法的语句起始符一路报错到thensym的检查点。最常见的触发点是保留字表没按字典序插。else的正确位置在do和end之间顺手插在表尾看起来“只是加了一行”但二分查找的前提被破坏了。二分查找不会报“表未排序”它只会静默返回ident。解决办法是把word[]打印出来核对一遍字典序或者干脆在初始化时加一个断言逐对比较strcmp(word[i], word[i1]) 0不满足就直接崩在启动阶段。这个自检值十行代码能省掉几小时的瞎找。现象二else认出来了但if语句的行为整体错乱odd变成了if。这是符号码错位。新增elsesym时插在枚举中间后面所有符号码整体后移一位而某些地方的case分支或者错误信息表是按数字硬编码的。wsym[]和word[]必须同位置插入这两个数组还好说。真正的问题是符号码还可能出现在错误信息表的索引、打印符号名的字符串数组、某些实现里的sym范围判断比如if (sym ifsym sym writesym)。任何一处没跟上症状都是“看起来毫无关联的语法结构出错”。解决方式是尽量用命名常量而不是数字并且在枚举末尾追加新符号用显式映射处理“语法上的顺序”和“枚举上的顺序”不一致。如果非要在中间插就把所有sym相关的数组和分支全局搜一遍。5.2 代码生成层的两个坑现象三else分支里的语句永远不执行且没有任何报错。回填桩 1 写晚了。code[cx_then].a cx如果放在解析完 else 分支之后cx已经推进到 if 之后条件为假时直接跳过整个 else 块。这个 bug 的隐蔽之处在于它完全不违反语法也不违反虚拟机语义只是控制流图少了一个分支。测试时如果你只测“条件为真”的路径永远发现不了。解决方式是拿一段打印目标代码的代码把JPC的a值当数组下标点过去看落点是不是 else 的第一条指令。另一种更省事的验证是构造一个“两个分支输出不同字符串”的用例跑一遍看输出。现象四嵌套 if 时外层条件为假却跳进了内层的 else。回填变量被定义成了全局或者静态变量。内层if覆盖了外层的cx_then/cx_jmp外层回填时填的是内层的地址。递归下降里这类状态必须跟着递归走定义成case分支内的局部变量是最省心的做法。如果确实需要跨函数传递就显式维护一个回填栈push在进入分支前、pop在回填后。顺带说一句这个坑在“给 while 加 break”的时候会再踩一次因为 break 也需要维护一个待回填的跳转链。血泪经验只要看到“待填地址”先想清楚它的作用域该跟着谁走。5.3 运行期的一个坑现象五短程序正常循环里套 if-else 跑几十次之后报“栈越界”。JPC忘了弹栈。标准语义是“弹出栈顶为零则跳转”如果自己改虚拟机时写成“读栈顶为零则跳转”每次条件判断都会在栈上留一个值循环一多就溢出了。表现是报错位置跟 if 语句完全无关看起来像是表达式求值出了问题。排查时把JPC的实现和OPR 0 8~OPR 0 13的实现放在一起看比较指令压入 1 个值JPC消费 1 个值净变化为 0这是必须成立的不变式。另一个变种是JPC在跳转时忘了先pc再赋值、或者赋值后又pc跳转目标整体偏移一位。这种偏移在单条 if 里可能恰好落在一条无害的指令上看起来正常嵌套之后才暴露。6. 设计取舍为什么教学编译器宁可一边生成一边回填把 ELSE 加完之后很自然会冒出一个问题为什么要一边解析一边生成目标代码而不是先建一棵语法树、遍历完再统一生成后者在工程上明显更常见。教学版 PL/0 选单遍我觉得理由是“可见性”。单遍编译把cx和pc的关系压缩到几乎同一个东西上code[cx]就是将来pc能取到的地址。学生盯着cx自增、盯着桩先填 0 再回填能亲眼看到“源程序的顺序结构”是怎么变成“目标代码的地址序列”的。一旦引入 AST中间隔了一层树的遍历顺序地址从哪来就变得抽象了。代价也很明确。单遍生成看不到全局所以做不了常量折叠、公共子表达式消除这类需要“整棵树”的优化回填状态脆弱少一个局部变量就串味错误恢复也麻烦——语法错误发生时cx里可能已经躺着半截指令如果不做快照回滚后续生成的地址全乱。我一般会这么理解单遍编译是把“正确但不可优化”和“简单但脆弱”绑在一起卖教学场景买的是前半句。验证这套东西对不对最有效的手段始终是“打出来看”。我习惯在每次改动代码生成逻辑后固定跑三个用例单层 if-else、两层嵌套 if-else、while 里套 if-else。每个用例都把目标代码清单打印出来逐条核对JMP/JPC的a字段落点。这个习惯来自一次教训——当时改完嵌套 if 觉得逻辑没问题跑了个简单的赋值测试也“看起来对”结果是因为两个分支恰好赋了相同的值跳转填错了都看不出来。从那以后我每次动回填代码都强制走一遍“打印清单 手工点地址 跑分支输出不同的用例”这三步再也不敢只靠肉眼读代码。如果你手上正好有这份 PL/0 实验的源码和文档建议从保留字表和statement()的 if 分支这两处开始读先把cx的变化盯一遍再去看虚拟机的pc怎么走。两边对上之后剩下那些扩展——加repeat、加for、加break——都是同一套回填骨架换个形状而已。希望帮到你。本文还有配套的精品资源点击获取