小型C编译器源码解析：词法分析、AST与栈帧布局全流程

简介这是一份小型C编译器实现的完整源代码适合正在学习编译原理、操作系统底层机制或希望深入理解C语言执行过程的开发者。源码按编译器工作流程组织覆盖词法分析、语法分析、语义分析、优化与代码生成五个核心阶段包含词法分析器、语法解析器、符号表管理、基本优化策略以及面向特定架构的代码生成器等模块也涉及指针、结构体、函数调用等C语言特性的处理。压缩包共86个文件以C源文件50个和头文件12个为主另有若干配置文件、批处理脚本、文本说明等整体仅210KB便于快速下载和研读。目前已有478人学习下载。通过阅读和修改这份代码能够清晰看到源代码如何一步步转化为可执行程序对后续编写高效代码、调试编译错误或自行开发编译器都很有帮助。1. 小型C编译器源码一条从token流到栈帧落地的完整链路拆完这套小型C编译器源码之后我最大的感受是编译器本质上不是复杂的魔法而是一条按顺序执行的文本处理流水线。这套源码在编译器的核心主线上相当完整——词法分析、递归下降语法分析、语义检查、代码生成四层都有对应的实现能覆盖变量声明、赋值、表达式运算、if/else、while 循环和函数调用这些最常见的 C 子集语法。第一次读它时我建议别急着找一个 main 函数从头看到尾而是先按模块边界去理解四个层面的职责调试的时候才不会一头扎进“去哪看报错”的黑匣子。适合读这份源码的人有两类一类是刚学完 C 语言和数据结构的在校学生想搞清楚“编译器到底怎么把指针和循环变成可运行的目标码”另一类是拿它做课程设计或二次原型的开发者想在一个不超过几千行的骨架上快速加入新语法。这篇笔记就按“词法 → 语法 → 代码生成 → 调试”的顺序来讲尽量把每一步能直接照抄的代码骨架和参数选择写清楚坑放在单独的章节里集中提。2. 词法与符号表实现状态机切 token 与作用域链管理2.1 词法分析器骨架先处理 EOF再处理字符类大多数小型编译器不会用 flex 这类词法生成器而是手写一个自包含的扫描器。这套源码的做法也是经典的逐字符读入维护一个全局的current_char和一个缓冲区。关键点在于状态机的顺序判断标识符、数字、运算符和分隔符之前先检查是否到达文件末尾。很多刚上手的人会先把isalpha、isdigit的分类逻辑写得很完整却忘了 EOF 分支结果在最后一个 token 之后出现越界读取。下面是这类扫描器最常见的主循环写法我用伪代码还原了它的核心结构跟你在这份源码里看到的 lexer 设计方向是一致的/* lexer.c —— 词法分析主循环 */ #include ctype.h #include stdio.h #define MAX_TOKEN_LEN 128 #define MAX_ID_LEN 64 typedef enum { TOK_EOF 0, TOK_ID, TOK_NUM, TOK_ASSIGN, TOK_PLUS, TOK_MINUS, TOK_STAR, TOK_SLASH, TOK_LPAREN, TOK_RPAREN, TOK_SEMI, TOK_LBRACE, TOK_RBRACE } TokenType; typedef struct { TokenType type; char text[MAX_TOKEN_LEN]; int value; /* 数字字面量使用 */ int line; /* 报错定位用 */ } Token; static FILE *src_file; static int current_char; static int line_num 1; static void next_char(void) { current_char fgetc(src_file); /* EOF 以 -1 出现必须先判 */ } Token get_next_token(void) { Token tok {0}; /* 跳过空白与换行换行时累积行号 */ while (isspace(current_char)) { if (current_char \n) line_num; next_char(); } if (current_char EOF) { tok.type TOK_EOF; tok.line line_num; return tok; } if (isalpha(current_char) || current_char _) { int i 0; while (isalnum(current_char) || current_char _) { if (i MAX_ID_LEN) tok.text[i] current_char; next_char(); } tok.text[i] \0; tok.type TOK_ID; tok.line line_num; return tok; } if (isdigit(current_char)) { int val 0; while (isdigit(current_char)) { val val * 10 (current_char - 0); next_char(); } tok.value val; tok.type TOK_NUM; tok.line line_num; return tok; } /* 运算符分支这里最容易漏掉对 // 注释的处理 */ switch (current_char) { case : tok.type TOK_PLUS; next_char(); break; case -: tok.type TOK_MINUS; next_char(); break; case *: tok.type TOK_STAR; next_char(); break; case /: next_char(); if (current_char /) { /* 行注释 */ while (current_char ! \n current_char ! EOF) next_char(); return get_next_token(); /* 递归调用跳过注释 */ } tok.type TOK_SLASH; break; case : tok.type TOK_ASSIGN; next_char(); break; case (: tok.type TOK_LPAREN; next_char(); break; case ): tok.type TOK_RPAREN; next_char(); break; case ;: tok.type TOK_SEMI; next_char(); break; case {: tok.type TOK_LBRACE; next_char(); break; case }: tok.type TOK_RBRACE; next_char(); break; default: fprintf(stderr, line %d: unexpected char %c\n, line_num, current_char); exit(1); } return tok; }逻辑说明get_next_token每次只返回一个 token词法分析器的状态会被压缩到极简主线就是“跳过空白 → 判断字符类别 → 读满一个词法单元”。写的时候我会把current_char的更新全部收敛到next_char()一个函数里这样后续要加“读入字符串字面量”“处理转义字符”都只改一处。参数说明MAX_TOKEN_LEN和MAX_ID_LEN一定要区分开。标识符长度限制在 64token 缓冲区留到 128是为了给将来扩展关键字表留出余量。如果你照抄这份代码去改建议把value字段的类型从int换成long否则在 32 位目标上处理大于 32767 的数组定义会溢出。2.2 符号表结构每个变量都要记住自己来自哪一层小型编译器通常不单独做一个复杂的类型系统但符号表作用域链必须实现。原因很直接C 语言的块作用域决定了int i 0;和{ int i 1; }不能互相覆盖。常见做法是维护一个“栈”每个作用域是一个哈希表进入花括号时压栈出花括号时弹栈。/* symtab.c —— 分层符号表 */ typedef struct Symbol { char *name; int type; /* 0:int 1:char 2:pointer */ int offset; /* 栈帧中的位置偏移 */ int scope_level; /* 记录在那一层作用域 */ struct Symbol *next; } Symbol; typedef struct Scope { Symbol *head; int level; struct Scope *parent; } Scope; static Scope *current_scope NULL; Scope *enter_scope(void) { Scope *s calloc(1, sizeof(Scope)); s-level current_scope ? current_scope-level 1 : 0; s-parent current_scope; current_scope s; return s; } void leave_scope(void) { Scope *old current_scope; current_scope old-parent; free(old); } Symbol *declare_symbol(const char *name, int type, int offset) { /* 查重必须在当前层做不能递归到父层 */ for (Symbol *s current_scope-head; s; s s-next) { if (strcmp(s-name, name) 0) { fprintf(stderr, redefinition of %s at level %d\n, name, current_scope-level); return NULL; } } Symbol *s calloc(1, sizeof(Symbol)); s-name strdup(name); s-type type; s-offset offset; s-scope_level current_scope-level; s-next current_scope-head; current_scope-head s; return s; }逻辑说明declare_symbol里的查重只查当前层不递归到父层。这是 C 语言块作用域的语义要求——内层同名变量遮蔽外层变量是合法行为。如果你把查重写成“全局查重”编译int x; { int x; }会误报这是很多从解释器转型写编译器的人最容易翻车的地方。参数说明scope_level这个字段平时不参与代码生成但调试符号表时很重要。我一般会在报错信息里把变量名和 level 一起打印出来排查“变量作用域提前释放”的问题能省一半时间。另外注意offset是相对栈帧基址的偏移不是绝对内存地址这个字段的真正用法在第四章的栈帧布局里才能体现出来。3. 递归下降语法分析与 AST 构造优先级、左递归与节点设计3.1 表达式优先级用分层解析替代优先级表这份源码在语法分析层采用的手法是递归下降表达式部分按“加减 → 乘除 → 一元 → 主表达式”分为四层。你不需要一个运算符优先级表因为每一层函数本身就编码了优先级调用链越深优先级越高。这种写法的好处是容易阅读和调试优先级表写错了很难一眼看出来递归下降则是一步一行都能用 gdb 跟到。/* parser.c —— 表达式优先级分层 */ typedef struct { Token current; TokenType prev_type; } Parser; static int parse_primary(Parser *p) { if (p-current.type TOK_NUM) { int v p-current.value; return v; /* 实际工程中返回 AST 节点指针 */ } if (p-current.type TOK_ID) { /* 查符号表取出变量 */ return lookup_symbol(p-current.text); } if (p-current.type TOK_LPAREN) { advance(p); /* 跳过左括号 */ int v parse_expr(p); expect(p, TOK_RPAREN, expected )); return v; } error(syntax error at line %d, p-current.line); return 0; } static int parse_unary(Parser *p) { if (p-current.type TOK_MINUS) { advance(p); int v parse_unary(p); return -v; } return parse_primary(p); } static int parse_mul(Parser *p) { int left parse_unary(p); while (p-current.type TOK_STAR || p-current.type TOK_SLASH) { TokenType op p-current.type; advance(p); int right parse_unary(p); if (op TOK_STAR) left left * right; else left left / right; } return left; } static int parse_add(Parser *p) { int left parse_mul(p); while (p-current.type TOK_PLUS || p-current.type TOK_MINUS) { TokenType op p-current.type; advance(p); int right parse_mul(p); if (op TOK_PLUS) left left right; else left left - right; } return left; }逻辑说明parse_add调用parse_mulparse_mul调用parse_unaryparse_unary调用parse_primary。这条链一旦成立1 2 * 3就不会被解析成(1 2) * 3。递归下降最经典的坑在上面代码的while循环里parse_add循环收集和-如果写成递归调用自身处理1 - 2 - 3就会变成左结合错误。多亏这份源码用了迭代而非递归才没有在这上面犯病。参数说明所有返回int的地方在完整版里都要换成 AST 节点指针。上面代码是为了说明优先级控制流实际操作中直接返回数值会丢失操作符位置信息语义分析和代码生成都需要节点树。如果你在改这份源码建议先建立struct Node结构体再逐层替换返回值。3.2 AST 节点设计与类型检查不要只建语法树还要带语义信息AST 节点设计直接影响代码生成器的复杂度。小型编译器常见的做法是用一个带kind字段的大结构体加联合体节点类型分为ND_NUM、ND_VAR、ND_ADD、ND_ASSIGN、ND_IF、ND_WHILE、ND_FUNCALL等。这比为每个语法结构单建一个结构体更适合教学源码因为代码生成就是一个大的 switch可读性高。在这份资源里AST 节点还应携带两个额外的语义字段type和is_lvalue。前者判断表达式结果是 int 还是指针后者告诉后端“这个节点能不能作为赋值目标”。不加is_lvalue的编译器在解析1 2时会尴尬地生成非法目标码。下面是节点结构与对应的语义检查要点/* ast.h —— 统一AST节点 */ typedef enum { ND_ADD, ND_SUB, ND_MUL, ND_DIV, ND_ASSIGN, ND_EQ, ND_NE, ND_LT, ND_LE, ND_VAR, ND_NUM, ND_IF, ND_WHILE, ND_BLOCK, ND_FUNCALL } NodeKind; typedef struct Node Node; struct Node { NodeKind kind; Node *lhs, *rhs; /* 二元运算使用 */ Node *cond, *then, *else_node; /* if/while */ Node *body; /* 块语句使用 */ char *func_name; /* 函数调用 */ int val; /* ND_NUM 的值 */ int type; /* 0:int 1:char 2:ptr */ int is_lvalue; /* 关键字段能否做赋值左值 */ }; int check_expr_type(Node *n) { switch (n-kind) { case ND_NUM: n-type 0; /* int */ n-is_lvalue 0; return 0; case ND_VAR: n-type get_var_type(n); n-is_lvalue 1; /* 变量天生是左值 */ return n-type; case ND_ASSIGN: if (!n-lhs-is_lvalue) { error(assignment to non-lvalue); } n-type check_expr_type(n-rhs); n-is_lvalue 0; return n-type; /* ND_ADD / ND_MUL 等运算类似略 */ default: return 0; } }逻辑说明check_expr_type在遍历表达式树时同时完成类型推导和左值检查。赋值表达式要求左操作数必须是左值1 2会在这一层被拦截不会漏到代码生成。这里有个容易被忽略的点ND_ASSIGN这个表达式的整体类型取右操作数的类型但is_lvalue置 0因为a 1的结果本身不是可赋值的目标。参数说明type字段建议用整数码而不是直接塞TYPE_INT宏方便将来扩展数组和结构体。当你为这个编译器增加指针运算时ND_ADD的分支就要判断“左操作数是指针、右操作数是 int”的情况需要额外记录一个ptr_base_type。这份源码短小正好留给你扩展指针时动手改。4. 代码生成与栈帧布局从 AST 到目标码的落地选择4.1 生成方向的选择x86 汇编还是自定义虚拟机小型 C 编译器的代码生成有两个主流方向直接生成 x86 汇编或者生成自定义字节码在虚拟机上运行。这份资源选择的是直接生成汇编理由是更接近真实编译器的行为也能让使用者直观看到“C 语言的一个加法在机器层面变成几条指令”。生成汇编的常见实现是 Ast 到文本的递归翻译。每个 AST 节点都对应若干汇编模板。例如ND_ADD的基本思路是先求右操作数压栈再求左操作数放入 eax弹栈到 edxadd eaxedx。在这份源码里所有表达式求值结果统一约定放在eax寄存器中超过一个寄存器需求的操作数通过栈传递。这个约定极大简化了代码生成器。4.2 栈帧布局与调用约定四个字节的坑栈帧设计是代码生成器里最容易出错的地方。局部变量的位置在编译期就得确定下来用rsp offset直接寻址。每个函数进入时依次做三件事压入rbp、保存返回地址、根据局部变量总大小下移rsp。源码里采用固定大小的栈帧不对局部变量做alloca这能让代码生成器免去动态栈帧管理的复杂度。/* codegen.c —— 函数入口的栈帧建立 */ static void emit_func_prologue(Function *fn, int local_size) { /* 局部变量空间按 8 字节对齐 */ local_size (local_size 7) ~7; printf( .globl %s\n, fn-name); printf(%s:\n, fn-name); printf( push rbp\n); printf( mov rbp, rsp\n); printf( sub rsp, %d\n, local_size); /* 保存被调用者保存寄存器 */ printf( push rbx\n); printf( push r12\n); /* 把栈上空间初始化为 0防止未初始化变量读到脏数据 */ for (int i 0; i local_size; i 8) { printf( mov QWORD PTR [rbp-%d], 0\n, i 8); } } static void emit_expr(Node *n) { switch (n-kind) { case ND_NUM: printf( mov eax, %d\n, n-val); break; case ND_VAR: /* 变量偏移在符号表中记录一般为负数 */ printf( mov eax, DWORD PTR [rbp-%d]\n, n-var_offset); break; case ND_ADD: emit_expr(n-rhs); printf( push rax\n); emit_expr(n-lhs); printf( pop rcx\n); printf( add eax, ecx\n); break; /* ND_SUB / ND_MUL / ND_DIV 类似略 */ } }逻辑说明这段代码体现了两个约定一是所有运算中间结果统一放rax需要暂存时压栈二是局部变量统一按rbp - offset寻址。这里有一个血泪经验在emit_func_prologue里如果先sub rsp再push rbx被保存寄存器的位置就会覆盖局部变量空间。正确的顺序是先 push 保存再 sub 分配局部空间或者把两者统一计入偏移量。这份源码的顺序是对的——先 push 后 sub。参数说明local_size按 8 字节对齐很关键。如果你不对齐连续声明char a; char b;时后面变量的 offset 计算会乱。另一种常见选择是 16 字节对齐因为 System V 调用约定要求rsp在函数调用前保持 16 字节对齐。教学向的源码通常只做到 8 字节够用但你要是打算在 Linux 上调用 libc 的printf得把对齐升级到 16 字节。/* 函数调用序列参数从右往左压栈 */ static void emit_funcall(Node *n) { /* 先把右起参数压栈 */ for (int i n-argc - 1; i 0; i--) { emit_expr(n-args[i]); printf( push rax\n); } printf( mov rax, 0\n); printf( call %s\n, n-func_name); printf( add rsp, %d\n, n-argc * 8); }参数说明这里参数宽度一律按 8 字节处理即使函数形参是int。这是因为 x86-64 的栈操作是以 8 字节为最小单位的压缩到 4 字节反而要多写几条 mov。初学者可能会为了省内存把 int 参数按 4 字节压栈结果后续取参数时全部错位这就是栈帧布局里最典型的翻车。栈帧的整体布局可以用这张表来表述位置内容说明rbp 8返回地址调用方压入rbp 0旧 rbp函数入口压入rbp - 4第一个局部变量int a 占 4 字节rbp - 8第二个局部变量对齐到 8 字节rbp - local_size栈帧底rsp 指向这里栈顶再往上调用参数调用子函数时压入5. 调试编译器的避坑记录四个高频翻车点与排查手段5.1 现象、原因与解决步骤从段错误到错误目标码编译器自身的 bug 比普通程序难调试因为它引入了一个中间层你看到的错误可能是生成的目标码有问题而不是编译器程序本身逻辑崩溃。这里把实践中最常遇到的四类问题列出来每条按现象、原因、解决来排查。现象原因解决编译出来的程序启动即段错误函数入口push rbp与sub rsp顺序颠倒或者局部变量 offset 出现正数给每个函数入口打印完整汇编核对 rbp 初始值前后的偏移变量互相覆盖后声明的把先声明的冲掉符号表enter_scope和leave_scope在块语句的创建时机不对提前弹栈在语法分析器的{处加断点确认enter_scope调用时机表达式结果翻倍或变成负数压栈参数宽度不对int按 4 字节压弹出时按 8 字节读统一用push rax压栈绝不直接压寄存器低位编译超大表达式时报错“编译器堆空间不足”每个节点都递归callocAST 释放不及时在expect出错分支主动free整棵子树或复用节点池第一个翻车点基本是刚写完 prologue 的人必踩的。现象通常是编译和链接都成功一运行就在函数第一行崩掉。原因是push rbp; mov rbp, rsp之后sub rsp的数值没有计入局部变量对齐导致rbp-4这个偏移访问到的是尚未分配的栈空间。第二个关于符号表弹栈时机的问题排查难度稍高一些。现象是在同一函数里声明两个同名变量第二个没报重定义错反而是第一个的值被改写。原因多半是enter_scope被放在了parse_block的尾部而不是头部导致局部作用域建立在全局作用域之上离开时把外层符号一并弹掉。我一般会开一个临时日志每次declare_symbol打印符号名和scope_level对比两层栈的 level 就一目了然。第三个是栈上参数宽度不一致。很多从教学代码起步的实现编译器内部用的是int存变量值生成汇编时直接push eax但弹出时用了pop rcx加add eax, ecx——看起来对实际因为 x86-64 压栈按 8 字节对齐push eax会把高 4 字节留在栈上弹出的组合全乱。最简单可靠的方案是任何寄存器都按 64 位压栈值本身如果是 32 位的转换由寻址方式完成。第四个是 AST 内存管理导致的崩溃。在递归下降解析出错时很多实现直接在error()里 exit省去了清理逻辑。但如果你做的是交互式的多文件编译provider 模式会自动重试解析别的源文件泄漏的内存累积到一定量就会触发“编译器的堆空间不足”。常见处理方法是给 AST 节点加free_node递归函数并在expect失败时调用它或者实现一个 arena 分配器编译完一个文件整体释放。5.2 排错三板斧pos 打印、AST 转储、反汇编对照遇到编译器自己行为诡异时不要盯着源码看直接看中间产物。第一板斧是在词法分析器里加一个print_token语句输入源文件后输出全部 token 流检查是不是切错了第二板斧是语法分析完成后、代码生成之前把 AST 用缩进方式打印出来每个节点一行包含 kind 和 val 字段第三板斧是检查生成汇编放到编译器的cc1单步模式下运行对每一句输入看汇编输出是否符合常识。在调试过程中我一般不依赖 gdb 单步跟踪编译器本身的递归函数因为递归展开太深跟着跟着就不知道自己站在哪一层了。与其追运行过程不如让编译器把关键中间态吐出来。常见做法是加一个-d命令行选项-dlex打印 token-dast打印语法树-dasm打印目标汇编。这套调试手段能在词法层、语法层、生成层分别定位故障比任何日志插桩都直观。如果打印出来的 token 流正常、AST 结构也正确但生成的汇编执行结果不对那问题几乎必然出在代码生成层的指令选择或寄存器分配。此时我会直接构造一个最小用例比如只输入int a; a 5; return a;然后手推一遍期望的汇编再把编译器生成的拿来做逐行 diff。这个匹配过程能把玄学问题压缩成“哪一行汇编不符合预期”的明确问题。6. 回归验证与加一个新语法先跑通用例再动代码生成器拿到这份源码后不要急着改功能先做一轮回归验证。我会先建立三个测试用例第一个是纯表达式运算1 2 * 3 - 4第二个是局部变量和赋值int a; a 42;第三个是函数调用print_hello()。每个用例分别做“编译 → 运行 → 比较退出码”三步。如果你能跑通这三类场景说明词法、语法、生成三条主线都已正确后面的改动才能基于一个可信的基线。验证通过后的第一次进阶尝试我会选加一个语法扩展优先级最高的通常是复合赋值运算符和-。这个改动横跨四层能帮你把源码结构完全吃透词法层要新加TOK_PLUS_ASSIGN和TOK_MINUS_ASSIGN语法层在parse_assign的目标表达式分支里接住这两个 tokenAST 层在ND_ASSIGN上追加一个assign_op字段代码生成层判断这个字段先取旧值、再与右侧表达式做运算最后写回变量。最关键的验证点是旧值只求一次。如果你的复合赋值实现是先把左值读出来、再对右值求一次而右值表达式里有自增或函数调用结果就会多执行一次副作用。这个 bug 不太明显但正是编译器里最值得练手的边界。我会专门为它写一个测试用例a 10; a (a);预期结果是a先被取旧值 10a返回 10 并让 a 变成 11相加后写回最终 a 是 21。如果编译器输出 22说明实现把左值重复读了。关于复合赋值的展开我建议在语法分析阶段就把a expr直接改写成 AST 层面的a a expr但这需要临时复制一个左值变量节点。还有一种做法是保留复合赋值节点让代码生成器处理后者改动更小但需要新增一条寄存器使用规则。从教学角度我更推荐前者因为可读性好而且能让你在调试时直接看到重写后的 AST。从那以后我每次拿到一个编译器源码都会先强制走一遍三用例回归表达式、局部变量、函数调用。这三个点一旦断了后面任何新功能都会建立在不稳定的地基上。希望这篇笔记能帮你把这份小型 C 编译器的骨骼摸清改起来不那么“玄学”。本文还有配套的精品资源点击获取