PL/0语言扩充实战：从词法分析到代码生成的编译原理课设指南

简介这是一份面向编译原理课程设计的完整实验资源以 PL/0 语言编译器为基础围绕 if-then-else 条件分支、do-until 循环以及 for 循环 to/downto 两种步进形式进行语法扩充。资源覆盖条件判断、多种循环结构与变量迭代等典型编译实现场景并配有按功能划分的测试用例适合正在完成编译原理课设或自学编译器前端实现的学生参考。压缩包共 18 个文件包含 PL/0 编译器源码pl0.c、pl0.h、可直接运行的 pl0.exe以及验证各种扩充语法的测试文本如 test-else、testfor、dowhile 等和若干临时文件整体仅 62KB结构简洁、模块完整便于直接运行对照。目前已有 775 人学习下载。通过阅读源码与配套测试用例读者可以理解词法/语法分析、符号表维护和语句翻译等关键环节并据此继续扩展特性对于正在准备课设答辩或期末项目的学习者这份资源提供了直接可用的代码框架和验证思路。 编译原理课程设计选PL/0语言做扩充几乎是每个计算机专业学生都要过的一道坎。PL/0语言是Niklaus Wirth在《算法与数据结构》中设计的一个教学用Pascal子集规模不大但五脏俱全——词法分析、递归下降语法分析、符号表、目标代码生成、虚拟机解释执行一条完整的编译链路全都包含了。用这样一个小编译器练手能在一学期内把前端到后端的流程走通比直接去啃LLVM或者手写一个JavaScript解释器要现实得多。这篇文章就围绕“对PL/0语言进行扩充”这件事展开。我会从方案选型讲起逐步拆解词法、语法、语义和代码生成的改动思路再分享我实际调试时踩过的坑和排查技巧。如果你正在做类似的课程设计或者想拿一个高分这篇文章应该能帮你少走不少弯路。1. 项目背景PL/0语言的经典与局限1.1 为什么课程设计总爱选PL/0很多同学第一次听到PL/0心里都在犯嘀咕这语言也太简陋了连数组都没有循环只有WHILE简直不像一门“正经”编程语言。但恰恰是这种简单让它成了编译原理教学里最合适的实验载体。原版的PL/0语法结构非常紧凑EBNF描述下来没几页纸。整个编译器用C或Pascal写代码量通常在1000到2000行左右。很多学校的课设要求就是在这棵“小树”上做加法加几个控制流、加一批运算符、加一种数据类型既能锻炼对编译原理的理解又不至于让工作量失控。同时因为PL/0的代码结构足够清晰你做的每一项改动都能直观地对应到词法、语法、语义、目标代码生成这四个阶段中的一个或几个方便展示你“真的懂了”。拿我们实验室来说往年课设的常用扩充方向大概有十几种REPEAT-UNTIL循环、FOR循环、逻辑运算、一维数组、字符串类型、CASE分支语句、函数参数传递、注释支持、这类复合赋值符等等。把这些题目放在一起对比你就会发现看起来都是“改一个编译器”但工作量和风险差别特别大。选错了方向轻则熬夜debug重则直接把符号表和语义分析搞崩。1.2 原版PL/0编译器长什么样动手之前我建议先把原版代码完整读一遍别上来就改。原版PL/0编译器一般结构如下词法分析器负责把源代码流拆成token识别基本符号、数字、标识符、保留字。语法分析器递归下降实现核心入口是program、block、statement、condition、expression、term、factor这几层函数。符号表一张线性表每个符号记录name、kind常量/变量/过程、level层差、adr地址等信息。代码生成器在语法分析过程中同步生成P-code指令常见的指令集包含LIT、LOD、STO、CAL、INT、JMP、JPC、OPR。虚拟机/解释器读取P-code并执行维护一套栈式运行环境。值得注意的信号是原版的语句集合其实很小只有赋值语句、IF语句、WHILE语句、过程调用语句、复合语句BEGIN...END这些。这是一个EBNF式的简化语法保证了每一层递归下降解析函数都很好写。但对应的代价就是语言表达能力确实有限所以课设的扩充空间非常大。1.3 扩充前先想清楚的三件事按照我带过的项目经验改编前最怕的不是代码难写而是目标不清晰。这里有三件事越早想清楚越好。第一明确扩充目标的边界。你要加的是“REPEAT-UNTIL”还是“REPEAT-UNTIL加FOR加AND/OR加数组”边界一旦扩大功能之间会产生联动比如FOR循环和数组都得依赖符号表记录更多的类型信息注释识别要动词法层工程量会指数级上升。我见过太多同学一开始雄心勃勃列了六七个功能最后连一个REPEAT都没写完。第二搞清楚改动会波及哪些模块。很多特性的实现都不是孤立的。比如加FOR循环看起来只是statement层加个解析分支但你需要额外引入“循环变量在循环体内不可被赋值”这类语义检查这会牵动赋值语句的判断逻辑。再比如加逻辑运算符AND/OR如果只是把AND当成一个普通二元运算符处理不实现短路求值那很可能会被验收老师追问“为什么是jpc指令而不是opr指令”。第三准备好回归测试。原版PL/0编译器通常自带一个demo程序记录一下改动前能正常编译输出的正确结果。每改一个功能点就回归测试一次别等所有功能都写完了再统一调试否则你根本定位不了错误。2. 扩充方案选型加什么特性最稳2.1 常见扩充方向横向对比我整理了一下课程设计里常见的扩充方向按“实现难度”和“性价比”两个维度做了个对比便于大家选型。扩充方向涉及模块难度性价比常见坑点REPEAT-UNTIL语法代码生成低高条件与WHILE相反容易写反跳转逻辑FOR循环语法语义代码生成中较高循环变量处理容易出错逻辑运算AND/OR/NOT词法语法代码生成中高高短路求值表达式易拆错一维数组词法符号表语义代码生成高中符号表需要存数组长度和元素类型字符串类型词法符号表虚拟机高低需要引入新的存储模型复合赋值符等词法语法代码生成低中只是语法糖容易忽略左值语义多行注释支持词法低较高注释状态切换容易出bug观察这个表可以发现REPEAT-UNTIL和复合赋值符是典型的小改动适合时间紧张的同学逻辑运算虽然要动不少地方但做完后程序的表达能力提升非常明显性价比其实很高。一维数组是很经典的“进阶题”但需要在符号表上大改如果代码功底不够扎实容易陷入“数组元素赋值后取不出来”的调试泥潭。2.2 我的选择REPEAT、FOR、逻辑运算、注释我做这个项目时最终选了四个特性的组合增加REPEAT-UNTIL循环语句。增加FOR循环语句含TO和DOWNTO两种方向。增加逻辑运算符AND、OR、NOT且实现短路求值。支持源码中的单行注释用双斜杠//标识。选这四个理由很简单。前两个是控制流扩充对整个语法分析器的改造有代表性逻辑运算能体现你真正理解布尔表达式在栈式虚拟机上的求值过程注释支持虽然不起眼却能让词法分析器的状态处理思路得到体现而且对后续测试用例的编写帮助很大。不选数组和字符串也是听了之前学长学姐的教训。数组牵扯到符号表结构改动字符串牵扯到存储模型改动这两个方向在验收时一旦被追问需要解释的东西非常多。而我选的这四个特性彼此相对独立每个都在单独模块里适合逐个实现、逐个验证且“每个特性都能讲清原理”这正好符合课设的得分逻辑。2.3 实施顺序与依赖关系哪怕选好了特性实施顺序也很重要。我的实际顺序是先做词法层加入AND、OR、NOT、FOR、REPEAT、UNTIL、DO、DOWNTO这些保留字以及双斜杠注释。再做语法层分别加入REPEAT-UNTIL语句、FOR语句、逻辑表达式产生式。再做代码生成优先实现REPEAT-UNTIL的跳转逻辑然后实现FOR的初始化、判断、递增/递减跳转最后实现AND/OR/NOT的短路求值指令序列。最后扩展解释器实际上我的方案里没有新增P-code指令REPEAT和FOR都用原有的JMP、JPC、LIT、LOD、STO、OPR组合出来逻辑运算也用JMP/JPC做短路跳转。这样虚拟机不用动省了很多事。这一步很关键如果新增了指令集就得同步改虚拟机的指令解释逻辑工作量和排查难度都会变大。能用基础指令组合实现的尽量不要发明新指令。3. 核心实现词法、语法、语义与代码生成3.1 词法分析保留字表与符号识别的扩充PL/0原版词法分析通常是一个get_symbol函数读入下一个token并设置全局的sym、id、num等变量。基础符号像、-、*、/、、、、、、、:、(、)、,、;、.都通过字符判断逐一分流。扩充时最省事的做法是在保留字识别上做文章。原版识别保留字的方法是查表先把字母串读出来然后在一张写死的保留字表里查找。所以新增保留字只需两步在保留字表里加上AND、OR、NOT、FOR、REPEAT、UNTIL、DO、DOWNTO。在枚举类型里加上对应的sym值例如symfor、symrepeat、symuntil、symdo、symdownto、symand、symor、symnot。需要注意一个坑原始PL/0对保留字大小写是敏感的一般要求代码里必须小写。你新增的保留字也保持一致。如果想让编译器对大小写不敏感需要在词法分析阶段把所有标识符统一转成小写再查表但这会影响变量名区分属于额外需求课设阶段不建议贸然引入。再来说注释。双斜杠注释在词法上会带来一个跨行读取的状态切换。原来get_symbol只负责读一个token读完了就返回。加了//注释后如果读到斜杠还得再读下一个字符判断是不是另一个斜杠。如果是注释就一直读字符直到换行符或文件结束然后继续读下一个token。这里最直接的坑是读文件指针已经越过了换行符导致某些按行统计报错信息的同学报错行号会比实际少一行。解决办法是在跳过注释时遇到换行符要把全局行号计数器加一而不是直接丢掉不管。3.2 语法分析递归下降法的新增产生式语法层面的改动核心是给statement、condition、expression等函数增加新的分支。REPEAT-UNTIL语句的EBNF可以写成repeat_stmt repeat statement { ; statement } until condition .在递归下降的statement函数里增加一个branchif (sym symrepeat) { getsym(); int label cx; // 记录循环体起始位置 do { statement(); } while (sym semicolon getsym()); // 期望当前符号是 symuntil if (sym ! symuntil) error(...); getsym(); condition(); // 生成条件表达式代码 emit(JPC, 0, label); // 条件为假则跳回循环体 }注意这里有一个常见理解偏差PL/0的WHILE语句是“条件成立则继续循环”所以生成的是JPC跳向循环结束。而REPEAT-UNTIL是“条件成立则退出循环”条件为假时跳回循环体开始。所以REPEAT语句末尾的跳转目标和WHILE正好相反。我见过不少同学把REPEAT的JPC写错方向导致程序要么死循环要么一次都不执行。FOR循环的EBNF可以写成for_stmt for ident : expression (to | downto) expression do statement .实现时我的做法是先把初始表达式求值存入循环变量生成循环判断label在那里读取循环变量和终值表达式做比较如果满足循环条件则进入循环体循环体结束后对循环变量做加1或减1运算再跳回判断label。伪指令序列大致如下; for i : start to final do body 生成start表达式代码 STO i label_cond: LOD i 生成final表达式代码 OPR GT ; i final ? JPC label_do ; 不满足则进入循环体 JMP label_end label_do: 生成循环体代码 LOD i LIT 1 OPR ADD STO i JMP label_cond label_end:这里面最容易被忽略的是语义检查循环变量必须是一个已声明的整型变量不能是常量或过程名。同时循环体内部不允许对这个循环变量赋值。如果不做这个检查会出现匪夷所思的结果。我在代码里专门加了一个循环变量标志位来做这个检查。逻辑运算的实现我放在了condition层。我的condition函数原本只支持condition expression ( | | | | | ) expression .为了支持AND、OR、NOT我把条件表达式扩展成布尔表达式结构。这样每个bool_factor最终都可以递归回到关系比较同时支持括号嵌套。代码生成采用短路求值原理其实很直接对于表达式a AND b先求a如果a为假则整体为假不需要再求b对于a OR b先求a如果a为真则整体为真不需要求b。具体生成时用JMP和JPC指令配合标签做跳转。生成逻辑简述如下AND求aJPC到false_label再求bJPC到false_label设置结果为真JMP到end_labelfalse_label这里设置结果为假end_label合并。OR求aJPC跳过结果为真的设置再求bJPC到false_label真值路径上设置结果为真JMP到end_labelfalse_label设置结果为假end_label合并。这样每遇到一个逻辑运算符都会留下多个待回填的跳转目标。递归下降写起来会稍微麻烦一点但一旦理清“真假跳转”的思路代码就会非常清晰。3.3 语义分析与代码生成生成什么样的P-codePL/0的语义动作基本都是在语法分析的过程中同步完成的没有单独的语义分析阶段。符号表在这里承担了主要的语义信息。拿FOR循环来说符号表里需要记录循环变量的层差和偏移量。当进入FOR语句时我先在符号表里查找这个标识符确认它是变量再检查当前作用域里这个变量是否已经被标记为“循环变量”。如果是直接报错“for control variable cannot be assigned”。符号表本身在原版里比较简单每一条记录是(name, kind, level, value, adr)这样的组合。扩充逻辑运算时符号表不需要大动但扩充数组时就需要在记录里增加数组长度、元素类型等字段而且访问数组元素时要生成下标寻址指令。这也是我放弃数组方案的重要原因——工程量主要就在符号表结构的重构上。代码生成方面我的目标代码全部基于原有P-code指令集。这里有一个技巧无论你加多少语法糖只要它们能用一个顺序执行的栈式虚拟机表达就一定能用LIT、LOD、STO、JMP、JPC、OPR等指令组合出来。关键是别把指令序列当成“伪代码”一定要在纸上画出栈的变化过程。比如REPEAT的JPC跳转跳回label循环体开始处时栈顶状态必须和进入循环时保持一致否则下一次条件判断时栈里的数据就乱了。我在这个阶段踩过一个大坑写FOR循环时终值表达式被放在循环判断label之前生成导致每次循环都会重新计算终值。事实上如果终值是个常量表达式这问题不太明显但如果终值是个变量且循环体里修改了这个变量语义就不对了。正确的做法是循环开始前先把终值计算好存到一个临时变量或临时栈单元然后在每次判断时直接取这个临时值。我这里为了简便采用了“每次判断都重新计算终值”的方案但在文档里明确说明了这种实现的语义最终验收也能解释清楚。3.4 解释器虚拟机侧的适配有人说我扩充了语言却没动解释器是不是太容易了其实不是。不动解释器不代表不需要理解解释器。你生成的P-code最终要在这台虚拟机上跑所以你得清楚LOD和STO在运行时到底怎么操作栈帧JPC判断的是栈顶的哪个值。原版PL/0解释器通常维护三个寄存器程序计数器p、栈顶指针t、基地址寄存器b。每次执行LOD指令时需要沿着display链或静态链查找对应层级的地址。看懂这套运行时环境后再回头看自己生成的跳转指令才明白为什么循环体的前后不能有多余的栈残留。我的建议是在解释器的主循环里临时加一个打印指令码和栈顶值的调试输出开关。这样每次执行到JPC跳转时你能亲眼看到栈顶的值是什么、跳到了哪里排查死循环或跳转错位会快得多。4. 实操过程测试程序设计与联调4.1 一个覆盖全部新特性的测试程序扩充完成后我写了一个综合测试程序确保每个新特性都被执行到。核心代码如下program demo; var i, sum, neg, cnt; begin sum : 0; for i : 1 to 10 do sum : sum i; repeat sum : sum - 1 until sum 20; if (sum 0) and (sum 10) then write(sum) else write(0); cnt : 0; for i : 10 downto 1 do if (i 5) or (not (cnt 0)) then cnt : cnt 1 end.这个测试程序有几个设计考量FOR的TO和DOWNTO都测到了REPEAT-UNTIL测到了条件为真的退出路径AND/OR/NOT在关系表达式的基础上组合出现。如果这整个程序能编译并运行出正确结果说明核心功能基本靠谱。但要注意这只能证明“主流程通”。真正要测边界还需要单独写更小的用例。比如REPEAT只在条件满足时才退出、FOR循环终值小于初值、NOT作用于复杂括号表达式等。这些零散用例排查起来更容易定位。4.2 分阶段调试先语法后再语义我调试的顺序是先确保词法层识别正确再确保语法树构建正确最后才验证运行结果。具体做法是给编译器加一个“token流打印”的调试模式。每读到一个token就输出它的类型和原始文本。这样我一眼就能看出来AND、OR、NOT、FOR这些新保留字是否被正确识别注释是否被正确跳过。词法没问题后再做语法分析。我在语法分析函数的入口都打印当前函数名和当前token这样遇到“expected xx but found xx”之类的报错就能快速定位是哪一层递归出错。这个阶段最痛苦的是语法错误会引发连锁报错。比如REPEAT语句写错了可能连续报出五六个错误。后来我在error函数里只保留前三个错误并且打印出错的行号和预期符号定位速度快了很多。4.3 边界条件与错误处理下列边界情况是我在自测时专门构造的FOR循环初值大于终值TO方向循环体应执行0次。FOR循环终值等于初值循环体应执行1次。REPEAT循环体内条件在第一次判断就为真循环体至少执行1次。AND表达式左操作数为假时右操作数不应该被求值。我特意在右操作数里放了一个除零表达式来验证短路——如果没短路运行时就会出错。NOT括号表达式检查优先级是否正确。这些用例都很小但每一个都能命中一个容易出错的处理逻辑。比如FOR循环0次的实现很多人没注意导致循环体必然执行一次。短路求值的验证是最高性价比的一个测试很多实现只是把AND当成普通二元运算用乘法模拟必然过不了这个测试。5. 常见问题与排查技巧实录5.1 语法分析中的经典翻车点递归下降解析器一旦写错最常见的现象是“shift/reduce式”的连锁报错。比如我在实现FOR语句的DOWNTO时最初没有在语句解析分支里单独处理“识别DOWNTO和TO的差异”只是简单地在do前解析了一个终结符号结果导致“for i : 10 downto 1 do”在downto那里就报错了。原因很简单递归下降是顺序解析的你必须显式判断当前符号是TO还是DOWNTO然后走不同的表达式解析分支。另一个翻车点是REPEAT语句的;处理。REPEAT循环体内部是可以包含多个语句的这些语句用分号隔开但不是复合语句。所以在解析循环体的每个statement后如果遇到分号就继续解析下一个statement否则就要求遇到UNTIL。这里要注意最后一个循环体语句后不允许有多余的分号否则会解析出空语句虽然不报错但语义会很怪。5.2 符号表与作用域的坑符号表在PL/0里是按层管理的。嵌套过程里可以访问外层变量但外层不能访问内层。新增FOR循环时我只在全局层写了循环变量的声明一切正常。但后来在一个过程里写FOR循环时出现了“for variable not found”的错误。原因说出来很尴尬FOR循环变量查找时我没有按层差正确搜索符号表。原版符号表是一个按“层号序号”组织的线性表查找时从当前层开始向前找。我把层号搞错了导致在过程内部查不到全局变量。解决方法是把查找函数单独抽出来传入当前层号先查本层再逐层向外。还有一点容易忽略循环变量和普通变量的符号表记录要区分开。我是在符号表记录的kind字段上加了一个特殊标记表示“当前是循环变量”并在循环结束时恢复。否则两个嵌套FOR循环如果复用同一个循环变量第二次循环的语义检查就会误报“循环变量被赋值”。5.3 生成代码的执行期错误有时编译器不报错但运行结果不对。这种问题最头疼。我遇到的典型案例是REPEAT-UNTIL条件为假时应该跳回循环体结果它直接跳到了循环体中间的某一行导致变量只更新了一半进入死循环。排查方法我上面提过在解释器里加指令打印。打印后发现我生成的JPC目标地址是循环体的中间label而不是循环体开始。追根溯源是我在解析REPEAT时把循环体起始地址记录错了——记录在了condition解析完成之后而非循环体开始之前。这个bug只用肉眼检查生成代码很难发现但一旦打印指令流转一秒钟就能定位。逻辑运算短路求值也有一个隐藏很深的坑真值设置路径和假值设置路径没有正确合并。最终结果是表达式总能得到正确结果但如果表达式是另一个IF语句的条件程序会走出奇怪的跳转路径。后来我在每个bool_factor的生成函数返回前统一用explicit的“LIT 0,1”或“LIT 0,0”来表示真/假再用JMP合并路径代码可读性和正确性都提升了不少。5.4 避坑清单汇总症状根因处理建议注释识别后报错行号混乱跳过注释时未处理行号遇到换行符时递增行号计数器REPEAT循环体不执行条件跳转方向写反对照“入栈顺序”画跳转流程图FOR循环结束值为0次时仍执行1次判断条件使用了错误的比较指令明确“”跳出循环使用GT或LE正确配对AND/OR表达式短路失效未使用JPC/JMP做条件跳转而是当作普通算术重写bool_expr生成逻辑引入真假标签嵌套过程内FOR变量找不到符号表查找未处理层差迭代向上层搜索并检查层号运行死循环JPC目标地址指向了循环体中间在解释器里打印指令和跳转目标这份清单基本覆盖了我实现过程中遇到的所有高频bug。归根结底问题大多出在“对栈式运行模型的理解不够直观”而解决方案也很统一把每一条指令执行后的栈状态画出来对照着检查你生成的指令序列。最后再说一句课程设计以外的体会。编译器的调试和普通应用开发完全不同它的“程序”和“运行时环境”是两套逻辑。你在调试代码生成逻辑时要时刻保持“CPU视角”而不是“源码视角”。我自己最后能顺利完成这个扩充很大程度上是因为我在解释器里加了足够多的调试输出把黑盒变成了白盒。如果你也在做PL/0扩充不妨先从这一步开始。本文还有配套的精品资源点击获取