简介面向编译原理课程学习、课程设计与小型编译器实践者这份 SNL 语言编译器源码包给出从词法分析、语法递归与 LL(1) 分析到语义处理、主程序调用的完整实现线索可用于对照课堂理论理解编译前端各阶段的衔接方式也适合作为课程实验的参考底稿。压缩包为 zip 格式共 231 个文件、约 77.55MB主体包含 C/C 源码与少量头文件并配有 sln、vcxproj 等 Visual Studio 工程配置以及 exe 可执行文件、obj/pdb/ipch/tlog 等编译调试中间文件和日志便于直接查看工程结构、复现构建过程与排查运行问题。目前已有 1179 人学习。读者可据此梳理 SNL 语言从源程序输入到语义检查的模块划分参考词法分析、语法分析与语义程序的实现思路并结合可执行文件快速验证多套工程与调试产物也方便对比不同实现版本和定位常见错误。1. SNL语言编译器源码一份能把编译原理从期末考卷拽回终端的代码课设答辩前一晚最怕的不是程序跑不出结果而是被追问一句「你这个语法分析器为什么这么写」。这份 SNL语言编译器源码的价值就在这里SNLSimple Nested Language是一门教学用的嵌套语言而这份 C/C 源码把它从字符流一路干到可执行结果——词法扫描、递归下降语法分析、符号表与类型检查、四元式中间代码生成最后接一个栈式虚拟机解释执行。它适合两类人一是编译原理课设需要交完整前端、又不想只交一堆看不懂的生成式解析器骨架的人二是工作几年后想把「编译器前端到底怎么落地」补上的人。整份代码规模不大但分层清楚改起来不心虚。2. 工程结构拆解五个模块的边界在哪里2.1 一份典型的源码目录长什么样这类课程级编译器源码通常不是一个大文件硬写完的而是按编译阶段切成若干编译单元每个单元配一个头文件对外暴露少量接口。我第一次拿到这份代码时先扫了一遍目录看到模块划分心里就有底了——它不是那种「所有函数都塞在 main.c 里」的作业。文件职责改动频率globals.h跨模块共享的 Token、语法树节点、四元式、错误码定义高加语法就要动util.c/h内存分配、字符串池、打印缩进、错误输出低lexer.c/h字符流到 Token 序列的扫描器维护行号低加关键字才动parse.c/h递归下降语法分析产出语法树高symtab.c/h哈希桶符号表作用域链的压入与弹出中analyze.c/h遍历语法树做类型检查、符号解析高code.c/h四元式生成、跳转回填中main.c命令行入口串起整条流水线低test/*.snl示例源程序随便加拆成这个粒度最大的好处是当你只想验证「while 语句的四元式对不对」时只需要在parse.c和code.c之间来回看不必翻遍全文。代价是结构体定义必须集中否则symtab.c想用一个TreeNode就得反向包含parse.h很容易搞出循环依赖。2.2 层与层之间的约定三个核心数据结构编译器的模块化不是靠注释喊出来的是靠数据结构固定下来的。上层往下层传什么、下层往上返回什么全靠这几个结构体约束。/* globals.h —— 各模块共享的数据结构改这里等于改契约 */ typedef enum { TK_NUM, TK_ID, TK_CHAR, /* 字面量与标识符 */ TK_IF, TK_THEN, TK_ELSE, TK_END, /* 关键字加语句先加这里 */ TK_WHILE, TK_DO, TK_VAR, TK_PROC, TK_ASSIGN, TK_EQ, TK_LT, TK_PLUS, TK_MINUS, TK_LPAREN, TK_RPAREN, TK_SEMI, TK_EOF, TK_ERR } TokenType; typedef struct { TokenType type; /* 供 switch 分派决定语法分支 */ char lexeme[64];/* 原始拼写报错时直接打印给人看 */ int line; /* 行号错误定位的关键依据 */ union { int ival; char cval; } val; /* 字面量的真实值 */ } Token; typedef struct TreeNode { enum { StmtK, ExpK } nodekind; enum { IfK, WhileK, AssignK, ReadK, WriteK, CompoundK } stmt; enum { OpK, ConstK, IdK } exp; TokenType attr_op; /* 运算符 */ int attr_val; /* 常量值 */ char attr_name[32]; /* 标识符名 */ struct TreeNode *child[3]; /* 定长子节点够用且不用管理链表 */ struct TreeNode *sibling; /* 兄弟链表串起语句序列 */ } TreeNode;Token里多留一个lexeme是我强烈建议保留的设计很多精简版为了省事只存type和一个整数值结果报错时只能说「第 17 行有语法错误」而不能说「第 17 行的whilee附近有问题」。调试期这一条信息能省半小时。TreeNode用「子节点数组 兄弟链表」是标准做法语句序列靠sibling串成链if的 then 和 else 靠child[0]、child[1]挂上去方向明确遍历时不会绕晕。四元式则更简单本质就是一个定长数组下标即指令地址/* 四元式op, arg1, arg2, result —— 跳转类指令的 result 存目标地址 */ typedef struct { OpCode op; /* ADD/SUB/ASSIGN/JMP/JLT/LABEL/... */ int arg1, arg2; /* 操作数临时变量编号或符号表下标 */ int result; /* 目标临时变量编号或跳转目标指令下标 */ } Quad;这里有个必须统一的约定arg1/arg2/result里到底存什么。常见做法是「正数表示临时变量编号负数表示符号表下标」或者干脆全部走符号表、临时变量也塞进符号表。前一种省内存、查表快后一种实现简单、dump 出来好看。两种都行但全文必须统一中途换约定基本等于重写。我一般选后者因为四元式打印出来给人检查时能直接看到变量名。2.3 构建方式Makefile 与单文件编译源码包一般会带一个Makefile把util.c、lexer.c、parse.c、symtab.c、analyze.c、code.c、main.c一起编译成可执行文件。# 最常见的构建方式 make clean make # 产物一般是 snlc / snl / compiler看 Makefile 里的 TARGET # 如果没有 Makefile手动编译也一样 gcc -stdc99 -g -Wall -o snlc *.c-g不能省。这类代码最常见的崩溃位置是符号表查找返回空指针后继续解引用没有调试符号你只能看着段错误干瞪眼。-Wall也要留着递归下降里最容易犯的「函数声明了但某个分支忘记 return」全靠它提醒。如果 Makefile 里用了-O2建议调试期先手动降到-O0否则断点跳来跳去变量还会被优化掉。注意有些源码包把main.c里的入口写成int main(int argc, char *argv[])并直接用argv[1]当文件名不检查参数个数。第一次运行如果忘了带文件名段错误会伪装成「编译器有 bug」。3. 词法与语法分析手写扫描器 递归下降的完整链路3.1 扫描器主循环最大匹配、行号与回退手写扫描器的骨架非常简单本质是一个带前瞻的循环跳过空白、看首字符决定走哪条分支、把整个词素吃干净、返回 Token。难点全在边缘情况上——关键字和标识符前缀相同if和iffy、注释跨行、行号维护。/* lexer.c —— 每调用一次返回一个 Token靠全局游标推进 */ static char *src; /* 指向当前字符 */ static int line 1; /* 行号出错时要用 */ Token next_token(void) { /* 1. 跳过空白与换行换行必须计数 */ while (*src || *src \t || *src \n || *src \r) { if (*src \n) line; src; } Token t; t.line line; t.lexeme[0] \0; /* 2. 数字连续吃数字字符最大匹配 */ if (isdigit((unsigned char)*src)) { char *p t.lexeme; while (isdigit((unsigned char)*src)) *p *src; *p \0; t.type TK_NUM; t.val.ival atoi(t.lexeme); return t; } /* 3. 标识符或关键字先按标识符吃吃完再查关键字表 */ if (isalpha((unsigned char)*src)) { char *p t.lexeme; while (isalnum((unsigned char)*src) || *src _) *p *src; *p \0; t.type lookup_keyword(t.lexeme); /* 表里没有就返回 TK_ID */ return t; } /* 4. 运算符双字符必须优先于单字符匹配 */ if (*src ) { src; t.type TK_LT; strcpy(t.lexeme, ); return t; } if (*src : *(src 1) ) { src 2; t.type TK_ASSIGN; strcpy(t.lexeme, :); return t; } if (*src \0) { t.type TK_EOF; return t; } /* 5. 兜底吃一个未知字符返回错误 Token不要死循环 */ t.type TK_ERR; t.lexeme[0] *src; t.lexeme[1] \0; return t; }逐段说清楚第一步的换行计数是整个错误定位体系的基础\r也要一起跳过否则 Windows 换行会让扫描器把回车当成未知字符报错。第二步数字识别只处理十进制整数若要支持十六进制得在这里加0x前瞻。第三步的关键是「先吃完整的标识符再查关键字表」——反过来做就会把iffy拆成if和fy这是初学者最典型的翻车点。第四步双字符运算符必须在单字符之前判断: 和:的处理顺序写反赋值语句全线崩。第五步的兜底返回错误 Token 而不是while(1)是因为扫描器一旦卡住不前进整个程序就假死你连错在哪一行都看不到。关键字表本身就是一个静态数组加线性查找static struct { const char *word; TokenType type; } keywords[] { {if, TK_IF}, {then, TK_THEN}, {else, TK_ELSE}, {end, TK_END}, {while, TK_WHILE}, {do, TK_DO}, {var, TK_VAR}, {procedure, TK_PROC}, {NULL, TK_ID} };只有十来个关键字线性查找的开销完全可以忽略不用上来就建哈希表。加新关键字只需要在这个数组里补一行别的地方一行不用动这就是把字符串和 Token 类型解耦的收益。3.2 递归下降子程序怎么写才能和 EBNF 一一对应递归下降最大的优势是「文法长什么样代码就长什么样」。比如表达式这一层EBNF 写成expr - term { (|-) term }代码里花括号对应一个while循环而不是递归调用自己——这一点非常关键用递归写左结合会产生右结合的结果1-2-3会算成1-(2-3)2而不是-4。/* parse.c —— 加减层左结合靠循环不靠递归 */ static TreeNode *expr(void) { TreeNode *t term(); /* 先拿一个项必然存在 */ while (token.type TK_PLUS || token.type TK_MINUS) { TokenType op token.type; match(op); /* 消费掉运算符 */ TreeNode *n new_node(ExpK); n-exp OpK; n-attr_op op; n-child[0] t; /* 左操作数已经算好的部分 */ n-child[1] term(); /* 右操作数递归进乘除层 */ t n; /* 结果继续当左操作数形成左倾树 */ } return t; } /* 乘除层优先级更高所以被加减层调用 */ static TreeNode *term(void) { TreeNode *t factor(); while (token.type TK_MUL || token.type TK_DIV) { TokenType op token.type; match(op); TreeNode *n new_node(ExpK); n-exp OpK; n-attr_op op; n-child[0] t; n-child[1] factor(); t n; } return t; }match()的语义是「断言当前 Token 类型符合预期符合就前进到下一个不符合就记一条语法错误」。这里有个实现细节值得抄作业match失败后不要立刻 return而是记录错误、尽量继续往下走。编译器前端如果遇到第一个错误就退出用户改一个错、重新编译、再冒一个错来回十几次体验极差。常见的补救手段是「插入式恢复」——表达式缺右括号时补一个假的右括号继续解析只要不陷入死循环多报几条错误反而更有用。语句层的子程序结构同理。stmt_sequence()循环解析语句直到遇到end或else这类结束符号statement()用switch(token.type)按首 Token 分派到stmt_if()、stmt_while()、stmt_assign()等分支。分派依据就是每个候选式的 FIRST 集写代码时对着文法表抄一遍分支顺序即可不存在玄学。3.3 语法错误的定位与信息质量错误信息质量直接决定这份代码好不好用。我见过的最低配版本只打印syntax error连行号都没有调试时只能靠二分注释源码。合格的做法是带上行号、当前 Token 的原文、以及一句人话void syntax_error(const char *msg) { fprintf(stderr, Line %d: %s (near \%s\)\n, token.line, msg, token.lexeme[0] ? token.lexeme : EOF); }token.lexeme为空时说明已经读到文件尾此时打印EOF比打印空白有用得多——很多「语法错误」的真实原因是源程序少了最后那个end报错位置在文件末尾看到EOF就知道该往哪查。再往上一步是把语法树打印出来做可视化确认。写一个print_tree(TreeNode *t, int indent)用两空格缩进递归打印几十行代码但它能让你在写语义分析之前就确认while x 10 do的条件子树挂对了位置。我一般会在main.c里加个-t开关只在需要时打印避免正常运行时刷屏。4. 语义分析与中间代码符号表、类型检查与四元式回填4.1 符号表哈希桶加作用域链SNL 支持过程和函数嵌套符号表就必然要处理作用域。最省事的实现是「一张哈希表 每个条目记录所属作用域层级 查找时取层级最深的那条」更清晰的做法是「每个作用域一张表用parent指针串成链退出作用域时整张表丢弃」。/* symtab.c —— 经典哈希桶 作用域链 */ #define BUCKET_SIZE 211 /* 常用小质数冲突率够低 */ typedef struct Bucket { char name[32]; SymbolKind kind; /* VarK / ProcK / FunK / ConstK */ Type type; /* Int / Char / Bool / Array(...) */ int memloc; /* 运行时的栈偏移代码生成时用 */ int scope_level; /* 层级越大越内层 */ struct Bucket *next; /* 同桶链表 */ } Bucket; static Bucket *table[BUCKET_SIZE]; static int current_level 0; /* 进入过程 1退出 -1 */ static unsigned hash(const char *key) { unsigned h 0; while (*key) h h * 31 (unsigned char)*key; return h % BUCKET_SIZE; } Bucket *st_lookup(const char *name) { Bucket *best NULL; for (Bucket *p table[hash(name)]; p; p p-next) { if (strcmp(p-name, name) 0 p-scope_level current_level) { if (!best || p-scope_level best-scope_level) best p; /* 取可见范围内层级最深的那个实现内层遮蔽 */ } } return best; }st_lookup里那句「取层级最深的」是内层变量遮蔽外层同名变量的核心。如果偷懒直接返回链表中第一个匹配项就会出现「内层定义了同名变量但读写的还是外层那个」的诡异现象而且这种 bug 不会报错只会算错数——属于最难受的一类问题。插入时则要防重定义但只防同层重定义var x : integer;在一个过程里写两遍应该报错外层和内层各写一个x是合法的。所以st_insert里遍历同桶时判断条件是strcmp 相等 scope_level current_level一个写错就变成「所有嵌套都用不了同名变量」。memloc字段提前给变量分配栈偏移是语义分析和代码生成之间的桥梁。常见做法是从当前作用域的基址往上递增过程调用时靠这个偏移在运行栈上定位实参和局部变量。4.2 类型检查放在哪一遍做有三种常见组织方式一是完全融进语法分析边解析边检查类似一遍式编译器二是语法树建好之后单独跑一遍analyze.c三是再拆成「符号解析」和「类型检查」两遍。这份源码走的是第二种也就是main.c里清晰的流水线/* main.c —— 五个阶段顺序不能换 */ Token t; TreeNode *tree; while ((t next_token()).type ! TK_EOF) { /* 通常由 parse 内部驱动 */ } tree parse(); /* 1. 语法树 */ if (Error) { print_errors(); return 1; } build_symtab(tree); /* 2. 建符号表先声明后使用 */ type_check(tree); /* 3. 类型检查 */ code_gen(tree); /* 4. 生成四元式 */ vm_run(); /* 5. 解释执行 */分开的好处是类型检查报错时语法树已经完整可以继续检查下一棵子树一次报出所有类型错误而不是解析到一半就中断。代价是要在树节点上多存一些信息比如「这个IdK节点解析后绑定到了符号表哪个条目」通常加一个Bucket *sym指针避免后面反复查表。类型检查本身的规则不复杂就是几条/* analyze.c —— 赋值语句的类型规则其余类似 */ static void check_assign(TreeNode *t) { Bucket *lhs st_lookup(t-child[0]-attr_name); if (lhs NULL) { sem_error(t-line, undeclared variable %s, t-child[0]-attr_name); return; } Type rt check_expr(t-child[1]); if (rt ! lhs-type) sem_error(t-line, type mismatch in assignment to %s, t-child[0]-attr_name); }关键是所有分支都要return且不能因为一次错误就中断整体遍历。很多版本在这里用exit(1)直接退出导致用户一次只能看到一个错体验和只报syntax error一样糟。4.3 四元式生成与跳转回填表达式生成四元式是自底向上的先递归生成子表达式的四元式结果放在某个临时变量里然后把临时变量编号填进当前指令的arg。/* code.c —— 表达式生成返回存放结果的临时变量编号 */ int gen_expr(TreeNode *t) { if (t-exp ConstK) { int tmp new_temp(); emit(OP_LOADI, t-attr_val, 0, tmp); /* 常量装入临时变量 */ return tmp; } if (t-exp IdK) { Bucket *b st_lookup(t-attr_name); int tmp new_temp(); emit(OP_LOAD, b-memloc, 0, tmp); /* 从栈槽读到临时变量 */ return tmp; } /* 运算符先算子节点再算自己 */ int a gen_expr(t-child[0]); int b gen_expr(t-child[1]); int r new_temp(); emit(op_of(t-attr_op), a, b, r); return r; }控制流才是真正需要技巧的地方。if和while在生成时还不知道跳转目标的具体位置——条件分支的目标是「then 之后」循环回跳的目标是「条件开头」。标准解法是回填先emit一条目标地址待定的跳转记住它的指令下标等目标位置确定后再把下标填回去。/* 回填先发一条空目标指令占位后补 */ int emit_jump(OpCode op) { return emit(op, 0, 0, -1); /* result -1 表示待回填 */ } void backpatch(int quad_index, int target) { quads[quad_index].result target; /* target 是四元式数组下标 */ } /* while 语句的生成顺序环环相扣 */ void gen_while(TreeNode *t) { int loop_start nquad; /* 条件表达式的起始位置 */ int cond gen_expr(t-child[0]); int jf emit_jump(OP_JF); /* 条件为假就跳出循环 */ gen_stmt(t-child[1]); /* 循环体 */ emit(OP_JMP, loop_start, 0, 0); /* 回跳到条件开头 */ backpatch(jf, nquad); /* 假出口 循环体之后 */ }backpatch(jf, nquad)这一句nquad在回填那一刻正好等于「循环体之后第一条指令」的下标。这个写法是整个代码生成里最容易写错的地方如果把backpatch挪到gen_stmt前面假出口就会指进循环体内部如果把loop_start记在gen_expr之后回跳会跳过条件判断变成死循环。这类错误不会在编译期暴露只能靠跑用例。临时变量计数new_temp()必须全局唯一跨语句、跨过程都不能重号。有些版本在每个函数开头把计数器清零看起来「每个函数有自己的临时变量区」很合理实际上会导致不同过程的临时变量占用同一个栈槽递归调用时直接互相覆盖。5. 跑通与排查从 make 到四元式输出的 5 个常见坑5.1 构建、运行与验证一条龙先确认能编译通过再拿示例程序跑通最后才是改代码。顺序反了容易把「环境问题」误判成「代码 bug」。# 1. 编译保留调试符号打开全部警告 make clean make CFLAGS-stdc99 -g -O0 -Wall # 2. 跑一个示例程序看整体输出 ./snlc test/while_sum.snl # 3. 只想看中间代码时走 -q 开关如果源码带了 ./snlc -q test/while_sum.snl配套的验证程序建议自己写一个语法以源码里的parse.c为准别照抄别的教材program sum_demo var i, sum : integer; begin sum : 0; i : 1; while i 11 do sum : sum i; i : i 1 end; write(sum) end期望的输出分两段四元式列表里应该能看到一个LABEL或循环条件起点、一条JLT/JF条件跳转、循环体三条赋值、一条回跳JMP程序运行结果是55。如果四元式看着合理但结果不对问题在虚拟机如果四元式本身就错了问题在代码生成阶段。用这个二分法定位比漫无目的地读代码快得多。5.2 五个真实踩过的坑坑一源文件看着没错扫描器却报未知字符。现象是在第 1 行就报unexpected character打开文件看第一行是program开头的正常内容。原因通常是文件带了 CRLF 换行或者被编辑器存成了带 BOM 的 UTF-8扫描器读到\r或\xEF就直接当非法字符。解决方式是在扫描器跳过空白的循环里加上*src \r并在文件头显式跳过 BOM 三字节实在懒得改代码用dos2unix转一遍也行。坑二while 循环永远只执行一次。现象是sum最终等于1而不是55。原因是backpatch把跳出目标填成了循环体的第一条指令下标而不是循环体之后的下标导致第一次循环结束时并没有真正跳出反而跳回体内某处然后一路走到结束。排查方法是在gen_while里临时打印jf和nquad两个数对照四元式 dump 看跳转目标落在哪条指令上一眼就能看出来。坑三语义分析阶段段错误。现象是程序在type_check里崩溃gdb 栈顶停在lhs-type那一行。原因是st_lookup返回了NULL变量未声明而代码没有判空就直接解引用。这类崩溃在「故意写一个错误程序测试报错功能」时才暴露正常用例跑不出来。解决办法是在所有st_lookup调用点强制判空并且养成习惯查表函数的返回值默认可能为 NULL先判再用。坑四递归过程调用结果错乱。现象是单个过程调用没问题一旦递归比如求阶乘结果就离谱。原因是临时变量编号在每个过程内部从 0 重新计数不同过程的临时变量映射到了同一个栈槽递归展开时相互覆盖。解决办法是把临时变量计数器做成全局的或者按过程名加前缀区段分配让每个过程的临时变量区间不重叠。坑五嵌套过程里读到了外层的同名变量。现象是内层过程声明了var x但赋值后外层看到的还是旧值。原因就是前面提到的st_lookup只返回链表中第一个匹配项没有按scope_level取最深的一层。排查方法是写一个三行的小程序外层x : 1进入内层再x : 2内层write(x)退出后再write(x)。正常应该输出2和1如果两次都是2或者都是1问题就锁死在符号表查找上。提示这五个坑里有三个的根因都是「没有判空」和「作用域没取最深」改代码之前先把这两处收紧能省掉一大半调试时间。6. 二次开发给 SNL 加一条 for 语句的完整改法拿到这份源码后最想做的事多半是「加个新语法」。for语句是最合适的练手目标因为它能一次性串起词法、语法、语义、代码生成四个阶段改完你就彻底摸清这条流水线了。第一步globals.h的TokenType里加TK_FOR和TK_TO同时去lexer.c的关键字表里补两行{for, TK_FOR}, {to, TK_TO}。第二步parse.c加一个stmt_for()文法写成for_stmt - FOR ID ASSIGN expr TO expr DO stmt_seq END函数体照着stmt_while()的结构抄只是把条件部分换成「循环变量 上界」。第三步analyze.c里检查循环变量已声明且是整型上界表达式也是整型。真正省事的是第四步——代码生成阶段不要新增四元式指令直接降糖成已有的赋值和 while/* gen_for把 for 还原成 i : lo; while i hi do body; i : i 1 */ void gen_for(TreeNode *t) { int ivar st_lookup(t-var_name)-memloc; int lo gen_expr(t-child[0]); emit(OP_STORE, lo, 0, ivar); /* i : lo */ int loop_start nquad; int tmp new_temp(); emit(OP_LOAD, ivar, 0, tmp); /* 取 i */ int hi gen_expr(t-child[1]); /* 上界每轮重算语义上等价 */ int cmp new_temp(); emit(OP_LE, tmp, hi, cmp); int jf emit_jump(OP_JF); gen_stmt(t-child[2]); /* 循环体 */ emit(OP_ADD, ivar, 1, ivar); /* i : i 1 */ emit(OP_JMP, loop_start, 0, 0); backpatch(jf, nquad); }这么写的收益是虚拟机一行都不用改风险全压在语法和语义两层出问题好定位。想再加数组思路类似Type里加TyArray(base, size)符号表条目多存一个size字段和一段连续memloc代码生成时新增一条OP_INDEX四元式算地址虚拟机里补一个case。验证方法永远是老三样——先打印语法树看结构对不对再 dump 四元式看跳转和下标有没有算错最后才跑用例比结果。血泪经验是每加一个语法特性先把「错误写法」的用例准备好比如for的上界写成字符常量、循环变量没声明、循环体里给循环变量重新赋值。这些用例在新功能刚写完时跑一遍能立刻暴露符号表和行为约定的漏洞比等一周后别人拿去用再报错强得多。从那以后我每次动语法都强制走一遍「语法树 → 四元式 → 正确/错误用例」这三关没有例外。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/11/6 5:41:03 · 阅读 1.2k SNL语言编译器源码实战：词法分析、递归下降与四元式
简介面向编译原理课程学习、课程设计与小型编译器实践者这份 SNL 语言编译器源码包给出从词法分析、语法递归与 LL(1) 分析到语义处理、主程序调用的完整实现线索可用于对照课堂理论理解编译前端各阶段的衔接方式也适合作为课程实验的参考底稿。压缩包为 zip 格式共 231 个文件、约 77.55MB主体包含 C/C 源码与少量头文件并配有 sln、vcxproj 等 Visual Studio 工程配置以及 exe 可执行文件、obj/pdb/ipch/tlog 等编译调试中间文件和日志便于直接查看工程结构、复现构建过程与排查运行问题。目前已有 1179 人学习。读者可据此梳理 SNL 语言从源程序输入到语义检查的模块划分参考词法分析、语法分析与语义程序的实现思路并结合可执行文件快速验证多套工程与调试产物也方便对比不同实现版本和定位常见错误。1. SNL语言编译器源码一份能把编译原理从期末考卷拽回终端的代码课设答辩前一晚最怕的不是程序跑不出结果而是被追问一句「你这个语法分析器为什么这么写」。这份 SNL语言编译器源码的价值就在这里SNLSimple Nested Language是一门教学用的嵌套语言而这份 C/C 源码把它从字符流一路干到可执行结果——词法扫描、递归下降语法分析、符号表与类型检查、四元式中间代码生成最后接一个栈式虚拟机解释执行。它适合两类人一是编译原理课设需要交完整前端、又不想只交一堆看不懂的生成式解析器骨架的人二是工作几年后想把「编译器前端到底怎么落地」补上的人。整份代码规模不大但分层清楚改起来不心虚。2. 工程结构拆解五个模块的边界在哪里2.1 一份典型的源码目录长什么样这类课程级编译器源码通常不是一个大文件硬写完的而是按编译阶段切成若干编译单元每个单元配一个头文件对外暴露少量接口。我第一次拿到这份代码时先扫了一遍目录看到模块划分心里就有底了——它不是那种「所有函数都塞在 main.c 里」的作业。文件职责改动频率globals.h跨模块共享的 Token、语法树节点、四元式、错误码定义高加语法就要动util.c/h内存分配、字符串池、打印缩进、错误输出低lexer.c/h字符流到 Token 序列的扫描器维护行号低加关键字才动parse.c/h递归下降语法分析产出语法树高symtab.c/h哈希桶符号表作用域链的压入与弹出中analyze.c/h遍历语法树做类型检查、符号解析高code.c/h四元式生成、跳转回填中main.c命令行入口串起整条流水线低test/*.snl示例源程序随便加拆成这个粒度最大的好处是当你只想验证「while 语句的四元式对不对」时只需要在parse.c和code.c之间来回看不必翻遍全文。代价是结构体定义必须集中否则symtab.c想用一个TreeNode就得反向包含parse.h很容易搞出循环依赖。2.2 层与层之间的约定三个核心数据结构编译器的模块化不是靠注释喊出来的是靠数据结构固定下来的。上层往下层传什么、下层往上返回什么全靠这几个结构体约束。/* globals.h —— 各模块共享的数据结构改这里等于改契约 */ typedef enum { TK_NUM, TK_ID, TK_CHAR, /* 字面量与标识符 */ TK_IF, TK_THEN, TK_ELSE, TK_END, /* 关键字加语句先加这里 */ TK_WHILE, TK_DO, TK_VAR, TK_PROC, TK_ASSIGN, TK_EQ, TK_LT, TK_PLUS, TK_MINUS, TK_LPAREN, TK_RPAREN, TK_SEMI, TK_EOF, TK_ERR } TokenType; typedef struct { TokenType type; /* 供 switch 分派决定语法分支 */ char lexeme[64];/* 原始拼写报错时直接打印给人看 */ int line; /* 行号错误定位的关键依据 */ union { int ival; char cval; } val; /* 字面量的真实值 */ } Token; typedef struct TreeNode { enum { StmtK, ExpK } nodekind; enum { IfK, WhileK, AssignK, ReadK, WriteK, CompoundK } stmt; enum { OpK, ConstK, IdK } exp; TokenType attr_op; /* 运算符 */ int attr_val; /* 常量值 */ char attr_name[32]; /* 标识符名 */ struct TreeNode *child[3]; /* 定长子节点够用且不用管理链表 */ struct TreeNode *sibling; /* 兄弟链表串起语句序列 */ } TreeNode;Token里多留一个lexeme是我强烈建议保留的设计很多精简版为了省事只存type和一个整数值结果报错时只能说「第 17 行有语法错误」而不能说「第 17 行的whilee附近有问题」。调试期这一条信息能省半小时。TreeNode用「子节点数组 兄弟链表」是标准做法语句序列靠sibling串成链if的 then 和 else 靠child[0]、child[1]挂上去方向明确遍历时不会绕晕。四元式则更简单本质就是一个定长数组下标即指令地址/* 四元式op, arg1, arg2, result —— 跳转类指令的 result 存目标地址 */ typedef struct { OpCode op; /* ADD/SUB/ASSIGN/JMP/JLT/LABEL/... */ int arg1, arg2; /* 操作数临时变量编号或符号表下标 */ int result; /* 目标临时变量编号或跳转目标指令下标 */ } Quad;这里有个必须统一的约定arg1/arg2/result里到底存什么。常见做法是「正数表示临时变量编号负数表示符号表下标」或者干脆全部走符号表、临时变量也塞进符号表。前一种省内存、查表快后一种实现简单、dump 出来好看。两种都行但全文必须统一中途换约定基本等于重写。我一般选后者因为四元式打印出来给人检查时能直接看到变量名。2.3 构建方式Makefile 与单文件编译源码包一般会带一个Makefile把util.c、lexer.c、parse.c、symtab.c、analyze.c、code.c、main.c一起编译成可执行文件。# 最常见的构建方式 make clean make # 产物一般是 snlc / snl / compiler看 Makefile 里的 TARGET # 如果没有 Makefile手动编译也一样 gcc -stdc99 -g -Wall -o snlc *.c-g不能省。这类代码最常见的崩溃位置是符号表查找返回空指针后继续解引用没有调试符号你只能看着段错误干瞪眼。-Wall也要留着递归下降里最容易犯的「函数声明了但某个分支忘记 return」全靠它提醒。如果 Makefile 里用了-O2建议调试期先手动降到-O0否则断点跳来跳去变量还会被优化掉。注意有些源码包把main.c里的入口写成int main(int argc, char *argv[])并直接用argv[1]当文件名不检查参数个数。第一次运行如果忘了带文件名段错误会伪装成「编译器有 bug」。3. 词法与语法分析手写扫描器 递归下降的完整链路3.1 扫描器主循环最大匹配、行号与回退手写扫描器的骨架非常简单本质是一个带前瞻的循环跳过空白、看首字符决定走哪条分支、把整个词素吃干净、返回 Token。难点全在边缘情况上——关键字和标识符前缀相同if和iffy、注释跨行、行号维护。/* lexer.c —— 每调用一次返回一个 Token靠全局游标推进 */ static char *src; /* 指向当前字符 */ static int line 1; /* 行号出错时要用 */ Token next_token(void) { /* 1. 跳过空白与换行换行必须计数 */ while (*src || *src \t || *src \n || *src \r) { if (*src \n) line; src; } Token t; t.line line; t.lexeme[0] \0; /* 2. 数字连续吃数字字符最大匹配 */ if (isdigit((unsigned char)*src)) { char *p t.lexeme; while (isdigit((unsigned char)*src)) *p *src; *p \0; t.type TK_NUM; t.val.ival atoi(t.lexeme); return t; } /* 3. 标识符或关键字先按标识符吃吃完再查关键字表 */ if (isalpha((unsigned char)*src)) { char *p t.lexeme; while (isalnum((unsigned char)*src) || *src _) *p *src; *p \0; t.type lookup_keyword(t.lexeme); /* 表里没有就返回 TK_ID */ return t; } /* 4. 运算符双字符必须优先于单字符匹配 */ if (*src ) { src; t.type TK_LT; strcpy(t.lexeme, ); return t; } if (*src : *(src 1) ) { src 2; t.type TK_ASSIGN; strcpy(t.lexeme, :); return t; } if (*src \0) { t.type TK_EOF; return t; } /* 5. 兜底吃一个未知字符返回错误 Token不要死循环 */ t.type TK_ERR; t.lexeme[0] *src; t.lexeme[1] \0; return t; }逐段说清楚第一步的换行计数是整个错误定位体系的基础\r也要一起跳过否则 Windows 换行会让扫描器把回车当成未知字符报错。第二步数字识别只处理十进制整数若要支持十六进制得在这里加0x前瞻。第三步的关键是「先吃完整的标识符再查关键字表」——反过来做就会把iffy拆成if和fy这是初学者最典型的翻车点。第四步双字符运算符必须在单字符之前判断: 和:的处理顺序写反赋值语句全线崩。第五步的兜底返回错误 Token 而不是while(1)是因为扫描器一旦卡住不前进整个程序就假死你连错在哪一行都看不到。关键字表本身就是一个静态数组加线性查找static struct { const char *word; TokenType type; } keywords[] { {if, TK_IF}, {then, TK_THEN}, {else, TK_ELSE}, {end, TK_END}, {while, TK_WHILE}, {do, TK_DO}, {var, TK_VAR}, {procedure, TK_PROC}, {NULL, TK_ID} };只有十来个关键字线性查找的开销完全可以忽略不用上来就建哈希表。加新关键字只需要在这个数组里补一行别的地方一行不用动这就是把字符串和 Token 类型解耦的收益。3.2 递归下降子程序怎么写才能和 EBNF 一一对应递归下降最大的优势是「文法长什么样代码就长什么样」。比如表达式这一层EBNF 写成expr - term { (|-) term }代码里花括号对应一个while循环而不是递归调用自己——这一点非常关键用递归写左结合会产生右结合的结果1-2-3会算成1-(2-3)2而不是-4。/* parse.c —— 加减层左结合靠循环不靠递归 */ static TreeNode *expr(void) { TreeNode *t term(); /* 先拿一个项必然存在 */ while (token.type TK_PLUS || token.type TK_MINUS) { TokenType op token.type; match(op); /* 消费掉运算符 */ TreeNode *n new_node(ExpK); n-exp OpK; n-attr_op op; n-child[0] t; /* 左操作数已经算好的部分 */ n-child[1] term(); /* 右操作数递归进乘除层 */ t n; /* 结果继续当左操作数形成左倾树 */ } return t; } /* 乘除层优先级更高所以被加减层调用 */ static TreeNode *term(void) { TreeNode *t factor(); while (token.type TK_MUL || token.type TK_DIV) { TokenType op token.type; match(op); TreeNode *n new_node(ExpK); n-exp OpK; n-attr_op op; n-child[0] t; n-child[1] factor(); t n; } return t; }match()的语义是「断言当前 Token 类型符合预期符合就前进到下一个不符合就记一条语法错误」。这里有个实现细节值得抄作业match失败后不要立刻 return而是记录错误、尽量继续往下走。编译器前端如果遇到第一个错误就退出用户改一个错、重新编译、再冒一个错来回十几次体验极差。常见的补救手段是「插入式恢复」——表达式缺右括号时补一个假的右括号继续解析只要不陷入死循环多报几条错误反而更有用。语句层的子程序结构同理。stmt_sequence()循环解析语句直到遇到end或else这类结束符号statement()用switch(token.type)按首 Token 分派到stmt_if()、stmt_while()、stmt_assign()等分支。分派依据就是每个候选式的 FIRST 集写代码时对着文法表抄一遍分支顺序即可不存在玄学。3.3 语法错误的定位与信息质量错误信息质量直接决定这份代码好不好用。我见过的最低配版本只打印syntax error连行号都没有调试时只能靠二分注释源码。合格的做法是带上行号、当前 Token 的原文、以及一句人话void syntax_error(const char *msg) { fprintf(stderr, Line %d: %s (near \%s\)\n, token.line, msg, token.lexeme[0] ? token.lexeme : EOF); }token.lexeme为空时说明已经读到文件尾此时打印EOF比打印空白有用得多——很多「语法错误」的真实原因是源程序少了最后那个end报错位置在文件末尾看到EOF就知道该往哪查。再往上一步是把语法树打印出来做可视化确认。写一个print_tree(TreeNode *t, int indent)用两空格缩进递归打印几十行代码但它能让你在写语义分析之前就确认while x 10 do的条件子树挂对了位置。我一般会在main.c里加个-t开关只在需要时打印避免正常运行时刷屏。4. 语义分析与中间代码符号表、类型检查与四元式回填4.1 符号表哈希桶加作用域链SNL 支持过程和函数嵌套符号表就必然要处理作用域。最省事的实现是「一张哈希表 每个条目记录所属作用域层级 查找时取层级最深的那条」更清晰的做法是「每个作用域一张表用parent指针串成链退出作用域时整张表丢弃」。/* symtab.c —— 经典哈希桶 作用域链 */ #define BUCKET_SIZE 211 /* 常用小质数冲突率够低 */ typedef struct Bucket { char name[32]; SymbolKind kind; /* VarK / ProcK / FunK / ConstK */ Type type; /* Int / Char / Bool / Array(...) */ int memloc; /* 运行时的栈偏移代码生成时用 */ int scope_level; /* 层级越大越内层 */ struct Bucket *next; /* 同桶链表 */ } Bucket; static Bucket *table[BUCKET_SIZE]; static int current_level 0; /* 进入过程 1退出 -1 */ static unsigned hash(const char *key) { unsigned h 0; while (*key) h h * 31 (unsigned char)*key; return h % BUCKET_SIZE; } Bucket *st_lookup(const char *name) { Bucket *best NULL; for (Bucket *p table[hash(name)]; p; p p-next) { if (strcmp(p-name, name) 0 p-scope_level current_level) { if (!best || p-scope_level best-scope_level) best p; /* 取可见范围内层级最深的那个实现内层遮蔽 */ } } return best; }st_lookup里那句「取层级最深的」是内层变量遮蔽外层同名变量的核心。如果偷懒直接返回链表中第一个匹配项就会出现「内层定义了同名变量但读写的还是外层那个」的诡异现象而且这种 bug 不会报错只会算错数——属于最难受的一类问题。插入时则要防重定义但只防同层重定义var x : integer;在一个过程里写两遍应该报错外层和内层各写一个x是合法的。所以st_insert里遍历同桶时判断条件是strcmp 相等 scope_level current_level一个写错就变成「所有嵌套都用不了同名变量」。memloc字段提前给变量分配栈偏移是语义分析和代码生成之间的桥梁。常见做法是从当前作用域的基址往上递增过程调用时靠这个偏移在运行栈上定位实参和局部变量。4.2 类型检查放在哪一遍做有三种常见组织方式一是完全融进语法分析边解析边检查类似一遍式编译器二是语法树建好之后单独跑一遍analyze.c三是再拆成「符号解析」和「类型检查」两遍。这份源码走的是第二种也就是main.c里清晰的流水线/* main.c —— 五个阶段顺序不能换 */ Token t; TreeNode *tree; while ((t next_token()).type ! TK_EOF) { /* 通常由 parse 内部驱动 */ } tree parse(); /* 1. 语法树 */ if (Error) { print_errors(); return 1; } build_symtab(tree); /* 2. 建符号表先声明后使用 */ type_check(tree); /* 3. 类型检查 */ code_gen(tree); /* 4. 生成四元式 */ vm_run(); /* 5. 解释执行 */分开的好处是类型检查报错时语法树已经完整可以继续检查下一棵子树一次报出所有类型错误而不是解析到一半就中断。代价是要在树节点上多存一些信息比如「这个IdK节点解析后绑定到了符号表哪个条目」通常加一个Bucket *sym指针避免后面反复查表。类型检查本身的规则不复杂就是几条/* analyze.c —— 赋值语句的类型规则其余类似 */ static void check_assign(TreeNode *t) { Bucket *lhs st_lookup(t-child[0]-attr_name); if (lhs NULL) { sem_error(t-line, undeclared variable %s, t-child[0]-attr_name); return; } Type rt check_expr(t-child[1]); if (rt ! lhs-type) sem_error(t-line, type mismatch in assignment to %s, t-child[0]-attr_name); }关键是所有分支都要return且不能因为一次错误就中断整体遍历。很多版本在这里用exit(1)直接退出导致用户一次只能看到一个错体验和只报syntax error一样糟。4.3 四元式生成与跳转回填表达式生成四元式是自底向上的先递归生成子表达式的四元式结果放在某个临时变量里然后把临时变量编号填进当前指令的arg。/* code.c —— 表达式生成返回存放结果的临时变量编号 */ int gen_expr(TreeNode *t) { if (t-exp ConstK) { int tmp new_temp(); emit(OP_LOADI, t-attr_val, 0, tmp); /* 常量装入临时变量 */ return tmp; } if (t-exp IdK) { Bucket *b st_lookup(t-attr_name); int tmp new_temp(); emit(OP_LOAD, b-memloc, 0, tmp); /* 从栈槽读到临时变量 */ return tmp; } /* 运算符先算子节点再算自己 */ int a gen_expr(t-child[0]); int b gen_expr(t-child[1]); int r new_temp(); emit(op_of(t-attr_op), a, b, r); return r; }控制流才是真正需要技巧的地方。if和while在生成时还不知道跳转目标的具体位置——条件分支的目标是「then 之后」循环回跳的目标是「条件开头」。标准解法是回填先emit一条目标地址待定的跳转记住它的指令下标等目标位置确定后再把下标填回去。/* 回填先发一条空目标指令占位后补 */ int emit_jump(OpCode op) { return emit(op, 0, 0, -1); /* result -1 表示待回填 */ } void backpatch(int quad_index, int target) { quads[quad_index].result target; /* target 是四元式数组下标 */ } /* while 语句的生成顺序环环相扣 */ void gen_while(TreeNode *t) { int loop_start nquad; /* 条件表达式的起始位置 */ int cond gen_expr(t-child[0]); int jf emit_jump(OP_JF); /* 条件为假就跳出循环 */ gen_stmt(t-child[1]); /* 循环体 */ emit(OP_JMP, loop_start, 0, 0); /* 回跳到条件开头 */ backpatch(jf, nquad); /* 假出口 循环体之后 */ }backpatch(jf, nquad)这一句nquad在回填那一刻正好等于「循环体之后第一条指令」的下标。这个写法是整个代码生成里最容易写错的地方如果把backpatch挪到gen_stmt前面假出口就会指进循环体内部如果把loop_start记在gen_expr之后回跳会跳过条件判断变成死循环。这类错误不会在编译期暴露只能靠跑用例。临时变量计数new_temp()必须全局唯一跨语句、跨过程都不能重号。有些版本在每个函数开头把计数器清零看起来「每个函数有自己的临时变量区」很合理实际上会导致不同过程的临时变量占用同一个栈槽递归调用时直接互相覆盖。5. 跑通与排查从 make 到四元式输出的 5 个常见坑5.1 构建、运行与验证一条龙先确认能编译通过再拿示例程序跑通最后才是改代码。顺序反了容易把「环境问题」误判成「代码 bug」。# 1. 编译保留调试符号打开全部警告 make clean make CFLAGS-stdc99 -g -O0 -Wall # 2. 跑一个示例程序看整体输出 ./snlc test/while_sum.snl # 3. 只想看中间代码时走 -q 开关如果源码带了 ./snlc -q test/while_sum.snl配套的验证程序建议自己写一个语法以源码里的parse.c为准别照抄别的教材program sum_demo var i, sum : integer; begin sum : 0; i : 1; while i 11 do sum : sum i; i : i 1 end; write(sum) end期望的输出分两段四元式列表里应该能看到一个LABEL或循环条件起点、一条JLT/JF条件跳转、循环体三条赋值、一条回跳JMP程序运行结果是55。如果四元式看着合理但结果不对问题在虚拟机如果四元式本身就错了问题在代码生成阶段。用这个二分法定位比漫无目的地读代码快得多。5.2 五个真实踩过的坑坑一源文件看着没错扫描器却报未知字符。现象是在第 1 行就报unexpected character打开文件看第一行是program开头的正常内容。原因通常是文件带了 CRLF 换行或者被编辑器存成了带 BOM 的 UTF-8扫描器读到\r或\xEF就直接当非法字符。解决方式是在扫描器跳过空白的循环里加上*src \r并在文件头显式跳过 BOM 三字节实在懒得改代码用dos2unix转一遍也行。坑二while 循环永远只执行一次。现象是sum最终等于1而不是55。原因是backpatch把跳出目标填成了循环体的第一条指令下标而不是循环体之后的下标导致第一次循环结束时并没有真正跳出反而跳回体内某处然后一路走到结束。排查方法是在gen_while里临时打印jf和nquad两个数对照四元式 dump 看跳转目标落在哪条指令上一眼就能看出来。坑三语义分析阶段段错误。现象是程序在type_check里崩溃gdb 栈顶停在lhs-type那一行。原因是st_lookup返回了NULL变量未声明而代码没有判空就直接解引用。这类崩溃在「故意写一个错误程序测试报错功能」时才暴露正常用例跑不出来。解决办法是在所有st_lookup调用点强制判空并且养成习惯查表函数的返回值默认可能为 NULL先判再用。坑四递归过程调用结果错乱。现象是单个过程调用没问题一旦递归比如求阶乘结果就离谱。原因是临时变量编号在每个过程内部从 0 重新计数不同过程的临时变量映射到了同一个栈槽递归展开时相互覆盖。解决办法是把临时变量计数器做成全局的或者按过程名加前缀区段分配让每个过程的临时变量区间不重叠。坑五嵌套过程里读到了外层的同名变量。现象是内层过程声明了var x但赋值后外层看到的还是旧值。原因就是前面提到的st_lookup只返回链表中第一个匹配项没有按scope_level取最深的一层。排查方法是写一个三行的小程序外层x : 1进入内层再x : 2内层write(x)退出后再write(x)。正常应该输出2和1如果两次都是2或者都是1问题就锁死在符号表查找上。提示这五个坑里有三个的根因都是「没有判空」和「作用域没取最深」改代码之前先把这两处收紧能省掉一大半调试时间。6. 二次开发给 SNL 加一条 for 语句的完整改法拿到这份源码后最想做的事多半是「加个新语法」。for语句是最合适的练手目标因为它能一次性串起词法、语法、语义、代码生成四个阶段改完你就彻底摸清这条流水线了。第一步globals.h的TokenType里加TK_FOR和TK_TO同时去lexer.c的关键字表里补两行{for, TK_FOR}, {to, TK_TO}。第二步parse.c加一个stmt_for()文法写成for_stmt - FOR ID ASSIGN expr TO expr DO stmt_seq END函数体照着stmt_while()的结构抄只是把条件部分换成「循环变量 上界」。第三步analyze.c里检查循环变量已声明且是整型上界表达式也是整型。真正省事的是第四步——代码生成阶段不要新增四元式指令直接降糖成已有的赋值和 while/* gen_for把 for 还原成 i : lo; while i hi do body; i : i 1 */ void gen_for(TreeNode *t) { int ivar st_lookup(t-var_name)-memloc; int lo gen_expr(t-child[0]); emit(OP_STORE, lo, 0, ivar); /* i : lo */ int loop_start nquad; int tmp new_temp(); emit(OP_LOAD, ivar, 0, tmp); /* 取 i */ int hi gen_expr(t-child[1]); /* 上界每轮重算语义上等价 */ int cmp new_temp(); emit(OP_LE, tmp, hi, cmp); int jf emit_jump(OP_JF); gen_stmt(t-child[2]); /* 循环体 */ emit(OP_ADD, ivar, 1, ivar); /* i : i 1 */ emit(OP_JMP, loop_start, 0, 0); backpatch(jf, nquad); }这么写的收益是虚拟机一行都不用改风险全压在语法和语义两层出问题好定位。想再加数组思路类似Type里加TyArray(base, size)符号表条目多存一个size字段和一段连续memloc代码生成时新增一条OP_INDEX四元式算地址虚拟机里补一个case。验证方法永远是老三样——先打印语法树看结构对不对再 dump 四元式看跳转和下标有没有算错最后才跑用例比结果。血泪经验是每加一个语法特性先把「错误写法」的用例准备好比如for的上界写成字符常量、循环变量没声明、循环体里给循环变量重新赋值。这些用例在新功能刚写完时跑一遍能立刻暴露符号表和行为约定的漏洞比等一周后别人拿去用再报错强得多。从那以后我每次动语法都强制走一遍「语法树 → 四元式 → 正确/错误用例」这三关没有例外。希望帮到你。本文还有配套的精品资源点击获取