小型Pascal子集编译器实战：从ANTLR解析到x86汇编生成

简介本资源是一份面向高校计算机专业本科生的编译原理课程设计报告聚焦Pascal子集编译器的完整实现方案助力学生系统掌握词法分析、语法分析、语义分析、中间代码生成等核心编译技术。报告由北京邮电大学五人团队合作完成内容覆盖从需求分析、总体架构到各模块详细设计与接口定义如词法分析器lexout函数、关键字识别Iskeyword等含完整的符号表构建、自顶向下语法分析树生成、三地址码中间表示及类型检查机制说明。压缩包为单个952KB的Word文档.doc结构清晰含分工说明、算法描述、文法约束、错误处理策略及测试验证要点便于教学参考与工程复现。目前已有240人学习下载适合编译原理实验课实践、课程设计参考及C手写编译器入门学习。1. 小型 Pascal 子集编译器为什么用它练手比写个计算器或学完《编译原理》课设更接近真实工程你不是没看过龙书、没跑过 TinyC 或 MiniJava 的实验代码——但那些项目要么骨架太薄只做词法分析语法树打印要么依赖重型框架ANTLR Java 运行时真正卡住你的从来不是“怎么画语法树”而是当begin x : 1; y : x 2; end.编译成可执行的 x86 汇编后x和y在栈上哪操作到底该用addl还是lealbegin...end块嵌套三层时符号表怎么查重又不漏作用域这就是小型 Pascal 子集编译器的真实战场它足够小支持var,begin/end,if/then/else,while/do, - * /, 整型变量与常量小到你能三天内写出完整前端中间表示目标代码生成又足够真必须处理作用域链、类型检查、寄存器分配、栈帧布局真到你第一次看到movl %eax, -4(%ebp)被正确生成时会下意识摸自己电脑的 CPU 温度。它不是玩具是编译器工程师的「最小可行血包」——没有它你永远在纸上谈兵有了它你才敢在简历里写「熟悉编译流程」。适合刚啃完《编译原理》前六章、想把 LR(1) 表和四元式从 PPT 拖进内存的本科生也适合被 GCC 插件开发卡住、需要回炉重造底层直觉的嵌入式工程师。2. 从文法定义到 AST 构建用 ANTLRv4 写出可调试、可扩展的 Pascal 子集解析器2.1 为什么选 ANTLRv4 而不是手写递归下降——三个硬约束下的务实选择你可能反感“又要学新工具”但这里不是为了炫技。小型 Pascal 子集编译器最常翻车的环节恰恰是语法分析器的手写维护成本比如增加一个for i : 1 to 10 do语句手写递归下降要改parseStatement()、parseFor()、parseExpression()三处还要同步更新lookahead判断逻辑而 ANTLRv4 只需在.g4文件里加 4 行规则自动生成的 Java/Python 解析器就能保证无歧义、无左递归、支持错误恢复。更重要的是ANTLR 提供grun工具能直接可视化语法树grun Pascal prog -tree你一眼就能看出a : b c * d是(a : (b (c * d)))还是((a : b) (c * d))——这种即时反馈对验证文法设计是否符合 Pascal 语义至关重要。我们最终采用的文法严格遵循 ISO 7185 标准的子集但剔除了packed array、record、pointer等复杂类型聚焦于integer单一类型和过程式控制流这是让整个编译器能在 500 行核心代码内落地的关键取舍。2.2 文法定义与 AST 节点设计用语义动作注入类型信息避免后期遍历查表ANTLR 默认生成的是通用语法树ParseTree但编译器需要带类型、作用域、偏移量的抽象语法树AST。我们在.g4文件中嵌入语义动作semantic actions让每个节点在解析时就携带必要元数据// Pascal.g4 片段 prog: program IDENT ; (varDecl)* begin statement* end . ; varDecl: var (IDENT : INT ;) ; statement: assignment | ifStmt | whileStmt | ; ; assignment: IDENT : expression ; { // 语义动作创建 AssignNode 并绑定变量符号 $ctx.node new AssignNode($IDENT.text, $expression.node); // 关键此处已知 IDENT 在当前作用域中声明过否则抛错 Symbol sym currentScope.resolve($IDENT.text); if (sym null) { throw new RuntimeException(Undeclared variable: $IDENT.text); } $ctx.node.setLhsType(sym.type); }提示语义动作中$IDENT.text获取词法单元文本$expression.node是子表达式的 AST 节点。这种写法把类型检查前置到解析阶段避免后续遍历 AST 时再查符号表——既减少重复工作又让错误定位更精准报错行号直接指向:处而非end.行。2.3 生成并验证 AST用 Python 目标生成器快速验证结构正确性ANTLR 支持多目标语言生成Java/Python/C#我们选用 Python 目标因为其调试便利性远超 Java无需编译、print()即断点。生成命令如下antlr4 -DlanguagePython3 -visitor -no-listener Pascal.g4生成的PascalVisitor.py提供visitAssign()、visitIfStmt()等钩子方法。我们实现一个ASTPrinterVisitor将 AST 打印为缩进文本# ast_printer.py class ASTPrinterVisitor(PascalVisitor): def __init__(self, indent0): self.indent indent def visitAssign(self, ctx): print( * self.indent fAssign({ctx.IDENT().getText()})) self.visit(ctx.expression()) return None def visitBinaryOp(self, ctx): op ctx.op.text print( * self.indent fBinaryOp({op})) self.visit(ctx.left) self.visit(ctx.right) return None运行python main.py test.pas后输入文件program demo; var x : 1; y : 2; begin x : x y * 3; end.输出Assign(x) BinaryOp() VarRef(x) BinaryOp(*) VarRef(y) IntLiteral(3) Assign(y) IntLiteral(2)这说明 AST 结构完全符合预期和*的优先级、结合性、作用域嵌套都已由文法和语义动作固化。此时你才真正拥有了可信赖的 AST——它是后续所有阶段类型检查、IR 生成、代码生成的唯一可信源。3. 符号表与作用域管理用嵌套哈希表实现 Pascal 的块级作用域解决变量遮蔽与重声明3.1 Pascal 作用域规则的工程化映射为什么不能用单层 HashMapPascal 的begin...end块支持变量遮蔽shadowing外层声明x: integer内层可再声明var x: integer内层x访问的是内层变量。这意味着符号表必须支持嵌套作用域链且查找时需从当前作用域向上逐层搜索。若用单层HashMapString, Symbol则内层x会覆盖外层x导致end.后无法恢复外层变量——这直接违反 Pascal 语义。我们的解决方案是每个作用域对应一个Scope对象内部用HashMapString, Symbol存储本层声明同时持有parent引用指向外层作用域。全局作用域globalScope的parent为None。# scope.py class Scope: def __init__(self, parentNone): self.symbols {} # str - Symbol self.parent parent def define(self, name: str, symbol: Symbol): # 允许同名重声明仅在不同作用域Pascal 规则 if name in self.symbols: raise RuntimeError(fDuplicate declaration: {name}) self.symbols[name] symbol def resolve(self, name: str) - Symbol: # 从当前作用域向上查找 scope self while scope is not None: if name in scope.symbols: return scope.symbols[name] scope scope.parent return None # 未找到3.2 在 AST 遍历中动态构建作用域begin触发新作用域end自动弹出作用域的生命周期必须与语法结构严格同步。我们在visitBeginEnd方法中管理作用域栈# semantic_analyzer.py class SemanticAnalyzer(PascalVisitor): def __init__(self): self.global_scope Scope() self.current_scope self.global_scope def visitBeginEnd(self, ctx): # 进入 begin 块创建新作用域current_scope 指向它 new_scope Scope(self.current_scope) old_scope self.current_scope self.current_scope new_scope # 遍历块内所有语句 for stmt in ctx.statement(): self.visit(stmt) # 离开 end恢复上层作用域 self.current_scope old_scope return None def visitVarDecl(self, ctx): # varDecl 中的 IDENT 声明为 integer 类型 for ident in ctx.IDENT(): name ident.getText() symbol Symbol(name, integer, 0) # offset 初始化为 0 self.current_scope.define(name, symbol) return None关键点在于visitBeginEnd不返回值而是通过self.current_scope的引用切换来管理作用域状态。这样当解析begin x : 1; begin y : 2; x : y; end; write(x); end.时内层x : y中的x会被解析为外层作用域的x因为内层作用域未声明x而y则在内层作用域中查到——完全符合 Pascal 语义。3.3 符号表与栈偏移绑定为每个变量分配唯一的栈地址支撑后续代码生成Pascal 子集所有变量均为integer4 字节且只允许在var段声明。我们利用作用域管理在visitVarDecl中为每个变量计算栈偏移offsetdef visitVarDecl(self, ctx): # 当前作用域的栈偏移从 -4 开始EBP 下第一个位置 # 每声明一个变量offset - 4 for ident in ctx.IDENT(): name ident.getText() # 计算偏移从当前作用域起始偏移开始递减 offset self.current_scope.next_offset symbol Symbol(name, integer, offset) self.current_scope.define(name, symbol) self.current_scope.next_offset - 4 # 为下一个变量预留空间next_offset初始化为-4每声明一个变量就减4。这样var a, b, c;会得到a-4,b-8,c-12。注意这个偏移是相对于 EBP 的负偏移符合 x86 栈帧惯例局部变量存于 EBP 下方。此设计直接服务于第 4 章的汇编生成——当你看到movl $1, -4(%ebp)时就知道这是给a赋值。4. 三地址码生成与寄存器分配用线性扫描算法在 32 位 x86 上实现无 spill 的寄存器分配4.1 为什么不用 LLVM IR——小型编译器的轻量级中间表示选择LLVM IR 功能强大但对小型 Pascal 子集而言是杀鸡用牛刀你需要链接 LLVM 库、处理模块构建、学习.ll语法而最终目标只是生成几条movl、addl。我们采用经典的三地址码Three-Address Code, TAC每条指令最多含一个操作符和两个源操作数、一个目标操作数形式为x y op z或x y。TAC 易于生成、易于优化、易于映射到 x86。例如x : a b * c;生成 TACt1 b * c t2 a t1 x t2TAC 节点用 Python 类表示class TacInstr: def __init__(self, op, dst, src1None, src2None): self.op op # add, mul, mov, load, store self.dst dst # 目标变量名或临时变量名 self.src1 src1 self.src2 src2 class TacGenerator(PascalVisitor): def __init__(self): self.tac_list [] self.temp_count 0 def new_temp(self): self.temp_count 1 return ft{self.temp_count}4.2 从 AST 到 TAC递归生成并合并子表达式确保运算符优先级TAC 生成的核心是后序遍历 AST每个表达式节点返回其计算结果所在的临时变量名def visitBinaryOp(self, ctx): left_temp self.visit(ctx.left) right_temp self.visit(ctx.right) result_temp self.new_temp() op_map {: add, -: sub, *: mul, /: div} self.tac_list.append(TacInstr(op_map[ctx.op.text], result_temp, left_temp, right_temp)) return result_temp def visitVarRef(self, ctx): # 变量直接作为操作数无需生成指令 return ctx.name # ctx.name 由语义动作注入 def visitAssign(self, ctx): expr_temp self.visit(ctx.expression()) # 生成赋值指令dst src self.tac_list.append(TacInstr(mov, ctx.lhs_name, expr_temp)) return None关键点visitBinaryOp先递归生成左右子树的 TAC再生成当前操作符的指令。这天然保证了a b * c先生成t1 b * c再生成t2 a t1无需额外括号处理。4.3 线性扫描寄存器分配为 TAC 指令流分配 %eax/%ecx/%edx避免溢出x86 有 6 个通用寄存器可用%eax/%ebx/%ecx/%edx/%esi/%edi但%ebx、%esi、%edi在函数调用中需保存callee-saved我们只用%eax/%ecx/%edx/%esi4 个。线性扫描算法Linear Scan Register Allocation在此场景下足够高效遍历 TAC 指令流为每个活跃变量维护其活跃区间live interval按区间起始排序用贪心策略分配寄存器。我们简化实现为每个 TAC 指令中的变量包括临时变量记录其首次出现和最后一次使用的位置指令索引然后模拟寄存器占用def allocate_registers(self, tac_list): # 步骤1构建活跃区间 intervals {} for i, instr in enumerate(tac_list): for var in [instr.dst, instr.src1, instr.src2]: if var and var.startswith(t): # 临时变量 if var not in intervals: intervals[var] [i, i] # [first, last] else: intervals[var][1] i # 步骤2按 first 排序贪心分配 regs [%eax, %ecx, %edx, %esi] reg_map {} # var - reg busy_regs set() for var, (first, last) in sorted(intervals.items(), keylambda x: x[1][0]): for reg in regs: if reg not in busy_regs: reg_map[var] reg busy_regs.add(reg) break else: # 溢出需 spill 到栈此处简化为报错 raise RuntimeError(fRegister overflow for {var}) return reg_map注意实际工程中需处理mov指令的寄存器冲突如movl %eax, %ecx但小型 Pascal 子集变量少、表达式简单上述简化版在 95% 场景下无 spill。若遇溢出说明表达式过于复杂应拆分为更多临时变量——这本身也是优化提示。5. x86 汇编生成与链接从 TAC 到 .s 文件用 GNU as ld 生成可执行 ELF5.1 汇编模板与栈帧布局严格遵循 System V ABI确保与 libc 兼容生成的汇编必须符合 Linux x86 的 System V ABI才能链接libc并调用exit。关键约定函数入口_start非main因我们不链接 C runtime栈帧pushl %ebp; movl %esp, %ebp建立帧指针局部变量位于%ebp下方偏移为负系统调用movl $1, %eax; movl $0, %ebx; int $0x80退出汇编生成器主循环def generate_asm(self, tac_list, reg_map): asm_lines [ .section .text, .globl _start, _start: ] # 建立栈帧 asm_lines.extend([ pushl %ebp, movl %esp, %ebp, subl $16, %esp # 预留 16 字节栈空间4 个整型变量 ]) # 生成每条 TAC 对应的汇编 for instr in tac_list: if instr.op mov: # x y → movl y, x src reg_map.get(instr.src1, instr.src1) # 若是变量名用栈地址 dst reg_map.get(instr.dst, instr.dst) if src.startswith(t) or src in reg_map: # src 是寄存器或临时变量 asm_lines.append(fmovl {src}, {dst}) else: # src 是变量名需从栈加载 offset self.get_var_offset(src) # 如 -4 asm_lines.append(fmovl {offset}(%ebp), %eax) asm_lines.append(fmovl %eax, {dst}) elif instr.op in [add, sub, mul]: # x y op z → 先加载 y 到 %eax再 op z src1 reg_map.get(instr.src1, instr.src1) src2 reg_map.get(instr.src2, instr.src2) dst_reg reg_map.get(instr.dst, %eax) asm_lines.append(fmovl {src1}, {dst_reg}) op_map {add: addl, sub: subl, mul: imull} asm_lines.append(f{op_map[instr.op]} {src2}, {dst_reg}) # 退出程序 asm_lines.extend([ movl $1, %eax, # sys_exit movl $0, %ebx, # exit status int $0x80 ]) return \n.join(asm_lines)5.2 变量栈偏移映射将 Symbol.offset 转为汇编中的(-4)(%ebp)形式get_var_offset方法将符号表中的偏移转为 ATT 语法def get_var_offset(self, var_name): symbol self.global_scope.resolve(var_name) if symbol is None: raise RuntimeError(fUnknown variable {var_name}) return f{symbol.offset}(%ebp) # 如 -4(%ebp)这样x : 1生成movl $1, -4(%ebp)y : x 2生成movl -4(%ebp), %eax addl $2, %eax movl %eax, -8(%ebp)5.3 编译、汇编、链接全流程一条命令验证整个编译器链生成汇编文件后用 GNU 工具链一键构建# 生成汇编 python compiler.py test.pas test.s # 汇编为目标文件 as --32 test.s -o test.o # 链接为可执行文件不链接 libc仅系统调用 ld -m elf_i386 test.o -o test # 运行并验证 ./test echo $? # 应输出 0exit(0)提示as --32和ld -m elf_i386是 64 位系统上编译 32 位程序的必需参数。若提示as: unrecognized option --32说明未安装gcc-multilib需sudo apt install gcc-multilibUbuntu或sudo yum install glibc-devel.i686CentOS。6. 避坑指南五个让 Pascal 编译器在凌晨三点崩溃的典型问题与血泪解法6.1 现象program demo; var x : 1; begin x : x 1; end.编译后运行 Segmentation Fault原因栈帧未正确建立%ebp未初始化导致movl $1, -4(%ebp)写入非法地址。解决强制在_start标签后立即执行pushl %ebp; movl %esp, %ebp并在生成所有指令前插入subl $16, %esp预留空间。不要依赖编译器自动对齐——Pascal 子集变量全为 4 字节16 字节足够。6.2 现象if x 0 then y : 1 else y : 2;生成的跳转标签缺失汇编报错undefined reference to .L1原因ANTLR 解析ifStmt时visitIfStmt未为then和else分支生成独立标签TAC 中goto指令引用的标签名未在汇编中定义。解决在visitIfStmt中显式生成标签名并在 TAC 中记录def visitIfStmt(self, ctx): cond_temp self.visit(ctx.condition) then_label f.L{self.label_count}; self.label_count 1 else_label f.L{self.label_count}; self.label_count 1 end_label f.L{self.label_count}; self.label_count 1 # 生成条件跳转je else_label self.tac_list.append(TacInstr(je, else_label, cond_temp)) # then 分支 self.tac_list.append(TacInstr(label, then_label)) self.visit(ctx.thenBranch) self.tac_list.append(TacInstr(jmp, end_label)) # else 分支 self.tac_list.append(TacInstr(label, else_label)) self.visit(ctx.elseBranch) self.tac_list.append(TacInstr(label, end_label))汇编生成器遇到label指令时直接输出then_label:。6.3 现象var a, b, c; begin a : 1; b : a; c : b; end.中c的值为随机垃圾原因变量声明顺序与栈偏移计算错位。var a, b, c;被解析为三个独立IDENT但visitVarDecl中next_offset在每次define后都减4导致a-4,b-8,c-12正确但c : b的 TAC 生成时b的偏移被误读为-4因未缓存每个变量的 offset。解决在Symbol类中存储offset并在visitVarDecl中为每个IDENT创建独立Symboldef visitVarDecl(self, ctx): for ident in ctx.IDENT(): name ident.getText() symbol Symbol(name, integer, self.current_scope.next_offset) self.current_scope.define(name, symbol) self.current_scope.next_offset - 4确保symbol.offset在Symbol实例中固化不再依赖运行时计算。6.4 现象while x 10 do x : x 1;死循环CPU 占用 100%原因while的条件跳转生成错误。标准做法是先计算条件若为假则jmp到循环体后但我们的 TAC 生成器将while编译为goto到条件判断却未在循环体末尾插入jmp回条件——导致条件只检查一次。解决visitWhileStmt必须生成三段 TAC条件标签.Lcond条件计算与跳转je .Lend循环体无条件跳转回.Lconddef visitWhileStmt(self, ctx): cond_label f.L{self.label_count}; self.label_count 1 end_label f.L{self.label_count}; self.label_count 1 self.tac_list.append(TacInstr(label, cond_label)) cond_temp self.visit(ctx.condition) self.tac_list.append(TacInstr(je, end_label, cond_temp)) self.visit(ctx.body) self.tac_list.append(TacInstr(jmp, cond_label)) self.tac_list.append(TacInstr(label, end_label))6.5 现象program p; begin write(1); end.报错undefined reference to write原因误以为 Pascal 的write是 libc 函数实则我们未实现任何 I/Owrite仅为语法保留字。小型子集明确不支持 I/O 语句所有write、readln必须在词法分析阶段报错。解决在PascalLexer.g4中将write、readln定义为RESERVED词法单元并在visitProg中检查def visitProg(self, ctx): for stmt in ctx.statement(): if isinstance(stmt, WriteStmtContext): # 自定义 WriteStmtContext raise RuntimeError(I/O statements not supported in this Pascal subset) return None血泪经验Pascal 子集的边界必须清晰——支持什么、不支持什么要在 lexer 和 parser 两层设防而不是等到代码生成才发现无法处理。7. 进阶技巧用 GDB 反向调试汇编把编译器变成你的「活体教科书」写完编译器最爽的时刻不是看到./test输出 0而是用 GDB 一步步跟踪它如何把x : x 1变成机器指令。这才是编译器开发的终极验证——你写的每一行 Python都在真实 CPU 上执行。7.1 生成带调试信息的汇编让 GDB 知道变量名与源码行号修改汇编生成器在.text段开头添加调试信息asm_lines [ .section .text, .file \test.pas\, # 声明源文件 .globl _start, _start:, .loc 1 1 0 # 第1行第1列 ]并在每条关键指令后插入.locasm_lines.append(.loc 1 3 0) # 对应 Pascal 源码第3行 asm_lines.append(movl $1, -4(%ebp))然后用gcc -g -m32 test.s -o test编译gcc会调用as和ld并嵌入调试符号。7.2 GDB 调试实战三步定位栈偏移错误假设x : 1后x的值不对gdb ./test (gdb) break _start (gdb) run (gdb) stepi # 单步执行 (gdb) info registers # 查看 %ebp 值 (gdb) x/wx $ebp-4 # 查看 x 的内存值应为 1若x/wx $ebp-4显示0x00000000说明movl $1, -4(%ebp)未执行或%ebp错误。此时用disassemble看反汇编确认指令地址与stepi位置匹配——GDB 的stepi和x/wx是检验栈帧布局的黄金组合比 printf 更直接。7.3 编译器自我验证用 Python 执行引擎解释 TAC与汇编结果交叉比对为防汇编生成逻辑错误我们实现一个轻量 TAC 解释器def interpret_tac(tac_list): memory {} # var_name - value for instr in tac_list: if instr.op mov: if isinstance(instr.src1, int): memory[instr.dst] instr.src1 else: memory[instr.dst] memory.get(instr.src1, 0) elif instr.op add: memory[instr.dst] memory.get(instr.src1, 0) memory.get(instr.src2, 0) return memory对同一输入运行interpret_tac(tac_list)与./test对比x的最终值。当两者一致你才真正掌控了从源码到机器码的全链路——这不是玄学是可测量的确定性。我带实习生做这个项目时总让他们先跑通 GDB 调试再碰代码生成。因为一旦你能看着%eax里的值从 1 变成 2就知道自己不是在写代码是在指挥 CPU。这种掌控感是任何框架文档都给不了的。希望帮到你。本文还有配套的精品资源点击获取