南航编译原理课程设计：从词法分析到目标代码生成的完整实现指南

简介这份南京航空航天大学编译原理课程设计资源面向计算机专业学生及需要完成编译原理课设的学习者提供一套经检验无BUG的完整实现方案。压缩包共32个文件约961KB包含词法分析与语法分析两大模块源码部分有c、cpp、h文件配套可执行exe、obj、pdb等编译产物另有doc实验报告、ppt答辩课件及txt说明文档覆盖从代码到文档的全流程。资源中词法部分实现字符读取、token识别与属性字管理语法部分提供分析程序与符号表结构便于理解编译前端各阶段的衔接逻辑。目前已有749人学习下载适合参考其目录组织、模块划分与调试思路快速搭建课设框架并对照完善自己的实现。1. 南航编译原理课程设计从词法分析到目标代码生成的完整落地路径如果你正在南航读计算机相关专业大概率会在大三上学期撞上编译原理课程设计。这门课不是让你背几个文法推导就完事而是要求你从零实现一个能跑通的小型编译器通常覆盖词法分析、语法分析、语义分析、中间代码生成和目标代码生成五个阶段。南航的课设一般给一个简化语言子集比如类 Pascal 或类 C 的迷你语法让你用 C 或 Java 写完整前端加后端。很多人第一次拿到题目觉得无从下手其实核心就一句话把源程序翻译成等价的汇编或四元式序列。适合已经学过编译原理理论课、但不知道如何把龙书里的算法变成可运行代码的同学。接下来我会按实际开发顺序把每个阶段的实现要点、参数设置和常见翻车点讲清楚。2. 词法分析与符号表用有限自动机把字符流切成 Token2.1 为什么先做词法分析而不是直接写语法分析词法分析是整个编译器的入口任务是把源程序的字符流转换成有意义的 Token 序列。南航课设通常要求支持关键字、标识符、整数常量、运算符和界符。常见做法是手写一个确定有限自动机DFA用状态转移表驱动。为什么不建议一上来就写语法分析因为语法分析依赖 Token 流如果词法阶段没有把标识符和关键字区分开后面语法规则会写得非常混乱。我一般会先定义 Token 结构体包含类型和值两个字段类型用枚举表示值用字符串或整数存储。// token.h typedef enum { TOKEN_KEYWORD, // 关键字如 if、while、int TOKEN_ID, // 标识符 TOKEN_NUM, // 整数常量 TOKEN_OP, // 运算符 - * / TOKEN_DELIM, // 界符 ( ) { } ; , TOKEN_EOF // 结束符 } TokenType; typedef struct { TokenType type; char value[64]; // 存储原始字符串 int line; // 行号用于报错 } Token;逻辑说明枚举类型覆盖了南航课设要求的所有 Token 类别。value 字段用字符数组而不是指针避免动态内存管理带来的悬空指针问题。line 字段是必须的否则语法错误时无法定位到具体行。参数说明value 长度设为 64 足够容纳课设中出现的标识符和数字如果要求支持长字符串可以改成动态分配。2.2 符号表的三种实现方式与选型建议符号表贯穿词法分析到语义分析用来记录变量名、类型、作用域和存储位置。南航课设一般要求支持全局变量和局部变量所以符号表需要支持作用域嵌套。常见做法有三种线性表、二叉搜索树和哈希表。线性表实现最简单但查找效率低适合变量数量少于 50 个的场景。哈希表查找接近 O(1)但需要处理冲突。我一般用哈希表加链地址法因为课设规模不大冲突概率低实现起来也不复杂。// symtab.h #define HASH_SIZE 211 typedef struct Symbol { char name[64]; char type[16]; // int 或 char int scope; // 作用域层级0 为全局 int offset; // 相对于栈帧的偏移 struct Symbol *next; // 哈希冲突链 } Symbol; Symbol *hashTable[HASH_SIZE]; unsigned int hash(char *name) { unsigned int h 0; while (*name) { h h * 31 *name; } return h % HASH_SIZE; } void insertSymbol(char *name, char *type, int scope) { unsigned int idx hash(name); Symbol *s (Symbol *)malloc(sizeof(Symbol)); strcpy(s-name, name); strcpy(s-type, type); s-scope scope; s-next hashTable[idx]; hashTable[idx] s; }逻辑说明哈希函数用经典的 h*31字符 方式31 是经验值能减少冲突。insertSymbol 采用头插法新符号插入链表头部查找时从头部开始遍历。参数说明HASH_SIZE 取 211 是因为它是质数能进一步降低冲突率。scope 字段用于区分同名变量在不同作用域的情况查找时需要从当前作用域向外逐层查找。提示符号表插入时不要覆盖同名符号应该先查找当前作用域是否已存在存在则报重复定义错误。3. 语法分析与抽象语法树递归下降是课设最稳的选择3.1 递归下降分析器的代码骨架语法分析阶段要把 Token 流转换成抽象语法树AST。南航课设通常要求支持表达式、赋值语句、if 语句和 while 语句。常见做法有递归下降、LL(1) 和 LR(1)。递归下降最容易手写代码结构清晰调试方便。LL(1) 需要构造预测分析表LR(1) 需要构造项目集规范族工作量更大。我一般推荐递归下降因为课设时间有限递归下降能快速跑通。// parser.c Token currentToken; void nextToken() { currentToken getNextToken(); } ASTNode *parseExpression() { ASTNode *left parseTerm(); while (currentToken.type TOKEN_OP (currentToken.value[0] || currentToken.value[0] -)) { char op currentToken.value[0]; nextToken(); ASTNode *right parseTerm(); left createBinaryNode(op, left, right); } return left; } ASTNode *parseTerm() { ASTNode *left parseFactor(); while (currentToken.type TOKEN_OP (currentToken.value[0] * || currentToken.value[0] /)) { char op currentToken.value[0]; nextToken(); ASTNode *right parseFactor(); left createBinaryNode(op, left, right); } return left; }逻辑说明parseExpression 处理加减运算parseTerm 处理乘除运算这样自然实现了乘除优先级高于加减。createBinaryNode 创建一个二叉树节点左子节点和右子节点分别指向操作数。参数说明currentToken 是全局变量nextToken 负责从词法分析器获取下一个 Token。注意在解析完一个表达式后要检查 currentToken 是否在预期集合中否则报语法错误。3.2 AST 节点设计与内存管理AST 节点需要存储节点类型、子节点指针和附加信息如变量名、常量值。南航课设一般要求输出语法树或直接用于后续语义分析。我一般用联合体union来节省内存因为不同节点类型携带的信息不同。typedef enum { NODE_NUM, NODE_ID, NODE_BINOP, NODE_ASSIGN, NODE_IF, NODE_WHILE, NODE_BLOCK } NodeType; typedef struct ASTNode { NodeType type; union { int num; // NODE_NUM char name[64]; // NODE_ID struct { // NODE_BINOP char op; struct ASTNode *left, *right; } binop; struct { // NODE_ASSIGN char name[64]; struct ASTNode *expr; } assign; struct { // NODE_IF struct ASTNode *cond, *thenBranch, *elseBranch; } ifStmt; struct { // NODE_WHILE struct ASTNode *cond, *body; } whileStmt; } data; } ASTNode;逻辑说明union 让所有节点类型共享同一块内存节省空间。NODE_BINOP 存储运算符和左右子节点NODE_ASSIGN 存储变量名和右值表达式。参数说明name 数组长度 64 与符号表保持一致。内存管理方面建议在程序结束时统一释放 AST避免内存泄漏。如果课设要求输出语法树可以写一个递归打印函数按缩进输出节点信息。注意递归下降分析器遇到左递归文法会死循环必须先把文法消除左递归再写代码。比如 E - E T 要改成 E - T EE - T E | ε。4. 语义分析与中间代码生成四元式是课设的通用语言4.1 语义检查的三个核心任务语义分析阶段要完成类型检查、作用域检查和符号表填充。南航课设通常要求检测变量未声明、重复声明和类型不匹配。类型检查可以在 AST 遍历时进行给每个表达式节点标注类型。作用域检查依赖符号表的 scope 字段进入新作用域时增加层级退出时恢复。我一般用一遍 AST 遍历完成所有语义检查同时生成中间代码。// semantic.c void checkNode(ASTNode *node, int currentScope) { if (node NULL) return; switch (node-type) { case NODE_ID: if (lookupSymbol(node-data.name, currentScope) NULL) { fprintf(stderr, Error: undeclared variable %s\n, node-data.name); } break; case NODE_ASSIGN: checkNode(node-data.assign.expr, currentScope); if (lookupSymbol(node-data.assign.name, currentScope) NULL) { fprintf(stderr, Error: undeclared variable %s\n, node-data.assign.name); } break; case NODE_BINOP: checkNode(node-data.binop.left, currentScope); checkNode(node-data.binop.right, currentScope); break; default: break; } }逻辑说明checkNode 递归遍历 AST遇到标识符节点时查找符号表找不到就报未声明错误。赋值语句先检查右值表达式再检查左值变量是否声明。参数说明currentScope 表示当前作用域层级lookupSymbol 需要从当前层级向外逐层查找。4.2 四元式生成规则与回填技术中间代码用四元式表示格式为 (op, arg1, arg2, result)。南航课设一般要求生成四元式序列然后翻译成汇编。四元式生成可以在语义分析时同步完成。对于 if 和 while 语句需要用到回填技术因为条件跳转的目标地址在生成时还不确定。// quad.c typedef struct { char op[8]; // 操作符如 、jmp、jz char arg1[32]; char arg2[32]; char result[32]; } Quadruple; Quadruple quads[1000]; int quadCount 0; int emitQuad(char *op, char *arg1, char *arg2, char *result) { strcpy(quads[quadCount].op, op); strcpy(quads[quadCount].arg1, arg1); strcpy(quads[quadCount].arg2, arg2); strcpy(quads[quadCount].result, result); return quadCount; } void backpatch(int *list, int len, int target) { for (int i 0; i len; i) { sprintf(quads[list[i]].result, %d, target); } }逻辑说明emitQuad 生成一条四元式并返回索引。backpatch 把跳转指令的目标地址回填为指定索引。参数说明quads 数组大小 1000 足够课设规模如果程序较大可以改成动态数组。op 字段用字符串存储方便调试时打印。回填技术的关键是维护一个待回填列表记录所有需要回填的四元式索引。提示生成四元式时临时变量命名要统一比如 t1、t2、t3避免和用户变量冲突。可以在符号表里加一个临时变量计数器。5. 目标代码生成与寄存器分配把四元式翻译成可运行汇编5.1 从四元式到 x86 汇编的映射规则目标代码生成阶段把四元式翻译成汇编指令。南航课设一般要求生成 x86 汇编或 MIPS 汇编。我一般选 x86因为可以在本地用 gcc 直接汇编链接运行。映射规则很简单加法四元式 (, a, b, t1) 翻译成 mov eax, a; add eax, b; mov t1, eax。跳转四元式 (jmp, -, -, L1) 翻译成 jmp L1。条件跳转 (jz, a, -, L1) 翻译成 cmp a, 0; je L1。// codegen.c void generateAssembly() { for (int i 0; i quadCount; i) { Quadruple q quads[i]; if (strcmp(q.op, ) 0) { printf( mov eax, %s\n, q.arg1); printf( add eax, %s\n, q.arg2); printf( mov %s, eax\n, q.result); } else if (strcmp(q.op, -) 0) { printf( mov eax, %s\n, q.arg1); printf( sub eax, %s\n, q.arg2); printf( mov %s, eax\n, q.result); } else if (strcmp(q.op, *) 0) { printf( mov eax, %s\n, q.arg1); printf( imul eax, %s\n, q.arg2); printf( mov %s, eax\n, q.result); } else if (strcmp(q.op, jmp) 0) { printf( jmp L%s\n, q.result); } else if (strcmp(q.op, jz) 0) { printf( cmp %s, 0\n, q.arg1); printf( je L%s\n, q.result); } } }逻辑说明generateAssembly 遍历四元式数组根据操作符输出对应汇编指令。加减乘用 eax 作为累加器结果写回临时变量。跳转指令直接输出 jmp 或条件跳转。参数说明L%s 中的 result 字段存储跳转目标索引需要在汇编输出时加上 L 前缀避免和数字混淆。5.2 寄存器分配的简化策略与栈帧布局课设规模不大不需要复杂的图着色寄存器分配。我一般用最简单的策略所有变量都放在栈上每次运算把操作数加载到 eax计算完写回栈。这样虽然效率低但正确性容易保证。栈帧布局需要计算每个变量的偏移量通常从 ebp-4 开始每分配一个变量偏移减 4。// stack.c int stackOffset 0; int allocateStack(char *name) { stackOffset - 4; Symbol *s lookupSymbol(name, 0); if (s ! NULL) { s-offset stackOffset; } return stackOffset; } void generatePrologue() { printf( push ebp\n); printf( mov ebp, esp\n); printf( sub esp, %d\n, -stackOffset); } void generateEpilogue() { printf( mov esp, ebp\n); printf( pop ebp\n); printf( ret\n); }逻辑说明allocateStack 每分配一个变量就把栈偏移减 4并记录到符号表。generatePrologue 输出函数序言保存 ebp 并调整 esp。generateEpilogue 输出函数尾声恢复栈指针并返回。参数说明-stackOffset 是栈帧总大小因为 stackOffset 是负数取反得到正数。注意栈对齐问题x86 要求 esp 16 字节对齐可以在 sub esp 时向上取整到 16 的倍数。注意如果课设要求支持函数调用需要额外处理参数传递和返回值。参数通常压栈传递返回值放在 eax 中。6. 避坑与排查南航编译原理课设最容易翻车的五个地方6.1 词法分析器把关键字识别成标识符现象源程序里的 if、while 被当成普通变量名语法分析时报 unexpected token。原因词法分析器先匹配标识符规则没有优先匹配关键字。解决在识别出标识符后查关键字表如果命中则把 Token 类型改成 TOKEN_KEYWORD。关键字表可以用简单的字符串数组实现。6.2 递归下降分析器遇到左递归死循环现象程序运行后卡死CPU 占用 100%。原因文法中存在左递归比如 E - E T递归下降会无限展开。解决消除左递归把 E - E T | T 改成 E - T EE - T E | ε。改写后代码里 parseExpression 先调用 parseTerm再循环处理加减。6.3 符号表作用域退出时没有恢复层级现象内层作用域声明的变量在外层也能访问导致未声明变量检查失效。原因进入新作用域时增加了 scope 层级但退出时没有恢复。解决在解析块语句时进入块前保存当前 scope退出块后恢复。符号表查找时从当前 scope 向外逐层查找找到就返回。6.4 四元式回填时目标地址错误现象if 语句跳转到错误位置程序行为异常。原因回填列表维护错误或者回填时索引计算错误。解决每次生成跳转指令时把索引加入待回填列表回填时遍历列表把 result 字段改成目标四元式索引。建议在回填后打印四元式序列检查。6.5 目标代码生成时寄存器冲突现象生成的汇编运行结果和预期不符变量值被覆盖。原因多个四元式同时使用 eax没有保存中间结果。解决每个四元式执行完后把 eax 写回栈下一个四元式重新加载。如果课设要求优化可以引入简单的寄存器分配但正确性优先。7. 用测试用例驱动开发一个能跑通的最小验证流程课设最怕写完几千行代码才发现跑不通。我一般用测试用例驱动开发每完成一个阶段就写一个小测试验证。词法分析阶段用一段包含所有 Token 类型的源程序检查输出的 Token 序列是否正确。语法分析阶段用简单的表达式和语句检查 AST 结构。语义分析阶段故意写未声明变量检查是否报错。中间代码生成阶段用赋值和加法检查四元式序列。目标代码生成阶段把汇编代码保存成 .s 文件用 gcc 汇编链接后运行对比输出结果。# 编译并运行测试 gcc -o compiler main.c lexer.c parser.c semantic.c quad.c codegen.c ./compiler test.pas test.s gcc -m32 -o test test.s ./test echo $?逻辑说明先编译编译器本身然后对测试源程序生成汇编再用 gcc 汇编链接成可执行文件运行后检查退出码。参数说明-m32 表示生成 32 位代码因为课设一般用 32 位汇编。如果环境不支持 32 位可以改成 64 位汇编但寄存器名称和调用约定需要调整。我踩过最深的坑是符号表作用域没处理好导致内层变量覆盖外层变量调试了一整天才发现是退出块时忘了恢复 scope。后来养成习惯每写一个阶段就打印中间结果词法输出 Token 序列语法输出 AST语义输出符号表中间代码输出四元式。这样出问题能快速定位到具体阶段。希望帮到你。本文还有配套的精品资源点击获取