C语言实现小型编译器：从词法分析到四元式的完整指南

简介：面向编译原理课程设计与C语言进阶实践，这份资源以小型编译程序的完整实现为主线，覆盖词法分析、语法分析、语义分析与四元式生成等核心环节，适合计算机专业学生或需要动手理解编译过程的开发者参考。压缩包共4个文件，包含C、C++源码与MD格式说明文档及LICENSE文件，整体仅14KB，代码量精炼，便于快速阅读与调试。已有288人学习浏览，属于轻量但典型的课程设计范例。从源码与文档中可学到如何设计有限状态自动机识别标记、构建递归下降语法分析器，以及将表达式和语句转化为四元式中间表示的具体实现思路，同时附带错误处理与代码组织方面的参考，对完成同类作业或深入理解编译器工作流程很有帮助。

1. 这个标题在讲什么：为什么 C 语言仍是编译原理实验的默认答案

"基于 C 语言实现一个小型编译程序"是编译原理课程设计里出现频率最高的题目之一，要求不高但范围不小：从读入源码文件开始，经过词法分析、语法分析、符号表管理，最后生成可运行的中间代码或目标代码。它能解决的问题很具体——搞懂编译器不是翻阅龙书的玄学，而是亲手把字符流一步步变成机器能懂的指令流，顺带把 C 语言的指针、内存管理和文件操作全部实练一遍。适合正在做课程设计的学生、想补编译原理短板的在职开发者，以及想用 C 语言验证科班知识的人。

2. 编译器五段式管线：从字符流到目标码，C 语言版骨架怎么搭

2.1 五段式骨架：每段的输入、输出与职责边界

一个完整编译器通常被拆成五段：词法分析、语法分析、语义分析、中间代码生成、目标代码生成。课程设计的小型编译器一般砍掉最后一层的复杂优化，把目标定在「生成四元式中间代码 + 简单目标代码」上。段与段之间是严格的接力关系：前一段的输出是后一段的输入，这决定了你的 C 语言数据结构从一开始就要设计对，后面改结构体牵扯面非常大。

词法分析读入的是整个源码文件，输出是 Token 流；语法分析吃 Token 流，输出是语法树——但很多教学编译器为了减少代码量，选择在递归下降分析的同时直接生成四元式，跳过显式建树。符号表是全局公共设施，词法分析阶段登记标识符，语法分析阶段查重和补充类型信息。这个「边分析边生成」的做法对小型编译程序完全够用，也是大多数课程设计参考答案采用的路子。

语义分析在小编译器里通常不单独设段：变量是否声明、类型是否匹配，靠符号表在语法分析过程中同步检查。这样做的缺点是代码耦合度高，优点是代码量小、答辩时容易讲清楚。真正需要单独检查的只有一件事——变量未声明就使用，这个错误必须挂在符号表上才能统一拦住。我一般会在写代码前先画一张管线图，把每段的输入输出写在纸上，原因很实际：C 语言不像 Python 或 Java 那样有现成的容器和垃圾回收机制，Token 流怎么存放、符号表怎么扩容、四元式数组怎么动态增长，这些在动笔前就得定下来，否则写一半重构，血泪经验。

2.2 为什么选 C：指针、内存管理与贴近底层的控制力

先回答一个很多人会问的问题：编译原理课用 Java 或 Python 的项目也不少，为什么教材和课程设计还是偏爱 C 语言？三个理由。第一，编译器本质上是文本处理程序，C 语言指针和数组正好用来操作字符缓冲区、动态增长的结构体，符号表用链表还是动态数组、Token 流用 realloc 扩容，这些练习本身就是系统编程的基本功。第二，真实世界的编译器——TCC、Lua、早期 GCC——都是用 C 写的，读它们的源码能直接对照课程知识，换成别的语言就少了一层参照。第三，C 语言库函数数量少，反而逼你把每个环节的数据结构和算法亲手实现，不会出现「调库调完什么都不懂」的情况。

