简介小型Pascal子集编译器设计报告是一份以北京邮电大学编译原理课程设计为背景的完整报告文档面向学习编译原理、需要完成或参考编译器课程设计的高校学生。报告覆盖词法分析、语法分析、语义分析、中间代码生成与目标代码生成等全部阶段详细说明了Pascal子集文法下的分析表构造、FIRST/FOLLOW集求解函数、分析树输出方式、三地址码/四元式中间表示、类型检查与转化以及函数调用参数传递机制等设计要点。同时给出了五位成员的团队分工、各类接口函数如词法分析器与语法分析器之间的调用接口和符号表数据结构便于理解编译器各模块的衔接也具体涉及词法分析器的接口定义、符号表行号列号记录方式及错误处理流程可供实际编码时参考。整个压缩包约952KB仅含1个doc文档。已有240人学习下载适合作为计算机专业编译原理课程设计的参考模板或实现对照。1. 小型Pascal子集编译器为什么还要自己写一个一个小型Pascal子集编译器设计报告——这个标题是不是让你想起了编译原理的期末课设很多人的第一反应是“又得造一个编译器”第二反应是“有没有现成代码可以改”。但真动手做的人都知道它根本不是照着龙书抄个词法分析那么简单。从选子集、定文法到中间表示每一步都在逼你做取舍而这个取舍的过程恰恰是这门课里最值钱的部分。读者心里的问题其实很实际这东西到底要多大工作量用什么语言写要不要用生成器设计报告写多少页下面我用一线工程视角把这个项目拆开先划边界再给实现方案然后列踩过的坑最后说报告怎么收尾。目标是让你照着能复现而不是停留在概念上。我见过有人花两周时间用工具跑通词法和语法最后却卡在语义分析和报告上。原因很简单工具生成帮你处理了识别却不能帮你看清一个程序变成了什么。所以我不推荐一上来就上生成器更建议把手写的递归下降完整走一遍。这样报告里才有属于你自己的设计权衡答辩时也经得住追问。2. 划边界词法、语法、语义该做到哪一层先说选型。小型Pascal子集编译器这种东西最容易失败的起点不是代码而是“什么都想做”。有人的报告里写支持指针、记录、集合、函数重载结果中期检查时连整数除法都没调通。子集就是要做减法设计报告的首要任务是在回答一个问题你的编译器能编译哪些Pascal程序不能编译哪些。2.1 子集选型砍掉什么保留什么常见做法是把Pascal的核心语法保留下来变量声明区、整数和实数、赋值语句、IF-THEN-ELSE、WHILE、FOR、BEGIN-END复合语句、WRITE输出。这套组合已经能覆盖表达式求值、控制流、作用域足够讲清编译器的各个阶段又不会把语义分析拖到不可控。如果要加一维整数数组我建议放到第二个迭代版本而不是第一版就把数组和下标检查全都塞进来。砍掉什么更关键。我在这个子集里会砍掉指针、记录、集合、数组下标越界检查、过程参数传递。函数可以保留但没有递归理由不是“太难”而是每一类语法特征都会牵出一条独立的语义规则和错误处理分支。设计报告里如果列了支持列表那每一项都得有对应的测试用例砍掉的内容也要单独写一段说明为什么砍答辩时这反而是加分项。给出一个示意性的文法边界这个边界将作为后面所有设计的基线program : PROGRAM ident ; block . block : var_part stmt_part var_part : VAR { ident (, ident)* : type ; } type : INTEGER | REAL stmt_part : comp_stmt comp_stmt : BEGIN stmt { ; stmt } END stmt : assign_stmt | if_stmt | while_stmt | for_stmt | write_stmt | comp_stmt if_stmt : IF expr THEN stmt [ ELSE stmt ] expr : simple_expr [ relop simple_expr ] simple_expr : term { addop term } term : factor { mulop factor } factor : number | ident | ( expr )这段文法定义了“子集”的边界。它把Pascal里的TYPE声明段、CASE、GOTO都排除掉了程序结构被压成“程序头 变量声明 BEGIN-END块”。参数说明[ ELSE stmt ]里的方括号表示ELSE可选这是后面悬空ELSE问题的主要来源{ ... }表示重复零次或多次ident是要由词法分析返回的标识符。这组规则是自己手写词法和语法时的依据不是设计文档里的装饰后面递归下降的每个函数都能在这条文法里找到对应项。2.2 词法分析手写扫描器还是用生成器词法分析阶段的选型常见选择是手写扫描器和生成器。生成器适合词法规则特别复杂的语言比如要处理Unicode、嵌套注释。但Pascal子集的词法非常规整保留字、标识符、数字、运算符、界符加起来不超过三十种。手写扫描器大概两百行就能覆盖而且你可以完全控制错误恢复的逻辑报错时给出行列号也更容易。从写报告的角度看手写扫描器的代码可以直接引用到文档附录里比贴生成器配置更有说服力。手写扫描器要处理的token类型包括关键字PROGRAM、VAR、BEGIN、END、IF、THEN、ELSE、WHILE、DO、FOR、TO、WRITE、标识符、整数、实数、赋值号:、运算符 - * / 、分隔符( ) , ; .。注意:必须是最长匹配一次读入两个字符不能先读冒号再单独读等号否则后面语法分析会莫名其妙地撞上一堆“期望变量名实际得到冒号”的错误。我一般会把手写扫描器做成一个独立模块对外只暴露next_token()接口。下面是一个最小版本的骨架用Python展示逻辑换成C或Java只是类型声明和内存管理的问题class Lexer: def __init__(self, text): self.text text self.pos 0 self.line 1 def next_token(self): self._skip_whitespace() if self.pos len(self.text): return (EOF, None, self.line) ch self.text[self.pos] if ch.isalpha(): return self._read_ident_or_keyword() if ch.isdigit(): return self._read_number() if self.text.startswith(:, self.pos): self.pos 2 return (:, :, self.line) if ch in -*/(),;:: self.pos 1 return (ch, ch, self.line) raise LexError(fline {self.line}: unexpected char {ch!r})逻辑说明_skip_whitespace负责跳过空格、换行、制表符并把line计数加一_read_ident_or_keyword先读完整串字母再去保留字表里判断是关键字还是普通标识符_read_number读数字并判断是否是带小数点的实数。参数说明返回值里的self.line非常关键后面语法报错和报告里的错误信息都要靠它建议从一开始就保留不要在调试时再补。LexError可以单独定义也可以直接复用语法异常但错误类型分开会更方便定位问题。这里有一个容易翻车的点Pascal的保留字和标识符都不区分大小写Begin、BEGIN和begin是同一个词。常见做法是把读取到的标识符统一转成大写再查保留字表。大小写归一化的时机放在词法阶段做一次后面符号表查找就再也不用关心大小写否则第4章里的重复声明检测会出现X和x不冲突的诡异情况。2.3 语法分析递归下降为什么是首选对这个子集递归下降是最直白的方案。相比LR生成器递归下降的每一段代码直接对应文法里的一条规则读代码就能读到文法。写报告时你可以把规则和函数对照着放进去不用额外画一堆状态图。另一个隐性好处是错误信息容易做好某个函数里发现预期符号不匹配时直接抛“第几行期望什么得到什么”比LR的冲突报告友好得多。递归下降要处理的核心问题是左递归。表达式文法expr : expr term不能直接写进函数否则会无限循环。解决办法是改写为expr : term { addop term }对应代码用循环累加def parse_expr(self): node self.parse_term() while self.peek() in (, -): op self.next_token()[1] right self.parse_term() node (binop, op, node, right) return node这段代码对应的文法就是simple_expr : term { addop term }。每次循环先看当前token是不是加号或减号是的话就吃掉运算符再解析一个term把它和左边已有的节点拼成一个二元运算树。参数说明peek()做的是不消耗token的前瞻只读不取递归下降通常只需要一个token的前瞻就够了不必像LL分析那样维护预测集合。(binop, op, node, right)这个三元结构在后面语义分析里可以直接复用。下一步是程序结构和语句块。Pascal的每个程序都以PROGRAM开头接着标识符和分号然后是VAR声明和BEGIN-END块。对应的递归下降大概长这样def parse_program(self): self._expect(PROGRAM) name self._expect(IDENT) self._expect(;) self.parse_block() self._expect(.)逻辑说明_expect检查当前token是否等于预期值等于就消费并返回不等于就抛异常。parse_program是最顶层的入口它规定了一个程序必须是以PROGRAM 名字 ;开头、以.结尾的文本。parse_block接下来会处理变量声明和复合语句。参数说明这个顶层函数只做结构匹配不检查名字有没有被重复使用重复检查放在符号表阶段更合适。2.4 语法错误恢复遇到报错不要立刻崩溃语法分析器如果一碰到错误就抛异常退出使用者会很不舒服程序里明明只有一个小错误却只能看到第一个报错改完再跑又看到第二个。我一般会在递归下降里加一层简单的错误恢复原则是“跳过本语句剩余部分同步到下一个分号或END继续分析”。这样一次能报出多个错误报告也能列一个错误个数统计。错误恢复的实现思路是在parse_stmt里包一层try-except捕获语法异常后调用一个synchronize方法把token流快进到;或END或EOF。里层语句的错误不会导致整个分析器退出但要注意不要在循环里反复报同一个错否则会变成死循环。这一节内容不多但在设计报告里很显眼能体现你考虑过真实编译器的用户体验。到这里词法、语法、语义的边界基本清楚了词法管“词对不对”语法管“结构对不对”语义管“意思对不对”。接下来进入中间阶段也就是从语法树到中间表示的转换。3. 写一个能跑的设计从符号表到三地址码语法树建出来之后真正的设计工作量才刚开始。很多同学把词法和语法写完跑通几个样例就觉得大功告成结果一算表达式就发现类型对不上变量还没声明就被使用。这一章讲语义阶段的核心符号表、类型检查、中间表示以及一个能证明设计跑通了的最小执行器。3.1 符号表和类型检查的设计符号表在这个子集里不需要做得太复杂但要保证两件事变量必须先声明后使用同一作用域里不允许重复声明。常见做法是做一个栈式符号表进入BEGIN-END块时压一层退出时弹一层。每个条目记录名字、类型、声明行号行号对报错非常有用。class SymTable: def __init__(self): self.scopes [{}] def push_scope(self): self.scopes.append({}) def pop_scope(self): self.scopes.pop() def declare(self, name, typ, line): if name in self.scopes[-1]: raise CompileError(fline {line}: duplicate variable {name}) self.scopes[-1][name] {type: typ, line: line} def lookup(self, name, line): for scope in reversed(self.scopes): if name in scope: return scope[name] raise CompileError(fline {line}: variable {name} not declared)逻辑说明scopes列表里的第一个元素永远是全局作用域进入复合语句时push_scope压一个新字典退出时pop_scope弹掉。declare只检查当前层所以两个不同块里的同名变量并不冲突lookup从内向外查找这是典型的作用域遮蔽规则。参数说明line不是可有可无的调试信息报告的错误处理章节会用到它所以声明和查找的接口都要带行号。类型检查在这个子集里主要是“整数和实数的隐式转换”。常见做法是遇到二元运算时先查左右子树的类型两边都是INTEGER结果就是INTEGER只要有一边是REAL结果就是REAL。赋值时允许INTEGER赋给REAL反过来要报错。不要在语法分析阶段顺手做类型检查等语法树完整建好后再走一趟访问器逻辑会更清晰也不容易把语法分析代码搞成一团乱麻。类型检查本身可以设计成一个只读的遍历器不改动语法树只收集类型信息。比如下面这个方法返回一个表达式的类型字符串def type_of(self, node): if node[0] num: return REAL if . in node[1] else INTEGER if node[0] var: return self.symtab.lookup(node[1], node[2])[type] if node[0] binop: lt self.type_of(node[2]) rt self.type_of(node[3]) return REAL if REAL in (lt, rt) else INTEGER逻辑说明叶子节点里数字字面量通过有没有小数点区分REAL和INTEGER变量通过符号表查类型。二元运算的规则就一行只要左右任意一边是REAL结果就是REAL。参数说明node[2]和node[3]对应语法树里二元运算的左子树和右子树与2.3里语法分析生成的(binop, op, node, right)结构保持一致。这个type_of只返回类型不修改树方便在赋值语句里单独检查。3.2 中间表示三地址码还是栈式代码中间表示的选择会影响后面代码生成和报告篇幅。常见的两条路线是栈式代码和三地址码。栈式代码像虚拟机指令直接进栈出栈生成简单但三地址码更接近人们熟悉的汇编每条指令形如result : operand1 op operand2语义非常直白设计报告里展示起来也最直观。我推荐三地址码具体形式是四元式op, arg1, arg2, result。比如a b * c可以翻译成两条*, b, c, t1然后, a, t1, t2。临时变量从t0开始编号。这样写最大的好处是后面无论做解释器还是翻译成C代码都只需要把四元式按顺序处理一遍不需要再重新分析语法树。class IRGenerator: def __init__(self): self.insts [] self.tmp 0 def gen(self, op, arg1, arg2None, resultNone): if result is None: result ft{self.tmp} self.tmp 1 self.insts.append((op, arg1, arg2, result)) return result逻辑说明gen负责分配临时变量并记录指令。result传空时自动生成t0、t1这样的名字表达式递归过程中不用手动管理临时变量编号。参数说明arg1和arg2对单目运算可以不填但建议统一保留四个字段后面打印和解释执行都不用做特殊分支。四元式的打印格式也要在一开始定好报告里展示时所有指令保持一致。3.3 从语法树到三地址码一趟遍历有了IRGenerator遍历语法树生成三地址码的代码会很短。每个节点处理自己的子节点把结果串起来就好。下面是二元运算节点的处理def emit_expr(self, node): if node[0] num: return node[1] if node[0] var: return node[1] if node[0] binop: left self.emit_expr(node[2]) right self.emit_expr(node[3]) return self.ir.gen(node[1], left, right)逻辑说明叶子节点直接返回名字或常量二元运算先递归生成左操作数和右操作数的代码再调用gen把运算本身落成一条三地址码。控制流语句如WHILE需要生成跳转指令这是另一个容易疏忽的点循环体的入口和退出标签要提前留好LABEL和JUMP也需要作为四元式的操作符否则后面解释执行时没法跳转。控制流的生成建议单独放在一个方法里不要和表达式生成混在一起。WHILE的典型模式是先记一个标签然后判断条件条件为假跳到结束标签为真执行循环体循环体末尾再跳回条件标签。给标签编号同样用计数器比如L0、L1避免和临时变量混淆。3.4 最小执行器用四元式跑出最终结果到这里设计报告的核心链路已经完整词法分析、语法树、符号表、类型检查、三地址码。最后一个能证明链路跑通的手段是写一个最小执行器。执行器的思路很简单维护一个变量表按顺序遍历指令、-、*、/直接在值上运算JUMP修改程序计数器LABEL不做任何操作。def run(insts, vars): pc 0 while pc len(insts): op, a1, a2, res insts[pc] if op LABEL: pc 1 elif op JUMP: pc labels[a1] elif op in (, -, *, /): vars[res] calc(op, value(vars, a1), value(vars, a2)) pc 1 return vars逻辑说明value(vars, name)负责取变量值或常量值实现时先看是不是纯数字再看是不是变量表里的名字。calc就是普通的四则运算。参数说明labels字典要在执行前先扫描一遍指令集把每个LABEL对应的编号映射到指令下标这样JUMP才能直接跳。这个执行器虽然简陋但足以把测试程序跑出正确结果报告里也可以拿它来演示中间表示的有效性。4. 避坑指南编译原理课设里最常见的翻车点这一章是血泪经验每一条都来自实际调试不是理论推演。你在设计报告里如果把这些作为“已知问题与解决方案”列出来答辩老师通常会认为你真的跑过而不是在网上拼了一份文档。4.1 悬空ELSE静默错配比报错更可怕现象程序里嵌套IF-THEN-ELSE源代码里ELSE想挂在外层IF上生成的代码却挂到了内层算出来的结果完全不对而且编译过程没有任何报错。原因文法里的if_stmt : IF expr THEN stmt [ ELSE stmt ]是典型的二义性文法。递归下降如果不做特殊约定ELSE会优先匹配最近的IF。解决在解析IF语句时遇到IF expr THEN后面的stmt可以直接递归解析但ELSE分支必须在递归返回后立即处理。更可靠的办法是让内部stmt的解析禁止在遇到ELSE时结束语法分析器在判定一个stmt结束时先看一眼当前token是不是ELSE如果是就留给外层。设计报告里把这一条写进“文法设计说明”比贴一堆状态机图更能体现你理解了问题。4.2 变量先使用后声明符号表顺序的坑现象程序里先用变量再声明编译器第一遍扫描没有报错等到解释执行时才报undefined。原因符号表只在一个方向上做检查忘记了Pascal声明区的特殊性。Pascal的变量声明集中在程序头必须在执行任何语句前全部处理完而不是边处理语句边声明。解决语法分析阶段先把VAR部分完整解析把所有声明填进符号表然后再进入BEGIN-END块解析语句。我一般会在block的解析函数里分两步先parse_var_part再parse_stmt_part两步之间不做任何语句分析。这个顺序在报告里可以用一个小流程图标出来简单但有效。4.3 实数比较导致死循环WHILE条件永远成立现象用REAL类型做WHILE循环的控制变量例如x : x 0.1循环条件x 1.0结果程序不退出。原因浮点数二进制表示不精确0.1累加十次后不是精确的1.0可能永远小于1.0。这不是编译器生成代码的问题而是程序本身的问题但用户会认为你的编译器坏了。解决在设计报告里明确说明本子集对REAL的运算采用双精度浮点并建议控制循环次数或使用可容忍误差。更进一步的方案是引入一个简单的常量折叠如果能静态判断循环条件恒真或恒假就给出警告。这个特性不加也完全没问题但是报告里写一句“已知局限”能避免很多不必要的质疑。4.4 词法分析大小写归一化保留字识别失败现象程序里写Begin词法分析把它当成了标识符语法分析报“期望BEGIN实际得到标识符”。原因检查保留字时直接用原始文本去查字典而Pascal不区分大小写。解决扫描器读取标识符后先做upper()再查表同时把所有保留字表写成大写。这里有个附加坑Pascal的标识符本身也不区分大小写所以符号表里做lookup时也要统一大小写否则X和x会被当成两个不同变量重复声明检测就形同虚设。4.5 分号规则最后一条语句后面不能有多余分号现象BEGIN a : 1; END报错用户很困惑。原因Pascal的BEGIN-END块里分号是语句之间的分隔符不是语句结束符。文法里写的是stmt { ; stmt }最后一个stmt后面不允许有分号。解决解析复合语句时先解析第一个stmt然后循环判断;后面是否还有内容如果有就继续解析。更宽容的做法是把分号改成可选的终结符这偏离了标准Pascal但能让用户少骂你。两种方案都可以但要在报告里写明你是哪一种不要做成了“能跑但说不清规则”的实现。5. 收尾技巧生成一个能看的报告并快速验证设计报告本身不是写给老师看的材料而是你设计过程的复盘。写报告有个很实用的顺序先写测试用例再写编译器的模块最后根据测试结果补报告。这样做的好处是你报告里的每个功能都有对应的测试证据不会出现“写了但不工作”的功能。5.1 测试驱动设计先写测试用例再写编译器把要支持的Pascal程序全部列出来从最简单的PROGRAM p; BEGIN END.开始到包含嵌套IF和WHILE的程序为止。每个测试文件命名带上编号和意图例如test06_while_loop.pas。编译器每完成一个阶段就跑一遍测试集记录哪些通过哪些失败。报告的性能分析表格就可以直接引用这个测试记录数据真实不靠编。5.2 测试用例的构造怎么测才算覆盖覆盖不能只看数量。建议按三组来写合法程序组验证功能非法程序组验证错误检测边界程序组验证词法和语法边界。边界组至少要包含空程序、只有声明的程序、超长标识符、嵌套到第五层的BEGIN-END以及所有一元运算符和括号的组合。非法程序组每条都要写清楚期望报什么错误错误信息里是否包含行号。5.3 报告怎么写才像工程文档报告的框架按照“需求定义、设计、实现、测试、结论”五个部分来组织中间插入文法和核心数据结构测试部分用表格列出通过数和失败数。不推荐写那种只有代码加注释的报告更适合画两个图一个是整体模块图一个是符号表作用域切换图。图不需要精美能表示清楚模块边界就行。我自己的习惯是花一半时间写编译器再花三分之一的时间跑测试和修正剩下的时间才写报告。这个顺序能保证报告里的每一个“设计决策”都是你实际做过的选择而不是从网上参考文档里搬来的套话。编译器的各项设计往往要到测试阶段才会真正暴露缺陷那时候改的设计比凭空想出来的可靠得多。一定要给自己留一个后悔药每次修改代码前把当前版本的基本测试跑一遍。这个习惯帮我避免过很多次“调完一个 bug 带出两个 bug”的窘境。做一个能执行、能报错、有测试依据的小型Pascal子集编译器比一个功能列表华丽但跑不通的程序有价值得多。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/14 21:18:11 · 阅读 1.2k 小型Pascal子集编译器设计与实现：从词法分析到三地址码
简介小型Pascal子集编译器设计报告是一份以北京邮电大学编译原理课程设计为背景的完整报告文档面向学习编译原理、需要完成或参考编译器课程设计的高校学生。报告覆盖词法分析、语法分析、语义分析、中间代码生成与目标代码生成等全部阶段详细说明了Pascal子集文法下的分析表构造、FIRST/FOLLOW集求解函数、分析树输出方式、三地址码/四元式中间表示、类型检查与转化以及函数调用参数传递机制等设计要点。同时给出了五位成员的团队分工、各类接口函数如词法分析器与语法分析器之间的调用接口和符号表数据结构便于理解编译器各模块的衔接也具体涉及词法分析器的接口定义、符号表行号列号记录方式及错误处理流程可供实际编码时参考。整个压缩包约952KB仅含1个doc文档。已有240人学习下载适合作为计算机专业编译原理课程设计的参考模板或实现对照。1. 小型Pascal子集编译器为什么还要自己写一个一个小型Pascal子集编译器设计报告——这个标题是不是让你想起了编译原理的期末课设很多人的第一反应是“又得造一个编译器”第二反应是“有没有现成代码可以改”。但真动手做的人都知道它根本不是照着龙书抄个词法分析那么简单。从选子集、定文法到中间表示每一步都在逼你做取舍而这个取舍的过程恰恰是这门课里最值钱的部分。读者心里的问题其实很实际这东西到底要多大工作量用什么语言写要不要用生成器设计报告写多少页下面我用一线工程视角把这个项目拆开先划边界再给实现方案然后列踩过的坑最后说报告怎么收尾。目标是让你照着能复现而不是停留在概念上。我见过有人花两周时间用工具跑通词法和语法最后却卡在语义分析和报告上。原因很简单工具生成帮你处理了识别却不能帮你看清一个程序变成了什么。所以我不推荐一上来就上生成器更建议把手写的递归下降完整走一遍。这样报告里才有属于你自己的设计权衡答辩时也经得住追问。2. 划边界词法、语法、语义该做到哪一层先说选型。小型Pascal子集编译器这种东西最容易失败的起点不是代码而是“什么都想做”。有人的报告里写支持指针、记录、集合、函数重载结果中期检查时连整数除法都没调通。子集就是要做减法设计报告的首要任务是在回答一个问题你的编译器能编译哪些Pascal程序不能编译哪些。2.1 子集选型砍掉什么保留什么常见做法是把Pascal的核心语法保留下来变量声明区、整数和实数、赋值语句、IF-THEN-ELSE、WHILE、FOR、BEGIN-END复合语句、WRITE输出。这套组合已经能覆盖表达式求值、控制流、作用域足够讲清编译器的各个阶段又不会把语义分析拖到不可控。如果要加一维整数数组我建议放到第二个迭代版本而不是第一版就把数组和下标检查全都塞进来。砍掉什么更关键。我在这个子集里会砍掉指针、记录、集合、数组下标越界检查、过程参数传递。函数可以保留但没有递归理由不是“太难”而是每一类语法特征都会牵出一条独立的语义规则和错误处理分支。设计报告里如果列了支持列表那每一项都得有对应的测试用例砍掉的内容也要单独写一段说明为什么砍答辩时这反而是加分项。给出一个示意性的文法边界这个边界将作为后面所有设计的基线program : PROGRAM ident ; block . block : var_part stmt_part var_part : VAR { ident (, ident)* : type ; } type : INTEGER | REAL stmt_part : comp_stmt comp_stmt : BEGIN stmt { ; stmt } END stmt : assign_stmt | if_stmt | while_stmt | for_stmt | write_stmt | comp_stmt if_stmt : IF expr THEN stmt [ ELSE stmt ] expr : simple_expr [ relop simple_expr ] simple_expr : term { addop term } term : factor { mulop factor } factor : number | ident | ( expr )这段文法定义了“子集”的边界。它把Pascal里的TYPE声明段、CASE、GOTO都排除掉了程序结构被压成“程序头 变量声明 BEGIN-END块”。参数说明[ ELSE stmt ]里的方括号表示ELSE可选这是后面悬空ELSE问题的主要来源{ ... }表示重复零次或多次ident是要由词法分析返回的标识符。这组规则是自己手写词法和语法时的依据不是设计文档里的装饰后面递归下降的每个函数都能在这条文法里找到对应项。2.2 词法分析手写扫描器还是用生成器词法分析阶段的选型常见选择是手写扫描器和生成器。生成器适合词法规则特别复杂的语言比如要处理Unicode、嵌套注释。但Pascal子集的词法非常规整保留字、标识符、数字、运算符、界符加起来不超过三十种。手写扫描器大概两百行就能覆盖而且你可以完全控制错误恢复的逻辑报错时给出行列号也更容易。从写报告的角度看手写扫描器的代码可以直接引用到文档附录里比贴生成器配置更有说服力。手写扫描器要处理的token类型包括关键字PROGRAM、VAR、BEGIN、END、IF、THEN、ELSE、WHILE、DO、FOR、TO、WRITE、标识符、整数、实数、赋值号:、运算符 - * / 、分隔符( ) , ; .。注意:必须是最长匹配一次读入两个字符不能先读冒号再单独读等号否则后面语法分析会莫名其妙地撞上一堆“期望变量名实际得到冒号”的错误。我一般会把手写扫描器做成一个独立模块对外只暴露next_token()接口。下面是一个最小版本的骨架用Python展示逻辑换成C或Java只是类型声明和内存管理的问题class Lexer: def __init__(self, text): self.text text self.pos 0 self.line 1 def next_token(self): self._skip_whitespace() if self.pos len(self.text): return (EOF, None, self.line) ch self.text[self.pos] if ch.isalpha(): return self._read_ident_or_keyword() if ch.isdigit(): return self._read_number() if self.text.startswith(:, self.pos): self.pos 2 return (:, :, self.line) if ch in -*/(),;:: self.pos 1 return (ch, ch, self.line) raise LexError(fline {self.line}: unexpected char {ch!r})逻辑说明_skip_whitespace负责跳过空格、换行、制表符并把line计数加一_read_ident_or_keyword先读完整串字母再去保留字表里判断是关键字还是普通标识符_read_number读数字并判断是否是带小数点的实数。参数说明返回值里的self.line非常关键后面语法报错和报告里的错误信息都要靠它建议从一开始就保留不要在调试时再补。LexError可以单独定义也可以直接复用语法异常但错误类型分开会更方便定位问题。这里有一个容易翻车的点Pascal的保留字和标识符都不区分大小写Begin、BEGIN和begin是同一个词。常见做法是把读取到的标识符统一转成大写再查保留字表。大小写归一化的时机放在词法阶段做一次后面符号表查找就再也不用关心大小写否则第4章里的重复声明检测会出现X和x不冲突的诡异情况。2.3 语法分析递归下降为什么是首选对这个子集递归下降是最直白的方案。相比LR生成器递归下降的每一段代码直接对应文法里的一条规则读代码就能读到文法。写报告时你可以把规则和函数对照着放进去不用额外画一堆状态图。另一个隐性好处是错误信息容易做好某个函数里发现预期符号不匹配时直接抛“第几行期望什么得到什么”比LR的冲突报告友好得多。递归下降要处理的核心问题是左递归。表达式文法expr : expr term不能直接写进函数否则会无限循环。解决办法是改写为expr : term { addop term }对应代码用循环累加def parse_expr(self): node self.parse_term() while self.peek() in (, -): op self.next_token()[1] right self.parse_term() node (binop, op, node, right) return node这段代码对应的文法就是simple_expr : term { addop term }。每次循环先看当前token是不是加号或减号是的话就吃掉运算符再解析一个term把它和左边已有的节点拼成一个二元运算树。参数说明peek()做的是不消耗token的前瞻只读不取递归下降通常只需要一个token的前瞻就够了不必像LL分析那样维护预测集合。(binop, op, node, right)这个三元结构在后面语义分析里可以直接复用。下一步是程序结构和语句块。Pascal的每个程序都以PROGRAM开头接着标识符和分号然后是VAR声明和BEGIN-END块。对应的递归下降大概长这样def parse_program(self): self._expect(PROGRAM) name self._expect(IDENT) self._expect(;) self.parse_block() self._expect(.)逻辑说明_expect检查当前token是否等于预期值等于就消费并返回不等于就抛异常。parse_program是最顶层的入口它规定了一个程序必须是以PROGRAM 名字 ;开头、以.结尾的文本。parse_block接下来会处理变量声明和复合语句。参数说明这个顶层函数只做结构匹配不检查名字有没有被重复使用重复检查放在符号表阶段更合适。2.4 语法错误恢复遇到报错不要立刻崩溃语法分析器如果一碰到错误就抛异常退出使用者会很不舒服程序里明明只有一个小错误却只能看到第一个报错改完再跑又看到第二个。我一般会在递归下降里加一层简单的错误恢复原则是“跳过本语句剩余部分同步到下一个分号或END继续分析”。这样一次能报出多个错误报告也能列一个错误个数统计。错误恢复的实现思路是在parse_stmt里包一层try-except捕获语法异常后调用一个synchronize方法把token流快进到;或END或EOF。里层语句的错误不会导致整个分析器退出但要注意不要在循环里反复报同一个错否则会变成死循环。这一节内容不多但在设计报告里很显眼能体现你考虑过真实编译器的用户体验。到这里词法、语法、语义的边界基本清楚了词法管“词对不对”语法管“结构对不对”语义管“意思对不对”。接下来进入中间阶段也就是从语法树到中间表示的转换。3. 写一个能跑的设计从符号表到三地址码语法树建出来之后真正的设计工作量才刚开始。很多同学把词法和语法写完跑通几个样例就觉得大功告成结果一算表达式就发现类型对不上变量还没声明就被使用。这一章讲语义阶段的核心符号表、类型检查、中间表示以及一个能证明设计跑通了的最小执行器。3.1 符号表和类型检查的设计符号表在这个子集里不需要做得太复杂但要保证两件事变量必须先声明后使用同一作用域里不允许重复声明。常见做法是做一个栈式符号表进入BEGIN-END块时压一层退出时弹一层。每个条目记录名字、类型、声明行号行号对报错非常有用。class SymTable: def __init__(self): self.scopes [{}] def push_scope(self): self.scopes.append({}) def pop_scope(self): self.scopes.pop() def declare(self, name, typ, line): if name in self.scopes[-1]: raise CompileError(fline {line}: duplicate variable {name}) self.scopes[-1][name] {type: typ, line: line} def lookup(self, name, line): for scope in reversed(self.scopes): if name in scope: return scope[name] raise CompileError(fline {line}: variable {name} not declared)逻辑说明scopes列表里的第一个元素永远是全局作用域进入复合语句时push_scope压一个新字典退出时pop_scope弹掉。declare只检查当前层所以两个不同块里的同名变量并不冲突lookup从内向外查找这是典型的作用域遮蔽规则。参数说明line不是可有可无的调试信息报告的错误处理章节会用到它所以声明和查找的接口都要带行号。类型检查在这个子集里主要是“整数和实数的隐式转换”。常见做法是遇到二元运算时先查左右子树的类型两边都是INTEGER结果就是INTEGER只要有一边是REAL结果就是REAL。赋值时允许INTEGER赋给REAL反过来要报错。不要在语法分析阶段顺手做类型检查等语法树完整建好后再走一趟访问器逻辑会更清晰也不容易把语法分析代码搞成一团乱麻。类型检查本身可以设计成一个只读的遍历器不改动语法树只收集类型信息。比如下面这个方法返回一个表达式的类型字符串def type_of(self, node): if node[0] num: return REAL if . in node[1] else INTEGER if node[0] var: return self.symtab.lookup(node[1], node[2])[type] if node[0] binop: lt self.type_of(node[2]) rt self.type_of(node[3]) return REAL if REAL in (lt, rt) else INTEGER逻辑说明叶子节点里数字字面量通过有没有小数点区分REAL和INTEGER变量通过符号表查类型。二元运算的规则就一行只要左右任意一边是REAL结果就是REAL。参数说明node[2]和node[3]对应语法树里二元运算的左子树和右子树与2.3里语法分析生成的(binop, op, node, right)结构保持一致。这个type_of只返回类型不修改树方便在赋值语句里单独检查。3.2 中间表示三地址码还是栈式代码中间表示的选择会影响后面代码生成和报告篇幅。常见的两条路线是栈式代码和三地址码。栈式代码像虚拟机指令直接进栈出栈生成简单但三地址码更接近人们熟悉的汇编每条指令形如result : operand1 op operand2语义非常直白设计报告里展示起来也最直观。我推荐三地址码具体形式是四元式op, arg1, arg2, result。比如a b * c可以翻译成两条*, b, c, t1然后, a, t1, t2。临时变量从t0开始编号。这样写最大的好处是后面无论做解释器还是翻译成C代码都只需要把四元式按顺序处理一遍不需要再重新分析语法树。class IRGenerator: def __init__(self): self.insts [] self.tmp 0 def gen(self, op, arg1, arg2None, resultNone): if result is None: result ft{self.tmp} self.tmp 1 self.insts.append((op, arg1, arg2, result)) return result逻辑说明gen负责分配临时变量并记录指令。result传空时自动生成t0、t1这样的名字表达式递归过程中不用手动管理临时变量编号。参数说明arg1和arg2对单目运算可以不填但建议统一保留四个字段后面打印和解释执行都不用做特殊分支。四元式的打印格式也要在一开始定好报告里展示时所有指令保持一致。3.3 从语法树到三地址码一趟遍历有了IRGenerator遍历语法树生成三地址码的代码会很短。每个节点处理自己的子节点把结果串起来就好。下面是二元运算节点的处理def emit_expr(self, node): if node[0] num: return node[1] if node[0] var: return node[1] if node[0] binop: left self.emit_expr(node[2]) right self.emit_expr(node[3]) return self.ir.gen(node[1], left, right)逻辑说明叶子节点直接返回名字或常量二元运算先递归生成左操作数和右操作数的代码再调用gen把运算本身落成一条三地址码。控制流语句如WHILE需要生成跳转指令这是另一个容易疏忽的点循环体的入口和退出标签要提前留好LABEL和JUMP也需要作为四元式的操作符否则后面解释执行时没法跳转。控制流的生成建议单独放在一个方法里不要和表达式生成混在一起。WHILE的典型模式是先记一个标签然后判断条件条件为假跳到结束标签为真执行循环体循环体末尾再跳回条件标签。给标签编号同样用计数器比如L0、L1避免和临时变量混淆。3.4 最小执行器用四元式跑出最终结果到这里设计报告的核心链路已经完整词法分析、语法树、符号表、类型检查、三地址码。最后一个能证明链路跑通的手段是写一个最小执行器。执行器的思路很简单维护一个变量表按顺序遍历指令、-、*、/直接在值上运算JUMP修改程序计数器LABEL不做任何操作。def run(insts, vars): pc 0 while pc len(insts): op, a1, a2, res insts[pc] if op LABEL: pc 1 elif op JUMP: pc labels[a1] elif op in (, -, *, /): vars[res] calc(op, value(vars, a1), value(vars, a2)) pc 1 return vars逻辑说明value(vars, name)负责取变量值或常量值实现时先看是不是纯数字再看是不是变量表里的名字。calc就是普通的四则运算。参数说明labels字典要在执行前先扫描一遍指令集把每个LABEL对应的编号映射到指令下标这样JUMP才能直接跳。这个执行器虽然简陋但足以把测试程序跑出正确结果报告里也可以拿它来演示中间表示的有效性。4. 避坑指南编译原理课设里最常见的翻车点这一章是血泪经验每一条都来自实际调试不是理论推演。你在设计报告里如果把这些作为“已知问题与解决方案”列出来答辩老师通常会认为你真的跑过而不是在网上拼了一份文档。4.1 悬空ELSE静默错配比报错更可怕现象程序里嵌套IF-THEN-ELSE源代码里ELSE想挂在外层IF上生成的代码却挂到了内层算出来的结果完全不对而且编译过程没有任何报错。原因文法里的if_stmt : IF expr THEN stmt [ ELSE stmt ]是典型的二义性文法。递归下降如果不做特殊约定ELSE会优先匹配最近的IF。解决在解析IF语句时遇到IF expr THEN后面的stmt可以直接递归解析但ELSE分支必须在递归返回后立即处理。更可靠的办法是让内部stmt的解析禁止在遇到ELSE时结束语法分析器在判定一个stmt结束时先看一眼当前token是不是ELSE如果是就留给外层。设计报告里把这一条写进“文法设计说明”比贴一堆状态机图更能体现你理解了问题。4.2 变量先使用后声明符号表顺序的坑现象程序里先用变量再声明编译器第一遍扫描没有报错等到解释执行时才报undefined。原因符号表只在一个方向上做检查忘记了Pascal声明区的特殊性。Pascal的变量声明集中在程序头必须在执行任何语句前全部处理完而不是边处理语句边声明。解决语法分析阶段先把VAR部分完整解析把所有声明填进符号表然后再进入BEGIN-END块解析语句。我一般会在block的解析函数里分两步先parse_var_part再parse_stmt_part两步之间不做任何语句分析。这个顺序在报告里可以用一个小流程图标出来简单但有效。4.3 实数比较导致死循环WHILE条件永远成立现象用REAL类型做WHILE循环的控制变量例如x : x 0.1循环条件x 1.0结果程序不退出。原因浮点数二进制表示不精确0.1累加十次后不是精确的1.0可能永远小于1.0。这不是编译器生成代码的问题而是程序本身的问题但用户会认为你的编译器坏了。解决在设计报告里明确说明本子集对REAL的运算采用双精度浮点并建议控制循环次数或使用可容忍误差。更进一步的方案是引入一个简单的常量折叠如果能静态判断循环条件恒真或恒假就给出警告。这个特性不加也完全没问题但是报告里写一句“已知局限”能避免很多不必要的质疑。4.4 词法分析大小写归一化保留字识别失败现象程序里写Begin词法分析把它当成了标识符语法分析报“期望BEGIN实际得到标识符”。原因检查保留字时直接用原始文本去查字典而Pascal不区分大小写。解决扫描器读取标识符后先做upper()再查表同时把所有保留字表写成大写。这里有个附加坑Pascal的标识符本身也不区分大小写所以符号表里做lookup时也要统一大小写否则X和x会被当成两个不同变量重复声明检测就形同虚设。4.5 分号规则最后一条语句后面不能有多余分号现象BEGIN a : 1; END报错用户很困惑。原因Pascal的BEGIN-END块里分号是语句之间的分隔符不是语句结束符。文法里写的是stmt { ; stmt }最后一个stmt后面不允许有分号。解决解析复合语句时先解析第一个stmt然后循环判断;后面是否还有内容如果有就继续解析。更宽容的做法是把分号改成可选的终结符这偏离了标准Pascal但能让用户少骂你。两种方案都可以但要在报告里写明你是哪一种不要做成了“能跑但说不清规则”的实现。5. 收尾技巧生成一个能看的报告并快速验证设计报告本身不是写给老师看的材料而是你设计过程的复盘。写报告有个很实用的顺序先写测试用例再写编译器的模块最后根据测试结果补报告。这样做的好处是你报告里的每个功能都有对应的测试证据不会出现“写了但不工作”的功能。5.1 测试驱动设计先写测试用例再写编译器把要支持的Pascal程序全部列出来从最简单的PROGRAM p; BEGIN END.开始到包含嵌套IF和WHILE的程序为止。每个测试文件命名带上编号和意图例如test06_while_loop.pas。编译器每完成一个阶段就跑一遍测试集记录哪些通过哪些失败。报告的性能分析表格就可以直接引用这个测试记录数据真实不靠编。5.2 测试用例的构造怎么测才算覆盖覆盖不能只看数量。建议按三组来写合法程序组验证功能非法程序组验证错误检测边界程序组验证词法和语法边界。边界组至少要包含空程序、只有声明的程序、超长标识符、嵌套到第五层的BEGIN-END以及所有一元运算符和括号的组合。非法程序组每条都要写清楚期望报什么错误错误信息里是否包含行号。5.3 报告怎么写才像工程文档报告的框架按照“需求定义、设计、实现、测试、结论”五个部分来组织中间插入文法和核心数据结构测试部分用表格列出通过数和失败数。不推荐写那种只有代码加注释的报告更适合画两个图一个是整体模块图一个是符号表作用域切换图。图不需要精美能表示清楚模块边界就行。我自己的习惯是花一半时间写编译器再花三分之一的时间跑测试和修正剩下的时间才写报告。这个顺序能保证报告里的每一个“设计决策”都是你实际做过的选择而不是从网上参考文档里搬来的套话。编译器的各项设计往往要到测试阶段才会真正暴露缺陷那时候改的设计比凭空想出来的可靠得多。一定要给自己留一个后悔药每次修改代码前把当前版本的基本测试跑一遍。这个习惯帮我避免过很多次“调完一个 bug 带出两个 bug”的窘境。做一个能执行、能报错、有测试依据的小型Pascal子集编译器比一个功能列表华丽但跑不通的程序有价值得多。希望帮到你。本文还有配套的精品资源点击获取