编译原理实验全链路源码：从词法分析到四元式生成

简介一套面向编译原理课程学习与实验复现的代码包对应中国海洋大学OUC2020年春季学期编译原理课程的8个实验适合高校学生、自学者及需要梳理编译器构造流程的开发者使用。内容从词法分析、语法分析、语义分析延伸到中间代码生成、代码优化、目标代码生成、错误处理与编译器综合集成并配有实验要求文档便于对照目标、预期输出和评估标准逐项实践。压缩包共74个文件以18个C源码、8个.l词法规则、8个.y语法规则、8个C头文件及Makefile构建脚本为主辅以txt说明和可执行样例整体约774KB目录按实验划分清晰。已有4419人学习读者可据此搭建Flex/Bison等工具环境复现完整编译流程理解符号表、语法树、三地址码与优化策略并积累组件调试和排错经验。1. 编译原理实验的五个“断点”这套源码连线编译原理实验最反常识的一点是课表上排在后面的语法分析往往比前面的词法分析先跑通。原因很简单词法分析这一步需要手写扫描器但很多教材没有完整示例。这套某高校编译原理课程的全套实验源码覆盖的就是从词法分析、语法分析、语义处理到四元式中间代码生成的完整链路。它最大的价值在于每个阶段都能单独编译、单独喂输入、单独看输出你不需要先跑通整条链路才能验证某一步做对了没有。适合两类人一类是实验周还没动手、想找一份能逐行对照的参考实现的人另一类是实验早就交了、但心里对“递归下降到底怎么把四元式吐出来”一直是黑匣子的人。源码按实验编号分目录C 和 Python 两种写法都有可以在命令行下直接 make。2. 目录结构与数据契约五个实验其实是同一条流水线的五个断点先看骨架。这套源码的组织方式不像教科书那样按“第几章”分而是按编译阶段分目录每个目录都是一个能独立make ./run的工程。这么分的好处是调试时可以用二分法定位如果四元式生成结果不对就先看语法分析输出的树对不对再看词法输出的 token 流对不对一层层往回倒。2.1 目录长什么样每个实验一个独立可编译单元剥掉构建产物之后主干大概是这样compile-lab/ ├── 01-lexer/ │ ├── src/lexer.c # 手写扫描器逐字符推进 │ ├── src/dfa.c # 正则 - NFA - DFA 的子集构造 │ ├── src/main.c # 读源文件按行打印 token 流 │ ├── tests/ok1.c # 正常样例关键字、运算、注释 │ ├── tests/bad1.c # 错误样例非法字符、未闭合注释 │ └── Makefile ├── 02-parser-rd/ # 递归下降一个非终结符一个函数 ├── 03-parser-ll1/ # 表驱动FIRST/FOLLOW 自动算 ├── 04-parser-lr/ # 项目集规范族 SLR(1) 分析表 ├── 05-semantic/ # 符号表、作用域、类型检查 ├── 06-quad/ # 四元式生成与回填 └── common/ ├── token.h # 五个实验共用的 Token 定义 ├── ast.h # 语法树节点 └── symtab.h # 符号表common/是这套源码里最容易被忽略、但最值得先读的目录。它定义了各阶段之间传递的数据结构也决定了你后面改代码时要改动哪些地方。很多同学做实验时每个实验单独写一套结构体词法那边叫Token语法那边叫Lexeme到语义分析又要写一层转换。五个实验做完手上五套不兼容的数据格式。这套源码强迫自己先定common/token.h后面所有阶段都只认这一份。需要说明的是目录里的03-parser-ll1和04-parser-lr是两条并列路线不是先后依赖。LL(1) 适合验证你对预测分析表的理解LR 适合验证你对项目集闭包的理解两者都吃01-lexer输出的 token 流。你完全可以在 03 里把表打印出来对一遍答案然后跳到 05 继续不碰 04。2.2 阶段之间的数据契约Token、AST、符号表、四元式流水线上真正需要约定的只有四样东西把这四样的接口固定下来各阶段就能像插头一样对接。这套源码的约定如下阶段输入输出主要数据结构01 词法分析源文件字符流Token 序列Token{kind, lexeme, line, col, val}02/03/04 语法分析Token 序列语法树 / 归约序列Node{type, child[], attr}05 语义分析语法树带类型的语法树 符号表SymTab哈希桶 作用域链06 中间代码带类型语法树四元式数组Quad{op, a1, a2, result}这张表里最关键的是最后一列的line和col。很多人写词法分析时不记位置等到语法分析报“第 ? 行语法错误”时才发现自己没法定位只能翻源码数行号。血泪经验line字段在写词法分析的第一步就要加成本几乎为零不加的话后面每一个阶段都要为它补课。另一个契约点是Node的attr字段。语法树节点既要承载结构信息这是 if那是 while又要承载语义信息这个表达式的类型是 int这个标识符在符号表里的槽位是 3。这套源码的做法是attr用一个联合体语法分析阶段只填结构部分语义分析阶段往上挂类型和符号表指针。这样一份树从头用到尾不用中途复制一遍。提示如果你打算把实验改成能处理真实语言子集的迷你编译器先把这张表抄下来后面加特性时对着表判断“这次改动落在哪一格”比在脑子里维护一张隐形的地图靠谱。2.3 语言与构建方式选型C 单文件还是 Python 脚本源码里 01、02、05 是 C03、04、06 是 Python。这个分布看起来随意其实对应两类不同的实验目标。C 版本适合那些你要“看清内存里到底发生了什么”的部分。词法分析器的状态机、语法树的指针结构、符号表的哈希冲突链用 C 写出来是裸露的gdb一挂就能看到每个节点。Makefile 也很朴素# 01-lexer/Makefile —— 只依赖 common 下的头文件 CC gcc CFLAGS -stdc11 -Wall -Wextra -g -I../common TARGET lexer OBJS src/main.o src/lexer.o src/dfa.o $(TARGET): $(OBJS) $(CC) $(CFLAGS) -o $ $^ %.o: %.c $(CC) $(CFLAGS) -c -o $ $ clean: rm -f $(OBJS) $(TARGET) # 跑法./lexer ../tests/ok1.c-g是必须的因为你会不止一次想在next_token里下断点。-Wall -Wextra也留着语法分析里少写一个return导致的未定义行为靠眼睛是看不出来的。Python 版本适合表驱动的部分。LL(1) 的预测分析表、LR 的项目集规范族本质上是集合运算用 Python 的set和frozenset表达闭包和转移代码量能压到 C 的三分之一而且中间结果可以直接print出来对照手算。这部分如果用 C 写光是实现一个集合类型就要花掉半天实验的重点反而被稀释了。我一般会建议先用 Python 把表的构造跑通、把中间结果打印出来和手算结果对一遍确认算法无误之后如果课程要求 C 实现再照着 Python 版的逻辑翻译。反过来先写 C 再对答案会痛苦很多因为你在调试的是“算法错了”还是“指针写错了”这两件事混在一起分不开。3. 词法分析器拆解手写扫描循环与 DFA 状态机怎么选词法分析这块源码里给了两条实现路线src/lexer.c是手写的逐字符扫描器src/dfa.c是把正则表达式编译成 DFA 之后的表驱动版本。两条路线不是替代关系而是“先会手写再看懂自动生成”的递进。3.1 Token 结构与关键字表先定 token。这套源码把单字符运算符直接用它自己的 ASCII 码当kind双字符运算符和关键字从 256 开始排这样kind一个 int 就能同时表达两类信息判断时也不用额外查表/* common/token.h —— 五个实验共用的词法单元 */ typedef enum { TK_ID 256, TK_NUM, TK_FLOAT, /* 标识符与常量 */ TK_IF, TK_ELSE, TK_WHILE, TK_INT, TK_RETURN, /* 关键字 */ TK_EQ, TK_NE, TK_LE, TK_GE, TK_ASSIGN, /* 双字符运算符 */ TK_EOF, TK_ERR } TokenKind; typedef struct { TokenKind kind; char lexeme[64]; /* 原始串报错和建符号表都要用 */ int line; /* 从 1 开始 */ int col; /* 从 1 开始 */ union { long ival; double fval; } val; /* 常量折叠时直接用 */ } Token;关键字识别的常见做法是先用标识符规则扫出整串再拿这串去查表而不是在扫描循环里逐个字符判断“是不是 if”。查表用一个以 NULL 结尾的静态数组就够了关键字数量通常不超过二十个线性查找比哈希快/* src/lexer.c —— 关键字表扫完标识符后回头查一次 */ static const struct { const char *word; TokenKind kind; } keywords[] { {if, TK_IF}, {else, TK_ELSE}, {while, TK_WHILE}, {int, TK_INT}, {return, TK_RETURN}, {NULL, 0} }; static TokenKind lookup_keyword(const char *s) { for (int i 0; keywords[i].word; i) if (strcmp(keywords[i].word, s) 0) return keywords[i].kind; return TK_ID; /* 没命中就是普通标识符 */ }这个设计的直接好处是以后要加for、break、continue只需要在数组里加一行扫描循环一个字都不用动。反过来如果你的词法分析器里写满了if (c i peek() f)这种判断加关键字就要动核心逻辑翻车概率直线上升。3.2 主扫描循环逐段拆整个扫描器的心脏是next_token它每次调用吃掉一个完整的词法单元跳过空白和注释。调用方语法分析器只关心“给我下一个 token”不关心内部是怎么推进的/* src/lexer.c —— 主扫描循环一次吃一个 token */ Token next_token(Lexer *lx) { skip_blank_and_comment(lx); /* 空格、换行、// 与 多行注释都在这里消化 */ Token tk {0}; tk.line lx-line; tk.col lx-col; if (lx-cur EOF) { tk.kind TK_EOF; return tk; } /* 数字与标识符各有专属扫描函数避免主循环膨胀 */ if (isdigit(lx-cur)) return scan_number(lx); if (isalpha(lx-cur) || lx-cur _) return scan_ident(lx); /* 双字符运算符必须先看顺序反了会把 拆成两个 */ char c lx-cur; if (c peek(lx) ) { advance(lx); advance(lx); tk.kind TK_EQ; strcpy(tk.lexeme, ); return tk; } if (c ! peek(lx) ) { advance(lx); advance(lx); tk.kind TK_NE; strcpy(tk.lexeme, !); return tk; } if (c peek(lx) ) { advance(lx); advance(lx); tk.kind TK_LE; strcpy(tk.lexeme, ); return tk; } if (c peek(lx) ) { advance(lx); advance(lx); tk.kind TK_GE; strcpy(tk.lexeme, ); return tk; } /* 剩下的单字符运算符和界符直接用自己的 ASCII 当 kind */ advance(lx); tk.kind (TokenKind)c; tk.lexeme[0] c; tk.lexeme[1] \0; return tk; }这段代码有三处值得单独说。第一处是peek(lx)的存在。如果扫描器只有一个cur指针判断就得“先读一个再看下一个是不是不是的话还得退回去”。用peek提前看一眼下一个字符就不用回退状态机始终单向前进。.c文件用一个FILE*加一个int peeked缓存就能实现不复杂但省掉的回退逻辑能让整个扫描器少一半分支。第二处是双字符运算符必须在单字符之前判断。这是最容易踩的坑如果先写了“发现就返回 TK_ASSIGN”那后面的永远走不到。判断顺序不是风格问题是正确性问题。第三处是skip_blank_and_comment里对未闭合注释的处理。/*之后一直扫到 EOF 都没遇到*/正确的做法不是静默结束而是返回一个TK_ERR并带上起始行号。实验验收时老师往往就是拿一个未闭合注释的文件来试能不能报出准确的行号直接决定这一项给不给分。scan_number单独说一下它要处理整数、小数、以及可选的科学计数法后缀。判断逻辑是“先吃整数部分遇到.就转小数遇到e/E就转指数”三个状态用一个小循环加一个枚举变量就够不需要正则在前面兜底。3.3 正则到 DFA子集构造法的实验版实现src/dfa.c走的是另一条路把你写的词法规则正则表达式先转成 NFA再用子集构造法压成 DFA最后把 DFA 存成一张二维转移表扫描时纯查表。这条路线的价值不在于性能而在于让你亲手实现一遍“正则表达式是怎么变成状态机的”。NFA 用 Thompson 构造法从正则表达式搭出来得到的是一个带 ε 边的图。子集构造法的核心是两件事ε 闭包和状态集合的转移# dfa.py —— 子集构造法把 NFA 的状态集合压成 DFA 的一个状态 def epsilon_closure(states, nfa): 从 states 出发沿 ε 边走到底能到达的所有状态 stack, closure list(states), set(states) while stack: s stack.pop() for t in nfa.eps.get(s, []): # eps[s] 是 s 的 ε 后继列表 if t not in closure: closure.add(t) stack.append(t) return frozenset(closure) def subset_construction(nfa, alphabet, start): d0 epsilon_closure({start}, nfa) dfa_states, trans, work {d0}, {}, [d0] while work: cur work.pop() for ch in alphabet: move set() for s in cur: move | nfa.step(s, ch) # step(s, ch) 返回 s 在 ch 上的后继集合 if not move: # 空集不产生转移直接跳过 continue nxt epsilon_closure(move, nfa) trans[(cur, ch)] nxt if nxt not in dfa_states: # 新状态入队继续展开 dfa_states.add(nxt) work.append(nxt) return dfa_states, transepsilon_closure用的是显式栈而不是递归。原因很实际正则表达式稍微一长ε 链能深到几百层Python 默认递归深度一千一不小心就RecursionError。显式栈没有这个限制而且调试时能在循环里打断点看每一步的闭包长什么样。subset_construction里的work列表是待处理状态队列。这里有个容易写错的地方nxt not in dfa_states这个判断必须放在“记录转移”之后、“入队”之前。如果先入队再判断同一批状态会被反复展开程序不一定错但状态数会炸你会以为自己的算法写错了。跑完之后dfa_states里每个元素是一个frozenset包含着若干 NFA 状态。用frozenset而不是list是因为它可哈希能直接当字典的键写起来省事。构造出 DFA 之后还有一步是把状态集合映射成整数下标生成trans[state][ch]的二维表再对没有转移的格子填上“回退”标记。这一步在实验里通常要求你手工验算一个简单的正则比如(a|b)*abb把 DFA 的状态数和转移表打印出来和课本答案对照。这一步别偷懒跳过去因为后面 LR 分析表的构造思路是一模一样的都是“闭包 转移 不动点迭代”。3.4 错误定位与恢复报错信息决定验收体验词法阶段的错误分三类非法字符、$这种没定义的、未闭合字符串、未闭合块注释。源码里这三类都走同一条路生成一个TK_ERR的 tokenlexeme里存上出错的原始片段line/col记准位置然后跳过当前字符继续扫描而不是直接退出。“继续扫描”这个选择很重要。如果遇到第一个错误就exit(1)你一次只能看到一个错改完再跑又冒出下一个来回十几轮。跳过并继续一次运行能把文件里所有词法错误都列出来效率差好几倍。main.c里打印 token 流的格式也很值得抄它是按行对齐的/* src/main.c —— 把 token 流按行打印方便和源文件对照 */ while ((tk next_token(lx)).kind ! TK_EOF) { if (tk.kind TK_ERR) printf(%4d:%-3d ERROR %s\n, tk.line, tk.col, tk.lexeme); else printf(%4d:%-3d %-8s %s\n, tk.line, tk.col, kind_name(tk.kind), tk.lexeme); }kind_name是一个把枚举转成字符串的小函数十几行switch就行。看着不起眼但语法分析报错的时候你会希望自己没偷这个懒。4. 语法分析拆解递归下降、LL(1) 表驱动与 SLR(1)语法分析这块源码给了三份实现对应三种理解层次递归下降是“把文法直接翻译成函数”LL(1) 是“把文法翻译成一张表”SLR(1) 是“把文法翻译成状态机”。三份实现共用同一套 token 流和语法树节点所以你可以拿同一个源文件分别喂给它们比较输出的树是不是一样。4.1 递归下降一个非终结符一个函数递归下降最直观每一个非终结符对应一个函数函数体就是该非终结符所有产生式的 if/switch 分支。以if语句和语句分派为例/* src/parser.c —— 语句分派看当前 token 决定走哪个分支 */ Node *parse_stmt(Parser *p) { switch (p-cur.kind) { case TK_IF: return parse_if(p); case TK_WHILE: return parse_while(p); case {: return parse_block(p); default: return parse_expr_stmt(p); /* 表达式语句 分号 */ } } /* if :: if ( expr ) stmt [ else stmt ] */ Node *parse_if(Parser *p) { expect(p, TK_IF); expect(p, (); Node *cond parse_expr(p); expect(p, )); Node *then_br parse_stmt(p); Node *else_br NULL; if (p-cur.kind TK_ELSE) { /* else 是可选的靠 lookahead 决定 */ advance(p); else_br parse_stmt(p); } return make_node(N_IF, cond, then_br, else_br); }expect是一个辅助函数它检查当前 token 是不是期望的类型是就前进不是就报错。把“检查 前进”封装成一个动作能让每个 parse 函数只剩结构可读性提升非常明显。if的三叉节点设计也值得说一下make_node(N_IF, cond, then_br, else_br)直接把条件、真分支、假分支挂在同一个节点下而不是用“链表 标记”的方式串起来。后者在语义分析阶段要重新解析结构前者直接node-child[2]就能拿到 else 分支判空即可。语法树的结构应该和语言的语法结构一一对应别为了省内存搞成扁平列表。递归下降最大的坑是左递归。如果你照着课本写E :: E T | T然后直译成Node *parse_expr(Parser *p) { Node *left parse_expr(p); /* 无限递归栈直接爆 */ ... }第一次调用就会无限递归。正确的做法是把左递归改写成循环也就是教科书上的 EBNF 形式E :: T { T }/* 消除左递归后的写法把递归换成 while 循环 */ Node *parse_add(Parser *p) { Node *left parse_mul(p); while (p-cur.kind || p-cur.kind -) { Token op p-cur; advance(p); Node *right parse_mul(p); left make_node(N_BIN, left, right, op.kind); /* 左结合树往左长 */ } return left; }循环写法的另一个好处是天然左结合1-2-3会被解析成(1-2)-3而不是1-(2-3)和语言的语义一致。如果你用递归写法又忘了处理结合性算出来的结果在某些表达式上会静默出错这种 bug 最难查。4.2 FIRST/FOLLOW 与 LL(1) 预测分析表递归下降靠代码里的switch隐式表达了“看到这个 token 该走哪条产生式”。LL(1) 把这件事显式化算出一张表M[非终结符][终结符] 产生式编号分析时纯查表加一个栈不需要递归。建表前要先算 FIRST 和 FOLLOW。FIRST 集的算法是不动点迭代每轮扫一遍所有产生式有变化就再来一轮直到收敛# ll1.py —— FIRST 集的不动点迭代 def build_first(productions, first, nullable): changed True while changed: # 一轮没有任何变化就收敛 changed False for head, body in productions: for sym in body: add first[sym] - {ε} if not add first[head]: first[head] | add changed True if ε not in first[sym]: break # 该符号不可空后面不用看了 else: if ε not in first[head]: # 整个右部都可空head 也可空 first[head].add(ε) nullable.add(head) changed True return firstfor...else这个结构在这里用得恰到好处break表示“遇到不可空符号提前结束”else分支表示“循环跑完了都没 break说明右部所有符号都可空”。翻译成 C 的话要额外加一个标志变量Python 这里省掉了。FOLLOW 集依赖 FIRST算法也是不动点迭代对每条产生式A :: αBβ把FIRST(β)-{ε}加进FOLLOW(B)如果 β 可空再把FOLLOW(A)加进FOLLOW(B)。这里最容易漏的是“开始符号的 FOLLOW 里要放$”漏了的话分析到文件末尾会卡住报一个莫名其妙的错误。建好表之后分析器就是一个循环看栈顶符号和当前 token查表查不到就报错。源码里把表打印成了一个可读的二维矩阵方便和手算结果对照。这一步建议真的手算一个三到五条产生式的小文法然后和程序输出逐格比对。手算过的表和只看过程序输出的表理解深度差一个量级。LL(1) 的局限也要清楚它要求文法无左递归、无公共左因子而且不能有 FIRST/FIRST 或 FIRST/FOLLOW 冲突。真实语言的文法基本都不满足所以工程上很少直接用 LL(1)但它的表构造过程是理解“分析表”这个概念最好的入口。4.3 LR(0) 项目集规范族与 SLR(1) 分析表LR 分析器的核心是“项目”这个概念产生式右部加一个圆点表示“我们已经解析到哪儿了”。比如E :: E · T表示已经看到一个 E接下来期待。构造项目集规范族的第一步是求闭包如果圆点后面是个非终结符 B就把 B 的所有产生式圆点在开头都加进同一个项目集# lr.py —— 项目集闭包圆点后面是非终结符时把它展开进来 def closure(items, grammar): result set(items) changed True while changed: changed False for head, body, dot in list(result): if dot len(body) and body[dot] in grammar: # 圆点后是非终结符 for prod in grammar[body[dot]]: item (body[dot], tuple(prod), 0) # 圆点放在最前面 if item not in result: result.add(item) changed True return frozenset(result)项目用三元组(左部, 右部元组, 圆点位置)表示。用元组而不是列表是因为整个项目要放进set里做去重列表不可哈希。这个细节在 Python 里很关键用列表写会在result.add(item)那一行直接抛TypeError。有了闭包goto(I, X)的定义就很直接把 I 里所有圆点后面是 X 的项目圆点右移一位然后求闭包。从初始项目S :: ·S出发对所有符号反复求 goto就能得到完整的项目集规范族和状态转移图。这个过程的代码大概三十行但它是整个编译原理课程里最值得亲手写一遍的三十行。得到状态机之后构造 SLR(1) 分析表要做两件事对每个状态里的A :: α·圆点在末尾项目在该行的FOLLOW(A)各列填上归约动作对每个goto(I, a) Ja 是终结符在ACTION[I][a]填移进到 J对非终结符则填进 GOTO 表。冲突是这一步的常客。移进-归约冲突的典型来源是悬空 elsestmt :: if ( expr ) stmt | if ( expr ) stmt else stmt分析到if (e) stmt · else ...这个位置时既可以按第一条产生式归约也可以移进else。SLR(1) 只靠 FOLLOW 集判断解决不了要上 LR(1) 或者给文法加优先级声明。实验里遇到这个冲突不是错误报告里写清“冲突状态编号 冲突类型 一种解决方式”就够了往往还是加分项。4.4 把语义动作埋进语法分析符号表与四元式语法树建出来之后语义分析和中间代码生成通常是两次独立的树遍历。但这套源码在语法分析阶段就顺手把一部分工作做了因为有些信息只有在解析的那一刻才拿得到。四元式的生成就属于这一类。看加法表达式的处理/* src/quad.c —— 在 parse_add 的循环里就地生成四元式 */ ExprAttr parse_add(Parser *p) { ExprAttr left parse_mul(p); while (p-cur.kind || p-cur.kind -) { Token op p-cur; advance(p); ExprAttr right parse_mul(p); char *t new_temp(); /* 生成 t1、t2…… */ emit_quad(op.kind ? : -, left.place, right.place, t); /* (op, a1, a2, result) */ left.place t; /* 结果继续往上传递 */ } return left; }ExprAttr是一个很小的结构只有place这个表达式的结果现在在哪临时变量名、常量、或者变量名和type。每个 parse 函数返回它父节点拿它拼四元式。这种“边解析边生成”的写法比“先建完整棵树再遍历生成”少一次遍历也少了一层“从树节点反推操作数”的转换代码。代价是语法分析和代码生成耦合了。如果课程要求两个实验分开验收就得把emit_quad换成“往树上挂属性”再在下一阶段遍历。两种写法源码里都有#ifdef隔开改一行宏就能切换。符号表这边common/symtab.h用的是哈希桶加作用域链/* common/symtab.h —— 作用域链上的一个符号表 */ typedef struct SymTab { Bucket *buckets[211]; /* 211 是个够用的质数冲突链不会太长 */ struct SymTab *parent; /* 指向外层作用域NULL 表示全局 */ int depth; } SymTab; Symbol *lookup(SymTab *tab, const char *name) { for (SymTab *t tab; t; t t-parent) /* 由内向外逐层查找 */ for (Bucket *b t-buckets[hash(name) % 211]; b; b b-next) if (strcmp(b-sym.name, name) 0) return b-sym; return NULL; /* 一路找到全局都没有 */ }hash用最简单的 BKDR 就行重点是for (SymTab *t tab; t; t t-parent)这个外层循环先查当前作用域查不到再往外一层找这就是词法作用域的实现方式。注意不要写成“全局只有一张表进作用域时压栈、出作用域时弹栈”那种写法在遇到同名变量遮蔽时容易把外层变量一起删掉。四元式里的跳转目标还有个回填问题。布尔表达式短路求值时a b需要在a为假时跳到整个表达式之后但那时候你还没解析到后面目标地址根本不知道/* 先占位把四元式下标当句柄返回等目标确定了再回填 */ int emit_jump_if_false(const char *cond) { int idx next_quad_index(); emit_quad(jf, cond, _, _); /* 目标先填空 */ return idx; /* 句柄 */ } void backpatch(int idx, int target) { quads[idx].result strdup(itoa(target)); /* 目标确定填回去 */ }这套源码的做法是维护若干“待回填列表”truelist存所有“条件为真时该跳到某处”的四元式下标falselist存相反的。解析到时把左边的truelist回填到右边代码的起始位置解析到语句结束时把整个表达式的falselist回填到语句之后。回填是编译原理实验里少数几个“想不到就写不出来、想到了十行搞定”的机制建议单独拿张纸画一下列表的合并和回填时机。5. 避坑与排查跑不通实验时先看这五处实验代码跑不起来九成的问题集中在这几个地方。下面每一条都按“现象 → 原因 → 解决”写遇到问题时按顺序对一遍比漫无目的地单步调试快得多。5.1 词法分析器卡死或者输出的 token 数远超预期现象./lexer tests/ok1.c跑了几秒没结束CtrlC之后发现输出了几十万行一模一样的 token。原因next_token在某条分支上返回了 token但没有推进读指针cur。最常见的是“认不出的字符”这条兜底分支代码里写了tk.kind TK_ERR; return tk;却没写advance(lx)。调用方拿到错误 token 继续要下一个扫描器原地踏步主循环永不结束。解决在next_token的每个返回路径上都确认一次“指针是否前进”。更稳妥的做法是把推进动作前移凡是进入主循环体先无条件advance一次再根据刚吃掉的字符决定后续。这样结构上就不可能出现“返回了但没推进”的情况。另外给主循环加一个“连续错误超过 100 次就中止”的保护调试期能省很多时间。5.2 递归下降一跑就段错误栈溢出现象程序启动后立刻崩溃gdb的 backtrace 里parse_expr出现几千层。原因文法里有直接左递归或者间接左递归直译成递归函数之后无限调用自己。间接左递归更隐蔽比如A :: B x | ...、B :: A y | ...两个函数互相调用看代码时不容易发现。解决先用一个小脚本或者手工把文法里的左递归全部消掉再写函数。检验方法是给每个 parse 函数加一个静态计数器进入时加一、退出时减一跑一个正常样例如果某个计数器超过一百基本可以确定是左递归。另外表达式这类“可以无限长”的结构即使消了左递归也要用循环而不是递归来处理同一优先级的运算符链111...写上一千项照样能压爆栈。5.3 FIRST/FOLLOW 算出来是空集或者迭代不收敛现象build_first打印出来的表全是空集或者程序卡在while changed里转了几十秒。原因初始化的时候漏了终结符的 FIRST 集。不动点迭代的起点必须包含“每个终结符 a 的 FIRST(a) {a}”少了这个所有推导都起不来迭代永远没有输入自然收敛到一个全空的结果。不收敛则多半是集合更新时写成了first[head] add而不是first[head] | add把之前累积的结果覆盖掉了。解决初始化阶段显式把终结符填进去first {t: {t} for t in terminals} # 终结符的 FIRST 是自己 first.update({n: set() for n in nonterms}) # 非终结符从空集开始再加一个“迭代轮数超过 100 就抛异常”的保护能快速把“不收敛”和“收敛很慢”区分开。正常的文法则几轮就收敛了超过十几轮的八成是文法本身有问题比如存在A :: A这种无用产生式。5.4 LR 分析表里出现大量冲突且集中在同一个状态现象构造出的 SLR(1) 表里ACTION表的某一格同时有移进和归约程序拒绝继续。原因不一定是算法错了。SLR(1) 用 FOLLOW 集来决定归约动作这个近似比较粗所以它天然处理不了悬空 else 和某些表达式文法。真正算错的情况通常有两种一是goto函数里对非终结符的转移漏了二是项目集去重时用的键包含了圆点位置的冗余信息导致同一个项目被当成两个。解决先把冲突状态里的所有项目打印出来人工判断一下是不是真的歧义。如果是悬空 else 这类经典问题在实验报告里写明冲突原因和一种解决方案给 else 更高的移进优先级、或者改用 LR(1)比硬改成“无冲突”更有说服力。如果打印出来的项目本身就不对回头检查closure里的展开条件body[dot] in grammar这里grammar必须是“非终结符 - 产生式列表”的字典写成“产生式 - 编号”就会永远展开不出东西。5.5 四元式顺序对但算出来的结果差一现象跑a b c * d四元式列表看着没问题临时变量的编号也对但把四元式解释执行一遍结果和预期对不上。原因临时变量命名冲突。如果临时变量的编号在每次进入表达式解析时都从t1重新开始那嵌套表达式里外层和内层的临时变量就会撞名后写的覆盖先写的。另一个原因是常量折叠时把整型字面量当成字符串处理2 3变成了23而不是5。解决临时变量计数器必须是全局单调递增的不能在任何函数入口重置。另外emit_quad之前统一做一次“操作数解析”如果a1或a2是常量字面量先把它们转成数值存进val字段四元式里的place仍然记原始串但计算时用val。这样既保留了可读性又不会出现字符串拼接那种低级错误。顺带提一个排查技巧写一个几十行的四元式解释器 - * / 赋值 跳转支持这四五种操作就够把四元式数组喂进去直接算出结果。有这个工具之后中间代码对不对不用靠眼睛看跑一遍就知道调试效率提升非常明显。6. 二次开发把六个实验拼成一个能跑通源程序的迷你编译器六个实验单独跑通只说明每一段都写对了把六个拼起来才是真正的验收。我的习惯是写一个driver.py读源文件 → 词法 → 语法 → 语义 → 四元式 → 目标代码 → 交给一个极简栈式虚拟机执行中间每一步的产物都可以通过--dumplex|ast|quad单独打印。这样任何一步出问题都能立刻定位到是哪个阶段的输出不对。目标代码生成这一步实验里通常不要求但加上之后整条链就闭环了。四元式到栈式指令的映射非常规整核心就二十行# codegen.py —— 四元式到栈式虚拟机指令 OPMAP {: ADD, -: SUB, *: MUL, /: DIV} LABEL, CODE [L%d % i for i in range(4)], [] # 简化演示标签复用 def gen(quads): for op, a1, a2, res in quads: if op in OPMAP: CODE.append(fLOAD {a1}) # 左操作数入栈 CODE.append(fLOAD {a2}) # 右操作数入栈 CODE.append(OPMAP[op]) # 弹两个压一个 CODE.append(fSTORE {res}) elif op jf: # 条件为假时跳转 CODE.append(fLOAD {a1}) CODE.append(fJZ {a2}) elif op j: CODE.append(fJMP {a1}) return CODELOAD/STORE用变量名而不是寄存器编号虚拟机内部用一个字典当内存几千行代码的性能完全够用。真要往寄存器分配方向扩展把字典换成活跃变量分析加线性扫描寄存器分配那就是另一个实验的量级了。加语法特性时建议按“一条产生式、一个语义动作、一个测试用例”的节奏来别一次改五个特性再一起调试。我一般会按下面这个顺序加每一步都能独立验证特性改动位置验证方式for循环词法加关键字、语法加产生式、语义糖化成 while打印四元式确认和手写 while 版本一致一维数组符号表加维度信息、四元式加[]取址跑一段数组求和比对结果函数调用符号表加参数表、四元式加call/ret递归求阶乘验证栈帧短路求值回填逻辑扩展到 验证方法上别只测“正确的程序能跑通”。我每次改完都会准备两组用例一组是应该编译通过的比对虚拟机执行结果和手算结果另一组是应该报错的检查错误行号和错误类型对不对。后者更有价值因为它逼你在每个阶段都维护好位置信息而这些位置信息一旦某个阶段丢了错误就会在后面的阶段以一脸茫然的方式冒出来。从那以后我每次动语法分析之前都强制先跑一遍错误用例集确认报错信息没退化再开始加新特性。编译器的错误处理比正确路径更容易在重构中悄悄坏掉而它坏掉的时候往往没有任何测试会失败。希望帮到你。本文还有配套的精品资源点击获取