C 语言的典型取舍在这类项目里体现得很充分：内存分配用 malloc/realloc，释放要自己管理所有权，根本绕不开 C 语言内存管理；字符串处理靠 strcmp、strncpy 这类 C 语言字符串函数；读取源码文件用 fopen/fgetc，依赖标准库的文件缓冲区，而不是每次读一个字符都发生一次系统调用。这些恰好是 C 语言编程里最容易考到、也最容易出错的地方。如果你打算拿这份代码去答辩，老师大概率会追问「缓冲区怎么设计的」「内存有没有泄漏」，后者我会在第五章专门展开。

主流程骨架代码如下，它把各模块的调用顺序固定下来，后续填实现时只需要往对应函数里加内容：

/* 编译器主流程：从源码文件到四元式中间代码 */ #include <stdio.h> #include <stdlib.h> static FILE *src; /* 源码文件句柄，词法分析用 */ int main(int argc, char *argv[]) { if (argc < 2) { fprintf(stderr, "用法: %s 源码文件\n", argv[0]); return 1; } src = fopen(argv[1], "r"); if (src == NULL) { perror("打开源码文件失败"); return 1; } init_lexer(src); /* 1. 词法分析初始化，准备读取 */ init_symbol_table(); /* 2. 符号表清零，容量预分配 */ init_quad_list(); /* 3. 四元式动态数组初始化 */ program(); /* 4. 递归下降分析入口 */ print_quads(); /* 5. 输出中间代码 */ print_symbols(); /* 6. 输出符号表，便于查错 */ fclose(src); free_all(); /* 统一释放动态内存，防泄漏 */ return 0; }

逻辑说明：main 只做四件事，打开文件、初始化三个全局设施、调用语法分析入口 program()、最后把结果打印出来。参数说明上有几个细节值得注意——argc 小于 2 时的报错写到 stderr，避免错误混进标准输出；fopen 失败后用 perror 打印系统错误原因，方便区分是路径问题还是权限问题；free_all() 把所有 malloc 出来的内存集中释放，比零散 free 更容易保证不泄漏。初始化顺序不严格要求谁先谁后，但建议固定不变，减少排错时的变量。

3. 词法分析器实现：Token 结构体、保留字表与手写扫描循环

3.1 Token 结构体设计与保留字表：行号和原文都要留

词法分析器要回答的问题只有一个：给定一个字符，它是某个单词的开头吗？如果是，这个单词有多长、属于哪一类？所以 Token 结构体至少要有四样东西：类型、单词原文、行号、以及数字字面量的值。行号容易被初学者忽略，但语法分析报错时「第几行」全靠它，漏掉行号的编译器调试起来会让人抓狂。

/* Token 类型：关键字、标识符、数字、运算符、文件结束、错误 */ typedef enum { TOK_IDENT, /* 标识符：变量名、函数名 */ TOK_NUMBER, /* 整型数字字面量 */ TOK_KEYWORD, /* 保留字：int if else while 等 */ TOK_OP, /* 运算符：+ - * / = == < <= */ TOK_EOF, /* 文件结束 */ TOK_ERROR /* 无法识别的字符 */ } TokenType; typedef struct { TokenType type; char lexeme[64]; /* 单词原文，最长 63 字符加结束符 */ int line; /* 单词所在行号，报错用 */ int value; /* 仅数字字面量使用，存整数值 */ } Token;

参数说明：lexeme 定长数组是最省事的做法，代价是标识符长度超限时需要截断处理；如果不想定长，可以用 char* 加 malloc，但每次扫描都要算长度、分配、拷贝，还要记得释放，课程设计没必要。line 字段初始化时要赋当前行号，很多翻车案例是这里漏赋值，导致所有报错行号都变成 0。value 字段用 int 对应整型字面量；想支持浮点得改成 double 外加一个标志位，一般不用做这个扩展。

保留字表用静态数组加 strcmp 线性查找就够，不需要上哈希：

/* 保留字表：按字典序排列，查找走线性扫描 */ static const char *keywords[] = { "else", "float", "if", "int", "return", "void", "while" }; #define KEYWORD_COUNT (sizeof(keywords) / sizeof(keywords[0])) static int is_keyword(const char *s) { for (int i = 0; i < KEYWORD_COUNT; i++) { if (strcmp(s, keywords[i]) == 0) return 1; } return 0; }

