基于Pascal文法的编译器实现：从词法分析到三地址码生成

简介：这份资源是面向计算机专业学生与编译原理学习者的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_statement，compound_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, value=None): 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, value=None): 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, indent=0): 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的类型能赋给x；div、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，出错时跳到下一个;或end：

def 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 f't{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': a+b, '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、mod，parse_factor处理括号和原子。改完用2 + 3 * 4和2 * 3 + 4两个用例交叉验证。

5.2 现象：嵌套过程里访问外层变量报「未声明」

原因：符号表用了单层字典，或者enter_scope/exit_scope的调用时机不对——常见的是在解析完整个block之后才enter_scope，导致声明和查找不在同一层。解决：在parse_block进入时立刻enter_scope，解析var声明时declare，解析语句时lookup，end之后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 现象：编译大文件时递归深度超限

原因：递归下降对深层嵌套表达式（比如一长串1+1+1+...）会线性增加调用栈，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算成 14

IR 里出现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 用一张表对比各阶段输入输出，方便定位问题

这张表我一般贴在显示器边上，哪一步输出不对就往前一步查，比盲目加 print 快得多。

6.4 一个具体技巧：用文法文件自动生成解析函数骨架

手写递归下降最烦的是每个非终结符都要敲一遍match/expect。如果文法用 EBNF 写在单独文件里，可以写个几十行的脚本，按::=左边生成函数名、右边生成match调用序列。比如statement ::= ID ':=' expression | 'begin' ...生成parse_statement里先peek判断分支。这个脚本不用多完善，能省掉 70% 的样板代码就值。我自己的习惯是文法文件改一行、脚本跑一次、函数骨架更新，手写的部分只留语义动作。这样文法调整时不会漏改解析函数，也方便把同一份文法喂给不同的后端。

写到这里，整条链路从.pas源码到解释执行已经能跑通。最后说个我自己的教训：早期我总想一步到位支持完整 Pascal 标准，结果record、array、指针全堆上去，解析器写到一半就失控。后来改成每次只加一个文法产生式，加完立刻补测试用例，跑通再动下一个，反而两周就把子集做稳了。编译器这东西，文法驱动是骨架，测试用例是血肉，缺一个都站不住。希望帮到你。

本文还有配套的精品资源，点击获取