简介这份资源是面向计算机专业学生与编译原理学习者的Pascal文法编译器课程设计项目围绕词法分析、语法分析、语义检查与代码生成等核心环节展开适合正在完成编译原理实验或课程设计的人群参考。压缩包共140个文件约8.18MB以cpp与h源码、txt与md说明文档、cmake与make构建脚本为主另含少量exe、o、bin等编译产物及pptx、xls等辅助材料覆盖从源码到构建配置的完整工程结构。目前已有288人学习下载。项目内容涉及Pascal的类型系统、函数与过程、if与while控制结构、嵌套定义等特性并包含词法规则设计、上下文无关文法构建、解析算法实现、类型检查与目标代码生成等步骤可帮助读者理解编译器各阶段的衔接方式并对照自身课程设计查漏补缺。1. 从一段 Pascal 源码到可执行文件编译器到底在编译什么很多人第一次接触「基于 Pascal 文法的编译器」脑子里浮现的是把.pas文件丢进去、吐出一个.exe的黑匣子。真动手写一遍才会发现编译器不是「翻译器」而是一条流水线词法分析把字符流切成 token语法分析按文法规则搭出语法树语义分析往符号表里填类型和作用域最后才轮到代码生成。Pascal 之所以常被选作教学与自研编译器的宿主语言是因为它的文法足够规整——program头、var声明段、begin...end复合语句、procedure/function嵌套定义几乎每一块都能用 LL(1) 或递归下降干净地吃掉不像 C 那样被声明与表达式的歧义反复折磨。这篇笔记面向三类人想从零手写一个能跑通四则运算和变量声明的 Pascal 子集编译器的学习者手里有老 Pascal 代码、想自己加语法扩展或做静态检查的维护者以及需要把「文法驱动」这套思路迁移到配置语言、DSL 解析上的工程师。核心问题只有一个给定一份 Pascal 文法怎么把它变成能实际解析、能报错、能生成中间代码的程序而不是停在纸面推导。下面按「文法怎么读 → 解析器怎么写 → 语义怎么查 → 代码怎么出 → 坑在哪」的顺序推下去每一步都给可抄的代码和参数。2. 把 Pascal 文法翻译成可执行的递归下降解析器2.1 先分清 EBNF 里的终结符、非终结符和递归形态写解析器之前必须把文法读成「函数签名」。Pascal 子集的 EBNF 常见写法里program、block、statement、expression是非终结符每个对应一个解析函数begin、end、:、;、标识符、数字是终结符对应 token 匹配。关键判断是递归形态statement里出现compound_statementcompound_statement又回到statement这是直接左递归之外的嵌套递归递归下降能直接处理但如果文法写成expression - expression term那就是左递归递归下降会栈溢出必须先改写成expression - term { (|-) term }的循环形式。Pascal 的表达式优先级是另一处必须提前定死的参数。常见分层是expression加减、关系运算→term乘除、div、mod→factor数字、变量、括号、函数调用。层数定错2 3 * 4就会算成 20 而不是 14。我一般会在文法文件顶部用注释把优先级表钉死避免后面改代码时忘了哪层管哪层。2.2 用 Python 写一个能跑通的最小词法分析器词法分析器负责把源码字符串切成(type, value)的 token 流。Pascal 大小写不敏感关键字要单独识别注释用{ }或(* *)包裹。下面是最小可用版本import re # token 类型关键字、标识符、数字、运算符、界符、EOF KEYWORDS {program, var, begin, end, integer, procedure, function, if, then, else, while, do, div, mod} TOKEN_SPEC [ (NUMBER, r\d), (ID, r[A-Za-z_]\w*), (ASSIGN, r:), (OP, r[\-*/]), (PUNC, r[;,().:]), (SKIP, r[ \t\r\n]), (COMMENT, r\{[^}]*\}|\(\*.*?\*\)), (MISMATCH, r.), ] def tokenize(code): tok_re re.compile(|.join(f(?P{n}{p}) for n, p in TOKEN_SPEC)) tokens [] for mo in tok_re.finditer(code): kind mo.lastgroup value mo.group() if kind in (SKIP, COMMENT): continue if kind ID and value.lower() in KEYWORDS: kind KEYWORD value value.lower() # 关键字统一小写后续比较省事 elif kind MISMATCH: raise SyntaxError(f非法字符 {value!r}) tokens.append((kind, value)) tokens.append((EOF, )) return tokens逻辑说明TOKEN_SPEC的顺序决定匹配优先级ASSIGN必须排在OP前面否则:会被拆成:和。COMMENT放在SKIP之后、MISMATCH之前保证注释被吞掉而不是报错。参数上ID的正则[A-Za-z_]\w*决定了标识符不能以数字开头这是 Pascal 标准如果你要支持下划线开头的扩展标识符把_留在字符类里即可。关键字统一转小写是血泪经验——Pascal 里Begin和begin等价不统一后面语法分析要写两套比较。2.3 递归下降解析器每个非终结符一个函数有了 token 流解析器就是一个带pos指针的类每个非终结符对应一个方法。核心是match和expect两个原语class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def match(self, kind, valueNone): t self.peek() if t[0] kind and (value is None or t[1] value): self.pos 1 return t return None def expect(self, kind, valueNone): t self.match(kind, value) if t is None: cur self.peek() raise SyntaxError(f期望 {kind} {value}实际 {cur}) return t def parse_program(self): self.expect(KEYWORD, program) name self.expect(ID)[1] self.expect(PUNC, ;) block self.parse_block() self.expect(PUNC, .) return (program, name, block) def parse_block(self): decls [] while self.match(KEYWORD, var): decls.append(self.parse_var_decl()) body self.parse_compound() return (block, decls, body) def parse_var_decl(self): names [self.expect(ID)[1]] while self.match(PUNC, ,): names.append(self.expect(ID)[1]) self.expect(PUNC, :) typ self.expect(KEYWORD)[1] self.expect(PUNC, ;) return (var, names, typ) def parse_compound(self): self.expect(KEYWORD, begin) stmts [self.parse_statement()] while self.match(PUNC, ;): if self.peek()[1] end: break stmts.append(self.parse_statement()) self.expect(KEYWORD, end) return (compound, stmts) def parse_statement(self): if self.peek()[1] begin: return self.parse_compound() if self.peek()[0] ID: name self.expect(ID)[1] self.expect(ASSIGN) expr self.parse_expression() return (assign, name, expr) raise SyntaxError(f无法识别的语句 {self.peek()}) def parse_expression(self): node self.parse_term() while self.peek()[1] in (, -): op self.tokens[self.pos][1] self.pos 1 node (binop, op, node, self.parse_term()) return node def parse_term(self): node self.parse_factor() while self.peek()[1] in (*, /, div, mod): op self.tokens[self.pos][1] self.pos 1 node (binop, op, node, self.parse_factor()) return node def parse_factor(self): t self.peek() if t[0] NUMBER: self.pos 1 return (num, int(t[1])) if t[0] ID: self.pos 1 return (var, t[1]) if t[1] (: self.pos 1 node self.parse_expression() self.expect(PUNC, )) return node raise SyntaxError(f非法因子 {t})逻辑说明parse_expression用while循环处理左结合的加减parse_term同理处理乘除这样2 - 3 - 4会解析成((2-3)-4)而不是(2-(3-4))符合 Pascal 左结合语义。parse_compound里while self.match(PUNC, ;)之后判断end是为了容忍begin a : 1; end这种末尾分号Pascal 标准允许空语句。参数上parse_var_decl里typ self.expect(KEYWORD)[1]只接受关键字类型如果你要支持array、record这里要扩展成parse_type函数。2.4 用 AST 打印验证解析结果解析完不要急着生成代码先把 AST 打出来看结构对不对。加一个缩进打印函数def dump(node, indent0): pad * indent if isinstance(node, tuple): print(pad node[0]) for child in node[1:]: dump(child, indent 1) else: print(pad repr(node)) # 测试 src program demo; var x, y: integer; begin x : 2 3 * 4; y : x - 1 end. dump(Parser(tokenize(src)).parse_program())跑出来应该看到program → demo → block → var → compound → assign → binop() → num(2) → binop(*) → num(3) → num(4)这样的树。如果3 * 4没有先结合成子树说明优先级分层写反了。这一步是后悔药等代码生成写完再回头查优先级成本翻十倍。3. 语义分析符号表、类型检查和那些必须提前拦住的错误3.1 符号表用栈式作用域别用单层字典Pascal 允许procedure和function嵌套内层可以访问外层变量外层不能访问内层。单层字典会在嵌套过程里把同名变量覆盖掉正确做法是作用域栈进入block压一层退出弹一层查找时从栈顶往下扫。class SymbolTable: def __init__(self): self.scopes [{}] # 全局作用域 def enter_scope(self): self.scopes.append({}) def exit_scope(self): self.scopes.pop() def declare(self, name, typ): if name in self.scopes[-1]: raise NameError(f重复声明 {name}) self.scopes[-1][name] typ def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] raise NameError(f未声明变量 {name})逻辑说明declare只查当前层允许内层var x遮蔽外层x这是 Pascal 的合法行为lookup从内往外找保证内层优先。参数上scopes初始有一层全局作用域enter_scope在解析procedure头之后、var声明之前调用exit_scope在end之后调用。常见翻车是忘记在exit_scope前把过程名本身注册到外层导致递归调用报「未声明」。3.2 类型检查整数运算、赋值兼容和除零预警Pascal 子集里类型不多但检查点不少。赋值语句x : expr要求expr的类型能赋给xdiv、mod只接受整数关系运算返回布尔但这里先只支持整数比较。下面是一个遍历 AST 做类型标注的骨架def check(node, symtab): kind node[0] if kind num: return integer if kind var: return symtab.lookup(node[1]) if kind binop: op node[1] lt check(node[2], symtab) rt check(node[3], symtab) if lt ! integer or rt ! integer: raise TypeError(f{op} 需要整数操作数) if op in (div, mod) and node[3][0] num and node[3][1] 0: raise ZeroDivisionError(编译期发现除零) return integer if kind assign: var_type symtab.lookup(node[1]) expr_type check(node[2], symtab) if var_type ! expr_type: raise TypeError(f不能把 {expr_type} 赋给 {var_type}) return None if kind compound: for stmt in node[1]: check(stmt, symtab) return None if kind block: symtab.enter_scope() for decl in node[1]: for name in decl[1]: symtab.declare(name, decl[2]) check(node[2], symtab) symtab.exit_scope() return None raise TypeError(f未知节点 {kind})逻辑说明check返回类型字符串assign节点比较左右类型binop要求两边都是integer。除零检查放在编译期是加分项——div的右操作数是字面量0时直接报错不用等运行时。参数上symtab在block节点进入时enter_scope这样每个过程体有独立作用域。注意check对program节点没有处理实际调用时要从block子节点开始或者给program加一个分支。3.3 错误恢复别让第一个错误就终止整个编译真实编译器不会遇到第一个错误就退出而是尽量跳过当前语句、继续检查后面的。递归下降里最简单的恢复策略是在parse_statement外层包一层try/except出错时跳到下一个;或enddef parse_statement_safe(self): try: return self.parse_statement() except SyntaxError as e: print(f[语法错误] {e}) while self.peek()[0] ! EOF and self.peek()[1] not in (;, end): self.pos 1 self.match(PUNC, ;) return (error, str(e))逻辑说明出错后吞 token 直到分号或end然后返回一个error节点占位后续语义分析跳过它。参数上end不吞掉留给上层parse_compound正常闭合。这个策略对「少写一个分号」这类错误特别有效能一次报出多行问题而不是改一行编译一次。4. 从 AST 到三地址码代码生成的最小闭环4.1 三地址码的指令集设计代码生成的目标不是直接出机器码而是先出中间表示IR三地址码是最容易验证的一种。指令集只需要几条LOAD把变量或常量取到临时变量STORE写回变量ADD/SUB/MUL/DIV/MOD做二元运算HALT结束。每条指令形如t1 a b操作数最多一个运算符。class CodeGen: def __init__(self): self.instructions [] self.temp_count 0 def new_temp(self): self.temp_count 1 return ft{self.temp_count} def emit(self, instr): self.instructions.append(instr) def gen(self, node): kind node[0] if kind num: t self.new_temp() self.emit(f{t} {node[1]}) return t if kind var: t self.new_temp() self.emit(f{t} {node[1]}) return t if kind binop: left self.gen(node[2]) right self.gen(node[3]) t self.new_temp() op_map {: ADD, -: SUB, *: MUL, /: DIV, div: DIV, mod: MOD} self.emit(f{t} {left} {op_map[node[1]]} {right}) return t if kind assign: val self.gen(node[2]) self.emit(f{node[1]} {val}) return None if kind compound: for stmt in node[1]: self.gen(stmt) return None raise ValueError(f无法生成 {kind})逻辑说明每个表达式节点返回一个临时变量名父节点用这些名字拼指令。assign节点把右值临时变量写回变量名。参数上temp_count全局递增保证临时变量不重名op_map把 Pascal 的div、mod映射到 IR 的DIV、MOD注意/在 Pascal 里是实数除法这里为了简化也映射到DIV真实实现要区分整数和浮点。4.2 用一段完整程序验证生成结果拿第 2 章的测试源码跑一遍src program demo; var x, y: integer; begin x : 2 3 * 4; y : x - 1 end. ast Parser(tokenize(src)).parse_program() symtab SymbolTable() check(ast[2], symtab) # ast[2] 是 block cg CodeGen() cg.gen(ast[2]) for ins in cg.instructions: print(ins)预期输出类似t1 2 t2 3 t3 4 t4 t2 MUL t3 t5 t1 ADD t4 x t5 t6 x t7 1 t8 t6 SUB t7 y t8看到t4 t2 MUL t3在t5 t1 ADD t4之前说明优先级正确。如果顺序反了回去查parse_expression和parse_term的调用关系。这一步是整条流水线的验收点AST 对、IR 对后面接解释器或目标代码生成都只是体力活。4.3 接一个栈式解释器把 IR 跑起来IR 有了写个几十行的解释器就能看到运行结果def interpret(instructions): env {} for ins in instructions: if not in ins: continue lhs, rhs ins.split(, 1) lhs lhs.strip() rhs rhs.strip() parts rhs.split() if len(parts) 1: val env.get(parts[0], parts[0]) env[lhs] int(val) if str(val).isdigit() else val else: a, op, b parts a env.get(a, a) b env.get(b, b) a, b int(a), int(b) env[lhs] {ADD: ab, SUB: a-b, MUL: a*b, DIV: a//b, MOD: a % b}[op] return env env interpret(cg.instructions) print(x , env.get(x), y , env.get(y))逻辑说明解释器按顺序执行遇到单操作数就查环境或当字面量遇到三操作数就做运算。参数上DIV用//保证整数除法和 Pascal 的div一致env.get(parts[0], parts[0])处理临时变量和字面量混用。跑出来x 14, y 13就说明从文法到执行整条链路通了。5. 避坑与排查Pascal 编译器实现里最容易翻车的 5 个点5.1 现象2 3 * 4算成 20原因parse_expression里把*也当成同级运算符或者parse_term没有在parse_expression之前被调用。递归下降的优先级完全靠函数调用层次体现层次写错就是数学错误。解决确认parse_expression只处理、-parse_term处理*、/、div、modparse_factor处理括号和原子。改完用2 3 * 4和2 * 3 4两个用例交叉验证。5.2 现象嵌套过程里访问外层变量报「未声明」原因符号表用了单层字典或者enter_scope/exit_scope的调用时机不对——常见的是在解析完整个block之后才enter_scope导致声明和查找不在同一层。解决在parse_block进入时立刻enter_scope解析var声明时declare解析语句时lookupend之后exit_scope。用嵌套procedure的用例验证内外层同名变量互不干扰。5.3 现象begin a : 1; end报「期望语句」原因parse_compound在while self.match(PUNC, ;)之后直接调parse_statement没有判断下一个 token 是不是end。Pascal 允许复合语句末尾有多余分号。解决在循环里加if self.peek()[1] end: break或者把空语句;也当成合法statement处理。这个坑在写测试用例时必现早加早省事。5.4 现象:被拆成:和原因词法分析器的TOKEN_SPEC里OP排在ASSIGN前面正则引擎先匹配到:就返回了。解决把ASSIGN的正则:放在OP之前或者把:从OP里拿掉、单独放进PUNC。改完用x : 1和x : 1后者应报错两个用例验证。5.5 现象编译大文件时递归深度超限原因递归下降对深层嵌套表达式比如一长串111...会线性增加调用栈Python 默认递归上限 1000 层几千个加号就崩。解决把parse_expression和parse_term里的递归改成while循环——实际上第 2 章的代码已经是循环形式左结合运算不会加深栈真正会加深的是括号嵌套那种情况要么调sys.setrecursionlimit要么改成显式栈的迭代解析。参数上sys.setrecursionlimit(10000)能顶一阵但生产级解析器还是建议用算符优先或 LR 表驱动。6. 进阶把文法驱动扩展到过程调用与常量折叠6.1 支持procedure声明与调用到第 4 章为止只处理了全局变量和赋值。Pascal 的灵魂在过程。扩展点有三个parse_block里识别procedure关键字解析过程名和形参表符号表里注册过程签名parse_factor里遇到标识符后跟(时生成call节点。代码生成侧call节点要先把实参求值到临时变量再发CALL指令被调过程体单独生成一段带RETURN的指令序列。这里最容易翻车的是参数传递方式——Pascal 默认值传递var参数是引用传递符号表里要记录每个形参的传递模式否则swap(a, b)这种经典用例会静默失败。6.2 常量折叠在语义分析阶段就把2 3 * 4算成 14IR 里出现t1 2; t2 3; t3 4; t4 t2 MUL t3; t5 t1 ADD t4是浪费。在check函数返回类型的同时如果节点是binop且两个子节点都是num直接算出结果替换成num节点。实现上给check加一个返回值(type, folded_node)或者单独写一个fold遍历。参数上只折叠整数运算div、mod的除零检查在折叠时一并做掉。折叠后 IR 变成t1 14; x t1解释器少跑四条指令。6.3 用一张表对比各阶段输入输出方便定位问题阶段输入输出典型错误词法分析源码字符串token 列表非法字符、:被拆语法分析token 列表AST优先级错、缺分号语义分析AST 符号表带类型的 AST未声明、类型不匹配代码生成带类型 AST三地址码临时变量重名、操作数顺序解释执行三地址码变量环境除零、变量未初始化这张表我一般贴在显示器边上哪一步输出不对就往前一步查比盲目加 print 快得多。6.4 一个具体技巧用文法文件自动生成解析函数骨架手写递归下降最烦的是每个非终结符都要敲一遍match/expect。如果文法用 EBNF 写在单独文件里可以写个几十行的脚本按::左边生成函数名、右边生成match调用序列。比如statement :: ID : expression | begin ...生成parse_statement里先peek判断分支。这个脚本不用多完善能省掉 70% 的样板代码就值。我自己的习惯是文法文件改一行、脚本跑一次、函数骨架更新手写的部分只留语义动作。这样文法调整时不会漏改解析函数也方便把同一份文法喂给不同的后端。写到这里整条链路从.pas源码到解释执行已经能跑通。最后说个我自己的教训早期我总想一步到位支持完整 Pascal 标准结果record、array、指针全堆上去解析器写到一半就失控。后来改成每次只加一个文法产生式加完立刻补测试用例跑通再动下一个反而两周就把子集做稳了。编译器这东西文法驱动是骨架测试用例是血肉缺一个都站不住。希望帮到你。本文还有配套的精品资源点击获取