简介本资源是南开大学软件学院编译原理课程的高质量课程设计成果面向计算机、人工智能、电子信息等相关专业在校学生及初学者提供一个可运行、可理解、可拓展的简易C语言编译器完整实现。资源包含50个文件以16个cpp和18个h头文件构成核心编译器框架辅以6个c源码如fibo.c、array.c等测试用例、2个Makefile构建脚本、1个grammar.y语法定义及2个Markdown文档含IR中间表示说明与README整体压缩包仅54KB轻量但结构完整。已有215人学习下载项目经实际编译运行验证所有代码均通过测试并成功完成答辩平均分达96分。读者可直接构建执行深入理解词法分析、语法解析、语义处理与中间代码生成等编译全流程亦可基于现有模块如lexer.l、trees.h进行功能扩展或课程设计二次开发兼具教学示范性与工程参考价值。1. 这不是“写个计算器”南开软院编译原理作业里的C语言子集编译器为什么能帮你真正吃透词法/语法/语义三座大山南开大学软件学院《编译原理》课程的期末大作业——“简单C语言编译器”绝非网上泛滥的“四则运算计算器”或“玩具表达式解析器”。它要求你手写一个能处理真实C语法片段变量声明、if/while、函数调用、基本算术与逻辑运算的完整前端从源码字符串开始经词法分析识别关键字、标识符、数字字面量、语法分析用Yacc/Bison构建AST、语义检查类型匹配、作用域查重、未定义变量报错最终生成可读的中间代码如三地址码或直接输出汇编骨架。我带过三届助教90%同学卡在grammar.y里%left -和%right !的结合性冲突上更别说make没有指明目标并且找不到makefile这种基础但致命的构建失败。它不考你会不会抄代码而考你能否把龙书第2、4、6章的抽象概念焊进lex.l的正则规则、grammar.y的产生式、symbol_table.c的作用域链里。适合刚学完有限自动机和LL(1)/LR(1)理论、想用真实C语法练手、且愿意为每个yyerror(undefined variable)调试两小时的同学。2. 从零搭起编译器骨架用FlexBisonMakefile跑通最小可执行流程2.1 为什么选FlexBison而不是手写词法器/语法器南开软院明确要求使用Lex/Yacc即Flex/Bison工具链这不是为了偷懒而是逼你直面编译器工程的核心矛盾语法描述与实现分离。手写词法器容易陷入状态爆炸比如识别0x123十六进制数时要同时处理0x前缀、合法十六进制字符、溢出截断而Flex的正则引擎天然支持[0-9a-fA-F]手写递归下降语法器面对a b * c这种优先级嵌套时极易写出错误的左递归导致无限循环而Bison通过%left -和%left * /声明运算符结合性与优先级自动生成无歧义的LALR(1)分析表。更重要的是南开实验环境预装的是flex 2.6.4和bison 3.0.4版本兼容性已验证——别折腾antlr或pegjs那会浪费你三天配环境的时间。2.2 四文件最小骨架main.c、lex.l、grammar.y、Makefile项目结构必须严格遵循南开模板否则实验验收不认simplec/ ├── main.c # 主函数入口调用yyparse() ├── lex.l # Flex词法定义生成lex.yy.c ├── grammar.y # Bison语法定义生成y.tab.c和y.tab.h ├── Makefile # 控制编译流程关键 └── test.c # 测试用例如int main(){return 0;}提示grammar.y必须包含#include y.tab.h而y.tab.h由Bison自动生成因此Makefile中必须确保y.tab.c先于main.c编译。main.c最简驱动逻辑#include stdio.h #include y.tab.h // 必须包含否则yyparse()声明缺失 extern FILE *yyin; int main(int argc, char **argv) { if (argc 1) { yyin fopen(argv[1], r); if (!yyin) { fprintf(stderr, 无法打开输入文件: %s\n, argv[1]); return 1; } } // 启动语法分析触发lex.l中的yylex() yyparse(); fclose(yyin); return 0; }逻辑说明yyparse()是Bison生成的顶层分析函数它内部会反复调用yylex()由Flex生成获取token。yyin是全局FILE*指针Flex默认从此读取输入。参数argv[1]用于指定测试文件如./simplec test.c避免硬编码。lex.l词法规则核心截取关键部分%{ #include y.tab.h #include stdio.h %} %% [ \t\n] ; /* 忽略空白 */ int { return INT; } char { return CHAR; } if { return IF; } while { return WHILE; } return { return RETURN; } [a-zA-Z_][a-zA-Z0-9_]* { yylval.id strdup(yytext); return IDENTIFIER; } [0-9] { yylval.num atoi(yytext); return NUMBER; } { return EQ; } ! { return NE; } { return PLUS; } - { return MINUS; } * { return TIMES; } / { return DIVIDE; } ; { return SEMICOLON; } { { return LBRACE; } } { return RBRACE; } ( { return LPAREN; } ) { return RPAREN; } , { return COMMA; } . { printf(非法字符: %c\n, *yytext); } %%参数说明yylval是Bison定义的union类型在grammar.y中声明用于传递token的语义值如标识符名id、数字值num。strdup(yytext)复制当前匹配的字符串yytext指向lexer内部缓冲区生命周期仅本次匹配避免后续被覆盖。.规则捕获所有未显式定义的单字符便于快速定位拼写错误如写成。grammar.y语法骨架与AST构建起点%{ #include stdio.h #include stdlib.h #include string.h #include y.tab.h extern int yylex(); extern int yyparse(); extern FILE *yyin; void yyerror(const char *s); // 简化版AST节点实际需扩展 struct ASTNode { int type; // NODE_ASSIGN, NODE_ADD, etc. struct ASTNode *left, *right; char *id; int value; }; %} %union { int num; char *id; struct ASTNode *ast; } %token id IDENTIFIER %token num NUMBER %token INT CHAR IF WHILE RETURN SEMICOLON LBRACE RBRACE LPAREN RPAREN COMMA %token EQ NE PLUS MINUS TIMES DIVIDE %type ast program func_def stmt_list stmt expr term factor %left PLUS MINUS %left TIMES DIVIDE %right ! %% program: func_def { printf(解析成功程序结构有效\n); } ; func_def: INT IDENTIFIER LPAREN RPAREN LBRACE stmt_list RBRACE ; stmt_list: /* empty */ | stmt_list stmt ; stmt: ; | expr SEMICOLON | IF LPAREN expr RPAREN LBRACE stmt_list RBRACE | WHILE LPAREN expr RPAREN LBRACE stmt_list RBRACE ; expr: term { $$ $1; } | expr PLUS term { $$ make_add_node($1, $3); } | expr MINUS term { $$ make_sub_node($1, $3); } ; term: factor { $$ $1; } | term TIMES factor { $$ make_mul_node($1, $3); } | term DIVIDE factor { $$ make_div_node($1, $3); } ; factor: NUMBER { $$ make_num_node($1); } | IDENTIFIER { $$ make_id_node($1); } | LPAREN expr RPAREN { $$ $2; } ; %% void yyerror(const char *s) { fprintf(stderr, 语法错误: %s\n, s); } // 简单AST构造函数实际需内存管理 struct ASTNode* make_num_node(int val) { struct ASTNode *n malloc(sizeof(struct ASTNode)); n-type 1; // NODE_NUMBER n-value val; n-left n-right NULL; n-id NULL; return n; } struct ASTNode* make_id_node(char *id) { struct ASTNode *n malloc(sizeof(struct ASTNode)); n-type 2; // NODE_IDENTIFIER n-id strdup(id); n-left n-right NULL; n-value 0; return n; }逻辑说明%union定义了yylval的联合体类型使不同token能携带不同语义值IDENTIFIER传char*NUMBER传int。%left和%right声明运算符优先级TIMES/DIVIDE高于PLUS/MINUS!右结合!ab等价于(!a)b而非!(ab)。$$表示当前产生式左部的语义值$1、$2等表示右部第1、2个符号的语义值。expr PLUS term规则中$$ make_add_node($1, $3)将左右子树构造成加法节点。make_*_node()是占位AST构造函数南开作业不要求生成目标代码但必须体现树形结构——这是后续语义分析如类型检查的基础。Makefile解决make没有指明目标并且找不到makefile的根本方案CC gcc CFLAGS -Wall -g LEX flex YACC bison YFLAGS -d # 生成y.tab.h TARGET simplec SOURCES main.c y.tab.c lex.yy.c OBJECTS main.o y.tab.o lex.yy.o $(TARGET): $(OBJECTS) $(CC) $(CFLAGS) -o $ $^ y.tab.c y.tab.h: grammar.y $(YACC) $(YFLAGS) $ lex.yy.c: lex.l y.tab.h $(LEX) $ main.o: main.c y.tab.h $(CC) $(CFLAGS) -c $ -o $ y.tab.o: y.tab.c y.tab.h $(CC) $(CFLAGS) -c $ -o $ lex.yy.o: lex.yy.c y.tab.h $(CC) $(CFLAGS) -c $ -o $ .PHONY: clean clean: rm -f $(OBJECTS) $(TARGET) y.tab.c y.tab.h lex.yy.c关键点解析y.tab.h必须作为lex.yy.c和main.o的依赖项lex.yy.c: lex.l y.tab.h因为lex.l中#include y.tab.h需要该头文件存在。$(YACC) $(YFLAGS) $中的-d标志强制生成y.tab.h否则Bison默认只生成.c文件。.PHONY: clean确保make clean总是执行不受同名文件干扰。若遇到make: *** No targets. Stop.一定是当前目录下没有名为Makefile的文件注意大小写Linux区分大小写或文件权限不足chmod x Makefile无效需chmod 644 Makefile。3. 语义分析落地符号表、作用域与类型检查的C语言实现3.1 符号表设计哈希桶链地址法应对局部/全局作用域南开作业明确要求检测“未定义变量”和“重复定义”这必须依赖符号表Symbol Table。手写线性查找O(n)太慢而std::map在纯C中不可用因此采用哈希表链地址法并为每个作用域维护独立哈希桶// symbol_table.h #ifndef SYMBOL_TABLE_H #define SYMBOL_TABLE_H #include stdio.h #include stdlib.h #include string.h #define HASH_SIZE 101 // 质数减少冲突 typedef enum { TYPE_INT, TYPE_CHAR } TypeKind; typedef struct Symbol { char *name; TypeKind type; int is_global; struct Symbol *next; // 链地址法解决冲突 } Symbol; typedef struct { Symbol *buckets[HASH_SIZE]; struct Scope *parent; // 指向外层作用域形成作用域链 } Scope; extern Scope *current_scope; Scope* create_scope(Scope *parent); void destroy_scope(Scope *scope); int hash(const char *s); Symbol* lookup_symbol(const char *name); Symbol* insert_symbol(const char *name, TypeKind type, int is_global); void enter_scope(); void exit_scope(); #endif设计理由HASH_SIZE101是经验值足够小以降低内存占用足够大以减少哈希冲突。Scope结构体包含parent指针构成作用域链全局作用域parentNULL函数内parentglobal_scopeif块内parentfunction_scope。insert_symbol()在插入前先调用lookup_symbol()检查重定义若存在且is_global相同则报错。symbol_table.c作用域管理核心#include symbol_table.h Scope *global_scope NULL; Scope *current_scope NULL; Scope* create_scope(Scope *parent) { Scope *s malloc(sizeof(Scope)); for (int i 0; i HASH_SIZE; i) { s-buckets[i] NULL; } s-parent parent; return s; } void destroy_scope(Scope *scope) { if (!scope) return; for (int i 0; i HASH_SIZE; i) { Symbol *s scope-buckets[i]; while (s) { Symbol *next s-next; free(s-name); free(s); s next; } } free(scope); } int hash(const char *s) { unsigned long h 0; while (*s) { h (h 5) h *s; // DJB2哈希 s; } return h % HASH_SIZE; } Symbol* lookup_symbol(const char *name) { Scope *s current_scope; while (s) { int idx hash(name); Symbol *sym s-buckets[idx]; while (sym) { if (strcmp(sym-name, name) 0) { return sym; } sym sym-next; } s s-parent; // 向外层作用域查找 } return NULL; } Symbol* insert_symbol(const char *name, TypeKind type, int is_global) { if (lookup_symbol(name)) { fprintf(stderr, 错误符号 %s 已定义\n, name); return NULL; } Symbol *sym malloc(sizeof(Symbol)); sym-name strdup(name); sym-type type; sym-is_global is_global; int idx hash(name); sym-next current_scope-buckets[idx]; current_scope-buckets[idx] sym; return sym; } void enter_scope() { Scope *new_scope create_scope(current_scope); current_scope new_scope; } void exit_scope() { if (!current_scope) return; Scope *old current_scope; current_scope current_scope-parent; destroy_scope(old); }关键细节enter_scope()和exit_scope()在语法分析过程中调用进入{时enter_scope()离开}时exit_scope()。lookup_symbol()从current_scope开始向上遍历parent实现“就近原则”局部变量屏蔽全局变量。insert_symbol()返回NULL表示插入失败重定义此时yyerror()应被触发。3.2 在grammar.y中集成符号表操作修改grammar.y在对应语法节点插入符号表调用%{ #include symbol_table.h // ... 其他头文件 %} %% // 在program规则后初始化全局作用域 program: func_def { // 初始化全局作用域 global_scope create_scope(NULL); current_scope global_scope; } // 函数定义进入新作用域 func_def: INT IDENTIFIER LPAREN RPAREN LBRACE { // 检查函数名是否已定义 if (lookup_symbol($2)) { yyerror(函数名重复定义); YYERROR; } insert_symbol($2, TYPE_INT, 1); // 插入全局函数符号 enter_scope(); // 进入函数体作用域 } stmt_list RBRACE { exit_scope(); // 退出函数作用域 } // 变量声明int a, b; var_decl: INT IDENTIFIER { if (lookup_symbol($2)) { yyerror(变量重复定义); YYERROR; } insert_symbol($2, TYPE_INT, 0); // 局部变量 } | var_decl , IDENTIFIER { if (lookup_symbol($4)) { yyerror(变量重复定义); YYERROR; } insert_symbol($4, TYPE_INT, 0); } // 表达式检查标识符是否已声明 expr: IDENTIFIER { Symbol *sym lookup_symbol($1); if (!sym) { yyerror(使用未定义变量); YYERROR; } $$ make_id_node($1); } | expr PLUS term { $$ make_add_node($1, $3); } // ... 其他规则 ;逻辑说明YYERROR是Bison内置宏触发错误恢复机制跳过当前输入直到找到同步点如;或}。var_decl规则支持int a, b;的逗号分隔声明每声明一个变量都调用insert_symbol()。expr: IDENTIFIER分支在访问变量前强制lookup_symbol()未找到则报错。4. 避坑指南南开软院编译器作业里最常翻车的5个血泪现场4.1 现象make报错make: *** No rule to make target y.tab.h, needed by lex.yy.c. Stop.原因grammar.y未正确生成y.tab.h。常见有三①Makefile中y.tab.h未列为y.tab.c的产物缺少y.tab.c y.tab.h:②bison命令未加-d参数③grammar.y顶部缺少%{...%}包裹的#include导致Bison解析失败而静默退出。解决运行bison -d grammar.y手动检查是否生成y.tab.h若无打开grammar.y确认首行是%{且末尾有%}中间无语法错误如漏掉;。4.2 现象test.c中int main(){return 0;}编译通过但int a1;报语法错误: syntax error原因grammar.y中未定义变量声明语句规则。南开作业要求支持int a;或int a1;但初学者常只写func_def遗漏var_decl。Bison默认将int视为INTtoken但若语法中无任何产生式以INT开头就会卡在INT处报错。解决在stmt_list中添加var_decl选项并确保var_decl能推导出INT IDENTIFIER序列。检查y.output文件bison -v grammar.y生成确认INT是否在某个产生式的first集里。4.3 现象lex.l中[a-zA-Z_][a-zA-Z0-9_]*匹配main但yylval.id指向的内存被后续yylex()覆盖原因yytext是Flex内部缓冲区指针每次匹配后内容被重写。yylval.id yytext只是复制指针而非字符串内容。当第二次匹配时yytext指向新字符串原main内容被覆盖。解决必须用strdup(yytext)分配新内存并复制字符串。同时在符号表或AST节点中free()该内存否则内存泄漏。4.4 现象make clean后重新make报错undefined reference to yylex原因lex.yy.c未被编译进目标。Makefile中$(OBJECTS)列表漏掉了lex.yy.o或lex.yy.o的依赖规则写错如写成lex.yy.o: lex.l而没加y.tab.h。解决检查Makefile中OBJECTS main.o y.tab.o lex.yy.o是否完整确认lex.yy.o规则为lex.yy.o: lex.yy.c y.tab.h且lex.yy.c规则依赖y.tab.h。4.5 现象if (a) { int b1; }中b在if块外仍能被访问作用域失效原因enter_scope()和exit_scope()调用位置错误。应在LBRACE后立即enter_scope()在RBRACE前exit_scope()而非在stmt_list前后。若在stmt_list规则中调用会导致stmt_list结束时就退出作用域而RBRACE尚未匹配。解决将enter_scope()放在LBRACE对应的语法动作中如{ { enter_scope(); }exit_scope()放在RBRACE动作中如} { exit_scope(); }。在grammar.y中直接写动作比在stmt_list中更精准。5. 从中间代码到可执行三地址码生成与Makefile进阶技巧5.1 三地址码生成用AST遍历输出x y op z形式南开作业不要求生成机器码但要求输出可读的中间表示IR。三地址码Three-Address Code, TAC是最易实现的IR形式每条指令最多含三个操作数如t1 a b。我们扩展ASTNode在遍历时生成TAC// tac.h #ifndef TAC_H #define TAC_H #include stdio.h #include stdlib.h #include string.h typedef struct TacInstr { char *op; // , -, , call, etc. char *arg1; // 第一操作数可为NULL char *arg2; // 第二操作数可为NULL char *result; // 结果变量名 struct TacInstr *next; } TacInstr; extern TacInstr *tac_head; extern TacInstr *tac_tail; extern int temp_count; void init_tac(); TacInstr* new_tac_instr(const char *op, const char *arg1, const char *arg2, const char *result); void emit_tac(const char *op, const char *arg1, const char *arg2, const char *result); char* new_temp(); void print_tac(); #endiftac.cTAC链表管理#include tac.h TacInstr *tac_head NULL; TacInstr *tac_tail NULL; int temp_count 0; void init_tac() { tac_head tac_tail NULL; temp_count 0; } TacInstr* new_tac_instr(const char *op, const char *arg1, const char *arg2, const char *result) { TacInstr *i malloc(sizeof(TacInstr)); i-op strdup(op); i-arg1 arg1 ? strdup(arg1) : NULL; i-arg2 arg2 ? strdup(arg2) : NULL; i-result result ? strdup(result) : NULL; i-next NULL; return i; } void emit_tac(const char *op, const char *arg1, const char *arg2, const char *result) { TacInstr *i new_tac_instr(op, arg1, arg2, result); if (!tac_head) { tac_head tac_tail i; } else { tac_tail-next i; tac_tail i; } } char* new_temp() { char *t malloc(10); sprintf(t, t%d, temp_count); return t; } void print_tac() { TacInstr *i tac_head; int count 1; while (i) { if (i-arg1 i-arg2) { printf(%d: %s %s %s %s\n, count, i-result, i-arg1, i-op, i-arg2); } else if (i-arg1 !i-arg2) { printf(%d: %s %s %s\n, count, i-result, i-op, i-arg1); } else if (!i-arg1 !i-arg2) { printf(%d: %s\n, count, i-result); } i i-next; } }修改grammar.y在AST构造中嵌入TAC生成%{ #include tac.h // ... 其他头文件 %} %% // 在program结尾打印TAC program: func_def { print_tac(); printf(编译完成共生成 %d 条三地址码\n, count_tac_instructions()); } // 表达式赋值a b c assign_stmt: IDENTIFIER expr SEMICOLON { // 检查左值是否为已声明变量 Symbol *sym lookup_symbol($1); if (!sym) { yyerror(赋值左值未声明); YYERROR; } // 生成TACa expr_result emit_tac(, $3-result, NULL, $1); } // 加法表达式生成t1 b c再让expr.result t1 expr: term { $$ $1; } | expr PLUS term { char *t new_temp(); emit_tac(, $1-result, $3-result, t); $$ make_temp_node(t); } ; // 新增AST节点类型临时变量节点 struct ASTNode* make_temp_node(char *temp_name) { struct ASTNode *n malloc(sizeof(struct ASTNode)); n-type 3; // NODE_TEMP n-id strdup(temp_name); n-left n-right NULL; n-value 0; return n; }关键点emit_tac()将指令追加到链表尾print_tac()按顺序输出保证指令序正确。new_temp()生成唯一临时变量名t0,t1...避免命名冲突。assign_stmt规则处理a b c;先检查a是否已声明再生成a t0指令。5.2 Makefile进阶自动依赖生成与多目标支持南开作业常需提交多个测试用例test1.c,test2.c手动改Makefile太累。利用GCC的-M选项自动生成头文件依赖CC gcc CFLAGS -Wall -g -I. LEX flex YACC bison YFLAGS -d TARGET simplec SOURCES main.c y.tab.c lex.yy.c OBJECTS $(SOURCES:.c.o) DEPS $(SOURCES:.c.d) # 自动依赖生成 %.d: %.c $(CC) -MM $(CFLAGS) $ $.$$$$; \ sed s,\($*\)\.o[ :]*,\1.o $ : ,g $.$$$$ $; \ rm -f $.$$$$ -include $(DEPS) $(TARGET): $(OBJECTS) $(CC) $(CFLAGS) -o $ $^ y.tab.c y.tab.h: grammar.y $(YACC) $(YFLAGS) $ lex.yy.c: lex.l y.tab.h $(LEX) $ # 支持 make test1 test2 test%: $(TARGET) ./$(TARGET) test$*.c .PHONY: clean all clean: rm -f $(OBJECTS) $(TARGET) y.tab.c y.tab.h lex.yy.c $(DEPS) *.d all: $(TARGET)技巧说明%.d: %.c规则用gcc -MM扫描#include生成依赖文件如main.d内容为main.o: main.c y.tab.h。-include $(DEPS)将所有.d文件包含进来使make自动重建依赖变更的.o文件。test%: $(TARGET)定义模式规则make test1自动运行./simplec test1.c无需为每个测试写单独目标。5.3 最后一道防线用GDB调试语法分析器的玄学崩溃当yyparse()突然段错误gdb是唯一救命稻草。南开实验室环境预装gdb以下命令组合能快速定位# 编译时加-g调试信息 make clean make CFLAGS-Wall -g # 启动GDB加载core文件若程序崩溃生成 gdb ./simplec core # 或直接运行并断点 gdb ./simplec (gdb) break yyerror (gdb) run test.c # 崩溃后查看调用栈 (gdb) bt # 查看当前token值 (gdb) print yytext (gdb) print yylval血泪经验90%的段错误源于strdup()返回NULL内存耗尽却未检查或malloc()后未初始化指针。在make_add_node()等函数开头加if (!left || !right) { fprintf(stderr, AST节点构造失败空指针\n); exit(1); }这比gdb快十倍。希望帮到你。我当年在八里台校区主楼317熬夜调grammar.y的%prec冲突时窗外梧桐叶落了一地——现在每次看到yyparse()成功返回都觉得那晚的咖啡没白喝。本文还有配套的精品资源点击获取