简介面向高校编译原理课程学习者与任课教师这份实验代码合集对应中国海洋大学2020年春季学期课程覆盖从词法分析到编译器综合的八个实验及配套要求文档帮助读者把文法、自动机与代码生成知识落到可运行程序。压缩包共74个文件、约774KB以18个C源文件为核心配合8个Lex规则、8个Yacc规则、8个头文件、7个文本说明及Makefile等构建脚本另含实验要求doc与测试数据目录按实验阶段组织。已有4419人学习适合课程实验复现与编译器构造入门。读者可依次练习记号识别、递归下降与LL(1)/LR解析、符号表与类型检查、中间代码生成、常量折叠与死代码消除、目标代码生成及错误诊断并在综合实验中串起完整编译流程也可参考Flex/Bison工具链的写法理解各阶段的输入输出衔接与调试思路。1. 一套编译原理实验包的定位从字符流走到四元式中间不能断链编译原理这门课实验比课难啃。教材讲完 NFA 转 DFA 就翻页真落到代码一个字符回退没处理好整个词法分析器就在注释边界上死循环调试两小时找不到原因。这套某高校编译原理课程的整套实验把词法分析、语法分析、语义分析与四元式生成几关一次性摆齐每一关都有可对照的输入输出。它适合正在赶实验、被 DFA 和分析表卡住的人也适合上完课想把课堂上那套理论真正写成可运行代码的人。代码不一定漂亮但链路是完整的字符流进Token 流出Token 进语法树或四元式出中间哪一环断了立刻能看出来。这种“能对照”的价值比一份只有最终答案的代码高得多。2. 实验全景与目录结构五个实验如何共用一份 Token 与 AST 定义很多人第一次拆这类实验包会下意识按实验序号一个个文件夹翻翻完发现 src 目录里的东西互相引用改一处编译全崩。真正该先看的是接口Token 结构体长什么样、AST 节点怎么定义、四元式怎么表示。这三个结构定死了后面五个实验其实是在同一根管道上加零件——词法负责把字符流切成 Token语法负责把 Token 组织成树语义负责在树上挂类型和符号中间代码生成负责把树摊平成四元式序列目标代码生成则是把四元式翻译成栈式虚拟机的指令。想清楚这根管道再看目录就不会迷路。2.1 从词法到目标代码每个实验的输入输出契约不同学校的实验切分粒度不一样常见做法是切五到六关。第一关词法输入一个源文件输出 Token 序列要求能正确处理关键字、标识符、常量、注释和双字符运算符第二关语法分析之一用递归下降或 LL(1) 处理表达式和语句输出语法树或直接输出归约序列第三关语法分析之二构造 SLR(1) 或 LR(1) 分析表表驱动地跑一遍同样的输入两边结果要能对上第四关语义分析建符号表、做类型检查、报告未声明变量和重复定义第五关中间代码生成把语法树翻译成四元式布尔表达式要做短路求值和控制流回填。部分实验包还会加一关目标代码生成把四元式映射成一套简单的栈式指令。把这五关的输入输出列成表比翻代码快得多实验关输入输出核心数据结构词法分析源文件字符流Token 序列Token{type, lexeme, line, col}语法分析递归下降Token 序列ASTAst{kind, child[], attr}语法分析SLRToken 序列 文法文件分析表 接受/报错Action/Goto二维表语义分析AST带类型的 AST 符号表Sym{name, type, offset}中间代码生成带类型 AST四元式序列Quad{op, a1, a2, res}这张表最有用的地方在于排错顺序。输出不对时不要急着改后面先确认上一关的输出是不是对的——词法把切成了和语法分析怎么写都会报错而你会在第 4 关浪费掉一整晚。2.2 目录与文件职责头文件里藏着实验之间的接口典型的目录长这样不同版本名字会有出入但分层逻辑基本一致compiler-lab/ ├── include/ │ ├── token.h # Token 类型枚举与结构体全项目最底层契约 │ ├── lexer.h # next_token() 等对外接口 │ ├── ast.h # AST 节点种类与构造函数声明 │ ├── parser.h # 递归下降与 SLR 两套解析入口 │ ├── symtab.h # 符号表作用域链 │ └── quad.h # 四元式结构与回填链表 ├── src/ │ ├── lexer.c # 手写状态机 │ ├── nfa.c / dfa.c # 正则→NFA→DFA 的子集构造与最小化 │ ├── parser_rd.c # 递归下降 │ ├── parser_lr.c # SLR 分析表构造 表驱动主循环 │ ├── sema.c # 语义动作与类型检查 │ ├── quad.c # 四元式生成与回填 │ └── main.c # 按 -stage 参数决定跑到哪一关 ├── grammar/ │ └── grammar.txt # 产生式文本SLR 那关直接读它建表 ├── tests/ │ ├── lex/ parse/ sema/ └── Makefileinclude/下面这几个头文件本质上是各关之间的合同。token.h改了字段lexer.c和parser_rd.c都要跟着改quad.h加了label字段回填逻辑就得重写。我一般建议先只读三个头文件把字段含义抄在纸上再去看实现效率比直接读.c快一倍。grammar/grammar.txt这类文本文件容易被忽略但它决定了 SLR 那关能不能自动建表。常见格式是每行一条产生式左侧非终结符右侧符号序列用空格分开|表示或空串用一个特殊符号比如ε表示。写文法时踩过的最典型的坑是忘了消除左递归和提取左公因子——这两个操作在递归下降里是必须的在 SLR 里则不是必须的但能显著减少冲突。2.3 构建与首次跑通Makefile 里预留的三个 stage 开关这类实验包基本不依赖第三方库gcc加make就能编。少数版本会用 Flex/Bison 做对照实现那就需要额外装flex、bison也有纯 Java 版本走mvn package。拿到手先看有没有Makefile或CMakeLists.txt没有的话直接gcc src/*.c -Iinclude -o cc也能编出来只是调试信息会少一些。一个有经验的写法是把 stage 做成运行时参数而不是编译期宏。这样同一份二进制可以跑到任意一关对照测试时特别省事CC gcc CFLAGS -g -O0 -Wall -Iinclude SRCS $(wildcard src/*.c) OBJS $(SRCS:.c.o) TARGET bin/cc all: $(TARGET) $(TARGET): $(OBJS) mkdir -p bin $(CC) $(OBJS) -o $ # 单独编某一关方便只改一个文件时快速验证 lex: src/lexer.o src/main.o $(CC) $^ -o bin/cc_lex clean: rm -f $(OBJS) $(TARGET) bin/cc_lex .PHONY: all clean lex-g -O0是故意的实验代码本来就慢不到哪去开着调试信息才能用gdb单步跟状态机的state变量-Wall也别省Token 结构体里少初始化一个字段靠警告比靠运行时报错发现得早。bin/cc_lex这个单独目标是为了在只改词法时不用重编整个项目几十个文件的工程全量编译一轮十几秒改十次就是几分钟。编完之后先跑冒烟测试三条命令确认环境没问题# 1. 只跑词法看 Token 流是否合理 ./bin/cc -stage lex tests/lex/basic.c # 2. 跑到语法分析输出 AST 的括号表示 ./bin/cc -stage parse tests/parse/expr.c # 3. 跑到四元式检查生成的中间代码条数对不对 ./bin/cc -stage quad tests/sema/loop.c提示-stage lex这类参数在不同版本里可能叫--phase、-p或者干脆用环境变量控制。跑之前先./bin/cc -h看一眼别照着别人的命令硬敲报unknown option时先怀疑参数名而不是代码。三条都跑通说明工具链和基本逻辑没问题接下来再逐关深入。跑不通时优先看第一条——词法这关的输出是纯文本 Token 流肉眼就能判断对错是整条链路上最容易定位问题的一段。3. 前端两关拆解手写 DFA 词法分析器与 SLR 语法分析器前端这两关是整个实验包里代码量最大、也最容易翻车的部分。词法看着简单一个或者1..10就能让状态机走错分支语法分析看着复杂但真正难的不是写主循环是把文法改造成递归下降能吃下去的形状或者把分析表构造过程中的闭包算对。这两关有个共同点它们都属于“输入确定、输出确定”的确定性计算所以调试手段很直接——把中间结果打出来比对不需要靠猜。3.1 词法分析最长匹配、回退与行号维护手写词法分析器的核心就一条规则最长匹配。读到a不能立刻返回标识符得继续往后吃字符直到遇见不能构成标识符的字符为止然后把位置回退到那个字符前。数字、运算符同理后面跟就得切成而不是两个 Token。这套逻辑用一个大while加若干if分支就能写完不一定要写成表驱动的状态转移矩阵但状态边界要想清楚。/* src/lexer.c一次调用返回一个 Token指针只前进不倒退 */ Token next_token(Lexer *lx) { while (lx-pos lx-len) { char c lx-src[lx-pos]; /* 1. 空白与换行行号必须在这里累加后面报错全靠它 */ if (c || c \t || c \r) { lx-pos; lx-col; continue; } if (c \n) { lx-line; lx-col 1; lx-pos; continue; } /* 2. 注释// 吞到行尾块注释吞到闭合没闭合要报错而不是死循环 */ if (c / peek(lx, 1) /) { skip_line_comment(lx); continue; } if (c / peek(lx, 1) *) { skip_block_comment(lx); continue; } /* 3. 标识符与关键字先按标识符整段收下再回查关键字表 */ if (isalpha((unsigned char)c) || c _) { int start lx-pos; while (isalnum((unsigned char)lx-src[lx-pos]) || lx-src[lx-pos] _) lx-pos; return make_ident_or_keyword(lx, start, lx-pos - start); } /* 4. 数字常量整数部分收完只有后面真的跟数字才吃小数点 */ if (isdigit((unsigned char)c)) { int start lx-pos; while (isdigit((unsigned char)lx-src[lx-pos])) lx-pos; if (lx-src[lx-pos] . isdigit((unsigned char)lx-src[lx-pos 1])) { lx-pos; while (isdigit((unsigned char)lx-src[lx-pos])) lx-pos; } return make_number(lx, start, lx-pos - start); } /* 5. 双字符运算符贪心先看两位再退回一位 */ if (c || c || c || c !) { if (peek(lx, 1) ) { lx-pos 2; return make_op2(lx, c, ); } lx-pos 1; return make_op1(lx, c); } if ((c peek(lx, 1) ) || (c - peek(lx, 1) -)) { lx-pos 2; return make_op2(lx, c, c); } /* 6. 单字符运算符与界符 */ lx-pos; return make_single(lx, c); } return make_token_eof(lx); }这段代码有三个地方值得单独拎出来看。第一是行号维护\n分支必须放在跳过空白之前否则行号永远不涨语义阶段报“变量未声明”时定位全错。第二是数字里的小数点判断1.这种写法在 C 里不合法但在很多实验用的简化语言里要当整数1加一个界符.处理所以必须往后多看一位确认不确认就会把1..10这种输入吃成1.加.10然后语法分析报一堆莫名其妙的错。第三是peek(lx, 1)在文件末尾的越界问题稳妥做法是让源文件缓冲区末尾多留两个\0或者让peek内部先判pos n len。关键字识别不要写成一长串strcmp。常见做法是维护一张静态表用首字母做一次粗筛再逐个比较或者更省事的办法是在哈希桶里同时放标识符和关键字查到了就返回对应 Token 类型。几十个关键字的小语言线性比较也够快但把len先比一遍能省掉大部分strcmp调用。col字段很多人不写觉得有行号就够。真调起来会发现同一行里有三个报错只告诉你第 7 行你还是得自己数。加上列号报错信息直接指到字符改起来省事得多。3.2 正则到 DFA子集构造与最小化的另一条路线实验包里通常会有一关单独做“正则表达式到 DFA”的转换和手写词法器并列用来对照。这条路线的流程是固定的正则表达式先加显式连接符和括号转成后缀表达式用 Thompson 构造法建成 NFA再用子集构造法确定化成 DFA最后做最小化。真正写起来子集构造那一步的closure和move是两个必须写对的函数。# tools/subset.py子集构造的核心两个操作演示用 Python 更直观 def epsilon_closure(states, nfa): 从状态集合出发沿 ε 边能到达的所有状态注意用栈而不是递归 stack, closure list(states), set(states) while stack: s stack.pop() for ch, t in nfa[s]: # nfa[s] 是 (字符, 目标状态) 列表 if ch is None and t not in closure: # None 表示 ε 边 closure.add(t) stack.append(t) return frozenset(closure) def move(states, ch, nfa): 吃掉一个字符 ch 之后能到达的状态集合不含 ε 扩展 return frozenset(t for s in states for c, t in nfa[s] if c ch) def subset_construction(nfa, start, alphabet): dfa_start epsilon_closure({start}, nfa) dfa, queue, seen {}, [dfa_start], {dfa_start} while queue: cur queue.pop(0) for ch in alphabet: nxt epsilon_closure(move(cur, ch, nfa), nfa) if not nxt: # 空集不建状态直接记死状态 continue dfa.setdefault(cur, {})[ch] nxt if nxt not in seen: seen.add(nxt) queue.append(nxt) return dfaepsilon_closure用显式栈而不是递归是因为 NFA 状态数虽小但 ε 环在错误构造下可能出现递归会直接栈溢出。move返回空集时不要新建 DFA 状态直接当死状态处理——很多实现给死状态也分配一个编号结果最小化时多出一堆无用的等价类。最小化用 Hopcroft 划分法先把状态分成“接受态”和“非接受态”两组再按每个字符上的转移落在哪一组不断细分直到划分不再变化。实验用的字母表通常只有几十个字符暴力按字符扫描分组完全够用不需要真的去实现带分裂队列的优化版本。这条路线和手写词法器最大的区别在于手写版能处理/* */这种非正则的嵌套结构吗其实块注释不是正则语言但因为它不允许嵌套所以仍是正则的一旦要求支持嵌套注释就必须在手写状态机里加一个计数器。这个细节在实验报告里写上一句往往能加分。3.3 递归下降先消左递归再谈语法树递归下降的代码结构几乎是一比一照着文法抄的每个非终结符一个函数。但有个前提文法里不能有左递归也不能有需要回溯的公共前缀否则递归下降要么爆栈要么回溯到天荒地老。E - E T | T这种写法直接照抄程序第一次调用parse_E就会无限递归下去血泪经验是拿到文法第一件事就是检查每条产生式的第一个符号是不是它自己。/* src/parser_rd.cE - E T | T 消除左递归后写成循环 */ Ast *parse_E(Parser *p) { Ast *left parse_T(p); /* 先拿到第一个 T */ while (check(p, TK_PLUS) || check(p, TK_MINUS)) { Token op advance(p); /* 吃掉运算符 */ Ast *right parse_T(p); /* 再拿一个 T右结合的部分递归 */ left ast_binop(op.type, left, right, op.line); } return left; /* 循环结束说明后面没有 /-返回整棵子树 */ } /* T - T * F | T / F | F同样改写成循环 */ Ast *parse_T(Parser *p) { Ast *left parse_F(p); while (check(p, TK_STAR) || check(p, TK_SLASH)) { Token op advance(p); Ast *right parse_F(p); left ast_binop(op.type, left, right, op.line); } return left; }左递归消除的标准变换是把E - E T | T变成E - T E、E - T E | ε但落到代码上E这个非终结符没必要真的单独写一个函数用一个while循环吸收掉即可效果完全等价而且省掉一层函数调用的开销和一层 ε 判断。这是递归下降里最实用的一条经验凡是形如“左递归 单个后缀”的产生式都可以直接折叠成循环。parse_F处理括号和一元负号时要注意优先级。-a * b在多数语言里等价于(-a) * b而不是-(a * b)所以一元负号应该在parse_F里处理直接构造成ast_unary(NEG, parse_F(p))而不是在parse_E层面处理。语法树的节点结构建议用“类型 定长子节点数组”而不是“左孩子右兄弟”实验规模的表达式深度撑死几十层定长数组更好写也好打印。打印函数写成括号前缀形式( (* a b) c)这种一行输出就能看出结构对不对比在调试器里展开指针快十倍。3.4 SLR(1) 分析表驱动ACTION/GOTO 表怎么用起来SLR 这一关的难点不在驱动循环在于把分析表构造出来。流程是给文法增广求所有非终结符的 FIRST 和 FOLLOW 集构造 LR(0) 项目集规范族然后对每个项目集移进项目填 ACTION 的 shift归约项目按 FOLLOW 集填 reduce接受项目填 acceptGOTO 表则按项目集的转移填。表建好之后驱动循环其实很短。/* src/parser_lr.c分析表驱动状态栈与符号栈同步压弹 */ int lr_parse(LRTable *t, Token *input, int n) { int state_stack[256], sp 0, ip 0; state_stack[sp] 0; /* 0 号状态是初始状态 */ while (1) { int s state_stack[sp]; int a terminal_index(input[ip].type); /* EOF 也要占一个终结符位 */ Action act t-action[s][a]; if (act.kind ACT_SHIFT) { state_stack[sp] act.target; /* 移进状态入栈输入指针后移 */ ip; } else if (act.kind ACT_REDUCE) { Rule *r t-rules[act.target]; sp - r-rhs_len; /* 按产生式右部长度弹栈 */ int g t-gotos[state_stack[sp]][r-lhs]; if (g 0) return syntax_error(input[ip], goto 表缺失); state_stack[sp] g; /* 归约后按 GOTO 压新状态 */ } else if (act.kind ACT_ACCEPT) { return 1; /* 接受 */ } else { return syntax_error(input[ip], unexpected token); } } }terminal_index这个函数看着不起眼但它决定了表的列顺序。常见的坑是词法阶段返回的 Token 类型有几十种而文法里只用到其中一部分两边索引对不上表查出来的动作就全错位了。稳妥做法是写一个显式的映射数组长度等于 Token 类型总数用不到的填-1查表时先判断再访问。SLR 出现冲突是常态不是 bug。if (E) S else S这种悬挂 else 文法天生就有移进-归约冲突表达式文法如果不分层写E - E E | E * E也会冲突一片。解决办法有两个方向一是改文法把优先级编码进非终结符层次里E/T/F三层写法就是为了这个二是保留冲突用优先级和结合性规则手工指定移进优先还是归约优先。实验里更推荐第一种因为改完文法后 SLR 表和递归下降的结果能对上方便互相验证。验证方法很直接拿同一份测试输入分别跑递归下降和 SLR比较两者的接受/拒绝结果。如果递归下降接受而 SLR 拒绝多半是 FOLLOW 集算错了导致该归约的地方没归约如果两边都接受但归约序列不一样那可能是文法有二义性得回去检查。4. 语义分析与中间代码生成符号表、类型检查与四元式回填前端两关跑通只是知道了“这句话语法合法”还不知道“这句话有没有意义”。int a; a hello;语法上完全合法语义上是错的。语义分析这一关要干三件事建符号表、检查类型、报告未声明和重复定义。中间代码生成则要把树形结构摊平成线性的四元式序列难点全在控制流的跳转目标上——布尔表达式的短路求值、if/else的分支汇合、while的循环回边这些跳转目标在生成当下根本不知道必须靠回填。4.1 符号表作用域链 哈希桶的最小实现符号表要考虑作用域。全局变量和函数里的局部变量可以同名内层块又能遮蔽外层所以结构上必须是一条链每进入一个{}就压一个新的作用域退出就弹掉。查找时从当前作用域往外走找到第一个匹配就停这就是最内层优先的遮蔽规则。/* include/symtab.h作用域链 哈希桶 */ #define BUCKET_SIZE 211 /* 取个质数减少哈希冲突 */ typedef struct Sym { char name[64]; Type type; int offset; /* 相对 fp 的偏移目标代码生成时才填 */ int defined; /* 0 表示只声明未定义用于查重复定义 */ struct Sym *next; /* 同一个桶里的下一个符号 */ } Sym; typedef struct Scope { Sym *bucket[BUCKET_SIZE]; struct Scope *parent; } Scope; /* 在当前作用域插入返回 NULL 表示同名重复定义 */ Sym *scope_insert(Scope *sc, const char *name, Type ty) { unsigned h hash(name) % BUCKET_SIZE; for (Sym *s sc-bucket[h]; s; s s-next) if (strcmp(s-name, name) 0) return NULL; Sym *s calloc(1, sizeof(Sym)); strncpy(s-name, name, sizeof(s-name) - 1); s-type ty; s-next sc-bucket[h]; sc-bucket[h] s; return s; } /* 从当前作用域往外找 */ Sym *scope_lookup(Scope *sc, const char *name) { unsigned h hash(name) % BUCKET_SIZE; for (; sc; sc sc-parent) for (Sym *s sc-bucket[h]; s; s s-next) if (strcmp(s-name, name) 0) return s; return NULL; }插入时只查当前作用域的桶不往外查这样才能允许内层同名遮蔽查找时才沿parent链一路往外。defined标志位是为了区分int a;和int a 1;前者只声明后者才定义两次声明不算错两次定义才算。offset字段在语义阶段留空等目标代码生成时按类型大小顺序分配符号表本身不关心布局。哈希函数用最朴素的h h * 31 c就行几十个变量的实验规模冲突率可以忽略。桶大小取质数是为了让%出来的分布更均匀取 128 这种 2 的幂反而容易在名字长度相似时扎堆。4.2 语义动作挂哪里类型检查与隐式转换语义动作的挂载位置有两种流派一种是边解析边做递归下降的函数里直接调check和emit另一种是先建完整语法树再单独遍历一遍。实验规模下两种都行但边解析边做省一次遍历而且报错时手上的line信息更准确缺点是解析函数会变得很脏语法和语义搅在一起。真要二开建议先建树再遍历结构清晰得多。/* src/sema.c二元运算的类型检查返回结果类型出错返回 TY_ERROR */ Type check_binop(int op, Type l, Type r, int line) { if (l TY_ERROR || r TY_ERROR) return TY_ERROR; /* 错误已报过别重复报 */ switch (op) { case OP_ADD: case OP_SUB: case OP_MUL: if (l TY_INT r TY_INT) return TY_INT; if (l TY_FLOAT r TY_FLOAT) return TY_FLOAT; if (l TY_INT r TY_FLOAT) return TY_FLOAT; /* 隐式提升 */ if (l TY_FLOAT r TY_INT) return TY_FLOAT; error_at(line, 类型不匹配%s %s %s, type_name(l), op_name(op), type_name(r)); return TY_ERROR; case OP_DIV: if (r TY_INT) return TY_INT; /* 整数除法需注意除零 */ if (r TY_FLOAT) return l; /* 浮点除法结果随左操作数 */ error_at(line, 除数类型不合法); return TY_ERROR; case OP_LT: case OP_GT: case OP_EQ: if (l ! r !(is_numeric(l) is_numeric(r))) { error_at(line, 比较运算两边类型不可比); return TY_ERROR; } return TY_BOOL; /* 比较结果一定是布尔 */ } return TY_ERROR; }这段代码有两个细节值得注意。第一是错误传播TY_ERROR一旦出现就往上冒泡不要在每个调用点重复报错否则一个类型错误能刷出十几条重复信息把真正的第一个错误埋掉。第二是隐式转换的方向int和float混合运算统一提升到float这在生成四元式时要插一条int2float的转换指令不能只在类型上标一下就算了否则后面算出来的机器码是错的。数组和指针的类型检查更麻烦a[i]要检查a是数组且i是整数*p要检查p是指针。实验包的简化语言里这部分通常砍掉了如果要做二次开发这块是第一个能加分的扩展点。4.3 四元式与回填短路求值的跳转链怎么补四元式就是(op, arg1, arg2, result)四元组a b c生成(, b, c, t1)加(, t1, _, a)。麻烦的是控制流if (a b) S里a为假时该跳到哪生成a的四元式的那一刻S的代码还没生成跳转目标根本不知道只能先留个空记下这条指令的位置等目标确定了再回头补上。这就是回填。/* include/quad.h四元式与回填链表 */ typedef struct { char op[8]; char a1[16], a2[16], res[16]; } Quad; typedef struct IntList { /* 待回填的指令位置链表 */ int idx; struct IntList *next; } IntList; int next_quad 0; Quad quads[MAX_QUAD]; /* 生成一条四元式返回它的下标后面回填要用 */ int emit(const char *op, const char *a1, const char *a2, const char *res) { Quad *q quads[next_quad]; snprintf(q-op, sizeof(q-op), %s, op); snprintf(q-a1, sizeof(q-a1), %s, a1 ? a1 : _); snprintf(q-a2, sizeof(q-a2), %s, a2 ? a2 : _); snprintf(q-res, sizeof(q-res), %s, res ? res : _); return next_quad; } /* 把链表里所有位置的目标字段补成 target */ void backpatch(IntList *l, int target) { char buf[16]; snprintf(buf, sizeof(buf), %d, target); for (; l; l l-next) snprintf(quads[l-idx].res, sizeof(quads[l-idx].res), %s, buf); }配合短路求值文法是这么写的E - E1 || M E2 { backpatch(E1.falselist, M.quad); E.truelist merge(E1.truelist, E2.truelist); E.falselist E2.falselist; } M - ε { M.quad next_quad; } /* 记录 || 右边第一条指令的位置 */M这个空产生式看起来多余实际上它是整个回填机制的关键。E1 || E2里如果E1为真整串就为真右边的E2根本不该算所以要跳过E2的代码。跳到哪里跳到E2的第一条指令之后也就是M.quad那个位置。而E1为真时的跳转链是在生成E1的时候就记下来的truelist那时候还不知道目标只能等M出现后回填。少了M你就只能把目标猜成“下一行”一旦E2展开成多条指令整个跳转就偏了而且这种错很难在四元式文本里看出来跑起来才发现少执行了一段。对称处理E1.falselist和E2.falselist合并E1.truelist回填到M.quad。while语句则需要多记一个循环入口的标号循环体结束时生成无条件跳转回入口break语句的跳转链挂在循环外层的下一条指令上。这些规则写清楚了中间代码这一关基本就稳了。5. 避坑与排查五个能让实验卡到凌晨的坑实验代码的 bug 有个共同特征报错信息指向的位置往往不是出错的位置。词法错了会在语法报错语法错了会在语义报错语义错了会在四元式跑飞。所以排查的第一原则是逐关验证输出而不是从最后的报错往前猜。下面这五个坑基本覆盖了大部分实验卡壳的场景。5.1 词法与语法层的三个坑现象输入ab或者1..10词法输出一堆莫名其妙的 Token语法分析直接报 unexpected token。原因没有做最长匹配或者双字符运算符判断顺序写反了。应该切成和但如果先判断单字符就会切成三个1..10如果数字分支不往后多看一位就会把1.当成浮点数吃掉剩下.10变成界符加数字。解决所有多字符 Token 严格按“先看两位、再看一位”的顺序判断数字里的小数点必须往后多看一位确认是数字才吃。写完拿ab、1..10、ab、x--y这四个输入手工验一遍 Token 流比跑任何测试都直观。现象语义阶段报“变量i未声明”但源文件里明明写了int i;。原因词法阶段的Token结构体里没存行号或者存了但\n分支没累加更隐蔽的一种是 Token 之间的空白被跳过时pos前进了而col没跟着变导致后续定位全偏。解决所有前进指针的地方统一走一个advance(lx)函数行号和列号在里面同步更新杜绝手写lx-pos。报错函数只用Token.line和Token.col不再自己算。现象递归下降跑稍微长一点的表达式就段错误栈直接爆掉。原因文法里的左递归没消除parse_E调用parse_Tparse_T又绕回parse_E无限递归。或者文法本身没问题但输入里有语法错误错误恢复没写解析器在某个非终结符上原地打转。解决拿到文法先扫一遍每条产生式右部第一个符号如果等于左部立刻消除左递归改成循环。错误恢复至少要做到“遇到不认识的 Token 就advance一个继续”保证解析器一定往前走不会卡死在原地。5.2 语义与中间代码层的两个坑现象SLR 分析表构造出来一堆冲突程序在某个输入上该归约的时候却移进了最后报错位置莫名其妙。原因FOLLOW 集算错了或者项目集规范族的闭包函数漏了传播。经典错误是closure只做了一层没有递归到不动点导致某些归约项目的展望符不全ACTION 表里该填 reduce 的格子空着。解决把 FIRST 和 FOLLOW 集打印出来和手工算的对一遍closure一定用while循环跑到集合不再变化为止。建表时顺手把每个动作的来源哪条产生式、哪个项目集记下来冲突时能直接看到是哪两条规则在打架比盯着ACTION[s][a]的整数编码强得多。现象四元式生成出来条数对得上但执行顺序不对if (a b)里b明明为假后面的S还是执行了。原因回填的目标位置错了最常见的是M产生式的位置记成了next_quad - 1或者干脆没写M导致||和的短路跳转跳到了错误的行。解决把四元式按行号打印出来每行标上next_quad的下标然后手工在纸上画一遍跳转箭头。凡是res字段里出现非变量名的数字就是跳转目标对照源码逻辑走一遍哪条箭头指向了不该去的地方一眼就能看出来。注意这五个坑里有四个的共同点是“上游输出没验证就往下走”。养成每关跑完先看一眼输出的习惯比事后用调试器追指针省下的时间多得多。6. 二次开发把实验级编译器改成能跑真实子集的玩具编译器实验代码能跑通之后最有价值的动作不是加功能是先把它从“只能演示”变成“能验证”。我一般会做三件事给每一关加一个金标准输出比对脚本把tests/目录下的用例按关卡组织跑完自动 diff把main.c里散落的printf收敛到一个统一的 dump 函数输出格式固定把文法文件真正做成运行时可替换的而不是编译进代码里。这三件事做完后面每改一处都能立刻知道有没有把前面的关卡改坏。改造方向上成本最低、收益最明显的是加类型系统里的数组。符号表加一个elem_type和array_len字段语义检查里给a[i]加一条“左部是数组、下标是整数”的规则四元式生成时把a[i]翻译成([], i, _, t)取址再加偏移。改动集中在symtab.h、sema.c、quad.c三个文件两三百行能收住。其次是常量折叠在语义遍历到二元运算且两边都是字面量时直接算出结果不生成四元式改动只涉及一个函数但能立刻在四元式输出里看到条数下降验证起来很爽。改造点需要改的文件验证方式数组与下标symtab.h、sema.c、quad.c用int a[10]; a[3] 1;看四元式是否生成取址常量折叠sema.c的二元运算分支对比12*3折叠前后四元式条数目标代码生成新增codegen.c、quad.h加标号字段用栈式虚拟机跑四元式比对运行结果错误恢复parser_rd.c各同步点故意写错一行看能否继续报出后续错误验证方法我吃过亏。最早是改完直接拿一个大例子跑跑通了就认为没问题结果三周后回头发现中间代码里的跳转偏移全错了一位之前那个例子恰好没走到那条分支。后来改成小步验证每加一个特性先在tests/sema/里加一个最小用例只覆盖这一条规则跑通了再加第二个用例。用例小到只有三五行代码出问题时一眼能定位到是哪条规则写错了而不是在一百行输出里捞针。从那以后我每次动语义或回填相关的代码都强制先把最小用例跑一遍再碰大例子这个习惯救过我不少次。希望帮到你。本文还有配套的精品资源点击获取
简介面向高校编译原理课程学习者与任课教师这份实验代码合集对应中国海洋大学2020年春季学期课程覆盖从词法分析到编译器综合的八个实验及配套要求文档帮助读者把文法、自动机与代码生成知识落到可运行程序。压缩包共74个文件、约774KB以18个C源文件为核心配合8个Lex规则、8个Yacc规则、8个头文件、7个文本说明及Makefile等构建脚本另含实验要求doc与测试数据目录按实验阶段组织。已有4419人学习适合课程实验复现与编译器构造入门。读者可依次练习记号识别、递归下降与LL(1)/LR解析、符号表与类型检查、中间代码生成、常量折叠与死代码消除、目标代码生成及错误诊断并在综合实验中串起完整编译流程也可参考Flex/Bison工具链的写法理解各阶段的输入输出衔接与调试思路。1. 一套编译原理实验包的定位从字符流走到四元式中间不能断链编译原理这门课实验比课难啃。教材讲完 NFA 转 DFA 就翻页真落到代码一个字符回退没处理好整个词法分析器就在注释边界上死循环调试两小时找不到原因。这套某高校编译原理课程的整套实验把词法分析、语法分析、语义分析与四元式生成几关一次性摆齐每一关都有可对照的输入输出。它适合正在赶实验、被 DFA 和分析表卡住的人也适合上完课想把课堂上那套理论真正写成可运行代码的人。代码不一定漂亮但链路是完整的字符流进Token 流出Token 进语法树或四元式出中间哪一环断了立刻能看出来。这种“能对照”的价值比一份只有最终答案的代码高得多。2. 实验全景与目录结构五个实验如何共用一份 Token 与 AST 定义很多人第一次拆这类实验包会下意识按实验序号一个个文件夹翻翻完发现 src 目录里的东西互相引用改一处编译全崩。真正该先看的是接口Token 结构体长什么样、AST 节点怎么定义、四元式怎么表示。这三个结构定死了后面五个实验其实是在同一根管道上加零件——词法负责把字符流切成 Token语法负责把 Token 组织成树语义负责在树上挂类型和符号中间代码生成负责把树摊平成四元式序列目标代码生成则是把四元式翻译成栈式虚拟机的指令。想清楚这根管道再看目录就不会迷路。2.1 从词法到目标代码每个实验的输入输出契约不同学校的实验切分粒度不一样常见做法是切五到六关。第一关词法输入一个源文件输出 Token 序列要求能正确处理关键字、标识符、常量、注释和双字符运算符第二关语法分析之一用递归下降或 LL(1) 处理表达式和语句输出语法树或直接输出归约序列第三关语法分析之二构造 SLR(1) 或 LR(1) 分析表表驱动地跑一遍同样的输入两边结果要能对上第四关语义分析建符号表、做类型检查、报告未声明变量和重复定义第五关中间代码生成把语法树翻译成四元式布尔表达式要做短路求值和控制流回填。部分实验包还会加一关目标代码生成把四元式映射成一套简单的栈式指令。把这五关的输入输出列成表比翻代码快得多实验关输入输出核心数据结构词法分析源文件字符流Token 序列Token{type, lexeme, line, col}语法分析递归下降Token 序列ASTAst{kind, child[], attr}语法分析SLRToken 序列 文法文件分析表 接受/报错Action/Goto二维表语义分析AST带类型的 AST 符号表Sym{name, type, offset}中间代码生成带类型 AST四元式序列Quad{op, a1, a2, res}这张表最有用的地方在于排错顺序。输出不对时不要急着改后面先确认上一关的输出是不是对的——词法把切成了和语法分析怎么写都会报错而你会在第 4 关浪费掉一整晚。2.2 目录与文件职责头文件里藏着实验之间的接口典型的目录长这样不同版本名字会有出入但分层逻辑基本一致compiler-lab/ ├── include/ │ ├── token.h # Token 类型枚举与结构体全项目最底层契约 │ ├── lexer.h # next_token() 等对外接口 │ ├── ast.h # AST 节点种类与构造函数声明 │ ├── parser.h # 递归下降与 SLR 两套解析入口 │ ├── symtab.h # 符号表作用域链 │ └── quad.h # 四元式结构与回填链表 ├── src/ │ ├── lexer.c # 手写状态机 │ ├── nfa.c / dfa.c # 正则→NFA→DFA 的子集构造与最小化 │ ├── parser_rd.c # 递归下降 │ ├── parser_lr.c # SLR 分析表构造 表驱动主循环 │ ├── sema.c # 语义动作与类型检查 │ ├── quad.c # 四元式生成与回填 │ └── main.c # 按 -stage 参数决定跑到哪一关 ├── grammar/ │ └── grammar.txt # 产生式文本SLR 那关直接读它建表 ├── tests/ │ ├── lex/ parse/ sema/ └── Makefileinclude/下面这几个头文件本质上是各关之间的合同。token.h改了字段lexer.c和parser_rd.c都要跟着改quad.h加了label字段回填逻辑就得重写。我一般建议先只读三个头文件把字段含义抄在纸上再去看实现效率比直接读.c快一倍。grammar/grammar.txt这类文本文件容易被忽略但它决定了 SLR 那关能不能自动建表。常见格式是每行一条产生式左侧非终结符右侧符号序列用空格分开|表示或空串用一个特殊符号比如ε表示。写文法时踩过的最典型的坑是忘了消除左递归和提取左公因子——这两个操作在递归下降里是必须的在 SLR 里则不是必须的但能显著减少冲突。2.3 构建与首次跑通Makefile 里预留的三个 stage 开关这类实验包基本不依赖第三方库gcc加make就能编。少数版本会用 Flex/Bison 做对照实现那就需要额外装flex、bison也有纯 Java 版本走mvn package。拿到手先看有没有Makefile或CMakeLists.txt没有的话直接gcc src/*.c -Iinclude -o cc也能编出来只是调试信息会少一些。一个有经验的写法是把 stage 做成运行时参数而不是编译期宏。这样同一份二进制可以跑到任意一关对照测试时特别省事CC gcc CFLAGS -g -O0 -Wall -Iinclude SRCS $(wildcard src/*.c) OBJS $(SRCS:.c.o) TARGET bin/cc all: $(TARGET) $(TARGET): $(OBJS) mkdir -p bin $(CC) $(OBJS) -o $ # 单独编某一关方便只改一个文件时快速验证 lex: src/lexer.o src/main.o $(CC) $^ -o bin/cc_lex clean: rm -f $(OBJS) $(TARGET) bin/cc_lex .PHONY: all clean lex-g -O0是故意的实验代码本来就慢不到哪去开着调试信息才能用gdb单步跟状态机的state变量-Wall也别省Token 结构体里少初始化一个字段靠警告比靠运行时报错发现得早。bin/cc_lex这个单独目标是为了在只改词法时不用重编整个项目几十个文件的工程全量编译一轮十几秒改十次就是几分钟。编完之后先跑冒烟测试三条命令确认环境没问题# 1. 只跑词法看 Token 流是否合理 ./bin/cc -stage lex tests/lex/basic.c # 2. 跑到语法分析输出 AST 的括号表示 ./bin/cc -stage parse tests/parse/expr.c # 3. 跑到四元式检查生成的中间代码条数对不对 ./bin/cc -stage quad tests/sema/loop.c提示-stage lex这类参数在不同版本里可能叫--phase、-p或者干脆用环境变量控制。跑之前先./bin/cc -h看一眼别照着别人的命令硬敲报unknown option时先怀疑参数名而不是代码。三条都跑通说明工具链和基本逻辑没问题接下来再逐关深入。跑不通时优先看第一条——词法这关的输出是纯文本 Token 流肉眼就能判断对错是整条链路上最容易定位问题的一段。3. 前端两关拆解手写 DFA 词法分析器与 SLR 语法分析器前端这两关是整个实验包里代码量最大、也最容易翻车的部分。词法看着简单一个或者1..10就能让状态机走错分支语法分析看着复杂但真正难的不是写主循环是把文法改造成递归下降能吃下去的形状或者把分析表构造过程中的闭包算对。这两关有个共同点它们都属于“输入确定、输出确定”的确定性计算所以调试手段很直接——把中间结果打出来比对不需要靠猜。3.1 词法分析最长匹配、回退与行号维护手写词法分析器的核心就一条规则最长匹配。读到a不能立刻返回标识符得继续往后吃字符直到遇见不能构成标识符的字符为止然后把位置回退到那个字符前。数字、运算符同理后面跟就得切成而不是两个 Token。这套逻辑用一个大while加若干if分支就能写完不一定要写成表驱动的状态转移矩阵但状态边界要想清楚。/* src/lexer.c一次调用返回一个 Token指针只前进不倒退 */ Token next_token(Lexer *lx) { while (lx-pos lx-len) { char c lx-src[lx-pos]; /* 1. 空白与换行行号必须在这里累加后面报错全靠它 */ if (c || c \t || c \r) { lx-pos; lx-col; continue; } if (c \n) { lx-line; lx-col 1; lx-pos; continue; } /* 2. 注释// 吞到行尾块注释吞到闭合没闭合要报错而不是死循环 */ if (c / peek(lx, 1) /) { skip_line_comment(lx); continue; } if (c / peek(lx, 1) *) { skip_block_comment(lx); continue; } /* 3. 标识符与关键字先按标识符整段收下再回查关键字表 */ if (isalpha((unsigned char)c) || c _) { int start lx-pos; while (isalnum((unsigned char)lx-src[lx-pos]) || lx-src[lx-pos] _) lx-pos; return make_ident_or_keyword(lx, start, lx-pos - start); } /* 4. 数字常量整数部分收完只有后面真的跟数字才吃小数点 */ if (isdigit((unsigned char)c)) { int start lx-pos; while (isdigit((unsigned char)lx-src[lx-pos])) lx-pos; if (lx-src[lx-pos] . isdigit((unsigned char)lx-src[lx-pos 1])) { lx-pos; while (isdigit((unsigned char)lx-src[lx-pos])) lx-pos; } return make_number(lx, start, lx-pos - start); } /* 5. 双字符运算符贪心先看两位再退回一位 */ if (c || c || c || c !) { if (peek(lx, 1) ) { lx-pos 2; return make_op2(lx, c, ); } lx-pos 1; return make_op1(lx, c); } if ((c peek(lx, 1) ) || (c - peek(lx, 1) -)) { lx-pos 2; return make_op2(lx, c, c); } /* 6. 单字符运算符与界符 */ lx-pos; return make_single(lx, c); } return make_token_eof(lx); }这段代码有三个地方值得单独拎出来看。第一是行号维护\n分支必须放在跳过空白之前否则行号永远不涨语义阶段报“变量未声明”时定位全错。第二是数字里的小数点判断1.这种写法在 C 里不合法但在很多实验用的简化语言里要当整数1加一个界符.处理所以必须往后多看一位确认不确认就会把1..10这种输入吃成1.加.10然后语法分析报一堆莫名其妙的错。第三是peek(lx, 1)在文件末尾的越界问题稳妥做法是让源文件缓冲区末尾多留两个\0或者让peek内部先判pos n len。关键字识别不要写成一长串strcmp。常见做法是维护一张静态表用首字母做一次粗筛再逐个比较或者更省事的办法是在哈希桶里同时放标识符和关键字查到了就返回对应 Token 类型。几十个关键字的小语言线性比较也够快但把len先比一遍能省掉大部分strcmp调用。col字段很多人不写觉得有行号就够。真调起来会发现同一行里有三个报错只告诉你第 7 行你还是得自己数。加上列号报错信息直接指到字符改起来省事得多。3.2 正则到 DFA子集构造与最小化的另一条路线实验包里通常会有一关单独做“正则表达式到 DFA”的转换和手写词法器并列用来对照。这条路线的流程是固定的正则表达式先加显式连接符和括号转成后缀表达式用 Thompson 构造法建成 NFA再用子集构造法确定化成 DFA最后做最小化。真正写起来子集构造那一步的closure和move是两个必须写对的函数。# tools/subset.py子集构造的核心两个操作演示用 Python 更直观 def epsilon_closure(states, nfa): 从状态集合出发沿 ε 边能到达的所有状态注意用栈而不是递归 stack, closure list(states), set(states) while stack: s stack.pop() for ch, t in nfa[s]: # nfa[s] 是 (字符, 目标状态) 列表 if ch is None and t not in closure: # None 表示 ε 边 closure.add(t) stack.append(t) return frozenset(closure) def move(states, ch, nfa): 吃掉一个字符 ch 之后能到达的状态集合不含 ε 扩展 return frozenset(t for s in states for c, t in nfa[s] if c ch) def subset_construction(nfa, start, alphabet): dfa_start epsilon_closure({start}, nfa) dfa, queue, seen {}, [dfa_start], {dfa_start} while queue: cur queue.pop(0) for ch in alphabet: nxt epsilon_closure(move(cur, ch, nfa), nfa) if not nxt: # 空集不建状态直接记死状态 continue dfa.setdefault(cur, {})[ch] nxt if nxt not in seen: seen.add(nxt) queue.append(nxt) return dfaepsilon_closure用显式栈而不是递归是因为 NFA 状态数虽小但 ε 环在错误构造下可能出现递归会直接栈溢出。move返回空集时不要新建 DFA 状态直接当死状态处理——很多实现给死状态也分配一个编号结果最小化时多出一堆无用的等价类。最小化用 Hopcroft 划分法先把状态分成“接受态”和“非接受态”两组再按每个字符上的转移落在哪一组不断细分直到划分不再变化。实验用的字母表通常只有几十个字符暴力按字符扫描分组完全够用不需要真的去实现带分裂队列的优化版本。这条路线和手写词法器最大的区别在于手写版能处理/* */这种非正则的嵌套结构吗其实块注释不是正则语言但因为它不允许嵌套所以仍是正则的一旦要求支持嵌套注释就必须在手写状态机里加一个计数器。这个细节在实验报告里写上一句往往能加分。3.3 递归下降先消左递归再谈语法树递归下降的代码结构几乎是一比一照着文法抄的每个非终结符一个函数。但有个前提文法里不能有左递归也不能有需要回溯的公共前缀否则递归下降要么爆栈要么回溯到天荒地老。E - E T | T这种写法直接照抄程序第一次调用parse_E就会无限递归下去血泪经验是拿到文法第一件事就是检查每条产生式的第一个符号是不是它自己。/* src/parser_rd.cE - E T | T 消除左递归后写成循环 */ Ast *parse_E(Parser *p) { Ast *left parse_T(p); /* 先拿到第一个 T */ while (check(p, TK_PLUS) || check(p, TK_MINUS)) { Token op advance(p); /* 吃掉运算符 */ Ast *right parse_T(p); /* 再拿一个 T右结合的部分递归 */ left ast_binop(op.type, left, right, op.line); } return left; /* 循环结束说明后面没有 /-返回整棵子树 */ } /* T - T * F | T / F | F同样改写成循环 */ Ast *parse_T(Parser *p) { Ast *left parse_F(p); while (check(p, TK_STAR) || check(p, TK_SLASH)) { Token op advance(p); Ast *right parse_F(p); left ast_binop(op.type, left, right, op.line); } return left; }左递归消除的标准变换是把E - E T | T变成E - T E、E - T E | ε但落到代码上E这个非终结符没必要真的单独写一个函数用一个while循环吸收掉即可效果完全等价而且省掉一层函数调用的开销和一层 ε 判断。这是递归下降里最实用的一条经验凡是形如“左递归 单个后缀”的产生式都可以直接折叠成循环。parse_F处理括号和一元负号时要注意优先级。-a * b在多数语言里等价于(-a) * b而不是-(a * b)所以一元负号应该在parse_F里处理直接构造成ast_unary(NEG, parse_F(p))而不是在parse_E层面处理。语法树的节点结构建议用“类型 定长子节点数组”而不是“左孩子右兄弟”实验规模的表达式深度撑死几十层定长数组更好写也好打印。打印函数写成括号前缀形式( (* a b) c)这种一行输出就能看出结构对不对比在调试器里展开指针快十倍。3.4 SLR(1) 分析表驱动ACTION/GOTO 表怎么用起来SLR 这一关的难点不在驱动循环在于把分析表构造出来。流程是给文法增广求所有非终结符的 FIRST 和 FOLLOW 集构造 LR(0) 项目集规范族然后对每个项目集移进项目填 ACTION 的 shift归约项目按 FOLLOW 集填 reduce接受项目填 acceptGOTO 表则按项目集的转移填。表建好之后驱动循环其实很短。/* src/parser_lr.c分析表驱动状态栈与符号栈同步压弹 */ int lr_parse(LRTable *t, Token *input, int n) { int state_stack[256], sp 0, ip 0; state_stack[sp] 0; /* 0 号状态是初始状态 */ while (1) { int s state_stack[sp]; int a terminal_index(input[ip].type); /* EOF 也要占一个终结符位 */ Action act t-action[s][a]; if (act.kind ACT_SHIFT) { state_stack[sp] act.target; /* 移进状态入栈输入指针后移 */ ip; } else if (act.kind ACT_REDUCE) { Rule *r t-rules[act.target]; sp - r-rhs_len; /* 按产生式右部长度弹栈 */ int g t-gotos[state_stack[sp]][r-lhs]; if (g 0) return syntax_error(input[ip], goto 表缺失); state_stack[sp] g; /* 归约后按 GOTO 压新状态 */ } else if (act.kind ACT_ACCEPT) { return 1; /* 接受 */ } else { return syntax_error(input[ip], unexpected token); } } }terminal_index这个函数看着不起眼但它决定了表的列顺序。常见的坑是词法阶段返回的 Token 类型有几十种而文法里只用到其中一部分两边索引对不上表查出来的动作就全错位了。稳妥做法是写一个显式的映射数组长度等于 Token 类型总数用不到的填-1查表时先判断再访问。SLR 出现冲突是常态不是 bug。if (E) S else S这种悬挂 else 文法天生就有移进-归约冲突表达式文法如果不分层写E - E E | E * E也会冲突一片。解决办法有两个方向一是改文法把优先级编码进非终结符层次里E/T/F三层写法就是为了这个二是保留冲突用优先级和结合性规则手工指定移进优先还是归约优先。实验里更推荐第一种因为改完文法后 SLR 表和递归下降的结果能对上方便互相验证。验证方法很直接拿同一份测试输入分别跑递归下降和 SLR比较两者的接受/拒绝结果。如果递归下降接受而 SLR 拒绝多半是 FOLLOW 集算错了导致该归约的地方没归约如果两边都接受但归约序列不一样那可能是文法有二义性得回去检查。4. 语义分析与中间代码生成符号表、类型检查与四元式回填前端两关跑通只是知道了“这句话语法合法”还不知道“这句话有没有意义”。int a; a hello;语法上完全合法语义上是错的。语义分析这一关要干三件事建符号表、检查类型、报告未声明和重复定义。中间代码生成则要把树形结构摊平成线性的四元式序列难点全在控制流的跳转目标上——布尔表达式的短路求值、if/else的分支汇合、while的循环回边这些跳转目标在生成当下根本不知道必须靠回填。4.1 符号表作用域链 哈希桶的最小实现符号表要考虑作用域。全局变量和函数里的局部变量可以同名内层块又能遮蔽外层所以结构上必须是一条链每进入一个{}就压一个新的作用域退出就弹掉。查找时从当前作用域往外走找到第一个匹配就停这就是最内层优先的遮蔽规则。/* include/symtab.h作用域链 哈希桶 */ #define BUCKET_SIZE 211 /* 取个质数减少哈希冲突 */ typedef struct Sym { char name[64]; Type type; int offset; /* 相对 fp 的偏移目标代码生成时才填 */ int defined; /* 0 表示只声明未定义用于查重复定义 */ struct Sym *next; /* 同一个桶里的下一个符号 */ } Sym; typedef struct Scope { Sym *bucket[BUCKET_SIZE]; struct Scope *parent; } Scope; /* 在当前作用域插入返回 NULL 表示同名重复定义 */ Sym *scope_insert(Scope *sc, const char *name, Type ty) { unsigned h hash(name) % BUCKET_SIZE; for (Sym *s sc-bucket[h]; s; s s-next) if (strcmp(s-name, name) 0) return NULL; Sym *s calloc(1, sizeof(Sym)); strncpy(s-name, name, sizeof(s-name) - 1); s-type ty; s-next sc-bucket[h]; sc-bucket[h] s; return s; } /* 从当前作用域往外找 */ Sym *scope_lookup(Scope *sc, const char *name) { unsigned h hash(name) % BUCKET_SIZE; for (; sc; sc sc-parent) for (Sym *s sc-bucket[h]; s; s s-next) if (strcmp(s-name, name) 0) return s; return NULL; }插入时只查当前作用域的桶不往外查这样才能允许内层同名遮蔽查找时才沿parent链一路往外。defined标志位是为了区分int a;和int a 1;前者只声明后者才定义两次声明不算错两次定义才算。offset字段在语义阶段留空等目标代码生成时按类型大小顺序分配符号表本身不关心布局。哈希函数用最朴素的h h * 31 c就行几十个变量的实验规模冲突率可以忽略。桶大小取质数是为了让%出来的分布更均匀取 128 这种 2 的幂反而容易在名字长度相似时扎堆。4.2 语义动作挂哪里类型检查与隐式转换语义动作的挂载位置有两种流派一种是边解析边做递归下降的函数里直接调check和emit另一种是先建完整语法树再单独遍历一遍。实验规模下两种都行但边解析边做省一次遍历而且报错时手上的line信息更准确缺点是解析函数会变得很脏语法和语义搅在一起。真要二开建议先建树再遍历结构清晰得多。/* src/sema.c二元运算的类型检查返回结果类型出错返回 TY_ERROR */ Type check_binop(int op, Type l, Type r, int line) { if (l TY_ERROR || r TY_ERROR) return TY_ERROR; /* 错误已报过别重复报 */ switch (op) { case OP_ADD: case OP_SUB: case OP_MUL: if (l TY_INT r TY_INT) return TY_INT; if (l TY_FLOAT r TY_FLOAT) return TY_FLOAT; if (l TY_INT r TY_FLOAT) return TY_FLOAT; /* 隐式提升 */ if (l TY_FLOAT r TY_INT) return TY_FLOAT; error_at(line, 类型不匹配%s %s %s, type_name(l), op_name(op), type_name(r)); return TY_ERROR; case OP_DIV: if (r TY_INT) return TY_INT; /* 整数除法需注意除零 */ if (r TY_FLOAT) return l; /* 浮点除法结果随左操作数 */ error_at(line, 除数类型不合法); return TY_ERROR; case OP_LT: case OP_GT: case OP_EQ: if (l ! r !(is_numeric(l) is_numeric(r))) { error_at(line, 比较运算两边类型不可比); return TY_ERROR; } return TY_BOOL; /* 比较结果一定是布尔 */ } return TY_ERROR; }这段代码有两个细节值得注意。第一是错误传播TY_ERROR一旦出现就往上冒泡不要在每个调用点重复报错否则一个类型错误能刷出十几条重复信息把真正的第一个错误埋掉。第二是隐式转换的方向int和float混合运算统一提升到float这在生成四元式时要插一条int2float的转换指令不能只在类型上标一下就算了否则后面算出来的机器码是错的。数组和指针的类型检查更麻烦a[i]要检查a是数组且i是整数*p要检查p是指针。实验包的简化语言里这部分通常砍掉了如果要做二次开发这块是第一个能加分的扩展点。4.3 四元式与回填短路求值的跳转链怎么补四元式就是(op, arg1, arg2, result)四元组a b c生成(, b, c, t1)加(, t1, _, a)。麻烦的是控制流if (a b) S里a为假时该跳到哪生成a的四元式的那一刻S的代码还没生成跳转目标根本不知道只能先留个空记下这条指令的位置等目标确定了再回头补上。这就是回填。/* include/quad.h四元式与回填链表 */ typedef struct { char op[8]; char a1[16], a2[16], res[16]; } Quad; typedef struct IntList { /* 待回填的指令位置链表 */ int idx; struct IntList *next; } IntList; int next_quad 0; Quad quads[MAX_QUAD]; /* 生成一条四元式返回它的下标后面回填要用 */ int emit(const char *op, const char *a1, const char *a2, const char *res) { Quad *q quads[next_quad]; snprintf(q-op, sizeof(q-op), %s, op); snprintf(q-a1, sizeof(q-a1), %s, a1 ? a1 : _); snprintf(q-a2, sizeof(q-a2), %s, a2 ? a2 : _); snprintf(q-res, sizeof(q-res), %s, res ? res : _); return next_quad; } /* 把链表里所有位置的目标字段补成 target */ void backpatch(IntList *l, int target) { char buf[16]; snprintf(buf, sizeof(buf), %d, target); for (; l; l l-next) snprintf(quads[l-idx].res, sizeof(quads[l-idx].res), %s, buf); }配合短路求值文法是这么写的E - E1 || M E2 { backpatch(E1.falselist, M.quad); E.truelist merge(E1.truelist, E2.truelist); E.falselist E2.falselist; } M - ε { M.quad next_quad; } /* 记录 || 右边第一条指令的位置 */M这个空产生式看起来多余实际上它是整个回填机制的关键。E1 || E2里如果E1为真整串就为真右边的E2根本不该算所以要跳过E2的代码。跳到哪里跳到E2的第一条指令之后也就是M.quad那个位置。而E1为真时的跳转链是在生成E1的时候就记下来的truelist那时候还不知道目标只能等M出现后回填。少了M你就只能把目标猜成“下一行”一旦E2展开成多条指令整个跳转就偏了而且这种错很难在四元式文本里看出来跑起来才发现少执行了一段。对称处理E1.falselist和E2.falselist合并E1.truelist回填到M.quad。while语句则需要多记一个循环入口的标号循环体结束时生成无条件跳转回入口break语句的跳转链挂在循环外层的下一条指令上。这些规则写清楚了中间代码这一关基本就稳了。5. 避坑与排查五个能让实验卡到凌晨的坑实验代码的 bug 有个共同特征报错信息指向的位置往往不是出错的位置。词法错了会在语法报错语法错了会在语义报错语义错了会在四元式跑飞。所以排查的第一原则是逐关验证输出而不是从最后的报错往前猜。下面这五个坑基本覆盖了大部分实验卡壳的场景。5.1 词法与语法层的三个坑现象输入ab或者1..10词法输出一堆莫名其妙的 Token语法分析直接报 unexpected token。原因没有做最长匹配或者双字符运算符判断顺序写反了。应该切成和但如果先判断单字符就会切成三个1..10如果数字分支不往后多看一位就会把1.当成浮点数吃掉剩下.10变成界符加数字。解决所有多字符 Token 严格按“先看两位、再看一位”的顺序判断数字里的小数点必须往后多看一位确认是数字才吃。写完拿ab、1..10、ab、x--y这四个输入手工验一遍 Token 流比跑任何测试都直观。现象语义阶段报“变量i未声明”但源文件里明明写了int i;。原因词法阶段的Token结构体里没存行号或者存了但\n分支没累加更隐蔽的一种是 Token 之间的空白被跳过时pos前进了而col没跟着变导致后续定位全偏。解决所有前进指针的地方统一走一个advance(lx)函数行号和列号在里面同步更新杜绝手写lx-pos。报错函数只用Token.line和Token.col不再自己算。现象递归下降跑稍微长一点的表达式就段错误栈直接爆掉。原因文法里的左递归没消除parse_E调用parse_Tparse_T又绕回parse_E无限递归。或者文法本身没问题但输入里有语法错误错误恢复没写解析器在某个非终结符上原地打转。解决拿到文法先扫一遍每条产生式右部第一个符号如果等于左部立刻消除左递归改成循环。错误恢复至少要做到“遇到不认识的 Token 就advance一个继续”保证解析器一定往前走不会卡死在原地。5.2 语义与中间代码层的两个坑现象SLR 分析表构造出来一堆冲突程序在某个输入上该归约的时候却移进了最后报错位置莫名其妙。原因FOLLOW 集算错了或者项目集规范族的闭包函数漏了传播。经典错误是closure只做了一层没有递归到不动点导致某些归约项目的展望符不全ACTION 表里该填 reduce 的格子空着。解决把 FIRST 和 FOLLOW 集打印出来和手工算的对一遍closure一定用while循环跑到集合不再变化为止。建表时顺手把每个动作的来源哪条产生式、哪个项目集记下来冲突时能直接看到是哪两条规则在打架比盯着ACTION[s][a]的整数编码强得多。现象四元式生成出来条数对得上但执行顺序不对if (a b)里b明明为假后面的S还是执行了。原因回填的目标位置错了最常见的是M产生式的位置记成了next_quad - 1或者干脆没写M导致||和的短路跳转跳到了错误的行。解决把四元式按行号打印出来每行标上next_quad的下标然后手工在纸上画一遍跳转箭头。凡是res字段里出现非变量名的数字就是跳转目标对照源码逻辑走一遍哪条箭头指向了不该去的地方一眼就能看出来。注意这五个坑里有四个的共同点是“上游输出没验证就往下走”。养成每关跑完先看一眼输出的习惯比事后用调试器追指针省下的时间多得多。6. 二次开发把实验级编译器改成能跑真实子集的玩具编译器实验代码能跑通之后最有价值的动作不是加功能是先把它从“只能演示”变成“能验证”。我一般会做三件事给每一关加一个金标准输出比对脚本把tests/目录下的用例按关卡组织跑完自动 diff把main.c里散落的printf收敛到一个统一的 dump 函数输出格式固定把文法文件真正做成运行时可替换的而不是编译进代码里。这三件事做完后面每改一处都能立刻知道有没有把前面的关卡改坏。改造方向上成本最低、收益最明显的是加类型系统里的数组。符号表加一个elem_type和array_len字段语义检查里给a[i]加一条“左部是数组、下标是整数”的规则四元式生成时把a[i]翻译成([], i, _, t)取址再加偏移。改动集中在symtab.h、sema.c、quad.c三个文件两三百行能收住。其次是常量折叠在语义遍历到二元运算且两边都是字面量时直接算出结果不生成四元式改动只涉及一个函数但能立刻在四元式输出里看到条数下降验证起来很爽。改造点需要改的文件验证方式数组与下标symtab.h、sema.c、quad.c用int a[10]; a[3] 1;看四元式是否生成取址常量折叠sema.c的二元运算分支对比12*3折叠前后四元式条数目标代码生成新增codegen.c、quad.h加标号字段用栈式虚拟机跑四元式比对运行结果错误恢复parser_rd.c各同步点故意写错一行看能否继续报出后续错误验证方法我吃过亏。最早是改完直接拿一个大例子跑跑通了就认为没问题结果三周后回头发现中间代码里的跳转偏移全错了一位之前那个例子恰好没走到那条分支。后来改成小步验证每加一个特性先在tests/sema/里加一个最小用例只覆盖这一条规则跑通了再加第二个用例。用例小到只有三五行代码出问题时一眼能定位到是哪条规则写错了而不是在一百行输出里捞针。从那以后我每次动语义或回填相关的代码都强制先把最小用例跑一遍再碰大例子这个习惯救过我不少次。希望帮到你。本文还有配套的精品资源点击获取
