PL/0编译器扩展：为递归下降编译器新增%取模与**幂运算

简介编译原理课程设计项目面向计算机专业学生与编译器初学者。针对经典PL/0语言进行系统修改扩充基本要求完成、-赋值运算以及Pascal风格FOR语句的TO与DOWNTO两种步长实现选做部分实现了、--自增自减运算符和一维数组类型未完成的字符型、实数型、带返回值/带参数函数等功能也在文档中给出了设计思路。资源包共42个文件压缩后仅1.25MB其中pl0文件为PL/0源程序cod文件对应中间代码cpp与pas文件是宿主编译器实现源码exe可直接运行验证doc为课程设计说明文档结构较完整。已有1053人学习下载。通过该资源可获取完整的修改扩充源码、配套测试程序、可执行程序与设计文档适合用来对照理解运算符重载/扩展、循环语句编译实现、数组类型构造等编译原理核心环节也可直接作为课程设计报告与代码的参考蓝本。1. 从一道算术题说起为什么PL/0需要修改扩充标准PL/0只认加减乘除这是每个拿到编译原理课设的人都会碰到的第一堵墙想写个“210 % 7”验算结果词法扫描器直接报不认识。这道算术题不难但要把这两个运算符填进编译器得从词法、语法、中间代码、解释执行一路改到底缺一环都跑不出结果。本方案就围绕“运算符扩充”这条主线为PL/0新增取模%与幂运算把每一步改动、每一段关键代码、每一个最容易翻车的细节都摆出来。适合正在做编译原理课设、需要一次“独立改动”来撑起设计报告的同学也适合想快速看清一条完整编译链路的从业者作为参考。2. 总体架构设计五段式PL/0与新运算符的接入点PL/0的C语言实现一般分成五段。词法分析器getSYM把源程序切成一个个符号语法分析器用expression、term、factor三个嵌套函数做递归下降生成指令时统一走Gen函数输出到P-code数组解释器interpret用一块栈把指令跑完符号表table只负责登记常量、变量、过程。整个编译过程是单遍扫描边归约边出指令结构非常干净。这意味着新增运算符不是“在词法里加两个case”就完事。%和**要从字符流变成符号从符号变成表达式结构的一部分再变成一条可执行的P-code指令最后在解释器栈上算出结果。任何一个环节漏了编译器要么报语法错要么生成了指令却跑不出正确值。我一般把这种改法叫“全链路最小改动”每个模块都碰一点但每个模块都不大动符号表这种和运算符无关的部分干脆不动。2.1 PL/0原始结构回顾与改动范围评估动手前先画一张改动范围表比直接改代码重要得多。原版的expression处理加减、term处理乘除、factor处理原子表达式新增运算符之后%和乘除同级放进term**优先级最高且右结合放进factor。优先级关系完全由递归调用的嵌套顺序表达不需要额外的运算符优先级表也不会引入LR冲突。模块改动量具体改动词法分析中新增SYM_PERCENT和SYM_POWER处理*的两字符窥探与回退语法分析小term增加%循环分支factor尾部增加**递归检查中间代码小P-code新增OPR 13MOD与OPR 14POW两条编码解释执行小interpret增加两个case注意弹栈次序符号表无运算符不引入新对象类型不增加作用域规则这张表也是答辩时“设计思路”那一页PPT的原型。评审一眼就能看出你动过哪里、为什么这样动比一上来就贴三屏代码有效得多。2.2 三个改动点与一个不动的点顺着表捋一遍。词法分析器是第一个改动点负责把%识别成SYM_PERCENT、把识别成SYM_POWER难点在于*和的边界扫描器读到星号后必须多看一个字符才能决定返回哪个符号多读的这个字符如果属于下一个token还要回退这个细节在第3章单独讲。语法分析是第二个改动点term里补一个%分支factor末尾补递归的**检查。第三个改动点在解释器。而符号表完全不用动这是很多同学容易想多的位置——运算符不进符号表、不占符号表空间、不改变查找逻辑动了反而增加无谓的出错面。2.3 P-code指令扩展为什么不用新指令类型P-code原本就有OPR指令承载运算加减乘除、比较、读写都编码在OPR的第3个参数上。取模和幂本质上也是算术运算直接沿用OPR、在操作数上扩展编号13和14是最省事的做法。如果另起一种指令类型比如新增MOD和POW两个助记符反而要改指令发射、调试输出、解释器分派三处地方属于给自己找活干。通常的做法是在Gen的输出调试模块里同步加两行助记符翻译例如把OPR 13在中间代码清单里打印成MOD把OPR 14打印成POW。这样中间代码的可读性保住查指令序列时不用翻编号表调试效率和答辩说服力都能提升。2.4 单遍编译与递归下降改动为什么能控制在三天内递归下降法的好处是文法结构直接对应函数调用新增运算符只是加分支和加递归不影响其他文法的归约路径。单遍扫描意味着不需要重新设计AST或符号表传递边分析边出指令调试时把错误定位到某一行源代码就够。按这个方案一周内完成“改代码写测试跑通演示”是正常节奏前提是先按第2章把改动范围表做出来再动手。我见过不少同学上来就改getSYM改完发现term不认再改term改完又发现解释器跑不了来回折腾两周。先盘清楚“哪里动、哪里不动”后面每一步都有据可依。3. 词法与语法层实现运算符优先级与右结合的处理地图画好了开始落地。先处理词法再处理语法顺序不能反过来——语法层只认symbol词法认不出%和**的话后面全白搭。3.1 词法识别%与**怎么进符号流标准PL/0的getSYM逐个字符扫描遇到运算符就把ch翻译成对应的SYM枚举值然后继续GetCh()读下一个字符。新增%没有歧义单个字符就能定。**是真正常见的坑读到星号时不知道是一个星号还是两个必须先GetCh()窥探第二个字符再决定返回SYM_TIMES还是SYM_POWER。关键在这个“窥探”。如果第二个字符也是*当前符号是SYM_POWER两个星号都消费掉了如果第二个字符不是*当前符号是SYM_TIMES但这个第二个字符属于下一个token不能丢。最简单的实现是让它留在全局变量ch里不需要真正的回退——递归下降的分析器下一次调用GetSym()时自然会继续用这个ch。核心代码我写成这样case *: GetCh(); /* 窥探第二个字符 */ if (ch *) { sym SYM_POWER; /* 两个星号幂运算符号 */ GetCh(); /* 消费掉第二个星号 */ } else { sym SYM_TIMES; /* 单个星号乘法ch已指向下一字符 */ } return; case %: GetCh(); sym SYM_PERCENT; return;这段代码里SYM_POWER需要加进符号枚举SYM_PERCENT同理。注意else分支里没有再调GetCh()因为ch已经变成下一个待处理字符了再调用会把一个非运算符字符白白读掉这是“缺字符”类报错最常见的来源很多同学第一次实现就在这里翻车。3.2 运算符优先级总表递归下降天然表达结合性优先级关系整理成一张表写报告和答辩都能直接用优先级运算符结合性实现位置高**右factor尾部递归中* / %左term循环低 -左expression循环这张表的顺序直接对应语法函数的嵌套expression调用termterm调用factor。谁的优先级高谁就放在更内层被“先归约”。**是右结合选递归而不是循环因为循环天然左结合——这个点是整个课设里最值得展开讲的实现细节。3.3 语法层改动term与factor的关键代码factor函数原版处理标识符、数字和括号新增长度只有几行。在解析完基本因子之后检查当前符号是不是SYM_POWER如果在就直接递归解析右操作数然后生成一条OPR 14指令void factor(void) { if (sym SYM_IDENT) { /* 查符号表变量生成LOD常量生成LIT过程生成CAL */ GetSym(); } else if (sym SYM_NUMBER) { Gen(LIT, 0, num); GetSym(); } else if (sym SYM_LPAREN) { GetSym(); expression(); if (sym SYM_RPAREN) GetSym(); else error(22); } /* 新增幂运算右结合优先级最高 */ if (sym SYM_POWER) { GetSym(); factor(); /* 递归解析右操作数右结合由此而来 */ Gen(OPR, 0, 14); /* OPR 14 POW */ } }为什么右结合靠递归就能出来以232为例第一个factor调用处理完2后看到**于是GetSym()再递归调factor去解析32。内层factor把3算完又看到再嵌套一层处理2最后生成的指令序列是LIT 2, LIT 3, LIT 2, OPR 14, OPR 14。解释器按栈式计算时先算329再算29512正好是2^(3^2)。如果偷懒把这个分支写成while循环指令就变成LIT 2, LIT 3, POW, LIT 2, POW算出来64——这是整个扩充里最容易翻车、也最值得在答辩时主动讲清楚的点。3.4 term循环的完整形态term函数和factor配套。原版while条件是TIMES或SLASH把%加进去生成指令按符号区分void term(void) { factor(); while (sym SYM_TIMES || sym SYM_SLASH || sym SYM_PERCENT) { int sym0 sym; GetSym(); factor(); if (sym0 SYM_TIMES) Gen(OPR, 0, 4); /* MUL */ else if (sym0 SYM_SLASH) Gen(OPR, 0, 5); /* DIV */ else Gen(OPR, 0, 13); /* MOD */ } }term里三个运算符的优先级一致所以用循环实现左结合。7 % 3 * 2会被归约为(7 % 3) * 2和C、Java的行为一致。这里有个容易被忽略的细节PL/0的负数写在expression层不是作为前缀运算符挂在factor上所以-7 % 3的语义由整个表达式结构决定term里不用特殊处理。如果硬把负号塞进factor反而会破坏现有的加减优先级这是典型的越改越乱。4. 中间代码生成与解释执行P-code扩展与栈式运行语法层归约的同时把指令发出去接下来解释器要能算。这一章负责把OPR 13和OPR 14变成真实结果顺带把栈式虚拟机最容易踩的弹栈次序问题讲透。4.1 OPR指令的编号约定原版PL/0里OPR 0到12分别是返回、取负、加减乘除、奇偶判断和六种比较。扩展编号时从13开始避免和原有编号冲突。约定如下操作数助记符语义栈变化栈顶在前13MOD次栈顶 % 栈顶弹两个压一个14POW次栈顶 ** 栈顶弹两个压一个助记符只用于调试输出解释器分派时看数字。Gen生成代码时把助记符一并打印到指令列表里比如printf(OPR 13 // MOD)这样中间代码dump一眼能看懂不用拿编号表对着数。4.2 解释器实现MOD与POW栈式虚拟机里LIT把常量压栈LOD把变量值压栈OPR从栈顶取操作数、算完把结果压回。新增两个case的代码不长但弹栈次序必须固定case 13: /* MOD */ b stack[top--]; /* 先弹出栈顶右操作数 */ a stack[top]; /* 此时栈顶是左操作数 */ if (b 0) { printf(Runtime error: div by zero in MOD\n); exit(1); } stack[top] a % b; break; case 14: /* POW */ b stack[top--]; /* 指数 */ a stack[top]; /* 底数 */ stack[top] (int)pow((double)a, (double)b); break;这里用pow转double的方式在课设阶段够用。两边都是int先转double再取整行为稳定结果超过int范围时整型溢出行为与C编译器一致。答辩被问到溢出就答“这是int边界扩展为long long即可”不要把话说死说不会溢出。4.3 弹栈次序这段代码为什么不能颠倒上面代码里b stack[top--]先弹右操作数a取次栈顶。如果把顺序写成a stack[top--]再b stack[top]得到的a和b就互换了。对加法没影响对MOD和POW是致命的5 % 17会被算成17 % 5 23 ** 2会被算成2 ** 3 8。这类错误单独看很难发现因为不报错只是结果“有点怪”。我通常的做法是写一个三行的小指令序列LIT 17, LIT 5, OPR 13先在纸上推一遍栈序列再跑解释器。这种哑调试比盯着看代码快得多算是血泪经验——凡是双操作数的OPR指令写成“先弹右、再取左”的口诀SUB和DIV也适用。4.4 负数底数幂与括号的语义PL/0的负号挂在expression层所以-3 ** 2和(-3) ** 2在语法上不是一回事。前者的指令序列是LIT 3, LIT 2, POW, NEG语义是-(3**2)结果是-9后者括号内先归约出-3指令是LIT 3, NEG, LIT 2, POW结果是9。这是标准数学约定答辩时主动演示这两个用例能直接证明你不只是改了词法连运算符语义都做过推敲。4.5 指令生成与解释的联调方式PL/0单遍编译指令数组在语法分析时填满解释器跑之前可以先把指令序列打印出来。我习惯在Gen()里加一个开关打开后输出“指令号、助记符、参数”拿232的中间代码和手推结果对一遍再跑解释器。对了再收工不对就回去看语法层——这样把问题限定在词法、语法、解释三个桶里不至于全乱成一锅粥。中间代码清单是这门课里最好用的后悔药比任何调试器都直观。5. 常见问题与避坑运算符扩充最容易翻车的五个点把最容易出问题的地方集中写出来每一条都按“现象—原因—解决”展开。这些点绝大多数不是理论难而是实现细节。5.1 term循环忘了加%分支现象7 % 3编译直接报错错误位置往往指向行尾有的实现会报“缺分号”让人一头雾水。原因词法已经识别出SYM_PERCENT但term的while条件只有TIMES和SLASH。语法分析器把%当成表达式结束后的非法符号后面的内容全被打乱。出错信息指向的位置通常不是%本身而是它后面的合法符号很容易让人误判成词法问题。解决在term循环条件里补上SYM_PERCENT同时补上对应的Gen(OPR, 0, 13)分支。改完跑一个最简单的VAR a; BEGIN a : 7 % 3 END.验证过了再继续向下。每次动term先把这三个运算符的两两组合测一遍不要只测一个。5.2 把幂运算写成了左结合现象2 ** 3 ** 2输出64而数学上应该是2^(3^2)512。原因factor里用了while循环而不是递归。循环会先归约左侧子表达式生成的是LIT 2, LIT 3, POW, LIT 2, POW天然左结合。光改生成指令的顺序也救不了归约顺序在语法层就已经定了。解决改成if (sym SYM_POWER) { GetSym(); factor(); Gen(OPR, 0, 14); }利用递归让右侧子表达式先归约。改完用带注释的指令序列dump验证看到LIT 2, LIT 3, LIT 2, OPR 14, OPR 14的顺序就对了。这个用例在答辩演示中有奇效评委一看就知道你懂结合性。5.3 弹栈次序颠倒结果看起来“没报错但不对”现象3 ** 2输出85 % 17输出2。单测一个用例时很难意识到错了因为结果都是合法数字编译器不报任何错。原因解释器里先弹左操作数再弹右操作数导致实际计算了2**3和17%5。这类错不抛异常、不给提示是纯运行时逻辑问题最消耗时间。解决定义一条硬口诀“先弹栈顶的是右操作数次栈顶是左操作数。”所有双目运算包括SUB、DIV、六种比较都遵循这个次序。写完先构造LIT 3, LIT 2, OPR 14的指令序列单独验证不经过语法层直接跑解释器定位最快。5.4 *和**的边界识别失败现象a * b能编译a ** b报错或者源程序里写2**3词法把三个字符切成数字、TIMES、数字幂运算完全没生效。原因getSYM遇到读了第二个字符后没有正确保留状态把属于下一个token的字符吞掉了或者另一种写法先把翻译成TIMES再发现第二个*想升级成POWER但符号已经发出去了代码生成阶段收到的已经是错误序列。解决按第3章的写法遇到先GetCh()窥探是则直接发SYM_POWER并消费掉第二个星号不是*则发SYM_TIMES全局ch保留在第二个字符上下一次GetSym()自然接管。这个ch是全局变量不存在真正的“回退”理解这一点就不会写错。5.5 边界测试缺失答辩现场翻车现象演示5 % 0时解释器直接除零退出或者被追问“(-3) ** 0等于多少”答不上来。如果没准备边界用例现场临时试很可能当场暴露没测过的死角。原因只测了正常用例没有覆盖除零、模零、负底数、零指数四类边界。课设报告里“测试”一章如果只写三个例子评审一眼就看穿。解决预先准备一张边界测试表至少包括17 % 5 2、5 % 0报错、0 % 5 0、(-3) ** 2 9、2 ** 0 1。答辩时主动说“边界我测过”评审追问的概率立刻降一半。这张表也直接放进报告作为测试设计的一部分。6. 验收与答辩让评审一眼看出你改了什么6.1 验收清单把验收做成一张表逐项打勾比口头说“跑通了”有说服力得多。按四类列一下类别用例预期结果词法2 ** 10识别为SYM_POWER中间代码出现OPR 14语法优先级2 3 % 2输出3证明%优先级高于结合性2 ** 3 ** 2512证明右结合边界与错误5 % 0运行时明确报错不崩溃再加一条回归用PL/0原生能跑的求最大公约数程序编译运行结果必须和改动前完全一致证明新增运算符没有破坏原有文法。6.2 答辩演示脚本3分钟就够。先花30秒讲需求标准PL/0只有四则运算我要加%和**再花60秒指着中间代码清单展示词法和语法改动重点提右结合用递归实现接着60秒跑测试用例把上面表格逐条过一遍最后30秒讲一个避坑点比如弹栈次序这会让评审觉得你真踩过坑而不是背了PPT。不要从头读代码评审判的是设计思路和工程意识。6.3 三个高频提问“优先级怎么保证的”答递归嵌套expression调term调factor谁的优先级高谁在更内层被先归约。“为什么不新增指令类型”答OPR本身就承载算术运算扩一个操作数比新增指令类型改动面小解释器只需要加case。“负数幂为什么是-9”答负号在expression层-32按语义是-(32)括号版(-3)**2才是9。这套方案做完我不敢说你的编译器能上生产环境但作为一次“独立改动”去答辩词法、语法、代码生成、解释执行、测试、边界六个环节都有说头。想起当年我把弹栈次序写反对着3**28的结果怀疑了一晚上解释器是不是有玄学问题第二天手推栈序列才定位到两行代码。从那以后凡是动OPR指令我都先写三行指令序列在草稿纸上推一遍再上机。希望这个习惯和这套方案对你也有用。本文还有配套的精品资源点击获取