说明：这里用 strcmp 而不是 strncmp，因为传入的 s 是已经用 '\0' 结尾的 lexeme，不会越界。KEYWORD_COUNT 用 sizeof 计算，后面增减关键字不用改第二处。线性查找性能足够，源码里关键字出现次数最多几百次，为这个上哈希属于过早优化。

3.2 扫描主循环：最长匹配、回退字符与文件缓冲区的配合

词法分析的核心循环可以概括成「看一个字符，决定走哪条分支，多读的字符推回去」。推回操作用 ungetc(c, src) 实现，它依赖 stdio 的文件缓冲区把字符留在内存里，而不是真的回到磁盘——所以 C 语言读文件天然快，fgetc 看似一次读一个字节，底层其实是整块读入缓冲。手写扫描器时这里最容易出细节问题：多读了一个字符不推回，Token 边界就会错位；推回太频繁，缓冲区也可能出问题。

先写跳过空白和注释的辅助函数，它直接决定行号统计是否正确：

/* 跳过空白与注释，返回下一个有效字符 */ static int skip_ws_and_comment(void) { int c; for (;;) { c = fgetc(src); if (c == '/') { /* 可能是注释或除法 */ int next = fgetc(src); if (next == '/') { /* 行注释：跳到行尾 */ while ((c = fgetc(src)) != '\n' && c != EOF) { } if (c == '\n') current_line++; continue; } else if (next == '*') { /* 块注释：一直找到结束符 */ c = fgetc(src); while (c != EOF) { if (c == '\n') current_line++; int d = fgetc(src); if (c == '*' && d == '/') break; c = d; } if (c == EOF) error("块注释未闭合"); continue; } else { /* 普通除法：推回 next */ ungetc(next, src); return '/'; } } if (c == '\n') current_line++; /* 统一在这里分行号 */ if (c == ' ' || c == '\t' || c == '\r') continue; return c; /* EOF 或有效字符都到这里 */ } }

逻辑说明：行号只在一个地方递增，就是 '\n' 出现时，这样行注释和块注释内的换行也不会漏统计。注释结束符的判断用两个字符配对，写完记得自测「没闭合的注释要报错而不是死循环」。参数方面，c 声明为 int 而不是 char，这是 fgetc 返回值的要求——EOF 是负数，用 char 会截断成其他字符，这个细节我会在第五章再提醒一次。

然后是主扫描函数：

/* 读取下一个 Token：主扫描循环 */ Token next_token(void) { Token tok; memset(&tok, 0, sizeof(tok)); tok.line = current_line; int c = skip_ws_and_comment(); /* 已经跳过空白和注释 */ if (isalpha((unsigned char)c) || c == '_') { /* 标识符或保留字 */ int len = 0; while (isalnum((unsigned char)c) || c == '_') { if (len < 63) /* 超长部分截断，保证不越界 */ tok.lexeme[len++] = (char)c; c = fgetc(src); } if (c != EOF) ungetc(c, src); /* 多读的字符推回 */ tok.lexeme[len] = '\0'; tok.type = is_keyword(tok.lexeme) ? TOK_KEYWORD : TOK_IDENT; return tok; } if (isdigit((unsigned char)c)) { /* 整型字面量 */ int val = 0; while (isdigit((unsigned char)c)) { val = val * 10 + (c - '0'); c = fgetc(src); } if (c != EOF) ungetc(c, src); snprintf(tok.lexeme, sizeof(tok.lexeme), "%d", val); tok.type = TOK_NUMBER; tok.value = val; return tok; } /* 运算符：先试双字符 == != <= >=，再退回单字符 */ if (c == '=' || c == '!' || c == '<' || c == '>') { int next = fgetc(src); if (next == '=') { snprintf(tok.lexeme, sizeof(tok.lexeme), "%c%c", c, next); tok.type = TOK_OP; return tok; } if (next != EOF) ungetc(next, src); tok.lexeme[0] = (char)c; tok.lexeme[1] = '\0'; tok.type = TOK_OP; return tok; } if (c == EOF) { tok.type = TOK_EOF; strcpy(tok.lexeme, "EOF"); return tok; } snprintf(tok.lexeme, sizeof(tok.lexeme), "未识别字符 %c", c); tok.type = TOK_ERROR; return tok; }

