尧图网页设计 
简介山东大学SDU编译原理课程PL/0编译器实验的完整实现包面向高校计算机专业学生及编译原理学习者适合作为课程实验参考、复习与二次开发基础。资源包含完整的C/C源代码.cpp/.h/.c、CMake构建脚本、测试用例.in/.out及编译产物.obj/.exe并附有实验报告与多张运行截图系统覆盖词法分析、语法分析BNF/EBNF文法、语义分析、符号表管理等编译器前端核心环节部分源码还涉及中间表示与目标代码生成的实现思路。压缩包共94个文件总大小约513KB虽然包含out、txt、png、cmake等多种类型但目录结构清晰便于按模块查阅和重新构建。目前已有104人学习下载适合需要完成类似PL/0实验或想深入掌握编译器前端原理的学生能提供从文法设计到代码落地的完整参考。1. PL0-Compiler是什么一门能被“写出来”而不是“读出来”的编译原理课很多学校的编译原理课理论部分能把递归下降、LR分析表、语法制导翻译推到黑板上但一进实验课学生面对的是另一道题写一个能编译、能执行的小型编译器。PL0-CompilerPL/0编译器就是这类课程实验最常见的载体山东大学SDU编译原理课程实验用的也正是这套方案用一门极小语言PL/0从零手写词法分析、语法分析、语义分析和目标代码解释执行最后产出一个可运行的编译器加一份实验报告。它解决的问题很具体让“编译原理”这四个字从一个黑匣子变成一条你能单步调试、敢说“每一行都是我写的”的流水线。适合正在上编译原理课、需要交付可运行程序和报告的学生也适合想补手写编译器基本功的从业者。2. 先定文法再落代码PL0的语法骨架与SDU课程实验的工程划分2.1 PL/0语言到底有多“小”从产生式看这门语言边界在哪PL/0是Niklaus Wirth在《Algorithms Data Structures Programs》里定义的教学语言整套语法只有十几条产生式。你别嫌它小它保留了高级语言最核心的东西常量定义、变量声明、嵌套过程声明、表达式、赋值、条件分支、循环、过程调用和输入输出。先看核心文法这是整个实验的“宪法”program :: block . . block :: [const decl] [var decl] {procedure decl} statement . const decl :: const ident number {, ident number} ; . var decl :: var ident {, ident} ; . procedure decl :: procedure ident ; block ; . statement :: [ident : expression | call ident | begin statement {; statement} end | if condition then statement | while condition do statement | read ( ident ) | write ( expression ) | ε] . condition :: odd expression | expression relop expression . expression :: [|-] term {(|-) term} . term :: factor {(*|/) factor} . factor :: ident | number | ( expression ) . relop :: | # | | | | .注意两点。第一PL/0没有负数字面量负号是作为表达式的单目前缀出现的这意味着词法分析器里不需要处理“负数”这个token一切负数在语法层被拆成“0减正数”或“取负操作”。第二不等于号是#不是!。这两点看似不起眼却是后面最常见的翻车点。这门语言没有数组、没有自定义类型、没有返回值概念过程调用靠全局变量通信所以实验的工作量被控制在一个学期能完成的范围词法分析约150行递归下降语法分析约300行代码生成和解释器约300行加起来一千行左右正好是一份课程实验报告该有的体量。2.2 课程实验的常见交付物四个模块与一张指令集对照表SDU这类编译原理课程实验的验收口径一般是能编译PL/0源码输出中间代码或直接解释执行且报告里要有设计说明、流程图、测试用例。常见做法是把编译器拆成四个模块顺序严格执行前一个模块的输出是后一个模块的输入。词法分析把源码字符串切成token序列token类型包括保留字、标识符、数字和特殊符号。语法分析用递归下降法按产生式逐层下降同时做语法错误检查与恢复。语义分析与代码生成PL/0实验里这两步不分离语法分析过程中直接查符号表、输出类Pascal虚拟机指令。解释执行用C语言模拟一个栈式虚拟机执行生成的指令序列。这四个模块对应到代码上就是五个文件或五个函数块。最关键的接口是中间代码的格式PL/0虚拟机指令是经典的三字段结构指令作用参数说明LIT 0,a将常数a压栈a为立即数LOD l,a将层差l、偏移a的变量值压栈l为层差a为栈内偏移STO l,a将栈顶值弹入层差l、偏移a的变量赋值操作CAL l,a调用层差l处的入口a过程进入过程前要建活动记录INT 0,a栈顶指针加a为局部变量腾出空间JMP 0,a无条件跳转到a用于while回跳JPC 0,a栈顶为假时跳转到a用于while和ifOPR 0,op执行运算或子程序返回op为运算子码其中OPR的子码是整个虚拟机的“运算大管家”OPR子码操作OPR子码操作0过程返回9奇数判断ODD1取负10等于2加11不等于3减12小于4乘13小于等于5除14大于6~8保留未用15大于等于16read读入17write输出这张表就是整个实验的“指令集手册”代码生成阶段的任务就是把语法分析过程中遇到的每个操作翻译成上面某一条指令。2.3 工程结构怎么摆源文件划分、全局变量分配和报告配合工程结构我建议直接按“单文件主程序清晰分节”来不建议一上来就拆多文件。PL/0编译器精华在逻辑不在架构单文件里用注释把词法、语法、解释器三个区域隔开调试时能省去头文件同步的麻烦。但全局变量的规划要提前想清楚这是很多人翻车的地方。我需要保留的全局状态有这么几个当前输入的字符ch、当前解析出的token类型sym、符号表tab、符号表当前指针tx、中间代码区code、代码区写入指针cx、当前过程层级level、当前过程中的变量偏移dx。符号表的设计是整个编译器的核心数据结构我建议结构体如下#define SYM_MAX 100 #define ALNX_MAX 10 #define CODE_MAX 500 typedef enum { nul, ident, number, plus, minus, times, slash, oddsym, eql, neq, lss, leq, gtr, geq, lparen, rparen, comma, semicolon, period, becomes, beginsym, endsym, ifsym, thensym, whilesym, dosym, callsym, constsym, varsym, procsym, readsym, writesym } SYMBOL; typedef struct { char name[ALNX_MAX]; // 名字 SYMBOL kind; // const / var / procedure int value; // const的值或var/procedure的地址 int level; // 层号过程嵌套深度 int addr; // 相对当前活动记录基址的偏移 int size; // 仅过程使用记录过程体局部空间大小 } TABLE;词法分析器往sym里填token类型语法分析器查符号表时用tx遍历解释器执行时靠level和addr定位变量。这一套设计是PL/0实验的通行做法照着这个结构写后面无论做扩展还是写报告都顺。报告部分重点放三张图整体流程图、递归下降调用关系图、虚拟机执行流程图。别放代码大段截图验收老师看的是“你有没有想清楚”不是“你复制了多少行”。3. 词法分析与语法分析把PL0源码变成Token流再变成调用树3.1 词法分析怎么实现保留字表、标识符与无符号数识别词法分析器的输入是PL/0源码文件输出是一个接一个的token。PL/0的token就四类保留字、标识符、数字、特殊符号。实现思路很简单先读一个字符跳过空白然后按首字符分类——字母开头走标识符/保留字分支数字开头走数字分支其余按符号映射。先看主逻辑代码这段我一般写成getSym函数void getSym(void) { int i, j; // 跳过空白 while (ch || ch \n || ch \t) nextch(); // 字母开头: 标识符或保留字 if (isalpha(ch)) { j 0; while (isalnum(ch) j ALNX_MAX - 1) { name[j] ch; nextch(); } name[j] \0; // 查保留字表 i 0; while (i NORW strcmp(keyword[i], name) ! 0) i; if (i NORW) sym wsym[i]; // 是保留字 else { sym ident; // 是普通标识符 // 同时可在此处查符号表决定是const/var/procedure } return; } // 数字开头: 无符号整数 if (isdigit(ch)) { num 0; while (isdigit(ch)) { num num * 10 (ch - 0); nextch(); } sym number; return; } // 特殊符号 switch (ch) { case : sym plus; nextch(); break; case -: sym minus; nextch(); break; case *: sym times; nextch(); break; case /: sym slash; nextch(); break; case (: sym lparen; nextch(); break; case ): sym rparen; nextch(); break; case ,: sym comma; nextch(); break; case ;: sym semicolon; nextch(); break; case .: sym period; nextch(); break; case #: sym neq; nextch(); break; case : sym eql; nextch(); break; case : nextch(); if (ch ) { sym leq; nextch(); } else sym lss; break; case : nextch(); if (ch ) { sym geq; nextch(); } else sym gtr; break; case :: nextch(); if (ch ) { sym becomes; nextch(); } else sym nul; // 单独冒号非法 break; default: sym nul; error(0); // 非法字符 nextch(); break; } }这段代码的逻辑重点有三个。第一nextch()负责读下一个字符并维护当前行号出错时报错信息能带行列号。第二标识符被读进全局name数组语法分析阶段查符号表时直接比对name即可。第三保留字表keyword里放的是begin call const do end if odd procedure read then var while write这13个词对应枚举wsym数组顺序必须一一对应否则const会被当成普通标识符。参数说明ALNX_MAX是标识符最大长度我设10够用超过会截断截断逻辑在循环条件里——j ALNX_MAX - 1。NORW是保留字个数13。数字累加时没做溢出保护PL/0实验不需要但你可以顺手加一个if (num 32767) error(5)。3.2 递归下降分析器的骨架factor、term、expression、statement语法分析采用递归下降法原因是PL/0的每个产生式都能对应一个同名函数代码结构跟文法一一映射出错位置也能直接定位到函数栈。整个分析器的入口是blockblock里按文法顺序调statementstatement里按语句类型分发到具体处理逻辑。下面这段是factor和statement的核心写法也是我认为最需要理解的递归下降代码void factor(void) { if (sym ident) { // 标识符: 变量或常量 int pos position(name); if (pos 0) { error(11); // 未声明标识符 getSym(); return; } if (table[pos].kind constsym) { gen(LIT, 0, table[pos].value); getSym(); } else if (table[pos].kind varsym) { gen(LOD, level - table[pos].level, table[pos].addr); getSym(); } else { error(13); // 过程名出现在表达式中 getSym(); } } else if (sym number) { gen(LIT, 0, num); getSym(); } else if (sym lparen) { getSym(); expression(); if (sym rparen) getSym(); else error(9); // 缺右括号 } else { error(12); // factor位置出现非法符号 getSym(); } }statement分发逻辑看起来更直观void statement(void) { int pos, savedCx1, savedCx2; if (sym ident) { // 赋值语句 pos position(name); if (pos 0) { error(11); getSym(); return; } if (table[pos].kind ! varsym) { error(12); getSym(); return; } getSym(); if (sym ! becomes) { error(10); // 缺赋值号 : return; } getSym(); expression(); gen(STO, level - table[pos].level, table[pos].addr); } else if (sym beginsym) { // begin statement {; statement} end getSym(); do { statement(); } while (sym semicolon); if (sym ! endsym) error(8); // 缺 end getSym(); } else if (sym ifsym) { getSym(); condition(); if (sym thensym) getSym(); else error(4); savedCx1 cx; // 保存JPC位置 gen(JPC, 0, 0); // 条件为假跳过then语句 statement(); code[savedCx1].a cx; // 回填跳转地址 } else if (sym whilesym) { getSym(); savedCx1 cx; // 保存条件判断位置 condition(); savedCx2 cx; gen(JPC, 0, 0); // 条件为假跳出循环 statement(); gen(JMP, 0, savedCx1); // 跳回条件判断 code[savedCx2].a cx; // 回填跳出地址 } else if (sym callsym) { getSym(); if (sym ! ident) { error(11); return; } pos position(name); if (pos 0) { error(11); return; } if (table[pos].kind ! procsym) { error(13); return; } gen(CAL, level - table[pos].level, table[pos].addr); getSym(); } else if (sym readsym) { getSym(); if (sym ! lparen) error(9); getSym(); if (sym ident) { pos position(name); if (pos 0 table[pos].kind varsym) { gen(OPR, 0, 16); // read gen(STO, level - table[pos].level, table[pos].addr); } else error(11); } else error(4); getSym(); if (sym rparen) getSym(); else error(9); } else if (sym writesym) { getSym(); if (sym ! lparen) error(9); getSym(); expression(); gen(OPR, 0, 17); // write if (sym rparen) getSym(); else error(9); } }这段代码看着长但每个分支都只做三件事检查token类型、调对应的子程序、生成中间代码指令。savedCx1、savedCx2的用法就是“标号回填”先留一个0占位等分支体编译完再把真实地址写回去。这是整个编译器里最经典的技巧务必吃透。3.3 语法错误的现场恢复报错后如何继续编译而不是直接退出递归下降分析器天然有错误定位能力但大多数初学者写的版本会在第一处错误就崩掉——直接exit(1)或无限递归。课程实验验收时要的是“能报多个错误并继续分析”所以错误恢复逻辑得单独写。我的做法是维护一个全局错误计数errCounterror(int n)只负责打印错误号和行号不退出。然后在statement的入口做一个“安全网”判断if (sym semicolon || sym endsym || sym period) { return; // 不该出现在statement开头跳过去 }更通用的恢复策略是“跳过到同步符号”。我一般把begin、end、;、period作为同步符号如果某个子程序发现token跟预期完全对不上就循环调getSym()直到遇到同步符号再返回。比如expression里循环解析/-项时如果term返回后sym不是预期的plus或minus就当作表达式结束。这个恢复逻辑不完美但够用。它的价值在于一次运行能输出所有错误清单而不是让学生对着终端干瞪眼。4. 目标代码生成与解释器让PL0程序真正“跑起来”4.1 中间代码的形态PL0虚拟机指令与三字段表很多人以为实验做到语法分析就结束了其实“能编译”和“能运行”中间还隔着一层目标代码生成。PL/0实验的对象码不是x86汇编而是一套为教学设计的虚拟机指令。每条指令三个字段f功能、l层差、a地址或数值。代码区我建议直接用结构体数组#define CODE_MAX 500 typedef struct { int f; // 指令功能: LIT/LOD/STO/CAL/INT/JMP/JPC/OPR int l; // 层差 level差 int a; // 地址、数值或OPR子码 } INSTRUCTION; INSTRUCTION code[CODE_MAX]; int cx 0; // 代码区写入指针 void gen(int f, int l, int a) { if (cx CODE_MAX) { error(20); // 程序太长代码区溢出 return; } code[cx].f f; code[cx].l l; code[cx].a a; cx; }gen函数是整个代码生成的中转站所有指令都必须经过它写入。层差l的计算方式是level - table[pos].level含义是“当前过程层级减去变量定义过程层级”。层差为0表示当前过程变量为1表示外层过程变量。这套层差机制是PL/0栈式分配的核心理解它就能解释为什么嵌套过程能引用外层变量。4.2 语义动作怎么嵌入语法分析emit生成指令与标号回填语义动作不是单独一遍扫描而是“语法制导翻译”——在递归下降过程的每个归约点调用gen。我在第三章的代码里已经穿插了gen调用这里把关键模式抽出来讲透。第一类模式是表达式求值。expression处理加减term处理乘除每个运算符归约时生成对应OPR指令void term(void) { factor(); while (sym times || sym slash) { getSym(); factor(); if (lastOp times) gen(OPR, 0, 4); // 乘法 else gen(OPR, 0, 5); // 除法 } }注意顺序先算出两个操作数压栈再生成运算指令。因为虚拟机运算是对栈顶两个值做操作结果再压回栈顶。这个顺序一旦写反比如先gen再factor运行结果必然错乱。第二类模式是标号回填。以while循环为例完整流程是记下条件指令开始地址savedCx1 cx。编译条件条件结束生成JPC 0,0占位地址记为savedCx2。编译循环体。生成JMP 0,savedCx1跳回条件。回填code[savedCx2].a cx。这一套在递归下降代码里就是三行赋值但它是循环和分支能否正确跳转的生命线。如果你做扩展加else分支同样是先占位再回填多一个标号而已。4.3 解释执行活动记录、display表和OPR指令的分发解释器是C语言写的栈式虚拟机数据区是一个大数组stack栈顶由指针top维护。过程调用时要建立“活动记录”包含返回地址、动态链、局部变量区。PL/0实验里我建议用display表而不是静态链因为静态链在过程嵌套深时容易算错层差。核心执行逻辑是对每条指令做分发void interpret(void) { int pc 0; // 程序计数器 int top 0; // 栈顶指针 int b 1; // 基址指针指向当前活动记录起点 int p, a, op; printf(Begin executing PL/0 program...\n); while (pc cx) { p code[pc].f; a code[pc].a; switch (p) { case LIT: stack[top] a; break; case LOD: // 层差为0直接用当前基址偏移否则沿display找 stack[top] stack[base(b, code[pc].l) a]; break; case STO: stack[base(b, code[pc].l) a] stack[top - 1]; top--; break; case INT: top a; // a为负时是分配空间为正时释放 break; case JMP: pc a; continue; case JPC: if (stack[top - 1] 0) { pc a; top--; continue; } top--; break; case CAL: // 调用过程: 建立display条目保存返回地址 p base(b, code[pc].l); // 找到被调过程的基址 stack[top] b; // 保存动态链 b top; display[code[pc].l] b; // 更新display stack[top 1] pc 1; // 保存返回地址 pc a; top top 2; continue; case OPR: op a; if (op 0) { // 过程返回 top b - 1; pc stack[top 1]; b stack[top]; continue; } // 双目运算统一从栈顶取两个数 if (op 2 op 5 || op 10 op 15) { int x stack[top - 2]; int y stack[top - 1]; top - 2; switch (op) { case 2: stack[top] x y; break; case 3: stack[top] x - y; break; case 4: stack[top] x * y; break; case 5: stack[top] x / y; break; case 10: stack[top] (x y); break; case 11: stack[top] (x ! y); break; case 12: stack[top] (x y); break; case 13: stack[top] (x y); break; case 14: stack[top] (x y); break; case 15: stack[top] (x y); break; } } else if (op 1) { // 取负 stack[top - 1] -stack[top - 1]; } else if (op 9) { // 奇数判断 stack[top - 1] stack[top - 1] % 2; } else if (op 16) { // read scanf(%d, stack[top]); } else if (op 17) { // write printf(%d\n, stack[top - 1]); top--; } break; } pc; } }base函数的作用是做层差寻址int base(int basePtr, int levelDiff) { while (levelDiff 0) { basePtr display[levelDiff 0]; // 简化写法 levelDiff--; } return basePtr; }这段代码的关键是display表。每次进入过程时b指向新活动记录的起点display[level]更新为当前的b。当内层过程要访问外层变量时层差l告诉解释器沿display跳几层。常见坑是层差算错一位访问到的是外层过程的活动记录头部而非变量区表现是运行结果随机、有时直接栈溢出。5. 避坑清单PL0-Compiler交实验前最容易翻车的五个地方5.1 代码区溢出还是死循环gen函数不做上限检查的翻车现象编译稍微复杂一点的PL/0程序比如嵌套三层的递归求阶乘程序直接卡死或者终端反复刷“PROGRAM TOO LONG”。原因code数组只有500条递归下降对每个语句都会生成多条指令嵌套过程多时很容易逼近上限。更隐蔽的是gen函数没有上限检查cx一路涨超越数组边界写坏内存后执行结果变成玄学。解决在gen开头加if (cx CODE_MAX) { error(20); return; }。别小看这行代码它能把“内存写坏”变成“报错后优雅退出”。如果编译大程序不是实验要求CODE_MAX维持500就好要做扩展实验直接改到2000。5.2 负数写成“负数字面量”-1不是LIT而是OPR取负现象源码里写x : -1;编译通过但运行结果错或者你为了实现负数硬在词法分析里加了一个负号token导致x : - 1这种写法报语法错。原因PL/0文法里factor只能接受number负号只能出现在expression开头的[|-]部分。标准实现里-1被翻译成LIT 0,1加OPR 0,1取负。如果你在词法层把“-1”合成一个数字token文法就全乱了。解决不要在词法层做任何负号合并。在expression函数入口处检查sym minus是则先压一个0再接term然后生成OPR 0,1取负。这样1-2和1- -2都能正确解析。5.3 嵌套过程的display更新错位局部变量引用乱套现象一个两层嵌套的程序内层过程调用外层过程运行结果完全不对或者过程结束返回后外层函数的局部变量被改掉。原因CAL指令执行时做了三件事保存动态链、更新display、保存返回地址。顺序不能乱。更常见的问题是base函数实现错误比如直接拿basePtr做加减而不是沿display链逐层上跳。解决把base和CAL的执行逻辑在纸上画一遍栈布局再写代码。画一次栈帧布局比调试三小时有效得多。5.4 while循环的JMP/JPC回填顺序跳转地址错一个就死循环或跳过循环体现象while循环要么一次都不执行要么无限循环要么循环体顺序错乱。原因JPC的占位地址和JMP的回跳地址搞反了。正确顺序是——条件判断前记startCx条件结束后JPC占位循环体结束后JMP回startCx最后回填JPC地址为循环体后的地址。解决写代码时先梳三条标号循环体入口、条件入口、循环体出口。PL/0没有for循环但你可以在纸上推演i : 1; while i 5 do i : i 1的指令序列跑一遍虚拟机单步执行标号对不对一目了然。5.5 read和write的OPR顺序只看结果栈顶操作错位现象read(x)执行一次结果x的值是随机的或者write(x)多打了一个数。原因read的语义是“读入一个数压栈再把栈顶存到变量”必须先生成OPR 0,16再生成STO。反过来write是“先算表达式压栈再OPR 0,17弹出打印”。顺序反了就是存取错位。解决在statement的read分支里先getSym()解析括号内的标识符再gen(OPR,0,16)最后gen(STO,...)。而write分支是先expression()再gen(OPR,0,17)。这两个分支我各写错过一次全是运行结果不对才回头查到的。6. 给PL0-Compiler加三个扩展顺手用批测脚本给自己验收扩展是实验报告里最能拿分的地方但扩展别贪多选两三个跟文法贴合紧密的即可。我建议优先做这三个改动量小、测试容易、报告里能写清楚设计思路。第一个是if-else。在文法里加elsesym保留字语法分析时把statement的if分支改为JPC占位后编译then语句遇到else再生成一个JMP跳过else部分回填两个标号。改动不到十行但能说明你理解了标号回填。第二个是repeat-until循环。文法就一句话repeat statement {; statement} until condition。语义是“先执行循环体再判断条件条件为假继续循环”。这跟while的结构正好相反只需要一个标号回填比if-else还简单。第三个是注释。词法分析里处理{和}之间的内容直接跳过注意不要跨行吞掉行号计数。这个扩展能展示你对词法分析的边界把握。扩展写完后用shell批测#!/bin/bash # 批测脚本逐个运行测试用例对比实际输出和预期输出 for case in tests/*.pl0; do name$(basename $case .pl0) printf Running %s: $name ./pl0 $case tests/$name.in tests/$name.out 21 if diff -q tests/$name.out tests/$name.expected /dev/null; then echo PASS else echo FAIL diff tests/$name.out tests/$name.expected fi done批测脚本的价值在回归每改一次扩展跑一遍全部用例能立刻发现“新功能把老功能改坏了”。这是我在实验最后一天最后悔没早做的事。这个实验做完最大的收获不是“我会写递归下降了”而是“编译器不是黑匣子是一行行能跑通能调试的代码”。我自己当年做的时候卡在display表上耗了三个晚上后来把栈布局画在草稿纸上才想通。希望帮到你。本文还有配套的精品资源点击获取 手写PL/0编译器：从词法分析到解释器的编译原理课程实验指南
简介山东大学SDU编译原理课程PL/0编译器实验的完整实现包面向高校计算机专业学生及编译原理学习者适合作为课程实验参考、复习与二次开发基础。资源包含完整的C/C源代码.cpp/.h/.c、CMake构建脚本、测试用例.in/.out及编译产物.obj/.exe并附有实验报告与多张运行截图系统覆盖词法分析、语法分析BNF/EBNF文法、语义分析、符号表管理等编译器前端核心环节部分源码还涉及中间表示与目标代码生成的实现思路。压缩包共94个文件总大小约513KB虽然包含out、txt、png、cmake等多种类型但目录结构清晰便于按模块查阅和重新构建。目前已有104人学习下载适合需要完成类似PL/0实验或想深入掌握编译器前端原理的学生能提供从文法设计到代码落地的完整参考。1. PL0-Compiler是什么一门能被“写出来”而不是“读出来”的编译原理课很多学校的编译原理课理论部分能把递归下降、LR分析表、语法制导翻译推到黑板上但一进实验课学生面对的是另一道题写一个能编译、能执行的小型编译器。PL0-CompilerPL/0编译器就是这类课程实验最常见的载体山东大学SDU编译原理课程实验用的也正是这套方案用一门极小语言PL/0从零手写词法分析、语法分析、语义分析和目标代码解释执行最后产出一个可运行的编译器加一份实验报告。它解决的问题很具体让“编译原理”这四个字从一个黑匣子变成一条你能单步调试、敢说“每一行都是我写的”的流水线。适合正在上编译原理课、需要交付可运行程序和报告的学生也适合想补手写编译器基本功的从业者。2. 先定文法再落代码PL0的语法骨架与SDU课程实验的工程划分2.1 PL/0语言到底有多“小”从产生式看这门语言边界在哪PL/0是Niklaus Wirth在《Algorithms Data Structures Programs》里定义的教学语言整套语法只有十几条产生式。你别嫌它小它保留了高级语言最核心的东西常量定义、变量声明、嵌套过程声明、表达式、赋值、条件分支、循环、过程调用和输入输出。先看核心文法这是整个实验的“宪法”program :: block . . block :: [const decl] [var decl] {procedure decl} statement . const decl :: const ident number {, ident number} ; . var decl :: var ident {, ident} ; . procedure decl :: procedure ident ; block ; . statement :: [ident : expression | call ident | begin statement {; statement} end | if condition then statement | while condition do statement | read ( ident ) | write ( expression ) | ε] . condition :: odd expression | expression relop expression . expression :: [|-] term {(|-) term} . term :: factor {(*|/) factor} . factor :: ident | number | ( expression ) . relop :: | # | | | | .注意两点。第一PL/0没有负数字面量负号是作为表达式的单目前缀出现的这意味着词法分析器里不需要处理“负数”这个token一切负数在语法层被拆成“0减正数”或“取负操作”。第二不等于号是#不是!。这两点看似不起眼却是后面最常见的翻车点。这门语言没有数组、没有自定义类型、没有返回值概念过程调用靠全局变量通信所以实验的工作量被控制在一个学期能完成的范围词法分析约150行递归下降语法分析约300行代码生成和解释器约300行加起来一千行左右正好是一份课程实验报告该有的体量。2.2 课程实验的常见交付物四个模块与一张指令集对照表SDU这类编译原理课程实验的验收口径一般是能编译PL/0源码输出中间代码或直接解释执行且报告里要有设计说明、流程图、测试用例。常见做法是把编译器拆成四个模块顺序严格执行前一个模块的输出是后一个模块的输入。词法分析把源码字符串切成token序列token类型包括保留字、标识符、数字和特殊符号。语法分析用递归下降法按产生式逐层下降同时做语法错误检查与恢复。语义分析与代码生成PL/0实验里这两步不分离语法分析过程中直接查符号表、输出类Pascal虚拟机指令。解释执行用C语言模拟一个栈式虚拟机执行生成的指令序列。这四个模块对应到代码上就是五个文件或五个函数块。最关键的接口是中间代码的格式PL/0虚拟机指令是经典的三字段结构指令作用参数说明LIT 0,a将常数a压栈a为立即数LOD l,a将层差l、偏移a的变量值压栈l为层差a为栈内偏移STO l,a将栈顶值弹入层差l、偏移a的变量赋值操作CAL l,a调用层差l处的入口a过程进入过程前要建活动记录INT 0,a栈顶指针加a为局部变量腾出空间JMP 0,a无条件跳转到a用于while回跳JPC 0,a栈顶为假时跳转到a用于while和ifOPR 0,op执行运算或子程序返回op为运算子码其中OPR的子码是整个虚拟机的“运算大管家”OPR子码操作OPR子码操作0过程返回9奇数判断ODD1取负10等于2加11不等于3减12小于4乘13小于等于5除14大于6~8保留未用15大于等于16read读入17write输出这张表就是整个实验的“指令集手册”代码生成阶段的任务就是把语法分析过程中遇到的每个操作翻译成上面某一条指令。2.3 工程结构怎么摆源文件划分、全局变量分配和报告配合工程结构我建议直接按“单文件主程序清晰分节”来不建议一上来就拆多文件。PL/0编译器精华在逻辑不在架构单文件里用注释把词法、语法、解释器三个区域隔开调试时能省去头文件同步的麻烦。但全局变量的规划要提前想清楚这是很多人翻车的地方。我需要保留的全局状态有这么几个当前输入的字符ch、当前解析出的token类型sym、符号表tab、符号表当前指针tx、中间代码区code、代码区写入指针cx、当前过程层级level、当前过程中的变量偏移dx。符号表的设计是整个编译器的核心数据结构我建议结构体如下#define SYM_MAX 100 #define ALNX_MAX 10 #define CODE_MAX 500 typedef enum { nul, ident, number, plus, minus, times, slash, oddsym, eql, neq, lss, leq, gtr, geq, lparen, rparen, comma, semicolon, period, becomes, beginsym, endsym, ifsym, thensym, whilesym, dosym, callsym, constsym, varsym, procsym, readsym, writesym } SYMBOL; typedef struct { char name[ALNX_MAX]; // 名字 SYMBOL kind; // const / var / procedure int value; // const的值或var/procedure的地址 int level; // 层号过程嵌套深度 int addr; // 相对当前活动记录基址的偏移 int size; // 仅过程使用记录过程体局部空间大小 } TABLE;词法分析器往sym里填token类型语法分析器查符号表时用tx遍历解释器执行时靠level和addr定位变量。这一套设计是PL/0实验的通行做法照着这个结构写后面无论做扩展还是写报告都顺。报告部分重点放三张图整体流程图、递归下降调用关系图、虚拟机执行流程图。别放代码大段截图验收老师看的是“你有没有想清楚”不是“你复制了多少行”。3. 词法分析与语法分析把PL0源码变成Token流再变成调用树3.1 词法分析怎么实现保留字表、标识符与无符号数识别词法分析器的输入是PL/0源码文件输出是一个接一个的token。PL/0的token就四类保留字、标识符、数字、特殊符号。实现思路很简单先读一个字符跳过空白然后按首字符分类——字母开头走标识符/保留字分支数字开头走数字分支其余按符号映射。先看主逻辑代码这段我一般写成getSym函数void getSym(void) { int i, j; // 跳过空白 while (ch || ch \n || ch \t) nextch(); // 字母开头: 标识符或保留字 if (isalpha(ch)) { j 0; while (isalnum(ch) j ALNX_MAX - 1) { name[j] ch; nextch(); } name[j] \0; // 查保留字表 i 0; while (i NORW strcmp(keyword[i], name) ! 0) i; if (i NORW) sym wsym[i]; // 是保留字 else { sym ident; // 是普通标识符 // 同时可在此处查符号表决定是const/var/procedure } return; } // 数字开头: 无符号整数 if (isdigit(ch)) { num 0; while (isdigit(ch)) { num num * 10 (ch - 0); nextch(); } sym number; return; } // 特殊符号 switch (ch) { case : sym plus; nextch(); break; case -: sym minus; nextch(); break; case *: sym times; nextch(); break; case /: sym slash; nextch(); break; case (: sym lparen; nextch(); break; case ): sym rparen; nextch(); break; case ,: sym comma; nextch(); break; case ;: sym semicolon; nextch(); break; case .: sym period; nextch(); break; case #: sym neq; nextch(); break; case : sym eql; nextch(); break; case : nextch(); if (ch ) { sym leq; nextch(); } else sym lss; break; case : nextch(); if (ch ) { sym geq; nextch(); } else sym gtr; break; case :: nextch(); if (ch ) { sym becomes; nextch(); } else sym nul; // 单独冒号非法 break; default: sym nul; error(0); // 非法字符 nextch(); break; } }这段代码的逻辑重点有三个。第一nextch()负责读下一个字符并维护当前行号出错时报错信息能带行列号。第二标识符被读进全局name数组语法分析阶段查符号表时直接比对name即可。第三保留字表keyword里放的是begin call const do end if odd procedure read then var while write这13个词对应枚举wsym数组顺序必须一一对应否则const会被当成普通标识符。参数说明ALNX_MAX是标识符最大长度我设10够用超过会截断截断逻辑在循环条件里——j ALNX_MAX - 1。NORW是保留字个数13。数字累加时没做溢出保护PL/0实验不需要但你可以顺手加一个if (num 32767) error(5)。3.2 递归下降分析器的骨架factor、term、expression、statement语法分析采用递归下降法原因是PL/0的每个产生式都能对应一个同名函数代码结构跟文法一一映射出错位置也能直接定位到函数栈。整个分析器的入口是blockblock里按文法顺序调statementstatement里按语句类型分发到具体处理逻辑。下面这段是factor和statement的核心写法也是我认为最需要理解的递归下降代码void factor(void) { if (sym ident) { // 标识符: 变量或常量 int pos position(name); if (pos 0) { error(11); // 未声明标识符 getSym(); return; } if (table[pos].kind constsym) { gen(LIT, 0, table[pos].value); getSym(); } else if (table[pos].kind varsym) { gen(LOD, level - table[pos].level, table[pos].addr); getSym(); } else { error(13); // 过程名出现在表达式中 getSym(); } } else if (sym number) { gen(LIT, 0, num); getSym(); } else if (sym lparen) { getSym(); expression(); if (sym rparen) getSym(); else error(9); // 缺右括号 } else { error(12); // factor位置出现非法符号 getSym(); } }statement分发逻辑看起来更直观void statement(void) { int pos, savedCx1, savedCx2; if (sym ident) { // 赋值语句 pos position(name); if (pos 0) { error(11); getSym(); return; } if (table[pos].kind ! varsym) { error(12); getSym(); return; } getSym(); if (sym ! becomes) { error(10); // 缺赋值号 : return; } getSym(); expression(); gen(STO, level - table[pos].level, table[pos].addr); } else if (sym beginsym) { // begin statement {; statement} end getSym(); do { statement(); } while (sym semicolon); if (sym ! endsym) error(8); // 缺 end getSym(); } else if (sym ifsym) { getSym(); condition(); if (sym thensym) getSym(); else error(4); savedCx1 cx; // 保存JPC位置 gen(JPC, 0, 0); // 条件为假跳过then语句 statement(); code[savedCx1].a cx; // 回填跳转地址 } else if (sym whilesym) { getSym(); savedCx1 cx; // 保存条件判断位置 condition(); savedCx2 cx; gen(JPC, 0, 0); // 条件为假跳出循环 statement(); gen(JMP, 0, savedCx1); // 跳回条件判断 code[savedCx2].a cx; // 回填跳出地址 } else if (sym callsym) { getSym(); if (sym ! ident) { error(11); return; } pos position(name); if (pos 0) { error(11); return; } if (table[pos].kind ! procsym) { error(13); return; } gen(CAL, level - table[pos].level, table[pos].addr); getSym(); } else if (sym readsym) { getSym(); if (sym ! lparen) error(9); getSym(); if (sym ident) { pos position(name); if (pos 0 table[pos].kind varsym) { gen(OPR, 0, 16); // read gen(STO, level - table[pos].level, table[pos].addr); } else error(11); } else error(4); getSym(); if (sym rparen) getSym(); else error(9); } else if (sym writesym) { getSym(); if (sym ! lparen) error(9); getSym(); expression(); gen(OPR, 0, 17); // write if (sym rparen) getSym(); else error(9); } }这段代码看着长但每个分支都只做三件事检查token类型、调对应的子程序、生成中间代码指令。savedCx1、savedCx2的用法就是“标号回填”先留一个0占位等分支体编译完再把真实地址写回去。这是整个编译器里最经典的技巧务必吃透。3.3 语法错误的现场恢复报错后如何继续编译而不是直接退出递归下降分析器天然有错误定位能力但大多数初学者写的版本会在第一处错误就崩掉——直接exit(1)或无限递归。课程实验验收时要的是“能报多个错误并继续分析”所以错误恢复逻辑得单独写。我的做法是维护一个全局错误计数errCounterror(int n)只负责打印错误号和行号不退出。然后在statement的入口做一个“安全网”判断if (sym semicolon || sym endsym || sym period) { return; // 不该出现在statement开头跳过去 }更通用的恢复策略是“跳过到同步符号”。我一般把begin、end、;、period作为同步符号如果某个子程序发现token跟预期完全对不上就循环调getSym()直到遇到同步符号再返回。比如expression里循环解析/-项时如果term返回后sym不是预期的plus或minus就当作表达式结束。这个恢复逻辑不完美但够用。它的价值在于一次运行能输出所有错误清单而不是让学生对着终端干瞪眼。4. 目标代码生成与解释器让PL0程序真正“跑起来”4.1 中间代码的形态PL0虚拟机指令与三字段表很多人以为实验做到语法分析就结束了其实“能编译”和“能运行”中间还隔着一层目标代码生成。PL/0实验的对象码不是x86汇编而是一套为教学设计的虚拟机指令。每条指令三个字段f功能、l层差、a地址或数值。代码区我建议直接用结构体数组#define CODE_MAX 500 typedef struct { int f; // 指令功能: LIT/LOD/STO/CAL/INT/JMP/JPC/OPR int l; // 层差 level差 int a; // 地址、数值或OPR子码 } INSTRUCTION; INSTRUCTION code[CODE_MAX]; int cx 0; // 代码区写入指针 void gen(int f, int l, int a) { if (cx CODE_MAX) { error(20); // 程序太长代码区溢出 return; } code[cx].f f; code[cx].l l; code[cx].a a; cx; }gen函数是整个代码生成的中转站所有指令都必须经过它写入。层差l的计算方式是level - table[pos].level含义是“当前过程层级减去变量定义过程层级”。层差为0表示当前过程变量为1表示外层过程变量。这套层差机制是PL/0栈式分配的核心理解它就能解释为什么嵌套过程能引用外层变量。4.2 语义动作怎么嵌入语法分析emit生成指令与标号回填语义动作不是单独一遍扫描而是“语法制导翻译”——在递归下降过程的每个归约点调用gen。我在第三章的代码里已经穿插了gen调用这里把关键模式抽出来讲透。第一类模式是表达式求值。expression处理加减term处理乘除每个运算符归约时生成对应OPR指令void term(void) { factor(); while (sym times || sym slash) { getSym(); factor(); if (lastOp times) gen(OPR, 0, 4); // 乘法 else gen(OPR, 0, 5); // 除法 } }注意顺序先算出两个操作数压栈再生成运算指令。因为虚拟机运算是对栈顶两个值做操作结果再压回栈顶。这个顺序一旦写反比如先gen再factor运行结果必然错乱。第二类模式是标号回填。以while循环为例完整流程是记下条件指令开始地址savedCx1 cx。编译条件条件结束生成JPC 0,0占位地址记为savedCx2。编译循环体。生成JMP 0,savedCx1跳回条件。回填code[savedCx2].a cx。这一套在递归下降代码里就是三行赋值但它是循环和分支能否正确跳转的生命线。如果你做扩展加else分支同样是先占位再回填多一个标号而已。4.3 解释执行活动记录、display表和OPR指令的分发解释器是C语言写的栈式虚拟机数据区是一个大数组stack栈顶由指针top维护。过程调用时要建立“活动记录”包含返回地址、动态链、局部变量区。PL/0实验里我建议用display表而不是静态链因为静态链在过程嵌套深时容易算错层差。核心执行逻辑是对每条指令做分发void interpret(void) { int pc 0; // 程序计数器 int top 0; // 栈顶指针 int b 1; // 基址指针指向当前活动记录起点 int p, a, op; printf(Begin executing PL/0 program...\n); while (pc cx) { p code[pc].f; a code[pc].a; switch (p) { case LIT: stack[top] a; break; case LOD: // 层差为0直接用当前基址偏移否则沿display找 stack[top] stack[base(b, code[pc].l) a]; break; case STO: stack[base(b, code[pc].l) a] stack[top - 1]; top--; break; case INT: top a; // a为负时是分配空间为正时释放 break; case JMP: pc a; continue; case JPC: if (stack[top - 1] 0) { pc a; top--; continue; } top--; break; case CAL: // 调用过程: 建立display条目保存返回地址 p base(b, code[pc].l); // 找到被调过程的基址 stack[top] b; // 保存动态链 b top; display[code[pc].l] b; // 更新display stack[top 1] pc 1; // 保存返回地址 pc a; top top 2; continue; case OPR: op a; if (op 0) { // 过程返回 top b - 1; pc stack[top 1]; b stack[top]; continue; } // 双目运算统一从栈顶取两个数 if (op 2 op 5 || op 10 op 15) { int x stack[top - 2]; int y stack[top - 1]; top - 2; switch (op) { case 2: stack[top] x y; break; case 3: stack[top] x - y; break; case 4: stack[top] x * y; break; case 5: stack[top] x / y; break; case 10: stack[top] (x y); break; case 11: stack[top] (x ! y); break; case 12: stack[top] (x y); break; case 13: stack[top] (x y); break; case 14: stack[top] (x y); break; case 15: stack[top] (x y); break; } } else if (op 1) { // 取负 stack[top - 1] -stack[top - 1]; } else if (op 9) { // 奇数判断 stack[top - 1] stack[top - 1] % 2; } else if (op 16) { // read scanf(%d, stack[top]); } else if (op 17) { // write printf(%d\n, stack[top - 1]); top--; } break; } pc; } }base函数的作用是做层差寻址int base(int basePtr, int levelDiff) { while (levelDiff 0) { basePtr display[levelDiff 0]; // 简化写法 levelDiff--; } return basePtr; }这段代码的关键是display表。每次进入过程时b指向新活动记录的起点display[level]更新为当前的b。当内层过程要访问外层变量时层差l告诉解释器沿display跳几层。常见坑是层差算错一位访问到的是外层过程的活动记录头部而非变量区表现是运行结果随机、有时直接栈溢出。5. 避坑清单PL0-Compiler交实验前最容易翻车的五个地方5.1 代码区溢出还是死循环gen函数不做上限检查的翻车现象编译稍微复杂一点的PL/0程序比如嵌套三层的递归求阶乘程序直接卡死或者终端反复刷“PROGRAM TOO LONG”。原因code数组只有500条递归下降对每个语句都会生成多条指令嵌套过程多时很容易逼近上限。更隐蔽的是gen函数没有上限检查cx一路涨超越数组边界写坏内存后执行结果变成玄学。解决在gen开头加if (cx CODE_MAX) { error(20); return; }。别小看这行代码它能把“内存写坏”变成“报错后优雅退出”。如果编译大程序不是实验要求CODE_MAX维持500就好要做扩展实验直接改到2000。5.2 负数写成“负数字面量”-1不是LIT而是OPR取负现象源码里写x : -1;编译通过但运行结果错或者你为了实现负数硬在词法分析里加了一个负号token导致x : - 1这种写法报语法错。原因PL/0文法里factor只能接受number负号只能出现在expression开头的[|-]部分。标准实现里-1被翻译成LIT 0,1加OPR 0,1取负。如果你在词法层把“-1”合成一个数字token文法就全乱了。解决不要在词法层做任何负号合并。在expression函数入口处检查sym minus是则先压一个0再接term然后生成OPR 0,1取负。这样1-2和1- -2都能正确解析。5.3 嵌套过程的display更新错位局部变量引用乱套现象一个两层嵌套的程序内层过程调用外层过程运行结果完全不对或者过程结束返回后外层函数的局部变量被改掉。原因CAL指令执行时做了三件事保存动态链、更新display、保存返回地址。顺序不能乱。更常见的问题是base函数实现错误比如直接拿basePtr做加减而不是沿display链逐层上跳。解决把base和CAL的执行逻辑在纸上画一遍栈布局再写代码。画一次栈帧布局比调试三小时有效得多。5.4 while循环的JMP/JPC回填顺序跳转地址错一个就死循环或跳过循环体现象while循环要么一次都不执行要么无限循环要么循环体顺序错乱。原因JPC的占位地址和JMP的回跳地址搞反了。正确顺序是——条件判断前记startCx条件结束后JPC占位循环体结束后JMP回startCx最后回填JPC地址为循环体后的地址。解决写代码时先梳三条标号循环体入口、条件入口、循环体出口。PL/0没有for循环但你可以在纸上推演i : 1; while i 5 do i : i 1的指令序列跑一遍虚拟机单步执行标号对不对一目了然。5.5 read和write的OPR顺序只看结果栈顶操作错位现象read(x)执行一次结果x的值是随机的或者write(x)多打了一个数。原因read的语义是“读入一个数压栈再把栈顶存到变量”必须先生成OPR 0,16再生成STO。反过来write是“先算表达式压栈再OPR 0,17弹出打印”。顺序反了就是存取错位。解决在statement的read分支里先getSym()解析括号内的标识符再gen(OPR,0,16)最后gen(STO,...)。而write分支是先expression()再gen(OPR,0,17)。这两个分支我各写错过一次全是运行结果不对才回头查到的。6. 给PL0-Compiler加三个扩展顺手用批测脚本给自己验收扩展是实验报告里最能拿分的地方但扩展别贪多选两三个跟文法贴合紧密的即可。我建议优先做这三个改动量小、测试容易、报告里能写清楚设计思路。第一个是if-else。在文法里加elsesym保留字语法分析时把statement的if分支改为JPC占位后编译then语句遇到else再生成一个JMP跳过else部分回填两个标号。改动不到十行但能说明你理解了标号回填。第二个是repeat-until循环。文法就一句话repeat statement {; statement} until condition。语义是“先执行循环体再判断条件条件为假继续循环”。这跟while的结构正好相反只需要一个标号回填比if-else还简单。第三个是注释。词法分析里处理{和}之间的内容直接跳过注意不要跨行吞掉行号计数。这个扩展能展示你对词法分析的边界把握。扩展写完后用shell批测#!/bin/bash # 批测脚本逐个运行测试用例对比实际输出和预期输出 for case in tests/*.pl0; do name$(basename $case .pl0) printf Running %s: $name ./pl0 $case tests/$name.in tests/$name.out 21 if diff -q tests/$name.out tests/$name.expected /dev/null; then echo PASS else echo FAIL diff tests/$name.out tests/$name.expected fi done批测脚本的价值在回归每改一次扩展跑一遍全部用例能立刻发现“新功能把老功能改坏了”。这是我在实验最后一天最后悔没早做的事。这个实验做完最大的收获不是“我会写递归下降了”而是“编译器不是黑匣子是一行行能跑通能调试的代码”。我自己当年做的时候卡在display表上耗了三个晚上后来把栈布局画在草稿纸上才想通。希望帮到你。本文还有配套的精品资源点击获取