简介这份资源是南京航空航天大学编译原理课程设计的完整实践成果面向正在学习编译原理、需要动手实现编译器的计算机专业学生与自学者。项目以PL0这一简化版Pascal教学语言为对象完整走通词法分析、语法分析、语义分析与代码生成等核心阶段帮助读者把课堂理论落到可运行的编译器代码上。压缩包共7个文件约1.71MB包含cpp源代码、可执行程序、课程设计报告PDF以及多组测试用例txt分别对应编译器实现、功能验证与设计思路记录。目前已有420人学习下载。读者可借助源码理解lexer、parser与codegen的组织方式通过报告复盘设计路径与问题解决策略并用测试用例检验编译器对变量声明、赋值、流程控制等语法的处理是否正确适合作为课程设计参考与编译器入门练手素材。1. PL/0 编译器课设从语法分析到目标代码一个能跑通的完整路径PL/0 是 Pascal 的子集语法精简到一页纸就能写完但五脏俱全——常量定义、变量声明、过程嵌套、条件分支、循环、甚至递归调用都有。南京航空航天大学编译原理课程设计选它做编译器实现核心原因就一个你必须在有限时间里把词法分析、语法分析、符号表管理、语义检查、代码生成这条完整链路全部走通而不是只做一道习题。很多人拿到题目第一反应是去搜“编译原理第三版答案”但课设和课后习题是两回事——习题考的是你懂不懂概念课设考的是你能不能把概念变成能跑的程序。这篇文章面向正在做或准备做 PL/0 编译器的同学也面向任何想用一个最小可行项目理解编译器全流程的开发者。我会按实际实现顺序拆解先定架构再写词法再做递归下降语法分析然后处理符号表和语义最后生成类 P-code 目标代码并解释执行。每一步都给可复现的代码骨架和参数说明不绕弯子。2. 架构选型与 PL/0 语言子集裁剪先画边界再动手2.1 为什么选递归下降而不是 LR 分析器生成器PL/0 的文法天然适合递归下降。它的语法结构是块状嵌套的每个begin...end和procedure...end都形成清晰的递归边界。用递归下降写语法分析函数的调用栈直接对应语法树的嵌套层次调试时看调用栈就能定位问题。如果用 yacc/bison 这类 LALR 生成器你得先把文法改写成 LALR(1) 可接受的形式PL/0 里的过程声明和语句序列会产生移进-归约冲突改文法的时间可能比手写还长。我一般建议课设场景直接手写递归下降代码量在 800 到 1200 行左右可控性最强。2.2 PL/0 必须支持的语法子集清单动手前先把要支持的语法列清楚避免写到一半发现漏了特性。下面这张表是我做课设时裁剪后的最小可用集语法成分示例是否必须常量定义const a 10;必须变量声明var x, y;必须过程声明procedure foo; begin ... end;必须赋值语句x : x 1必须条件语句if x 0 then ...必须循环语句while x 10 do ...必须复合语句begin ... end必须输出语句write(x)或! x必须输入语句read(x)或? x建议过程调用call foo必须嵌套过程过程内再声明过程必须递归调用过程调用自身必须裁剪原则凡是能通过组合已有语句实现的就不单独加语法。比如for循环可以用while加赋值模拟repeat可以用while加条件取反模拟。这样语法分析器少写两三个函数但语义完整性不受影响。2.3 目标代码形式类 P-code 指令集设计PL/0 经典实现生成的是栈式虚拟机的 P-code。我建议沿用这个思路但把指令集精简到 15 条左右够用且好调试。核心指令包括LIT 0, a将常量 a 压栈LOD l, a将层差 l、偏移 a 的变量值压栈STO l, a栈顶值存入层差 l、偏移 a 的变量CAL l, a调用层差 l、入口地址 a 的过程INT 0, a在栈顶分配 a 个存储单元JMP 0, a无条件跳转到地址 aJPC 0, a栈顶为 0 时跳转到地址 aOPR 0, a执行算术/逻辑/输入输出操作a 为操作码这套指令集的好处是每条指令的行为都能用几行 C 或 Python 模拟解释器不到 200 行就能写完。调试时你可以直接打印指令序列对照源码逐条检查。3. 词法分析器实现从字符流到 token 序列3.1 状态机设计与关键字识别词法分析器的任务是把源程序的字符流切分成有意义的 token。PL/0 的 token 类型不多关键字const、var、procedure、begin、end、if、then、while、do、call、read、write、标识符、数字、运算符、-、*、/、、、、、、、:、分隔符;、,、.、(、)。实现上用一个循环读字符根据首字符分派字母开头读标识符读完查关键字表决定是关键字还是普通标识符数字开头读整数其他字符按运算符表匹配。注意:和:的区分以及、、的双字符运算符要优先匹配。# 词法分析器核心循环Python 伪代码C 版本逻辑相同 KEYWORDS {const,var,procedure,begin,end,if,then, while,do,call,read,write} def next_token(self): while self.pos len(self.src) and self.src[self.pos].isspace(): self.pos 1 if self.pos len(self.src): return (EOF, None) ch self.src[self.pos] if ch.isalpha(): start self.pos while self.pos len(self.src) and self.src[self.pos].isalnum(): self.pos 1 word self.src[start:self.pos] if word in KEYWORDS: return (word.upper(), None) # 关键字 token return (IDENT, word) # 标识符 token if ch.isdigit(): start self.pos while self.pos len(self.src) and self.src[self.pos].isdigit(): self.pos 1 return (NUMBER, int(self.src[start:self.pos])) # 双字符运算符优先 if ch : and self.peek() : self.pos 2 return (ASSIGN, :) if ch and self.peek() : self.pos 2 return (LE, ) if ch and self.peek() : self.pos 2 return (NE, ) # 单字符运算符和分隔符 single {:PLUS,-:MINUS,*:TIMES,/:SLASH, :EQ,:LT,:GT,(:LPAREN,):RPAREN, ;:SEMI,,:COMMA,.:DOT} if ch in single: self.pos 1 return (single[ch], ch) raise SyntaxError(f非法字符 {ch} 在位置 {self.pos})这段代码的关键点peek()函数返回当前字符的下一个字符但不移动位置用于双字符运算符的前瞻判断。关键字表用集合存储查找是 O(1)。标识符和数字的读取用 while 循环吞掉连续字符注意边界检查self.pos len(self.src)不能漏否则遇到文件末尾会越界。3.2 token 数据结构与错误定位每个 token 建议用结构体或元组存三个字段类型、值、行号。行号在报错时至关重要——编译器课设的评分点里错误恢复和错误提示占不小比重。行号维护很简单词法分析器每读到一个换行符就把行号加一生成 token 时带上当前行号。错误处理策略遇到非法字符时不要直接崩溃退出而是记录错误信息行号 字符然后跳过该字符继续分析。这样一次编译能报出所有词法错误而不是改一个报一个。我见过不少同学在这里翻车——词法阶段遇到一个非法字符就exit(1)结果调试时来回改十几次才把词法错误清完。4. 递归下降语法分析与符号表把 token 流变成结构化中间表示4.1 每个非终结符对应一个分析函数递归下降的核心思想文法里每个非终结符写一个函数函数内部按照产生式右部依次调用其他非终结符函数或匹配终结符。PL/0 的主要非终结符包括program、block、const_decl、var_decl、proc_decl、statement、expression、term、factor、condition。以statement为例它的产生式大致是statement - IDENT : expression | call IDENT | begin statement {; statement} end | if condition then statement | while condition do statement | read ( IDENT ) | write ( expression ) | ε对应的分析函数先看当前 token 类型如果是IDENT就预测是赋值语句如果是CALL就预测是过程调用以此类推。这种“看一个 token 决定走哪条分支”的方式叫 LL(1) 预测分析PL/0 的文法经过适当改写后满足 LL(1) 条件。// statement 分析函数骨架C 语言 void parse_statement() { switch (current_token.type) { case IDENT: parse_assignment(); // x : expr break; case CALL: parse_call(); // call proc_name break; case BEGIN: parse_compound(); // begin ... end break; case IF: parse_if(); // if cond then stmt break; case WHILE: parse_while(); // while cond do stmt break; case READ: parse_read(); // read(x) break; case WRITE: parse_write(); // write(expr) break; default: // 空语句不消耗 token break; } }每个分支函数内部继续递归调用parse_expression、parse_condition等。注意parse_compound里要循环处理;分隔的多条语句直到遇到end。parse_if和parse_while里要生成跳转指令的占位符等回填地址——这是后面代码生成阶段的事但语法分析阶段就要把结构信息传下去。4.2 符号表嵌套作用域与层差计算符号表管理是 PL/0 编译器里最容易出 bug 的地方。PL/0 允许过程嵌套声明每个过程形成一个新作用域。变量查找规则是先在当前层找找不到再去外层找直到最外层主程序层层号为 0。如果所有层都找不到报“未声明标识符”错误。符号表的数据结构我推荐用栈式符号表进入一个过程时压入一个新表项记录过程名、层号、入口地址同时该过程内声明的变量也记录在这个表项下。退出过程时弹出。查找时从栈顶往下遍历。层差level difference的计算当内层过程访问外层过程的变量时需要知道跨了几层。比如层 2 的过程访问层 0 的变量层差是 2。这个层差会编码到LOD和STO指令的第一个参数里解释器执行时根据层差沿着静态链static link往上找活动记录。// 符号表查找返回变量所在层差和偏移 typedef struct { char name[MAX_NAME]; int kind; // 0常量, 1变量, 2过程 int level; // 声明所在层号 int addr; // 变量偏移或过程入口地址 int value; // 常量值 } Symbol; Symbol* lookup(char* name, int current_level, int* out_level_diff) { for (int lv current_level; lv 0; lv--) { for (int i table_top[lv]; i table_base[lv]; i--) { if (strcmp(sym_table[i].name, name) 0) { *out_level_diff current_level - sym_table[i].level; return sym_table[i]; } } } return NULL; // 未声明 }这段代码里table_base[lv]和table_top[lv]分别记录第 lv 层符号在全局符号表中的起始和结束下标。查找时从当前层往外层遍历找到后计算层差。注意常量查找和变量查找共用这个函数但常量不需要层差常量值直接内联到指令里。4.3 语义检查类型、重复声明与未声明引用语法分析通过不代表程序合法语义检查必须同步做。PL/0 的语义检查点不多但必须覆盖重复声明同一作用域内同名标识符只能声明一次。在插入符号表前先查当前层是否已存在。未声明引用赋值语句左侧、表达式中的标识符、过程调用名都必须能在符号表中找到。常量不可赋值const声明的标识符出现在:左侧时报错。过程调用参数PL/0 经典版本不支持参数传递如果扩展了参数要检查实参个数和形参个数是否匹配。条件表达式if和while的条件必须是关系表达式不能是裸的算术表达式除非语言定义允许隐式非零判断。这些检查在语法分析函数里顺手做掉不要等语法树建完再遍历一遍。递归下降的优势就是“边走边查”发现错误立即报报完继续走尽量一次编译报出所有语义错误。5. 代码生成与虚拟机执行从中间表示到可运行结果5.1 表达式求值的栈式代码生成PL/0 的目标代码是栈式指令序列表达式求值天然适合栈式生成。规则很简单遇到数字生成LIT压栈遇到变量生成LOD压栈遇到二元运算符先递归生成左右操作数的代码再生成OPR指令。比如x y * 2的生成顺序是LOD 0, x_addr ; 压入 x LOD 0, y_addr ; 压入 y LIT 0, 2 ; 压入 2 OPR 0, MUL ; 弹出 2 和 y压入 y*2 OPR 0, ADD ; 弹出 y*2 和 x压入 xy*2运算符优先级通过递归下降的层次自然处理expression处理加减term处理乘除factor处理括号和原子。不需要显式维护优先级表。# 表达式代码生成Python 伪代码 def gen_expression(self): self.gen_term() while self.cur.type in (PLUS, MINUS): op self.cur.type self.next_token() self.gen_term() if op PLUS: self.emit(OPR, 0, OPR_ADD) else: self.emit(OPR, 0, OPR_SUB) def gen_term(self): self.gen_factor() while self.cur.type in (TIMES, SLASH): op self.cur.type self.next_token() self.gen_factor() if op TIMES: self.emit(OPR, 0, OPR_MUL) else: self.emit(OPR, 0, OPR_DIV)emit函数把指令追加到代码数组同时返回当前指令地址方便后面回填跳转目标。注意除法要处理除零——可以在生成时插入检查也可以在解释器执行OPR_DIV时检查栈顶除数是否为零。5.2 控制流语句的跳转回填if和while需要生成条件跳转指令但跳转目标地址在生成跳转指令时还不知道必须等语句体生成完才能确定。经典做法是“回填”先生成一条占位跳转指令记录它的地址等目标确定后再修改该指令的跳转参数。以if cond then stmt为例生成 cond 的代码 JPC 0, ??? ; 条件为假时跳转到 stmt 之后 记录 JPC 指令地址 jpc_addr 生成 stmt 的代码 回填code[jpc_addr].a 当前代码地址while cond do stmt稍微复杂一点需要两个跳转条件为假时跳出循环循环体结束后无条件跳回条件判断处。记录循环开始地址 loop_start 生成 cond 的代码 JPC 0, ??? ; 条件为假时跳出 记录 jpc_addr 生成 stmt 的代码 JMP 0, loop_start ; 跳回条件判断 回填code[jpc_addr].a 当前代码地址回填是代码生成里最容易出错的地方血泪经验是每次回填后打印完整指令序列对照源码逐条验证跳转地址是否正确。我调试时会在每条指令后面注释对应的源码行号这样一眼就能看出跳转有没有跳错位置。5.3 虚拟机解释器活动记录与静态链生成的 P-code 需要一个解释器来执行。解释器的核心数据结构是栈数据栈存变量和临时值指令指针指向当前执行的指令基址指针指向当前活动记录的基地址。活动记录activation record的布局位置内容基址 0静态链指向外层过程活动记录的基址基址 1动态链指向调用者活动记录的基址基址 2返回地址基址 3 起局部变量和临时值LOD l, a的执行逻辑从当前基址出发沿静态链走 l 步找到目标活动记录基址然后取偏移 a 处的值压栈。STO类似只是方向相反。CAL创建新活动记录压入静态链当前层差对应的基址、动态链当前基址、返回地址然后跳转到过程入口。// 解释器主循环C 语言核心片段 while (running) { Instruction inst code[pc]; switch (inst.op) { case LIT: stack[top] inst.a; break; case LOD: { int base get_base(inst.l); // 沿静态链走 l 步 stack[top] stack[base inst.a]; break; } case STO: { int base get_base(inst.l); stack[base inst.a] stack[top--]; break; } case OPR: execute_opr(inst.a); // 算术、比较、输入输出 break; case JMP: pc inst.a; break; case JPC: if (stack[top--] 0) pc inst.a; break; case CAL: { // 创建新活动记录 stack[top 1] get_base(inst.l); // 静态链 stack[top 2] base_ptr; // 动态链 stack[top 3] pc; // 返回地址 base_ptr top 1; pc inst.a; break; } case INT: top inst.a; // 分配局部变量空间 break; } }get_base(l)函数沿静态链走 l 步从当前base_ptr开始每次取stack[base_ptr]作为新基址重复 l 次。这个函数是理解 PL/0 运行时结构的关键——静态链把嵌套作用域串成一条链层差就是链上走的步数。6. 避坑与排查PL/0 编译器课设里最容易翻车的五个地方6.1 符号表层号计算错误导致变量访问越界现象程序能编译通过但运行时读取变量得到垃圾值或者直接段错误。原因层差计算时把当前层号减错了比如内层过程访问同层变量时层差算成了 1 而不是 0。或者符号表压栈/弹栈时机不对退出过程时没清理该层的符号导致外层同名变量被内层覆盖。解决在lookup函数里加打印输出每次查找的标识符名、当前层号、找到的层号和计算出的层差。对照源码手工验证几个关键变量的层差。符号表弹栈的时机是过程体分析完毕、遇到end时不要提前也不要延后。6.2 跳转回填地址偏移一位现象if或while语句执行时跳转到了错误的位置程序行为完全不对。原因回填时填的是“当前代码地址”但解释器执行JPC后pc已经自增过了实际跳转目标应该是“下一条要执行的指令地址”。如果填的是“最后一条已生成指令的地址”就会偏移一位。解决统一约定——emit返回的是新指令的地址回填时用“当前代码数组长度”作为跳转目标因为下一条生成的指令就会放在这个位置。在回填后打印指令序列手工模拟执行几条跳转指令验证。6.3 过程调用时静态链指向错误现象递归调用返回后变量值错乱或者多层嵌套过程调用时访问外层变量得到错误结果。原因CAL指令创建活动记录时静态链应该指向“被调用过程声明所在层”的当前活动记录而不是调用者的活动记录。这两者在非递归直接调用时可能相同但递归或多层嵌套时不同。解决CAL l, a里的l是层差表示从调用者当前层到被调用过程声明层的层数差。创建活动记录时静态链的值是get_base(l)的结果。在解释器里加调试输出每次CAL时打印层差、计算出的静态链基址和调用者基址。6.4 表达式求值顺序与栈不平衡现象复杂表达式计算结果错误或者解释器执行到某条OPR时栈顶元素不是预期的操作数。原因递归下降生成表达式代码时左右操作数的生成顺序和OPR指令弹出顺序不匹配。栈式指令的约定是先压入左操作数再压入右操作数OPR弹出右操作数再弹出左操作数。如果生成顺序反了减法和除法就会算反。解决在gen_expression和gen_term里严格保证“先 gen 左再 gen 右最后 emit OPR”。在解释器的execute_opr里加断言检查栈深度是否足够弹出两个操作数。调试时打印每条OPR执行前的栈顶两个值。6.5 输入输出指令与宿主语言缓冲冲突现象read语句读不到用户输入或者write输出没有立即显示。原因C 语言的scanf/printf和解释器的输入输出指令混用时缓冲区刷新时机不对。特别是printf不带换行符时输出留在缓冲区里用户看不到提示信息。解决在write指令执行后强制fflush(stdout)在read指令执行前也fflush(stdout)确保提示信息先输出。如果宿主语言是 Python用sys.stdout.flush()。这个坑不涉及编译原理但调试时非常影响体验。7. 进阶验证用测试用例集反向检验编译器正确性课设验收时老师不会只看你跑一个hello world而是会拿一组覆盖各种语法特性的测试程序来跑。我建议自己先建一个测试用例集按特性分类每类至少三个用例正常用例、边界用例、错误用例。下面这张表是我当时用的分类框架测试类别正常用例边界用例错误用例常量与变量多常量多变量声明常量参与表达式重复声明表达式加减乘除混合多层括号嵌套除零条件语句if-then 单分支if 嵌套条件非关系表达式循环语句while 计数循环while 嵌套循环变量未声明过程调用无参过程调用递归调用调用未声明过程作用域内层访问外层变量三层嵌套访问已退出作用域变量验证方法每个用例先手工推导预期输出然后跑编译器看实际输出是否一致。不一致时先打印生成的 P-code 指令序列对照源码逐条检查指令生成是否正确如果指令序列正确但执行结果不对再检查解释器的活动记录管理。一个具体技巧给解释器加一个--trace开关开启后每执行一条指令就打印指令内容、执行前的栈顶五个元素、当前基址和指令指针。这样程序跑飞时你能看到是从哪条指令开始偏离预期的。这个 trace 输出会很长但定位问题时比单步调试快得多。我自己的习惯是每实现完一个语法特性立刻写三个测试用例跑一遍通过了再写下一个特性。不要等全部写完再统一测试——编译器 bug 的定位成本随代码量增长是超线性的早测早省心。希望帮到你。本文还有配套的精品资源点击获取 PL/0编译器课设实战：从词法分析到目标代码的完整实现路径
简介这份资源是南京航空航天大学编译原理课程设计的完整实践成果面向正在学习编译原理、需要动手实现编译器的计算机专业学生与自学者。项目以PL0这一简化版Pascal教学语言为对象完整走通词法分析、语法分析、语义分析与代码生成等核心阶段帮助读者把课堂理论落到可运行的编译器代码上。压缩包共7个文件约1.71MB包含cpp源代码、可执行程序、课程设计报告PDF以及多组测试用例txt分别对应编译器实现、功能验证与设计思路记录。目前已有420人学习下载。读者可借助源码理解lexer、parser与codegen的组织方式通过报告复盘设计路径与问题解决策略并用测试用例检验编译器对变量声明、赋值、流程控制等语法的处理是否正确适合作为课程设计参考与编译器入门练手素材。1. PL/0 编译器课设从语法分析到目标代码一个能跑通的完整路径PL/0 是 Pascal 的子集语法精简到一页纸就能写完但五脏俱全——常量定义、变量声明、过程嵌套、条件分支、循环、甚至递归调用都有。南京航空航天大学编译原理课程设计选它做编译器实现核心原因就一个你必须在有限时间里把词法分析、语法分析、符号表管理、语义检查、代码生成这条完整链路全部走通而不是只做一道习题。很多人拿到题目第一反应是去搜“编译原理第三版答案”但课设和课后习题是两回事——习题考的是你懂不懂概念课设考的是你能不能把概念变成能跑的程序。这篇文章面向正在做或准备做 PL/0 编译器的同学也面向任何想用一个最小可行项目理解编译器全流程的开发者。我会按实际实现顺序拆解先定架构再写词法再做递归下降语法分析然后处理符号表和语义最后生成类 P-code 目标代码并解释执行。每一步都给可复现的代码骨架和参数说明不绕弯子。2. 架构选型与 PL/0 语言子集裁剪先画边界再动手2.1 为什么选递归下降而不是 LR 分析器生成器PL/0 的文法天然适合递归下降。它的语法结构是块状嵌套的每个begin...end和procedure...end都形成清晰的递归边界。用递归下降写语法分析函数的调用栈直接对应语法树的嵌套层次调试时看调用栈就能定位问题。如果用 yacc/bison 这类 LALR 生成器你得先把文法改写成 LALR(1) 可接受的形式PL/0 里的过程声明和语句序列会产生移进-归约冲突改文法的时间可能比手写还长。我一般建议课设场景直接手写递归下降代码量在 800 到 1200 行左右可控性最强。2.2 PL/0 必须支持的语法子集清单动手前先把要支持的语法列清楚避免写到一半发现漏了特性。下面这张表是我做课设时裁剪后的最小可用集语法成分示例是否必须常量定义const a 10;必须变量声明var x, y;必须过程声明procedure foo; begin ... end;必须赋值语句x : x 1必须条件语句if x 0 then ...必须循环语句while x 10 do ...必须复合语句begin ... end必须输出语句write(x)或! x必须输入语句read(x)或? x建议过程调用call foo必须嵌套过程过程内再声明过程必须递归调用过程调用自身必须裁剪原则凡是能通过组合已有语句实现的就不单独加语法。比如for循环可以用while加赋值模拟repeat可以用while加条件取反模拟。这样语法分析器少写两三个函数但语义完整性不受影响。2.3 目标代码形式类 P-code 指令集设计PL/0 经典实现生成的是栈式虚拟机的 P-code。我建议沿用这个思路但把指令集精简到 15 条左右够用且好调试。核心指令包括LIT 0, a将常量 a 压栈LOD l, a将层差 l、偏移 a 的变量值压栈STO l, a栈顶值存入层差 l、偏移 a 的变量CAL l, a调用层差 l、入口地址 a 的过程INT 0, a在栈顶分配 a 个存储单元JMP 0, a无条件跳转到地址 aJPC 0, a栈顶为 0 时跳转到地址 aOPR 0, a执行算术/逻辑/输入输出操作a 为操作码这套指令集的好处是每条指令的行为都能用几行 C 或 Python 模拟解释器不到 200 行就能写完。调试时你可以直接打印指令序列对照源码逐条检查。3. 词法分析器实现从字符流到 token 序列3.1 状态机设计与关键字识别词法分析器的任务是把源程序的字符流切分成有意义的 token。PL/0 的 token 类型不多关键字const、var、procedure、begin、end、if、then、while、do、call、read、write、标识符、数字、运算符、-、*、/、、、、、、、:、分隔符;、,、.、(、)。实现上用一个循环读字符根据首字符分派字母开头读标识符读完查关键字表决定是关键字还是普通标识符数字开头读整数其他字符按运算符表匹配。注意:和:的区分以及、、的双字符运算符要优先匹配。# 词法分析器核心循环Python 伪代码C 版本逻辑相同 KEYWORDS {const,var,procedure,begin,end,if,then, while,do,call,read,write} def next_token(self): while self.pos len(self.src) and self.src[self.pos].isspace(): self.pos 1 if self.pos len(self.src): return (EOF, None) ch self.src[self.pos] if ch.isalpha(): start self.pos while self.pos len(self.src) and self.src[self.pos].isalnum(): self.pos 1 word self.src[start:self.pos] if word in KEYWORDS: return (word.upper(), None) # 关键字 token return (IDENT, word) # 标识符 token if ch.isdigit(): start self.pos while self.pos len(self.src) and self.src[self.pos].isdigit(): self.pos 1 return (NUMBER, int(self.src[start:self.pos])) # 双字符运算符优先 if ch : and self.peek() : self.pos 2 return (ASSIGN, :) if ch and self.peek() : self.pos 2 return (LE, ) if ch and self.peek() : self.pos 2 return (NE, ) # 单字符运算符和分隔符 single {:PLUS,-:MINUS,*:TIMES,/:SLASH, :EQ,:LT,:GT,(:LPAREN,):RPAREN, ;:SEMI,,:COMMA,.:DOT} if ch in single: self.pos 1 return (single[ch], ch) raise SyntaxError(f非法字符 {ch} 在位置 {self.pos})这段代码的关键点peek()函数返回当前字符的下一个字符但不移动位置用于双字符运算符的前瞻判断。关键字表用集合存储查找是 O(1)。标识符和数字的读取用 while 循环吞掉连续字符注意边界检查self.pos len(self.src)不能漏否则遇到文件末尾会越界。3.2 token 数据结构与错误定位每个 token 建议用结构体或元组存三个字段类型、值、行号。行号在报错时至关重要——编译器课设的评分点里错误恢复和错误提示占不小比重。行号维护很简单词法分析器每读到一个换行符就把行号加一生成 token 时带上当前行号。错误处理策略遇到非法字符时不要直接崩溃退出而是记录错误信息行号 字符然后跳过该字符继续分析。这样一次编译能报出所有词法错误而不是改一个报一个。我见过不少同学在这里翻车——词法阶段遇到一个非法字符就exit(1)结果调试时来回改十几次才把词法错误清完。4. 递归下降语法分析与符号表把 token 流变成结构化中间表示4.1 每个非终结符对应一个分析函数递归下降的核心思想文法里每个非终结符写一个函数函数内部按照产生式右部依次调用其他非终结符函数或匹配终结符。PL/0 的主要非终结符包括program、block、const_decl、var_decl、proc_decl、statement、expression、term、factor、condition。以statement为例它的产生式大致是statement - IDENT : expression | call IDENT | begin statement {; statement} end | if condition then statement | while condition do statement | read ( IDENT ) | write ( expression ) | ε对应的分析函数先看当前 token 类型如果是IDENT就预测是赋值语句如果是CALL就预测是过程调用以此类推。这种“看一个 token 决定走哪条分支”的方式叫 LL(1) 预测分析PL/0 的文法经过适当改写后满足 LL(1) 条件。// statement 分析函数骨架C 语言 void parse_statement() { switch (current_token.type) { case IDENT: parse_assignment(); // x : expr break; case CALL: parse_call(); // call proc_name break; case BEGIN: parse_compound(); // begin ... end break; case IF: parse_if(); // if cond then stmt break; case WHILE: parse_while(); // while cond do stmt break; case READ: parse_read(); // read(x) break; case WRITE: parse_write(); // write(expr) break; default: // 空语句不消耗 token break; } }每个分支函数内部继续递归调用parse_expression、parse_condition等。注意parse_compound里要循环处理;分隔的多条语句直到遇到end。parse_if和parse_while里要生成跳转指令的占位符等回填地址——这是后面代码生成阶段的事但语法分析阶段就要把结构信息传下去。4.2 符号表嵌套作用域与层差计算符号表管理是 PL/0 编译器里最容易出 bug 的地方。PL/0 允许过程嵌套声明每个过程形成一个新作用域。变量查找规则是先在当前层找找不到再去外层找直到最外层主程序层层号为 0。如果所有层都找不到报“未声明标识符”错误。符号表的数据结构我推荐用栈式符号表进入一个过程时压入一个新表项记录过程名、层号、入口地址同时该过程内声明的变量也记录在这个表项下。退出过程时弹出。查找时从栈顶往下遍历。层差level difference的计算当内层过程访问外层过程的变量时需要知道跨了几层。比如层 2 的过程访问层 0 的变量层差是 2。这个层差会编码到LOD和STO指令的第一个参数里解释器执行时根据层差沿着静态链static link往上找活动记录。// 符号表查找返回变量所在层差和偏移 typedef struct { char name[MAX_NAME]; int kind; // 0常量, 1变量, 2过程 int level; // 声明所在层号 int addr; // 变量偏移或过程入口地址 int value; // 常量值 } Symbol; Symbol* lookup(char* name, int current_level, int* out_level_diff) { for (int lv current_level; lv 0; lv--) { for (int i table_top[lv]; i table_base[lv]; i--) { if (strcmp(sym_table[i].name, name) 0) { *out_level_diff current_level - sym_table[i].level; return sym_table[i]; } } } return NULL; // 未声明 }这段代码里table_base[lv]和table_top[lv]分别记录第 lv 层符号在全局符号表中的起始和结束下标。查找时从当前层往外层遍历找到后计算层差。注意常量查找和变量查找共用这个函数但常量不需要层差常量值直接内联到指令里。4.3 语义检查类型、重复声明与未声明引用语法分析通过不代表程序合法语义检查必须同步做。PL/0 的语义检查点不多但必须覆盖重复声明同一作用域内同名标识符只能声明一次。在插入符号表前先查当前层是否已存在。未声明引用赋值语句左侧、表达式中的标识符、过程调用名都必须能在符号表中找到。常量不可赋值const声明的标识符出现在:左侧时报错。过程调用参数PL/0 经典版本不支持参数传递如果扩展了参数要检查实参个数和形参个数是否匹配。条件表达式if和while的条件必须是关系表达式不能是裸的算术表达式除非语言定义允许隐式非零判断。这些检查在语法分析函数里顺手做掉不要等语法树建完再遍历一遍。递归下降的优势就是“边走边查”发现错误立即报报完继续走尽量一次编译报出所有语义错误。5. 代码生成与虚拟机执行从中间表示到可运行结果5.1 表达式求值的栈式代码生成PL/0 的目标代码是栈式指令序列表达式求值天然适合栈式生成。规则很简单遇到数字生成LIT压栈遇到变量生成LOD压栈遇到二元运算符先递归生成左右操作数的代码再生成OPR指令。比如x y * 2的生成顺序是LOD 0, x_addr ; 压入 x LOD 0, y_addr ; 压入 y LIT 0, 2 ; 压入 2 OPR 0, MUL ; 弹出 2 和 y压入 y*2 OPR 0, ADD ; 弹出 y*2 和 x压入 xy*2运算符优先级通过递归下降的层次自然处理expression处理加减term处理乘除factor处理括号和原子。不需要显式维护优先级表。# 表达式代码生成Python 伪代码 def gen_expression(self): self.gen_term() while self.cur.type in (PLUS, MINUS): op self.cur.type self.next_token() self.gen_term() if op PLUS: self.emit(OPR, 0, OPR_ADD) else: self.emit(OPR, 0, OPR_SUB) def gen_term(self): self.gen_factor() while self.cur.type in (TIMES, SLASH): op self.cur.type self.next_token() self.gen_factor() if op TIMES: self.emit(OPR, 0, OPR_MUL) else: self.emit(OPR, 0, OPR_DIV)emit函数把指令追加到代码数组同时返回当前指令地址方便后面回填跳转目标。注意除法要处理除零——可以在生成时插入检查也可以在解释器执行OPR_DIV时检查栈顶除数是否为零。5.2 控制流语句的跳转回填if和while需要生成条件跳转指令但跳转目标地址在生成跳转指令时还不知道必须等语句体生成完才能确定。经典做法是“回填”先生成一条占位跳转指令记录它的地址等目标确定后再修改该指令的跳转参数。以if cond then stmt为例生成 cond 的代码 JPC 0, ??? ; 条件为假时跳转到 stmt 之后 记录 JPC 指令地址 jpc_addr 生成 stmt 的代码 回填code[jpc_addr].a 当前代码地址while cond do stmt稍微复杂一点需要两个跳转条件为假时跳出循环循环体结束后无条件跳回条件判断处。记录循环开始地址 loop_start 生成 cond 的代码 JPC 0, ??? ; 条件为假时跳出 记录 jpc_addr 生成 stmt 的代码 JMP 0, loop_start ; 跳回条件判断 回填code[jpc_addr].a 当前代码地址回填是代码生成里最容易出错的地方血泪经验是每次回填后打印完整指令序列对照源码逐条验证跳转地址是否正确。我调试时会在每条指令后面注释对应的源码行号这样一眼就能看出跳转有没有跳错位置。5.3 虚拟机解释器活动记录与静态链生成的 P-code 需要一个解释器来执行。解释器的核心数据结构是栈数据栈存变量和临时值指令指针指向当前执行的指令基址指针指向当前活动记录的基地址。活动记录activation record的布局位置内容基址 0静态链指向外层过程活动记录的基址基址 1动态链指向调用者活动记录的基址基址 2返回地址基址 3 起局部变量和临时值LOD l, a的执行逻辑从当前基址出发沿静态链走 l 步找到目标活动记录基址然后取偏移 a 处的值压栈。STO类似只是方向相反。CAL创建新活动记录压入静态链当前层差对应的基址、动态链当前基址、返回地址然后跳转到过程入口。// 解释器主循环C 语言核心片段 while (running) { Instruction inst code[pc]; switch (inst.op) { case LIT: stack[top] inst.a; break; case LOD: { int base get_base(inst.l); // 沿静态链走 l 步 stack[top] stack[base inst.a]; break; } case STO: { int base get_base(inst.l); stack[base inst.a] stack[top--]; break; } case OPR: execute_opr(inst.a); // 算术、比较、输入输出 break; case JMP: pc inst.a; break; case JPC: if (stack[top--] 0) pc inst.a; break; case CAL: { // 创建新活动记录 stack[top 1] get_base(inst.l); // 静态链 stack[top 2] base_ptr; // 动态链 stack[top 3] pc; // 返回地址 base_ptr top 1; pc inst.a; break; } case INT: top inst.a; // 分配局部变量空间 break; } }get_base(l)函数沿静态链走 l 步从当前base_ptr开始每次取stack[base_ptr]作为新基址重复 l 次。这个函数是理解 PL/0 运行时结构的关键——静态链把嵌套作用域串成一条链层差就是链上走的步数。6. 避坑与排查PL/0 编译器课设里最容易翻车的五个地方6.1 符号表层号计算错误导致变量访问越界现象程序能编译通过但运行时读取变量得到垃圾值或者直接段错误。原因层差计算时把当前层号减错了比如内层过程访问同层变量时层差算成了 1 而不是 0。或者符号表压栈/弹栈时机不对退出过程时没清理该层的符号导致外层同名变量被内层覆盖。解决在lookup函数里加打印输出每次查找的标识符名、当前层号、找到的层号和计算出的层差。对照源码手工验证几个关键变量的层差。符号表弹栈的时机是过程体分析完毕、遇到end时不要提前也不要延后。6.2 跳转回填地址偏移一位现象if或while语句执行时跳转到了错误的位置程序行为完全不对。原因回填时填的是“当前代码地址”但解释器执行JPC后pc已经自增过了实际跳转目标应该是“下一条要执行的指令地址”。如果填的是“最后一条已生成指令的地址”就会偏移一位。解决统一约定——emit返回的是新指令的地址回填时用“当前代码数组长度”作为跳转目标因为下一条生成的指令就会放在这个位置。在回填后打印指令序列手工模拟执行几条跳转指令验证。6.3 过程调用时静态链指向错误现象递归调用返回后变量值错乱或者多层嵌套过程调用时访问外层变量得到错误结果。原因CAL指令创建活动记录时静态链应该指向“被调用过程声明所在层”的当前活动记录而不是调用者的活动记录。这两者在非递归直接调用时可能相同但递归或多层嵌套时不同。解决CAL l, a里的l是层差表示从调用者当前层到被调用过程声明层的层数差。创建活动记录时静态链的值是get_base(l)的结果。在解释器里加调试输出每次CAL时打印层差、计算出的静态链基址和调用者基址。6.4 表达式求值顺序与栈不平衡现象复杂表达式计算结果错误或者解释器执行到某条OPR时栈顶元素不是预期的操作数。原因递归下降生成表达式代码时左右操作数的生成顺序和OPR指令弹出顺序不匹配。栈式指令的约定是先压入左操作数再压入右操作数OPR弹出右操作数再弹出左操作数。如果生成顺序反了减法和除法就会算反。解决在gen_expression和gen_term里严格保证“先 gen 左再 gen 右最后 emit OPR”。在解释器的execute_opr里加断言检查栈深度是否足够弹出两个操作数。调试时打印每条OPR执行前的栈顶两个值。6.5 输入输出指令与宿主语言缓冲冲突现象read语句读不到用户输入或者write输出没有立即显示。原因C 语言的scanf/printf和解释器的输入输出指令混用时缓冲区刷新时机不对。特别是printf不带换行符时输出留在缓冲区里用户看不到提示信息。解决在write指令执行后强制fflush(stdout)在read指令执行前也fflush(stdout)确保提示信息先输出。如果宿主语言是 Python用sys.stdout.flush()。这个坑不涉及编译原理但调试时非常影响体验。7. 进阶验证用测试用例集反向检验编译器正确性课设验收时老师不会只看你跑一个hello world而是会拿一组覆盖各种语法特性的测试程序来跑。我建议自己先建一个测试用例集按特性分类每类至少三个用例正常用例、边界用例、错误用例。下面这张表是我当时用的分类框架测试类别正常用例边界用例错误用例常量与变量多常量多变量声明常量参与表达式重复声明表达式加减乘除混合多层括号嵌套除零条件语句if-then 单分支if 嵌套条件非关系表达式循环语句while 计数循环while 嵌套循环变量未声明过程调用无参过程调用递归调用调用未声明过程作用域内层访问外层变量三层嵌套访问已退出作用域变量验证方法每个用例先手工推导预期输出然后跑编译器看实际输出是否一致。不一致时先打印生成的 P-code 指令序列对照源码逐条检查指令生成是否正确如果指令序列正确但执行结果不对再检查解释器的活动记录管理。一个具体技巧给解释器加一个--trace开关开启后每执行一条指令就打印指令内容、执行前的栈顶五个元素、当前基址和指令指针。这样程序跑飞时你能看到是从哪条指令开始偏离预期的。这个 trace 输出会很长但定位问题时比单步调试快得多。我自己的习惯是每实现完一个语法特性立刻写三个测试用例跑一遍通过了再写下一个特性。不要等全部写完再统一测试——编译器 bug 的定位成本随代码量增长是超线性的早测早省心。希望帮到你。本文还有配套的精品资源点击获取