逻辑说明：三个分支都严格遵循「最长匹配」——标识符会一直吃合法字符直到遇到分隔符；数字会把连续数字全部吃掉再推回；运算符优先匹配双字符。注意我统一在推回前判断了c != EOF，否则 ungetc 收到 EOF 属于未定义行为，在部分编译器上会静默出错。参数说明：isalpha、isdigit 传参时要转成 unsigned char，这是 ctype 函数的安全用法，避免负数下标问题；lexeme 在截断后仍然写 '\0'，保证字符串函数永远安全。

4. 递归下降与四元式：语法分析、符号表和中间代码的配合

4.1 递归下降分析器：为什么课程设计不选 yacc

很多课程允许用 lex/yacc 生成分析器，但我建议手写递归下降，理由很直接：yacc 生成的解析器对你是个黑匣子，一旦状态冲突报错，排查成本比手写高一个数量级。递归下降把一个产生式对应成一个 C 函数，语法分析规则和代码结构一一对应，答辩时老师一问「 if 语句怎么匹配」你能直接指出代码行。代价是要自己处理文法设计——最典型的是左递归，不改写就会死循环，下面这段就是改写后的表达式文法。

/* 表达式递归下降：E -> T { (+|-) T } * 每个函数通过 out 参数返回本次解析结果的变量名 */ static void expr(char *out) { char left[32], right[32], tmp[32]; term(left); /* 解析第一个 T */ while (lookahead.type == TOK_OP && (lookahead.lexeme[0] == '+' || lookahead.lexeme[0] == '-')) { char op[8]; snprintf(op, sizeof(op), "%c", lookahead.lexeme[0]); advance(); /* 消耗运算符，推进 Token */ term(right); /* 解析右侧 T */ snprintf(tmp, sizeof(tmp), "t%d", next_temp()); emit_quad(op, left, right, tmp); /* tmp = left op right */ snprintf(left, sizeof(left), "%s", tmp); /* 结果参与后续运算 */ } snprintf(out, 32, "%s", left); }

逻辑说明：原始文法 E -> E + T 是左递归，递归下降会无限调用自己；改写为 E -> T { (+|-) T } 后，用 while 循环表达「任意多个加减项」，彻底避免栈溢出。每个函数通过 out 参数回传结果名，而不是直接 return char*，是为了避免返回局部数组地址形成悬垂指针。参数说明：lookahead 是全局 Token，作为当前待处理符号；advance() 每次只消费一个 Token，同时更新 lookahead——这两个变量必须严格配对，否则分析位置错乱，我在第五章会讲具体表现。term 和 factor 的结构与 expr 完全相同，factor 负责处理标识符、数字字面量和括号，这里不重复贴。

4.2 符号表：动态数组和链表怎么选

符号表是语义检查的依靠，设计上两条路：动态数组适合「查询为主」的场景，链表适合「作用域不断嵌套推入弹出」的场景。课程设计的小型语言作用域最多两层（全局 + 函数体），用动态数组加 scope 字段就够了；链表反而要在出作用域时逐个删除，代码更碎。

typedef struct { char name[64]; /* 变量名，作为主键 */ int type; /* INT_TYPE=0, FLOAT_TYPE=1, VOID_TYPE=2 */ int scope; /* 0=全局，1=第一个局部作用域 */ int offset; /* 相对活动记录基址的偏移，目标生成用 */ } Symbol; typedef struct { Symbol *items; /* 动态数组首地址 */ int count; /* 当前符号数 */ int capacity; /* 已分配容量 */ } SymbolTable; /* 查找：线性扫描，找到返回下标，否则返回 -1 */ static int find_symbol(const char *name) { for (int i = 0; i < g_symtab.count; i++) { if (strcmp(g_symtab.items[i].name, name) == 0) return i; } return -1; } /* 插入：容量不足先倍增扩容，再写入 */ static int add_symbol(const char *name, int type, int scope) { if (g_symtab.count >= g_symtab.capacity) { int cap = g_symtab.capacity ? g_symtab.capacity * 2 : 16; g_symtab.items = realloc(g_symtab.items, cap * sizeof(Symbol)); if (g_symtab.items == NULL) { error("符号表扩容失败"); return -1; } g_symtab.capacity = cap; } Symbol *s = &g_symtab.items[g_symtab.count++]; snprintf(s->name, sizeof(s->name), "%s", name); s->type = type; s->scope = scope; s->offset = 0; /* offset 由语义分析阶段统一分配 */ return g_symtab.count - 1; }

