C语言实现小型编译器：从词法分析到中间代码生成

简介基于C语言实现的小型编译程序课程设计资源包面向编译原理学习者及高校课程设计学生完整演示了从源代码到四元式中间表示的编译实现流程涵盖词法分析、语法分析、语义分析与中间代码生成等关键环节。资源共4个文件压缩包仅14KB包含C语言源程序、C辅助文件、说明文档及LICENSE许可md文档用于快速理解设计思路c/cpp代码供直接阅读与二次开发。已有288人学习下载适合作为编译原理课程设计的参考实现或入门实践模板。借助包内源码可学习四元式OP,A,B,C结构定义、正则规则到有限状态自动机的词法识别、递归下降语法分析以及常量折叠等简单优化技巧为后续目标代码生成打下扎实基础。 好先想清楚一个前提用 C 语言实现一个小型编译程序不是在造一个能跟 GCC 扳手腕的产品而是把「源代码怎么变成机器能懂的东西」这条链路亲手走通一遍。如果你正面临课程设计、考研复试项目或者入职后要写解释器/DSL这个题目的价值在于它逼你把词法分析、语法分析、符号表、中间代码生成这些黑匣子一个个拆开并且因为用的是 C你没法靠语言本身的封装绕坑——内存、指针、字符串缓冲全部裸奔在你面前。本文按我实际做过的路径从词法到代码生成给出一套可复现的最小实现方案顺带把最容易翻车的几个位置提前指出来。2. 词法分析器从字符流到 token 表的三个关键选择词法分析是整个编译程序的地基。它干的事很朴素把源码字符串切成一个个有意义的词素比如int a 10 b;切出int、a、、10、、b、;。这块看似简单但有几个选型会直接影响你后面所有代码的写法。2.1 token 结构体与关键字表先用 C 把词的形态定死我见过不少初学者一上来就写一个get_token()返回字符串然后后面到处用strcmp比较。这种做法不是不行但会让语法分析阶段的代码变成一堆字符串比较的泥潭。更稳的做法是先定义一套 token 类型枚举每个 token 带着类型、值、源码位置三件套。/* token.h */ #ifndef TOKEN_H #define TOKEN_H #define MAX_ID_LEN 64 #define MAX_TOKENS 4096 typedef enum { T_EOF, T_NUM, /* 整数常量 */ T_ID, /* 变量名如 a、b */ T_KW, /* 关键字如 int、return */ T_PLUS, T_MINUS, T_STAR, T_SLASH, T_LPAREN, T_RPAREN, T_SEMI, /* ; */ T_ASSIGN /* */ } TokenType; typedef struct { TokenType type; int value; /* T_NUM 时存数值 */ char text[MAX_ID_LEN]; /* 原始拼写关键字和变量名都用 */ int line, col; /* 报错时告诉你位置 */ } Token; #endif我把T_KW关键字和T_ID标识符分开而不是让关键字作为标识符的一个子集原因是后续涉及变量名与关键字冲突的检查。line和col一定要有——等你在 300 行代码里定位一个语法错误时就知道位置信息有多救命。关键字表用静态字符串数组即可这个规模下不需要哈希。/* lexer.c 片段 */ static const char *keywords[] { int, return, if, else, while }; #define NUM_KEYWORDS (sizeof(keywords) / sizeof(keywords[0])) static int lookup_keyword(const char *s) { for (int i 0; i NUM_KEYWORDS; i) { if (strcmp(keywords[i], s) 0) return 1; } return 0; }为什么不用哈希或二分因为小型编译程序的关键字一般不超过 20 个线性查找一次也就 20 次strcmp耗时可以忽略。这里强行引入哈希表只会增加代码量和出错面得不偿失。如果你后续要支持更多关键字再换成 bsearch 也来得及。2.2 手写状态机读 token绕过正则与 flex 的工程化理由很多教材会推荐用 flex 生成词法分析器但我更建议你手写。原因有三一是 flex 生成的 C 代码可读性差报错信息不友好二是你没法在扫描过程中灵活插入符号表登记逻辑三是作为课程设计手写状态机是明显的加分项评阅老师一眼就能看出你是真懂还是调包。这里给出一个核心实现思路把整个源码读进内存用pos指针逐字符扫描配合line和col追踪位置。不要边读文件边用getchar()做词法分析否则字符回退问题后面 5.1 会讲会把你折磨到怀疑人生。/* lexer.c 片段 */ static char *src; /* 整个源码读入内存 */ static int pos 0; /* 当前字符下标 */ static int line 1; static int col 0; Token get_token(void) { Token tk; tk.line line; tk.col col; /* 跳过空白和换行 */ while (src[pos] || src[pos] \t) { pos; col; } if (src[pos] \n) { line; col 0; pos; return get_token(); } if (src[pos] \0) { tk.type T_EOF; return tk; } /* 数字只支持十进制整数先不做溢出检测 */ if (isdigit(src[pos])) { tk.type T_NUM; tk.value 0; while (isdigit(src[pos])) { tk.value tk.value * 10 (src[pos] - 0); pos; col; } return tk; } /* 标识符或关键字 */ if (isalpha(src[pos]) || src[pos] _) { int len 0; while (isalnum(src[pos]) || src[pos] _) { if (len MAX_ID_LEN - 1) tk.text[len] src[pos]; pos; col; } tk.text[len] \0; tk.type lookup_keyword(tk.text) ? T_KW : T_ID; return tk; } /* 运算符和界符 */ switch (src[pos]) { case : tk.type T_PLUS; pos; col; break; case -: tk.type T_MINUS; pos; col; break; case *: tk.type T_STAR; pos; col; break; case /: tk.type T_SLASH; pos; col; break; case (: tk.type T_LPAREN; pos; col; break; case ): tk.type T_RPAREN; pos; col; break; case ;: tk.type T_SEMI; pos; col; break; case : tk.type T_ASSIGN; pos; col; break; default: fprintf(stderr, 第 %d 行第 %d 列无法识别的字符 %c\n, line, col, src[pos]); exit(1); } return tk; }这里有几个关键参数需要说明。MAX_ID_LEN定为 64意味着变量名最长 63 个字符超过部分被截断——实际写代码时没人用这么长的变量名但截断逻辑必须有否则strcpy会把内存写穿。isdigit、isalpha接收的是 int 类型而src[pos]是 char当字符为负值时非 ASCII 扩展字符行为是未定义的所以源文件里最好只允许 ASCII 字符遇到中文字符直接报错。数字扫描我特意没做溢出检测因为 10 * value digit 在 value 接近 INT_MAX 时会溢出成负数。真实场景里你至少应该判断value (INT_MAX - digit) / 10但这个小程序里先记录这个坑等测试集跑完再补。2.3 符号表初成型标识符登记与作用域标记词法分析阶段其实还不需要完整的符号表但你应该先把“登记变量”这个动作想清楚。我的做法是词法阶段只负责把 token 流生成出来符号表在语法分析和语义检查阶段填写。不过 token 结构体和符号表条目的设计可以提前对齐。/* symtab.h */ #define SYM_MAX 256 typedef struct { char name[MAX_ID_LEN]; int declared; /* 是否已声明 */ int addr; /* 模拟内存地址偏移单位字节 */ } SymEntry; static SymEntry symtab[SYM_MAX]; static int sym_count 0; int lookup_symbol(const char *name) { for (int i 0; i sym_count; i) { if (strcmp(symtab[i].name, name) 0) return i; } return -1; } int add_symbol(const char *name) { int idx lookup_symbol(name); if (idx 0) return idx; if (sym_count SYM_MAX) { fprintf(stderr, 符号表溢出最多支持 %d 个变量\n, SYM_MAX); exit(1); } strncpy(symtab[sym_count].name, name, MAX_ID_LEN - 1); symtab[sym_count].name[MAX_ID_LEN - 1] \0; symtab[sym_count].addr sym_count * 4; /* 每个变量占 4 字节 */ sym_count; return sym_count - 1; }addr字段是给后面的中间代码生成用的。我设计的是简化内存模型从地址 0 开始每个变量固定占 4 字节这样生成伪汇编时可以直接用变量名对标地址。sym_count * 4这种分配策略虽然粗糙但对于小型编译程序完全够用。注意strncpy不会自动补结尾的\0所以我在后面手动补了一位。这是 C 语言字符串函数的经典陷阱所有用到strncpy的地方都要检查这个。符号表数组大小SYM_MAX设为 256 意味着最多支持 256 个变量真写大型程序不够但课程设计级别的测试样例绰绰有余。3. 递归下降语法分析表达式文法怎么设计才不翻车语法分析是把 token 流按文法组织成语法树或者直接驱动翻译。我选递归下降法因为它和文法规则一一对应C 语言写出来天然是函数调用树也最容易配合后续的中间代码生成。3.1 文法与优先级先定义死两级还是三级考虑表达式a 1 2 * 3;2 * 3必须先算这反映在文法里就是优先级层次。我用的是一条简化文法program - stmt_list stmt - ID ASSIGN expr SEMI expr - term ( ( PLUS | MINUS ) term )* term - factor ( ( STAR | SLASH ) factor )* factor - NUM | ID | LPAREN expr RPAREN注意我把expr写成term开头再用循环拼接而不是教科书里常见的左递归形式expr - expr term | term。因为递归下降法直接翻译左递归规则会导致无限递归parse_expr()第一件事是调用parse_expr()栈瞬间溢出。用循环改写是标准做法也是在 C 里最容易实现的方案。这个文法里有两个优先级层次expr对应加减term对应乘除。如果需要支持一元负号-x再在factor里加一层。三级优先级对小型语言来说已经够用盲目增加层次会让parse_factor里的分支越来越复杂。3.2 递归下降实现表达式每个函数对应一个非终结符有了 token 流数组tok[]和当前位置pos_tok每个非终结符写一个解析函数。/* parser.c */ Token tok[MAX_TOKENS]; int pos_tok 0; void expect(TokenType t) { if (tok[pos_tok].type t) { pos_tok; } else { fprintf(stderr, 第 %d 行期望 %d实际 %d位置 %d\n, tok[pos_tok].line, t, tok[pos_tok].type, pos_tok); exit(1); } } void parse_factor(void) { if (tok[pos_tok].type T_NUM || tok[pos_tok].type T_ID) { pos_tok; /* 吃掉数字或变量名 */ } else if (tok[pos_tok].type T_LPAREN) { pos_tok; /* 吃掉 ( */ parse_expr(); /* 括号里是完整表达式 */ expect(T_RPAREN); } else { fprintf(stderr, 第 %d 行factor 位置出现非法 token\n, tok[pos_tok].line); exit(1); } } void parse_term(void) { parse_factor(); /* 先解析第一部分 */ while (tok[pos_tok].type T_STAR || tok[pos_tok].type T_SLASH) { pos_tok; /* 吃掉运算符 */ parse_factor(); /* 再解析右侧 */ } } void parse_expr(void) { parse_term(); while (tok[pos_tok].type T_PLUS || tok[pos_tok].type T_MINUS) { pos_tok; parse_term(); } }关键点在于parse_term里while循环处理a * b * c这种左结合情况每遇到一个乘除号就再解析一个factor而不是递归调用自身所以不会爆栈。expect函数集中处理 token 类型匹配失败的情况——一开始你可能觉得每次多写一个expect很啰嗦但等到你调试一个括号不匹配的 bug 时expect里打出的“期望 X实际 Y”就是最快的定位线索。这里还要强调一下模块边界parse_expr只负责检查语法结构是否正确不负责计算表达式的值。计算是中间代码生成阶段的事。很多入门实现会在parse_factor里顺手做整数运算这种“边解析边求值”的方案在表达式上能跑通但一旦引入变量赋值和控制流就完全没法扩展了。3.3 错误恢复策略编译程序不能死在第一个错上如果遇到一个错误就exit(1)用户改错一次就得重跑一次这在真实使用中不可接受。更实用的策略是恐慌模式恢复发现错误时跳过当前语句的部分 token直到遇到一个可信的同步点比如分号然后继续解析下一条语句。void synchronize(void) { while (tok[pos_tok].type ! T_EOF tok[pos_tok].type ! T_SEMI) { pos_tok; } if (tok[pos_tok].type T_SEMI) pos_tok; /* 跳过同步点 */ } /* 在 parse_stmt 的调用处这样用 */ void parse_stmt(void) { if (tok[pos_tok].type T_ID tok[pos_tok 1].type T_ASSIGN) { pos_tok 2; /* 吃掉 ID */ parse_expr(); expect(T_SEMI); } else { fprintf(stderr, 第 %d 行语句格式错误已跳过该语句\n, tok[pos_tok].line); synchronize(); } }synchronize是和expect配合使用的expect负责精准报错synchronize负责把解析指针推到一个安全位置。一个小技巧是错误信息里带上当前 token 的行号——如果没有行号面对一个 100 行的测试程序你只能在 VS Code 里数花括号碰运气。我没有选择恢复后继续解析表达式因为表达式结构一旦断裂后续匹配括号和运算符的逻辑全是错的。跳过整条语句虽然粗暴但至少保证编译器不会陷入死循环而且能把一个文件里的多个独立错误一次性都报出来。4. 中间代码生成三地址码的指令设计与符号表落地语法分析通过之后下一步是生成中间代码。我选三地址码three-address code因为它每条指令最多只有一个运算符和三个操作数结构与汇编接近但不用处理寄存器分配、标志位这些底层细节。输出成线性指令序列即可后续想转成汇编或解释执行都有现成路线。4.1 三地址码设计指令集越小越不容易写崩/* ir.h */ typedef enum { Q_ASSIGN, /* c a */ Q_ADD, /* c a b */ Q_SUB, /* c a - b */ Q_MUL, /* c a * b */ Q_DIV, /* c a / b */ Q_LABEL, /* 标记位置用于跳转 */ Q_JMP, /* 无条件跳转到 label */ Q_JMPZ /* if a 0 跳转到 label */ } QuadOp; typedef struct { QuadOp op; char a[32], b[32], c[32]; } Quad; static Quad quads[4096]; static int nquads 0;这里a、b是源操作数c是目标。Q_ASSIGN只用到a和cQ_JMPZ用到a和c因为 c 存标签名。临时变量命名规则是t0、t1、t2……用一个计数器生成。注意我没让label单独做字符串拼接而是直接用L0、L1这种可读名字。指令集为什么这么小因为小型语言只需要表达式求值和赋值控制流可以后续再加if和while的跳转。指令类型每多一种print_assembly和后续解释器就要多一个分支调试面积成倍增加。先做到能跑再扩展指令集这才是 C 项目的正确节奏。4.2 语法制导翻译在递归下降里顺手发指令最简单的方式是在语法分析的函数里直接生成三地址码。给parse_expr_t加上返回值每个子表达式返回其结果的存放位置变量名或临时变量名父表达式生成一条运算指令。/* 生成代码时的临时变量分配 */ static int temp_count 0; char *new_temp(void) { static char buf[32]; /* 静态缓冲区调用方必须立即拷贝 */ snprintf(buf, sizeof(buf), t%d, temp_count); return buf; } void emit(QuadOp op, const char *a, const char *b, const char *c) { if (nquads 4096) { fprintf(stderr, 四元式数量超过上限\n); exit(1); } snprintf(quads[nquads].a, sizeof(quads[nquads].a), %s, a ? a : ); snprintf(quads[nquads].b, sizeof(quads[nquads].b), %s, b ? b : ); snprintf(quads[nquads].c, sizeof(quads[nquads].c), %s, c ? c : ); nquads; } char *parse_expr_t(void) { char *left parse_term_t(); while (tok[pos_tok].type T_PLUS || tok[pos_tok].type T_MINUS) { int op tok[pos_tok].type; pos_tok; char *right parse_term_t(); char tmp[32]; new_temp_to(tmp); /* 把名字写进 tmp */ emit(op T_PLUS ? Q_ADD : Q_SUB, left, right, tmp); left strdup(tmp); /* 注意后续要 free */ } return left; } char *parse_factor_t(void) { char tmp[32]; if (tok[pos_tok].type T_NUM) { snprintf(tmp, sizeof(tmp), %d, tok[pos_tok].value); pos_tok; return strdup(tmp); } if (tok[pos_tok].type T_ID) { int idx lookup_symbol(tok[pos_tok].text); if (idx 0) { fprintf(stderr, 第 %d 行变量 %s 未声明\n, tok[pos_tok].line, tok[pos_tok].text); exit(1); } pos_tok; return strdup(tok[pos_tok - 1].text); } if (tok[pos_tok].type T_LPAREN) { pos_tok; char *e parse_expr_t(); expect(T_RPAREN); return e; } fprintf(stderr, 第 %d 行表达式格式错误\n, tok[pos_tok].line); exit(1); }这段代码里strdup是必须的。我的new_temp返回静态缓冲区第二次调用就会覆盖第一次的内容——这是 C 语言里最常见的内存管理踩坑点。如果parse_term_t返回的left指向同一块静态内存后续emit时拿到的值就已经被改写了。strdup每次分配新内存配合free才能保证每层表达式的名字互不干扰。关于查符号表parse_factor_t里遇到T_ID时立即查符号表未声明直接报错。这一步把语义检查嵌进了语法翻译过程省掉了一次独立的语义分析遍历。代价是符号表必须在进入表达式翻译前已经填充完毕——所以声明语句的翻译要先于表达式语句执行。4.3 从三地址码到可执行一个 printf 输出器就够生成完四元式最后一步是把它翻译成一句话能讲清楚的汇编风格代码。这里我不做真实汇编而是输出一种简化指令并提供一个模拟器来执行。void print_assembly(void) { for (int i 0; i nquads; i) { Quad *q quads[i]; switch (q-op) { case Q_ASSIGN: printf( LOAD %s\n STORE %s\n, q-a, q-c); break; case Q_ADD: printf( LOAD %s\n ADD %s\n STORE %s\n, q-a, q-b, q-c); break; case Q_SUB: printf( LOAD %s\n SUB %s\n STORE %s\n, q-a, q-b, q-c); break; case Q_MUL: printf( LOAD %s\n MUL %s\n STORE %s\n, q-a, q-b, q-c); break; case Q_DIV: printf( LOAD %s\n DIV %s\n STORE %s\n, q-a, q-b, q-c); break; default: break; } } }这段输出对应的执行模型是LOAD x把变量 x 的值压入栈ADD y弹出栈顶与 y 相加后压回STORE t1弹出栈顶存入 t1。用符号名代替寄存器地址实现时可以维护一张name - value的映射表。这条路线比直接生成 x86 汇编简单得多也更适合验证语义是否正确。注意print_assembly里的LOAD和STORE参数顺序是我自己定义的。你在自己的实现里要写清楚每个伪指令的语义否则过两天自己都看不懂。我一般会在代码文件头部注释里写一段伪指令规范比在代码里到处加注释更有效。5. 编译程序调试避坑5 个让 C 实现崩溃的典型错误这部分全是实操中反复出现的坑。每一条我都按「现象 → 原因 → 解决」来说照着对照能省下你几个晚上的排查时间。5.1 词法分析器丢字符现象输入12;识别出的数字是1但变成2的第一个字符或者运算符莫名缺失。原因用getchar()边读边扫时为了判断数字结束多读了一个字符比如读到这个字符没有回退机制被直接丢弃。ungetc()只能回退一个字符多层回退或交替回退加前读会互相覆盖。文件缓冲区的处理一旦没走对这种 bug 就随时冒头。解决统一走“整文件读入内存 下标扫描”路线就是 2.2 的做法。如果坚持用流式读取务必用ungetc实现精确回退并且每次回退后立即读回中间不能夹其他读操作。我自己的血泪经验是词法分析器绝不边读边处理边界先把fread或者fgets拿到的缓冲区当作唯一数据源。5.2 左递归文法导致爆栈现象输入a 1 2;程序在parse_expr里不断递归最后栈溢出报Segmentation fault或者直接卡死。原因把文法里expr - expr term | term这条左递归规则原封不动翻译成递归下降函数parse_expr每次都调用自己没有任何基线条件。解决用右结合循环改写。parse_expr内先parse_term()然后while(遇到 或 -)继续parse_term()。同一个模式适用于所有优先级层级。顺便说一句真正无限制的嵌套表达式比如括号套括号套 100 层是会让所有递归下降实现爆栈的但正常代码不可能这么写。5.3 临时变量名被覆盖现象生成的中间代码里t0出现了几十次但每个t0对应的值来源不同执行结果错乱。原因new_temp()返回静态缓冲区指针两次调用指向同一个地址。比如parse_expr_t先得到left t0再parse_term_t后生成right new_temp()此时left可能已经变成t1了。解决两个层面。一是new_temp提供出参版本void new_temp_to(char *out)调用方保证缓冲区足够大二是所有跨函数传递的临时变量名必须strdup拷贝。后者的代价是内存泄漏风险所以定制小型语言时要定好规则临时变量名在emit之后就没人再用了可在emit内部做一次完全复制释放由后续统一管理。这里其实是 C 语言指针使用的典型场景宁可多写一层拷贝也不要赌调用顺序。5.4 错误恢复变成死循环现象测试程序里有一个括号不匹配编译器输出几百条重复错误最后打印“四元式数量超过上限”退出。原因synchronize()的跳转条件写错。比如只在while里检查tok[pos_tok].type T_SEMI但当前 token 恰好是T_EOF循环永远不会推进或者同步点选择得太少解析器跳不出出错的区域。解决synchronize里必须同时检查T_EOF并且要有“至少前进一个 token”的保障。再加一道保险设置最大错误数比如 10 个超过后打印“错误过多编译终止”并退出。这道保险不是用来兜底的而是防止打印缓冲刷屏影响定位真正的问题。5.5 未声明变量等到代码生成才报错现象a b 1;中b未声明编译器运行时出现“符号表查无此项”或者生成了错误的地址。原因符号表查询放在emit之后导致语义错误在四元式已经生成一半时才爆出此时nquads状态已经乱了。解决把符号表查询提前到parse_factor_t见 4.2——在生成任何中间代码之前所有T_ID必须先过lookup_symbol查不到直接exit(1)。既然是小编译程序“编译失败”并不是丢人的事明确报错比吞掉错误继续跑更符合用户预期。这里多说一句为符号表声明和引用各加一个计数器诊断信息会更完整因为你能区分“确实未声明”和“作用域里不可见”两种情况。6. 从能跑到能用一个最小测试集与 gdb 验证习惯程序写完了怎么证明它是对的我的习惯是准备两个文件一个放合法用例一个放非法用例然后每次改完代码跑一遍。test_ok.c内容我一般这么设计int a; int b; a 1 2 * 3; b (a 4) * 2; return 0;合法用例要覆盖数字常量、变量赋值、括号改变优先级、连续加减乘除。test_err.c则准备三类错误未声明变量、缺分号、右括号缺失。跑非法用例时重点不是看程序是否退出而是看错误信息里的行号能不能指到正确位置——这个是靠tok[pos_tok].line打出来的如果跑到后面几行才报错说明词法分析的line计数出了问题。调试时的 gdb 命令我固定用这几条gdb ./compiler break parse_factor_t run test_ok.c print pos_tok print tok[pos_tok].type print tok[pos_tok].text nextprint tok[pos_tok].type能直接看到当前 token 的类型配合next单步走到递归深处很快能定位状态机卡在哪个分支。C 语言调试不依赖 IDE 的高亮提示gdb 的断点加打印就是最快的定位手段。如果你发现某一行代码改完后所有测试都过但一加新语法就崩优先怀疑新增分支里是否有strcpy越界或数组下标越界用valgrind ./compiler test_ok.c跑一遍会比肉眼快得多。另一个提升可靠性的习惯是在关键位置加断言。比如emit函数里nquads每次增加前检查是否小于 4096parse_factor_t里pos_tok增加后立刻检查是否大于MAX_TOKENS。这些assert在发布前可以留到#ifdef里但开发期不要删。我自己的习惯是宁可运行时崩溃暴露问题也不要让非法状态悄悄传播到几百行之后才爆。最后给临时变量命名加个上限检查。如果生成的t变量超过 1000 个说明表达式翻译逻辑里有死循环或漏了pos_tok推进。这种异常跑不到编译结束打印中间四元式列表就能看出来——我一般会在print_assembly里顺带打印nquads用来快速判断代码生成是否异常膨胀。以上这套做法从词法分析到中间代码生成再到测试和调试基本就是我用 C 语言实现小型编译程序的完整路径。这种工程看起来难但每一步拆开都有可验证的产出词法阶段有 token 列表语法阶段能画出表达式树代码生成阶段有伪汇编。沿着这条链路走一遍你收获的不仅仅是一个能跑的小编译器——你对“一段字符串是怎么变成可执行指令的”这个过程的理解会彻底从原来的黑匣子变成白盒。希望帮到你。本文还有配套的精品资源点击获取