PL/0编译器课程设计实战：从词法分析到符号表扩充指南

简介编译原理课程设计资料包聚焦经典教学编译器PL/0的功能扩充面向高校计算机专业学生、课程设计者以及对编译器实现感兴趣的初学者。PL/0虽结构精简却完整覆盖了词法、语法、语义分析和目标代码生成等核心环节很适合作为教学实践起点。压缩包共42个文件以pl0源程序、cod中间代码、cpp工程文件、doc设计说明和测试用例等为主整包仅1.25MB目录按工程、源码、文档分类便于查阅。目前已有1053人学习下载。作者已实现赋值运算和-并完成Pascal风格FOR语句的扩充支持TO步长1和DOWNTO步长-1两种循环方向选做部分则实现了、--运算符和一维数组类型同时附有可执行exe及配套PL0测试程序。通过对照pl0源码与cod中间码可深入理解符号表组织、语法分析流程以及中间代码生成策略为后续扩展其他语言设施提供了实例参考。1. 课程设计选PL/0修改扩充一次看得见摸得着的编译器实战很多人把编译原理课程设计当成一次“背模板交差”但PL/0是个例外。它是一个完整到能运行的编译器骨架词法分析、语法分析、符号表、目标代码生成、解释执行五脏俱全但代码量只有千行级别。拿到这个题目意味着你不需要从零写一个编译器而是站在一个能跑的教学编译器上做手术——这正是我推荐的入门路径。它能回答“这是什么”最直接的问题PL/0本身就是一本会动的教科书。这篇文章要解决的是“怎么做、参数怎么设、坑在哪”适合那些选了或想选这个题目的学生也适合想快速把编译原理串起来的自学读者。2. 先读懂PL/0原版代码四个模块和两条必须摸清的链很多人拿到PL/0源码第一件事是找main函数然后开始瞎改改完发现解释器疯狂报错却不知道为什么。我一般会做两件事先看数据流再看符号表。这两件事弄明白后面加任何语句都是填空题。2.1 原版PL/0的四个模块从源码到执行的长什么样PL/0原版代码通常由四个相对独立的部分组成哪怕是不同语言重写的版本结构也大同小异。词法分析器负责把源程序拆成token比如关键字、标识符、数字、运算符。它的核心是一个叫getsym的函数每次调用都会读进一个符号并给全局的sym变量赋值。你加关键字比如for、repeat第一站就是这里。语法分析器负责按文法规则做递归下降分析。PL/0原版用的是自顶向下的递归下降每种语句对应一个函数比如statement()处理赋值和调用expression()处理表达式。这个模块是“总导演”它一边分析一边直接调用代码生成器输出目标指令。符号表管理负责记录每个标识符在哪个层次、什么类型、分配在栈的哪个位置。PL/0原版用的是一个固定大小的数组table数组元素是结构体字段包括name、kind、level、adr有的版本还有个size字段用来表示过程体内局部变量占用的空间。目标代码生成与解释器原版PL/0生成的是P-code也就是一套面向栈的中间指令最后用一个解释器逐条执行。解释器维护一个栈和指令指针用switch语句按操作码分发。这四个模块不是平等的。语法分析器是核心词法给符号符号表给地址代码生成给指令解释器消费指令。你加任何功能基本都会影响到至少两个模块这就是为什么要先画数据流。2.2 符号表从声明到引用的唯一通道符号表是PL/0里最容易出玄学问题的地方。它的作用就一条把标识符的名字映射到运行时的地址。PL/0没有局部变量表那样的复杂结构它用的是相对寻址每个变量在栈里的位置用层差和偏移量描述比如LOD 1 3表示“从当前栈帧往上数一层的过程的栈基址再偏移3个单元”。这里有个关键点原版PL/0的符号表只在声明阶段写入在语句分析阶段只查找不写入。所以过程引用局部变量时查找路径是从当前过程的作用域一路往最外层找找到后记录层差。这个层差要算准不是简单记一个level差值还要考虑嵌套过程之间的栈帧关系。很多人在做扩充时加了数组、加了新语句都没事一但涉及嵌套过程里的数组就爆炸基本是符号表层次定位的问题。2.3 双标号链表跳转指令的经典补法看PL/0源码时最让人懵的是处理if和while时那一串“tx”相关的代码。PL/0生成跳转指令时目标地址是未知的因为后面的语句还没生成。它采用的做法是先写一条带占位地址的跳转指令用tx作为指针把这个待回填的指令位置挂到一个链表上。等目标位置确定后再回头把地址填进去。这个链表技法在扩充语句时非常实用。比如你加repeat语句结束时要回头把repeat体第一条指令的地址填到循环开始处你加for语句需要在循环体的结尾回填修改步长后的跳转地址。理解了这个“先填占位、后面回填”的思路再多语句都不怕。2.4 怎么选扩充点先算工作量再动手课程设计常见的扩充点有好几个repeat语句、for语句、case语句、数组类型、字符串、布尔表达式短路求值甚至有人做函数返回值。我的建议是先按风险排序。三段式优先级是这样的——低风险repeat语句、逻辑运算符AND/OR、带else的if语句。它们不需要动符号表也不改运行时栈布局只是多了几条控制流指令。中风险for语句、case语句。for语句涉及初值、终值、步长三种状态的存放case语句需要构建跳转表容易在回填布尔判断上翻车。高风险数组、记录、函数参数传递、中间表示生成。数组需要改符号表结构、地址计算和解释器一改就是三处联动。我一般建议第一次做扩充的学生选一个低风险加一个中风险把核心链路跑通后再决定是否挑战数组。很多人上来就加数组结果卡在地址计算上最后只能删掉重来非常浪费时间。不是不能做而是要先学会走再跑。3. 扩充repeat和for语句从EBNF文法到目标代码生成这一章是整篇的核心操作章。你会看到改一个语句要经过词法、文法、代码生成三个关卡。我不会贴完整源码因为不同版本的PL/0源码细节不同贴了反而误导我给出的是和版本无关的改动步骤和关键代码片段。3.1 扩充repeat语句最小改动对应最小的文法变化repeat语句的语义很简单先执行一遍循环体再判断条件条件为假则继续循环。它和while的区别是先执行后判断而且循环体可以是多条语句。原版PL/0的statement文法一般是statement : identifier : expression | call identifier | begin statement {; statement} end | if condition then statement | while condition do statement | read identifier | write expression加repeat后文法变成statement : ... | repeat statement {; statement} until condition注意repeat的循环体不需要begin/end包裹这是一个隐蔽的小考点。很多学生按while的习惯硬给repeat体加begin结果分析器不认。代码生成也不复杂。我常用的写法是在解析repeat时记录循环体第一条指令的位置然后生成一条jpc跳转指令作为占位等条件表达式生成完后回填jpc的目标地址为循环体第一条指令的位置同时生成一条jmp跳转回循环体开头。整体框架如下int label_begin cx; /* 循环体第一条指令的位置 */ /* 这里递归调用statement来解析循环体 */ /* 解析until后的condition */ int jpc_pos gen(JPC, 0, 0); /* 生成条件跳转指令目标待回填 */ code[jpc_pos].a label_begin; /* 回填条件为假则跳回循环体开头 */ gen(JMP, 0, label_begin); /* 无条件跳转回循环体开头形成循环 */这段代码的逻辑很简单先记住循环体开始的位置生成一个jpc条件为真则继续往下走为假则跳回开始位置。回填地址是这里唯一容易出错的地方很多人忘记生成最后的jmp导致循环体只执行一次就退出。参数说明JPC指令弹出栈顶值如果它为0就跳转所以条件表达式计算出的值必须落在栈顶。3.2 扩充for语句词法、语法、代码生成三步联动for语句是PL/0课程设计里最经典的扩充题因为它的实现能很好地体现“变量绑定”的思想。PL/0没有for关键字词法分析器需要新增一个识别标识符FOR的逻辑。这里有个细节PL/0的关键字表是一个字符串数组你往数组里加for和to即可。但不同版本的getsym在识别关键字时用的是顺序查找还是二分查找决定了你加关键字的成本。顺序查找就一行二分查找要保证数组有序。语法上for语句的典型文法是这样的statement : ... | for identifier : expression to expression do statement实现时核心问题是循环变量怎么存终值放哪步长怎么处理常见做法是循环变量和终值都放在栈上临时位置初值赋给循环变量后比较循环变量和终值如果循环变量小于终值则进入循环体否则跳过循环体每执行完一次循环体把循环变量加一再比较重复上述过程。/* 伪代码以C语言思路描述PL/0代码生成逻辑 */ int loop_var_l get_level(varname); int loop_var_a get_addr(varname); /* 1. 初值赋值计算表达式压栈然后STO存入循环变量 */ gen_expression(/* 初值表达式 */); gen(STO, loop_var_l, loop_var_a); /* 2. 记录循环体开始位置便于循环回来 */ int loop_begin cx; /* 3. LOD循环变量LIT步长OPR ADDSTO循环变量循环变量自增 */ gen(LOD, loop_var_l, loop_var_a); gen(LIT, 0, 1); /* 步长为1 */ gen(OPR, 0, ADD); gen(STO, loop_var_l, loop_var_a); /* 4. LOD循环变量LOD终值比较满足条件则继续循环体 */ gen(LOD, loop_var_l, loop_var_a); gen(LOD, 终值的层差, 终值的地址); gen(OPR, 0, LEQ); int jpc_pos gen(JPC, 0, 0); /* 条件不成立则退出循环 */ /* 这里生成循环体语句 */ /* 循环体结束后回填jpc并跳回loop_begin */ code[jpc_pos].a cx; gen(JMP, 0, loop_begin);这个方案有个经典陷阱循环体里如果修改了循环变量循环次数就会变得不可预期。原版PL/0没有“值传递”这个概念for的循环变量在语义上应该是只读的但你实现时很难限制用户不写for i : 1 to 3 do i : i 1这种源码。多数课程设计不要求在此处报错但你要知道这个边界。参数说明几处最关键的自增操作放在循环体之前而不是之后。这么做的目的是让第一次进入循环体时循环变量已经是初值加一了。看上去不直观但能统一处理“循环体执行完后继续循环”的逻辑不产生重复代码。LEQ是小于等于比较对应i 终值这个判断条件。如果你想做的是for i : 10 downto 1这种降序循环比较指令就要改成GEQ步长变为-1但自增逻辑的顺序不变。JPC回填的位置必须在循环体生成完之后否则跳转目标指向未生成的指令解释器就会乱跳。3.3 语法合法性检查改完文法先过这关每改完一处文法我都会先跑一遍“合法程序”和“非法程序”的对照测试。合法程序是能通过原版编译器的测试集非法程序是故意写错语法、期望报错的测试集。这一步不是浪费时间它能帮你快速定位是词法问题还是语法问题而不用等到解释器跑起来才蒙。一个经常被忽略的点是加一个新语句关键字时检查它是否和已有token冲突。比如原版PL/0的符号符号表里已经有call如果你把新的关键字写成c开头且被词法分析器按前缀匹配就会有莫名其妙的问题。我的检查方法是在getsym里加打印开关把每次识别出的token名称打出来跑一遍测试程序人工确认每个关键字都被正确识别。3.4 repeat和for都做完后手动走一遍栈变化这一步是我个人特别推崇的验证方式别看这个过程枯燥它比任何断言都能帮你建立运行时感觉。拿到一段小代码比如for i : 1 to 3 do write i;手动模拟几条P-ce码指令的执行把栈里每个位置的数值变化写在草稿纸上再对照真实解释器打出的执行结果。这是把“纸上谈兵”变成“肌肉记忆”最快的方法。4. 给PL/0加数组类型符号表与P-code解释器的联动改动数组是PL/0扩充题里的硬骨头。它的改动横跨符号表、地址计算、解释器三个区域任何一个环节漏一拍程序就跑出荒诞结果。这一章按“声明阶段做什么、访问阶段做什么、解释器配合什么”的顺序来讲。4.1 数组声明符号表条目里加一个size字段原版PL/0符号表条目至少有name、kind、level、adr四个字段没有任何一个字段能表示数组占用的空间。所以第一步是给符号表结构体加size字段。声明数组时比如var a[10]你要在符号表里记录该标识符的kind为数组adr为该数组首元素地址size为10。这一步有个决策点数组下标从0开始还是从1开始。建议从0开始这能减少后续地址计算时的“真1调整”次数。很多人习惯把下标从1开始结果每一次访问都要多做一个减法还容易在边界判断上翻车。4.2 地址访问数组读写时怎么算偏移数组访问的代码生成分两步算出元素地址然后按地址读写。原版PL/0的栈式机器没有地址运算指令所以常见的做法是采用一条新指令比如IXAindex address它把栈顶的索引值弹出加上基地址再把结果压回栈顶。这样数组读和数组写就统一了。数组读先取数组首地址压栈再计算索引压栈然后调用IXA栈顶变成实际元素地址最后用一个取地址内容的指令读取。数组写先算地址再算要写入的值然后把值存入该地址。核心代码片段长这样/* 数组访问的代码生成逻辑以数组读为例 */ gen(LIT, 0, array_base_addr); /* 把数组首地址压栈 */ /* 生成索引表达式这一步会得到索引值并压栈 */ gen(OPR, 0, IXA_OP); /* 弹出索引和基地址压入实际元素地址 */ gen(OPR, 0, LOAD_OP); /* 弹出地址压入该地址的内容 */这里的两个操作码在做法上有很多种叫法有些版本用IND指令读写地址内容有些版本则拆成LOD/STO。参数说明IXA操作在栈上至少要占用两个临时位置一个放基地址一个放索引。你在表达式求值时要保证这两者的入栈顺序固定我习惯先压基地址再压索引。索引表达式可能很复杂比如a[i * 2 1]。它会在栈顶留下一个值这个值会被当作索引所以要确保索引表达式求值时没有污染栈里已有的基地址。越界检查原版PL/0不做。如果你想让解释器报告“数组下标越界”就得在解释器里存数组长度信息。做法通常是在生成代码时把size也压到栈上但这样会浪费栈空间大多数课程设计不要求做这一步我建议不做除非题目明确要求。4.3 解释器配合新增操作码一定要先测单元指令解释器是最后一道关卡。你新增的操作码必须加到解释器的switch分发里否则就算代码生成对了解释器也会报“未知操作码”或者直接乱算。这里有一个必须养成的习惯每新增一条指令先写一个最简测试代码只测这条指令比如const x 2; write a[x];。如果这条指令的行为没验证就别往下写更复杂的逻辑。测试的具体步骤是这样的把解释器改成调试模式每次执行一条指令就打印当前栈指针、栈顶几个值、指令指针位置。对照你预期的手工栈变化哪怕一人一值不对都要停下来查。如果栈顶值比预期多了一个基本都是IXA入栈顺序反了如果地址内容不对基本是LOAD/STORE的取址与取值混了。4.4 数组加完后别忘了全局变量和嵌套过程数组在全局区声明和过程内声明地址计算逻辑一致但层差不同。全局数组的层差是0过程内数组的层差是当前过程层数到目标过程层数的差值。很多人在全局数组上测试通过一放到过程里就变成“写不进去”就是因为符号表查找时嵌套过程层差算错把应为1的算成了0导致更新的是全局同名变量。另外PL/0原版的过程没有参数机制你的数组如果放在过程里过程调用时的栈空间分配是靠INT指令预留的。数组声明后过程内的局部空间要留够否则数组元素会把返回地址覆盖掉造成一种“看起来是写数组其实是写坏栈”的诡异现象。这种问题在解释器里非常难定位因为报错点离出错点非常远。5. PL/0扩充避坑5个让调试器无话可说的翻车现场这一章是血泪经验合集每条都是我在给学生改代码时反复见到的有的自己也踩过。按“现象 → 原因 → 解决”来写方便你对照排查。5.1 加了else之后else后面的语句永远不执行现象修改if语句支持else分支但编译后无论条件真假else分支都不执行。原因if语句生成的跳转指令顺序混乱。典型的错误是条件为真时本应继续执行then分支结果代码生成器先写了一条jmp跳到整个if语句之后再用jpc跳过then分支进入else分支两条跳转的目标地址相互覆盖。解决牢记三条规则then分支的条件判断用的jpc要跳过then直接落到elsethen分支结束时要有一条jmp跳过else回填jpc地址的位置放在else分支生成完之后。我一般在代码里注释好四条地址句柄分别是then_begin、else_begin、else_end按顺序回填。5.2 for循环跑一次就停循环体只执行一次现象for i : 1 to 3循环体只执行一遍i停在2。原因自增代码和目标比较指令的顺序颠倒。如果先比较再自增第一次比较时i1满足条件进入循环循环体结束后自增变成2再次比较时i2还是满足条件不应该停。一旦出现只执行一次多半是循环体结尾的跳转指令jmp回跳位置错了跳回了自增之后而不是循环体开始。解决把循环体开始标签设在自增指令之前让循环体结束后的jmp跳回“取循环变量再次比较”那个位置而不是跳回循环体第一条语句。5.3 数组下标越界把整个解释器搞崩现象给数组分配了10个元素的栈空间访问下标为9的元素时解释器直接把栈顶指针推到了不可思议的位置。原因过程内声明数组时INT指令预留的栈空间没有把数组大小算进去。原版PL/0在过程block分析结束时会用tx记录本过程声明占用的栈单元数有的版本忘了把数组size乘进去。解决在符号表声明阶段声明数组变量时对应地给tx加上(size)而不是加1。检查方法是打印每个过程声明结束后的tx值手动核对栈布局。5.4 加了新关键字后原来的程序反而报语法错现象往关键字表里加了for和repeat结果原版测试程序输不进编译器词法分析阶段就报错。原因词法分析在识别关键字时多数版本是取前两个字符做唯一性判断的。比如原版检测到b开头的token马上判定为begin你再加入beginend以外的关键字如果前缀冲突就会干扰原有判定逻辑。解决找到词法分析器的关键字识别代码检查它是否采用“穷举比较”而不是顺序查找。顺序查找会逐个比较全部关键字错误率低但性能差穷举比较快但不易维护。改了关键字表必须把getsym的识别逻辑一起改。5.5 嵌套过程中数组访问“张冠李戴”取到外层变量的值现象内层过程里定义一个数组写入值后再读取读出来是0。外层恰好也有同名数组内层过程不去改外层数组读出来的值却等于外层数组的值。原因符号表查找时内层的数组声明因为size字段没填或者填错了查找逻辑没匹配到内层条目顺着外层同名条目找到了外层变量。解决在符号表查找函数的遍历顺序上做文章。内层过程查找时优先匹配当前层的符号表条目当前层查不到再往外层找。很多学生写的查找函数是从符号表头开始向尾部遍历内层声明是靠后插入的一旦函数没有按层过滤就会被外层条目抢先拦截。6. 回归验证与进阶给PL/0写一组可复用的测试用例扩充做到能跑只是及格做到敢说自己没改坏原功能才是优秀。我在每一次扩充完成后都会跑一套固定的测试程序集这套测试集我用一个check脚本管理。测试集包含三组第一组是不含新特性的原版测试程序保证原功能不回归第二组是针对新特性的正例测试覆盖边界情形第三组是故意写错语法的反例测试确保错误报告不崩。正例测试里我固定会写这几个用例repeat循环体只执行一次、for循环从1到1只执行一次、for循环里循环变量只读不写、数组下标从0访问到size-1、嵌套过程内访问数组、数组内容在多层嵌套后依然保持原值。每一个用例跑完后对照预期输出做diffdiff不一致立刻停下来查。我还会做一步升级操作在解释器里加一个断点函数遇到指定的操作码就暂停并打印当前栈的完整内容。这个功能只用几十行代码但它让调试效率提升了一个量级。我加过一次后再也不想回到只能看报错输出的状态。最后说一个个人习惯我做PL/0课题时坚持每天只改一个功能点改完跑全部测试后过夜第二天再动下一个。原因很简单PL/0的改动彼此牵连一次改两个功能排错时长往往翻三倍。这套节奏帮我避开了绝大部分翻车现场希望帮到你。本文还有配套的精品资源点击获取