逻辑说明：realloc 的返回值必须重新赋给 items，而不是沿用旧指针——这是 C 语言内存管理里最经典的坑，realloc 移动内存块后旧指针直接失效。初始容量 16，后续每次翻倍，摊还复杂度是 O(1)。参数说明：offset 字段现在用不到，但在目标代码生成阶段要算变量在栈帧里的位置，所以提前留好；scope 字段除了区分全局变量和局部变量，还在报错时提示「变量作用域」，答辩时很加分。注意查找没有区分 scope，小型语言里两个同名不同作用域的变量按先找到者处理，如果要做严格作用域规则，得在 find 时加一层 scope 过滤，代码量不大但容易被忽略。

4.3 四元式：三地址码的数据结构与生成时机

四元式是中间代码的常见形式，每条指令由 op、arg1、arg2、result 四个字段组成，本质是三地址码。它离目标代码近、又能跨指令集复用，教学编译器几乎都选它作为输出终点。数据结构定义如下：

/* 四元式：op arg1 arg2 result，即三地址码 */ typedef struct { char op[8]; /* "+" "-" "*" "/" "=" "jmp" "j<" 等 */ char arg1[32]; /* 第一操作数：变量名、常量或临时量 */ char arg2[32]; /* 第二操作数；单目运算填空串 */ char result[32]; /* 结果：通常是一个新的临时变量 */ } Quad;

生成时机有两个选择：语法分析过程中边归约边生成，或者先建语法树再遍历生成。后者结构清晰但要多实现一套树节点和遍历逻辑；前者代码紧凑、中间结果不需要落树，更符合「小型」的定位。我通常选前者，但会把 emit_quad 单独封装成函数，这样以后想改成先建树再生成也能隔离改动面。

看一个表达式 a = b + c * 2 生成的四元式序列，就能直观理解三地址码的形态：

三条指令对应一个表达式，每个子表达式的结果都落入新的临时变量 t1、t2。这个设计的好处是每条指令至多一次运算，翻译成汇编时几乎一一对应；坏处是临时变量数量膨胀，所以进阶阶段会做临时变量合并——那部分在第六章提一句，初版不要花时间做。

5. 避坑与排查：编译器课程设计最容易翻车的 5 个点

这一章是真实做题才会遇到的排错经验，每条都按「现象 → 原因 → 解决」记录。我见过太多小组把八成时间耗在最后一步才发现是前端的低级问题，所以这些坑值得提前看。

5.1 标识符超长导致缓冲区越界，程序崩溃或输出乱码

现象：源码里写了一个特别长的变量名，编译器运行到一半崩溃，或者符号表里出现乱码符号。

原因：扫描循环里没有检查 len 是否超过 63，fgetc 不停往里写，最后还在越界位置写 '\0'，破坏了相邻内存。

解决：写入前判断if (len < 63)，超长部分继续读完但不再写入，循环结束后统一在 len 处写 '\0'。我的习惯是同时用下标保护宏定义缓冲区大小，比如#define LEXEME_MAX 64，避免魔法数字散落各处。

5.2 advance 和 ungetc 不配对，Token 流静默错位

现象：语法分析读到的运算符总是偏一个 Token，表达式a + b被解析成a和b两个独立项，中间没有加法。

原因：某处扫描多读了一个字符后没有 ungetc 推回，或者语法分析里手动移动了 lookahead 而没有调用 advance。Token 流一旦错位，后续所有分析都在错误的节奏上进行，错误信息还经常指向错误行。

