NUAA编译原理实验全解析：从词法分析到三地址码避坑指南

简介面向NUAA南航计算机科学与技术、物联网工程专业的编译原理课程实验包聚焦词法分析与语法分析两大核心模块配套C源码与可执行程序适合正在学习编译原理、需要实现编译器前端的本科学生。包内共7个文件压缩包仅1.01MB含2个cpp源文件、2个exe程序和3个txt测试文件源码、可运行程序与测试用例齐全便于对照学习。已有602人浏览学习可作为相关专业实验课的实用参考。通过本实验包可直观理解词法分析器如何用正则表达式和状态机切分字符流为标记以及语法分析器如何依据上下文无关文法生成抽象语法树。测试样例覆盖非法字符、未匹配括号等异常情形有助于掌握错误检测与恢复思路并显著缩短实验搭建时间。1. 拿到“NUAA南航 编译原理实验.zip”之后先搞清楚这个包里到底在考什么下载完“NUAA南航 计算机科学与技术专业/物联网工程专业 编译原理实验.zip”大多数人的第一反应是解压、打开工程、点编译然后被满屏报错糊脸。这很正常因为这个 zip 并不是一个“点击就能运行”的代码包而是一台小型编译器的骨架工程——从源代码字符串变成 Token 流从 Token 流变成语法树再往下走中间代码每一步都要你亲手补齐。不管你是计算机科学与技术还是物联网工程专业这个实验的共同目标只有一个让你亲手证明编译器不是玄学而是一条环环相扣的流水线。适合谁来看这类笔记两类人一类是还没动手、想先知道这包东西水有多深的新手另一类是已经跑通但感觉分数不高的同学想摸清边界和扣分点。2. 词法分析实验从字符流到 Token 流手写状态机还是正则库2.1 实验包里的词法器通常长什么样大多数编译原理实验的第一关都长得差不多要求识别关键字、标识符、整数、浮点数、运算符和界符把输入的源代码文本切成一个接一个 Token。实验包不同给出的骨架也不同。有的包已经给你定义好了 Token 枚举类型和主循环只让你填状态转换逻辑有的直接给个空目录只留一句“实现词法分析器”。第二种才是真实世界里最常见的形态也是最容易让新手懵掉的地方。这里要分清两条路线。一条是手工构造状态转换图用fgetc逐字符读取同时维护“当前状态”和“当前字符”遇到边界字符就回退另一条是直接调正则库甚至flex生成。很多同学会把第二条当成捷径但实验的埋点往往就在这用正则库能跑出结果可报告里“状态转换图”“DFA 最小化”“最长匹配”这些词一句都写不出来答辩时教授只要问一句“你这个等价状态为什么合并”当场就尬住。所以我一般建议手写状态机生成器可以当作对照工具但不要当成答案本身。词法分析的核心是把字符流切成“不可再分”的单词符号。要理解这个词法实验的边界先抓住三个原则最长匹配、回退、错误恢复。这三个原则没想清楚后面语法分析做得再花哨输入一个带空格的换行注释就能让整个程序翻车。2.2 用 C 写一个能跑的最小词法器下面这个 C 代码是一个最小可运行的词法器能识别关键字、标识符、整数、括号、赋值号和加减乘除。代码刻意没有用任何正则库纯粹用状态机的方式逐字符推进。#include stdio.h #include string.h #include ctype.h enum TokenType { T_NUM, T_ID, T_KW, T_OP, T_LP, T_RP, T_ASSIGN, T_EOF, T_ERROR }; static const char* keywords[] {if, else, while, return, int}; struct Token { int type; char text[64]; }; static struct Token token; void next_token(FILE* fp) { int c fgetc(fp); /* 跳过空白字符空格、制表符、换行 */ while (isspace(c)) c fgetc(fp); if (c EOF) { token.type T_EOF; token.text[0] 0; return; } /* 标识符/关键字字母或下划线开头后跟字母数字下划线 */ if (isalpha(c) || c _) { int n 0; while (isalnum(c) || c _) { if (n 63) token.text[n] (char)c; c fgetc(fp); } ungetc(c, fp); /* 回退一个字符保证最长匹配 */ token.text[n] 0; token.type T_ID; for (int i 0; i 5; i) { if (strcmp(token.text, keywords[i]) 0) { token.type T_KW; /* 命中关键字表则改为 T_KW */ break; } } return; } /* 整数常量连续数字 */ if (isdigit(c)) { int n 0; while (isdigit(c) n 63) { token.text[n] (char)c; c fgetc(fp); } ungetc(c, fp); token.text[n] 0; token.type T_NUM; return; } /* 运算符和界符 */ token.text[0] (char)c; token.text[1] 0; switch (c) { case (: token.type T_LP; break; case ): token.type T_RP; break; case : token.type T_ASSIGN; break; case : case -: case *: case /: token.type T_OP; break; default: token.type T_ERROR; break; } } int main(int argc, char** argv) { FILE* fp fopen(argc 1 ? argv[1] : demo.c, r); if (!fp) { perror(open); return 1; } do { next_token(fp); printf(%2d %s\n, token.type, token.text); } while (token.type ! T_EOF); fclose(fp); return 0; }这段代码的逻辑可以拆成四块看。第一块是空白跳过编译器的词法器必须能容忍任意位置的换行和缩进。第二块是标识符识别从字母或下划线开始贪心地往后读字母和数字直到读到一个不属于标识符的字符再用ungetc把这个字符退回输入流。这个“回退”动作就是最长匹配的实现基础。第三块是数字识别逻辑和标识符一样。第四块是单字符运算符和界符用switch完成之后扩展、!这类双字符运算符时只需要在分支里多读一个字符判断即可。参数上最值得注意的是token.text的长度。我写死 64 字节但真实实验要求可能会遇到 128 字节甚至更长的标识符如果缓冲区满就停止读取会截断 Token后续语法分析根本对不上。我一般把它改成动态分配的缓冲区或者直接定义成 256避免边界输入把程序搞崩。另外注意这个示例没有处理浮点数的小数点和科学计数法实验要求里有浮点数的同学需要在这里继续加状态而不是靠atof去擦屁股。2.3 三个必调参数最长匹配、错误恢复、符号表管理词法器真正的实验价值不在“匹配成功”的路径而在“匹配失败”的边界。第一个必调参数是“长度上限”。常见做法是哪里的扫描循环都加一个长度判断防止超长标识符打爆缓冲区。第二个必调参数是“错误恢复策略”当输入出现、#这类非法字符时正确的做法是输出一条带行号列号的错误信息然后把当前字符丢弃继续扫描下一个字符而不是直接exit(1)。因为有经验的验收者会专门扔一个带非法字符的测试文件给你期望看到的是“编译器还能坚持报完所有错”而不是“崩在第 3 行”。第三个参数是符号表管理。词法阶段的符号表不需要做作用域嵌套只需要登记见过的标识符给每个标识符分配一个内部编号。这样语法分析阶段可以直接用编号代替字符串比较省掉大量时间。struct Symbol { char name[64]; int id; struct Symbol* next; }; static struct Symbol* symtab NULL; static int next_id 1; int lookup_or_insert(const char* name) { for (struct Symbol* s symtab; s; s s-next) { if (strcmp(s-name, name) 0) return s-id; } struct Symbol* s malloc(sizeof(struct Symbol)); strcpy(s-name, name); s-id next_id; s-next symtab; symtab s; return s-id; }这段代码用头插法维护链表查找时从头往后扫。对课程实验来说符号表条目数量不会超过几千链表足够但如果你后续想做中间代码优化O(n)的查找会让编译速度变得不可接受那时候再换哈希表不迟。这里要强调一个常见误用符号表不是“越复杂越好”——在词法实验阶段用哈希表报告里却写不清装载因子和冲突处理策略反而会被追问到后悔。先用链表把语义跑通比什么花活都实在。3. 语法分析实验递归下降与 LL(1)选型决定你熬夜的量3.1 左递归为什么教科书里的文法不能直接抄进代码语法分析是编译原理实验几个阶段里翻车率最高的一关。最典型的问题出现在表达式文法上。教科书上写的是经典四则运算文法E - E T | E - T | T T - T * F | T / F | F F - ( E ) | num这个文法人看没问题但直接照搬进递归下降马上遇到灾难E的第一条产生式右部自己还是E于是expr()函数一进来就调expr()没有任何终结符作为入口栈直接被自己塞爆程序秒崩。这就是左递归。递归下降只能处理从左向右扫描、自上而下推导的 LL 文法自带左递归的产生式必须改写。消除左递归的标准做法是引入一个新非终结符把左递归变成右递归。上面文法的等价变换是E - T E E - T E | - T E | ε T - F T T - * F T | / F T | ε F - ( E ) | num这里有同学会问右递归文法不是破坏了左结合性吗答案是语法树层面确实偏好右结合但你在语义动作里可以用循环累加、先算左边再算右边的方式把结合性修正回来。也就是语法分析阶段“接收”右递归树语义分析阶段“纠正”运算顺序这是课程实践里最常见、最稳妥的做法。3.2 递归下降分析器的最小骨架下面是一份极简递归下降代码它假设上一章词法器已经把运算符拆成不同 Token 类型并提供cur_type和cur_text两个全局变量。这份代码的重点在于展示怎么用函数调用关系表达文法产生式。int cur_type; /* 当前 Token 类型 */ char cur_text[64]; /* 当前 Token 文本 */ void advance(void) { next_token(stdin); } void error(const char* msg) { fprintf(stderr, syntax error: %s\n, msg); } void expect(int t) { if (cur_type ! t) error(unexpected token); advance(); } double expr(void) { double left term(); while (cur_type T_PLUS || cur_type T_MINUS) { int op cur_type; advance(); double right term(); if (op T_PLUS) left right; else left - right; } return left; } double term(void) { double left factor(); while (cur_type T_MUL || cur_type T_DIV) { int op cur_type; advance(); double right factor(); if (op T_MUL) left * right; else left / right; } return left; } double factor(void) { if (cur_type T_NUM) { double v atof(cur_text); advance(); return v; } else if (cur_type T_LP) { advance(); double v expr(); expect(T_RP); return v; } error(factor expected); return 0; }逻辑说明要盯住两点。第一expr()里的while循环替代了右递归文法中的E它先解析左操作数每读到一个或-就再解析一个右操作数并立即计算。这种“循环 左操作数累积”的模式就是修正结合性的关键不会掉进右递归的坑里。第二advance()统一负责向前移动 Token所有出错的地方都集中在error()处打印信息而不是到处printf。参数上唯一需要调的是“出错后是否要继续”。做课程实验时我推荐error()里只打印、不退出把语法错误攒着一起报因为这个行为很接近真实编译器的“恐慌模式”错误恢复。但要注意循环会带来死循环风险——如果出错位置没有推进 Tokenwhile会卡死在原地。所以写error()时要么同时advance()跳过当前 Token要么在错误计数超过上限时强制结束二选一。3.3 LL(1) 与 LR(1)手写还是上生成器边界在哪递归下降本质上是个“手写 LL(1)”。它要求文法满足 LL(1) 条件对每个非终结符任意两个产生式的 First 集不相交如果有空产生式还要保证 First 集和 Follow 集不相交。教课书会花大篇幅教你怎么算 First 和 Follow实践里的作用很简单——算完你就知道这个文法能不能用递归下降写。举一个真实的冲突例子。如果把if语句写成S - if ( E ) S | if ( E ) S else S | other两个产生式的前缀都是if ( E ) SLL(1) 没法区分该选哪一个。这个现象叫“悬空 else”。C 语言的做法是 bind 到最近的else递归下降里也这么处理——解析到else时不匹配也不算错直接当作内部 if 的后续分支吃掉。这正是 LL(1) 冲突的一种人工化解法。另一条路是走 LR(1) 或 LALR(1)用生成器自动构造分析表。常见工具是 Bison/Yacc甚至可以直接写成这样%token NUMBER PLUS MINUS MUL DIV LP RP %left PLUS MINUS %left MUL DIV %% expr : expr PLUS expr { $$ $1 $3; } | expr MINUS expr { $$ $1 - $3; } | expr MUL expr { $$ $1 * $3; } | expr DIV expr { $$ $1 / $3; } | LP expr RP { $$ $2; } | NUMBER { $$ $1; } ; %%这个文法保留了左递归但 LR 系列分析器正好能处理左递归不需要人工消除。%left声明则直接告诉 Bison 运算符的结合性和优先级由它自动解决冲突。但生成器不是万能后悔药。它的问题在于一旦文法里有二义性Bison 会输出几百行冲突报告新手根本看不懂.output文件里的状态转移表只能瞎调优先级。而且课程答辩现场常会问“你这个语法树怎么画出来的”用生成器的人容易答不上来。我给的建议是如果实验包允许自由选型那就手写递归下降为主Bison 当作验证工具——把同一个测试用例喂给两份实现输出结果一致手写版就基本稳了。直接拿生成器交差省下的时间会在答辩环节连本带利还回来。4. 语义分析与中间代码实验三地址码是交差还是加分4.1 语法制导翻译把动作挂在语法规则的节点上语义分析这一关很多人误以为要把前一章的代码全部推翻重写。不是这样的。最常见的做法是在语法分析的同时做“语法制导翻译”也就是在递归下降的每个规约点上插入“语义动作”一边分析一边生成中间代码。三地址码是课程里最常见的中间表示每条指令右边最多一个运算符例如t1 a b。为什么选它而不是 AST因为三地址码足够简单内存布局像指令流水线后端的寄存器分配、公共子表达式删除都是拿它做文章实验报告里也方便贴出来逐条解释。赋值语句的翻译规则可以写成一张对照表。我一般这样给同学讲把S - id E翻译成emit(id.place, , E.place)把E - E1 E2翻译成E.place newtemp(); emit(E.place, , E1.place, , E2.place)。这个形式就是“综合属性”在实践里的直接体现——左侧非终结符的属性由右侧子节点计算出来向上一层传递。4.2 三地址码生成的最小实现实现三地址码生成只需要在递归下降骨架上加两个工具一个newtemp()负责生成新临时变量名一个emit()负责输出形如t1 t2 t3的指令。static int temp_no 0; char* newtemp(void) { char* p malloc(16); sprintf(p, t%d, temp_no); return p; } void emit(const char* fmt, ...) { va_list ap; va_start(ap, fmt); vprintf(fmt, ap); va_end(ap); printf(\n); }接下来在factor()和expr()里插入语义动作。比如处理数字常量时把它拉成一个临时变量emit(%s %s, place, cur_text)让上层运算统一操作临时变量而不是直接操作字面量。处理加法时先递归生成左右两个操作数的三地址码再把两个临时变量相加char* gen_expr(void) { if (cur_type T_NUM || cur_type T_ID) { char* p newtemp(); emit(%s %s, p, cur_text); advance(); return p; } char* left gen_term(); while (cur_type T_PLUS || cur_type T_MINUS) { int op cur_type; advance(); char* right gen_term(); char* p newtemp(); emit(%s %s %c %s, p, left, (op T_PLUS) ? : -, right); left p; } return left; }注意这个片段里我故意省略了term()的递归细节因为它和上一章的term()结构一模一样只是把返回值从double换成临时变量名。真正值得理解的是运算符优先级为什么不需要额外处理因为乘法在gen_term()里先被递归解析生成的加法代码永远在乘法指令之后输出自然构成“先乘除后加减”的顺序。这就是语法制导翻译的精妙之处——语法层次决定计算顺序你不需要单独写一个优先级判断。4.3 符号表与类型检查中间代码生成完成之后语义分析还有一个重头戏类型检查。实验要求里常见的是变量未定义检查、类型不匹配检查和赋值兼容性检查。这在实现上并不复杂只需要在符号表里加一个type字段。struct Symbol { char name[64]; int type; /* 0int, 1float, 2char */ int is_const; struct Symbol* next; };遇到赋值语句id E时先lookup(id)查不到就报“undefined variable”查得到就继续检查E的返回类型和id.type是否兼容。整数赋给浮点通常给一个警告而不是硬错误浮点赋给整数则要看实验要求的语言规范很多要求直接判类型错误避免隐式截断的坑。这一章在报告里的呈现方式直接决定它是“交差”还是“加分”。我见过太多人把三地址码样例贴到报告里却不解释临时变量编号从几开始、怎么释放。你只需要加一张“输入输出对照表”左边给一段五行的if语句源码右边给生成的十几条三地址码再用两三句话说明每个t变量对应源码的哪一段。这一页写清楚答辩时教授顺着你的表提问你就能一直答在点子上而不是被灵感型追问打懵。5. 编译原理实验避坑指南从 zip 伪加密到答辩验收的 5 个血泪经验5.1 解压要密码先查 zip 伪加密现象下载的“编译原理实验.zip”双击解压弹出要密码的窗口压缩包里明明没有附带密码说明。这时候先别急着满世界找密码。原因很可能是 zip 伪加密——压缩包把加密标志位设成了 1但实际上文件内容并没有被真正加密某些解压工具看到标志位就开始要密码。解决用任意十六进制编辑器查看 zip 局部文件头加密标志位通常在文件头偏移 6 字节处占 2 字节。如果它的值为0x0001而旁路数据能直接看到明文源码那就是伪加密。把标志位改成0x0000再保存重新解压就能直接释放。也可以写几行 Python 自动处理import struct import sys with open(sys.argv[1], rb) as f: data bytearray(f.read()) count 0 i 0 while i len(data) - 30: # 查找 PK\x03\x04 局部文件头签名 if data[i:i4] bPK\x03\x04: flags struct.unpack_from(H, data, i 6)[0] if flags 0x01: struct.pack_into(H, data, i 6, flags ~0x01) count 1 i 1 with open(fixed_ sys.argv[1], wb) as f: f.write(data) print(fcleared {count} local headers)注意这脚本只能处理伪加密。如果压缩包是真加密内容已经被密钥打乱清标志位解出来的也是一堆乱码。那种情况别折腾老老实实找实验包发布方要密码。区分真伪加密的方法很简单用十六进制编辑器看PK头后面跟着的文件名的下一段如果是明文的main.c、report.docx说明文件内容没有被真正混淆基本可以断定是伪加密。5.2 Windows 上能跑、Linux 上全崩现象在宿舍用自己的 Windows 笔记本 Visual Studio 把代码跑通了拿到学校 Linux 服务器上一编译报错内容千奇百怪——找不到头文件、stray \357 in program、各种中文乱码。原因无非两个一是代码文件被以 GBK/GB18030 编码保存Linux gcc 默认按 UTF-8 解码二是文件换行符是 CRLF某些旧版 Makefile 脚本会把它带入字符串或预处理器指令。解决代码文件统一转成 UTF-8 无 BOM换行符统一转成 LF再编译。一条dos2unix可以解决换行iconv -f GBK -t UTF-8可以解决编码。如果实验包自带的.vcxproj工程文件只有 Windows 版我一般建议直接抛开 IDE 手写 Makefile结构就三行的事CC gcc CFLAGS -Wall -g -stdc99 all: compiler compiler: main.o lexer.o parser.o $(CC) $(CFLAGS) -o compiler main.o lexer.o parser.o动手早一点做这件事比验收前一晚在机房现改编码靠谱得多。物联网工程的同学更要注意很多嵌入式开发板的交叉编译环境对文件编码同样敏感这个习惯是真能带进工作的。5.3 边界输入直接把程序打崩现象正常的int a 1;能跑但一输入空文件就段错误输入一个只有右括号的)程序直接卡死给一个 200 个字符的超长标识符缓冲区就爆了。这些边界输入在验收时经常被用作“测试用例”目的不是刁难人而是验证你有没有做过错误恢复和资源保护。原因通常是三个fgetc读到 EOF 后没有判空标识符缓冲区定长但扫描循环没有长度上限语法错误后 Token 没有推进导致while不断读同一个 Token 形成死循环。解决词法器里每次fgetc后判断返回值标识符和数字扫描加长度上限error()后强制advance()或做错误计数超过 100 个错误就直接返回。代码写得再漂亮边界一测就原形毕露这比任何理论题目都更能看出工程习惯。5.4 实验报告写成源码注释堆现象报告前半段贴代码后半段还是贴代码中间只有两句“这是词法分析”“这是语法分析”。这种报告看起来工作量巨大其实分数往往垫底——因为编译原理实验的核心不是代码行数而是“设计决策的理由”。解决报告按四块写。第一块给程序总体结构图说明模块边界词法器谁调用谁、语法分析器如何取 Token。第二块写关键数据结构Token 怎么组织、符号表用什么结构、为什么选数组不选链表给出一句话理由。第三块写理论到实现的映射比如把状态转换图贴出来旁边对应标注代码里的哪个函数。第四块放测试用例至少包含正常程序、错误程序、边界输入三类。写完这四块哪怕代码是参考着改的报告也像是你“做了设计”而不是“抄了代码”。5.5 用生成器偷懒却被问进死角现象用 Bison 生成分析器代码量极小运行正常以为稳了。答辩时教授指着.output文件问了一句“你这里为什么有 3 个 shift/reduce 冲突”人直接呆住。这不是个别现象是生成器用户最常见的翻车点。原因是你用了工具但没理解工具帮你消解了什么。Bison 默认对 shift/reduce 冲突选择移进对特定文法再配%left优先级声明这背后的规则是教材里“移进-归约冲突”那一整节。解决如果你决定用生成器至少把 Bison 的.output文件打开找到冲突状态用一页报告写清冲突发生在哪个产生式、为什么靠%left能消解。如果你连这一步都不想写那就老老实实手写递归下降——手写的版本虽然代码量大但每一行都能讲出道理答辩时反而从容得多。6. 让实验包产生额外价值搭一套验证编译器行为的测试脚本实验代码写到这里功能上已经满足“能跑”但我建议再往前一步给编译器加一个调试开关输出各阶段的中间产物。这能让你的实验包从“交差”变成“一套可验收的编译器工具链”。做法很简单。给编译器认两个命令行参数-l表示只做词法分析并打印 Token 流-t表示做完语法分析后打印三地址码。同时在主函数里加一个全局的debug选项根据参数决定在哪里停。然后写一个测试脚本把测试用例批量喂进去比对输出。#!/bin/bash # 编译实验测试脚本tests 内存测试源码expected 内存期望输出 tests_dirtests out_dirout mkdir -p $out_dir for f in $tests_dir/*.c; do name$(basename $f .c) ./compiler -l $f $out_dir/$name.tokens 21 ./compiler -t $f $out_dir/$name.ir 21 if diff -q expected/$name.tokens $out_dir/$name.tokens /dev/null \ diff -q expected/$name.ir $out_dir/$name.ir /dev/null; then echo PASS: $name else echo FAIL: $name diff expected/$name.tokens $out_dir/$name.tokens diff expected/$name.ir $out_dir/$name.ir fi done这个脚本一眼就能看懂对每个.c测试文件先跑-l得到 Token 流再跑-t得到三地址码然后和目录下的期望输出做比对。为什么要做这一步因为很多编译错误是“中间某个结构错了但最终结果碰巧对”有了这个脚本每一次改动代码后再跑一遍能立刻知道破坏了哪个阶段的输出。最后补一句专门给物联网工程背景同学的话。这个专业做嵌入式、搞单片机的时候编译器对你是个黑匣子做完这套实验后你至少能读懂报错信息背后是哪一层出的问题这种“从黑匣子里往外看”的能力是编译原理实验带走的真正手艺。我自己的惯例是每个编译实验的第一版代码就带上-l调试开关从 Token 流一路打到三地址码宁可前期多花半天也不愿最后拿肉眼查几十条输出。做编译原理实验少熬夜的正道不是找答案是让自己每一步改动都能被看见。希望帮到你。本文还有配套的精品资源点击获取