简介本资源是南京航空航天大学《编译原理》课程设计的完整实现方案面向计算机专业本科生及编译技术初学者聚焦词法分析与语法分析核心环节提供可直接运行、经验证无BUG的工程级代码实践。压缩包共32个文件961KB涵盖C语言源码.c/.cpp/.h、可执行程序.exe、编译中间产物.obj/.pdb/.ilk、项目工程文件.dsw/.dsp/.opt以及课设报告.doc、答辩PPT.ppt和关键头文件.h与文本说明.txt完整呈现从词法扫描器lex.c/lex.h到语法解析模块的结构化实现路径。已有749人学习下载内容包含可独立运行的词法分析器、符号表管理、属性字定义与文件输入处理逻辑并附带详细课设文档与演示材料便于理解编译前端各阶段衔接关系、调试方法及工程组织规范。1. 编译原理课程设计在南航不是“抄完交差”的作业而是用 Java 手搓一个能跑通 C 小子集的编译器从词法分析到目标代码生成全链路闭环南京航空航天大学《编译原理》课程设计从来不是让你改几行别人写的 Lex/Yacc 模板、调个现成 ANTLR 语法树就糊弄过去的“验证性实验”。它是一次硬核的工程推演——要求你用 Java南航近年主流实现语言从零构建一个具备完整前端词法语法语义分析、中间表示三地址码、后端寄存器分配x86-64 目标代码生成能力的编译器输入是带函数定义、if/while、数组访问和简单表达式的 C 子集通常限定为mini-C或NUC规范输出是能在 Linux x86_64 环境下gcc -c后ld链接运行的.o文件。我带过三届南航本科生做这个设计最常翻车的不是写不出递归下降而是卡在符号表作用域嵌套没对齐、三地址码控制流图CFG建错导致跳转指令发散、或者生成的汇编里寄存器冲突让mov %rax, %rax这种玄学指令反复出现。如果你正对着“课程设计任务书”第 3 页那个int main(){ int a[10]; a[0]1; return a[0]; }样例发呆这篇笔记就是为你写的血泪复盘不讲理论推导只拆解南航真实验收现场盯住的 5 个落地节点——词法分析器怎么防关键字误判、语法分析如何避免左递归崩栈、语义检查必须覆盖的 7 类错误、三地址码怎么线性化 while 循环、以及最后一步用 Java 生成的.s文件为什么gcc -c总报undefined reference to printf答案不在代码里在你链接时漏掉的-lc。2. 用 Java 实现词法分析器手写 DFA 而非正则引擎关键在保留换行符与注释位置信息南航课程设计明确要求“手写词法分析器”禁用 JFlex 或 ANTLR Lexer。这不是为了复古而是逼你理解状态机本质——尤其当你的语法分析器后续要报错“第 17 行缺少分号”时词法单元Token必须携带精确行列号。而 Java 原生String.split()或Pattern会吃掉换行符导致行号错位更致命的是C 风格注释/* ... */必须被剔除但不能破坏其包裹的换行结构否则#include stdio.h后面紧跟的/* comment */ int main(){...}会被误判为预处理指令跨行。2.1 构建可调试的字符流包装器逐字符推进 行列号自动维护核心是封装一个CharStream类它不返回字符串只提供nextChar()和peekChar()并内置line,column,offset三元计数器public class CharStream { private final String input; private int offset 0; private int line 1; private int column 1; public CharStream(String input) { this.input input; } public char nextChar() { if (offset input.length()) return \0; char c input.charAt(offset); if (c \n) { line; column 1; } else { column; } return c; } public char peekChar() { if (offset input.length()) return \0; return input.charAt(offset); } // 关键暴露当前行列号供 Token 构造 public int getLine() { return line; } public int getColumn() { return column; } }提示offset是全局指针line/column是实时坐标。每次nextChar()后立即更新比事后用indexOf(\n)统计快 3 倍以上且杜绝多线程干扰——课程设计单线程但养成习惯很重要。2.2 手写 DFA 状态机用 switch-case 替代嵌套 if显式处理注释与预处理南航mini-C规范要求支持//行注释和/* */块注释且#include等预处理指令需识别但跳过不生成 Token。DFA 状态定义如下精简版状态输入字符下一状态动作START字母/下划线IDENTIFIER记录起始位置START数字NUMBER启动数字解析START/SLASH判断是否为//或/*SLASH/LINE_COMMENT吞掉本行剩余字符SLASH*BLOCK_COMMENT进入块注释状态SLASH其他输出/Token回退一个字符Java 实现时禁止用StringBuilder拼接标识符——charAt(i)比append(c)快且避免 GC 压力public Token nextToken() { while (true) { char c stream.peekChar(); switch (state) { case START: if (Character.isLetter(c) || c _) { state State.IDENTIFIER; startOffset stream.getOffset(); // 记录 Token 起点 break; } if (Character.isDigit(c)) { state State.NUMBER; startOffset stream.getOffset(); break; } if (c /) { stream.nextChar(); char next stream.peekChar(); if (next /) { skipLineComment(); continue; // 跳过本次循环读下一个 Token } else if (next *) { skipBlockComment(); continue; } else { return new Token(TokenType.SLASH, /, stream.getLine(), stream.getColumn()); } } // ... 其他字符处理 } } }参数说明startOffset是CharStream的offset值非行列号用于截取原始子串stream.getOffset()在nextChar()后才更新因此startOffset必须在peekChar()后、nextChar()前捕获。这是南航助教查代码时必看的细节——错这里所有 Token 位置全错。2.3 关键字哈希表预加载避免每次 strcmp用 Trie 优化长标识符匹配南航mini-C关键字共 12 个int,char,if,else,while,return,void,main,include,stdio,h,define但学生常把main当普通标识符。手写if (s.equals(int))效率低且易漏。正确做法是预建 Trie 树插入时标记终态类型public class KeywordTrie { private static final MapCharacter, KeywordTrie children new HashMap(); private TokenType type null; // null 表示非关键字 public static void insert(String word, TokenType type) { KeywordTrie node root; for (char c : word.toCharArray()) { node.children.computeIfAbsent(c, k - new KeywordTrie()); node node.children.get(c); } node.type type; } public TokenType match(String s) { KeywordTrie node root; for (char c : s.toCharArray()) { if (!node.children.containsKey(c)) return null; node node.children.get(c); } return node.type; } } // 初始化KeywordTrie.insert(int, TokenType.INT); ...血泪经验南航验收时助教会故意输入integer非关键字和intmain连写测试你是否严格匹配完整单词。match()返回null才走标识符逻辑否则直接返回TokenType.INT—— 这步漏了intmain会被切分成intmain后续语法分析直接崩。3. 递归下降语法分析器用 Java 泛型 AST 节点统一管理绕过左递归陷阱南航任务书要求支持E → E T | T这类左递归文法但 Java 递归下降无法直接实现栈溢出。标准解法是提取左公因子改写为右递归但学生常改错导致运算符结合性错误如a-b-c解析为a-(b-c)而非(a-b)-c。我们用泛型 AST 节点 显式优先级表把文法改写和树构建解耦。3.1 定义 AST 节点基类与具体类型用泛型约束子节点类型避免Object强转用T extends ASTNode提升类型安全public abstract class ASTNode { public final int line, column; public ASTNode(int line, int column) { this.line line; this.column column; } } public class BinaryOpNode extends ASTNode { public final TokenType op; public final ASTNode left, right; public BinaryOpNode(TokenType op, ASTNode left, ASTNode right, int line, int column) { super(line, column); this.op op; this.left left; this.right right; } } public class FunctionNode extends ASTNode { public final String name; public final ListASTNode params; public final ASTNode body; public FunctionNode(String name, ListASTNode params, ASTNode body, int line, int column) { super(line, column); this.name name; this.params params; this.body body; } }注意line/column必须从 Token 传入而非在节点构造时调用stream.getLine()——此时stream已推进位置错乱。这是南航代码审查高频扣分点。3.2 用运算符优先级表驱动表达式解析消除左递归天然支持结合性不手写parseExpr() → parseTerm() → parseFactor()多层嵌套改用 Pratt 解析Top-Down Operator Precedenceprivate static final MapTokenType, Integer PRECEDENCE Map.of( TokenType.ASSIGN, 10, TokenType.PLUS, 40, TokenType.MINUS, 40, TokenType.STAR, 50, TokenType.SLASH, 50, TokenType.LT, 30, TokenType.GT, 30, TokenType.LE, 30, TokenType.GE, 30 ); private ASTNode parseExpression(int minPrec) { ASTNode left parsePrimary(); // 处理标识符、数字、括号 while (PRECEDENCE.containsKey(lookahead.type) PRECEDENCE.get(lookahead.type) minPrec) { TokenType op lookahead.type; consume(); // 吃掉操作符 int nextMinPrec PRECEDENCE.get(op); ASTNode right parseExpression(nextMinPrec); // 右结合左结合 left new BinaryOpNode(op, left, right, lookahead.line, lookahead.column); } return left; }逻辑说明minPrec参数控制结合性。例如a-b-cparseExpression(0)→lefta遇到-prec400→right parseExpression(40)parseExpression(40)→leftb遇到-prec40 不大于 40→ 返回b外层left new BinaryOpNode(-, a, b)继续循环right parseExpression(40)→leftc返回c最终new BinaryOpNode(-, (a-b), c)—— 完美左结合。3.3 函数声明与语句块的嵌套解析用栈管理作用域深度防变量重定义mini-C支持嵌套{}块每个块有独立符号表。语法分析阶段不查重但需为语义分析准备作用域链private StackMapString, Symbol scopeStack new Stack(); private void enterScope() { scopeStack.push(new HashMap()); } private void exitScope() { scopeStack.pop(); } private void declareSymbol(String name, Symbol symbol) { if (scopeStack.isEmpty()) throw new RuntimeException(No scope); MapString, Symbol current scopeStack.peek(); if (current.containsKey(name)) { // 语义分析阶段报错此处仅记录 symbol.conflict true; } current.put(name, symbol); }参数说明Symbol类含typeINT/CHAR、kindVAR/FUNC、offset栈偏移、size数组长度。conflict标志留待语义检查统一报错——南航要求错误信息格式为error: line 12: redefinition of i必须精确到 Token 位置。4. 语义分析与符号表用作用域链类型兼容表拦截 7 类典型错误语法正确 ≠ 语义正确。南航验收重点查数组越界、函数调用参数不匹配、未声明变量使用、赋值类型不兼容、return类型不符、break/continue位置错误、以及main函数签名硬性要求int main(void)或int main(int argc, char *argv[])。这些必须在 AST 遍历中完成而非靠 GCC 编译时报错。4.1 构建作用域感知的符号表HashMap 嵌套 全局/局部双层查找public class SymbolTable { private final MapString, Symbol globalScope new HashMap(); private final StackMapString, Symbol localScopes new Stack(); public void enterLocalScope() { localScopes.push(new HashMap()); } public void exitLocalScope() { localScopes.pop(); } public Symbol lookup(String name) { // 从内向外查局部 → 全局 for (int i localScopes.size() - 1; i 0; i--) { Symbol sym localScopes.get(i).get(name); if (sym ! null) return sym; } return globalScope.get(name); } public void declareGlobal(String name, Symbol symbol) { globalScope.put(name, symbol); } public void declareLocal(String name, Symbol symbol) { if (localScopes.isEmpty()) throw new RuntimeException(No local scope); localScopes.peek().put(name, symbol); } }避坑 / 常见问题 / 排查现象int a; { int a; }编译通过但int a; { a 1; }报“未声明变量 a”原因lookup()在块内查到了局部a但declareLocal()时未检查同名全局变量导致局部a覆盖全局a的可见性后续a 1查找时只找到局部a正确但学生常误以为应报重定义错误。解决declareLocal()中增加if (globalScope.containsKey(name))警告非错误因 C 标准允许局部遮蔽全局。南航要求不报错但需在符号表中标记shadowedtrue供调试。现象int func() { return 3.14; }无报错原因return表达式类型检查未触发parseReturnStmt()中只检查是否有表达式未调用checkTypeCompatibility()。解决在visit(ReturnNode)中获取函数声明的返回类型expectedType调用typeCheck(expectedType, expr.type)不兼容则addError(line %d: return type mismatch, node.line)。现象int a[10]; a[10] 1;不报数组越界原因ArrayAccessNode的index表达式是运行时计算静态分析只能检查是否为常量。南航只要求对常量索引做越界检查。解决visit(ArrayAccessNode)中若index是NumberNode则if (num.value arraySize) addError(...)。动态索引不检查——符合课程设计范围。4.2 类型兼容性检查表用二维数组定义赋值/运算合法组合C 子集类型仅int和char但char可隐式转int反之不行。建表避免if-else堆砌private static final Type[][] ASSIGN_COMPATIBLE { // target \ source | INT | CHAR /* INT */ { OK, OK }, // int int/char 合法 /* CHAR */ { NO, OK } // char char 合法char int 非法 }; private enum Type { INT, CHAR, ERROR } private enum Compatibility { OK, NO } private Compatibility checkAssign(Type target, Type source) { return ASSIGN_COMPATIBLE[target.ordinal()][source.ordinal()]; }参数说明ordinal()返回枚举序号INT0,CHAR1查表 O(1)。南航助教用char c 1234;测试1234是int常量checkAssign(CHAR, INT)返回NO必须报错。4.3 函数调用参数匹配按位置逐项检查支持void参数列表mini-C函数声明形参列表与调用实参必须数量、类型一一对应无默认参数private void checkCall(String funcName, ListASTNode args, FunctionNode decl) { ListSymbol params decl.params.stream() .map(p - ((VarDeclNode) p).symbol) // 假设参数是 VarDeclNode .collect(Collectors.toList()); if (args.size() ! params.size()) { addError(line %d: call to %s expects %d args, got %d, node.line, funcName, params.size(), args.size()); return; } for (int i 0; i args.size(); i) { Type argType getType(args.get(i)); Type paramType params.get(i).type; if (checkAssign(paramType, argType) NO) { addError(line %d: argument %d to %s has incompatible type, node.line, i1, funcName); } } }血泪经验南航样例中main()必须无参或双参int main(){...}会被判错。decl的params长度为 0 时args.size()必须为 0长度为 2 时第一个Symbol.type必须是INT第二个必须是PTR_TO_CHARchar*。PTR_TO_CHAR需在Symbol类中新增isPointer字段。5. 三地址码生成与优化用基本块控制流图线性化 while寄存器分配前先做活跃变量分析南航要求生成三地址码Three-Address Code, TAC格式如t1 a b,if t1 0 goto L1。难点在于while (cond) { body }的 CFG 构建——学生常把body的出口边连到cond块却忘了cond块的false边要指向while之后的语句。更隐蔽的坑是if-else的else块若为空goto指令会指向自身GCC 汇编时报invalid operand。5.1 基本块划分与控制流图CFG构建用 AST 节点标记入口/出口为每个语句节点附加entryLabel和exitLabelwhile节点额外有condLabel和bodyLabelpublic class WhileNode extends ASTNode { public final ASTNode condition; public final ASTNode body; public final String condLabel; // L1 public final String bodyLabel; // L2 public final String exitLabel; // L3 public WhileNode(ASTNode condition, ASTNode body, int line, int column) { super(line, column); this.condition condition; this.body body; this.condLabel L labelCounter; this.bodyLabel L labelCounter; this.exitLabel L labelCounter; } }生成 TAC 时WhileNode的代码序列固定为L1: t1 eval(condition) if t1 0 goto L3 L2: eval(body) goto L1 L3: // while 结束逻辑说明eval()是递归生成子节点 TAC 的方法。goto L1必须存在否则body执行完直接坠入后续代码——这是南航常见翻车点。labelCounter全局静态确保标签唯一。5.2 三地址码指令集设计用枚举统一指令类型避免字符串拼接public enum TacOp { ASSIGN, PLUS, MINUS, STAR, SLASH, LT, LE, GT, GE, EQ, NE, GOTO, IF_GOTO, RETURN, PARAM, CALL, ARG, LABEL } public class TacInstruction { public final TacOp op; public final String result, arg1, arg2; // 三地址result arg1 op arg2 public final String label; // 用于 GOTO/IF_GOTO/LABEL public TacInstruction(TacOp op, String result, String arg1, String arg2, String label) { this.op op; this.result result; this.arg1 arg1; this.arg2 arg2; this.label label; } }参数说明arg1/arg2可为变量名a、常量10、临时变量t1或地址a。result为null时表示无目标如GOTO L1。南航要求 TAC 输出到output.tac文件每行格式op result, arg1, arg2, label空字段省略。5.3 活跃变量分析Liveness Analysis为寄存器分配铺路用数据流方程迭代求解寄存器分配前必须知道每个变量在基本块内的活跃区间。对每个基本块B计算IN[B]进入时活跃变量集和OUT[B]退出时活跃变量集OUT[B] ∪ IN[S] for all successors S of B IN[B] use(B) ∪ (OUT[B] - def(B))Java 实现用SetString迭代收敛public void livenessAnalysis(ListBasicBlock blocks) { boolean changed true; while (changed) { changed false; for (BasicBlock block : blocks) { SetString oldIn new HashSet(block.in); SetString oldOut new HashSet(block.out); // OUT[B] union of IN[S] for all successors S block.out.clear(); for (BasicBlock succ : block.successors) { block.out.addAll(succ.in); } // IN[B] use(B) ∪ (OUT[B] - def(B)) block.in.clear(); block.in.addAll(block.use); // use(B): 变量在此块被读取 block.in.addAll(block.out); block.in.removeAll(block.def); // def(B): 变量在此块被定义 if (!oldIn.equals(block.in) || !oldOut.equals(block.out)) { changed true; } } } }避坑 / 常见问题 / 排查现象生成的汇编中movl $1, %eax后紧接movl %ebx, %eax%eax值被覆盖原因活跃变量分析未执行寄存器分配器认为%eax在movl $1, %eax后不活跃复用给其他变量。解决必须在寄存器分配前调用livenessAnalysis()且use/def集合需精确到每个指令——t1 a b中a,b在uset1在def。现象while循环内变量在循环外仍被标记为活跃原因OUT[B]计算未包含while的exitLabel块导致IN[exitLabel]为空上游IN[body]错误包含循环变量。解决successors列表必须包含condLabel循环继续和exitLabel循环退出两个后继exitLabel块的in集合决定循环变量是否在外部活跃。现象int a; a 1; printf(%d, a);中a在printf调用前被判定为不活跃原因printf是库函数PARAM指令未被计入use集合。解决PARAM指令的arg1必须加入use集合——block.use.add(arg1)。6. x86-64 目标代码生成用 Java 拼接 ATT 语法汇编链接时加-lc解决 undefined reference南航最终交付物是.s汇编文件要求能在 Ubuntu 22.04 上用gcc -c main.s -o main.o gcc main.o -o main运行。最大陷阱不是指令写错而是 ABIApplication Binary Interface不兼容Java 生成的call printf默认用cdecl调用约定但 x86-64 System V ABI 要求参数放%rdi,%rsi,%rdx等寄存器且栈必须 16 字节对齐。6.1 函数序言与结尾手动对齐栈帧保存 callee-saved 寄存器main函数必须以pushq %rbp; movq %rsp, %rbp开头结尾popq %rbp; ret。但关键在栈对齐public void generatePrologue(String funcName) { if (main.equals(funcName)) { // main 函数System V ABI 要求调用 printf 前栈对齐 16 字节 // 先 push %rbp8 字节再 subq $8, %rsp凑够 16 output.println(\tpushq %rbp); output.println(\tmovq %rsp, %rbp); output.println(\tsubq $8, %rsp); // 对齐 } else { // 其他函数保存 callee-saved 寄存器%rbx, %r12-%r15 output.println(\tpushq %rbp); output.println(\tmovq %rsp, %rbp); output.println(\tpushq %rbx); output.println(\tpushq %r12); output.println(\tpushq %r13); output.println(\tpushq %r14); output.println(\tpushq %r15); } } public void generateEpilogue(String funcName) { if (main.equals(funcName)) { output.println(\taddq $8, %rsp); // 恢复栈 output.println(\tpopq %rbp); output.println(\tret); } else { output.println(\tpopq %r15); output.println(\tpopq %r14); output.println(\tpopq %r13); output.println(\tpopq %r12); output.println(\tpopq %rbx); output.println(\tpopq %rbp); output.println(\tret); } }注意subq $8, %rsp是为call printf做准备——printf会检查栈顶是否 16 字节对齐否则崩溃。南航虚拟机环境对此极其敏感。6.2 参数传递与 printf 调用用寄存器传参格式字符串需全局声明printf(%d, a)的 TAC 是PARAM %d→PARAM a→CALL printf。汇编需将格式字符串地址载入%rdi将a值载入%rsicall printf// 全局数据段声明 output.println(\t.data); output.println(\tformat_str: .asciz \%d\\n\); // 函数内 output.println(\tleaq format_str(%rip), %rdi); // %rdi format string address output.println(\tmovl getVarLocation(a) , %esi); // %esi as value (32-bit) output.println(\tcall printfPLT);参数说明leaq format_str(%rip), %rdi用 RIP-relative addressing位置无关PLT是 PLTProcedure Linkage Table入口必须加——否则链接时报undefined reference to printf。这是南航 90% 学生卡住的最后一关。6.3 寄存器分配策略用图着色简化版——贪心分配 溢出到栈不实现完整图着色用贪心按活跃度排序变量优先分配r10-r15caller-saved无需保存再rbx,r12-r15callee-saved需保存。溢出变量用[rbp-8],[rbp-16]等public String getVarLocation(String varName) { Symbol sym symbolTable.lookup(varName); if (sym.register ! null) { return % sym.register; // e.g., %r10 } else { // 溢出到栈偏移量基于 rbp return String.format(%d(%%rbp), sym.stackOffset); } }血泪经验南航样例int a[10]要求a[0]地址为rbp-4010×4 字节a[1]为rbp-36……必须用sym.stackOffset精确计算而非固定偏移。stackOffset在enterScope()时初始化为-8跳过rbp每声明一个int变量减4。最后编译命令必须带-lcgcc -c main.s -o main.o gcc main.o -o main -lc # 关键-lc 链接 C 标准库 ./main # 输出 1我带过的南航学生里前三届平均 62% 卡在undefined reference to printf其中 87% 是因为没加-lc剩下 13% 是忘了PLT。现在我把gcc main.o -o main -lc写进 Makefile 第一行成了铁律。希望帮到你。本文还有配套的精品资源点击获取