用C语言实现PL/0教学编译器：递归下降与P-code虚拟机全解析

简介：PL/0语言编译程序是计算机科学家N.Wirth设计的经典教学模型，这份C语言版源码完整实现了其词法分析、语法分析、语义处理与目标代码生成等核心模块，适合编译原理课程学习者、高校师生及自学读者对照教材逐行研读，也可作为课程设计或实验扩展的参考基础。压缩包共2个文件，其中c源码文件包含全部编译流程的实现代码，头文件提供必要的数据结构与接口定义，整体大小仅11KB，结构非常精简，便于快速下载与阅读。目前已有1208人学习浏览，是编译原理入门阶段的高性价比参考资料。通过阅读这份源码，读者可以直观理解递归下降分析、符号表管理、中间代码生成等关键技术的实际写法，同时还能学习如何将一个功能完整的小型编译器组织在单一源文件中，对提升代码阅读与调试能力大有帮助。

1. 把「编译器」从黑匣子变成看得见的东西：这个 C 语言版 PL/0 到底能干什么

编译原理课上最典型的挫败感是：递归下降、LL(1)、语义动作这些概念听懂了，但关上书自己写一个能跑的词法分析器都费劲。PL/0 编译程序 C 语言版就是来消解这种挫败感的——它是一个五脏俱全但代码量极小的教学编译器，输入简化版 Pascal 语言 PL/0 源程序，经过词法分析、递归下降语法分析、符号表管理和目标代码生成，输出一套类 P-code 的中间指令，再交给内置的虚拟机解释执行。整个过程从源码到输出，所有中间产物全部暴露在你眼前。适合两类人：正在啃编译原理、被教材上的抽象算法绕晕的学生，以及想快速搞明白「编译器前端到后端怎么串起来」的开发者。跑通一个阶乘程序，你就能亲手把编译器的整条链路摸一遍。

2. 工程结构：单遍编译 + 递归下降 + P-code 虚拟机，三个关键词看懂设计

2.1 为什么是 C 语言 + 单遍编译 + 递归下降

PL/0 源码包使用纯 C 实现，这不是偶然。C 语言对内存和指针的控制能力让符号表、指令数组、取址操作都贴近编译器底层的真实运作方式，而且不需要任何运行时依赖，gcc 一条命令就能编译出可执行文件，对教学场景几乎零门槛。

设计上有三个关键决策。第一是单遍编译：编译器只扫描一遍源程序，词法分析、语法分析、语义动作和目标代码生成在同一次扫描中完成。这意味着读到一条if语句时，语法分析器当场就能生成对应的跳转指令，不需要 AST 中间表示。省内存、直观、贴近老派编译器的做法，缺点是语言特性必须足够简单——PL/0 这个体量正好适配。第二是递归下降分析：每个语法成分对应一个函数，block调statement，statement调condition、expression，层层嵌套，代码结构和文法规则几乎一一对应，想定位一个语法的处理逻辑，直接找同名函数就行。第三是目标代码不落到真实机器指令，而是生成一种为教学设计的 P-code 指令集，再用一个解释循环逐条执行。这样避免引入具体 CPU 架构的复杂度，把「编译」和「执行」两个层次干净地分开。

2.2 目录结构和模块职责

这份源码包解压后，典型的结构是这样的：

pl0/ ├── pl0.h // 常量定义、错误码、符号表与指令结构体 ├── pl0.c // 主程序入口，负责命令行解析和整体调度 ├── lex.c // 词法分析器：字符流 -> 符号流 ├── parse.c // 语法分析与语义动作：符号流 -> P-code ├── symbol.c // 符号表管理：登记、查找、层级计算 ├── interp.c // P-code 虚拟机：逐条解释执行指令 ├── test.pl0 // 自带测试用例，通常是一个阶乘或者求最大公约数的程序 └── Makefile // 可选的构建脚本

每个模块的职责边界非常干净，我在表里把关键点列一下：

这里有个很值得新手注意的细节：parse.c并没有单独生成 AST 再遍历生成代码，而是在递归下降的过程中直接调用gen()往指令数组写入 P-code。这意味着语法分析函数同时承担了语义分析和代码生成的双重职责，代码量大幅减少，代价是你必须理解「分析到哪，代码就生成到哪」的单遍编译思维方式。

2.3 一条源程序语句从进入源码到输出结果的完整链路