解决：约定「只有 advance() 能推进 Token，只有扫描器内部能用 ungetc」，语法分析代码里不允许直接操作 lookahead 的指针或下标。在 advance 里加一行调试宏开关，开启后打印消费的 Token 原文，排查时一秒定位。

5.3 左递归文法未消除，递归下降直接栈溢出

现象：程序一解析表达式就卡死，控制台疯狂输出然后段错误，gdb 里 bt 看到 expr 函数反复出现在栈帧里。

原因：文法写成 E -> E + T 这种左递归形式，递归下降每次调用 expr 都先再调一次 expr，永不走到终结符，栈被撑爆。

解决：改写为 E -> T { (+|-) T }，用循环替代左递归。写任何一条文法前先检查左部符号是不是出现在产生式最左边，如果是，要么拆成等价的循环写法，要么用 EBNF 的重复语法。这是语法分析阶段最值得花十分钟提前想清楚的问题。

5.4 换行符污染行号，报错定位全偏

现象：在 Windows 上编写的源码文件，编译器报错行号与实际行号差好几行，或者块注释跨行后行号完全混乱。

原因：Windows 文本文件换行是 \r\n 两个字符，如果只在 \n 加行号，\r 会被当成普通空白跳过，逻辑上没错；但如果在注释处理里也依赖行号递增，某个分支少处理了 \r，行号就对不齐。

解决：跳过空白时统一处理 ' '、'\t'、'\r'、'\n'，行号只在 '\n' 单独加一。文件打开方式用文本模式（即fopen(path, "r")而不是 "rb"），让标准库先把 \r\n 转换掉，省掉手工处理。

5.5 realloc 返回值没接住，悬垂指针和内存泄漏一起出现

现象：编译大一点的文件时符号表内容错乱，或者 valgrind 报 invalid read / definitely lost。

原因：realloc失败或移动内存块后，旧指针失效，但代码里还在用旧指针读写；另外插入符号时如果 realloc 失败直接返回，count 已经增加，符号表状态就不一致。

解决：realloc 结果必须赋值给 items 并判空，失败时给出错误信息而不是继续写。小程序也要养成在退出前统一 free 的习惯，把清理集中在 free_all() 里，Valgrind 看结果会干净很多。至于找泄漏或越界，我一般用 gdb 工具调试 C 语言程序的段错误：gdb ./mycc，运行后bt看栈帧，十次有九次能直接指出问题函数。

6. 验证与进阶：最小测试集锁定回归、错误恢复与常量折叠

做编译器最容易犯的错是「改一处坏一片」。语法分析加了一个新的语句类型，结果原来能编译的表达式崩了——这种回归靠人眼盯不出来，必须有一组最小测试集自动跑。我的做法是建 tests/ 目录，里面放十几个小文件，每个覆盖一个语法点，再手工确认一遍期望输出存成 golden 文件，之后每改一次代码就全量跑一遍。

回归脚本用 bash 写十几行就够，遍历每个用例，用 diff 对比输出，失败时打印用例名和差异位置。这样跑一轮下来，改动是否破坏原有功能一清二楚。

两个值得做的进阶点，按投入产出排序。第一是错误恢复。现在大多数实现的词法或语法错误都是「报错即停」，体验很差；panic mode 的做法是遇到错误后跳过一批 Token，直到碰见分号或右花括号这类同步点，再继续分析。实现量不大，却是答辩时能讲出亮点的部分。第二是常量折叠。四元式生成后扫一遍，如果某条四元式的 arg1 和 arg2 都是数字字面量，就直接在编译期算出结果替换进去，比如 t1 = 2 * 3 直接变成 t1 = 6。这个优化在四元式数组上就能做，不需要建数据流分析框架。

我现在接手任何编译器代码，第一件事永远是先把测试集补起来再读实现——没有回归保护的编译器改动就是在赌博。这个习惯救过我很多次，尤其是课程设计后期临时加功能的时候。希望帮到你。

本文还有配套的精品资源，点击获取