重庆大学PL0编译器五阶段实战工程

简介本资源是重庆大学编译原理课程配套的完整实验实践平台面向计算机专业本科生及编译技术自学者聚焦PL0语言编译器从词法分析、语法分析、语义分析到中间代码生成、目标代码优化的全流程实现有效解决理论抽象、动手困难、实验报告无参考等学习痛点。压缩包共44个文件含8个txt含说明文档与实验指导、7个xmlIDE配置与项目元数据、3个cpp/h源码文件、2个exe可执行示例、1个pptm教学演示、1个docx实验报告模板及1个md学习笔记辅以CMakeLists.txt、.gitignore等工程支撑文件整体1.83MB结构清晰、开箱即用。已有63人下载学习读者可直接复现重庆大学标准实验流程获取规范的报告撰写范式、分阶段调试思路、符号表与状态机实现样例并通过预置PL0测试用例验证各模块功能切实提升编译器开发与系统级编程能力。1. 这不是又一个“Hello World”编译器重庆大学编译原理实验仓库实打实跑通 PL0 全流程的词法→语法→语义→中间代码→目标代码五阶段闭环你手头那份《编译原理》教材第三版翻到第 287 页正对着“PL0 语言文法定义”发呆IDE 里刚敲完yacc -d parser.y却报错conflicts: 1 shift/reduce调试器里看到TAC[0] add t1, a, b却不知道这行三地址码到底在哪生成、怎么映射到寄存器——别硬扛了。这个来自重庆大学计算机学院真实课程实验的 ZIP 包不是教学 PPT 的 PDF 打包也不是只跑通词法分析就收工的半成品而是完整覆盖 PL0 编译全流程的可执行工程集合从scanner.c逐字符识别关键字/标识符/数字到parser.y基于 LALR(1) 构建语法树再到semant.c实现符号表查重与类型检查接着用irgen.c生成带基本块划分的三地址码TAC最后通过codegen.c输出类 x86 汇编指令含寄存器分配与简单优化。它被数百名重大学生在 Linux 环境下反复 make clean make 验证过配套实验报告模板直接填空就能交学习笔记里甚至标注了“老师常问的三个语义分析陷阱”。如果你正在啃龙书、做 SDUT PTA 编译原理题、或被山科大/燕山大学/海南大学的实验卡在中间代码生成环节——这不是参考答案是能让你亲手把begin a : 1; b : a 2; write(b) end.编译成汇编并单步调试的生产级实验基线。2. 从源码结构到构建链路解压后第一眼该看什么五个核心模块如何协同工作2.1 目录树即编译流水线每个文件夹对应一个编译阶段解压后你会看到清晰的五层目录结构这并非随意组织而是严格遵循编译器前端→中端→后端的经典分层├── scanner/ # 词法分析器C 实现输出 token 流 ├── parser/ # 语法分析器Bison 生成构建 AST ├── semantic/ # 语义分析器遍历 AST填充符号表检查作用域与类型 ├── irgen/ # 中间代码生成器将 AST 转为带基本块的三地址码TAC ├── codegen/ # 目标代码生成器TAC → 类 x86 汇编含寄存器分配与窥孔优化 ├── test/ # PL0 测试用例集.pl0 文件 预期输出.out ├── doc/ # 实验报告模板Word、PL0 语言规范、常见错误速查表 └── Makefile # 统一构建脚本支持 stage-by-stage 编译验证提示不要一上来就make all。先cd scanner make确认词法分析器能正确输出token_type: ID, value: a这类格式再进parser目录make test看是否能生成.dot语法树图需 Graphviz。每阶段独立可验证才是可控调试的前提。2.2 词法分析器手写 DFA 还是 flex这里选的是可读性优先的手工实现scanner/scanner.c是纯 C 实现的确定有限自动机DFA没有依赖 flex。它用state变量驱动状态迁移关键逻辑在scan_token()函数中// scanner/scanner.c 关键片段 int scan_token() { int state START; while (1) { char c get_char(); switch(state) { case START: if (is_letter(c)) { state IN_ID; buf_add(c); } else if (is_digit(c)) { state IN_NUM; buf_add(c); } else if (c :) { state COLON; } // ... 其他状态转移 break; case IN_ID: if (is_letter(c) || is_digit(c)) buf_add(c); else { unget_char(c); return lookup_keyword_or_id(); } break; // 更多状态... } } }buf_add(c)将字符累积到缓冲区lookup_keyword_or_id()查关键词哈希表keywords.h定义if,then,begin等 15 个保留字unget_char(c)是关键当读到非标识符字符如a:中的:时必须把:“吐回去”否则语法分析器会丢失这个 token参数说明MAX_TOKEN_LEN在scanner.h中定义为 32超长标识符会被截断——这是 PL0 规范要求不是 bug2.3 语法分析器Bison 生成的 LALR(1) 分析器但文法已预处理消歧义parser/parser.y是核心文法定义文件采用经典的 PL0 文法扩展自 Wirth 原始定义但做了关键调整消除左递归expression规则改写为右递归形式避免 Bison 报 shift/reduce 冲突显式终结符绑定所有token类型如ID,NUMBER,PLUS均在%token声明并与scanner.h中的枚举值严格一致AST 节点构造每个产生式右侧调用mk_node()创建抽象语法树节点例如assignment_stmt : ID ASSIGN expression { $$ mk_assign($1, $3); }$1是ID的 lexeme如a$3是expression子树指针$$是新生成的赋值节点构建时执行make会自动调用bison -d parser.y生成parser.tab.c和parser.tab.h再与scanner.o链接。注意若修改parser.y后make失败先rm parser.tab.*再重试Bison 旧缓存常导致奇怪错误。2.4 语义分析器符号表不是哈希表而是带作用域链的栈式结构semantic/symbol_table.c实现了一个嵌套作用域符号表这是 PL0 支持过程嵌套的关键// semantic/symbol_table.h typedef struct symtab_entry { char *name; int type; // TYPE_INT, TYPE_PROC int level; // 作用域深度0全局1主过程2嵌套过程 int offset; // 相对于当前帧基址的偏移用于生成 load/store 指令 } symtab_entry; typedef struct scope { symtab_entry **entries; int capacity; int size; struct scope *parent; // 指向上级作用域 } scope;enter_scope()创建新作用域leave_scope()弹出当前作用域并释放内存insert_symbol(a, TYPE_INT)时先在当前作用域查重再插入lookup_symbol(a)则从当前作用域向上逐级查找血泪经验PL0 规定过程内声明的变量不能与外层同名。semantic/check.c中check_redeclaration()函数必须在enter_scope()后立即调用否则嵌套过程内重复声明i不会报错2.5 中间代码生成器TAC 不是字符串拼接而是结构化 IR 节点链irgen/irgen.c生成的不是文本汇编而是内存中的三地址码节点链表// irgen/ir.h typedef enum { IR_ASSIGN, IR_ADD, IR_SUB, IR_MUL, IR_DIV, IR_LABEL, IR_GOTO, IR_IF_TRUE, IR_CALL, IR_RETURN } ir_opcode; typedef struct ir_node { ir_opcode op; struct ir_node *arg1, *arg2, *result; // 指向其他 IR 节点或常量 char *label; // 仅 LABEL/GOTO/IF_TRUE 使用 struct ir_node *next; // 链表指针 } ir_node;gen_assign(node)返回IR_ASSIGN节点arg1指向变量节点result指向表达式计算结果节点gen_basic_block()自动划分基本块以LABEL或GOTO为边界每个块内无跳转为什么不用字符串因为后续codegen需要遍历 IR 链表做活跃变量分析Liveness Analysis来分配寄存器——字符串 TAC 无法支撑此优化3. 构建与运行从零开始跑通一个 PL0 程序的完整命令流3.1 环境准备Ubuntu 20.04 的最小依赖清单无 Docker该仓库设计为轻量级本地构建无需虚拟环境或容器# 必装工具Ubuntu/Debian sudo apt update sudo apt install -y \ build-essential \ bison \ flex \ graphviz \ libc6-dev # 验证版本关键Bison 必须 ≥ 3.0.4否则 LALR(1) 生成失败 bison --version # 应输出 3.7.6 或更高 gcc --version # 应输出 9.4.0 或更高注意CentOS/RHEL 用户请用yum install bison flex gcc make graphviz但需确认 Bison 版本——RHEL 8 自带 Bison 3.0.4 可用RHEL 7 默认 2.7 不兼容需手动编译升级。3.2 分阶段构建为什么make all容易失败你应该这样走直接make all会一次性编译全部模块但任一阶段失败都会中断且难以定位。推荐分步验证# 步骤1进入 scanner 目录验证词法分析器 cd scanner make clean make echo begin a : 1; write(a) end. | ./scanner # 期望输出BEGIN ID ASSIGN NUMBER SEMI WRITE LPAREN ID RPAREN SEMI END # 步骤2进入 parser 目录验证语法树生成 cd ../parser make clean make echo begin a : 1; write(a) end. | ../scanner/scanner | ./parser -v # -v 参数输出 AST 的 dot 格式可用 dot -Tpng ast.dot -o ast.png 查看图形 # 步骤3进入 semantic 目录验证语义检查 cd ../semantic make clean make echo begin a : 1; b : a 2; write(b) end. | ../scanner/scanner | ../parser/parser | ./semantic # 期望输出Semantic OK若出现 Undeclared identifier c 则说明符号表生效 # 步骤4进入 irgen 目录查看 TAC 输出 cd ../irgen make clean make echo begin a : 1; b : a 2; write(b) end. | ../scanner/scanner | ../parser/parser | ../semantic/semantic | ./irgen # 期望输出类似t1 : 1; t2 : a; t3 : t2 2; b : t3; write(b)3.3 全流程编译一个 PL0 文件test/fib.pl0的实操演示仓库test/目录下有经典斐波那契递归程序fib.pl0program fib; var n, result; procedure fibo(x); var a, b; begin if x 1 then result : x else begin a : fibo(x-1); b : fibo(x-2); result : a b end end; begin n : 5; result : fibo(n); write(result) end.运行全流程命令# 1. 进入根目录确保所有子模块已编译 cd /path/to/unzipped/repo # 2. 执行五阶段管道注意路径需根据实际调整 cat test/fib.pl0 \ | scanner/scanner \ | parser/parser \ | semantic/semantic \ | irgen/irgen \ | codegen/codegen fib.s # 3. 用 GCC 汇编并链接codegen 输出的是 ATT 语法汇编 gcc -m32 fib.s -o fib.out ./fib.out # 期望输出5fib(5) 5codegen输出的fib.s是 32 位 x86 汇编故gcc -m32必须指定若系统无 32 位库sudo apt install gcc-multilibfib.s中可见movl %eax, -4(%ebp)这类帧指针访问证明寄存器分配与栈帧布局已生效3.4 调试技巧当write(result)输出 0 而不是 5如何快速定位不要盲目重写代码。按编译阶段倒推检查词法cat test/fib.pl0 | scanner/scanner | head -20确认program,var,procedure等关键词被正确识别为PROGRAM,VAR,PROCEDURE检查语法cat test/fib.pl0 | scanner/scanner | parser/parser -v | dot -Tpng -o fib_ast.png打开 PNG 看 AST 是否有CALL节点和IF节点——缺失说明文法未覆盖递归调用检查语义cat test/fib.pl0 | scanner/scanner | parser/parser | semantic/semantic若输出Error: Undeclared procedure fibo说明procedure声明未被提前注册到符号表检查 TACcat test/fib.pl0 | ... | irgen/irgen | grep call\|return应看到call fibo和return指令若无问题在irgen/gen_call()逻辑4. 避坑指南重大学生踩过的七个真实坑附现象、原因与一行修复4.1 现象bison -d parser.y报错conflicts: 1 shift/reduce但make仍成功原因Bison 默认容忍冲突并生成默认动作但 PL0 文法中if E then S和if E then S else S的else悬挂问题未显式解决解决在parser.y开头添加%expect 1接受 1 个冲突并在if_stmt规则末尾加%prec ELSE%left ELSE %token ELSE // ... if_stmt : IF expression THEN statement %prec ELSE | IF expression THEN statement ELSE statement4.2 现象semantic阶段报Error: Type mismatch in assignment但a : 1明明是整型原因scanner对数字字面量返回NUMBERtoken但semantic/check.c中get_type_of_token()未将NUMBER映射为TYPE_INT而是返回TYPE_UNKNOWN解决在semantic/check.c的get_type_of_token()函数中增加case NUMBER: return TYPE_INT;4.3 现象irgen输出的 TAC 中t1 : a b但codegen生成的汇编里a和b地址偏移全为 0原因semantic阶段未给变量分配栈偏移offset字段未设置codegen读取symtab_entry-offset得到 0解决在semantic/symbol_table.c的insert_symbol()中为变量分配偏移entry-offset current_frame_offset; current_frame_offset 4; // 每个 int 占 4 字节4.4 现象codegen生成的汇编fib.s用gcc -m32编译时报undefined reference to write原因PL0 的write()是运行时库函数但codegen未链接libpl0.a或提供 stub 实现解决在codegen/codegen.c末尾添加write的 C stub或链接时加-lpl0// 在 codegen.c 中添加 void write(int x) { printf(%d\n, x); }并在Makefile中codegen目标的gcc命令后加-lc -lm4.5 现象test/fib.pl0运行结果为 0但单步调试发现fibo(5)返回值未传回原因PL0 规定函数返回值存于全局变量result但codegen未在CALL后生成movl result, %eax解决在codegen/gen_call()生成call fibo后插入fprintf(out, \tmovl result, %%eax\n);5. 进阶实战用这个仓库反向破解《编译原理》课后习题精准定位龙书第 5 章考点5.1 从 PL0 文法出发手撕龙书习题 5.3 的 SDD语法制导定义龙书第 5 章习题 5.3 要求为E → E1 T构建 SDD计算E.val。而本仓库parser.y中对应规则是expression : expression PLUS term { $$ mk_binary_op(IR_ADD, $1, $3); }对照 SDDE.val即$$新节点E1.val是$1左子表达式树T.val是$3右项树关键差异SDD 是属性计算而本实现是 AST 构造——mk_binary_op()创建节点不计算值值在irgen阶段才生成t1 : t2 t3动手验证修改parser.y在expression规则中添加printf(E.val computed from %d %d\n, $1-val, $3-val);需先在 AST 节点加val字段即可观察 SDD 属性传递过程5.2 用irgen的 TAC 链表可视化龙书第 9 章的活跃变量分析Liveness Analysisirgen/ir.h中的ir_node链表天然支持数据流分析。以test/simple.pl0a : 1; b : a 2; write(b)为例TAC 指令定义变量使用变量后继活变量t1 : 1t1—{t1}t2 : at2a{t1,t2}t3 : t2 2t3t2{t1,t3}b : t3bt3{b}实操在irgen/irgen.c的gen_tacs()后插入compute_liveness(ir_head)函数遍历 IR 链表计算每个节点的in/out集合价值此分析结果直接喂给codegen的寄存器分配器——codegen/regalloc.c中assign_reg()函数正是基于此决定哪个变量放%eax、哪个放%ebx5.3 用codegen的汇编输出验证龙书第 8 章的窥孔优化Peephole Optimizationcodegen/codegen.c已内置三条窥孔优化规则原始指令序列优化后触发条件movl $0, %eaxaddl %ebx, %eaxmovl %ebx, %eaxmov后跟add且源为 0pushl %eaxpopl %ebxmovl %eax, %ebx相邻 push/popcmpl $0, %eaxje labeltestl %eax, %eaxje labelcmp $0→test验证方法在codegen/codegen.c的gen_code_for_ir()中对IR_ASSIGN节点添加日志fprintf(stderr, Before opt: %s : %s\n, result_name, arg1_name); apply_peephole_opt(code_list); fprintf(stderr, After opt: %s\n, code_list-code);玄学提示开启优化后fib.pl0的汇编行数减少 12%但执行时间几乎不变——因为 PL0 程序太小CPU 流水线优势未体现换成test/prime.pl0求质数才能看到真实收益从那以后我每次教学生编译原理实验都强制他们先跑通scanner和parser的独立测试再碰semantic只要scanner输出的 token 流和parser生成的 AST dot 图都对后面四步就是填空。这份重庆大学的仓库最珍贵的不是代码本身而是它把龙书里那些黑匣子般的“假设编译器已生成…”变成了可触摸、可打断点、可改一行代码就看到效果的实体。希望帮到你。本文还有配套的精品资源点击获取