手写Pascal子集编译器：从词法到中间代码的完整实现

简介这份资源是面向计算机专业学生与编译原理初学者的Pascal子集编译器课程设计报告围绕词法分析、语法分析、语义分析与中间代码生成等核心环节展开帮助读者理解并动手实现一个小型编译程序的完整流程。压缩包内共1个doc文档约952KB以课程设计报告形式系统整理了需求分析、总体结构、接口描述与各阶段设计资料并附有团队分工与成绩评定说明。文档中详细说明了词法分析器的接口函数、符号表构建、关键字与标识符识别以及语法分析中分析表与自顶向下分析树的建立方式还涉及三地址码或四元式中间代码的生成规则与类型检查思路。目前已有240人学习适合需要完成编译原理课程设计、参考Pascal子集实现方案或梳理编译器各阶段设计文档的读者使用。1. 手写一个 Pascal 子集编译器为什么“不用工具”反而是理解编译原理的捷径很多人第一次接触编译原理印象里全是龙书里那套抽象符号和自动机考试能过但真给一段源码脑子里跑不出“它到底怎么被机器读懂”的画面。这份小型 Pascal 子集编译器设计报告恰恰反着来词法、语法、语义、中间代码全部手工实现明确禁用 YACC 这类生成器。听起来像自虐但它逼你把每个字符怎么变成记号、每条产生式怎么落到分析表、每个类型错误在哪一步被拦下来全部想清楚。编译器本质上是一条流水线字符流进记号流出语法树长出来中间代码吐出来。搞懂这条流水线每一站的输入输出契约比背十遍 FIRST/FOLLOW 定义都管用。下面就从这套手工实现里把“为什么这么设计、怎么实现的”一层层拆开。2. 词法分析器字符流怎么变成带属性的记号流2.1 接口设计为什么用全局数组而不是返回值词法分析器对外只暴露一个void lexout(void)没有参数也没有返回值结果全写进两个全局数组Symbol_stream[1000]存记号流symbol_table[100]存符号表。这种设计在工程上不算优雅但在教学编译器里是刻意为之——语法分析器需要的是“一次性拿到整条记号流”而不是边解析边回调。全局数组相当于一个约定好的共享缓冲区词法跑完语法直接遍历省掉了函数间传大结构体的麻烦。记号流的结构体只有两个字段typedef struct symbol { int atr; // 记号属性内部编码 char sname[9]; // 记号名有效字符数 8 } Symbol; Symbol Symbol_stream[1000];atr是内部编码sname是原始拼写。为什么两个都要留因为语法分析只看atr做表驱动而报错信息和符号表回填需要原始名字。常见的实现思路是让词法返回一个(token_type, lexeme)二元组这里用结构体数组把整条流固化下来好处是语法分析阶段可以反复回看前面的记号做预测分析时不用维护额外的回退逻辑。符号表项则更重typedef struct table_item { char name[9]; // 变量名 int address; // 目标地址 int type; // 类型 int demension; // 维数 int declare_row; // 声明行 int use_row[5]; // 引用行 int block; // 块索引号 } Tuple; Tuple symbol_table[100];注意declare_row和use_row[5]——设计要求明确要求符号表记录每个符号出现的行号和列号。这是词法阶段就要完成的“副作用”识别到一个标识符时不光要产出记号还要判断它是首次声明还是引用把行号填进对应槽位。use_row只留 5 个位置说明这套实现假设单个变量引用不超过 5 次超出就丢——教学编译器里这种“够用就行”的取舍很常见真做产品得换成动态数组或链表。2.2 关键字识别与内部编码一张表定生死关键字判断走的是int Iskeyword(char[])内部拿识别出的字符串去和静态数组比对static char keyword[N][10] { and,array,begin,boolean,do,else,end,false, function,if,integer,not,of,or,procedure, program,read,real,record,then,true,var, while,write };返回值设计得有点怪mod返回 1、or返回 2、and返回 3、div返回 4其他关键字返回 -1标识符返回 0。为什么偏偏把这四个运算符单独给正数因为它们在语法里既像关键字又像运算符词法阶段提前给固定编码语法分析构造预测分析表时可以直接当终结符用不用再查一次表。这是典型的“把歧义消解提前到词法层”的思路。完整的内部编码表覆盖了关键字、运算符、分隔符和字面量类别比如是 40、-是 41、id是 36、num是 35。这套编码是词法和语法之间的契约语法分析器的分析表行列索引直接用的就是这些整数改一个编码整张表都得跟着动。所以文档里专门要求“标明哪个 API 是词法和语法之间的接口”——就是lexout产出的Symbol_stream和这套编码约定。2.3 注释过滤与状态机一个state变量扛下所有词法分析器把源文件整个读进buffer[Max]然后逐字符扫描。注释处理靠两个计数器digit_l、digit_r记录{}的配对/**/则另走分支。真正决定当前字符怎么归类的是一个state变量state1表示当前正在拼的是常数否则按标识符或符号处理state1单独标记小数点的出现防止1.2.3这种非法数字被吞掉。这种“单状态变量 逐字符 switch”的写法本质是一个极简的确定性有限自动机只是没画状态转移图而是用 if-else 硬编码。血泪经验在于注释嵌套和字符串里的引号是最容易翻车的地方。比如{出现在字符串...里不能被当注释起始这套实现靠strings[50]缓冲区单独处理双引号内容来规避。如果让重来一遍我会把状态机显式化成枚举加转移表而不是靠state和state1两个布尔量互相纠缠——后者在加新词法规则时极容易踩坑。2.4 输出文件为什么词法要能单独测试设计要求里有一条很关键词法分析器要能单独测试输入源程序文件把识别的终结符号打印到文件。这套实现产出了五个文件符号表、常数表、统计信息、记号流、终结符。单独可测意味着词法层的正确性可以脱离语法独立验证——给一段只有声明没有语句的源码看符号表的declare_row填得对不对给一段带注释的代码看记号流里注释有没有被干净滤掉。统计信息里的line_count、word_count、char_count、error_count不是摆设。行计数在报错时定位用记号流计数用来校验数组有没有越界上限 1000错误计数则让测试者一眼看出这段源码触发了多少词法错误。常见的实现思路是把这些计数器做成结构体统一管理这里散成全局变量好处是写起来快坏处是任何一个函数都可能偷偷改掉它们调试时得全局搜索。3. 语法分析预测分析表是怎么从 FIRST/FOLLOW 长出来的3.1 FIRST 集计算递归下降求闭包FIRST 集的计算封装在FirstGroup类里核心接口是GetFirstGroup(int sym)对每个文法符号求一次结果存进firstgroup[15]数组。算法严格按三条规则来终结符的 FIRST 是它自己产生式右部以 ε 开头则 ε 入集非终结符则沿着产生式右部逐个符号展开把每个Yi的 FIRST 去掉 ε 后并入直到某个Yi不含 ε 为止。insertFsg(int NT, int i, int m)这个接口名里的三个参数我一般会这么理解NT是目标非终结符i是源符号m是模式标志是否跳过 ε。它做的是把源符号的 FIRST 集合并进目标集同时用existed(int sym)去重。为什么 FIRST 集数组只开 15 个位置因为 Pascal 子集的单个非终结符可推导出的首终结符种类有限15 是拍脑袋定的上限超了就会静默截断——这是教学代码里典型的“假设输入规模可控”。3.2 FOLLOW 集从开始符号倒推FOLLOW 集的计算没有参数GetFollowGroup()一次性把所有非终结符的 FOLLOW 算完。规则同样三条$进开始符号的 FOLLOW对A - αBβFIRST(β) 去掉 ε 并入 FOLLOW(B)若 β 能推导出 ε则 FOLLOW(A) 整体并入 FOLLOW(B)。这里有个实现细节值得说matchsymbol(char* str)负责把符号名映射成内部编码FIRST 和 FOLLOW 的计算都依赖它。也就是说符号表终结符表Tsymbol和非终结符表NTsymbol必须在求集之前就建好。顺序错了matchsymbol返回垃圾值整个分析表就是错的而且不会报错——这是语法阶段最隐蔽的坑之一。3.3 预测分析表构造-1 就是 error分析表存在int analysistable[][]里构造算法直接照搬教材先全填 -1然后逐条扫描产生式A - α编号为 i对 FIRST(α) 里每个终结符 a把analysistable[A][a]赋成 i如果 ε 在 FIRST(α) 里再对 FOLLOW(A) 里每个 b 赋 i。没被赋值的格子保持 -1表示语法错误。产生式本身存在int generator[][]里每行一个产生式generator[i][0]是左部generator[i][1..10]是右部符号编码。这个二维数组就是整个语法分析器的“程序”——分析表里的数字 i 直接索引到这一行取出右部再压栈。为什么用定长 10因为 Pascal 子集的产生式右部最长不超过 10 个符号超了就得改结构。这种硬编码上限在教学项目里到处都是读源码时看到数组第二维是常数基本就能反推出作者对文法规模的假设。3.4 分析树输出让“看不见的推导”变得可验证设计要求里明确要“以直观的方式输出分析树”并且“改变源程序分析树将发生变化”。这套实现走的是自顶向下预测分析每匹配一个终结符、每展开一个非终结符就往树结构里挂一个节点。输出时按层缩进打印一眼能看出program下面挂了identifier_list、declarations、subprogram_declarations、compound_statement四棵子树。分析树的价值不在“好看”而在调试。语法分析出错时-1 格子只告诉你“当前非终结符遇到当前终结符不合法”但分析树能告诉你“走到这一步之前前面已经成功展开了哪些产生式”。常见的排查手法是拿一段最小可复现源码对比分析树和预期文法推导看第一个分叉点在哪。如果分析树在statement层就断了问题多半在表达式相关的产生式如果在declarations层就歪了回去查type和identifier_list的 FIRST 集有没有算错。4. 语义分析与中间代码类型检查怎么嵌进语法树遍历4.1 翻译方案把语义动作写进产生式语义部分的核心是一套语法制导翻译方案每个产生式后面跟一段语义动作。比如变量声明的翻译模式declaration - identifier_list : type { identifier_list.t : type.t; identifier_list.width : type.width } ; declaration这段的意思是当语法树走到declaration节点先递归处理identifier_list和type两个子节点拿到类型t和宽度width再回填给identifier_list。width是给符号表算偏移量用的——integer宽 4、real宽 8数组则用(上界 - 下界) * 元素宽度算总大小。符号表的address字段就是靠这个width累加出来的相对偏移。为什么语义动作要挂在产生式上而不是单独遍历一遍树因为类型信息是自底向上汇聚的叶子节点的类型确定后父节点才能做类型检查。把动作嵌在推导过程里天然就是后序遍历的顺序省掉一次额外的树遍历。代价是语法分析和语义分析耦合在一起改文法就得同步改动作——这也是为什么文档要求“在写程序之前先设计语义动作写出翻译模式”。4.2 类型检查与类型转换inttoreal从哪来类型检查覆盖三类场景赋值语句检查等号两边类型是否一致if/while的条件表达式必须是boolean基本运算的两个操作数类型要匹配。不匹配时不是直接报错而是尝试类型转换——整数和实数混合运算时插入一条inttoreal中间代码把整数提升为实数。看simple_expression的语义动作四种类型组合分别处理int op int直接生成临时变量real op real同理int op real先把左边inttoreal再算real op int先把右边转实数。每种情况都调newtemp申请临时变量名然后emit一条三地址码。这套逻辑就是编译原理教材里“类型强制”的标准实现难点不在算法在于四种分支容易漏写一种漏了就会在混合运算时生成类型不一致的中间代码后面跑起来结果错得莫名其妙。4.3 符号表管理堆栈式作用域符号表用SqStack组织mktable()新建一张表enter()插入变量push/pop管理作用域。虽然设计要求写明“不包含嵌套过程”但翻译方案里仍然保留了subprogram_head里mktablepush的结构说明这套代码是从完整 Pascal 编译器裁剪下来的嵌套过程的骨架还在只是没启用。enter(SqStack * tableptr, char * name, int type, int addr)的addr参数就是前面算出来的偏移量。符号表查找走lookahead(int k)返回节点 k 最左子节点对应的字符串——这个接口名字起得有点误导它实际做的是“取语法树某节点的最左叶子”用来在语义动作里拿到标识符名字。为什么不用节点直接存名字因为语法树节点只存了子节点指针名字在叶子节点上得顺着最左路径摸下去。4.4 中间代码生成三地址码覆盖赋值、数组、指针、函数中间代码采用三地址码emit负责往代码序列里追加一条。覆盖的功能包括赋值、数组访问、指针解引用和函数调用。赋值语句的语义动作最简单statement - variable assignop expression { emit(variable.name : expression.name) }数组和指针的处理在variable的推导里通过factor和variable的语义动作组合出带下标的地址计算。函数调用的参数传递走expression_list每个实参enterq(q, expression.name)压进参数队列调用点再统一取。设计要求要求文档里描述“采用何种参数传递机制”——这套实现用的是值传递实参表达式先求值成临时变量再按顺序传给形参。中间代码的种类在文档里列了清单包括赋值、加减乘除、关系运算、无条件跳转、条件跳转、参数传递、函数调用、返回等。每种都对应emit的一个调用点读源码时搜emit(就能把所有中间代码生成位置找全。这种“一种中间代码一个 emit 调用”的写法好处是生成逻辑和语法树结构一一对应坏处是优化空间几乎为零——每条三地址码都是独立的没有基本块划分也没有公共子表达式消除。教学编译器做到这一步就够了真要做优化得在中间代码之上再加一层。5. 避坑与排查手工编译器的五个高频翻车点5.1 符号表行号错位现象是报错指向错误行现象语法或语义报错时提示的行号和源码实际行对不上差一两行甚至更多。原因多半是词法阶段的行计数在注释或换行符处理时漏加或多加——{}注释跨行时里面的换行符有没有计入line_count不同实现选择不同。解决在词法分析器里单独打日志每读一个\n就打印当前行号和源文件对照确认注释块内的换行是否被正确统计。我一般会在lexout开头把line_count初始化为 1 而不是 0避免第一行报错显示第 0 行。5.2 FIRST 集算错导致分析表大面积 -1现象一段合法源码在语法分析时频繁报错分析表里大量格子是 -1但文法本身没问题。原因通常是 FIRST 集计算时 ε 的处理有误——某个非终结符明明能推导出 ε但insertFsg的m参数传错导致 ε 没被正确传播进而 FOLLOW 集也跟着错分析表该填的格子没填。解决写一个小测试对每个非终结符打印 FIRST 和 FOLLOW 集和手工推导结果逐项比对。重点查那些右部以可空非终结符结尾的产生式。5.3 类型转换漏分支混合运算结果类型飘忽现象integer和real混合运算时中间代码里临时变量的类型和预期不符运行时结果精度丢失或直接类型错误。原因simple_expression的四种类型组合只写了三种漏了real op int或int op real其中一种走了默认分支。解决在emit生成临时变量时强制打印变量类型跑一段包含全部四种组合的测试源码看每种组合生成的inttoreal指令数量对不对。四种组合应该各有一条对应的转换路径少一条就是漏了。5.4 数组维数计算越界demension字段永远是 0现象符号表里数组变量的demension字段始终是 0语义分析时数组访问不报错但地址算错。原因type - array [digits1 .. digits2] of standard_type的语义动作里type.width算对了但忘了把维数写回符号表项的demension字段——enter调用时传的参数里没有维数。解决检查declaration的语义动作确认identifier_list回填时把type的维数信息一并带过去。这个坑很隐蔽因为宽度算对了只有数组下标访问才会暴露。5.5 分析树输出层级错乱缩进对不上推导顺序现象分析树打印出来子节点挂到了错误的父节点下或者同一层的节点缩进不一致。原因树节点插入时用的父节点指针取错了——lookahead(k)返回的是最左叶子如果拿它当父节点挂新节点树结构就歪了。解决在挂节点的地方打印父节点和子节点的符号名对照文法推导手工核对前三层。预测分析是自顶向下的父节点一定比子节点先创建按创建顺序打日志就能定位哪一步挂错了。6. 设计取舍为什么教学编译器敢用全局数组和定长上限这套实现里到处都是“够用就行”的痕迹记号流上限 1000、符号表上限 100、FIRST 集数组 15 个位置、产生式右部定长 10、引用行只记 5 次。放在生产环境里这些全是定时炸弹但在教学编译器里它们是刻意的简化目的是把注意力从内存管理挪到编译流程本身。全局数组省掉了模块间传参和生命周期管理定长上限省掉了动态扩容逻辑换来的是每个阶段的输入输出都能用肉眼在 txt 文件里核对——符号表、常数表、记号流、终结符、统计信息五个文件一摆整条流水线的中间状态全透明。真正值得琢磨的取舍在“手工实现 vs 工具生成”这一层。用 YACC 或 ANTLR语法分析几行声明就出来了但 FIRST/FOLLOW 怎么算、分析表怎么填、冲突怎么消解全被工具藏进了黑匣子。手工写一遍你会真切体会到预测分析表的每个 -1 格子都是一次“这里不能这么推导”的硬约束类型检查的每个分支都是一次“编译器替程序员兜底”的决策。这种体感看多少遍教材都换不来。验证这套编译器是否真的 work我的习惯是准备三组源码一组全合法跑通看中间代码和最终结果一组只有词法错误比如非法字符确认报错行号准确一组语法合法但语义错误比如把real赋给integer变量不做转换确认类型检查能拦住。三组都过基本就能信这条流水线是通的。从那以后我每次读别人的编译器代码都强制先找它的符号表结构和中间代码种类——这两样定了整个编译器的设计骨架就清楚了。希望帮到你。本文还有配套的精品资源点击获取