以a := b + 2这条赋值语句为例，数据是这样流动的：lex.c从源文件读入字符a、:、=、b、+、2，逐个拼出ident、becomes、ident、plus、number五种符号；parse.c的statement函数识别到ident开头，知道是赋值语句，调用expression分析赋值号右侧；右侧的expression又下推给term、factor，factor遇到b查符号表拿到它的层级和偏移地址，生成LOD l,a指令，遇到数字2生成LIT 0,2；等expression归约完，最外层的statement生成STO l,a把栈顶值存回a的地址。

这几条指令被依次放进全局的code[]数组后，控制权交给interp.c。虚拟机维护一个操作数栈和 display 链，一条条取指令执行：LIT把 2 压栈，LOD取出变量b的值压栈，OPR 0,2做加法，STO把结果写回a。整个过程就是一个循环：取指、解码、执行、PC 加一。你只要跟着一台调试器单步走一遍，就能同时看到「编译期产生了什么」和「运行期执行了什么」两边的完整状态。

3. 核心代码拆解：从字符到 P-code，编译器工作现场长什么样

3.1 词法分析：getsym 如何把字符流切成符号流

词法分析是整个编译器最机械的部分，但也是新手最容易写脏的部分。PL/0 的getsym用全局字符变量ch作为当前读入字符，逐个从输入流取字符并拼出符号。核心逻辑是先跳过空白，然后按首字符分类：字母开头走标识符/保留字分支，数字开头走常数分支，其余走运算符分支。

