尧图网页设计 
简介这是南京航空航天大学编译原理课程设计全套方案面向计算机专业本科生及编译原理初学者覆盖词法分析与语法分析两大核心模块程序均经检验无BUG可直接运行验证帮助梳理编译器前端构建流程。压缩包共32个文件体积约961KB包含C/C与头文件源码、可执行程序、课程设计报告与答辩PPT以及配套文本材料从代码到汇报都一应俱全。词法分析与语法分析分别提供独立可执行版本可对照运行观察识别、解析过程报告与PPT同时可作为课程报告写作和答辩演练的参考。已有749人学习下载特别适合准备课设答辩或系统复习词法识别、递归下降等实现细节的计算机专业学生。1. 编译原理课程设计的真相不写编译器这门课就白学了很多人把编译原理当成一门“玄学”课教材翻完考试过了但你问他“编译器到底怎么把printf(hello)变成机器码”他只能支支吾吾。南京航空航天大学把这门课配上课程设计目的就是逼你亲手做一个能跑的小编译器哪怕只支持一个子集语言。课程设计不是让你复述龙书里的算法而是让你从词法、语法、语义到代码生成完整走一遍编译器前端和后端的核心链路。适合谁适合想搞清“编译器黑匣子”里到底装了什么的学生也适合工作后想转编译器方向、需要一份拿得出手项目经历的从业者。这篇笔记会按照做课程设计最常见的路径把设计取舍、关键代码、调试方法和踩坑点讲透让你照着能做出来而不是停留在概念层。2. 选定一个能完工的语言子集从文法到错误处理的设计取舍课程设计最忌讳“什么都想做”。你不可能在半个学期里写出一个标准C编译器也没人指望你做到GCC那个程度。关键是选一个“小而完整”的语言子集把它从源码到中间代码/目标代码的整条流水线打通。这个选择和你的文法定义直接绑定后面所有代码都围绕这套文法展开。2.1 语言子集怎么定南航历年题目里最常见的范围以南京航空航天大学历年课程设计题目为例最常见的做法是选择C语言的子集通常包含以下内容变量声明int和char、float以及简单数组一维下标为常量或变量表达式四则运算、取负、括号、比较运算、逻辑与或非语句赋值、if、while、for可选、read/write以及复合语句{ }函数最多支持无返回值或单返回值的函数不搞重载和指针。我建议把“函数”放进去哪怕只做一个主函数。因为课程设计的评分点通常包括符号表管理和中间代码生成没有函数符号表的作用域设计就看不出水平。但不要做嵌套函数、函数指针这类东西否则递归下降分析器会复杂到失控。文法定义建议用EBNF而非纯BNF。EBNF里的[ ]和{ }能减少左递归也让递归下降程序写起来更直观。下面是一个经过裁减的表达式和语句的文法骨架program - { function } function - type ID ( ) compound_stmt compound_stmt - { { local_decl | stmt } } local_decl - type ID [ expr ] ; stmt - if_stmt | while_stmt | read_stmt | write_stmt | ID expr ; | compound_stmt if_stmt - if ( expr ) stmt [ else stmt ] while_stmt - while ( expr ) stmt expr - add_expr [ ( | | | !) add_expr ] add_expr - mul_expr { ( | -) mul_expr } mul_expr - unary_expr { (* | /) unary_expr } unary_expr - (- | !) unary_expr | primary primary - INT_NUM | STRING | ID | ( expr )注意我故意把for排除了。为什么因为for在语法分析上只是while加个初始化语句代码生成却要额外处理continue标签。第一次做课程设计控制语句越少越能把语义分析和代码生成的逻辑做干净。等主体跑通了再自己加for也不迟。还有一个容易被低估的设计点是注释支持。很多学生开始时忘了注释程序一读带注释的测试就往崩溃。语法上预留//和/* */的跳过逻辑词法分析器里多写10行代码后面省一天调试时间。2.2 手写词法分析器和递归下降还是上Flex/Bison这是每个做课程设计的人都要面对的卡点。我的建议很明确语法分析器必须手写递归下降词法分析器可以手写也可以用工具。理由有三手写递归下降能让你真正理解文法和程序控制流的对应关系。expr - term { (|-) term }对应函数里一个while循环这种映射只有亲手写一遍才刻进脑子。Bison的LALR冲突解决对新手很不友好。如果你定义C子集文法else悬挂、表达式优先级、左递归都要处理Bison会给一堆shift/reduce冲突看不懂就去网上找答案结果别人的文法和你又不完全一样非常浪费时间。课程设计答辩时老师大概率会问你“递归下降遇到左递归怎么办”“你的FIRST集合怎么算的”。手写版你能当场答上来因为每个函数都是你自己写的。用工具生成反而容易一问三不知。词法分析器方面如果你对正则表达式和状态机足够熟练可以用Flex。但说实话一个支持关键字、标识符、数字、字符串、注释和运算符的词法分析器手写也就200-300行。而且手写词法能做到报错信息里带行列号Flex默认的错误信息不够友好。如果你非要用工具建议FlexBison但要把它们的代码生成选项弄明白Flex里yylex返回的token编号要和Bison里%token编号一致操作符优先级靠%left声明。下面用一个小例子说明Flex和Bison配合的最小骨架。先看Flex文件%{ #include y.tab.h #include stdio.h extern int yylval; %} %% [0-9] { yylval atoi(yytext); return NUMBER; } [a-zA-Z_][a-zA-Z0-9_]* { yylval yytext[0]; return ID; } { return PLUS; } - { return MINUS; } * { return TIMES; } / { return DIVIDE; } { return ASSIGN; } [ \t\n] ; . { fprintf(stderr, unexpected char: %s\n, yytext); } %%Bison文件里这样声明优先级%token NUMBER ID %left PLUS MINUS %left TIMES DIVIDE %% expr : expr PLUS expr | expr MINUS expr | expr TIMES expr | expr DIVIDE expr | NUMBER | ID ; %%这里的%left顺序尤为重要越在后面声明的运算符优先级越高。PLUS MINUS在前符合数学上加减比乘除低一级的约定。Bison会利用这个声明解决表达式文法的shift/reduce冲突不让它在12*3里产生歧义。编译时用bison -d parser.y生成y.tab.h然后flex lexer.l最后把lex.yy.c和y.tab.c一起编译。注意Flex生成的yylex默认符号表在yy.tab.h里声明如果你的C代码里提前引用了NUMBER必须先包含这个头文件。但如果你选手写路线可以考虑用Python或C。Python代码短、调试快适合第一个版本C多写一些类但最终性能更好。我在实际做课程设计时第一版用Python把整个流程跑通然后用C重写重写速度比直接写C快很多因为逻辑已经在Python里验证过了。下面正式进入实现环节。3. 词法与语法分析落地手写递归下降与构建AST的两种可行方案这一章解决从源代码流到抽象语法树AST的问题。我会先给出手写词法分析器的完整思路再给出递归下降语法分析器的核心代码框架最后说明AST怎么设计才不会在后面语义分析和三地址码生成时后悔。3.1 手写一个带行列号的词法分析器状态机与前进指针词法分析器的本质是“读下一个token”。但实际实现时很多人栽在“回退”和“越界”上。我习惯用一个结构体保存当前读到的字符缓冲区并维护行号和列号。下面的C代码展示了一个简化版词法分析器的核心结构它识别数字、标识符、关键字、运算符和字符串。enum TokenType { TK_ID, TK_INT, TK_FLOAT, TK_STRING, TK_PLUS, TK_MINUS, TK_TIMES, TK_DIVIDE, TK_ASSIGN, TK_EQ, TK_NEQ, TK_LT, TK_GT, TK_IF, TK_ELSE, TK_WHILE, TK_READ, TK_WRITE, TK_LPAREN, TK_RPAREN, TK_LBRACE, TK_RBRACE, TK_SEMI, TK_EOF }; struct Token { TokenType type; std::string text; int line; int col; }; class Lexer { public: explicit Lexer(const std::string src) : src(src), pos(0), line(1), col(1) {} Token next() { skipWhitespaceAndComments(); if (pos src.size()) return makeToken(TK_EOF, EOF); char ch peek(); if (isdigit(ch)) return readNumber(); if (isalpha(ch) || ch _) return readIdentifierOrKeyword(); return readOperator(); } private: std::string src; size_t pos; int line; int col; char peek(size_t ahead 0) const { size_t idx pos ahead; return idx src.size() ? src[idx] : \0; } void advance() { if (peek() \n) { line; col 1; } else { col; } pos; } Token makeToken(TokenType type, const std::string text) { Token t; t.type type; t.text text; t.line line; t.col col; return t; } void skipWhitespaceAndComments() { while (pos src.size()) { char ch peek(); if (ch || ch \t || ch \r || ch \n) { advance(); } else if (ch / peek(1) /) { while (pos src.size() peek() ! \n) advance(); } else if (ch / peek(1) *) { advance(); advance(); while (pos src.size() !(peek() * peek(1) /)) advance(); advance(); advance(); } else break; } } Token readNumber() { std::string text; while (isdigit(peek())) { text peek(); advance(); } return makeToken(TK_INT, text); } Token readIdentifierOrKeyword() { std::string text; while (isalnum(peek()) || peek() _) { text peek(); advance(); } static const std::unordered_mapstd::string, TokenType keywords { {if, TK_IF}, {else, TK_ELSE}, {while, TK_WHILE}, {read, TK_READ}, {write, TK_WRITE} }; auto it keywords.find(text); return makeToken(it ! keywords.end() ? it-second : TK_ID, text); } Token readOperator() { char ch peek(); std::string text(1, ch); advance(); if ((ch peek() ) || (ch ! peek() ) || (ch peek() ) || (ch peek() )) { text peek(); advance(); if (text ) return makeToken(TK_EQ, text); if (text !) return makeToken(TK_NEQ, text); if (text ) return makeToken(TK_LE, text); if (text ) return makeToken(TK_GE, text); } else if (ch ) { return makeToken(TK_LT, text); } else if (ch ) { return makeToken(TK_GT, text); } switch (ch) { case : return makeToken(TK_PLUS, text); break; case -: return makeToken(TK_MINUS, text); break; case *: return makeToken(TK_TIMES, text); break; case /: return makeToken(TK_DIVIDE, text); break; case : return makeToken(TK_ASSIGN, text); break; case (: return makeToken(TK_LPAREN, text); break; case ): return makeToken(TK_RPAREN, text); break; case {: return makeToken(TK_LBRACE, text); break; case }: return makeToken(TK_RBRACE, text); break; case ;: return makeToken(TK_SEMI, text); break; default: throw std::runtime_error(unknown char text at line std::to_string(line) col std::to_string(col)); } } };这段代码有几个关键设计。peek和advance是词法分析器的两个基本操作peek负责看当前或后续字符但不移动指针advance负责移动指针并更新行列号。skipWhitespaceAndComments把所有空白和注释吞掉注释支持//和/* */。readOperator里用了二级判断先读第一个字符再看第二个字符能不能组成双字符运算符。这里有个容易踩的坑识别时如果第二个字符不是比如遇到后面跟空白必须把指针停留在正确位置。我的实现是advance()先吃掉一个字符然后peek()读第二个如果不是配对字符其实已经多吃了一个需要回退。但我这里用了一个技巧先text peek(); advance();此时指针已经到第二个字符。如果发现不是双字符必须把pos回退一格同时col减一。上面代码简化了这种情况实际上你需要一个unadvance()操作。很多课程设计失败就失败在这个小细节。我在代码里没有写回退但实际实现时一定要加void unadvance() { if (pos 0) { pos--; char prev src[pos]; if (prev \n) { line--; /* col需恢复到上一行末尾建议保存一行快照 */ } else { col--; } } }更稳妥的办法是读到一个操作符时先用peek(0)和peek(1)判断组合再一次性advance两格避免回退。这样做就不会有“吃多”的问题。3.2 递归下降语法分析器每个文法产生式对应一个函数有了token流语法分析器就可以开始工作。递归下降的核心思想是为每个非终结符写一个函数函数内部按照产生式的右端逐个匹配终结符或调用其他非终结符函数。下面是一个简化版的Expr、Term和Stmt函数class Parser { public: explicit Parser(Lexer lexer) : lexer(lexer) { cur lexer.next(); } void parseProgram() { while (cur.type ! TK_EOF) { parseFunction(); } } private: Lexer lexer; Token cur; void advance() { cur lexer.next(); } bool check(TokenType type) { return cur.type type; } bool match(TokenType type) { if (check(type)) { advance(); return true; } return false; } void expect(TokenType type, const std::string msg) { if (!check(type)) { throw std::runtime_error(msg at line std::to_string(cur.line) col std::to_string(cur.col) , got cur.text); } advance(); } void parseFunction() { expect(TK_INT, expected int); expect(TK_ID, expected function name); expect(TK_LPAREN, expected (); expect(TK_RPAREN, expected )); parseCompoundStmt(); } void parseCompoundStmt() { expect(TK_LBRACE, expected {); while (!check(TK_RBRACE) !check(TK_EOF)) { if (cur.type TK_INT) { parseDeclaration(); } else { parseStmt(); } } expect(TK_RBRACE, expected }); } void parseDeclaration() { expect(TK_INT, expected int); expect(TK_ID, expected variable name); if (match(TK_ASSIGN)) { parseExpr(); } expect(TK_SEMI, expected ; after declaration); } void parseStmt() { if (check(TK_IF)) { advance(); expect(TK_LPAREN, expected ( after if); parseExpr(); expect(TK_RPAREN, expected ) after if condition); parseStmt(); if (match(TK_ELSE)) { parseStmt(); } } else if (check(TK_WHILE)) { advance(); expect(TK_LPAREN, expected ( after while); parseExpr(); expect(TK_RPAREN, expected ) after while condition); parseStmt(); } else if (check(TK_ID)) { advance(); expect(TK_ASSIGN, expected in assignment); parseExpr(); expect(TK_SEMI, expected ; after assignment); } else if (check(TK_LBRACE)) { parseCompoundStmt(); } else { throw std::runtime_error(unexpected token at line std::to_string(cur.line) col std::to_string(cur.col)); } } void parseExpr() { parseAddExpr(); if (check(TK_GT) || check(TK_LT)) { advance(); parseAddExpr(); } } void parseAddExpr() { parseMulExpr(); while (check(TK_PLUS) || check(TK_MINUS)) { advance(); parseMulExpr(); } } void parseMulExpr() { parseUnaryExpr(); while (check(TK_TIMES) || check(TK_DIVIDE)) { advance(); parseUnaryExpr(); } } void parseUnaryExpr() { if (check(TK_MINUS) || check(TK_NOT)) { advance(); parseUnaryExpr(); } else { parsePrimary(); } } void parsePrimary() { if (check(TK_INT)) { advance(); } else if (check(TK_ID)) { advance(); } else if (check(TK_LPAREN)) { advance(); parseExpr(); expect(TK_RPAREN, expected ) after expression); } else { throw std::runtime_error(unexpected token in primary at line std::to_string(cur.line)); } } };这段代码里有一个很关键的约定每个parse函数在调用时当前token已经被读好函数负责“消耗”自己所需的token。比如parseExpr先调用parseAddExpr然后如果看到比较运算符就继续读右操作数。这个“当前token全局唯一”的设计避免了回溯代价是程序设计必须严格符合文法。如果你写的文法有公共左因子递归下降就会出问题。比如stmt - IF ( expr ) stmt ELSE stmt | WHILE ( expr ) stmt这两个产生式开头不同所以没有冲突。如果遇到相同开头比如stmt - ID ASSIGN expr和stmt - ID LPAREN args RPAREN必须提取左因子否则无法确定该选哪条。上面的parseStmt里对if的处理有一个细节当if (match(TK_ELSE))时parseStmt会再递归地分析else分支。这实际上实现了“else就近匹配”。但如果不加花括号else可能会错误地匹配到内部的if上这就是经典的“悬挂else”问题。标准做法是在文法里强制stmt要么是复合语句要么是简单语句且else必须出现在复合语句前。但简单起见我建议在课程设计说明里就要求用户写if (x) { ... } else { ... }这样parseStmt里不会产生歧义。3.3 构建AST用std::variant还是继承体系语法分析的过程中直接生成三地址码是一种选项但更清晰的课程设计路径是先构建AST再遍历AST生成中间代码。AST的节点设计要覆盖表达式、语句、声明和整个程序。在C里常见有两种AST设计方式。一种是经典虚函数继承struct Node { virtual ~Node() default; }; struct Expr : Node { virtual ~Expr() default; }; struct IntLit : Expr { int value; IntLit(int v) : value(v) {} }; struct BinOp : Expr { Expr* lhs; Expr* rhs; int op; }; struct AssignStmt : Node { std::string name; Expr* value; };另一种是现代C的std::variant更安全但访问时需要写std::visit。考虑到答辩时老师可能会指着AST问“你如何区别不同节点”继承体系更直观。建议每个节点都保存line和col哪怕只用于报错也能省很多查错时间。AST构建需要修改上述parse函数让每个函数返回节点指针。比如Expr* parseExpr() { Expr* left parseAddExpr(); if (check(TK_LT) || check(TK_GT)) { Token op cur; advance(); Expr* right parseAddExpr(); return new BinOp(left, right, op.type); } return left; }这里注意if条件只处理了LT和GT如果你扩展和!还要在check里加入TK_EQ和TK_NEQ。每个运算符节点要保存运算符的token类型这样后面生成三地址码时可以直接switch。有一个很重要的工程习惯AST节点用指针后一定要设计统一的析构机制否则内存泄漏。最简单的方式是用std::unique_ptr。但如果为了代码可读性裸指针加上在Parser析构函数里统一delete也可以接受。课程设计的代码量不大只要不每次parse都new几十个节点却不解构答辩时内存泄漏不会被细究。但如果你在同一个测试程序里反复解析多个文件泄漏会让程序越跑越慢甚至崩掉。4. 语义分析与中间代码生成符号表、类型检查和三地址码的配合语法分析只检查“结构对不对”不检查“合不合理”。int x y 1;如果y没声明或者y是字符串语法上完全合法语义上却要报错。这一章把符号表和中间代码生成讲透这部分通常是课程设计评分最高的模块。4.1 符号表怎么设计作用域链与重定义检测符号表需要支持嵌套作用域。最简单的实现是“栈哈希表”两层结构。全局符号表保存函数名和全局变量每个复合语句进入时压入一个新作用域退出时弹出。struct Symbol { std::string name; std::string type; // int, char, float, array int arraySize; // 0表示非数组 int line; int col; int scope; }; class SymbolTable { public: void enterScope() { scopes.emplace_back(); } void exitScope() { scopes.pop_back(); } bool insert(const Symbol sym) { auto current scopes.back(); if (current.find(sym.name) ! current.end()) { return false; // 重定义 } current[sym.name] sym; return true; } const Symbol* lookup(const std::string name) { for (auto it scopes.rbegin(); it ! scopes.rend(); it) { auto found it-find(name); if (found ! it-end()) { return found-second; } } return nullptr; } private: std::vectorstd::unordered_mapstd::string, Symbol scopes; };这里有个容易忽略的点lookup要从最内层向外找。比如在{ int x; { x 1; } }中内层的x如果没声明应该找到外层的x。这个链式查找是作用域的关键也是老师最爱问的问题。insert只往当前作用域插如果当前作用域已有同名符号说明是重定义直接报错。数组的符号要额外存arraySize。如果你实现了下标访问AST里需要增加ArrayIndexExpr节点。语义分析时除了检查数组名还要检查下标是否为整数类型以及下标范围是否越界。不过课程设计通常不要求运行时数组越界检查因为静态分析只能查常量越界变量下标只能留给生成代码后运行时检查。如果要做得更完整可以在生成的三地址码里插入if (idx size) error代码。4.2 类型检查隐式转换要不要支持课程设计的测试用例里很可能出现int a; float b; a b;。如果完全不支持类型转换写起来简单但测试时容易被人故意恶心。常见做法是支持int和float两种类型int赋值给float自动转float赋值给int时给出警告并在生成的代码里截断。这样既不过分复杂又显得你考虑周到了。类型检查的“检查规则表”应该提前列出来运算左操作数类型右操作数类型结果类型 - * /intintint - * /floatfloatfloat - * /intfloatfloat !任意同左int变量类型表达式类型无具体实现时在AST节点上增加一个type字段。计算表达式时递归地返回结果类型。比如BinOp的getType()会先取左右子节点类型若左右都是int则结果为int若任一为float则结果为float。比较运算的结果统一为int1表示真0表示假。赋值语句检查左值类型和右值类型是否可转换如果左值是int而右值是float报错或警告。在语义分析阶段常见的做法是写一个SemanticAnalyzer类继承AST访问者模式。因为AST节点种类不多简单用switch遍历也行。下面演示一个visitBinOp的类型检查片段std::string visitBinOp(BinOp* node) { std::string lhs visitExpr(node-lhs); std::string rhs visitExpr(node-rhs); if (node-op TK_PLUS || node-op TK_MINUS || node-op TK_TIMES || node-op TK_DIVIDE) { if (lhs float || rhs float) { node-type float; } else { node-type int; } } else if (node-op TK_LT || node-op TK_GT || node-op TK_EQ || node-op TK_NEQ) { if (lhs ! rhs) { reportError(comparison of different types); } node-type int; } return node-type; }注意算术运算中int和float混用在生成三地址码时需要插入一条INT_TO_FLOAT指令否则汇编代码里两个不同类型的数无法直接相加。很多学生在这步忘记插入转换指令导致生成的目标代码在运行时计算结果不对。如果是生成自己的虚拟机指令也要在指令集里设计一条itof。4.3 三地址码生成的两种模式直接递归和显式临时变量三地址码TAC是中间代码的常见形式每条指令至多包含三个地址操作数或目标。课程设计通常选择它因为后面解释执行或翻译成汇编都很方便。生成TAC时我为每个表达式分配一个临时变量。例如表达式a b * c生成如下TACt1 b * c t2 a t1核心代码可以这样写class TACGenerator { public: std::vectorstd::string code; int tempCounter 0; std::string genTemp() { return t std::to_string(tempCounter); } std::string genExpr(Expr* node) { if (auto* intLit dynamic_castIntLit*(node)) { return # std::to_string(intLit-value); // 立即数 } if (auto* idExpr dynamic_castIdExpr*(node)) { return idExpr-name; } if (auto* binOp dynamic_castBinOp*(node)) { std::string lhs genExpr(binOp-lhs); std::string rhs genExpr(binOp-rhs); std::string temp genTemp(); std::string opStr opToString(binOp-op); code.push_back(temp lhs opStr rhs); return temp; } return ; } void genStmt(Stmt* node) { if (auto* assign dynamic_castAssignStmt*(node)) { std::string rhs genExpr(assign-value); code.push_back( assign-name rhs); } else if (auto* whileLoop dynamic_castWhileStmt*(node)) { std::string beginLabel L std::to_string(labelCounter); std::string endLabel L std::to_string(labelCounter); code.push_back(label beginLabel); std::string cond genExpr(whileLoop-cond); code.push_back(if cond false goto endLabel); genStmt(whileLoop-body); code.push_back(goto beginLabel); code.push_back(label endLabel); } // 其他语句类似 } };上面代码里有个设计值得注意genExpr返回的是“操作数地址”可能是一个变量名、临时变量名或立即数。返回字符串的方式很灵活但立即数前要加#以区分变量名。三地址码的指令格式我习惯写成variable operand operator operand label label_name if operand relop operand goto label_name其中if语句生成时条件表达式会生成一个临时变量保存真/假值然后插入if temp false goto end。这比直接让genExpr返回布尔条件更简单。但如果条件是个常量表达式比如while (1)不优化的话也会生成一次求值指令这没问题只是跑得慢一点。另一个需要小心的坑赋值语句左边是个变量但右边如果是对变量的引用比如x x 1TAC生成顺序很重要。先genExpr(right)得到右边结果再存到左边顺序对。但如果右边表达式里修改了同一个变量比如函数调用就有了副作用我们的语言子集没有函数调用副作用所以不用担心。这也是我建议不要做函数内置操作的原因。4.4 解释执行还是生成汇编课程设计怎么选中间代码生成之后一般有两种终态解释执行还是翻译成某种目标代码。南航的课程设计要求不一有的要求生成MIPS汇编有的只要求解释执行。解释执行的好处是避免和具体指令集较劲代码量小测试方便。做法是维护一个“符号→值”的运行时环境逐条执行TAC。下面是一个最小解释器框架void interpret(const vectorstring tac) { unordered_mapstring, int vars; unordered_mapstring, int labels; for (int i 0; i tac.size(); i) { if (tac[i].rfind(label, 0) 0) { labels[tac[i].substr(6)] i; } } int pc 0; while (pc tac.size()) { const string inst tac[pc]; if (inst.rfind(label, 0) 0) { pc; continue; } // 形如 t1 #1 #2 size_t eq inst.find(); if (eq ! string::npos) { string target inst.substr(0, eq - 1); // 提取左右操作数 string exprPart inst.substr(eq2); // 解析 op1 op op2 string op1, op2, op; // 简化处理用字符串流分割 // 计算后存入vars[target] pc; } else if (inst.rfind(if , 0) 0) { // 条件跳转 } else if (inst.rfind(goto , 0) 0) { // 跳转 } } }解释执行时操作数如果是#开头则是立即数否则查vars表。这需要把每个操作数解析成整数或浮点。为了不写得太长这里不展开完整解析课程设计里可以借助std::stringstream。生成目标代码如果要求汇编常见选MIPS。MIPS架构教学广泛指令集精简寄存器不用处理x86那些奇怪的分支条件。但纯手工生成代码分配寄存器很痛苦。最简单的方式是“临时变量全部放栈上”每条TAC的临时变量对应一个栈槽。虽然生成的代码很多冗余lw/sw但能正确工作。老师如果问你“为什么临时变量t1求完立刻回写内存”你可以回答这是课程设计的简化策略并指出后续可以通过寄存器分配优化。5. 课程设计避坑指南5个最常让学生翻车的编译实现细节这一章来自我见过的真实翻车现场每一条都是血泪经验。如果你能提前规避至少省出两个通宵。5.1 词法分析器在读取!时多吞了一个字符现象输入if (a ! b) x 1;语法分析时报“expected ( after if”或者“unexpected token ”。原因词法分析器的readOperator先读一个字符!然后判断第二个字符是否为。但实现时如果没有回退逻辑读到!后advance()了一次看到后advance()第二次此时指针已经越过了。如果处理流程里没有正确生成!这个token而是返回了!和两个token语法分析就懵了。解决在readOperator中先用peek(0)和peek(1)能一次看到两个字符再一次性advance对应的次数不要边读边前进。或者封装一个unadvance()方法把注意度放在正确回退上。写完词法分析器后特意构造测试用例a!b、ab、ab逐个验证。5.2 递归下降处理if语句时else被错误的if吞掉现象测试if (a) if (b) x1; else y2;本意是else匹配第二个if但你的程序匹配到了第一个ify2永远不会执行。原因递归下降的parseStmt在处理if时如果不加额外判断会无条件递归调用parseStmt去解析then分支。而else分支是可有可无的你在解析then分支时parseStmt会把后面的else当作一个新语句的开始导致它被吞掉或者报错。解决方法有多种。最稳的是要求所有if和else都带花括号这样parseStmt遇到else时能明确区分。如果想保留悬挂else需要在parseStmt里增加一个“能否以else开头”的标记或者先用一个预测函数判断当前token是否为TK_ELSE是则返回。我建议课程设计直接规定“控制语句必须写花括号”并在测试文档里说明。这不是偷懒而是为了让你把精力集中在语义分析和代码生成上。5.3 符号表作用域退出顺序错了查表查到已释放变量现象一个函数内部的复合语句{ int x; } x 1;理论上x在该复合语句外不可见但你的编译器竟然允许赋值成功而且不报错。原因符号表的作用域弹出处理有问题。常见是enterScope和exitScope没有对称调用比如在parseCompoundStmt中解析完内部语句后忘记调用exitScope或者提前调用了exitScope导致外层符号也被清掉。另一个隐蔽点是AST遍历在语义分析阶段也可能重新进入作用域如果你在语法分析阶段就插入了作用域标记但AST里没有保留作用域边界遍历时就会错乱。解决最好在AST节点上显式增加Scope节点类型或者给CompoundStmt节点保存一个SymbolTable*指针。语义分析遍历到CompoundStmt时enter出节点时exit。不要依赖语法分析时的临时动作。还要写个小测试同一作用域重复声明变量必须报错嵌套作用域同名变量必须允许。5.4 中间代码中临时变量的类型没有标注导致运行时计算错误现象float a; int b; a b 1.5;生成的三地址码是t1 #1 #2解释执行时把它按整数算结果t1变成2而不是2.5。原因TAC生成时没有携带类型信息。如果解释器只维护一个“int变量表”把浮点数也塞进去精度就丢了。解决要么在生成TAC时给每个临时变量一个类型标记比如t1_f b_itof #1.5要么更简单——让所有变量统一为double。课程设计如果不考察汇编优化全部用double能极大减少类型处理复杂度。但老师可能会问“你的int类型变量存储占多少字节”你需要答出“课程设计简化运行时统一用64位浮点但要指出真实编译器会在类型信息里区分”。在中间代码里加类型标记的格式可以这样写t1 b_itof 1.5 a t1其中b_itof是一条“整数转浮点”指令。5.5 生成的代码在无限循环中没有推进解释器卡死在goto上现象运行while (1) { }你的解释器直接死循环这本身没错但运行int i0; while(i3) { ii1; }竟然也死循环。原因问题多出在条件判断的TAC生成顺序上。我的genStmt里生成的是if cond false goto end条件表达式的TAC在label之前。解释器执行到goto begin后回到label begin条件重新计算——这没问题。但如果你的条件表达式TAC生成在使用条件之后、且临时变量的求值没有正确更新或者跳转标签被错误插入到了条件表达式中间i的值永远不会更新。解决打印生成的TAC人眼模拟一遍。检查如下序列label L0 t1 i 3 if t1 false goto L1 t2 i 1 i t2 goto L0 label L1如果发现if后面的跳转目标里没有label L1或者goto L0和label L0的顺序颠倒就要检查labelCounter和goto的插入时点。每生成一个goto必须确保对应的label已经存在于指令序列中。最好的做法是先为整个循环体创建一个唯一的结束label再把goto end和label end配对生成不要交错。6. 把课程设计做成能演示的成果测试用例、错误恢复与可视化最后一章讲怎么把代码从“能跑”变成“能展示”。课程设计答辩时光有一个能编译求和的程序是不够的你需要让别人看到你对错误输入的处理、对细节的把控以及你的扩展能力。先准备一套分层的测试用例。最外层是“正常用例”一组包含变量声明、赋值、算术表达式、if-else和while循环的小程序比如计算阶乘、求最大公约数、判断素数。第二层是“语义错误用例”未声明变量、类型不匹配、重定义变量、数组下标越界。第三层是“语法错误用例”缺少分号、括号不匹配、错误的token顺序。每一层至少3个文件。我习惯把这些测试放在test/目录下每个输入对应一个.c文件和一个.out文件里面写明期望输出或期望报错信息。一个很加分的功能是错误恢复。词法分析和语法分析遇到错误时如果不做恢复第一个错误就会终止编译。老师很可能故意在上一个错误后面藏第二个错误看你能不能全部报出来。常见的做法是“恐慌模式”在parseStmt中发现不认识的token时跳过一个分号或一个右花括号然后继续解析。下面是一个简单的panic恢复void synchronize() { while (!check(TK_SEMI) !check(TK_RBRACE) !check(TK_EOF)) { advance(); } if (check(TK_SEMI)) advance(); }在每一条语句的parse入口如果发现当前token不能开始任何语句调用synchronize()。这样错误报告可以继续而不是“一次只报一个错”。但这个策略也有副作用会吞掉有效代码。所以建议只在明显错误时使用比如期望;时却拿到其他token。可视化方面AST打印是一大亮点。写一个dumpAST函数用缩进展示语法树结构。例如CompileUnit FunctionDecl retint namemain CompoundStmt AssignStmt targeti BinOp op IntLit 0 IntLit 1这样在答辩时一个测试用例跑完立刻能看到编译过程的分层。如果你的课程设计支持生成三地址码也把TAC指令序列打印出来再配上解释器的输出。一方面证明你每一步都真的在工作另一方面也方便你调试——出错时先用肉眼检查AST和TAC再决定改哪里。还有一个我强烈建议做的优化是“死代码块跳过”。识别if (0)或while (0)语法分析和语义分析照常走中间代码生成时直接不生成对应语句的代码。这个优化实现非常简单在genStmt里检查while条件是否为常量表达式0如果是跳过后面的body。虽然作用不算太大但它是“编译优化”的入门级能力答辩时提一句老师会觉得你不是只会照本宣科。最后说说验证方法。不要只靠一个main里跑通了就宣布完成。我把整个工程拆成四个独立可执行的目标词法分析器只输出token流语法分析器只输出AST语义分析器输出带类型的AST最后的编译器输出TAC并解释执行。每个阶段都可以用--stage参数单独跑。这样如果最后一个输出错了你能快速定位是哪个阶段出的问题。我自己在实现时第一版没有分阶段输出遇到语义错误时往往要同时猜三个模块的bug浪费了很多时间。分阶段后调试效率至少提升一倍。这套方案做完你的课程设计已经不只是一个“交差”的作业而是一个你可以对着它讲二十分钟的微型编译器项目。以后再有人问编译器原理你已经不是从课本上背答案而是真正见过每一个坑。希望帮到你。本文还有配套的精品资源点击获取 编译原理课程设计实战：从零手写迷你编译器全流程指南
简介这是南京航空航天大学编译原理课程设计全套方案面向计算机专业本科生及编译原理初学者覆盖词法分析与语法分析两大核心模块程序均经检验无BUG可直接运行验证帮助梳理编译器前端构建流程。压缩包共32个文件体积约961KB包含C/C与头文件源码、可执行程序、课程设计报告与答辩PPT以及配套文本材料从代码到汇报都一应俱全。词法分析与语法分析分别提供独立可执行版本可对照运行观察识别、解析过程报告与PPT同时可作为课程报告写作和答辩演练的参考。已有749人学习下载特别适合准备课设答辩或系统复习词法识别、递归下降等实现细节的计算机专业学生。1. 编译原理课程设计的真相不写编译器这门课就白学了很多人把编译原理当成一门“玄学”课教材翻完考试过了但你问他“编译器到底怎么把printf(hello)变成机器码”他只能支支吾吾。南京航空航天大学把这门课配上课程设计目的就是逼你亲手做一个能跑的小编译器哪怕只支持一个子集语言。课程设计不是让你复述龙书里的算法而是让你从词法、语法、语义到代码生成完整走一遍编译器前端和后端的核心链路。适合谁适合想搞清“编译器黑匣子”里到底装了什么的学生也适合工作后想转编译器方向、需要一份拿得出手项目经历的从业者。这篇笔记会按照做课程设计最常见的路径把设计取舍、关键代码、调试方法和踩坑点讲透让你照着能做出来而不是停留在概念层。2. 选定一个能完工的语言子集从文法到错误处理的设计取舍课程设计最忌讳“什么都想做”。你不可能在半个学期里写出一个标准C编译器也没人指望你做到GCC那个程度。关键是选一个“小而完整”的语言子集把它从源码到中间代码/目标代码的整条流水线打通。这个选择和你的文法定义直接绑定后面所有代码都围绕这套文法展开。2.1 语言子集怎么定南航历年题目里最常见的范围以南京航空航天大学历年课程设计题目为例最常见的做法是选择C语言的子集通常包含以下内容变量声明int和char、float以及简单数组一维下标为常量或变量表达式四则运算、取负、括号、比较运算、逻辑与或非语句赋值、if、while、for可选、read/write以及复合语句{ }函数最多支持无返回值或单返回值的函数不搞重载和指针。我建议把“函数”放进去哪怕只做一个主函数。因为课程设计的评分点通常包括符号表管理和中间代码生成没有函数符号表的作用域设计就看不出水平。但不要做嵌套函数、函数指针这类东西否则递归下降分析器会复杂到失控。文法定义建议用EBNF而非纯BNF。EBNF里的[ ]和{ }能减少左递归也让递归下降程序写起来更直观。下面是一个经过裁减的表达式和语句的文法骨架program - { function } function - type ID ( ) compound_stmt compound_stmt - { { local_decl | stmt } } local_decl - type ID [ expr ] ; stmt - if_stmt | while_stmt | read_stmt | write_stmt | ID expr ; | compound_stmt if_stmt - if ( expr ) stmt [ else stmt ] while_stmt - while ( expr ) stmt expr - add_expr [ ( | | | !) add_expr ] add_expr - mul_expr { ( | -) mul_expr } mul_expr - unary_expr { (* | /) unary_expr } unary_expr - (- | !) unary_expr | primary primary - INT_NUM | STRING | ID | ( expr )注意我故意把for排除了。为什么因为for在语法分析上只是while加个初始化语句代码生成却要额外处理continue标签。第一次做课程设计控制语句越少越能把语义分析和代码生成的逻辑做干净。等主体跑通了再自己加for也不迟。还有一个容易被低估的设计点是注释支持。很多学生开始时忘了注释程序一读带注释的测试就往崩溃。语法上预留//和/* */的跳过逻辑词法分析器里多写10行代码后面省一天调试时间。2.2 手写词法分析器和递归下降还是上Flex/Bison这是每个做课程设计的人都要面对的卡点。我的建议很明确语法分析器必须手写递归下降词法分析器可以手写也可以用工具。理由有三手写递归下降能让你真正理解文法和程序控制流的对应关系。expr - term { (|-) term }对应函数里一个while循环这种映射只有亲手写一遍才刻进脑子。Bison的LALR冲突解决对新手很不友好。如果你定义C子集文法else悬挂、表达式优先级、左递归都要处理Bison会给一堆shift/reduce冲突看不懂就去网上找答案结果别人的文法和你又不完全一样非常浪费时间。课程设计答辩时老师大概率会问你“递归下降遇到左递归怎么办”“你的FIRST集合怎么算的”。手写版你能当场答上来因为每个函数都是你自己写的。用工具生成反而容易一问三不知。词法分析器方面如果你对正则表达式和状态机足够熟练可以用Flex。但说实话一个支持关键字、标识符、数字、字符串、注释和运算符的词法分析器手写也就200-300行。而且手写词法能做到报错信息里带行列号Flex默认的错误信息不够友好。如果你非要用工具建议FlexBison但要把它们的代码生成选项弄明白Flex里yylex返回的token编号要和Bison里%token编号一致操作符优先级靠%left声明。下面用一个小例子说明Flex和Bison配合的最小骨架。先看Flex文件%{ #include y.tab.h #include stdio.h extern int yylval; %} %% [0-9] { yylval atoi(yytext); return NUMBER; } [a-zA-Z_][a-zA-Z0-9_]* { yylval yytext[0]; return ID; } { return PLUS; } - { return MINUS; } * { return TIMES; } / { return DIVIDE; } { return ASSIGN; } [ \t\n] ; . { fprintf(stderr, unexpected char: %s\n, yytext); } %%Bison文件里这样声明优先级%token NUMBER ID %left PLUS MINUS %left TIMES DIVIDE %% expr : expr PLUS expr | expr MINUS expr | expr TIMES expr | expr DIVIDE expr | NUMBER | ID ; %%这里的%left顺序尤为重要越在后面声明的运算符优先级越高。PLUS MINUS在前符合数学上加减比乘除低一级的约定。Bison会利用这个声明解决表达式文法的shift/reduce冲突不让它在12*3里产生歧义。编译时用bison -d parser.y生成y.tab.h然后flex lexer.l最后把lex.yy.c和y.tab.c一起编译。注意Flex生成的yylex默认符号表在yy.tab.h里声明如果你的C代码里提前引用了NUMBER必须先包含这个头文件。但如果你选手写路线可以考虑用Python或C。Python代码短、调试快适合第一个版本C多写一些类但最终性能更好。我在实际做课程设计时第一版用Python把整个流程跑通然后用C重写重写速度比直接写C快很多因为逻辑已经在Python里验证过了。下面正式进入实现环节。3. 词法与语法分析落地手写递归下降与构建AST的两种可行方案这一章解决从源代码流到抽象语法树AST的问题。我会先给出手写词法分析器的完整思路再给出递归下降语法分析器的核心代码框架最后说明AST怎么设计才不会在后面语义分析和三地址码生成时后悔。3.1 手写一个带行列号的词法分析器状态机与前进指针词法分析器的本质是“读下一个token”。但实际实现时很多人栽在“回退”和“越界”上。我习惯用一个结构体保存当前读到的字符缓冲区并维护行号和列号。下面的C代码展示了一个简化版词法分析器的核心结构它识别数字、标识符、关键字、运算符和字符串。enum TokenType { TK_ID, TK_INT, TK_FLOAT, TK_STRING, TK_PLUS, TK_MINUS, TK_TIMES, TK_DIVIDE, TK_ASSIGN, TK_EQ, TK_NEQ, TK_LT, TK_GT, TK_IF, TK_ELSE, TK_WHILE, TK_READ, TK_WRITE, TK_LPAREN, TK_RPAREN, TK_LBRACE, TK_RBRACE, TK_SEMI, TK_EOF }; struct Token { TokenType type; std::string text; int line; int col; }; class Lexer { public: explicit Lexer(const std::string src) : src(src), pos(0), line(1), col(1) {} Token next() { skipWhitespaceAndComments(); if (pos src.size()) return makeToken(TK_EOF, EOF); char ch peek(); if (isdigit(ch)) return readNumber(); if (isalpha(ch) || ch _) return readIdentifierOrKeyword(); return readOperator(); } private: std::string src; size_t pos; int line; int col; char peek(size_t ahead 0) const { size_t idx pos ahead; return idx src.size() ? src[idx] : \0; } void advance() { if (peek() \n) { line; col 1; } else { col; } pos; } Token makeToken(TokenType type, const std::string text) { Token t; t.type type; t.text text; t.line line; t.col col; return t; } void skipWhitespaceAndComments() { while (pos src.size()) { char ch peek(); if (ch || ch \t || ch \r || ch \n) { advance(); } else if (ch / peek(1) /) { while (pos src.size() peek() ! \n) advance(); } else if (ch / peek(1) *) { advance(); advance(); while (pos src.size() !(peek() * peek(1) /)) advance(); advance(); advance(); } else break; } } Token readNumber() { std::string text; while (isdigit(peek())) { text peek(); advance(); } return makeToken(TK_INT, text); } Token readIdentifierOrKeyword() { std::string text; while (isalnum(peek()) || peek() _) { text peek(); advance(); } static const std::unordered_mapstd::string, TokenType keywords { {if, TK_IF}, {else, TK_ELSE}, {while, TK_WHILE}, {read, TK_READ}, {write, TK_WRITE} }; auto it keywords.find(text); return makeToken(it ! keywords.end() ? it-second : TK_ID, text); } Token readOperator() { char ch peek(); std::string text(1, ch); advance(); if ((ch peek() ) || (ch ! peek() ) || (ch peek() ) || (ch peek() )) { text peek(); advance(); if (text ) return makeToken(TK_EQ, text); if (text !) return makeToken(TK_NEQ, text); if (text ) return makeToken(TK_LE, text); if (text ) return makeToken(TK_GE, text); } else if (ch ) { return makeToken(TK_LT, text); } else if (ch ) { return makeToken(TK_GT, text); } switch (ch) { case : return makeToken(TK_PLUS, text); break; case -: return makeToken(TK_MINUS, text); break; case *: return makeToken(TK_TIMES, text); break; case /: return makeToken(TK_DIVIDE, text); break; case : return makeToken(TK_ASSIGN, text); break; case (: return makeToken(TK_LPAREN, text); break; case ): return makeToken(TK_RPAREN, text); break; case {: return makeToken(TK_LBRACE, text); break; case }: return makeToken(TK_RBRACE, text); break; case ;: return makeToken(TK_SEMI, text); break; default: throw std::runtime_error(unknown char text at line std::to_string(line) col std::to_string(col)); } } };这段代码有几个关键设计。peek和advance是词法分析器的两个基本操作peek负责看当前或后续字符但不移动指针advance负责移动指针并更新行列号。skipWhitespaceAndComments把所有空白和注释吞掉注释支持//和/* */。readOperator里用了二级判断先读第一个字符再看第二个字符能不能组成双字符运算符。这里有个容易踩的坑识别时如果第二个字符不是比如遇到后面跟空白必须把指针停留在正确位置。我的实现是advance()先吃掉一个字符然后peek()读第二个如果不是配对字符其实已经多吃了一个需要回退。但我这里用了一个技巧先text peek(); advance();此时指针已经到第二个字符。如果发现不是双字符必须把pos回退一格同时col减一。上面代码简化了这种情况实际上你需要一个unadvance()操作。很多课程设计失败就失败在这个小细节。我在代码里没有写回退但实际实现时一定要加void unadvance() { if (pos 0) { pos--; char prev src[pos]; if (prev \n) { line--; /* col需恢复到上一行末尾建议保存一行快照 */ } else { col--; } } }更稳妥的办法是读到一个操作符时先用peek(0)和peek(1)判断组合再一次性advance两格避免回退。这样做就不会有“吃多”的问题。3.2 递归下降语法分析器每个文法产生式对应一个函数有了token流语法分析器就可以开始工作。递归下降的核心思想是为每个非终结符写一个函数函数内部按照产生式的右端逐个匹配终结符或调用其他非终结符函数。下面是一个简化版的Expr、Term和Stmt函数class Parser { public: explicit Parser(Lexer lexer) : lexer(lexer) { cur lexer.next(); } void parseProgram() { while (cur.type ! TK_EOF) { parseFunction(); } } private: Lexer lexer; Token cur; void advance() { cur lexer.next(); } bool check(TokenType type) { return cur.type type; } bool match(TokenType type) { if (check(type)) { advance(); return true; } return false; } void expect(TokenType type, const std::string msg) { if (!check(type)) { throw std::runtime_error(msg at line std::to_string(cur.line) col std::to_string(cur.col) , got cur.text); } advance(); } void parseFunction() { expect(TK_INT, expected int); expect(TK_ID, expected function name); expect(TK_LPAREN, expected (); expect(TK_RPAREN, expected )); parseCompoundStmt(); } void parseCompoundStmt() { expect(TK_LBRACE, expected {); while (!check(TK_RBRACE) !check(TK_EOF)) { if (cur.type TK_INT) { parseDeclaration(); } else { parseStmt(); } } expect(TK_RBRACE, expected }); } void parseDeclaration() { expect(TK_INT, expected int); expect(TK_ID, expected variable name); if (match(TK_ASSIGN)) { parseExpr(); } expect(TK_SEMI, expected ; after declaration); } void parseStmt() { if (check(TK_IF)) { advance(); expect(TK_LPAREN, expected ( after if); parseExpr(); expect(TK_RPAREN, expected ) after if condition); parseStmt(); if (match(TK_ELSE)) { parseStmt(); } } else if (check(TK_WHILE)) { advance(); expect(TK_LPAREN, expected ( after while); parseExpr(); expect(TK_RPAREN, expected ) after while condition); parseStmt(); } else if (check(TK_ID)) { advance(); expect(TK_ASSIGN, expected in assignment); parseExpr(); expect(TK_SEMI, expected ; after assignment); } else if (check(TK_LBRACE)) { parseCompoundStmt(); } else { throw std::runtime_error(unexpected token at line std::to_string(cur.line) col std::to_string(cur.col)); } } void parseExpr() { parseAddExpr(); if (check(TK_GT) || check(TK_LT)) { advance(); parseAddExpr(); } } void parseAddExpr() { parseMulExpr(); while (check(TK_PLUS) || check(TK_MINUS)) { advance(); parseMulExpr(); } } void parseMulExpr() { parseUnaryExpr(); while (check(TK_TIMES) || check(TK_DIVIDE)) { advance(); parseUnaryExpr(); } } void parseUnaryExpr() { if (check(TK_MINUS) || check(TK_NOT)) { advance(); parseUnaryExpr(); } else { parsePrimary(); } } void parsePrimary() { if (check(TK_INT)) { advance(); } else if (check(TK_ID)) { advance(); } else if (check(TK_LPAREN)) { advance(); parseExpr(); expect(TK_RPAREN, expected ) after expression); } else { throw std::runtime_error(unexpected token in primary at line std::to_string(cur.line)); } } };这段代码里有一个很关键的约定每个parse函数在调用时当前token已经被读好函数负责“消耗”自己所需的token。比如parseExpr先调用parseAddExpr然后如果看到比较运算符就继续读右操作数。这个“当前token全局唯一”的设计避免了回溯代价是程序设计必须严格符合文法。如果你写的文法有公共左因子递归下降就会出问题。比如stmt - IF ( expr ) stmt ELSE stmt | WHILE ( expr ) stmt这两个产生式开头不同所以没有冲突。如果遇到相同开头比如stmt - ID ASSIGN expr和stmt - ID LPAREN args RPAREN必须提取左因子否则无法确定该选哪条。上面的parseStmt里对if的处理有一个细节当if (match(TK_ELSE))时parseStmt会再递归地分析else分支。这实际上实现了“else就近匹配”。但如果不加花括号else可能会错误地匹配到内部的if上这就是经典的“悬挂else”问题。标准做法是在文法里强制stmt要么是复合语句要么是简单语句且else必须出现在复合语句前。但简单起见我建议在课程设计说明里就要求用户写if (x) { ... } else { ... }这样parseStmt里不会产生歧义。3.3 构建AST用std::variant还是继承体系语法分析的过程中直接生成三地址码是一种选项但更清晰的课程设计路径是先构建AST再遍历AST生成中间代码。AST的节点设计要覆盖表达式、语句、声明和整个程序。在C里常见有两种AST设计方式。一种是经典虚函数继承struct Node { virtual ~Node() default; }; struct Expr : Node { virtual ~Expr() default; }; struct IntLit : Expr { int value; IntLit(int v) : value(v) {} }; struct BinOp : Expr { Expr* lhs; Expr* rhs; int op; }; struct AssignStmt : Node { std::string name; Expr* value; };另一种是现代C的std::variant更安全但访问时需要写std::visit。考虑到答辩时老师可能会指着AST问“你如何区别不同节点”继承体系更直观。建议每个节点都保存line和col哪怕只用于报错也能省很多查错时间。AST构建需要修改上述parse函数让每个函数返回节点指针。比如Expr* parseExpr() { Expr* left parseAddExpr(); if (check(TK_LT) || check(TK_GT)) { Token op cur; advance(); Expr* right parseAddExpr(); return new BinOp(left, right, op.type); } return left; }这里注意if条件只处理了LT和GT如果你扩展和!还要在check里加入TK_EQ和TK_NEQ。每个运算符节点要保存运算符的token类型这样后面生成三地址码时可以直接switch。有一个很重要的工程习惯AST节点用指针后一定要设计统一的析构机制否则内存泄漏。最简单的方式是用std::unique_ptr。但如果为了代码可读性裸指针加上在Parser析构函数里统一delete也可以接受。课程设计的代码量不大只要不每次parse都new几十个节点却不解构答辩时内存泄漏不会被细究。但如果你在同一个测试程序里反复解析多个文件泄漏会让程序越跑越慢甚至崩掉。4. 语义分析与中间代码生成符号表、类型检查和三地址码的配合语法分析只检查“结构对不对”不检查“合不合理”。int x y 1;如果y没声明或者y是字符串语法上完全合法语义上却要报错。这一章把符号表和中间代码生成讲透这部分通常是课程设计评分最高的模块。4.1 符号表怎么设计作用域链与重定义检测符号表需要支持嵌套作用域。最简单的实现是“栈哈希表”两层结构。全局符号表保存函数名和全局变量每个复合语句进入时压入一个新作用域退出时弹出。struct Symbol { std::string name; std::string type; // int, char, float, array int arraySize; // 0表示非数组 int line; int col; int scope; }; class SymbolTable { public: void enterScope() { scopes.emplace_back(); } void exitScope() { scopes.pop_back(); } bool insert(const Symbol sym) { auto current scopes.back(); if (current.find(sym.name) ! current.end()) { return false; // 重定义 } current[sym.name] sym; return true; } const Symbol* lookup(const std::string name) { for (auto it scopes.rbegin(); it ! scopes.rend(); it) { auto found it-find(name); if (found ! it-end()) { return found-second; } } return nullptr; } private: std::vectorstd::unordered_mapstd::string, Symbol scopes; };这里有个容易忽略的点lookup要从最内层向外找。比如在{ int x; { x 1; } }中内层的x如果没声明应该找到外层的x。这个链式查找是作用域的关键也是老师最爱问的问题。insert只往当前作用域插如果当前作用域已有同名符号说明是重定义直接报错。数组的符号要额外存arraySize。如果你实现了下标访问AST里需要增加ArrayIndexExpr节点。语义分析时除了检查数组名还要检查下标是否为整数类型以及下标范围是否越界。不过课程设计通常不要求运行时数组越界检查因为静态分析只能查常量越界变量下标只能留给生成代码后运行时检查。如果要做得更完整可以在生成的三地址码里插入if (idx size) error代码。4.2 类型检查隐式转换要不要支持课程设计的测试用例里很可能出现int a; float b; a b;。如果完全不支持类型转换写起来简单但测试时容易被人故意恶心。常见做法是支持int和float两种类型int赋值给float自动转float赋值给int时给出警告并在生成的代码里截断。这样既不过分复杂又显得你考虑周到了。类型检查的“检查规则表”应该提前列出来运算左操作数类型右操作数类型结果类型 - * /intintint - * /floatfloatfloat - * /intfloatfloat !任意同左int变量类型表达式类型无具体实现时在AST节点上增加一个type字段。计算表达式时递归地返回结果类型。比如BinOp的getType()会先取左右子节点类型若左右都是int则结果为int若任一为float则结果为float。比较运算的结果统一为int1表示真0表示假。赋值语句检查左值类型和右值类型是否可转换如果左值是int而右值是float报错或警告。在语义分析阶段常见的做法是写一个SemanticAnalyzer类继承AST访问者模式。因为AST节点种类不多简单用switch遍历也行。下面演示一个visitBinOp的类型检查片段std::string visitBinOp(BinOp* node) { std::string lhs visitExpr(node-lhs); std::string rhs visitExpr(node-rhs); if (node-op TK_PLUS || node-op TK_MINUS || node-op TK_TIMES || node-op TK_DIVIDE) { if (lhs float || rhs float) { node-type float; } else { node-type int; } } else if (node-op TK_LT || node-op TK_GT || node-op TK_EQ || node-op TK_NEQ) { if (lhs ! rhs) { reportError(comparison of different types); } node-type int; } return node-type; }注意算术运算中int和float混用在生成三地址码时需要插入一条INT_TO_FLOAT指令否则汇编代码里两个不同类型的数无法直接相加。很多学生在这步忘记插入转换指令导致生成的目标代码在运行时计算结果不对。如果是生成自己的虚拟机指令也要在指令集里设计一条itof。4.3 三地址码生成的两种模式直接递归和显式临时变量三地址码TAC是中间代码的常见形式每条指令至多包含三个地址操作数或目标。课程设计通常选择它因为后面解释执行或翻译成汇编都很方便。生成TAC时我为每个表达式分配一个临时变量。例如表达式a b * c生成如下TACt1 b * c t2 a t1核心代码可以这样写class TACGenerator { public: std::vectorstd::string code; int tempCounter 0; std::string genTemp() { return t std::to_string(tempCounter); } std::string genExpr(Expr* node) { if (auto* intLit dynamic_castIntLit*(node)) { return # std::to_string(intLit-value); // 立即数 } if (auto* idExpr dynamic_castIdExpr*(node)) { return idExpr-name; } if (auto* binOp dynamic_castBinOp*(node)) { std::string lhs genExpr(binOp-lhs); std::string rhs genExpr(binOp-rhs); std::string temp genTemp(); std::string opStr opToString(binOp-op); code.push_back(temp lhs opStr rhs); return temp; } return ; } void genStmt(Stmt* node) { if (auto* assign dynamic_castAssignStmt*(node)) { std::string rhs genExpr(assign-value); code.push_back( assign-name rhs); } else if (auto* whileLoop dynamic_castWhileStmt*(node)) { std::string beginLabel L std::to_string(labelCounter); std::string endLabel L std::to_string(labelCounter); code.push_back(label beginLabel); std::string cond genExpr(whileLoop-cond); code.push_back(if cond false goto endLabel); genStmt(whileLoop-body); code.push_back(goto beginLabel); code.push_back(label endLabel); } // 其他语句类似 } };上面代码里有个设计值得注意genExpr返回的是“操作数地址”可能是一个变量名、临时变量名或立即数。返回字符串的方式很灵活但立即数前要加#以区分变量名。三地址码的指令格式我习惯写成variable operand operator operand label label_name if operand relop operand goto label_name其中if语句生成时条件表达式会生成一个临时变量保存真/假值然后插入if temp false goto end。这比直接让genExpr返回布尔条件更简单。但如果条件是个常量表达式比如while (1)不优化的话也会生成一次求值指令这没问题只是跑得慢一点。另一个需要小心的坑赋值语句左边是个变量但右边如果是对变量的引用比如x x 1TAC生成顺序很重要。先genExpr(right)得到右边结果再存到左边顺序对。但如果右边表达式里修改了同一个变量比如函数调用就有了副作用我们的语言子集没有函数调用副作用所以不用担心。这也是我建议不要做函数内置操作的原因。4.4 解释执行还是生成汇编课程设计怎么选中间代码生成之后一般有两种终态解释执行还是翻译成某种目标代码。南航的课程设计要求不一有的要求生成MIPS汇编有的只要求解释执行。解释执行的好处是避免和具体指令集较劲代码量小测试方便。做法是维护一个“符号→值”的运行时环境逐条执行TAC。下面是一个最小解释器框架void interpret(const vectorstring tac) { unordered_mapstring, int vars; unordered_mapstring, int labels; for (int i 0; i tac.size(); i) { if (tac[i].rfind(label, 0) 0) { labels[tac[i].substr(6)] i; } } int pc 0; while (pc tac.size()) { const string inst tac[pc]; if (inst.rfind(label, 0) 0) { pc; continue; } // 形如 t1 #1 #2 size_t eq inst.find(); if (eq ! string::npos) { string target inst.substr(0, eq - 1); // 提取左右操作数 string exprPart inst.substr(eq2); // 解析 op1 op op2 string op1, op2, op; // 简化处理用字符串流分割 // 计算后存入vars[target] pc; } else if (inst.rfind(if , 0) 0) { // 条件跳转 } else if (inst.rfind(goto , 0) 0) { // 跳转 } } }解释执行时操作数如果是#开头则是立即数否则查vars表。这需要把每个操作数解析成整数或浮点。为了不写得太长这里不展开完整解析课程设计里可以借助std::stringstream。生成目标代码如果要求汇编常见选MIPS。MIPS架构教学广泛指令集精简寄存器不用处理x86那些奇怪的分支条件。但纯手工生成代码分配寄存器很痛苦。最简单的方式是“临时变量全部放栈上”每条TAC的临时变量对应一个栈槽。虽然生成的代码很多冗余lw/sw但能正确工作。老师如果问你“为什么临时变量t1求完立刻回写内存”你可以回答这是课程设计的简化策略并指出后续可以通过寄存器分配优化。5. 课程设计避坑指南5个最常让学生翻车的编译实现细节这一章来自我见过的真实翻车现场每一条都是血泪经验。如果你能提前规避至少省出两个通宵。5.1 词法分析器在读取!时多吞了一个字符现象输入if (a ! b) x 1;语法分析时报“expected ( after if”或者“unexpected token ”。原因词法分析器的readOperator先读一个字符!然后判断第二个字符是否为。但实现时如果没有回退逻辑读到!后advance()了一次看到后advance()第二次此时指针已经越过了。如果处理流程里没有正确生成!这个token而是返回了!和两个token语法分析就懵了。解决在readOperator中先用peek(0)和peek(1)能一次看到两个字符再一次性advance对应的次数不要边读边前进。或者封装一个unadvance()方法把注意度放在正确回退上。写完词法分析器后特意构造测试用例a!b、ab、ab逐个验证。5.2 递归下降处理if语句时else被错误的if吞掉现象测试if (a) if (b) x1; else y2;本意是else匹配第二个if但你的程序匹配到了第一个ify2永远不会执行。原因递归下降的parseStmt在处理if时如果不加额外判断会无条件递归调用parseStmt去解析then分支。而else分支是可有可无的你在解析then分支时parseStmt会把后面的else当作一个新语句的开始导致它被吞掉或者报错。解决方法有多种。最稳的是要求所有if和else都带花括号这样parseStmt遇到else时能明确区分。如果想保留悬挂else需要在parseStmt里增加一个“能否以else开头”的标记或者先用一个预测函数判断当前token是否为TK_ELSE是则返回。我建议课程设计直接规定“控制语句必须写花括号”并在测试文档里说明。这不是偷懒而是为了让你把精力集中在语义分析和代码生成上。5.3 符号表作用域退出顺序错了查表查到已释放变量现象一个函数内部的复合语句{ int x; } x 1;理论上x在该复合语句外不可见但你的编译器竟然允许赋值成功而且不报错。原因符号表的作用域弹出处理有问题。常见是enterScope和exitScope没有对称调用比如在parseCompoundStmt中解析完内部语句后忘记调用exitScope或者提前调用了exitScope导致外层符号也被清掉。另一个隐蔽点是AST遍历在语义分析阶段也可能重新进入作用域如果你在语法分析阶段就插入了作用域标记但AST里没有保留作用域边界遍历时就会错乱。解决最好在AST节点上显式增加Scope节点类型或者给CompoundStmt节点保存一个SymbolTable*指针。语义分析遍历到CompoundStmt时enter出节点时exit。不要依赖语法分析时的临时动作。还要写个小测试同一作用域重复声明变量必须报错嵌套作用域同名变量必须允许。5.4 中间代码中临时变量的类型没有标注导致运行时计算错误现象float a; int b; a b 1.5;生成的三地址码是t1 #1 #2解释执行时把它按整数算结果t1变成2而不是2.5。原因TAC生成时没有携带类型信息。如果解释器只维护一个“int变量表”把浮点数也塞进去精度就丢了。解决要么在生成TAC时给每个临时变量一个类型标记比如t1_f b_itof #1.5要么更简单——让所有变量统一为double。课程设计如果不考察汇编优化全部用double能极大减少类型处理复杂度。但老师可能会问“你的int类型变量存储占多少字节”你需要答出“课程设计简化运行时统一用64位浮点但要指出真实编译器会在类型信息里区分”。在中间代码里加类型标记的格式可以这样写t1 b_itof 1.5 a t1其中b_itof是一条“整数转浮点”指令。5.5 生成的代码在无限循环中没有推进解释器卡死在goto上现象运行while (1) { }你的解释器直接死循环这本身没错但运行int i0; while(i3) { ii1; }竟然也死循环。原因问题多出在条件判断的TAC生成顺序上。我的genStmt里生成的是if cond false goto end条件表达式的TAC在label之前。解释器执行到goto begin后回到label begin条件重新计算——这没问题。但如果你的条件表达式TAC生成在使用条件之后、且临时变量的求值没有正确更新或者跳转标签被错误插入到了条件表达式中间i的值永远不会更新。解决打印生成的TAC人眼模拟一遍。检查如下序列label L0 t1 i 3 if t1 false goto L1 t2 i 1 i t2 goto L0 label L1如果发现if后面的跳转目标里没有label L1或者goto L0和label L0的顺序颠倒就要检查labelCounter和goto的插入时点。每生成一个goto必须确保对应的label已经存在于指令序列中。最好的做法是先为整个循环体创建一个唯一的结束label再把goto end和label end配对生成不要交错。6. 把课程设计做成能演示的成果测试用例、错误恢复与可视化最后一章讲怎么把代码从“能跑”变成“能展示”。课程设计答辩时光有一个能编译求和的程序是不够的你需要让别人看到你对错误输入的处理、对细节的把控以及你的扩展能力。先准备一套分层的测试用例。最外层是“正常用例”一组包含变量声明、赋值、算术表达式、if-else和while循环的小程序比如计算阶乘、求最大公约数、判断素数。第二层是“语义错误用例”未声明变量、类型不匹配、重定义变量、数组下标越界。第三层是“语法错误用例”缺少分号、括号不匹配、错误的token顺序。每一层至少3个文件。我习惯把这些测试放在test/目录下每个输入对应一个.c文件和一个.out文件里面写明期望输出或期望报错信息。一个很加分的功能是错误恢复。词法分析和语法分析遇到错误时如果不做恢复第一个错误就会终止编译。老师很可能故意在上一个错误后面藏第二个错误看你能不能全部报出来。常见的做法是“恐慌模式”在parseStmt中发现不认识的token时跳过一个分号或一个右花括号然后继续解析。下面是一个简单的panic恢复void synchronize() { while (!check(TK_SEMI) !check(TK_RBRACE) !check(TK_EOF)) { advance(); } if (check(TK_SEMI)) advance(); }在每一条语句的parse入口如果发现当前token不能开始任何语句调用synchronize()。这样错误报告可以继续而不是“一次只报一个错”。但这个策略也有副作用会吞掉有效代码。所以建议只在明显错误时使用比如期望;时却拿到其他token。可视化方面AST打印是一大亮点。写一个dumpAST函数用缩进展示语法树结构。例如CompileUnit FunctionDecl retint namemain CompoundStmt AssignStmt targeti BinOp op IntLit 0 IntLit 1这样在答辩时一个测试用例跑完立刻能看到编译过程的分层。如果你的课程设计支持生成三地址码也把TAC指令序列打印出来再配上解释器的输出。一方面证明你每一步都真的在工作另一方面也方便你调试——出错时先用肉眼检查AST和TAC再决定改哪里。还有一个我强烈建议做的优化是“死代码块跳过”。识别if (0)或while (0)语法分析和语义分析照常走中间代码生成时直接不生成对应语句的代码。这个优化实现非常简单在genStmt里检查while条件是否为常量表达式0如果是跳过后面的body。虽然作用不算太大但它是“编译优化”的入门级能力答辩时提一句老师会觉得你不是只会照本宣科。最后说说验证方法。不要只靠一个main里跑通了就宣布完成。我把整个工程拆成四个独立可执行的目标词法分析器只输出token流语法分析器只输出AST语义分析器输出带类型的AST最后的编译器输出TAC并解释执行。每个阶段都可以用--stage参数单独跑。这样如果最后一个输出错了你能快速定位是哪个阶段出的问题。我自己在实现时第一版没有分阶段输出遇到语义错误时往往要同时猜三个模块的bug浪费了很多时间。分阶段后调试效率至少提升一倍。这套方案做完你的课程设计已经不只是一个“交差”的作业而是一个你可以对着它讲二十分钟的微型编译器项目。以后再有人问编译器原理你已经不是从课本上背答案而是真正见过每一个坑。希望帮到你。本文还有配套的精品资源点击获取