NUAA编译原理课设：PL/0编译器从架构到代码生成实战

简介这份资源是南京航空航天大学编译原理课程设计的完整实践成果面向正在学习编译原理、需要动手实现编译器的计算机专业学生与自学者。项目以PL0这一简化版Pascal教学语言为对象完整覆盖词法分析、语法分析、语义分析与代码生成等核心阶段帮助读者把课堂理论落到可运行的编译器代码上。压缩包共7个文件约1.71MB包含C实现的编译器源码、编译后的可执行程序、课程设计报告PDF以及多组PL0测试用例文本源码与报告相互印证便于对照理解各模块的解析规则与实现思路。目前已有420人学习下载。通过阅读源码、运行可执行文件并比对测试用例输出读者可以掌握用C构建编译器核心组件的具体方法理解变量声明、赋值、流程控制等语言元素的处理流程并借助报告中的设计思路与问题解决策略完成从理论到工程的完整闭环适合作为课程设计参考与编译器入门实战材料。1. 从 PL/0 到可运行的编译器NUAA 编译原理课设到底在做什么如果你在南航读计算机相关专业大概率会在某个学期撞上「编译原理课程设计」这门课而题目十有八九就是实现一个 PL/0 语言编译器。很多同学第一次听到这个任务时是懵的——PL/0 是什么编译器又该怎么写其实 PL/0 是 Pascal 的一个极小子集最早由 Niklaus Wirth 在《Compiler Construction》里作为教学语言提出它只支持整数变量、常量定义、四则运算、条件分支、循环和过程嵌套语法规则用 EBNF 写出来不到一页纸。正因为足够小它才适合作为编译原理实验的载体你不需要处理复杂的类型系统但词法分析、语法分析、符号表管理、错误恢复、目标代码生成这些编译器的核心环节一个都不少。NUAA 的课设通常要求你实现一个能跑通测试用例的完整编译器输入是 PL/0 源程序输出可以是中间代码如 P-code或者直接解释执行。这篇文章面向正在做这个课设、或者想自己动手写一个 PL/0 编译器的同学从环境搭建到代码生成把每一步拆开讲清楚包括我当年踩过的坑和后来带学弟时总结的调试技巧。2. 先想清楚架构PL/0 编译器的模块划分与数据流2.1 为什么 PL/0 适合用「一遍扫描」的递归下降PL/0 的语法足够简单没有向前看多个 token 的需求所以递归下降分析器是最自然的选择。所谓「一遍扫描」是指词法分析器按需从源文件读取字符语法分析器在需要 token 时调用词法分析器而不是先把所有 token 存成数组。这样做的好处是内存占用小、结构清晰而且和 Wirth 原始的实现思路一致。递归下降的核心是为每个非终结符写一个函数函数内部根据当前 token 决定走哪条产生式。比如statement函数会检查当前 token 是IDENT、IF、WHILE、CALL、BEGIN还是READ/WRITE然后分别处理。这种写法调试起来很直观因为调用栈就是语法树的展开路径。但要注意PL/0 的过程可以嵌套定义而且支持递归调用。这意味着符号表必须支持作用域链不能只用一个全局表。常见做法是用一个栈式符号表进入过程时压入新作用域退出时弹出。每个符号记录名字、种类常量/变量/过程、类型PL/0 只有整数、层级和值常量或地址变量。地址分配通常用相对地址相对于当前过程的基址寄存器这样递归调用时每个活动记录都有自己的变量副本。2.2 目标代码选 P-code 还是直接解释执行NUAA 课设一般要求生成 P-code也就是一种栈式虚拟机的指令。P-code 的指令集很小常见的有LIT压入常量、LOD加载变量、STO存储变量、OPR算术/关系运算、JMP无条件跳转、JPC条件跳转、CAL调用过程、INT分配栈空间、RET返回等。生成 P-code 的好处是你可以单独写一个虚拟机来执行它这样编译器和解释器解耦调试时可以先检查 P-code 是否正确再排查虚拟机的问题。如果你选择直接解释执行那语法分析过程中就要边分析边求值这其实更像一个解释器而不是编译器。对于课设来说生成 P-code 更符合「编译器」的定义也更容易拿高分。下面是一个典型的 P-code 指令表指令含义参数LIT将常量压入栈顶常量值LOD将变量值加载到栈顶层级差, 偏移STO将栈顶存入变量层级差, 偏移OPR执行算术或关系运算运算码JMP无条件跳转目标地址JPC栈顶为0时跳转目标地址CAL调用过程目标地址INT栈顶指针增加空间大小RET从过程返回无2.3 用 C 还是用 Java语言选型的实际考量热词里有人搜「java编译原理」也有人问「c语言编译器」。对于 PL/0 课设C 和 Java 都能做但侧重点不同。C 语言更贴近底层指针操作符号表和代码数组很直接而且南航的实验环境通常就是 GCC 或 MSVC用 C 写不会遇到运行时环境问题。Java 的好处是自带集合类符号表可以用HashMap或ArrayList不用手动管理内存但虚拟机部分需要自己写一个栈结构。我个人的建议是如果你以后想走系统方向用 C如果只是想快速完成课设Java 或 Python 也能做但 Python 的性能在跑递归测试时可能偏慢。不管选什么语言核心数据结构就三个符号表、代码数组、栈。符号表用数组或链表都行代码数组就是一个指令列表栈用于虚拟机执行。把这三个结构定义清楚后面的代码就是填充逻辑。3. 词法分析器从字符流到 token 序列的完整实现3.1 状态机设计与关键字识别词法分析器的任务是把源程序的字符流切分成有意义的 token。PL/0 的 token 类型包括关键字const、var、procedure、begin、end、if、then、while、do、call、read、write、odd、标识符、数字、运算符、-、*、/、、、、、、、:和分隔符;、,、.、(、)。识别标识符和关键字可以用同一个函数先读入字母开头的字母数字串然后查关键字表如果在表里就是关键字否则是标识符。下面是一个用 C 实现的词法分析核心函数我把它简化成最直观的版本#include ctype.h #include string.h #include stdio.h #define MAX_IDENT_LEN 32 #define NUM_KEYWORDS 13 const char *keywords[NUM_KEYWORDS] { const, var, procedure, begin, end, if, then, while, do, call, read, write, odd }; // token 类型枚举 typedef enum { TOK_IDENT, TOK_NUMBER, TOK_PLUS, TOK_MINUS, TOK_TIMES, TOK_SLASH, TOK_EQ, TOK_NEQ, TOK_LT, TOK_LE, TOK_GT, TOK_GE, TOK_ASSIGN, TOK_SEMI, TOK_COMMA, TOK_PERIOD, TOK_LPAREN, TOK_RPAREN, TOK_CONST, TOK_VAR, TOK_PROCEDURE, TOK_BEGIN, TOK_END, TOK_IF, TOK_THEN, TOK_WHILE, TOK_DO, TOK_CALL, TOK_READ, TOK_WRITE, TOK_ODD, TOK_EOF, TOK_ERROR } TokenType; typedef struct { TokenType type; char name[MAX_IDENT_LEN]; int value; } Token; // 从文件中读取下一个 token Token get_token(FILE *fp) { Token tok; int ch; // 跳过空白字符 while ((ch fgetc(fp)) ! EOF isspace(ch)); if (ch EOF) { tok.type TOK_EOF; return tok; } // 标识符或关键字 if (isalpha(ch)) { int len 0; tok.name[len] ch; while ((ch fgetc(fp)) ! EOF isalnum(ch)) { if (len MAX_IDENT_LEN - 1) tok.name[len] ch; } tok.name[len] \0; ungetc(ch, fp); // 多读的字符放回 // 查关键字表 for (int i 0; i NUM_KEYWORDS; i) { if (strcmp(tok.name, keywords[i]) 0) { tok.type TOK_CONST i; // 假设枚举顺序与关键字表一致 return tok; } } tok.type TOK_IDENT; return tok; } // 数字 if (isdigit(ch)) { int val ch - 0; while ((ch fgetc(fp)) ! EOF isdigit(ch)) { val val * 10 (ch - 0); } ungetc(ch, fp); tok.type TOK_NUMBER; tok.value val; return tok; } // 运算符和分隔符 switch (ch) { case : tok.type TOK_PLUS; break; case -: tok.type TOK_MINUS; break; case *: tok.type TOK_TIMES; break; case /: tok.type TOK_SLASH; break; case : tok.type TOK_EQ; break; case : ch fgetc(fp); if (ch ) tok.type TOK_LE; else if (ch ) tok.type TOK_NEQ; else { ungetc(ch, fp); tok.type TOK_LT; } break; case : ch fgetc(fp); if (ch ) tok.type TOK_GE; else { ungetc(ch, fp); tok.type TOK_GT; } break; case :: ch fgetc(fp); if (ch ) tok.type TOK_ASSIGN; else { tok.type TOK_ERROR; } break; case ;: tok.type TOK_SEMI; break; case ,: tok.type TOK_COMMA; break; case .: tok.type TOK_PERIOD; break; case (: tok.type TOK_LPAREN; break; case ): tok.type TOK_RPAREN; break; default: tok.type TOK_ERROR; break; } return tok; }这段代码的逻辑很直接先跳过空白然后根据首字符判断是标识符、数字还是符号。标识符读取时用ungetc把多读的一个字符放回这是递归下降分析器的常见技巧因为词法分析器不知道语法分析器什么时候需要下一个 token。关键字识别用线性查找13 个关键字对性能没影响。参数方面MAX_IDENT_LEN设为 32 足够 PL/0 使用NUM_KEYWORDS必须和关键字数组长度一致否则会越界。3.2 错误处理非法字符和数字溢出的应对词法分析阶段最常见的错误是遇到非法字符比如或#。上面的代码里遇到无法识别的字符会返回TOK_ERROR但更好的做法是记录错误位置和错误类型然后跳过该字符继续分析这样一次编译能报出多个错误。数字溢出也要考虑PL/0 的整数范围通常是 16 位有符号如果输入的数字超过 32767应该报错而不是静默截断。我一般会在数字解析时加一个检查if (val 32767) { fprintf(stderr, Error: number %d exceeds limit at line %d\n, val, line); tok.type TOK_ERROR; }另外注释的处理容易被忽略。PL/0 标准语法里注释是用{ ... }或(* ... *)包裹的词法分析器需要跳过注释内容。如果注释没有闭合要报错并指出起始位置。这个细节在课设测试用例里经常出现漏掉会直接导致解析失败。4. 语法分析与符号表递归下降的代码骨架和填表时机4.1 为每个非终结符写一个函数递归下降的核心思想是每个非终结符对应一个函数函数根据当前 token 决定展开哪条产生式。PL/0 的语法可以用 EBNF 描述比如program block . ; block [ const ident number { , ident number } ; ] [ var ident { , ident } ; ] { procedure ident ; block ; } statement ; statement [ ident : expression | call ident | begin statement { ; statement } end | if condition then statement | while condition do statement | read ident | write ident ] ;对应的函数就是parse_program、parse_block、parse_statement等。每个函数开头检查当前 token 是否符合预期不符合就报错。比如parse_statement里遇到TOK_IDENT就继续解析赋值语句遇到TOK_CALL就解析过程调用遇到TOK_BEGIN就循环解析语句直到TOK_END。这里的关键是「向前看一个 token」在进入函数之前当前 token 已经由词法分析器读出来了函数内部根据这个 token 决定分支。分支确定后再调用next_token读取下一个 token。这种模式要求词法分析器和语法分析器紧密配合不能一次性读完所有 token。4.2 符号表的栈式管理与作用域链符号表是编译器的记忆。PL/0 允许过程嵌套所以符号表必须支持多层作用域。我一般用一个数组模拟栈每个元素是一个符号记录同时维护一个scope_start数组记录每层作用域的起始下标。进入过程时把当前符号表长度压入scope_start退出时弹出并截断符号表。符号记录的结构如下typedef struct { char name[MAX_IDENT_LEN]; int kind; // 0常量, 1变量, 2过程 int type; // 0整数PL/0 只有整数 int level; // 所在层级 int value; // 常量值 int addr; // 变量地址或过程入口地址 } Symbol;查找符号时从当前作用域往外层找找到第一个匹配的就返回。如果找不到说明使用了未声明的标识符报错。这里有个坑过程名和变量名可以重名但 PL/0 不允许在同一作用域内重名。所以插入符号前要先检查当前作用域是否已有同名符号。4.3 常量定义、变量声明和过程声明的处理差异常量定义时符号表里记录kind0和具体的value。变量声明时kind1addr是相对于当前过程基址的偏移每声明一个变量偏移加 1。过程声明时kind2addr是过程入口的代码地址但入口地址在代码生成阶段才能确定所以通常先填一个占位符等过程体生成完再回填。过程声明还有一个特殊之处过程名本身要在外层作用域可见但过程体内的符号属于内层作用域。所以处理procedure时先在当前作用域插入过程名然后进入新作用域处理过程体处理完再退出作用域。这样递归调用时内层可以看到外层的过程名但外层看不到内层的变量。5. 代码生成与虚拟机P-code 指令序列的生成规则5.1 表达式求值的栈式代码生成PL/0 的表达式只有整数运算所以代码生成很简单遇到常量就生成LIT遇到变量就生成LOD遇到运算符就生成对应的OPR。比如a b * c会生成LOD 0 a LOD 0 b LOD 0 c OPR 4 ; 乘法 OPR 2 ; 加法这里OPR的参数是运算码通常定义如下1加法2减法3乘法4除法5取模6等于7不等于8小于9大于等于10大于11小于等于12逻辑非odd。注意栈式代码生成是后序遍历表达式树所以先加载左操作数再加载右操作数最后生成运算符指令。5.2 条件跳转与循环的回填技术if和while语句需要生成跳转指令但跳转目标地址在生成时还不知道所以要用「回填」技术先填一个占位地址比如 0等目标确定后再修改。比如if condition then statement的代码结构是condition 的代码 JPC 0 ; 条件为假时跳转到 else 或 end statement 的代码 ; 回填 JPC 的目标地址为当前位置while循环类似但需要在循环开始处记录地址循环结束后生成JMP跳回开始处。回填的时候要注意代码数组的下标别填错了位置。5.3 过程调用与栈帧布局过程调用涉及栈帧的创建和销毁。调用时CAL指令会保存返回地址、当前基址然后跳转到过程入口。过程入口处生成INT指令分配局部变量空间。返回时用RET恢复基址和返回地址。栈帧的布局通常是参数、返回地址、旧基址、局部变量。PL/0 的过程没有参数所以栈帧更简单但递归调用时仍然需要正确的基址链。虚拟机执行 P-code 时用一个栈和一个指令指针。每条指令从代码数组中取出根据操作码执行相应动作。比如LIT把参数压栈LOD根据层级差和偏移找到变量地址并压栈STO弹出栈顶存入变量。虚拟机的实现大约 200 行代码但调试时容易在层级差计算上出错建议每执行一条指令就打印栈状态方便追踪。6. 避坑与排查PL/0 编译器实现中的五个血泪教训6.1 符号表作用域没弹出导致变量重复定义现象编译一个包含多个过程的程序时报「变量重复定义」但源程序里明明没有重名。原因进入过程时压入了新作用域但退出时忘记弹出导致下一个过程的变量被插入到上一层作用域和外层变量冲突。解决在parse_block函数退出前必须把符号表截断到进入时的长度。我习惯在进入时保存symbol_table_len退出时直接赋值回去。6.2 回填地址时偏移算错导致跳转飞掉现象if或while语句执行时跳转到错误的指令程序行为完全混乱。原因回填时填的是代码数组的下标但生成跳转指令时可能多生成了一条指令导致下标偏移。解决每次生成跳转指令后立即记录当前代码数组长度回填时用这个长度减去 1 作为目标地址。最好写一个emit函数统一管理代码生成避免手动计算下标。6.3 递归下降中 token 超前读取导致解析错位现象解析到某个语句时突然报「意外的 token」但源程序语法没问题。原因在某个分支里多调用了一次next_token导致当前 token 跳过了应有的内容。解决严格遵循「进入函数时当前 token 已就绪分支确定后再读下一个」的原则。可以在每个函数入口打印当前 token方便定位。6.4 虚拟机栈溢出或下溢现象执行 P-code 时程序崩溃或者结果完全不对。原因LOD或STO的层级差计算错误导致访问了不存在的栈位置或者INT分配的空间不够局部变量覆盖了返回地址。解决在虚拟机里加边界检查每次压栈前检查栈是否满弹栈前检查是否空。层级差的计算公式是当前层级 - 变量层级别搞反了。6.5 错误恢复缺失导致一个错误报出几十条现象源程序有一个拼写错误编译器却报了几十条错误根本看不出真正的问题。原因语法分析器遇到错误后没有跳过任何 token导致同一个错误被反复触发。解决在报错后至少跳过一个 token或者跳到下一个分号再继续。PL/0 的分号是语句分隔符跳到分号通常能恢复到一个合理的同步点。7. 进阶技巧用测试用例反推编译器行为课设的测试用例通常包括常量定义、变量声明、嵌套过程、递归调用、条件分支、循环、读写语句以及各种错误情况。我建议先写一个最小的测试程序比如只包含begin write(1) end.确保能跑通然后逐步增加复杂度。每增加一个特性就写一个对应的测试用例观察 P-code 输出是否符合预期。一个很实用的技巧是把 P-code 反汇编成可读的文本和源程序对照。比如LIT 1对应常量 1OPR 14对应写操作。这样调试时能快速定位是哪条指令生成错了。另外虚拟机的执行轨迹可以打印出来每执行一条指令就输出指令和栈状态虽然输出量大但能精确找到出错的那一步。我当年做这个课设时最大的教训是不要等到全部写完再调试。每实现一个模块就单独测试词法分析器用几个 token 序列验证语法分析器用简单语句验证代码生成用表达式验证。这样出错时范围很小容易定位。希望帮到你。本文还有配套的精品资源点击获取