简介面向高校编译原理课程学习者与实验课教师围绕广工教学型PL/0编译程序提供一套可动手修改扩充的实验材料重点解决词法分析、语法分析与语义处理环节的改造练习。压缩包共24个文件约644KB包含cpp与h源码、dsw/dsp工程配置、doc实验报告以及exe、obj、pdb、ilk等编译调试产物和txt、tmp辅助文件便于直接打开工程对照阅读与复现。实验要求涉及新增ELSE、FOR、TO、DOWNTO、RETURN等保留字和、-、、--运算符将不等号#改为并为条件语句补充ELSE子句能够帮助读者理解PL/0各处理阶段的联动修改。目前已有790人学习适合需要参考工程组织、实验报告写法与扩充实现思路的读者。1. 保留字不是“特殊标识符”词法分析器在读到第五个字符时才做决定很多人第一次做编译原理实验都会默认一件事保留字就是被语言“占用”的标识符词法分析器把整个单词扫完再去表里查一遍命中就是关键字。这个理解不算错但它掩盖了一个更有意思的事实——在 PL/0 这类手写编译器里else和elsex一直到读完整个单词才分道扬镳而决定它们命运的不是那张保留字表是getsym里一个不起眼的循环边界。更反直觉的是给 PL/0 加 ELSE 语句时真正让人翻车的地方往往不是语法分析而是往保留字表插一项时的一个字母序以及条件跳转指令里那两个待回填的地址。搞懂这三处整个实验的骨架就通了。2. 保留字识别为什么elsex不会被拆成else加x先把一个容易混淆的边界理清楚。beginx、ifx、elsex在 PL/0 里都必须是普通标识符而不是“保留字 剩余字母”的拼接。这条规则在编译原理里叫最长匹配或者叫 maximal munch扫描器看到一个字母就一直吃到下一个非字母数字字符为止中间不允许断开。看起来是废话但它直接决定了后面查表的输入到底是什么——是一个完整的、已经被贪心截断的字符串而不是一个前缀。所以保留字识别这件事本质上是两段逻辑拼起来前一段负责把字符流切成“单词形状”后一段负责判断这个单词形状归谁。真正拉开各版本实现差距的是第二段怎么查。2.1 两种截然不同的识别结构查表与折叠进自动机手写词法分析器通常走查表路线先用一个通用规则扫出“字母开头的串”再去保留字表里比对命中就改 token 类型没命中就保持标识符类型。这是 PL/0 教科书版本的经典做法优点是保留字可增删改一个表项就能支持新语法。另一条路是把保留字折叠进自动机。为每个关键字画一棵前缀树根节点接收首字母走到底就是关键字走不到底又还在接受字符状态的按标识符处理。这类自动机可以用一串switch状态或者一张状态转移表实现查一遍就是 O(关键字长度)不需要字符串比较也不需要表。工业级编译器尤其是手工优化过的词法分析器更偏爱这条路因为它把“是不是关键字”这件事在扫描过程中就地判完了没有第二遍。两条路的关键差别在于扩展成本。往查表法里加else就是加一行数据往自动机里加else要重新算状态、重新画转移边改错一个分支可能让el开头的所有标识符都跑偏。教学编译器选查表法主要是这个原因不是因为查表更快。提示如果实验要求里写着“支持 ELSE”先确认老师要的是词法层的保留字还是语法层的语句形式。前者只改一张表后者要改动三个模块工作量差一个数量级。2.2 表结构的选择线性、二分、哈希与关键字树保留字表的组织方式是这个实验里第一个能写出“设计取舍”的地方。四种常见做法放在一起对比方式查找代价实现成本加一个关键字的代价适用规模线性扫描O(n)n 为关键字数最低追加一行n ≤ 20有序数组 二分O(log n)低但要求表有序插到正确位置n 中等哈希表平均 O(1)中要处理冲突重算或扩容n 较大关键字树前缀树O(长度)高状态要重排重构树关键字集合稳定PL/0 全部保留字加起来不到二十个而且全是短词。在这种规模下线性扫描实际上常常比二分更快——表小到能整块塞进缓存行循环次数也少没有分支预测压力。这是那种“复杂度分析赢不了实测”的玄学场景。但很多实现仍然选二分因为要“看起来规范”。这里有一处血泪经验值得提前说二分查找的正确性完全依赖表有序而表有序这件事编译器不会替你检查。线性扫描时表乱序完全无害一旦换成二分乱序的表不会报错只会让一部分保留字查不到表现出来就是“if能识别else死活是标识符”。这类 bug 的排查成本远高于它省下的那点性能。2.3 源码级拆解getsym里的最长匹配与首字符分流把上面两段逻辑合起来就是一个典型的getsym结构。它是整个词法分析器的心脏每一轮调用产出一个token把结果写进全局的sym如果 token 是标识符就把名字写进id缓冲区是数字就写进num。/* 取下一个字符换行时维护行号 ll文件读完给哨兵值 */ void getch(void) { if (cc \n) ll; /* 行号只在这里推进报错才有意义 */ if (pos len) cc src[pos]; else cc EOF_CH; /* 用哨兵收尾避免越界读 */ } /* 保留字表字典序排列二分查找依赖这个顺序 */ static const struct { const char *word; int sym; } keywords[] { {begin, beginsym}, {call, callsym}, {const, constsym}, {do, dosym}, {else, elsesym}, {end, endsym}, {if, ifsym}, {odd, oddsym}, {procedure, proceduresym}, {read, readsym}, {then, thensym}, {var, varsym}, {while, whilesym}, {write, writesym}, }; int lookup(const char *id) { int lo 0, hi NKEYS - 1; while (lo hi) { int mid (lo hi) 1; int c strcmp(id, keywords[mid].word); /* id 必须已转小写 */ if (c 0) return keywords[mid].sym; /* 命中改写 token 类型 */ if (c 0) hi mid - 1; else lo mid 1; } return identsym; /* 未命中就是普通标识符 */ } void getsym(void) { while (cc || cc \t || cc \r || cc \n) getch(); /* 跳过空白不产生 token */ if (isalpha(cc)) { /* 分支一字母开头 */ int k 0; do { if (k IDMAX - 1) id[k] tolower(cc); getch(); } while (isalnum(cc)); /* 最长匹配吃满整个单词 */ id[k] \0; sym lookup(id); /* 到这里才决定是不是保留字 */ } else if (isdigit(cc)) { /* 分支二常数 */ int n 0; while (isdigit(cc)) { n n * 10 (cc - 0); getch(); } num n; sym numbersym; } else if (cc :) { /* 分支三: 需要看两字符 */ getch(); if (cc ) { sym becomes; getch(); } else { sym colon; } /* 单个冒号留给错误处理 */ } else if (cc ) { getch(); if (cc ) { sym leis; getch(); } else if (cc ) { sym neqs; getch(); } else { sym lss; } } /* 其余运算符与非法字符省略 */ }这段代码里有三个参数值得留意。cc是当前字符整个扫描器是围绕它推进的ll是行号只在getch里推进保证报错位置准确id缓冲区必须留一位给\0所以写入时用k IDMAX - 1兜底否则超长标识符会踩到堆栈上的其他变量这种越界在实验里很难复现。getsym的结构也解释了开头那个问题else只有在读完e-l-s-e且下一个字符不是字母数字时才会以完整的else进入lookup。elsex走到lookup时是elsex二分查不到乖乖返回identsym。这也顺带说明了一点保留字和标识符共享同一条扫描路径区别只发生在查表那一瞬间它们在词法层面根本不是两类东西。3. 文法冲突ELSE 一进来PL/0 的递归下降为什么还站得住很多人以为加 ELSE 会撞上经典的 LL(1) 冲突改了文法之后分析器就崩了。实际情况更微妙PL/0 的递归下降在加了 ELSE 之后照样能跑难点不在“能不能分析”而在“else 归谁”这个语义归属以及一个藏在空语句里的暗礁。3.1 原始 PL/0 语句文法的 FIRST 集与那个隐藏的 ε先看扩展前的语句部分。用 EBNF 写出来大致是这样statement :: ident : expression | call ident | begin statement {; statement} end | if condition then statement | while condition do statement | read ( ident {, ident} ) | write ( expression {, expression} ) | ε注意最后一个分支 ε。原始 PL/0 的statement过程在遇到无法识别的符号时什么都不做直接返回这等价于允许一个空语句。这个设计在begin ... end里有用能让连续分号之类的写法不致死但它是后面所有麻烦的源头。现在算 FIRST 集FIRST(statement) { ident, call, begin, if, while, read, write }再加上 ε。而if产生式里then后面跟的正是statement所以FOLLOW里的东西会渗进“then 之后该不该继续读”的判断里。3.2 悬挂 else 的本质不是 LL(1) 表冲突而是二义性给if加上可选 else 之后产生式变成if :: if condition then statement [else statement]这时候if a then if b then x : 1 else y : 2就有了两种推导else 跟内层或跟外层。这就是悬挂 else 问题。它在递归下降里不会表现为预测表冲突因为递归下降根本不查表它靠代码顺序硬编码决策内层statement返回后立刻检查sym elsesym是就吃掉。所以递归下降天然给出“else 就近匹配”即跟最近的、还没配对的 if。但这里藏着一个真实问题。由于statement可以推导 εif a then else y : 2也是合法的——then 分支是个空语句else 跟外层。你觉得这没什么可如果词法分析器在then之后立刻读到了elsesym语法分析器就得判断这是“空语句 else”还是“一个出错的语句”前者说明空语句被允许后者说明这个 if 根本没有 then 分支体。原始 PL/0 的做法是什么都不做于是if a then else悄悄成立了跑到代码生成阶段就生成一段条件成立时什么都不做的指令。要堵住这个口子要么把 ε 从then后面的statement里禁掉进入 if 分支时用一个不允许空语句的变体要么在语法分析里显式报错。这不是 LL(1) 表能告诉你的事情是文法设计本身的问题。3.3 三种改法改文法、改分析器、改语言实际动手时有三种路线各有代价。第一种是改文法消除二义强制 then 分支用begin ... end包起来if :: if condition then block [else block]这样if a then begin if b then S1 end else S2里 else 只能跟外层二义彻底消失LL(1) 分析表也不会有冲突。代价是语言变得啰嗦写单条语句的 if 也得加块和“教学语言尽量轻”的初衷相悖。第二种是改分析器也就是保留二义文法靠递归下降的实现顺序天然实现“就近匹配”。这是绝大多数 PL/0 扩展的做法改动集中在一个过程的十几行里语义和 C、Java、Python 一致是能接受的设计。代价是你要在文档里写清楚这条规则否则别人用你的编译器写嵌套 if 时会踩坑。第三种是改语言干脆规定if必须有end收尾类似if c then S else S end。这让文法完全无二义分析器也好写但已经不是 PL/0 了属于另起炉灶。注意如果实验报告里要写“为什么选择递归下降而不选自动生成工具”答案不是“简单”而是“递归下降让悬挂 else 这种二义性变成一行代码顺序问题而 LR 分析器需要额外配置优先级或者改文法”。这是取舍不是优劣。4. 落地实现一个保留字引发的符号表、语法过程与跳转回填连锁反应词法层加一行、语法层加一个分支听起来是十几分钟的事。真做下来会发现改动会沿着三个模块往下渗每一层都有各自的坑。这一章按“词法 → 语法 → 代码生成”的顺序把 ELSE 从字符一路追到指令。4.1 词法层往保留字表插一项为什么顺序比内容更要紧词法层的改动就一句话往keywords表里加{else, elsesym}并在符号常量枚举里补一个elsesym。但这一步有两个连带的硬约束。第一个是枚举值要和语法分析的case分支对上。如果保留字码是连续枚举加一项之后后面的值全部顺移所有写死数字分支的地方都会错位。稳妥做法是显式赋值或者始终用符号名而不用数字。第二个是二分表的有序性。前面提过表乱序不会报错只会让部分关键字静默失效。更隐蔽的是如果你用strcmp比较而标识符读取时忘了转小写那Else、ELSE全部落到identsym用户会以为“只有小写 else 生效”。这类 bug 在验收时特别容易被抓因为老师第一件事往往就是大小写混着敲一遍。一个低成本的自检手段在程序启动时遍历保留字表确认strcmp(keywords[i].word, keywords[i1].word) 0对所有 i 成立不成立直接打印警告退出。二十行代码不到能省掉一晚上的排查。4.2 语法层statement过程里 else 分支的消费时机语法分析的改动集中在statement过程的if分支。核心问题是“什么时候看sym是不是 else”。答案是在 then 分支的statement调用返回之后立刻看中间不能有任何别的getsym插进来否则会把这个 else 吃掉或者跳过。procedure statement; var cx1, cx2: integer; begin if sym ifsym then begin getsym; condition; { 生成条件求值代码结果留在栈顶 } if sym thensym then getsym else error(16); { 缺少 then } cx1 : cx; { 记住 JPC 指令的位置 } gen(jpc, 0, 0); { 先占位跳转目标待回填 } statement; { then 分支体内层 if 会在这里消费自己的 else } if sym elsesym then begin getsym; cx2 : cx; { 记住 JMP 指令的位置 } gen(jmp, 0, 0); { then 体结束跳过 else 体 } code[cx1].a : cx; { 回填 JPC跳到 else 体起点 } statement; { else 分支体 } code[cx2].a : cx; { 回填 JMP跳到整个 if 之后 } end else code[cx1].a : cx; { 没有 elseJPC 直接跳过 then 体 } end else if sym whilesym then begin { ... 循环分支结构类似但多一个回跳 ... } end { ... 其余分支 } end;这里的cx是代码生成指针指向下一条要生成的指令位置gen(op, l, a)往code[cx]写一条指令然后cx加一。code[i].a是指令的地址字段也是所有跳转的目标。注意statement的调用顺序内层 if 的statement执行完返回时如果它自己有 else它已经在自己的过程里消费掉了。外层随后看到的sym要么是分号、要么是end、要么是外层自己的else。递归下降的“就近匹配”不是特意实现的是调用栈顺序自然给出来的这也是它在这个问题上比表驱动分析器省事的原因。error(16)之类的错误码需要一个统一的错误处理过程它不能简单打印了事否则语法分析器会卡在同一个符号上反复报错。常见的实现思路是记录错误、然后强制getsym推进一格或者跳到同步集分号、end、until再恢复。4.3 代码生成层JPC 与 JMP 的两处回填到了指令层if cond then S1 else S2的 P-code 布局是这样的计算 cond结果压栈 JPC L1 ; 栈顶为 0假时跳到 L1 S1 的代码 JMP L2 ; S1 执行完跳过 S2 L1: S2 的代码 L2: ... ; if 之后的代码问题在于生成JPC的那一刻L1还不知道在哪——else 体的第一条指令要到后面才生成。这是典型的前向引用解决办法是回填先生成一条目标地址为 0 的指令把位置记下来等目标确定了再回来改。生成时刻指令位置待填字段回填时机回填值then 体之前cx1JPC的a看到 else / if 结束else 体首地址 / if 结束地址then 体之后cx2JMP的aelse 体结束后if 结束地址这张表里最容易出错的是无 else 的分支。有 else 时JMP的生成和JPC的回填是同一个代码块里完成的没有 else 时只回填JPC一个地址指向 then 体之后。如果漏掉这个分支无 else 的 if 会跳到一个没被回填的 0 地址解释器直接跑到代码段开头表现出来就是“程序莫名其妙从头开始执行”或者死循环。还有一种更隐蔽的情况if里嵌套if两个JPC的cx1都用同一个局部变量记录。因为每次进入if分支都会重新赋值cx1递归调用返回后局部变量还在栈上所以不会串。但如果把它写成全局变量嵌套 if 一定出错。这是把cx1、cx2声明为过程内局部变量的真正原因不是风格问题。5. 避坑与排查PL/0 扩展 ELSE 时反复出现的 5 个翻车现场这几条都是从“改完能编译、跑起来不对”的现象倒推的按“看到什么 → 为什么 → 怎么修”组织方便对着自己的代码逐条比对。5.1 现象else 被当成普通标识符输入if a b then x : 1 else x : 2;语法分析报“缺少分号”或者“意外的标识符”。原因通常有两个。一是保留字表里根本没有 else 项词法层扫出来的else走到lookup返回identsym语法分析把它当成下一个语句的赋值目标。二是表里加了但插入位置破坏了字典序二分查找在某个分界点上直接跳过它。第二种更阴险因为它对部分关键字有效if、then都正常唯独else失效。修法是先确认表有序再确认比较前大小写已统一。加一条启动自检是最省事的遍历表检查是否严格递增不递增就打印出是哪两项一眼就能定位。5.2 现象嵌套 if 的 else 绑错层程序if a then if b then x : 1 else y : 2运行后a为真、b为假时y没被赋值。原因是 else 的归属错了。如果内层statement返回后没有立即检查sym elsesym而是把 else 留给了外层而外层又有自己的 else 分支两处就会错位。也可能是内层if分支里在statement调用之后插了别的getsym把 else 这个 token 提前消费掉了。修法是回到statement过程确认if分支的结构严格是“生成 JPC → 调 statement → 立刻判 elsesym”。中间不允许出现任何额外的getsym。另外检查cx1是否是局部变量全局变量在嵌套时会互相覆盖。5.3 现象空语句导致死循环输入if a then ;或者begin ; end这类写法编译器卡住不动。原因是statement遇到不认识的符号时直接返回没有推进sym外层循环又拿同一个符号进来形成空转。原始 PL/0 里这个分支是“什么都不做”在正常程序里几乎不会触发一旦允许 else 而用户又写了空 then 分支就暴露了。修法是在statement的兜底分支里要么显式报错并getsym推进一格要么跳到同步集。关键是任何一条路径都不能让sym原地不动否则循环不变量被破坏。5.4 现象没有 else 的 if 跳转目标错乱带了 else 的 if 正常不带 else 的 if 跑飞程序像从头开始执行。原因是JPC的回填漏了无 else 分支。有 else 时code[cx1].a : cx是在else的begin块里执行的如果代码写成“只在看到 else 时回填”无 else 的JPC就永远指向 0 地址解释器按code[0]执行表现就是重启。修法是把回填拆成两个出口有 else 时先回填JPC再生成JMP无 else 时直接回填JPC到当前cx。两条路径都必须让cx1被写上正确地址。5.5 现象大小写混用识别失败If a Then x : 1 Else y : 2;全部报错换成全小写就正常。原因是保留字比较用了区分大小写的strcmp而标识符读取时也没有统一大小写If进lookup自然查不到。另一种变体是转了小写但缓冲区越界最后一个字符被截断else变成els。修法是在扫描字母串时统一tolower写进id查表时不再做大小写转换。同时检查id缓冲区的长度上限写入前必须留一位给结束符。这两处任意一处出错表现都是“部分保留字失灵”很难和表乱序区分建议先跑一遍表自检再查缓冲区。6. 设计取舍手写递归下降凭什么比生成器更适合教学编译器同样一份 PL/0 加 ELSE 的需求用自动生成工具也能做写一段文法跑一遍工具拿到分析表和动作表改文法只要重新生成。但实验课上绝大多数实现仍然手写递归下降原因不在“简单”而在下面这张对比里的几行差异。维度手写递归下降自动生成表驱动二义性处理代码顺序即优先级悬挂 else 天然就近匹配需要配置优先级或改写文法错误恢复每个过程里可以写针对性恢复通用恢复信息颗粒度粗与代码生成耦合语法分析的同时直接gen指令通常要先生成中间结构再遍历改文法成本改函数改动局部可见改文法文件重新生成行为变化不可见最关键的是第三行。PL/0 是单遍编译语法分析走到哪P-code 就生成到哪cx指针、回填、符号表的域都在同一时刻被操作。这种“边分析边生成”的写法在表驱动框架里很难做因为分析表只告诉你“该归约了”不告诉你此刻cx停在哪。手写递归下降把这两件事绑在一个过程里输入一个 token 就能顺带吐出一条指令这正好是教学编译器想要的紧凑结构。代价也很清楚文法的正确性靠人肉保证。如果忘了处理then后面的空语句情况if a then else这种输入不会报错会一路生成到指令层最后表现成“程序行为诡异”而不是“语法错误”。所以我通常会在改完statement之后专门构造一组边界输入跑一遍空 then、嵌套 if、else 后接分号、大小写混用四个用例能覆盖绝大部分回归。从那以后我每次动保留字表都会先跑一遍顺序自检再编译这个习惯救过不止一次——顺手加一行else插错位置二分查不到现象却是“明明加了还是不识别”光靠看代码很难发现。希望帮到你。本文还有配套的精品资源点击获取
