C0到MIPS课设编译器实战：从词法分析到汇编生成的数据链

简介这是北航计算机学院2017级编译原理课程设计项目目标是从C0语言到MIPS汇编的完整编译器实现面向计算机专业高年级学生及编译原理自学者适用于课程设计、教学演示与实验参考。压缩包共33个文件、总大小81KB主体为19个C源文件与8个头文件覆盖词法分析、语法分析、语义分析、中间代码生成、优化、寄存器分配及目标代码生成等完整编译环节另有3个txt文件、2个docx文档和1个md说明包含testfile.txt输入样例、mips.txt输出结果、2019年文法文档与附赠教学资料便于对照学习和二次开发。该资源已有61人学习可作为系统研读或分模块破解的蓝本。从源码到文档的编排能帮助读者快速定位各编译阶段的实现细节理解高级语言到汇编指令的转换流程对巩固编译原理理论、完成同类课程设计项目具有实际的参考价值。1. 为什么C0到MIPS的课设编译器总卡在中间一条数据链决定成败接手北航计算机学院2017级编译原理课程设计这个C0到MIPS编译器时多数人的第一反应是词法分析能默写语法分析能背诵可真把testfile.txt喂进去出来的mips.txt经常一片空白。这个项目的本质不是写一个能编译的玩具而是把编译器的词法、语法、语义到代码生成串成一条数据链。C0语言是教学用的精简C语言子集去掉指针和结构体保留函数、数组、条件和循环MIPS汇编则是教学演示里最容易观察寄存器、栈帧和跳转规则的指令集。它适合两类人正在复现课设、准备答辩的本科生以及想在一个小语言上把编译原理实验做过一遍、为后续编译器开发铺路的从业者。只要把这条链路上的数据接口定清楚这个项目就是编译课设里含金量最高的一类。2. 词法分析与递归下降语法分析从testfile.txt建立起可用的符号表前端三件事做完testfile.txt才算真正进入编译器。很多同学拿到课设第一反应是直接写一个巨大的main函数边读字符边拼逻辑结果调试一周还没跑通。常见做法是把前端拆成三个独立模块词法分析负责把字符流切成种别码递归下降语法分析负责把种别码流拼成结构符号表负责记录每个名字的类型和位置。三个模块各干各的事通过两个接口衔接一个是nextToken返回的单词一个是声明/查找符号的API。前端地基打稳后面出MIPS汇编才不会到处打补丁。2.1 种别码表与扫描函数跳空白、查关键字、预读处理双子符种别码表是整个前端的地基。C0语言的单词种类不多标识符、整数、字符常量、五类关键字、算术符、比较符、逻辑符、分隔符满打满算三十多个。我习惯用C的枚举类型一口气列全后续语法分析直接拿枚举值做分支比字符串比较快也不会把“if”和标识符搞混。扫描函数每调用一次返回一个种别码同时把单词正文或数值回填给调用方。typedef enum { ERRTOK, IDEN, INTLIT, CHARLIT, IF, ELSE, WHILE, RETURN, INT, CHAR, MAIN, PLUS, MINUS, MUL, DIV, ASSIGN, LT, LE, GT, GE, EQ, NE, AND, OR, NOT, LPAREN, RPAREN, LBRACK, RBRACK, LBRACE, RBRACE, COMMA, SEMI } TokenKind; TokenKind scanToken(FILE *in, char *lexeme, int *numVal) { int ch; do { ch fgetc(in); } while (ch || ch\t || ch\n || ch\r); if (ch ) { int nxt fgetc(in); if (nxt ) return EQ; // 是一个单词 ungetc(nxt, in); // 普通赋值回退多读的字符 return ASSIGN; } if (isalpha(ch) || ch _) { int n 0; while (isalnum(ch) || ch _) { lexeme[n] ch; ch fgetc(in); } ungetc(ch, in); lexeme[n] \0; return lookupKeyword(lexeme); // 不在关键字表就返回 IDEN } if (isdigit(ch)) { int v 0; while (isdigit(ch)) { v v * 10 ch - 0; ch fgetc(in); } ungetc(ch, in); *numVal v; return INTLIT; } return ERRTOK; }这段代码有两个容易被忽略的地方。第一跳空白时把\r也加进去Windows下testfile.txt的换行是\r\n不处理\r会把回车当成非法字符。第二等号处理是典型的“预读一个字符再回退”用ungetc把多读的字符还回去这样ab和ab都不会断错。关键字查表是另一个细节先把完整单词收进lexeme再查关键字表而不是边读边猜否则标识符“intx”会被误判成关键字int加标识符x。2.2 递归下降C0的语法结构如何映射成解析函数C0的文法非常适合手写递归下降。程序由声明、函数定义组成函数定义由参数表、局部变量声明、复合语句组成复合语句里又可以递归嵌套语句。这类语法有一个特点只要看到一个token就能决定接下来走哪个分支属于LL(1)的范畴不需要上yacc这类LALR工具。我一般把每个非终结符写成一个解析函数函数名就叫parseProgram、parseStmt、parseExpr和文法一一对应。int pos; Token cur; void advance() { cur nextToken(); } void expect(TokenKind k) { if (cur.kind ! k) error(语法错误: 期望种别码 %d, 实际得到 %d, k, cur.kind); advance(); } void parseStmt() { if (cur.kind IF) { advance(); expect(LPAREN); parseExpr(); expect(RPAREN); parseStmt(); if (cur.kind ELSE) { advance(); parseStmt(); } } else if (cur.kind WHILE) { advance(); expect(LPAREN); parseExpr(); expect(RPAREN); parseStmt(); } else if (cur.kind RETURN) { advance(); parseExpr(); expect(SEMI); } else if (cur.kind LBRACE) { advance(); while (cur.kind ! RBRACE) parseStmt(); advance(); } else { parseExpr(); expect(SEMI); } }这里的核心是一个全局前瞻token整个语法分析过程只向前看一个单词。else分支匹配的是表达式语句赋值语句和函数调用语句都走这里。一个需要提前埋好的设计是“同步符号”如果expect失败不能立刻return否则接下来几百个token全部变成连锁报错。常见做法是报错后跳过当前语句直到下一个语句开始符号IF、WHILE、RETURN、LBRACE、IDEN再恢复解析这样一次编译能列出多个错误而不是崩在第一个。2.3 符号表栈式作用域、查找最近声明、重复声明检查符号表是前端和后端之间的传话人。C0支持函数嵌套调用的词法作用域内层声明可以遮蔽外层同名变量离开作用域后外层声明恢复可见。我习惯用栈式符号表数组下标是作用域层次每一层存一份名字列表。查找时从栈顶往下找找最内层的那个声明时只查当前层是否重名不查外层——内层遮蔽外层是合法行为不能报重复声明。#define MAX_SCOPE 128 typedef struct { char name[32]; int type; // CHAR / INT / ARRAY int elemType; // 数组元素类型非数组时填 -1 int offset; // 栈帧偏移由后端在声明处回填 } SymItem; typedef struct { SymItem items[256]; int count; } Scope; Scope scopes[MAX_SCOPE]; int top -1; SymItem *findSym(const char *name) { for (int i top; i 0; i--) for (int j scopes[i].count - 1; j 0; j--) if (strcmp(scopes[i].items[j].name, name) 0) return scopes[i].items[j]; return NULL; } void declareSym(const char *name, int type, int elemType) { for (int j 0; j scopes[top].count; j) if (strcmp(scopes[top].items[j].name, name) 0) error(重复声明 %s, name); SymItem *s scopes[top].items[scopes[top].count]; strcpy(s-name, name); s-type type; s-elemType elemType; s-offset -1; // 后端布局时回填 }offset字段留到后端回填这是容易忽视的设计点。符号表在语法分析阶段只解决“这个名字合不合法、类型对不对”至于变量放在栈帧哪个位置要等函数体全部分析完、统计完所有局部变量大小之后才能定。提前在符号表里存一个-1占位代码生成阶段统一布局时再写入真实偏移。整个前端做完testfile.txt里的源代码已经变成了符号表和一棵隐含在调用序列里的语法结构剩下的事就是把这棵树翻译成MIPS指令。3. 从语法树到MIPS汇编栈帧布局、寄存器分配与表达式代码生成语法分析回答的是“这句话对不对”MIPS生成回答的是“这句话怎么算”。从这个阶段开始编译器进入最麻烦的地方——大量错误不会在编译期爆发而是到SPIM运行时才翻车。我的做法是先定三张表栈帧布局表、寄存器分工表、指令输出表。三张表定死代码生成器只是按模板填空越填越顺手。3.1 栈帧的offset计算保存ra、局部变量与形参的三种偏移口径MIPS函数调用天生需要一个栈帧进入函数时把$sp向下移动N字节函数返回前加回N。这N字节里要装三类东西局部变量、保存寄存器至少包括$ra、给子函数预留的参数区。我用的简化模型是以$sp为基址所有局部变量都通过$sp offset访问省去$fp维护成本适合课时有限的课设。栈帧区域相对$sp偏移大小用途局部变量区0 起localBytes局部变量、溢出临时值保存寄存器区localBytes 起regSaveBytes保存$ra以及被调用者保存的$s0-$s7参数区frameSize - argBytes 起argBytes调用子函数时实参槽位typedef struct { int localBytes; // 局部变量与临时空间总数 int regSaveBytes; // 保存寄存器区大小 int argBytes; // 参数区大小 int frameSize; // 三者求和并对齐 } Frame; void layoutFrame(Frame *f) { f-frameSize f-localBytes f-regSaveBytes f-argBytes; f-frameSize (f-frameSize 7) ~7; // MIPS O32 要求栈指针8字节对齐 }offset分配的逻辑是声明一个局部变量就在localBytes里追加它的字节数。int占4字节char占1字节int数组占元素个数乘4字节。比如函数里声明了int a[5]和int ilocalBytes就是20加4再加4。frameSize最后做一次向上取整到8的倍数这步对齐看着玄学实际是SPIM下lw/sw对地址对齐要求很严不补齐后面递归一深就崩。3.2 寄存器分工t0-t9算表达式s0-s7跨调用a0/v0/ra留给约定MIPS有32个通用寄存器教学编译器用不到全部但分工必须确定。核心矛盾是“临时寄存器”和“保存寄存器”的差异$t0-$t7是调用者保存子函数随便改$s0-$s7是被调用者保存子函数想用必须先压栈、返回前恢复。如果编译器自己生成的代码里保存寄存器该压没压函数返回后调用方的变量被踩掉查错能查到怀疑人生。寄存器别名职责谁负责保存$t0-$t7临时寄存器表达式逐层求值调用者保存$s0-$s7保存寄存器跨调用存活变量被调用者保存$a0-$a3参数寄存器调用子函数时传前四个实参调用者保存$v0/$v1返回值函数运算结果调用者保存$ra返回地址jal自动写入被调用者保存$sp栈指针栈顶被调用者保存#define REG_TEMP_MAX 8 int tempBusy[REG_TEMP_MAX]; int allocTemp() { for (int i 0; i REG_TEMP_MAX; i) { if (!tempBusy[i]) { tempBusy[i] 1; return i; } } return spillToStack(); // 没有空闲临时寄存器时把最老的值压栈 } void freeTemp(int r) { tempBusy[r] 0; }临时寄存器分配采用最简单的“占用位图”方案。每个临时寄存器一个忙闲标记用完立即释放。溢出策略不怕笨怕没有八个临时寄存器对C0的表达式深度来说基本够用真正耗尽时压栈比做复杂的寄存器重分配划算得多。C0没有浮点$f0那一组寄存器完全不用管这也是这个课设相对gcc这类编译器开发简单一大截的原因。3.3 表达式的代码生成模板先算右操作数还是左操作数表达式生成是整个代码生成里最需要小心的部分。加减符合法交换序子也会直面先算左操作数MIPS的代码生成顺序是“先算右操作数再算左操作数”还是反过来我的方案是先递归生成右操作数表达式把结果挪到$t1再递归生成左操作数表达式结果放$t0最后以$t0为主操作数执行指令。这样左操作数一旦算出来立刻参与运算不会被右操作数的递归调用冲掉。void genBinaryExpr(TokenKind op) { // 右操作数 genExpr(); emit(move, $t1, $t0); // 左操作数 genExpr(); switch (op) { case PLUS: emit(addu, $t0, $t0, $t1); break; case MINUS: emit(subu, $t0, $t0, $t1); break; case MUL: emit(mul, $t0, $t0, $t1); break; case LT: emit(slt, $t0, $t0, $t1); break; case EQ: emit(seq, $t0, $t0, $t1); break; default: error(不支持的二元运算 %d, op); } }两个坑必须提前说。第一减法、除法和比较运算都有方向性代码生成顺序一旦颠倒a - b会被算成b - a加法乘法因为交换律顺序错了也不报错这反而会掩盖问题。第二右操作数如果是个复杂表达式比如a (b - c)递归生成右子树时内部也会用$t0所以在递归之前就要把右子树结果挪走正确顺序是先算右、暂存、再算左。短路逻辑和||需要额外插入标签和跳转指令不在这个模板里但套路一致先算左为假直接跳到0结果标签。3.4 生成mips.txt的emit出口标签命名、缩进与文件头mips.txt的格式决定了你能不能直接在SPIM里跑起来也决定调试时能不能一眼看出问题。我一般会写一个统一的emit函数所有汇编输出都走这一个出口顺手做缩进和标签管理。这样以后想加注释、加行号、加统计功能只改这一处。FILE *out; int mipsLine 1; void emit(const char *fmt, ...) { fprintf(out, ); va_list ap; va_start(ap, fmt); vfprintf(out, fmt, ap); va_end(ap); fprintf(out, \n); mipsLine; }标签命名策略对调试影响很大。条件跳转和函数调用会产生大量标签我习惯统一按三种前缀管理函数入口直接用源函数名但要在文件头放一个.globl main条件跳转用L0、L1这种数字标签配合一个全局计数器临时变量用t%d命名。整个mips.txt的结构固定为.data段全局变量在前.text段函数定义在后main函数放在文本段最前面。SPIM默认从main开始执行入口标号错了后面全是白搭。4. 编译课设避坑排查五个让mips.txt跑不动的现场与修补下面这几条是我复现这类编译器时翻车次数最多的位置。每一条都按“现象、原因、解决”三段写你在自己的编译器里看到类似症状直接对号入座。4.1 SPIM提示“未包含main类型”入口标号与文本段顺序现象testfile.txt编译过程正常mips.txt也生成出来了但QtSpim一加载就弹“未包含main类型”命令行spim直接拒绝执行。 原因MIPS程序入口必须是一个叫main的全局标签SPIM加载时在文本段里找这个名字。如果生成器把main也按统一规则改成了f_main或者文本段第一个函数不是main加载器就认为没有入口。 解决代码生成阶段对函数名做防冲突处理时单独放行main文件开头固定输出.globl main并把main函数排到文本段第一位。4.2 词法预读回退缺失ab被断成a和b现象语法分析阶段报错说在b前面多了一个t或者把ab当成a小于b处理答案全错。 原因扫描器处理时只读取了字符就返回留下字符没处理下一个token就从开始。比较符、逻辑与、赋值号这类双子符必须一次读取两个字符。 解决按2.1的写法读到一个运算符后再ungetc把第二个字符还回去至少要保证、、|这类字符参与双字符判断。这个bug越早修代价越小等语法分析写完再回头改词法牵一发而动全身。4.3 数组寻址偏移没乘元素宽度lw的offset全部错位现象编译能过但运行时a[0]的值取出来不对a[1]和a[2]混成一片甚至直接触发地址未对齐异常。 原因数组a[5]声明时localBytes分配了20字节但生成寻址代码时直接用下标i做offset没按元素类型乘宽度。int数组元素之间相隔4字节char数组相隔1字节混用数组时最明显。 解决寻址指令里lw/sw的offset是“基址 下标 * elementSize”。int elemBytes (elemType CHAR) ? 1 : 4; int addrOffset varOffset index * elemBytes;4.4 减法除法操作数颠倒交换律掩盖了加乘的错现象加法、乘法结果都对减法、除法、比较运算结果全反。比如调用一个函数计算a - bSPIM里算出来的却是b - a。 原因这就是3.3里那个顺序问题。先算左操作数放进$t0再算右操作数时递归过程把$t0覆盖了最后sub指令操作数变成了左值丢失后的结果。加法乘法是交换的所以顺序错了也碰巧“正确”让你误以为整个表达式生成没问题。 解决统一按“先右后左再计算”的模板。右操作数结果立刻挪到$t1保存左操作数算完留在$t0主操作数永远是$t0。这一条建议在生成阶段写一个assert任何递归生成表达式结束时结果约定在$t0。4.5 栈帧不对齐递归深度一上去就错乱现象单层函数调用正常两层、三层递归时SPIM报错或者函数返回后$sp值不对出现无法解释的内存写入。 原因MIPS的O32 ABI要求$sp始终保持8字节对齐进入函数压栈多少、返回前就弹栈多少。如果frameSize不是8的倍数第一次对齐没问题递归之后每次错4字节错误越积越多。 解决所有栈帧分配统一走对齐宏入口和出口的栈指针调整只允许成对出现。#define ALIGN8(x) (((x) 7) ~7)注意这类问题排查时先看每个函数的入口addiu和出口addiu。入口压入多少出口必须原样加回数字对不上就先把这里修复再去查别的寄存器和偏移。5. 把mips.txt跑起来自测样例设计与QtSpim仿真验证代码生成完不等于编译器写完。最后一步是把mips.txt扔进SPIM跑通并且验证结果可预期。很多同学栽在“不知道自己的编译器到底哪一步坏了”就是因为没有一份覆盖主要语法点的自测样例也没建立一套从汇编文本到运行的判定顺序。这一章给你一套可以直接抄的验证方法。5.1 一份覆盖主要语法点的testfile.txt自测程序自测样例的设计原则是“一个文件覆盖尽量多的语法点”。我常用的样例是一段递归求斐波那契加数组求和的混合程序函数调用、递归、数组、while、条件判断、算术比较全齐了。程序最终返回值是23fib(4)等于3数组求和是0加2加4加6加8等于20。int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); } int main() { int a[5]; int i; int sum; i 0; sum 0; while (i 5) { a[i] i * 2; sum sum a[i]; i i 1; } return fib(4) sum; }这个样例有几个测试点值得注意fib递归会反复调用自身能验证每条函数调用路径的栈帧分配与释放是否正确数组a[5]用下标赋值再累加能验证offset计算有没有乘元素宽度while和if两个控制流分支同时出现能验证条件跳转的标签生成顺序。编译成功后你把mips.txt里main函数的最后一条指令改成查看$v0SPIM执行完main返回值寄存器应该正好是23。对比预期值一次就能判断题是否正确。5.2 用QtSpim或命令行spim加载mips.txt的两种跑法QtSpim图形界面适合单步调试命令行spim适合快速回归。我一般两个都用命令行跑自动用例图形界面看可疑函数的单步指令。# 命令行方式加载并运行结束后可用 print $v0 查看返回值 spim -file mips.txt # 加载进交互环境手动执行 spim # 在 spim 交互提示符下 print $v0QtSpim操作路径是Reinitialize并加载mips.txt然后Run。运行结束后在Register面板找到$v0寄存器数值应该是指定返回值。如果程序在运行中途异常QtSpim会停在异常指令上面板上能看到当前PC地址和触发异常的指令。命令行spim的优点是脚本化适合把自测样例批量验证出了问题再回图形界面细看。5.3 从“黑匣子”到可信四个步骤的判错顺序mips.txt如果运行结果不对先别急着瞎改代码生成器。我按下面四步排查基本能定位九成问题。第一步检查文本结构。mips.txt第一处有效内容应该是.globl main.text段里第一个函数是main。用grep快速扫入口避免在入口标号错误上浪费时间。第二步检查栈平衡。把mips.txt里所有addiu/sp指令打出来人工配对每个函数入口和出口的栈指针调整。入口压了32字节出口就必须加回32字节中间嵌套函数的调用点也要检查子调用前的参数区预留。第三步检查数组寻址。凡是出现lw/sw带寄存器偏移的指令确认偏移值是不是已经乘过元素宽度。这一步可以用小数组样例单独验证。# 快速体检 mips.txt 的段与入口 grep -n main\|.text\|.data mips.txt # 查看所有栈指针调整手工配对分配与释放 grep -n \$sp mips.txt第四步单步执行。在QtSpim里给可疑函数设置断点或直接单步观察每条指令执行后寄存器变化。重点看$sp是否有回弹、$ra是否保存和恢复成对、$t0到$t2的值是否符合代码生成模板的预期。四步走完还定位不到就把生成器里emit加verbose开关每发一条指令打印源文件的对应行用“代码行号”反向追。6. 让教学编译器可维护的三个习惯表驱动、统一错误出口与自检断言课设验收之后如果需要继续改或加功能三个习惯能显著降低维护成本。第一个是把运算符到MIPS指令的映射做成表。C0的运算符不算多C语言里switch硬写也能行但表驱动的好处是“加运算符只加一行表项”生成器主体不用动。typedef struct { TokenKind op; const char *ins; // MIPS 指令名 int commutes; // 是否为交换操作 } OpMap; OpMap opTable[] { {PLUS, addu, 1}, {MINUS, subu, 0}, {MUL, mul, 1}, {DIV, div, 0}, {LT, slt, 0}, {EQ, seq, 0}, };第二个是统一错误出口。词法、语法、语义、代码生成四个阶段都会报错我习惯把它们全部收拢到一个reportError函数统一携带行号和当前token信息。课设答辩时老师问“错误处理怎么设计的”拿这一个函数就能讲清楚调试时错误信息带上行号也能直接定位到源文件对应行。void reportError(const char *fmt, ...) { fprintf(stderr, line %d: , lineNo); va_list ap; va_start(ap, fmt); vfprintf(stderr, fmt, ap); va_end(ap); fprintf(stderr, \n); exit(-1); }第三个是自检断言。所有parse函数和gen函数入口处用assert检查当前token或寄存器状态是否符合预期。比如genBinaryExpr开头断言$t0空闲parseExpr的递归分支前后检查临时寄存器数量平衡。这类断言看着啰嗦实则是编译器内部最廉价的“越早崩越好”——等生成出错的汇编再被SPIM弹异常排查成本是编译期的十倍。我做这个项目时最深的血泪经验是编译器和玩具之间就差那几张表。万能的寄存器分配、漂亮的优化器都不是课设的核心把token流、符号表、栈帧、标签这几条数据链的口径统一了mips.txt自然就能跑。后来写任何小型翻译器我都先把错误出口和映射表建好再写核心逻辑。如果你在复现C0到MIPS这条路时也卡在某一步把临时寄存器、栈偏移和标签名列成一张表多数问题会自己跳出来。希望帮到你。本文还有配套的精品资源点击获取