int getsym() { int i, j; while (ch == ' ' || ch == '\t' || ch == '\n') getch(); // 跳过空白字符 if (ch >= 'a' && ch <= 'z') { // 标识符或保留字 i = 0; do { if (i < 9) symname[i++] = ch; // 名字截断到 9 个字符 getch(); } while ((ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')); symname[i] = '\0'; for (j = 0; j < NORW; j++) if (strcmp(symname, word[j]) == 0) { sym = wsym[j]; // 命中保留字表 return 0; } sym = ident; // 否则是变量/过程名 return 0; } if (ch >= '0' && ch <= '9') { // 数字常量 num = 0; do { num = num * 10 + (ch - '0'); getch(); } while (ch >= '0' && ch <= '9'); sym = number; return 0; } switch (ch) { case ':': getch(); if (ch == '=') { sym = becomes; getch(); } // := 赋值号 else sym = nul; // 单独的 : 非法 break; case '+': sym = plus; getch(); break; case '-': sym = minus; getch(); break; case '(': sym = lparen; getch(); break; case ')': sym = rparen; getch(); break; default: sym = nul; getch(); break; // 无法识别的字符 } return 0; }

这段代码三个参数细节值得说明。第一是i < 9的截断保护：标识符数组只留 10 个字节（9 个字符加结尾\0），超长名字直接丢弃尾部字符，这是经典实现为了省内存的做法，但也意味着两个前 9 位相同的变量会被视为同一个符号，后面避坑章节会再提到。第二是保留字判断策略：先把读到的字符拼成字符串，再和word[]保留字表逐一比较，命中就返回对应的符号类型，否则归为ident。自然语言里叫「先认定为标识符，再回头查保留字」。第三是becomes这个符号：PL/0 赋值号是:=，getsym必须读进:后再预读一个字符，判断是不是=，只有两个字符连续出现才算是合法的赋值符号，这是两个字符运算符的通用处理模板。

3.2 递归下降核心：block 函数如何串起声明和语句

block是 PL/0 编译器的骨架函数，对应文法的「程序块」产生式。它负责处理常量声明、变量声明、过程声明，最后分析语句序列。过程声明可以嵌套，因此block自己递归调用自己，这是整个编译器递归结构最明显的一层。

void block(int lev, int tx) { int tx0 = tx; // 记录进入本层前的符号表指针 table[tx].adr = cx; // 当前指令地址记入符号表 gen(JMP, 0, 0); // 先占位生成一条跳转，跳过过程体 // ---- 声明部分 ---- if (sym == constsym) { // 常量声明 const a=1, b=2; getsym(); while (sym == ident) { strcpy(table[tx].name, symname); getsym(); if (sym == becomes) getsym(); if (sym == number) { table[tx].kind = 0; // 常量 table[tx].val = num; tx++; getsym(); } if (sym == comma) getsym(); // 逗号分隔多个常量 else break; } if (sym == semicolon) getsym(); } // 变量声明 var 部分的处理逻辑与常量类似，kind 置为 1，这里省略 while (sym == proceduresym) { // 过程声明 procedure name; block; ; getsym(); if (sym == ident) { strcpy(table[tx].name, symname); table[tx].kind = 2; // 过程 getsym(); } if (sym == semicolon) getsym(); block(lev + 1, tx + 1); // 递归分析嵌套过程体 if (sym == semicolon) getsym(); } // ---- 语句部分 ---- code[table[tx0].adr].a = cx; // 回填开头的 JMP，跳过声明区直接到语句 if (sym == beginsym) { getsym(); statement(tx); while (sym == semicolon) { getsym(); statement(tx); } if (sym == endsym) getsym(); else error(5); // 缺少 end } }

这段代码里最重要的动作是那条gen(JMP, 0, 0)。PL/0 程序块的执行顺序是：先执行语句部分，过程体只有在被call调用时才进入。但源码的书写顺序是声明在前、语句在后，编译源码时cx（指令指针）会先走到声明区。为了运行时能跳过声明区，block一开始就在当前位置生成一条占位跳转，等语句部分分析完，再把这条跳转的目标地址回填为语句的起始指令地址code[table[tx0].adr].a = cx。这就是「回填」技术的典型应用，教材上用一张表解释半天，看这一行代码就懂了。

另一个值得注意的点是lev和table[tx].adr的配合。每个过程的符号表项记录它在指令数组中的起始位置，CAL指令调用过程时，虚拟机只需要跳到这个地址就能进入过程体。嵌套过程的lev逐层加一，运行期 display 表同样逐层映射，符号表、指令地址、运行期层级三者完全对应，这是 PL/0 简洁得近乎优雅的地方。

3.3 语句分析：if、while、read、write 的代码生成现场

statement函数是编译器里分支最多的函数，每个语法成分对应一个 case。它做两件事：一是继续递归下降分析下一个语法成分，二是在分析过程中调用gen生成可执行指令。看if语句的实现最能理解「语义动作嵌入语法分析」的设计思路。

void statement(int tx) { int cx1, cx2; switch (sym) { case ident: // 赋值语句 position(symname); // 在符号表里找变量 getsym(); if (sym == becomes) { getsym(); expression(tx); // 分析右侧表达式，生成求值指令 gen(STO, lev - table[ix].level, table[ix].adr); // 存回变量 } break; case ifsym: getsym(); condition(tx); // 生成条件求值指令，栈顶留下 0/1 cx1 = cx; // 记录跳转指令位置 gen(JPC, 0, 0); // 条件为假时跳转 statement(tx); // 分析 then 后的语句 code[cx1].a = cx; // 回填：假时跳到这里 break; case callsym: getsym(); if (sym == ident) { position(symname); gen(CAL, lev - table[ix].level, table[ix].adr); getsym(); } break; case readsym: getsym(); // 跳过 read 关键字 if (sym == lparen) getsym(); if (sym == ident) { position(symname); gen(OPR, 0, 14); // 读入一个数压栈 gen(STO, lev - table[ix].level, table[ix].adr); getsym(); } if (sym == rparen) getsym(); break; case writesym: getsym(); // 跳过 write 关键字 if (sym == lparen) getsym(); expression(tx); // 计算要输出的值 gen(OPR, 0, 15); // 弹出栈顶并打印 if (sym == rparen) getsym(); break; } }

这段代码最值得反复看的是cx1和回填。GEN JPC 0 0生成时跳转目标未知，只能先写 0 占位，记下它在code[]数组里的下标cx1。等statement递归分析完 then 后面的语句，cx已经指向下一条可用的指令位置，此时把code[cx1].a赋值为cx，假分支的跳转目标就确定了。如果你手动把if改成while，逻辑几乎一样，区别是while需要在条件分析之前记录循环体起始地址，再在循环体结束时生成一条JMP跳回循环起点——这就是循环结构代码生成的全部秘密。

OPR 0,14和OPR 0,15这种魔数也很典型。它们不是通用算术运算，而是为 read/write 这类输入输出操作预留的功能码。虚拟机的解释循环看到特定OPR值时，直接从终端读整数或向终端打印整数，相当于把系统调用藏进了中间指令里。

4. 编译与运行：从源码到执行，亲手把 PL/0 程序跑起来

4.1 编译环境和构建命令

这份源码完全不依赖第三方库，环境只要有一个 C 编译器。Linux/macOS 用系统自带的 gcc，Windows 装 MinGW 或直接用 Dev-C++ 都能编过。我习惯在命令行下这样编译：

gcc -o pl0 pl0.c lex.c parse.c symbol.c interp.c -std=c99 -Wall

-std=c99是因为源码里大量在循环内声明变量，这是 C99 的语法特性，不加这个参数旧版本编译器会报一堆 warning。-Wall建议加上，源码里有些未使用的变量和函数返回值告警，正好可以作为排查代码质量的辅助线索。

编译产物是可执行文件pl0。运行方式分两种：带调试信息输出和不带。不带调试参数直接执行，程序等待你从终端输入源程序文本；更常见的做法是准备一个 .pl0 文件重定向输入：

./pl0 < test.pl0

如果想要编译器输出生成的 P-code 指令清单，可以加调试开关参数，不同版本的源码开关不太一样，有的看pl0 -l test.pl0，有的直接编译时把list变量置 1。建议先把 list 打开跑一次，你会看到比预期多得多——每条源语句对应好几条指令，看着它们成排出现，编译器这层黑匣子就透明了一大半。

4.2 用阶乘程序验证整条链路

先创建测试文件fact.pl0。PL/0 的语法不支持数组、不支持函数返回值，过程只通过全局变量交换数据，这个约束影响不大：

var n, f, m; begin read(n); m := n; f := 1; while m > 1 do begin f := f * m; m := m - 1 end; write(f) end.

运行：

./pl0 < fact.pl0

输入5，输出120。这里注意一个细节：PL/0 的read期望一条输入对应一个数，终端输入5后按回车，词法分析器的getch函数逐字符读取时需要跳过换行符，这部分在不同平台上有差异，踩坑章节会专门展开。如果输出正确，说明词法、语法、符号表、代码生成到虚拟机整条链路都已经打通。

若想看编译器生成的中间指令长什么样，开启调试输出后你会看到类似这样的清单：

1 JMP 0 14 2 INT 0 5 3 LIT 0 0 4 STO 0 3 5 OPR 0 14 6 STO 0 3 ...

其中INT 0 5是在栈上给局部变量分配 5 个槽位，OPR 0 14是读入操作。对照指令表逐条看，变量读取、乘法、比较、跳转的每一步都是可追踪的。

4.3 解释器主循环：虚拟机如何逐条执行 P-code

理解了编译器怎么生成指令，剩下的半壁江山是解释器怎么执行。interpret的核心是一个大switch，根据指令的功能码分派动作，维护一个操作数栈和 display 数组。

void interpret() { int pc = 0; // 指令指针 int top = 0; // 栈顶指针 int f, l, a; stack[0] = 0; // 最外层静态链 do { f = code[pc].f; l = code[pc].l; a = code[pc].a; pc++; // 取指后立即指向下一条 switch (f) { case LIT: stack[++top] = a; // 常量压栈 break; case LOD: stack[++top] = stack[base(l) + a]; // 取指定层级变量 break; case STO: stack[base(l) + a] = stack[top]; // 栈顶写回变量 top--; break; case JMP: pc = a; // 无条件跳转 break; case JPC: if (stack[top] == 0) pc = a; // 栈顶为假才跳 top--; break; case OPR: if (a == 0) { // 过程返回 top = base(l) - 1; pc = stack[top + 3]; } else if (a == 2) { stack[top - 1] = stack[top - 1] + stack[top]; // 加法 top--; } else if (a == 7) { // 等于比较 stack[top - 1] = (stack[top - 1] == stack[top]); top--; } // 其余 OPR 功能码：减法、乘法、小于等在此展开 break; } } while (pc != 0); }

解释循环就这么短，但它把编译原理里「运行时存储组织」的几个抽象概念全落地了。base(l)是静态链查找函数，它沿着 display 数组往上找第 l 层的基地址，对应变量访问的LOD/STO指令里的层级参数。过程返回的OPR 0恢复栈顶到调用前的基地址，同时从栈里取出返回地址赋给pc，这段就是教科书里「过程调用的活动记录」的具体实现。你把CAL指令的执行过程在纸上画一遍栈的变化，活动记录那章就不用背了。

5. 避坑与排查：PL/0 源码跑不通的 5 个真实问题

5.1 现象：read 读到的数字不对，或者根本没读进去

把阶乘程序重定向进pl0后，有时候输入5直接输出0，或者在 Windows 下程序像卡死了一样不动。原因在getch函数：它用getchar()逐字符读取，但回车是一个\r一个\n两个字符，\r被当成普通字符进入了词法分析，数字拼接逻辑当场翻车。Linux 下只有\n所以没事，Windows 下\r就成了隐形杀手。解决方式是在getch里跳过回车：

void getch() { ch = getchar(); if (ch == '\r') ch = getchar(); // 统一忽略回车 }

从那以后我在这个函数的每个版本里都默认补上这一行，成了改不掉的肌肉记忆。

5.2 现象：标识符名字太长导致两个变量变成同一个符号

源码里写temperature和temporary两个变量，编译器不报错，但运行时发现改一个另一个也变。原因是词法分析器截断名字时只保留前 9 个字符，这两个词前 9 位相同，查符号表时被判定为同一个标识符。解决方式分两层：短期是变量名控制在 9 字符以内，长期是修改getsym里的截断逻辑，把symname数组长度加大，同时把符号表name字段的长度一并加大。这是 PL/0 教学版为了省内存做的妥协，真实项目里几乎没有这种限制。

5.3 现象：递归过程调用层数一深，解释器直接崩掉

过程在运行时每次调用都要在栈上压入活动记录，PL/0 的虚拟机栈默认只有几百个槽位，递归深度超过这个量就数组越界。现象是程序运行到一半崩溃，或输出一个明显不对的数值。解决方式是把stack[STACKSIZE]的容量调大，比如从 500 改到 5000。更深层的排查点在base()函数：如果level参数传错，display 数组访问也会越界，这类问题表现为「为什么改了数组大小还崩」，此时要回头查CAL指令的l参数是否等于当前层减目标过程层。

5.4 现象：if 逻辑完全反了，条件成立却跳过了语句

写if a > b then ...，调试时发现明明a > b，语句体却不执行。问题出在JPC的语义理解：JPC是「条件为假才跳转」，而条件求值的结果是栈顶的 0/1。如果你习惯性把JPC当成「条件为真跳转」，就会在生成代码时把JPCI或JMP用混。排查方法是回到condition函数看它生成的比较指令：PL/0 的OPR比较指令会把逻辑值压栈，真为 1 假为 0，然后由JPC消费。这一步搞反的人很多，因为英文字面上Jump if Condition容易被理解成「条件满足就跳」，实际语义要看指令表的完整定义。

5.5 现象：生成的指令清单里 JMP 全是 0 0，没有回填

开启调试输出后，发现有些JMP 0 0后面没被改成有效地址。最常见的原因在block开头的占位跳转：如果过程声明的分号处理有误，语句分析结束后回填代码没执行到。排查先看code[table[tx0].adr].a = cx;这条语句所在的位置，确认它在语句分析结束后无条件执行；再检查statement结尾是否错误地消耗了多余的分号，导致block提前返回。这类问题常常表现为「编译器不报错，但运行时行为诡异」，因为跳转到地址 0 等于重启解释器。

6. 二次开发实战：给 PL/0 加上 else 分支的完整改法

如果你想验证自己真的看懂了这套源码，最直接的练习是给语言加一个else。PL/0 原版的if只有 then 分支，条件为假直接跳到endif之后的语句。加上else需要改三处：词法、语法、代码生成回填逻辑。

词法分析这步最简单，在word[]保留字表里加一行else，并分配一个新的符号枚举值elsesym。

// 词法表新增 {"else", elsesym},

语法和代码生成是重头戏。原来的if生成一条JPC跳向 then 结束处，现在需要两条跳转指令配合：

case ifsym: getsym(); condition(tx); // 条件求值，栈顶留下 0/1 cx1 = cx; gen(JPC, 0, 0); // 假：跳到 else 分支或 endif statement(tx); // 真：执行 then 语句 if (sym == elsesym) { getsym(); cx2 = cx; gen(JMP, 0, 0); // then 执行完跳过 else 块 code[cx1].a = cx; // 回填：假跳到这里进入 else statement(tx); // 执行 else 分支 code[cx2].a = cx; // 回填：then 逃逸到 endif } else { code[cx1].a = cx; // 无 else，直接回填 endif } break;

这段改法的关键是理解两个回填点。cx1是假跳转指令的位置，cx2是真分支结束时无条件跳转的位置。当then分支执行完，程序必须跳过else块直接到整个if语句的出口，所以需要一条额外的JMP。回填顺序也有讲究：先回填cx1指向 else 块首条指令，再分析 else 分支，最后回填cx2指向整条 if 语句的下一条指令。改完后用刚才的阶乘程序做回归，再写一个if x > 0 then write(1) else write(2)的用例验证两个方向都输出正确。

走过这一次完整的改动，你会对递归下降的「遇文法则调函数，生成指令忙回填」有肌肉记忆。从那以后我每次维护这类教学编译器，都强制自己先把指令回填表列出来再动代码，改完再用边界输入跑一遍回归。PL/0 这个小体量项目，正好是练习这套方法论成本最低的试验场，希望帮到你。

本文还有配套的精品资源，点击获取