简介编译器是连接高级语言与机器指令的桥梁其核心涉及词法分析、语法分析、中间代码生成与优化等技术。理解这些环节不仅能揭示程序从源码到可执行文件的完整转化过程也为构建高效、可移植的编译系统奠定基础。在工程实践中中间代码的四元式表示、DAG优化以及寄存器分配等策略直接影响生成代码的质量与运行效率。针对高校课程设计与工程入门基于C0语言的MIPS编译器提供了一个完整的全流程范例涵盖从语法树构建到目标汇编生成的关键模块。该实现以一份课设源码为线索逐步拆解各模块的协作方式与常见陷阱帮助读者快速掌握编译器后端翻译与优化的核心思想。1. 从testfile.txt到mips.txt这门课设真正难住人的是后端翻译说实话我拿到这份北航2017级编译原理课程设计源码时第一反应是“词法、语法应该不难”真正翻进去才发现从C0语言到MIPS汇编这个编译器里最耗精力的不是前端那几个扫描器而是把中间代码翻译成mips.txt那一步。整个项目把testfile.txt作为C0源代码输入经过词法分析、语法分析、语义检查、中间代码生成、优化、寄存器分配最终输出MIPS汇编文件清单里甚至连ARM后端都有对想弄懂编译器全流程的人来说是份很扎实的参考样本。适合正在赶编译原理实验报告的学生、想快速回顾一遍“源代码到机器指令”全链路的从业者或者准备编译器相关岗位面试的人。2. 词法与语法分析让testfile.txt先变成一棵可判错的语法树C0语言是教学用的类C语言保留字不多没有浮点没有字符串类型词法和语法都相对克制。但克制不等于简单——词法要把testfile.txt逐字符切成Token语法要把Token流按文法归约成语法树这棵树的正确性直接决定后面所有模块的输出质量。工程结构上词法在word_analyze.cpp里语法在grammar_analyze.cpp里符号表在symbolTable.h和symbol.cpp里错误统一走error.cpp文法依据是包里的2019年文法.docx。这章就按这个顺序拆。2.1 词法分析word_analyze.cpp怎么把C0源码切成TokenC0的Token类型比C语言少得多关键字、标识符、整数常量、运算符、界符外加文件结束符。word_analyze.cpp里采用的做法一般是逐字符扫描的主循环每进入一次返回一个Token。扫描时需要跳过空白和注释注释在C0里通常支持//和/* */两种这对词法分析器来说是个容易被忽略的细节。// word_analyze.cpp 词法扫描骨架示意 enum TokenType { TK_IDENT 1, TK_NUMBER, TK_KEYWORD, TK_OPERATOR, TK_DELIMITER }; typedef struct { TokenType type; char lexeme[64]; // 单词原文 int line, col; // 行列号供语法层报错 } Token; Token nextToken(FILE* src) { Token tok {0}; int ch skipWhitespaceAndComment(src); // 跳过空白与注释 if (ch EOF) { tok.type TK_EOF; return tok; } if (isalpha(ch) || ch _) { int len 0; while (isalnum(ch) || ch _) { tok.lexeme[len] (char)ch; ch fgetc(src); } ungetc(ch, src); tok.type lookupKeyword(tok.lexeme) ? TK_KEYWORD : TK_IDENT; } else if (isdigit(ch)) { // 连续读数字C0整型常量不支持后缀 tok.type TK_NUMBER; } else { // 运算符和界符注意 、! 这类双字符需要预读下一位 } return tok; }这里最关键的两点一是Token里必须带line和col后面语法分析报错全靠它否则排错要数行数二是双字符运算符要用预读一位的方式处理常见写法是先读进第一个字符再peek第二位拼成或!拼不上就把第二位ungetc回去。C0保留字就那么十几个lookupKeyword用线性表查都可以没必要上哈希。2.2 语法分析grammar_analyze.cpp的递归下降与优先级处理语法分析按2019年文法.docx用递归下降实现这类文法大多是LL(1)的写起来直接每个非终结符对应一个函数遇到终结符就比对lookahead遇到非终结符就调对应的函数。C0里最容易出问题的是表达式优先级。表达式文法通常是分层写法加法和减法一层乘法和除法一层括号和原子再一层这样左递归和优先级问题一起解决。// grammar_analyze.cpp 表达式解析示意 void parseExpression() { parseTerm(); // 先解析最高优先级的乘除层 while (lookahead.type TK_OPERATOR (lookahead.lexeme[0] || lookahead.lexeme[0] -)) { char op lookahead.lexeme[0]; advance(); // 吃掉双目运算符 parseTerm(); // 右操作数 emitQuaternion(op); // 生成一条四元式存入中间代码序列 } }parseTerm的实现结构和parseExpression几乎一样只是运算符换成*和/底层再调parseFactor处理数字、标识符和括号。这里的while循环对应文法的{ (|-) term }部分本质是“提取左因子后再展开闭包”比递归调自己稳妥得多不会栈溢出。语法错误时的恢复策略在error.cpp里记录当前行列号输出统一格式的错误信息然后跳过Token直到遇到分号或右花括号避免一次错误引发连锁报错。这个策略在课设里特别重要否则一个漏写的分号会让后面几十行全部变成错误报告。2.3 符号表与错误恢复symbolTable.h和error.cpp的协作符号表是编译器的“记账本”每个标识符的类型、作用域层级、栈帧偏移全部记在里面。type.cpp、type.h和gtype.h负责类型定义这一侧symbol.cpp负责插入和查找。教学编译器里函数不允许嵌套是常见约定于是符号表做成作用域链全局一层每进入一个函数或复合语句块就压一层退出时弹出。// symbolTable.h 符号表示意 struct Symbol { char name[64]; int type; // INT / VOID / ARRAY int level; // 0 表示全局1 表示函数内第一层块 int offset; // 相对栈帧的偏移目标代码生成时要用 Symbol* next; // 同层符号链表 };插入时走InsertSymbol查找时从当前层逐层向全局层回溯这样两个函数里同时定义变量i才不会互相覆盖。这里有个细节函数参数也占用一层作用域退出函数体时要把参数和局部变量一起弹出顺序反了就会出现后面讲的同名变量串台问题。error.cpp里通常把错误分成词法错误、语法错误、语义错误三类分别编号。语义错误典型的有“变量未定义”“函数重定义”“类型不匹配”这类错误不在语法分析阶段拦截而在遍历语法树阶段检查。3. 中间代码生成与优化tempCode.h里的四元式如何被DAG和活跃分析反复打磨语法分析做完程序已经被“看懂”了接下来要把它转成一种离机器更近、又跟具体指令集无关的中间表示。这个项目的中间表示是四元式定义在tempCode.h里。四元式的好处是结构规整每个运算都能映射成一条指令DAG优化、活跃变量分析、寄存器分配都在这一层操作。等这层处理完再交给目标代码生成前后端就能相对独立地改。3.1 四元式tempCode.h里中间表示的结构与生成四元式的四个字段是op、arg1、arg2、result语义是“arg1 op arg2 的结果存到 result”。操作码枚举覆盖C0需要的全部运算加减乘除、赋值、跳转、条件跳转、函数调用、返回、输出。// tempCode.h 四元式结构示意 enum QOp { Q_ADD, Q_SUB, Q_MUL, Q_DIV, Q_ASSIGN, Q_GOTO, Q_IF_TRUE_GOTO, Q_IF_FALSE_GOTO, Q_CALL, Q_RETURN, Q_PRINT }; struct Operand { int kind; // 0: 常量, 1: 变量, 2: 临时变量, 3: 函数名 int value; // 常量值或变量编号 char name[64]; // 变量名或函数名 }; struct Quad { QOp op; Operand arg1, arg2, result; };tempCode.cpp负责把这些结构填进一个动态数组就是中间代码序列。见到一个加法表达式就发一条Q_ADDresult里放一个新的临时变量编号编号由temp_reg.cpp统一分配一般是t1、t2这种形式。这里要特别说明临时变量和用户变量不要混用编号。用户变量可以在符号表里找到名字和栈帧偏移临时变量则只活在四元式流里后面寄存器分配时会优先处理它们区分开来才能让优化器清楚地判断一个值的活跃范围。3.2 DAG优化与常量折叠dag.cpp和constoptimize.cpp在做什么这一节讲优化侧。constoptimize.cpp负责常量折叠int a 2 3;这种在编译期就算出5直接生成a5的四元式运行时少算一次。dag.cpp做公共子表达式删除如果两处计算的是完全相同的表达式比如b * c d出现两次第一次算完后把结果临时存起来第二次直接复用不再重复计算。// dag.cpp DAG节点示意 struct DAGNode { int op; // 运算符Q_ADD / Q_MUL 等 int leftChild; // 左子节点编号-1 表示无子节点 int rightChild; // 右子节点编号 std::vectorint attachVars; // 挂在该节点上的变量编号 };构建顺序从基本块内第一条语句往后扫。每遇到一个形如t a op b的四元式先在已有节点里找op相同、左右子节点也相同的节点找到就把t挂到它的attachVars里找不到才新建节点。regenerate_quas.cpp负责把构建好的DAG重新展开成新的四元式序列这一步是“公共子表达式删除”的落地动作。需要留意的是跳转类语句不能进DAG遇到跳转就必须切到下一个基本块重新建图否则控制流会被破坏。很多课设优化出问题都出在这个边界条件上。3.3 基本块划分与活跃分析blockdivide.cpp和active_analyze.cpp基本块是优化和寄存器分配的基本单位。blockdivide.cpp按标准规则切块基本块入口是第一条语句、跳转目标语句、以及跳转语句的下一条语句一旦遇到跳转或函数调用返回基本块结束。切完块后active_analyze.cpp做活跃变量分析。活跃变量分析是反向数据流分析从基本块出口往回推。一个变量的活跃区间起点是“被赋值的那条四元式”终点是“最后一次被使用的那条四元式”。常见实现是用use和def集合迭代反向遍历基本块内每条指令 live_in (live_out - def) ∪ use这里use是“在赋值前被引用的变量集合”def是“被赋值的变量集合”。如果有变量只在某条赋值语句中作为def出现、从未被use那它在live_in和live_out里都是空的这条赋值就是死代码可以在优化阶段删掉。具体到项目里active_analyze.cpp输出的活跃信息会喂给register_allocate.cpp和optimized_mips_generate.cpp是优化版和基础版生成结果差异最大的信息源之一。4. 目标代码生成与寄存器分配把中间表示最终落成mips.txt后端是整条链路的最后一公里。前面做得再好这里翻译错一条指令整个程序结果就不对。这个项目里有两套后端mips_generate.cpp是基础版逐条把四元式翻译成MIPS指令optimized_mips_generate.cpp是优化版把寄存器分配结果用起来。两套可以对照着看很容易理解“优化到底优化了什么”。4.1 基础生成mips_generate.cpp的指令翻译规则基础版后端最稳妥的做法是全栈式分配每个临时变量在栈帧里占一个固定偏移每条四元式都翻译成“load到寄存器、运算、store回内存”三件套。虽然访存次数多但正确性容易保证适合先跑通再优化。四元式生成的MIPS指令备注Q_ADD t1, t2, t3lw $t0, off(t2); lw $t1, off(t3); add $t0, $t0, $t1; sw $t0, off(t1)临时变量全部放栈帧Q_ASSIGN a, blw $t0, off(b); sw $t0, off(a)常量直接liQ_IF_FALSE_GOTOlw $t0, off(arg); beq $t0, $zero, label分支目标后建议插入nopQ_CALLsw参数; jal 函数名func_insert.cpp负责插桩// mips_generate.cpp 指令发射骨架示意 void emitQuad(Quad q) { switch (q.op) { case Q_ADD: printf(lw $t0, %d($sp)\n, offsetOf(q.arg1)); printf(lw $t1, %d($sp)\n, offsetOf(q.arg2)); printf(add $t0, $t0, $t1\n); printf(sw $t0, %d($sp)\n, offsetOf(q.result)); break; case Q_ASSIGN: // 先load后store常量的情况直接li break; } }这里的offsetOf查的就是符号表里记录的offset字段。每个函数进入时由func_insert.cpp在入口调整栈指针、在出口恢复函数内的临时变量偏移都相对于栈指针计算。如果生成的mips.txt在模拟器里跑起来栈指针错乱优先检查函数序言和收尾的栈调整指令。基础版跑通后再去碰寄存器分配这是课程设计里性价比最高的推进顺序。4.2 寄存器分配register_allocate.cpp怎么减少load/store寄存器分配的目标就是少访存。register_allocate.cpp采用基于活跃区间的线性扫描分配策略先按四元式顺序算出每个临时变量的活跃区间再按区间起点排序依次给区间分配物理寄存器。// register_allocate.cpp 线性扫描分配骨架伪代码风格 sort(intervalsByStart); // 区间按起点排序 for (interval : intervals) { expireOldIntervals(); // 结束的区间释放寄存器 if (freeRegs.empty()) { spill(interval); // 没有空闲寄存器就溢出到栈 } else { bind(interval, allocReg()); // 绑定一个 $t/$s 寄存器 } }spill的常见策略是把当前区间值写回栈帧等区间再次被引用时再load回来。这里有个分层容易混temp_reg.cpp是临时寄存器分配器解决的是“发射一条指令前临时借用$t寄存器”的问题register_allocate.cpp解决的是“一个临时变量在整个活跃区间内驻留哪个寄存器”的问题。前者粒度是一条指令后者粒度是整个区间两套逻辑用在不同阶段。4.3 优化版与ARM版后端optimized_mips_generate.cpp说明了什么optimized_mips_generate.cpp的优化核心很简单寄存器分配完成后临时变量的值尽量留在寄存器里不再每条指令都load/store。同一个变量活跃区间内多次引用只load一次区间结束时才store回栈帧。配合active_analyze.cpp给出的区间终点它能做到精确控制回写时机。项目里有个optimized_mips_generatearm.cpp这个文件特别说明问题DAG优化、活跃分析、寄存器分配这些模块跟ISA无关真正要改的只有指令发射部分。换成ARM后寄存器数量从MIPS的32个变成16个$t0换成r0lw/sw换成ldr/strspill策略要更激进。两部分对照着看对“后端可移植”的理解会非常直观。optimize.cpp和optimize.h在这个项目里是优化总入口按“切基本块→DAG优化→活跃分析→寄存器分配→生成优化汇编”调度一遍跑完直接产出mips.txt。5. 课程设计避坑指南五件事先看明白省下通宵调错的四个小时这一章写的都是我在课设和实际教学里见过、踩过的真实坑。每一条都按“现象→原因→解决”说清楚前置知识够的话能省你大量排查时间。5.1 坑一testfile.txt的换行和编码带崩了词法分析现象用记事本新建的testfile.txt第一次跑编译器就报第一个Token非法或者报错行号整体偏移一行。 原因Windows记事本默认utf-8带BOM词法分析器把BOM当成普通字符另外\r\n换行下\r没被空白处理逻辑跳过。 解决源码里skipWhitespaceAndComment要把\r和\n都加入空白集合文件用VS Code或Notepad存成utf-8无BOM格式。项目里所有样例input都建议统一LF换行最省事。5.2 坑二左递归文法让递归下降直接栈溢出现象编译一跑就崩溃报栈溢出还挺稳定地崩在表达式解析。 原因文法写成了expr - expr term这种左递归形式递归下降直接无限递归。 解决把左递归改写成expr - term {(|-) term}用循环取代递归。2019年文法.docx里的表达式部分已经是改造后的写法直接照抄即可若自己设计新文法先检查有没有左递归。5.3 坑三MIPS延迟槽导致跳转指令行为错乱现象生成的mips.txt在MARS里跑得好好的换到SPIM里控制流全乱。 原因MIPS指令集有延迟槽分支指令后的那条指令无论是否跳转都会被执行。MARS默认关闭延迟槽SPIM默认开启同一个二进制在不同模拟器里表现不一致。 解决代码生成器在beq/bne/jal后面强制发射一条nop或者统一按延迟槽开启的方式生成。我一般会在发射器里写死“条件跳转后补nop”的规则这样两个模拟器下行为一致后面做大表达式测试时排错省非常多时间。5.4 坑四寄存器分配后忘了回写内存优化一开结果就错现象基础版编译器输出结果全对换成优化版输出只有前半段对后半段开始变量值串位。 原因寄存器分配器在活跃区间结束时没有把寄存器里的值store回栈帧下一个区间复用了这个寄存器旧值丢失。 解决分配器必须根据活跃分析算出的区间终点在该点生成sw指令把寄存器数据写回对应栈偏移。检查办法是编译一个函数内多次循环使用同一个变量、且变量不在循环外使用的样例观察生成的汇编里是否有对应回写。5.5 坑五符号表作用域没弹栈同名变量串台现象两个函数里都定义了int i第一个函数执行完第二个函数里的i初始值变成了第一个函数残留的值。 原因符号表在退出函数或复合语句块时没有弹出该层所有符号查找时命中了旧作用域里的同名项。 解决在符号表实现里维护一个作用域层级计数器进入块时level退出块时删除所有level等于当前层级的符号再level--。查找函数从当前层级向下回溯。加一个双函数同名变量的测试用例这道坑就露不出来。6. 用SPIM和MARS验证mips.txt三个让编译器“开口说话”的技巧编译器的“死法”很多但有个共性的验证思路先让程序跑起来再让程序跑错最后让程序跑出性能差异。第一步构造一个能覆盖全部语义的testfile.txt。测试代码要短但要全一个整型函数、一个带返回值的加法函数、一个while循环里累加变量、一个if-else分支、一个数组访问最后加一个调用函数并把返回值打印出来的语句。C0的打印一般通过MIPS系统调用实现输出整数在模拟器里能看到数值比对。预期结果先在纸上算好比如循环10次累加5到x等于50然后直接看模拟器输出。第二步把mips.txt喂给模拟器。MARS里File→Assemble之后再RunSPIM可以用命令行跑。我先关掉延迟槽跑通一遍再打开延迟槽选项跑一遍两遍结果一致说明分支指令后的nop处理是对的。遇到syntax error先看行号多半是代码生成器发射了MIPS不存在的指令或漏写了操作数逗号。这一步要用未优化的基础版mips.txt做基准再上优化版两个输出分别跑一遍数值一致才算优化没引入bug。第三步验证优化效果。把testfile里写两个完全相同的a*bc表达式分别赋给两个变量。用diff对比基础版和优化版生成的mips.txt重点看lw和sw指令数量。优化版明显减少且结果不变说明DAG公共子表达式删除和寄存器分配真的生效了。从那以后我每次拿到编译器项目都强制先跑一遍“错误注入测试”故意写错一个符号、漏一个分号、在函数里重复定义变量看编译器能不能优雅地报错而不是崩溃这比任何功能测试都更能检验一个编译器的真实完成度。希望帮到你。本文还有配套的精品资源点击获取