本文还有配套的精品资源点击获取简介这个资源包包含电子科技大学编译原理课程前四个实验的可运行参考实现覆盖整个前端到中间代码生成流程。实验一用lex编写词法分析器能识别C语言子集的关键字、标识符、数字、运算符等token实验二基于C语言实现递归下降语法分析器支持表达式、赋值、if/while语句等常见结构的语法解析实验三完成抽象语法树AST构建定义了完整的节点类型与内存管理逻辑并提供遍历和打印功能实验四通过遍历AST生成符合LLVM 14规范的文本格式IR代码输出结果可直接用llc工具编译为本地汇编。所有实验均配备Makefile一键编译脚本、多个测试源文件如test.c、lab4-test_example.c以及Python校验脚本check.py用于比对输出结果是否符合预期。整个代码在Ubuntu 20.04环境验证通过目录结构清晰关键函数和数据结构均有中文注释适合学生对照课堂内容理解编译各阶段作用、调试报错、撰写实验报告或拓展修改。1. 项目概述这不是一份“参考答案”而是一套可调试、可拆解、可延伸的编译流水线沙盒你手头这份“电子科大编译原理四次实验完整实现”表面看是课程作业的参考代码但真正价值远不止于此——它是一套高度结构化、阶段解耦、边界清晰、输出可验证的编译前端教学沙盒。我带过三届编译原理实验课也帮学生debug过上百份lab1的lex规则冲突、lab3的AST内存泄漏、lab4的LLVM IR语法报错最常听到的一句话是“老师我跑通了但不知道哪一步在干啥。” 这份资源就是为解决这个根本痛点而生的。它严格遵循经典编译器前端四阶段模型词法分析 → 语法分析 → 抽象语法树构建 → 中间代码生成每个实验对应一个独立可运行模块且模块之间通过明确定义的数据结构如token_t、ast_node_t和接口函数如parse_expression()、gen_llvm_for_ast()进行通信不搞黑箱粘连。关键词里提到的“词法分析器”“递归下降解析”“AST构建”“LLVM IR生成”不是并列的四个名词而是一条有向数据流lexer输出token流喂给parserparser构造AST节点树AST再被codegen遍历翻译成LLVM IR文本。这种设计让你能像拧开阀门一样单独测试任一环节——比如把test.c喂给lexer看它吐出哪些token或者跳过lexer手动构造一个AST节点直接扔给genllvm.c看IR是否符合预期。更关键的是它完全规避了教学中常见的两大陷阱一是“魔法式Makefile”很多参考实现把所有步骤打包进一个make all出错时根本分不清是词法错了还是IR语法错了二是“静态测试用例”只给一个test.c改一行就全崩。而本资源包里每个lab目录下都有多个渐进式测试文件test01.c,test02.c,lab4-test_example.c从最简int main(){return 0;}到含嵌套if/while/数组访问的复杂表达式配合check.py脚本做逐行文本比对不是简单diff而是忽略空格、注释、临时寄存器名差异后的语义等价判断相当于给你配了个自动阅卷老师。我在实验室亲眼见过学生用check.py发现自己的lab2在处理a b c * d时运算符优先级错了——因为生成的IR里%t1 add i32 %a, %b出现在%t2 mul i32 %c, %d之前而标准答案是反过来的。这种细节光靠肉眼读C代码根本抓不住。它面向的不是“想抄作业”的人而是“想搞懂编译器怎么呼吸”的人。你不需要会写lex或懂LLVM spec全文只要你会gcc -o lexer lexer.l、会./lexer test.c、会llc -marchx86-64 -filetypeasm output.ll -o output.s就能亲手触摸每个阶段的输入输出。接下来我会带你一层层剥开这颗洋葱告诉你每个.c、每个.l、每个Makefile规则背后的真实意图以及那些藏在注释里、没写进实验指导书里的关键细节。2. 实验一深度拆解lex词法分析器不只是正则匹配而是状态机与错误恢复的实战训练场2.1 核心设计逻辑为什么用lex而不是手写状态机看到lexer.l的第一反应可能是“不就是写一堆正则匹配关键字吗” 但电子科大这个实验的精妙之处在于它用lex实现了真正的词法分析器该有的健壮性而非玩具级匹配。核心在于两点状态管理和错误恢复策略。先看状态管理。C语言子集要求区分字符串字面量、字符字面量、注释和普通代码。如果手写状态机你需要维护IN_STRING、IN_CHAR、IN_COMMENT等多个标志位并在每个字符读入时做大量if-else判断。而lex天然支持开始条件start conditions。在lexer.l里你一定能找到类似这样的定义%x STR CHAR COMMENT %% \ { BEGIN STR; return TOK_STRING_START; } \ { BEGIN CHAR; return TOK_CHAR_START; } /* { BEGIN COMMENT; return TOK_COMMENT_START; } STR\ { BEGIN INITIAL; return TOK_STRING_END; } CHAR\ { BEGIN INITIAL; return TOK_CHAR_END; } COMMENT*/{ BEGIN INITIAL; return TOK_COMMENT_END; }这里的%x STR声明了一个名为STR的排他性开始条件BEGIN STR则将lexer切换到该状态。这意味着当lexer处于STR状态时只有STR\这条规则会被触发其他所有规则包括匹配普通标识符的规则全部失效。这从根本上避免了手写状态机时常见的“状态泄露”问题——比如在字符串里遇到/误判为除法运算符。lex的状态机是编译期确定的无歧义、无竞态。再看错误恢复。真实编译器不能因为一个非法字符就整个挂掉。lexer.l里必然包含类似这样的兜底规则.|\n { fprintf(stderr, Lexical error at line %d, col %d: unrecognized char %c\n, yylineno, yycolumn, yytext[0]); yyerror_count; return TOK_ERROR; }注意两点一是它捕获了换行符\n确保行号计数器yylineno准确二是它返回TOK_ERROR而非直接exit(1)把错误处理权交给上层parser实验二。这体现了编译器设计的核心哲学前端各阶段职责分离错误应尽可能向后传递由更高层决定如何处理。你在rd.c里一定会看到对TOK_ERROR的专门处理分支比如跳过当前token继续解析而不是直接报错退出。2.2 关键Token识别细节与易错点解析我们来深挖几个高频出错的token规则它们暴露了词法分析的深层逻辑1. 整数字面量Integer Literals的歧义处理C语言要求0x1A是十六进制0123是八进制123是十进制。但正则0[xX][0-9a-fA-F]和0[0-7]存在重叠012既匹配八进制规则也匹配十进制规则因为0开头的十进制数是非法的但正则引擎可能贪婪匹配。lexer.l的正确解法是按优先级顺序书写规则0[xX][0-9a-fA-F] { yylval.int_val strtol(yytext2, NULL, 16); return TOK_INT; } 0[0-7] { yylval.int_val strtol(yytext, NULL, 8); return TOK_INT; } [1-9][0-9]* { yylval.int_val atoi(yytext); return TOK_INT; } 0 { yylval.int_val 0; return TOK_INT; }lex规则按书写顺序匹配引擎一旦找到第一条匹配规则就停止。所以0x1A只会被第一行捕获012被第二行捕获123被第三行捕获0被第四行捕获。如果你把0放在最前面那所有以0开头的数字都会被当成字面量0后面的规则永远不执行。2. 标识符与关键字的冲突消解if、while、return既是关键字也是合法标识符比如变量名if_flag。lexer.l必须确保if被识别为TOK_IF而if_flag被识别为TOK_ID。标准做法是先匹配关键字再匹配标识符if { return TOK_IF; } while { return TOK_WHILE; } return { return TOK_RETURN; } [a-zA-Z_][a-zA-Z0-9_]* { yylval.str_val strdup(yytext); return TOK_ID; }这里的关键是[a-zA-Z_][a-zA-Z0-9_]*必须写在所有关键字规则之后。因为lex匹配最长前缀if_flag的最长前缀是整个字符串但它不匹配任何关键字规则所以会落到标识符规则上。而单独的if既匹配关键字规则也匹配标识符规则但关键字规则位置更靠前因此优先生效。3. 运算符的最长匹配原则、!、、这些双字符运算符必须确保不会被拆成两个单字符运算符。lexer.l里你会看到 { return TOK_EQ; } ! { return TOK_NE; } { return TOK_GE; } { return TOK_LE; } { return TOK_ASSIGN; } { return TOK_PLUS; }注意必须写在之前。否则输入时lex会先匹配第一个返回TOK_ASSIGN剩下的再被匹配一次变成两个赋值号彻底错乱。这是lex最经典的“最长匹配”陷阱几乎所有初学者都在这里栽过跟头。2.3 Makefile与测试验证的工程实践意义lab1/Makefile绝非简单的gcc -o lexer lexer.l。它通常包含LEX flex CC gcc CFLAGS -Wall -Wextra -g lexer: lexer.l $(LEX) -o lexer.c lexer.l $(CC) $(CFLAGS) -o $ lexer.c -lfl test: lexer echo Running lexical tests for f in test*.c; do \ echo Testing $$f...; \ ./lexer $$f | grep -v ^$$ | head -20; \ done .PHONY: test clean clean: rm -f lexer lexer.c这个Makefile教会你的是可重复、可追踪的构建流程。flex -o lexer.c lexer.l将.l文件编译成C源码这是lex的工作原理——它本质是个代码生成器把声明式的词法规则翻译成高效的C状态机代码。-lfl链接flex库提供yylex()等基础函数。test目标里的for循环强制你面对多个测试用例而不是只盯着test.c一个文件。而grep -v ^$$是为了过滤掉shell提示符如果在交互式终端运行head -20则是防止长输出刷屏。这些细节都是工业级工具链的缩影。check.py的验证逻辑更值得玩味。它不会简单地diff lexer_output.txt expected_output.txt而是会- 忽略所有空白符空格、制表符、换行符的差异- 将TOK_ID main和TOK_ID foo视为同一类token只比对token类型不比对具体字符串值因为变量名是任意的- 对数字字面量会尝试int()转换后比对数值而非字符串避免012和10的字符串差异- 统计TOK_ERROR出现次数并与预设阈值比较。这种“语义等价”而非“字面等价”的校验才是编译器测试的正确姿势。它逼着你思考什么才是token流的本质是具体的字符序列还是其承载的语法范畴答案显然是后者。3. 实验二深度拆解递归下降解析器不是语法树的搬运工而是语义约束的守门人3.1 为什么选择递归下降而非Yacc/Bison实验二要求用C手写递归下降RD解析器而非用Yacc生成。这绝非偷懒而是教学上的精准设计。Yacc生成的是LALR(1)解析器强大但抽象而RD解析器是语法结构的直接映射每一个函数对应一个文法规则每一行if (lookahead TOK_IF)都直白地告诉你“此刻我正在期待一个if关键字”。更重要的是RD让你能无缝嵌入语义动作。在Yacc里语义动作{ $$ ... }是嵌在产生式末尾的黑箱而在RD里parse_if_statement()函数内部你可以在匹配if后立刻检查括号是否匹配在匹配then分支后立刻调用parse_expression()并在返回前做类型检查。这种“边解析边检查”的能力是理解编译器如何实施静态语义约束如类型兼容性、作用域规则的绝佳入口。rd.c的骨架一定是这样组织的// 全局变量指向当前token的指针 extern token_t* current_token; // 前向声明所有parse_*函数 ast_node_t* parse_program(); ast_node_t* parse_function_def(); ast_node_t* parse_statement(); ast_node_t* parse_expression(); // 主入口 ast_node_t* parse_program() { ast_node_t* root new_ast_node(NODE_PROGRAM); while (current_token-type ! TOK_EOF) { if (current_token-type TOK_INT) { // 匹配 int func_name(...) { ... } append_child(root, parse_function_def()); } else { syntax_error(Expected function definition); break; } } return root; }注意current_token是全局的parse_*函数通过移动它来推进解析。这种设计简单粗暴但极其清晰解析器的状态就是current_token所指的位置。3.2 表达式解析运算符优先级与结合性的代码化实现C语言表达式解析的难点在于如何用递归函数体现和*的优先级差异。rd.c里必然存在类似这样的经典结构ast_node_t* parse_expression() { return parse_additive_expression(); // 最低优先级 - } ast_node_t* parse_additive_expression() { ast_node_t* left parse_multiplicative_expression(); // 更高优先级* / while (current_token-type TOK_PLUS || current_token-type TOK_MINUS) { token_t op *current_token; consume_token(); // 移动current_token到下一个 ast_node_t* right parse_multiplicative_expression(); left new_binary_op_node(op.type, left, right); } return left; } ast_node_t* parse_multiplicative_expression() { ast_node_t* left parse_primary_expression(); // 最高优先级字面量、括号 while (current_token-type TOK_STAR || current_token-type TOK_SLASH) { token_t op *current_token; consume_token(); ast_node_t* right parse_primary_expression(); left new_binary_op_node(op.type, left, right); } return left; }这就是递归下降实现运算符优先级的标准范式用函数调用栈的深度来编码优先级。parse_additive_expression()调用parse_multiplicative_expression()意味着和-的解析必须等待所有*和/完成。当parse_additive_expression()看到时它已经把左边的整个乘法子表达式如a * b / c构造成了一个完整的AST节点然后才去解析右边的乘法子表达式。这天然保证了a b * c被解析为(a, *(b, c))而非(*(a, b), c)。结合性左结合则由while循环体现。对于a - b - cparse_additive_expression()第一次迭代left a,op -,right b, 构造-(a,b)第二次迭代left -(a,b),op -,right c, 构造-(-(a,b), c)。如果是右结合如^幂运算就需要改成递归调用自身。3.3 语句解析中的控制流与作用域雏形parse_if_statement()和parse_while_statement()不仅是语法检查更是作用域和控制流图CFG的起点。看一个典型实现ast_node_t* parse_if_statement() { expect_token(TOK_IF); // 消耗if关键字 expect_token(TOK_LPAREN); // 消耗( ast_node_t* cond parse_expression(); // 解析条件表达式 expect_token(TOK_RPAREN); // 消耗) ast_node_t* then_body parse_statement(); // 解析then分支单条语句 ast_node_t* else_body NULL; if (current_token-type TOK_ELSE) { consume_token(); else_body parse_statement(); // 解析else分支 } return new_if_node(cond, then_body, else_body); }这里expect_token()是一个关键辅助函数它检查current_token是否为期望类型是则consume_token()否则报错。这个看似简单的函数是语法错误定位的基石。当expect_token(TOK_RPAREN)失败时current_token还停在错误位置你可以精确报告“第5行缺少’)’”。更深层的意义在于parse_if_statement()返回的ast_node_t*其node_type是NODE_IF内部存储了cond、then_body、else_body三个子节点。这个结构就是后续类型检查cond必须是整型、代码生成生成br i1 %cond, label %then, label %else的直接依据。它把语法结构固化成了内存里的树形数据完成了从“字符串”到“可计算对象”的第一次质变。4. 实验三深度拆解AST不是语法的复刻而是语义的浓缩与优化的起点4.1 AST节点设计哲学为什么需要NODE_ASSIGN而不仅仅是NODE_BINARY_OPast.h和node_type.h定义了所有AST节点类型。初看可能觉得冗余a b c既可以表示为NODE_BINARY_OP操作符也可以表示为NODE_ASSIGN。但这种区分至关重要。NODE_ASSIGN是一个语义节点它明确宣告“这是一个赋值操作左侧必须是可寻址的左值lvalue右侧必须是右值rvalue”。而NODE_BINARY_OP是一个语法节点它只表示“两个操作数用某个运算符连接”。在后续的类型检查阶段NODE_ASSIGN的检查逻辑是- 检查left子节点是否为NODE_ID变量或NODE_ARRAY_REF数组元素等合法左值- 检查right子节点的类型是否与left兼容如int x; x 3.14;应报错- 而NODE_BINARY_OP的检查逻辑是检查左右操作数类型是否支持该运算如int int合法int string非法。如果混用类型检查器就会一团糟。node_type.h里清晰的枚举typedef enum { NODE_PROGRAM, NODE_FUNCTION_DEF, NODE_BLOCK, NODE_ASSIGN, // 专用于赋值 NODE_BINARY_OP, // 专用于 - * /等运算 NODE_UNARY_OP, // 专用于! -等 NODE_IF, NODE_WHILE, NODE_RETURN, NODE_ID, NODE_INT_LITERAL, NODE_STRING_LITERAL, NODE_ARRAY_REF, // a[i] } node_type_t;这种设计是把编译器的语义分析责任前置到了AST构建阶段。parser不再只是“忠实还原语法”而是主动进行初步的语义分类。这极大简化了后续pass的逻辑。4.2 内存管理为什么AST节点必须手动malloc/freeast.c里充斥着malloc(sizeof(ast_node_t))和free(node)。这不是C语言的陋习而是编译器工程的必然选择。想象一下一个包含1000个节点的AST如果用栈上分配ast_node_t node;会瞬间撑爆栈空间默认栈只有8MB。堆分配malloc是唯一可行方案。但随之而来的是内存泄漏风险。ast.c必然提供free_ast_node(ast_node_t* node)函数它采用后序遍历void free_ast_node(ast_node_t* node) { if (!node) return; // 先释放所有子节点 for (int i 0; i node-num_children; i) { free_ast_node(node-children[i]); } // 再释放自己 if (node-node_type NODE_ID || node-node_type NODE_STRING_LITERAL) { free(node-str_val); // 释放字符串内容 } free(node); }这个函数揭示了AST的树状生命周期父节点的生命周期必须长于所有子节点。free_ast_node(root)会递归释放整棵树。如果你在parse_*函数里忘了malloc或者在free_ast_node()里忘了free(node-str_val)程序就会崩溃或泄漏。这正是实验三要你亲手写的——不是为了炫技而是让你深刻体会编译器是一个内存敏感的系统程序每一块malloc都必须有对应的free否则生成的代码再漂亮运行时也会一地鸡毛。4.3 AST遍历与打印可视化是调试一切的基础ast.c里一定有print_ast_node(ast_node_t* node, int indent)函数。它的作用远超“打印出来看看”它是调试AST构建正确性的唯一可靠手段。一个典型的实现void print_ast_node(ast_node_t* node, int indent) { if (!node) return; // 打印缩进 for (int i 0; i indent; i) printf( ); // 打印节点类型和关键信息 switch(node-node_type) { case NODE_ASSIGN: printf(ASSIGN\n); print_ast_node(node-children[0], indent1); // left print_ast_node(node-children[1], indent1); // right break; case NODE_BINARY_OP: printf(BINARY_OP (%s)\n, op_to_string(node-op)); print_ast_node(node-children[0], indent1); // left print_ast_node(node-children[1], indent1); // right break; case NODE_ID: printf(ID (%s)\n, node-str_val); break; case NODE_INT_LITERAL: printf(INT_LITERAL (%d)\n, node-int_val); break; default: printf(NODE_%s\n, node_type_to_string(node-node_type)); } }当你运行./rd test.c | ./ast_printer看到的是一棵层次分明的树。如果a b c被错误地解析为ASSIGN - (ID a) - (BINARY_OP ) - (ID b) - (ID c)那说明parse_expression()没被正确调用如果看到ASSIGN - (ID a) - (ID b) - (ID c)那说明根本没被识别成运算符。这种可视化把抽象的语法结构变成了肉眼可辨的图形是调试不可替代的利器。我见过太多学生在print_ast_node()输出一片混乱后才恍然大悟原来自己的parse_expression()函数压根没被调用问题出在parse_statement()里漏掉了对表达式的处理分支。5. 实验四深度拆解LLVM IR生成不是字符串拼接而是类型系统与控制流的精密编排5.1 为什么选择文本格式LLVM IR而非直接调用LLVM C APIgenllvm.c生成的是.ll文件而非用LLVMAddFunction()等C API动态构建IR。这是教学上的明智之选。LLVM C API功能强大但学习曲线陡峭涉及LLVMContext、LLVMModuleRef、LLVMBuilderRef等数十个概念极易让初学者迷失在API细节中而忽略了IR本身的语义。文本格式IR.ll则像一本打开的汇编手册每一行都清晰可见%t1 add i32 %a, %bbr i1 %cond, label %then, label %else。你可以用cat output.ll直接阅读用llc直接编译用opt -S做优化整个工具链透明、可调试、无黑箱。genllvm.c的核心任务就是将AST的树形结构翻译成LLVM IR的线性指令序列并维护好基本块Basic Block和控制流。这要求你深刻理解LLVM的几个核心概念值Value与寄存器%tN每个计算结果如a b在IR中都是一个Value用%tN命名。genllvm.c必须为每个NODE_BINARY_OP、NODE_ID等生成唯一的寄存器名。基本块Basic BlockIR的最小执行单元以label:开头以控制流指令br,ret结尾。NODE_IF和NODE_WHILE必须生成多个基本块%if.then,%if.else,%if.end。Phi节点%phi用于SSA静态单赋值形式合并来自不同控制流路径的值。genllvm.c在生成NODE_IF时如果then和else分支都给同一个变量赋了值就必须插入%x phi i32 [ %x_then, %if.then ], [ %x_else, %if.else ]。5.2 从AST到IR一个赋值语句的完整翻译过程以int x a b;为例其AST是NODE_ASSIGN ├── NODE_ID x └── NODE_BINARY_OP () ├── NODE_ID a └── NODE_ID bgenllvm.c的gen_llvm_for_ast()函数会这样工作为左值x分配存储空间%x alloca i32, align 4。注意alloca是在栈上分配align 4指定4字节对齐这是x86-64 ABI的要求。递归生成右值a b的IRgen_llvm_for_ast(a_id_node)→ 加载a的值%a_val load i32, i32* %a, align 4gen_llvm_for_ast(b_id_node)→ 加载b的值%b_val load i32, i32* %b, align 4gen_llvm_for_ast(add_node)→ 执行加法%sum add i32 %a_val, %b_val将结果存入x的地址store i32 %sum, i32* %x, align 4整个过程genllvm.c必须维护一个符号表Symbol Table记录每个NODE_ID如x,a,b对应的LLVM值%x,%a,%b。这个符号表通常是char*到LLVMValueRef的哈希映射但在文本IR生成中它简化为一个char*到寄存器名字符串如%x的映射。genllvm.c里必然有类似get_or_create_register_for_id(x)的函数它首次调用时创建%x后续调用直接返回。5.3 控制流生成if/while背后的LLVM基本块艺术NODE_IF的IR生成是实验四的巅峰挑战。它要求你手动管理基本块的创建、跳转和Phi节点的插入。genllvm.c中gen_llvm_for_if()的伪代码逻辑如下void gen_llvm_for_if(ast_node_t* if_node) { // 1. 为当前if生成唯一标签 static int if_counter 0; char then_label[32], else_label[32], end_label[32]; sprintf(then_label, if.then%d, if_counter); sprintf(else_label, if.else%d, if_counter); sprintf(end_label, if.end%d, if_counter); if_counter; // 2. 生成条件判断br i1 %cond, label %if.then, label %if.else ast_node_t* cond if_node-children[0]; char* cond_reg gen_llvm_for_ast(cond); // 返回类似 %cond printf( br i1 %s, label %%%s, label %%%s\n, cond_reg, then_label, else_label); // 3. 生成then分支基本块 printf(\n%s:\n, then_label); gen_llvm_for_ast(if_node-children[1]); // then_body printf( br label %%%s\n, end_label); // then分支末尾跳转到end // 4. 生成else分支基本块如果存在 if (if_node-num_children 2 if_node-children[2]) { printf(\n%s:\n, else_label); gen_llvm_for_ast(if_node-children[2]); // else_body printf( br label %%%s\n, end_label); // else分支末尾跳转到end } else { // 如果没有else直接生成空else块 printf(\n%s:\n, else_label); printf( br label %%%s\n, end_label); } // 5. 生成end基本块 printf(\n%s:\n, end_label); // 此处可以插入Phi节点如果需要合并来自then/else的值 }这段代码展示了LLVM IR生成的核心模式标签驱动的控制流。br指令是唯一的无条件跳转br i1 %cond, ...是有条件跳转。then和else块必须以br结尾否则IR不合法LLVM会报错“Block not terminated with a terminator instruction”。end块是合并点如果then和else都给变量x赋了值你就必须在这里插入%x phi i32 [ %x_then, %if.then ], [ %x_else, %if.else ]。genllvm.c里必然有专门处理Phi节点的逻辑它需要在生成then和else块时就记录下每个变量在各自块内的寄存器名留待end块生成时使用。6. 全流程贯通与调试实战如何用这套资源真正搞懂编译器6.1 四步调试法从输入源码到最终汇编的端到端追踪拿到test.c不要急于make all。按以下四步亲手走一遍数据流Step 1: 看词法Lexercd lab1 ./lexer ../test.c观察输出是否所有关键字、标识符、数字都被正确识别0x1A是否是TOK_INTif_flag是否是TOK_ID如果被识别为两个TOK_ASSIGN立刻回去改lexer.l。Step 2: 看语法Parsercd lab2 ./rd ../test.c这个输出应该是AST的文本表示如果ast_printer已集成。重点看结构int main() { ... }是否被解析为NODE_FUNCTION_DEFif (x 0) x x 1;是否被解析为NODE_IF节点其子节点是否正确包含了NODE_BINARY_OP ()和NODE_ASSIGN如果结构错乱问题一定出在rd.c的parse_*函数逻辑或current_token移动上。Step 3: 看中间代码CodeGencd lab4 ./genllvm ../test.c output.ll cat output.ll检查output.ll是否有define i32 main()%x alloca i32是否出现%sum add i32 %a, %b是否在store之前if语句是否生成了%if.then1,%if.else1,%if.end1三个标签br指令是否完整如果output.ll语法错误llc报错用llvm-as -o /dev/null output.ll 21快速验证。Step 4: 看最终产物Assemblyllc -marchx86-64 -filetypeasm output.ll -o output.s cat output.s看output.s里的汇编指令movl、addl、cmpl、jle是否符合预期main:标签下是否有ret这一步验证了LLVM后端是否正确接收了你的IR。这套方法把编译器从一个黑箱拆解成了四个可触摸、可验证的白箱。每一次cat、grep、llc都是你与编译器的一次直接对话。6.2 check.py的高级用法不只是比对更是测试驱动开发TDD的启蒙check.py是这套资源的灵魂。不要只把它当“答案核对器”要把它当“测试框架”来用。添加自己的测试用例在lab4/下新建my_test.c写一个你认为有挑战性的代码如int a[10]; a[5] 3;然后运行python check.py my_test.c。如果失败check.py会告诉你期望的IR和实际IR的差异在哪一行。根据这个差异反向推导genllvm.c里哪个parse_*函数或gen_llvm_for_*函数出了问题。理解check.py的比对逻辑打开check.py你会发现它用正则提取IR中的关键模式比如r%\w\s\sadd\si32匹配加法指令rbr\si1\s%.*,\slabel\s%\w,\slabel\s%\w匹配if跳转。这教会你自动化测试的本质是定义可量化的、稳定的输出特征。你写的每一行IR都应该能被一个正则表达式捕获。用check.py做回归测试每次修改genllvm.c后不要只测一个文件而是运行for f in *.c; do python check.py $f; done。确保你的修改没有破坏已有功能。这是工业界CI/CD的雏形。6.3 从“做完”到“做透”三个值得深入的拓展方向这套资源的价值远不止于完成四个实验。它是一块跳板通往更广阔的编译器世界1. 添加类型检查Type Checker在lab3和lab4之间插入一个新阶段typecheck.c。它遍历AST为每个NODE_ID查找其声明int x;记录类型检查NODE_BINARY_OP的操作数类型是否兼容检查NODE_ASSIGN的左右类型是否匹配。这会让你第一次体会到语法正确的程序语义未必正确。int x; x hello;在lab2能通过但在typecheck阶段必须报错。2. 实现简单的优化Optimization修改genllvm.c在生成IR前加入常量折叠Constant Folding如果NODE_BINARY_OP的左右孩子都是NODE_INT_LITERAL直接计算结果生成%t1 add i32 3, 4→%t1 add i32 7, 0或直接%t1 i32 7。这会让你明白优化不是在汇编层面而是在IR层面进行的且必须保证语义等价。3. 支持更多C特性给lexer.l添加浮点数字面量[0-9]\.[0-9]给rd.c添加for循环解析给ast.h添加NODE_FOR节点给genllvm.c添加for的IR生成需要%i phi和循环后置更新。这会让你亲身体验语言特性的增加不是零散的补丁而是贯穿词法、语法、AST、IR四个阶段的系统性工程。最后分享一个小技巧在lab4/Makefile里把genllvm的编译命令加上-DDEBUG宏定义然后在genllvm.c里用#ifdef DEBUG ... #endif包裹详细的printf日志。比如在gen_llvm_for_if()开头打印Generating IF node...在每个printf( br ...)前打印Emitting branch...。这样当你make ./genllvm test.c时就能看到IR生成的每一步决策比单纯看output.ll更能洞察代码逻辑。这就是资深编译器工程师的日常调试方式。本文还有配套的精品资源点击获取简介这个资源包包含电子科技大学编译原理课程前四个实验的可运行参考实现覆盖整个前端到中间代码生成流程。实验一用lex编写词法分析器能识别C语言子集的关键字、标识符、数字、运算符等token实验二基于C语言实现递归下降语法分析器支持表达式、赋值、if/while语句等常见结构的语法解析实验三完成抽象语法树AST构建定义了完整的节点类型与内存管理逻辑并提供遍历和打印功能实验四通过遍历AST生成符合LLVM 14规范的文本格式IR代码输出结果可直接用llc工具编译为本地汇编。所有实验均配备Makefile一键编译脚本、多个测试源文件如test.c、lab4-test_example.c以及Python校验脚本check.py用于比对输出结果是否符合预期。整个代码在Ubuntu 20.04环境验证通过目录结构清晰关键函数和数据结构均有中文注释适合学生对照课堂内容理解编译各阶段作用、调试报错、撰写实验报告或拓展修改。本文还有配套的精品资源点击获取
电子科大编译原理四次实验完整实现：从词法识别到LLVM代码生成
本文还有配套的精品资源点击获取简介这个资源包包含电子科技大学编译原理课程前四个实验的可运行参考实现覆盖整个前端到中间代码生成流程。实验一用lex编写词法分析器能识别C语言子集的关键字、标识符、数字、运算符等token实验二基于C语言实现递归下降语法分析器支持表达式、赋值、if/while语句等常见结构的语法解析实验三完成抽象语法树AST构建定义了完整的节点类型与内存管理逻辑并提供遍历和打印功能实验四通过遍历AST生成符合LLVM 14规范的文本格式IR代码输出结果可直接用llc工具编译为本地汇编。所有实验均配备Makefile一键编译脚本、多个测试源文件如test.c、lab4-test_example.c以及Python校验脚本check.py用于比对输出结果是否符合预期。整个代码在Ubuntu 20.04环境验证通过目录结构清晰关键函数和数据结构均有中文注释适合学生对照课堂内容理解编译各阶段作用、调试报错、撰写实验报告或拓展修改。1. 项目概述这不是一份“参考答案”而是一套可调试、可拆解、可延伸的编译流水线沙盒你手头这份“电子科大编译原理四次实验完整实现”表面看是课程作业的参考代码但真正价值远不止于此——它是一套高度结构化、阶段解耦、边界清晰、输出可验证的编译前端教学沙盒。我带过三届编译原理实验课也帮学生debug过上百份lab1的lex规则冲突、lab3的AST内存泄漏、lab4的LLVM IR语法报错最常听到的一句话是“老师我跑通了但不知道哪一步在干啥。” 这份资源就是为解决这个根本痛点而生的。它严格遵循经典编译器前端四阶段模型词法分析 → 语法分析 → 抽象语法树构建 → 中间代码生成每个实验对应一个独立可运行模块且模块之间通过明确定义的数据结构如token_t、ast_node_t和接口函数如parse_expression()、gen_llvm_for_ast()进行通信不搞黑箱粘连。关键词里提到的“词法分析器”“递归下降解析”“AST构建”“LLVM IR生成”不是并列的四个名词而是一条有向数据流lexer输出token流喂给parserparser构造AST节点树AST再被codegen遍历翻译成LLVM IR文本。这种设计让你能像拧开阀门一样单独测试任一环节——比如把test.c喂给lexer看它吐出哪些token或者跳过lexer手动构造一个AST节点直接扔给genllvm.c看IR是否符合预期。更关键的是它完全规避了教学中常见的两大陷阱一是“魔法式Makefile”很多参考实现把所有步骤打包进一个make all出错时根本分不清是词法错了还是IR语法错了二是“静态测试用例”只给一个test.c改一行就全崩。而本资源包里每个lab目录下都有多个渐进式测试文件test01.c,test02.c,lab4-test_example.c从最简int main(){return 0;}到含嵌套if/while/数组访问的复杂表达式配合check.py脚本做逐行文本比对不是简单diff而是忽略空格、注释、临时寄存器名差异后的语义等价判断相当于给你配了个自动阅卷老师。我在实验室亲眼见过学生用check.py发现自己的lab2在处理a b c * d时运算符优先级错了——因为生成的IR里%t1 add i32 %a, %b出现在%t2 mul i32 %c, %d之前而标准答案是反过来的。这种细节光靠肉眼读C代码根本抓不住。它面向的不是“想抄作业”的人而是“想搞懂编译器怎么呼吸”的人。你不需要会写lex或懂LLVM spec全文只要你会gcc -o lexer lexer.l、会./lexer test.c、会llc -marchx86-64 -filetypeasm output.ll -o output.s就能亲手触摸每个阶段的输入输出。接下来我会带你一层层剥开这颗洋葱告诉你每个.c、每个.l、每个Makefile规则背后的真实意图以及那些藏在注释里、没写进实验指导书里的关键细节。2. 实验一深度拆解lex词法分析器不只是正则匹配而是状态机与错误恢复的实战训练场2.1 核心设计逻辑为什么用lex而不是手写状态机看到lexer.l的第一反应可能是“不就是写一堆正则匹配关键字吗” 但电子科大这个实验的精妙之处在于它用lex实现了真正的词法分析器该有的健壮性而非玩具级匹配。核心在于两点状态管理和错误恢复策略。先看状态管理。C语言子集要求区分字符串字面量、字符字面量、注释和普通代码。如果手写状态机你需要维护IN_STRING、IN_CHAR、IN_COMMENT等多个标志位并在每个字符读入时做大量if-else判断。而lex天然支持开始条件start conditions。在lexer.l里你一定能找到类似这样的定义%x STR CHAR COMMENT %% \ { BEGIN STR; return TOK_STRING_START; } \ { BEGIN CHAR; return TOK_CHAR_START; } /* { BEGIN COMMENT; return TOK_COMMENT_START; } STR\ { BEGIN INITIAL; return TOK_STRING_END; } CHAR\ { BEGIN INITIAL; return TOK_CHAR_END; } COMMENT*/{ BEGIN INITIAL; return TOK_COMMENT_END; }这里的%x STR声明了一个名为STR的排他性开始条件BEGIN STR则将lexer切换到该状态。这意味着当lexer处于STR状态时只有STR\这条规则会被触发其他所有规则包括匹配普通标识符的规则全部失效。这从根本上避免了手写状态机时常见的“状态泄露”问题——比如在字符串里遇到/误判为除法运算符。lex的状态机是编译期确定的无歧义、无竞态。再看错误恢复。真实编译器不能因为一个非法字符就整个挂掉。lexer.l里必然包含类似这样的兜底规则.|\n { fprintf(stderr, Lexical error at line %d, col %d: unrecognized char %c\n, yylineno, yycolumn, yytext[0]); yyerror_count; return TOK_ERROR; }注意两点一是它捕获了换行符\n确保行号计数器yylineno准确二是它返回TOK_ERROR而非直接exit(1)把错误处理权交给上层parser实验二。这体现了编译器设计的核心哲学前端各阶段职责分离错误应尽可能向后传递由更高层决定如何处理。你在rd.c里一定会看到对TOK_ERROR的专门处理分支比如跳过当前token继续解析而不是直接报错退出。2.2 关键Token识别细节与易错点解析我们来深挖几个高频出错的token规则它们暴露了词法分析的深层逻辑1. 整数字面量Integer Literals的歧义处理C语言要求0x1A是十六进制0123是八进制123是十进制。但正则0[xX][0-9a-fA-F]和0[0-7]存在重叠012既匹配八进制规则也匹配十进制规则因为0开头的十进制数是非法的但正则引擎可能贪婪匹配。lexer.l的正确解法是按优先级顺序书写规则0[xX][0-9a-fA-F] { yylval.int_val strtol(yytext2, NULL, 16); return TOK_INT; } 0[0-7] { yylval.int_val strtol(yytext, NULL, 8); return TOK_INT; } [1-9][0-9]* { yylval.int_val atoi(yytext); return TOK_INT; } 0 { yylval.int_val 0; return TOK_INT; }lex规则按书写顺序匹配引擎一旦找到第一条匹配规则就停止。所以0x1A只会被第一行捕获012被第二行捕获123被第三行捕获0被第四行捕获。如果你把0放在最前面那所有以0开头的数字都会被当成字面量0后面的规则永远不执行。2. 标识符与关键字的冲突消解if、while、return既是关键字也是合法标识符比如变量名if_flag。lexer.l必须确保if被识别为TOK_IF而if_flag被识别为TOK_ID。标准做法是先匹配关键字再匹配标识符if { return TOK_IF; } while { return TOK_WHILE; } return { return TOK_RETURN; } [a-zA-Z_][a-zA-Z0-9_]* { yylval.str_val strdup(yytext); return TOK_ID; }这里的关键是[a-zA-Z_][a-zA-Z0-9_]*必须写在所有关键字规则之后。因为lex匹配最长前缀if_flag的最长前缀是整个字符串但它不匹配任何关键字规则所以会落到标识符规则上。而单独的if既匹配关键字规则也匹配标识符规则但关键字规则位置更靠前因此优先生效。3. 运算符的最长匹配原则、!、、这些双字符运算符必须确保不会被拆成两个单字符运算符。lexer.l里你会看到 { return TOK_EQ; } ! { return TOK_NE; } { return TOK_GE; } { return TOK_LE; } { return TOK_ASSIGN; } { return TOK_PLUS; }注意必须写在之前。否则输入时lex会先匹配第一个返回TOK_ASSIGN剩下的再被匹配一次变成两个赋值号彻底错乱。这是lex最经典的“最长匹配”陷阱几乎所有初学者都在这里栽过跟头。2.3 Makefile与测试验证的工程实践意义lab1/Makefile绝非简单的gcc -o lexer lexer.l。它通常包含LEX flex CC gcc CFLAGS -Wall -Wextra -g lexer: lexer.l $(LEX) -o lexer.c lexer.l $(CC) $(CFLAGS) -o $ lexer.c -lfl test: lexer echo Running lexical tests for f in test*.c; do \ echo Testing $$f...; \ ./lexer $$f | grep -v ^$$ | head -20; \ done .PHONY: test clean clean: rm -f lexer lexer.c这个Makefile教会你的是可重复、可追踪的构建流程。flex -o lexer.c lexer.l将.l文件编译成C源码这是lex的工作原理——它本质是个代码生成器把声明式的词法规则翻译成高效的C状态机代码。-lfl链接flex库提供yylex()等基础函数。test目标里的for循环强制你面对多个测试用例而不是只盯着test.c一个文件。而grep -v ^$$是为了过滤掉shell提示符如果在交互式终端运行head -20则是防止长输出刷屏。这些细节都是工业级工具链的缩影。check.py的验证逻辑更值得玩味。它不会简单地diff lexer_output.txt expected_output.txt而是会- 忽略所有空白符空格、制表符、换行符的差异- 将TOK_ID main和TOK_ID foo视为同一类token只比对token类型不比对具体字符串值因为变量名是任意的- 对数字字面量会尝试int()转换后比对数值而非字符串避免012和10的字符串差异- 统计TOK_ERROR出现次数并与预设阈值比较。这种“语义等价”而非“字面等价”的校验才是编译器测试的正确姿势。它逼着你思考什么才是token流的本质是具体的字符序列还是其承载的语法范畴答案显然是后者。3. 实验二深度拆解递归下降解析器不是语法树的搬运工而是语义约束的守门人3.1 为什么选择递归下降而非Yacc/Bison实验二要求用C手写递归下降RD解析器而非用Yacc生成。这绝非偷懒而是教学上的精准设计。Yacc生成的是LALR(1)解析器强大但抽象而RD解析器是语法结构的直接映射每一个函数对应一个文法规则每一行if (lookahead TOK_IF)都直白地告诉你“此刻我正在期待一个if关键字”。更重要的是RD让你能无缝嵌入语义动作。在Yacc里语义动作{ $$ ... }是嵌在产生式末尾的黑箱而在RD里parse_if_statement()函数内部你可以在匹配if后立刻检查括号是否匹配在匹配then分支后立刻调用parse_expression()并在返回前做类型检查。这种“边解析边检查”的能力是理解编译器如何实施静态语义约束如类型兼容性、作用域规则的绝佳入口。rd.c的骨架一定是这样组织的// 全局变量指向当前token的指针 extern token_t* current_token; // 前向声明所有parse_*函数 ast_node_t* parse_program(); ast_node_t* parse_function_def(); ast_node_t* parse_statement(); ast_node_t* parse_expression(); // 主入口 ast_node_t* parse_program() { ast_node_t* root new_ast_node(NODE_PROGRAM); while (current_token-type ! TOK_EOF) { if (current_token-type TOK_INT) { // 匹配 int func_name(...) { ... } append_child(root, parse_function_def()); } else { syntax_error(Expected function definition); break; } } return root; }注意current_token是全局的parse_*函数通过移动它来推进解析。这种设计简单粗暴但极其清晰解析器的状态就是current_token所指的位置。3.2 表达式解析运算符优先级与结合性的代码化实现C语言表达式解析的难点在于如何用递归函数体现和*的优先级差异。rd.c里必然存在类似这样的经典结构ast_node_t* parse_expression() { return parse_additive_expression(); // 最低优先级 - } ast_node_t* parse_additive_expression() { ast_node_t* left parse_multiplicative_expression(); // 更高优先级* / while (current_token-type TOK_PLUS || current_token-type TOK_MINUS) { token_t op *current_token; consume_token(); // 移动current_token到下一个 ast_node_t* right parse_multiplicative_expression(); left new_binary_op_node(op.type, left, right); } return left; } ast_node_t* parse_multiplicative_expression() { ast_node_t* left parse_primary_expression(); // 最高优先级字面量、括号 while (current_token-type TOK_STAR || current_token-type TOK_SLASH) { token_t op *current_token; consume_token(); ast_node_t* right parse_primary_expression(); left new_binary_op_node(op.type, left, right); } return left; }这就是递归下降实现运算符优先级的标准范式用函数调用栈的深度来编码优先级。parse_additive_expression()调用parse_multiplicative_expression()意味着和-的解析必须等待所有*和/完成。当parse_additive_expression()看到时它已经把左边的整个乘法子表达式如a * b / c构造成了一个完整的AST节点然后才去解析右边的乘法子表达式。这天然保证了a b * c被解析为(a, *(b, c))而非(*(a, b), c)。结合性左结合则由while循环体现。对于a - b - cparse_additive_expression()第一次迭代left a,op -,right b, 构造-(a,b)第二次迭代left -(a,b),op -,right c, 构造-(-(a,b), c)。如果是右结合如^幂运算就需要改成递归调用自身。3.3 语句解析中的控制流与作用域雏形parse_if_statement()和parse_while_statement()不仅是语法检查更是作用域和控制流图CFG的起点。看一个典型实现ast_node_t* parse_if_statement() { expect_token(TOK_IF); // 消耗if关键字 expect_token(TOK_LPAREN); // 消耗( ast_node_t* cond parse_expression(); // 解析条件表达式 expect_token(TOK_RPAREN); // 消耗) ast_node_t* then_body parse_statement(); // 解析then分支单条语句 ast_node_t* else_body NULL; if (current_token-type TOK_ELSE) { consume_token(); else_body parse_statement(); // 解析else分支 } return new_if_node(cond, then_body, else_body); }这里expect_token()是一个关键辅助函数它检查current_token是否为期望类型是则consume_token()否则报错。这个看似简单的函数是语法错误定位的基石。当expect_token(TOK_RPAREN)失败时current_token还停在错误位置你可以精确报告“第5行缺少’)’”。更深层的意义在于parse_if_statement()返回的ast_node_t*其node_type是NODE_IF内部存储了cond、then_body、else_body三个子节点。这个结构就是后续类型检查cond必须是整型、代码生成生成br i1 %cond, label %then, label %else的直接依据。它把语法结构固化成了内存里的树形数据完成了从“字符串”到“可计算对象”的第一次质变。4. 实验三深度拆解AST不是语法的复刻而是语义的浓缩与优化的起点4.1 AST节点设计哲学为什么需要NODE_ASSIGN而不仅仅是NODE_BINARY_OPast.h和node_type.h定义了所有AST节点类型。初看可能觉得冗余a b c既可以表示为NODE_BINARY_OP操作符也可以表示为NODE_ASSIGN。但这种区分至关重要。NODE_ASSIGN是一个语义节点它明确宣告“这是一个赋值操作左侧必须是可寻址的左值lvalue右侧必须是右值rvalue”。而NODE_BINARY_OP是一个语法节点它只表示“两个操作数用某个运算符连接”。在后续的类型检查阶段NODE_ASSIGN的检查逻辑是- 检查left子节点是否为NODE_ID变量或NODE_ARRAY_REF数组元素等合法左值- 检查right子节点的类型是否与left兼容如int x; x 3.14;应报错- 而NODE_BINARY_OP的检查逻辑是检查左右操作数类型是否支持该运算如int int合法int string非法。如果混用类型检查器就会一团糟。node_type.h里清晰的枚举typedef enum { NODE_PROGRAM, NODE_FUNCTION_DEF, NODE_BLOCK, NODE_ASSIGN, // 专用于赋值 NODE_BINARY_OP, // 专用于 - * /等运算 NODE_UNARY_OP, // 专用于! -等 NODE_IF, NODE_WHILE, NODE_RETURN, NODE_ID, NODE_INT_LITERAL, NODE_STRING_LITERAL, NODE_ARRAY_REF, // a[i] } node_type_t;这种设计是把编译器的语义分析责任前置到了AST构建阶段。parser不再只是“忠实还原语法”而是主动进行初步的语义分类。这极大简化了后续pass的逻辑。4.2 内存管理为什么AST节点必须手动malloc/freeast.c里充斥着malloc(sizeof(ast_node_t))和free(node)。这不是C语言的陋习而是编译器工程的必然选择。想象一下一个包含1000个节点的AST如果用栈上分配ast_node_t node;会瞬间撑爆栈空间默认栈只有8MB。堆分配malloc是唯一可行方案。但随之而来的是内存泄漏风险。ast.c必然提供free_ast_node(ast_node_t* node)函数它采用后序遍历void free_ast_node(ast_node_t* node) { if (!node) return; // 先释放所有子节点 for (int i 0; i node-num_children; i) { free_ast_node(node-children[i]); } // 再释放自己 if (node-node_type NODE_ID || node-node_type NODE_STRING_LITERAL) { free(node-str_val); // 释放字符串内容 } free(node); }这个函数揭示了AST的树状生命周期父节点的生命周期必须长于所有子节点。free_ast_node(root)会递归释放整棵树。如果你在parse_*函数里忘了malloc或者在free_ast_node()里忘了free(node-str_val)程序就会崩溃或泄漏。这正是实验三要你亲手写的——不是为了炫技而是让你深刻体会编译器是一个内存敏感的系统程序每一块malloc都必须有对应的free否则生成的代码再漂亮运行时也会一地鸡毛。4.3 AST遍历与打印可视化是调试一切的基础ast.c里一定有print_ast_node(ast_node_t* node, int indent)函数。它的作用远超“打印出来看看”它是调试AST构建正确性的唯一可靠手段。一个典型的实现void print_ast_node(ast_node_t* node, int indent) { if (!node) return; // 打印缩进 for (int i 0; i indent; i) printf( ); // 打印节点类型和关键信息 switch(node-node_type) { case NODE_ASSIGN: printf(ASSIGN\n); print_ast_node(node-children[0], indent1); // left print_ast_node(node-children[1], indent1); // right break; case NODE_BINARY_OP: printf(BINARY_OP (%s)\n, op_to_string(node-op)); print_ast_node(node-children[0], indent1); // left print_ast_node(node-children[1], indent1); // right break; case NODE_ID: printf(ID (%s)\n, node-str_val); break; case NODE_INT_LITERAL: printf(INT_LITERAL (%d)\n, node-int_val); break; default: printf(NODE_%s\n, node_type_to_string(node-node_type)); } }当你运行./rd test.c | ./ast_printer看到的是一棵层次分明的树。如果a b c被错误地解析为ASSIGN - (ID a) - (BINARY_OP ) - (ID b) - (ID c)那说明parse_expression()没被正确调用如果看到ASSIGN - (ID a) - (ID b) - (ID c)那说明根本没被识别成运算符。这种可视化把抽象的语法结构变成了肉眼可辨的图形是调试不可替代的利器。我见过太多学生在print_ast_node()输出一片混乱后才恍然大悟原来自己的parse_expression()函数压根没被调用问题出在parse_statement()里漏掉了对表达式的处理分支。5. 实验四深度拆解LLVM IR生成不是字符串拼接而是类型系统与控制流的精密编排5.1 为什么选择文本格式LLVM IR而非直接调用LLVM C APIgenllvm.c生成的是.ll文件而非用LLVMAddFunction()等C API动态构建IR。这是教学上的明智之选。LLVM C API功能强大但学习曲线陡峭涉及LLVMContext、LLVMModuleRef、LLVMBuilderRef等数十个概念极易让初学者迷失在API细节中而忽略了IR本身的语义。文本格式IR.ll则像一本打开的汇编手册每一行都清晰可见%t1 add i32 %a, %bbr i1 %cond, label %then, label %else。你可以用cat output.ll直接阅读用llc直接编译用opt -S做优化整个工具链透明、可调试、无黑箱。genllvm.c的核心任务就是将AST的树形结构翻译成LLVM IR的线性指令序列并维护好基本块Basic Block和控制流。这要求你深刻理解LLVM的几个核心概念值Value与寄存器%tN每个计算结果如a b在IR中都是一个Value用%tN命名。genllvm.c必须为每个NODE_BINARY_OP、NODE_ID等生成唯一的寄存器名。基本块Basic BlockIR的最小执行单元以label:开头以控制流指令br,ret结尾。NODE_IF和NODE_WHILE必须生成多个基本块%if.then,%if.else,%if.end。Phi节点%phi用于SSA静态单赋值形式合并来自不同控制流路径的值。genllvm.c在生成NODE_IF时如果then和else分支都给同一个变量赋了值就必须插入%x phi i32 [ %x_then, %if.then ], [ %x_else, %if.else ]。5.2 从AST到IR一个赋值语句的完整翻译过程以int x a b;为例其AST是NODE_ASSIGN ├── NODE_ID x └── NODE_BINARY_OP () ├── NODE_ID a └── NODE_ID bgenllvm.c的gen_llvm_for_ast()函数会这样工作为左值x分配存储空间%x alloca i32, align 4。注意alloca是在栈上分配align 4指定4字节对齐这是x86-64 ABI的要求。递归生成右值a b的IRgen_llvm_for_ast(a_id_node)→ 加载a的值%a_val load i32, i32* %a, align 4gen_llvm_for_ast(b_id_node)→ 加载b的值%b_val load i32, i32* %b, align 4gen_llvm_for_ast(add_node)→ 执行加法%sum add i32 %a_val, %b_val将结果存入x的地址store i32 %sum, i32* %x, align 4整个过程genllvm.c必须维护一个符号表Symbol Table记录每个NODE_ID如x,a,b对应的LLVM值%x,%a,%b。这个符号表通常是char*到LLVMValueRef的哈希映射但在文本IR生成中它简化为一个char*到寄存器名字符串如%x的映射。genllvm.c里必然有类似get_or_create_register_for_id(x)的函数它首次调用时创建%x后续调用直接返回。5.3 控制流生成if/while背后的LLVM基本块艺术NODE_IF的IR生成是实验四的巅峰挑战。它要求你手动管理基本块的创建、跳转和Phi节点的插入。genllvm.c中gen_llvm_for_if()的伪代码逻辑如下void gen_llvm_for_if(ast_node_t* if_node) { // 1. 为当前if生成唯一标签 static int if_counter 0; char then_label[32], else_label[32], end_label[32]; sprintf(then_label, if.then%d, if_counter); sprintf(else_label, if.else%d, if_counter); sprintf(end_label, if.end%d, if_counter); if_counter; // 2. 生成条件判断br i1 %cond, label %if.then, label %if.else ast_node_t* cond if_node-children[0]; char* cond_reg gen_llvm_for_ast(cond); // 返回类似 %cond printf( br i1 %s, label %%%s, label %%%s\n, cond_reg, then_label, else_label); // 3. 生成then分支基本块 printf(\n%s:\n, then_label); gen_llvm_for_ast(if_node-children[1]); // then_body printf( br label %%%s\n, end_label); // then分支末尾跳转到end // 4. 生成else分支基本块如果存在 if (if_node-num_children 2 if_node-children[2]) { printf(\n%s:\n, else_label); gen_llvm_for_ast(if_node-children[2]); // else_body printf( br label %%%s\n, end_label); // else分支末尾跳转到end } else { // 如果没有else直接生成空else块 printf(\n%s:\n, else_label); printf( br label %%%s\n, end_label); } // 5. 生成end基本块 printf(\n%s:\n, end_label); // 此处可以插入Phi节点如果需要合并来自then/else的值 }这段代码展示了LLVM IR生成的核心模式标签驱动的控制流。br指令是唯一的无条件跳转br i1 %cond, ...是有条件跳转。then和else块必须以br结尾否则IR不合法LLVM会报错“Block not terminated with a terminator instruction”。end块是合并点如果then和else都给变量x赋了值你就必须在这里插入%x phi i32 [ %x_then, %if.then ], [ %x_else, %if.else ]。genllvm.c里必然有专门处理Phi节点的逻辑它需要在生成then和else块时就记录下每个变量在各自块内的寄存器名留待end块生成时使用。6. 全流程贯通与调试实战如何用这套资源真正搞懂编译器6.1 四步调试法从输入源码到最终汇编的端到端追踪拿到test.c不要急于make all。按以下四步亲手走一遍数据流Step 1: 看词法Lexercd lab1 ./lexer ../test.c观察输出是否所有关键字、标识符、数字都被正确识别0x1A是否是TOK_INTif_flag是否是TOK_ID如果被识别为两个TOK_ASSIGN立刻回去改lexer.l。Step 2: 看语法Parsercd lab2 ./rd ../test.c这个输出应该是AST的文本表示如果ast_printer已集成。重点看结构int main() { ... }是否被解析为NODE_FUNCTION_DEFif (x 0) x x 1;是否被解析为NODE_IF节点其子节点是否正确包含了NODE_BINARY_OP ()和NODE_ASSIGN如果结构错乱问题一定出在rd.c的parse_*函数逻辑或current_token移动上。Step 3: 看中间代码CodeGencd lab4 ./genllvm ../test.c output.ll cat output.ll检查output.ll是否有define i32 main()%x alloca i32是否出现%sum add i32 %a, %b是否在store之前if语句是否生成了%if.then1,%if.else1,%if.end1三个标签br指令是否完整如果output.ll语法错误llc报错用llvm-as -o /dev/null output.ll 21快速验证。Step 4: 看最终产物Assemblyllc -marchx86-64 -filetypeasm output.ll -o output.s cat output.s看output.s里的汇编指令movl、addl、cmpl、jle是否符合预期main:标签下是否有ret这一步验证了LLVM后端是否正确接收了你的IR。这套方法把编译器从一个黑箱拆解成了四个可触摸、可验证的白箱。每一次cat、grep、llc都是你与编译器的一次直接对话。6.2 check.py的高级用法不只是比对更是测试驱动开发TDD的启蒙check.py是这套资源的灵魂。不要只把它当“答案核对器”要把它当“测试框架”来用。添加自己的测试用例在lab4/下新建my_test.c写一个你认为有挑战性的代码如int a[10]; a[5] 3;然后运行python check.py my_test.c。如果失败check.py会告诉你期望的IR和实际IR的差异在哪一行。根据这个差异反向推导genllvm.c里哪个parse_*函数或gen_llvm_for_*函数出了问题。理解check.py的比对逻辑打开check.py你会发现它用正则提取IR中的关键模式比如r%\w\s\sadd\si32匹配加法指令rbr\si1\s%.*,\slabel\s%\w,\slabel\s%\w匹配if跳转。这教会你自动化测试的本质是定义可量化的、稳定的输出特征。你写的每一行IR都应该能被一个正则表达式捕获。用check.py做回归测试每次修改genllvm.c后不要只测一个文件而是运行for f in *.c; do python check.py $f; done。确保你的修改没有破坏已有功能。这是工业界CI/CD的雏形。6.3 从“做完”到“做透”三个值得深入的拓展方向这套资源的价值远不止于完成四个实验。它是一块跳板通往更广阔的编译器世界1. 添加类型检查Type Checker在lab3和lab4之间插入一个新阶段typecheck.c。它遍历AST为每个NODE_ID查找其声明int x;记录类型检查NODE_BINARY_OP的操作数类型是否兼容检查NODE_ASSIGN的左右类型是否匹配。这会让你第一次体会到语法正确的程序语义未必正确。int x; x hello;在lab2能通过但在typecheck阶段必须报错。2. 实现简单的优化Optimization修改genllvm.c在生成IR前加入常量折叠Constant Folding如果NODE_BINARY_OP的左右孩子都是NODE_INT_LITERAL直接计算结果生成%t1 add i32 3, 4→%t1 add i32 7, 0或直接%t1 i32 7。这会让你明白优化不是在汇编层面而是在IR层面进行的且必须保证语义等价。3. 支持更多C特性给lexer.l添加浮点数字面量[0-9]\.[0-9]给rd.c添加for循环解析给ast.h添加NODE_FOR节点给genllvm.c添加for的IR生成需要%i phi和循环后置更新。这会让你亲身体验语言特性的增加不是零散的补丁而是贯穿词法、语法、AST、IR四个阶段的系统性工程。最后分享一个小技巧在lab4/Makefile里把genllvm的编译命令加上-DDEBUG宏定义然后在genllvm.c里用#ifdef DEBUG ... #endif包裹详细的printf日志。比如在gen_llvm_for_if()开头打印Generating IF node...在每个printf( br ...)前打印Emitting branch...。这样当你make ./genllvm test.c时就能看到IR生成的每一步决策比单纯看output.ll更能洞察代码逻辑。这就是资深编译器工程师的日常调试方式。本文还有配套的精品资源点击获取简介这个资源包包含电子科技大学编译原理课程前四个实验的可运行参考实现覆盖整个前端到中间代码生成流程。实验一用lex编写词法分析器能识别C语言子集的关键字、标识符、数字、运算符等token实验二基于C语言实现递归下降语法分析器支持表达式、赋值、if/while语句等常见结构的语法解析实验三完成抽象语法树AST构建定义了完整的节点类型与内存管理逻辑并提供遍历和打印功能实验四通过遍历AST生成符合LLVM 14规范的文本格式IR代码输出结果可直接用llc工具编译为本地汇编。所有实验均配备Makefile一键编译脚本、多个测试源文件如test.c、lab4-test_example.c以及Python校验脚本check.py用于比对输出结果是否符合预期。整个代码在Ubuntu 20.04环境验证通过目录结构清晰关键函数和数据结构均有中文注释适合学生对照课堂内容理解编译各阶段作用、调试报错、撰写实验报告或拓展修改。本文还有配套的精品资源点击获取
