简介一份编译原理课程设计完整资料涵盖C源程序压缩与解压、自动机、文法问题处理器、TINY扩充语言语法树生成等典型任务适合计算机、人工智能、通信工程等专业的学生用于课程设计、毕业设计或项目初期演示也适合有一定基础者在此基础上二次开发。压缩包共272个文件约72.55MB核心包括52个cpp源文件、23个h头文件、31个txt说明文档、18个pdf资料、10个docx实验报告、11个tny语法测试用例、11个exe可执行程序以及dll运行库和png截图等源码、文档、报告、可执行程序全部齐备目录结构清晰便于按需查阅。目前已有144人学习下载。作者在项目备注中说明代码均测试运行成功设计完成后才打包上传答辩评审平均分达到96分同时提供实验报告、文档说明和可执行文件遇到运行问题还可私聊咨询并远程教学对初学编译原理、需要参考完整作业流程的读者很有帮助。1. 把压缩解压、自动机、文法问题处理器、TINY语法树生成串成一条流水线每年编译原理实验交作业前总有人对着这份题目发愁C源程序的压缩和解压不是数据结构题吗自动机和文法问题处理器为什么单独列出来TINY扩充语言的语法树生成到底要交到什么程度我按一次课程设计的经验说这四个东西不是四个独立题目而是一条流水线——压缩解压负责把源码无损地送进内存自动机负责把字符流切成token文法问题处理器负责在递归下降之前把左递归和公共前缀清干净最后语法树生成把token流变成能打印的AST。适合要交实验报告和答辩的学生也适合想用TINY把词法、语法链路整体跑通的人。我的建议是先定接口再写实现后面至少少改三次。2. 先定模块边界再写代码四个模块的接口与数据流2.1 压缩解压为什么会在编译原理作业里很多人的第一反应是编译原理作业搞压缩干什么代码压缩不是数据结构的题吗这个要看题目出处。部分编译原理实验手册会把“源程序压缩存储”作为词法分析的前置扩展题要求你把一个C源文件先压成一包字节需要分析时再无损解压回来。表面考的是字符统计、变长编码和文件读写实际上考的是自动机——哈夫曼树的构造过程本身就是一种确定型编码和你后面写词法分析器用的DFA是同一套思维。常见做法是读入C源文件按字节统计频率构建哈夫曼树输出压缩后的二进制文件解压时先读回树结构还原出原始文本再交给后续模块。这一来一回必须完全无损空格、换行、注释一个都不能少因为词法分析器要靠空白字符分词注释也可能影响行号统计。换句话说压缩模块的验收标准只有一个解压出来的字节流和原文件完全一致。2.2 四条接口和一条main线我习惯先把模块间接口定死再各自实现。这样四个人做同一个大作业也不会互相等。// huffman.h 阶段1压缩与解压 int compressFile(const std::string inPath, const std::string outPath); std::string decompressFile(const std::string cmpPath); // lexer.h 阶段2自动机驱动的词法分析 std::vectorToken tokenize(const std::string srcText); // grammar.h 阶段3文法问题处理消除左递归/提取左因子 GrammarTable prepareGrammar(const Grammar g); // ast.h 阶段4TINY扩充语言语法树生成与打印 ASTNode* parse(const std::vectorToken tokens, const GrammarTable table); void printAST(const ASTNode* node, int depth);这套接口的意图很明确compressFile产出二进制文件decompressFile把文件还原成字符串tokenize只吃字符串不碰文件语法树生成只吃token流不关心源码怎么来的。每个模块之间只有一条数据通路出问题时按链路定位就行。main函数里把整条流水线穿起来只需要六行int main(int argc, char** argv) { compressFile(argv[1], out.cmp); // 1. 压缩 auto src decompressFile(out.cmp); // 2. 解压 auto tokens tokenize(src); // 3. 自动机切token auto table prepareGrammar(tinyGrammar()); // 4. 文法处理 auto root parse(tokens, table); // 5. 语法树生成 printAST(root, 0); // 6. 层级打印 }注意prepareGrammar的输入不是token而是文法定义。TINY文法在代码里单独写一个tinyGrammar()函数返回产生式集合文法处理器先对它做预处理产出的GrammarTable再给parse用。这么做的好处是你如果改文法不需要动词法分析器。2.3 目录结构与构建方式交付时需要“源代码文档说明实验报告可执行”目录从一开始就按这个组织src/ huffman.h huffman.cpp lexer.h lexer.cpp grammar.h grammar.cpp ast.h ast.cpp main.cpp data/ sample.cpp doc/ 实验报告.md构建用一条g命令就够了不需要引入CMakeg -stdc17 main.cpp huffman.cpp lexer.cpp grammar.cpp ast.cpp -o tiny_compiler ./tiny_compiler data/sample.cpp如果你在VS Code里配好了C/C环境和调试器也可以直接在tasks.json里把这条命令写成编译任务F5跑起来看断点。可执行文件就是tiny_compiler把它和sample.cpp、实验报告打成一个包就能交。实验报告里不需要贴全部代码重点是接口截图、AST打印效果图、压缩前后字节数对比这三样。2.4 顺序不能乱的三个原因模块顺序是题目指定好的不能调换背后有实际约束。压缩必须在词法分析之前因为词法分析器需要的是原始文本。有人想“先分词再压缩token流”那压缩率确实更高但题目要求的压缩对象是C源程序的文件内容不是token序列。解压必须直接在内存里出字符串不能解压到磁盘再读文件否则就没达到“压缩存储、按需还原”的目的。文法处理器必须跑在语法树生成之前因为它改的是文法本身——如果直接把带左递归的文法交给递归下降程序第一轮递归就会爆栈。这个顺序也决定了你的调试顺序先单独测压缩解压一致再测tokenize切分正确最后才轮到语法树。每一步的输入输出都是上一模块的产物链路长但好定位。3. 用Huffman实现C源程序的压缩与解压核心代码与两个必调参数3.1 为什么选Huffman而不是RLE或LZ77C源码的字节分布很典型小写字母、空格、换行、大括号、分号出现频率极高数字和生僻符号很少。对这种分布变长编码能压掉30%到40%而RLE只对连续重复数据有效比如位图C源码里很少有连续重复的字符LZ77/LZW效果好但实现量至少翻倍写进实验报告很难讲清楚。Huffman是最匹配课程设计定位的算法——原理好讲、代码量可控、能体现自动机思想。STL里的priority_queue可以直接当最小堆用这也是为什么用C写这个模块最顺手堆、编码表、位运算都有现成支撑不用自己造数据结构。算法压缩率实现成本适合C源码RLE低极低否Huffman中中是LZ77/LZW高高是但不划算3.2 构建哈夫曼树统计、建堆、合并、生成编码表#include queue #include vector #include unordered_map #include functional struct HuffNode { unsigned char ch; // 只在叶子节点有效 long long freq; HuffNode *left, *right; HuffNode(unsigned char c, long long f) : ch(c), freq(f), left(nullptr), right(nullptr) {} }; struct NodeCmp { bool operator()(HuffNode* a, HuffNode* b) const { return a-freq b-freq; // 小顶堆 } }; void buildHuffman(const std::string text, std::unordered_mapunsigned char, std::string codes) { long long freq[256] {0}; for (unsigned char c : text) freq[c]; // 按字节统计 std::priority_queueHuffNode*, std::vectorHuffNode*, NodeCmp pq; for (int i 0; i 256; i) if (freq[i]) pq.push(new HuffNode((unsigned char)i, freq[i])); // 只有一个字符时包一层空根避免生成空编码 if (pq.size() 1) { auto* only pq.top(); pq.pop(); auto* root new HuffNode(0, only-freq); root-left only; pq.push(root); } while (pq.size() 1) { auto* l pq.top(); pq.pop(); auto* r pq.top(); pq.pop(); auto* parent new HuffNode(0, l-freq r-freq); parent-left l; parent-right r; pq.push(parent); } std::functionvoid(HuffNode*, std::string) dfs [](HuffNode* p, std::string s) { if (!p-left !p-right) { codes[p-ch] s; return; } if (p-left) dfs(p-left, s 0); if (p-right) dfs(p-right, s 1); }; dfs(pq.top(), ); }代码逻辑分四步统计256个字节出现次数把出现过的字节建成叶子节点放进优先队列反复弹出频率最小的两个节点合并成新节点再入队直到只剩一棵树从根做DFS向左记0、向右记1到叶子就得到该字节的变长编码。两个关键参数一是freq的类型用long long作业里的测试文件可能只有几十KB但别低估源码文件大了之后int不够用二是叶子节点里的ch声明为unsigned char否则中文注释的UTF-8字节会被当成负数后面当数组下标时会越界。这个坑在后面避坑章还会专门讲。3.3 压缩文件格式让解压端能重建那棵树压缩和解压是成对出现的所以文件格式必须自己定清楚。我用最简单的定长头结构先写256个long long的频率数组再写入数据的字节数和最后一个字节的有效位数最后是压缩位流。bool compressFile(const std::string inPath, const std::string outPath) { std::ifstream in(inPath, std::ios::binary); std::string text((std::istreambuf_iteratorchar(in)), std::istreambuf_iteratorchar()); std::unordered_mapunsigned char, std::string codes; buildHuffman(text, codes); std::ofstream out(outPath, std::ios::binary); long long freq[256] {0}; for (unsigned char c : text) freq[c]; out.write(reinterpret_castchar*(freq), sizeof(freq)); // 文件头 int bitBuf 0, bitCount 0, totalBits 0; for (unsigned char c : text) { for (char b : codes[c]) { bitBuf (bitBuf 1) | (b - 0); if (bitCount 8) { out.put(static_castchar(bitBuf)); bitBuf 0; bitCount 0; } totalBits; } } if (bitCount) out.put(static_castchar(bitBuf (8 - bitCount))); out.write(reinterpret_castchar*(totalBits), sizeof(totalBits)); out.close(); return true; }这里有几个容易写错的地方。第一个是位流拼接用bitBuf按位左移累积满8位就写一个字节最后不足8位时左移补零这个补零的数量由totalBits负责找回。第二个是文件头写的是频率表不是编码表频率表只有256个long long固定2KB简单且可调试代价是文件头偏大但对课程设计完全够用。totalBits这个参数一定要存——它是最后一个字节里真实数据的位数解压时全靠它截断填充位。3.4 解压实现与边界情况解压是压缩的逆过程读回频率表重新建树然后按位从根节点走走到叶子就输出一个字节。std::string decompressFile(const std::string cmpPath) { std::ifstream in(cmpPath, std::ios::binary); long long freq[256] {0}; in.read(reinterpret_castchar*(freq), sizeof(freq)); // 用freq重建与压缩端完全相同的Huffman树 std::unordered_mapunsigned char, std::string codes; // ... 构造字符串后再buildHuffman或直接重构树 ... int totalBits 0; in.read(reinterpret_castchar*(totalBits), sizeof(totalBits)); std::string out; HuffNode* p root; int consumed 0; char byte; while (in.read(byte, 1) consumed totalBits) { for (int i 7; i 0 consumed totalBits; i--) { p ((byte i) 1) ? p-right : p-left; if (!p-left !p-right) { out.push_back(p-ch); p root; } consumed; } } return out; }边界情况必须处理三种。空文件freq全零pq为空解压时会crash压缩前先判断text.empty()直接返回。只有一种字符的文件buildHuffman里已经包了一层空根不会出现空编码导致死循环。短文件压完比原文还长因为2KB文件头摆在那小文件压缩率是负的——我一般在压缩前判断text.size()小于1KB就直接存原文文件头里写一个标记位区分格式。4. 把自动机落成词法分析器DFA转移表、最长匹配与Token设计4.1 词法规则与字符分类TINY扩充语言的词法规则不算复杂但要把运算符、关键字、标识符、数字分开得先定义字符分类。字符分类是把输入字符映射成类别这样转移表不用对256个ASCII码各做一列只需要对七八个类别做列。类别包含说明Lettera-z A-Z _标识符和关键字的首字符Digit0-9数字字面量Op - * / ( ) ; ,单字符运算符和定界符Rel 可能构成双字符关系运算符Space空格 \t 换行跳过不计入tokenEnd\0输入结束我给DFA设计的状态含义如下状态含义0初态1正在读标识符/关键字2正在读整数3正在读小数4已读到可能是赋值或5已读到可能是或6已读到可能是或状态4、5、6的目的是实现最长匹配读到号时不急着产出再看下一个字符是不是是就组成不是再回退产出单字符。这正是自动机里有别于简单分词的细节。4.2 DFA转移表与驱动循环转移表用二维数组表示行是当前状态列是字符类别值是下一状态-1表示无路可走。// 字符类: 0Letter 1Digit 2Op 3Rel 4Space 5End int nextState[7][6] { { 1, 2, -1, 4, 0, -1}, // 0 初态 { 1, 1, -1, -1, -1, -1}, // 1 标识符 {-1, 2, -1, -1, -1, -1}, // 2 整数 {-1, 3, -1, -1, -1, -1}, // 3 小数 {-1, -1, -1, 7, -1, -1}, // 4 号后面跟则到7 {-1, -1, -1, 8, -1, -1}, // 5 号后面跟则到8 {-1, -1, -1, 9, -1, -1}, // 6 号后面跟则到9 }; // 状态7、8、9为终态行内不需要再转移驱动循环是词法分析器的核心最长匹配就靠“转移失败才回退”实现std::vectorToken tokenize(const std::string src) { std::vectorToken tokens; int state 0, start 0; for (size_t i 0; i src.size(); i) { CharClass cc classify(src[i]); int ns nextState[state][cc]; if (ns ! -1) { state ns; // 能走就走 } else { TokenKind kind finalKind(state, src.substr(start, i - start)); if (kind ! Unknown) tokens.push_back({kind, src.substr(start, i - start), start}); state 0; start i; // 关键点 i--; // 当前字符没被消费重读 } } return tokens; }这个回退逻辑是自动机里最容易写错的地方。遇到转移失败时说明从start到i-1这段已经是一个完整token但当前字符属于下一个token所以要i--让循环重新读它。如果忘了i--会导致当前字符被跳过最典型的就是把“”拆成两个“”。finalKind根据结束状态判断token类型状态1还要查关键字表在关键字表里就是Keyword否则是Identifier状态2和3是Number状态7、8、9分别是、、单字符运算符在classify阶段直接归类处理。4.3 运算符、注释与空白压缩层保留、词法层丢弃运算符这里必须处理多字符组合。C源码和TINY语言里都有、、这种双字符运算符如果词法分析器只按单字符切后续语法树生成就全乱了。我在classify里把、、单独归为Rel并让状态4、5、6读下一个字符这就是转移表里那三行的作用。注释的处理策略要提前定好。压缩解压层必须原样保留注释因为它做的是无损字节复制不知道语义词法分析层读到时直接把//到行尾、/到/的内容丢弃。TINY本身的注释语法是{}扩充后一般会加入C风格注释。丢弃注释时要注意换行符不能丢否则行号全错报错信息定位就不准了。空白字符也一样——词法层跳过空格和\t但遇到\n要计入行号。5. 文法问题处理器常见问题排查左递归死循环与5个必踩的坑5.1 文法问题处理器到底在修什么文法问题处理器的输入是TINY扩充语言的文法定义输出是能让递归下降顺畅工作的LL(1)文法。最常见的两个问题是左递归和公共前缀。左递归就是E - E T | T这种产生式递归下降程序要实现ParseE第一步就调用ParseE直接无限递归。消除直接左递归的标准做法是改写为右递归// 消除直接左递归: A - Aα | β A - βA, A - αA | ε void eliminateLeftRecursion(Grammar g) { for (auto rule : g.rules) { if (rule.rhs.size() 1 rule.rhs[0] rule.lhs) { std::string alpha rule.rhs.substr(1); // α std::string beta /* 收集所有不以A开头的产生式右部 */; // 生成 A - βA // 生成 A - αA | ε } } }提取左因子解决的是FIRST集合冲突A - aB | aC两个产生式都以a开头递归下降没法决定走哪条。改写为A - aAA - B | C。判断文法是否LL(1)也可以自动化对每个非终结符检查任意两个产生式的FIRST集合是否有交集再检查如果有ε产生式FIRST与FOLLOW是否冲突。这三件事做下来文法问题处理器的功能就完整了。5.2 坑1解压后字节对不上多了乱码现象压缩再解压输出的C源码和原文件不一致末尾多了几个不可见字符。原因压缩时最后一个字节不满8位做了左移补零解压端把这些填充位也当成有效编码走树走到了某个叶子甚至可能停在错误节点。解决文件头里必须存totalBits最后一个字节的有效位数解压时走一位就数一位走到totalBits立即停止不再读取后面内容。5.3 坑2a b被切成了a b现象语法树里出现了两个赋值节点表达式的语义完全不对。原因转移表里没有给号后面跟号单独设状态DFA读到第一个时转移成功读到第二个转移失败于是回退产出了“”再把第二个当作新token重读。解决按第4章的方式给、、各设一个终态后面必须看一眼前瞻字符再决定产出什么。这个坑几乎每个做编译原理实验的人都会踩一遍踩完才能理解为什么需要前瞻。5.4 坑3FIRST/FOLLOW集合用肉眼推分析表冲突现象文法处理器报FIRST集合冲突但你对着文法看半天觉得没问题。原因含ε产生式的规则里FIRST(β)中的ε要往后传播到FOLLOW(A)这个传播经常被手算漏掉或者只传播一层就停了。解决把FIRST和FOLLOW的计算写成不动点循环反复扫描所有产生式直到集合不再变化为止。// 用不动点迭代算FOLLOW避免手算漏掉ε传播 bool changed true; while (changed) { changed false; for (auto rule : g.rules) { // 若整个rhs可空FOLLOW(lhs)要并进rhs末尾符号的FOLLOW // 若A - pBq 且q可空FOLLOW(B)需要并入FOLLOW(A) // 任何一步集合变大changed置true继续下一轮 } }这个过程有个学名叫“迭代到不动点”如果集合不再变大说明所有传播都完成了。依赖这个自动计算比手工推导可靠得多。5.5 坑4char有符号导致频率表越界现象压缩含中文注释的C文件时程序崩溃或者压缩率异常。原因char默认有符号UTF-8中文注释的每个字节都大于127转成char后变负数拿来当freq[256]的下标直接越界。解决全链路用unsigned char统计和索引读文件时用std::ios::binary模式打开避免文本模式的换行转换把字节流改掉。这个坑不踩一次很难意识到踩过之后就长记性了。5.6 坑5语法树打印挤成一团实验报告没东西可放现象printAST直接把value输出嵌套表达式全部连成一行答辩截图完全看不出树结构。原因递归打印时没有传深度参数每个节点都从第0列开始。解决打印函数加depth参数每层先输出depth*2个空格再输出节点内容子节点递归时depth1。实验报告里放一张带缩进的AST截图比一百行文字描述都管用。6. TINY扩充语言的语法树生成递归下降构造AST与缩进打印验证6.1 AST节点设计与递归下降的写法语法树生成是整条流水线的终点。AST节点不要设计得太复杂五个字段足够节点类型、节点值、子节点列表。struct ASTNode { std::string kind; // Program/Stmt/BinOp/Num/Id std::string value; // 运算符/变量名/数字字面量 std::vectorASTNode* children; ~ASTNode() { for (auto* c : children) delete c; } };递归下降的写法比LR分析表直观得多。每个非终结符对应一个Parse函数遇到什么token往下调哪个函数完全由文法决定。以表达式为例ASTNode* parseExpr() { ASTNode* left parseTerm(); // 先解析优先级低的一层 while (peek().kind Op (peek().value || peek().value -)) { Token op next(); ASTNode* n new ASTNode{BinOp, op.value}; n-children.push_back(left); n-children.push_back(parseTerm()); // 右操作数继续下降 left n; } return left; // while循环保证左结合 }注意这里用了while而不是递归调parseExpr这是为了避免右递归造成的结合性错误。TINY扩充语言里加减法都是左结合的这种写法生成的AST和预期完全一致。term和factor依次类推factor层处理括号和数字字面量。6.2 验证缩进打印AST比单测还好使写完语法树生成没出断言先别高兴。把AST按缩进打出来一眼能看出结构和文法是否匹配void printAST(const ASTNode* n, int depth) { std::cout std::string(depth * 2, ) n-kind; if (!n-value.empty()) std::cout ( n-value ); std::cout \n; for (auto* c : n-children) printAST(c, depth 1); }a b * 2应该打出类似下面的结构BinOp() Id(a) BinOp(*) Id(b) Num(2)如果打出的是BinOp(*)在上层说明parseTerm和parseExpr的先后关系写反了运算符优先级错了。这种缩进打印是我觉得整个项目里性价比最高的调试手段——它把黑盒子的内部结构直接摊在屏幕上。我自己的教训是第一次做完这整套作业时语法树输出只用一行cout答辩老师看了一眼说“你的树呢”。后来加上depth缩进生成、验证、报告截图全部一次通过。希望这套拆解和踩坑记录能帮你在编译原理实验上少走几步弯路把精力省下来放在真正有趣的文法设计和AST可视化上。本文还有配套的精品资源点击获取 
长河君 · 2026/10/12 19:46:50 · 阅读 1.2k 编译原理实验：Huffman压缩、DFA词法分析与TINY语法树生成全流程
简介一份编译原理课程设计完整资料涵盖C源程序压缩与解压、自动机、文法问题处理器、TINY扩充语言语法树生成等典型任务适合计算机、人工智能、通信工程等专业的学生用于课程设计、毕业设计或项目初期演示也适合有一定基础者在此基础上二次开发。压缩包共272个文件约72.55MB核心包括52个cpp源文件、23个h头文件、31个txt说明文档、18个pdf资料、10个docx实验报告、11个tny语法测试用例、11个exe可执行程序以及dll运行库和png截图等源码、文档、报告、可执行程序全部齐备目录结构清晰便于按需查阅。目前已有144人学习下载。作者在项目备注中说明代码均测试运行成功设计完成后才打包上传答辩评审平均分达到96分同时提供实验报告、文档说明和可执行文件遇到运行问题还可私聊咨询并远程教学对初学编译原理、需要参考完整作业流程的读者很有帮助。1. 把压缩解压、自动机、文法问题处理器、TINY语法树生成串成一条流水线每年编译原理实验交作业前总有人对着这份题目发愁C源程序的压缩和解压不是数据结构题吗自动机和文法问题处理器为什么单独列出来TINY扩充语言的语法树生成到底要交到什么程度我按一次课程设计的经验说这四个东西不是四个独立题目而是一条流水线——压缩解压负责把源码无损地送进内存自动机负责把字符流切成token文法问题处理器负责在递归下降之前把左递归和公共前缀清干净最后语法树生成把token流变成能打印的AST。适合要交实验报告和答辩的学生也适合想用TINY把词法、语法链路整体跑通的人。我的建议是先定接口再写实现后面至少少改三次。2. 先定模块边界再写代码四个模块的接口与数据流2.1 压缩解压为什么会在编译原理作业里很多人的第一反应是编译原理作业搞压缩干什么代码压缩不是数据结构的题吗这个要看题目出处。部分编译原理实验手册会把“源程序压缩存储”作为词法分析的前置扩展题要求你把一个C源文件先压成一包字节需要分析时再无损解压回来。表面考的是字符统计、变长编码和文件读写实际上考的是自动机——哈夫曼树的构造过程本身就是一种确定型编码和你后面写词法分析器用的DFA是同一套思维。常见做法是读入C源文件按字节统计频率构建哈夫曼树输出压缩后的二进制文件解压时先读回树结构还原出原始文本再交给后续模块。这一来一回必须完全无损空格、换行、注释一个都不能少因为词法分析器要靠空白字符分词注释也可能影响行号统计。换句话说压缩模块的验收标准只有一个解压出来的字节流和原文件完全一致。2.2 四条接口和一条main线我习惯先把模块间接口定死再各自实现。这样四个人做同一个大作业也不会互相等。// huffman.h 阶段1压缩与解压 int compressFile(const std::string inPath, const std::string outPath); std::string decompressFile(const std::string cmpPath); // lexer.h 阶段2自动机驱动的词法分析 std::vectorToken tokenize(const std::string srcText); // grammar.h 阶段3文法问题处理消除左递归/提取左因子 GrammarTable prepareGrammar(const Grammar g); // ast.h 阶段4TINY扩充语言语法树生成与打印 ASTNode* parse(const std::vectorToken tokens, const GrammarTable table); void printAST(const ASTNode* node, int depth);这套接口的意图很明确compressFile产出二进制文件decompressFile把文件还原成字符串tokenize只吃字符串不碰文件语法树生成只吃token流不关心源码怎么来的。每个模块之间只有一条数据通路出问题时按链路定位就行。main函数里把整条流水线穿起来只需要六行int main(int argc, char** argv) { compressFile(argv[1], out.cmp); // 1. 压缩 auto src decompressFile(out.cmp); // 2. 解压 auto tokens tokenize(src); // 3. 自动机切token auto table prepareGrammar(tinyGrammar()); // 4. 文法处理 auto root parse(tokens, table); // 5. 语法树生成 printAST(root, 0); // 6. 层级打印 }注意prepareGrammar的输入不是token而是文法定义。TINY文法在代码里单独写一个tinyGrammar()函数返回产生式集合文法处理器先对它做预处理产出的GrammarTable再给parse用。这么做的好处是你如果改文法不需要动词法分析器。2.3 目录结构与构建方式交付时需要“源代码文档说明实验报告可执行”目录从一开始就按这个组织src/ huffman.h huffman.cpp lexer.h lexer.cpp grammar.h grammar.cpp ast.h ast.cpp main.cpp data/ sample.cpp doc/ 实验报告.md构建用一条g命令就够了不需要引入CMakeg -stdc17 main.cpp huffman.cpp lexer.cpp grammar.cpp ast.cpp -o tiny_compiler ./tiny_compiler data/sample.cpp如果你在VS Code里配好了C/C环境和调试器也可以直接在tasks.json里把这条命令写成编译任务F5跑起来看断点。可执行文件就是tiny_compiler把它和sample.cpp、实验报告打成一个包就能交。实验报告里不需要贴全部代码重点是接口截图、AST打印效果图、压缩前后字节数对比这三样。2.4 顺序不能乱的三个原因模块顺序是题目指定好的不能调换背后有实际约束。压缩必须在词法分析之前因为词法分析器需要的是原始文本。有人想“先分词再压缩token流”那压缩率确实更高但题目要求的压缩对象是C源程序的文件内容不是token序列。解压必须直接在内存里出字符串不能解压到磁盘再读文件否则就没达到“压缩存储、按需还原”的目的。文法处理器必须跑在语法树生成之前因为它改的是文法本身——如果直接把带左递归的文法交给递归下降程序第一轮递归就会爆栈。这个顺序也决定了你的调试顺序先单独测压缩解压一致再测tokenize切分正确最后才轮到语法树。每一步的输入输出都是上一模块的产物链路长但好定位。3. 用Huffman实现C源程序的压缩与解压核心代码与两个必调参数3.1 为什么选Huffman而不是RLE或LZ77C源码的字节分布很典型小写字母、空格、换行、大括号、分号出现频率极高数字和生僻符号很少。对这种分布变长编码能压掉30%到40%而RLE只对连续重复数据有效比如位图C源码里很少有连续重复的字符LZ77/LZW效果好但实现量至少翻倍写进实验报告很难讲清楚。Huffman是最匹配课程设计定位的算法——原理好讲、代码量可控、能体现自动机思想。STL里的priority_queue可以直接当最小堆用这也是为什么用C写这个模块最顺手堆、编码表、位运算都有现成支撑不用自己造数据结构。算法压缩率实现成本适合C源码RLE低极低否Huffman中中是LZ77/LZW高高是但不划算3.2 构建哈夫曼树统计、建堆、合并、生成编码表#include queue #include vector #include unordered_map #include functional struct HuffNode { unsigned char ch; // 只在叶子节点有效 long long freq; HuffNode *left, *right; HuffNode(unsigned char c, long long f) : ch(c), freq(f), left(nullptr), right(nullptr) {} }; struct NodeCmp { bool operator()(HuffNode* a, HuffNode* b) const { return a-freq b-freq; // 小顶堆 } }; void buildHuffman(const std::string text, std::unordered_mapunsigned char, std::string codes) { long long freq[256] {0}; for (unsigned char c : text) freq[c]; // 按字节统计 std::priority_queueHuffNode*, std::vectorHuffNode*, NodeCmp pq; for (int i 0; i 256; i) if (freq[i]) pq.push(new HuffNode((unsigned char)i, freq[i])); // 只有一个字符时包一层空根避免生成空编码 if (pq.size() 1) { auto* only pq.top(); pq.pop(); auto* root new HuffNode(0, only-freq); root-left only; pq.push(root); } while (pq.size() 1) { auto* l pq.top(); pq.pop(); auto* r pq.top(); pq.pop(); auto* parent new HuffNode(0, l-freq r-freq); parent-left l; parent-right r; pq.push(parent); } std::functionvoid(HuffNode*, std::string) dfs [](HuffNode* p, std::string s) { if (!p-left !p-right) { codes[p-ch] s; return; } if (p-left) dfs(p-left, s 0); if (p-right) dfs(p-right, s 1); }; dfs(pq.top(), ); }代码逻辑分四步统计256个字节出现次数把出现过的字节建成叶子节点放进优先队列反复弹出频率最小的两个节点合并成新节点再入队直到只剩一棵树从根做DFS向左记0、向右记1到叶子就得到该字节的变长编码。两个关键参数一是freq的类型用long long作业里的测试文件可能只有几十KB但别低估源码文件大了之后int不够用二是叶子节点里的ch声明为unsigned char否则中文注释的UTF-8字节会被当成负数后面当数组下标时会越界。这个坑在后面避坑章还会专门讲。3.3 压缩文件格式让解压端能重建那棵树压缩和解压是成对出现的所以文件格式必须自己定清楚。我用最简单的定长头结构先写256个long long的频率数组再写入数据的字节数和最后一个字节的有效位数最后是压缩位流。bool compressFile(const std::string inPath, const std::string outPath) { std::ifstream in(inPath, std::ios::binary); std::string text((std::istreambuf_iteratorchar(in)), std::istreambuf_iteratorchar()); std::unordered_mapunsigned char, std::string codes; buildHuffman(text, codes); std::ofstream out(outPath, std::ios::binary); long long freq[256] {0}; for (unsigned char c : text) freq[c]; out.write(reinterpret_castchar*(freq), sizeof(freq)); // 文件头 int bitBuf 0, bitCount 0, totalBits 0; for (unsigned char c : text) { for (char b : codes[c]) { bitBuf (bitBuf 1) | (b - 0); if (bitCount 8) { out.put(static_castchar(bitBuf)); bitBuf 0; bitCount 0; } totalBits; } } if (bitCount) out.put(static_castchar(bitBuf (8 - bitCount))); out.write(reinterpret_castchar*(totalBits), sizeof(totalBits)); out.close(); return true; }这里有几个容易写错的地方。第一个是位流拼接用bitBuf按位左移累积满8位就写一个字节最后不足8位时左移补零这个补零的数量由totalBits负责找回。第二个是文件头写的是频率表不是编码表频率表只有256个long long固定2KB简单且可调试代价是文件头偏大但对课程设计完全够用。totalBits这个参数一定要存——它是最后一个字节里真实数据的位数解压时全靠它截断填充位。3.4 解压实现与边界情况解压是压缩的逆过程读回频率表重新建树然后按位从根节点走走到叶子就输出一个字节。std::string decompressFile(const std::string cmpPath) { std::ifstream in(cmpPath, std::ios::binary); long long freq[256] {0}; in.read(reinterpret_castchar*(freq), sizeof(freq)); // 用freq重建与压缩端完全相同的Huffman树 std::unordered_mapunsigned char, std::string codes; // ... 构造字符串后再buildHuffman或直接重构树 ... int totalBits 0; in.read(reinterpret_castchar*(totalBits), sizeof(totalBits)); std::string out; HuffNode* p root; int consumed 0; char byte; while (in.read(byte, 1) consumed totalBits) { for (int i 7; i 0 consumed totalBits; i--) { p ((byte i) 1) ? p-right : p-left; if (!p-left !p-right) { out.push_back(p-ch); p root; } consumed; } } return out; }边界情况必须处理三种。空文件freq全零pq为空解压时会crash压缩前先判断text.empty()直接返回。只有一种字符的文件buildHuffman里已经包了一层空根不会出现空编码导致死循环。短文件压完比原文还长因为2KB文件头摆在那小文件压缩率是负的——我一般在压缩前判断text.size()小于1KB就直接存原文文件头里写一个标记位区分格式。4. 把自动机落成词法分析器DFA转移表、最长匹配与Token设计4.1 词法规则与字符分类TINY扩充语言的词法规则不算复杂但要把运算符、关键字、标识符、数字分开得先定义字符分类。字符分类是把输入字符映射成类别这样转移表不用对256个ASCII码各做一列只需要对七八个类别做列。类别包含说明Lettera-z A-Z _标识符和关键字的首字符Digit0-9数字字面量Op - * / ( ) ; ,单字符运算符和定界符Rel 可能构成双字符关系运算符Space空格 \t 换行跳过不计入tokenEnd\0输入结束我给DFA设计的状态含义如下状态含义0初态1正在读标识符/关键字2正在读整数3正在读小数4已读到可能是赋值或5已读到可能是或6已读到可能是或状态4、5、6的目的是实现最长匹配读到号时不急着产出再看下一个字符是不是是就组成不是再回退产出单字符。这正是自动机里有别于简单分词的细节。4.2 DFA转移表与驱动循环转移表用二维数组表示行是当前状态列是字符类别值是下一状态-1表示无路可走。// 字符类: 0Letter 1Digit 2Op 3Rel 4Space 5End int nextState[7][6] { { 1, 2, -1, 4, 0, -1}, // 0 初态 { 1, 1, -1, -1, -1, -1}, // 1 标识符 {-1, 2, -1, -1, -1, -1}, // 2 整数 {-1, 3, -1, -1, -1, -1}, // 3 小数 {-1, -1, -1, 7, -1, -1}, // 4 号后面跟则到7 {-1, -1, -1, 8, -1, -1}, // 5 号后面跟则到8 {-1, -1, -1, 9, -1, -1}, // 6 号后面跟则到9 }; // 状态7、8、9为终态行内不需要再转移驱动循环是词法分析器的核心最长匹配就靠“转移失败才回退”实现std::vectorToken tokenize(const std::string src) { std::vectorToken tokens; int state 0, start 0; for (size_t i 0; i src.size(); i) { CharClass cc classify(src[i]); int ns nextState[state][cc]; if (ns ! -1) { state ns; // 能走就走 } else { TokenKind kind finalKind(state, src.substr(start, i - start)); if (kind ! Unknown) tokens.push_back({kind, src.substr(start, i - start), start}); state 0; start i; // 关键点 i--; // 当前字符没被消费重读 } } return tokens; }这个回退逻辑是自动机里最容易写错的地方。遇到转移失败时说明从start到i-1这段已经是一个完整token但当前字符属于下一个token所以要i--让循环重新读它。如果忘了i--会导致当前字符被跳过最典型的就是把“”拆成两个“”。finalKind根据结束状态判断token类型状态1还要查关键字表在关键字表里就是Keyword否则是Identifier状态2和3是Number状态7、8、9分别是、、单字符运算符在classify阶段直接归类处理。4.3 运算符、注释与空白压缩层保留、词法层丢弃运算符这里必须处理多字符组合。C源码和TINY语言里都有、、这种双字符运算符如果词法分析器只按单字符切后续语法树生成就全乱了。我在classify里把、、单独归为Rel并让状态4、5、6读下一个字符这就是转移表里那三行的作用。注释的处理策略要提前定好。压缩解压层必须原样保留注释因为它做的是无损字节复制不知道语义词法分析层读到时直接把//到行尾、/到/的内容丢弃。TINY本身的注释语法是{}扩充后一般会加入C风格注释。丢弃注释时要注意换行符不能丢否则行号全错报错信息定位就不准了。空白字符也一样——词法层跳过空格和\t但遇到\n要计入行号。5. 文法问题处理器常见问题排查左递归死循环与5个必踩的坑5.1 文法问题处理器到底在修什么文法问题处理器的输入是TINY扩充语言的文法定义输出是能让递归下降顺畅工作的LL(1)文法。最常见的两个问题是左递归和公共前缀。左递归就是E - E T | T这种产生式递归下降程序要实现ParseE第一步就调用ParseE直接无限递归。消除直接左递归的标准做法是改写为右递归// 消除直接左递归: A - Aα | β A - βA, A - αA | ε void eliminateLeftRecursion(Grammar g) { for (auto rule : g.rules) { if (rule.rhs.size() 1 rule.rhs[0] rule.lhs) { std::string alpha rule.rhs.substr(1); // α std::string beta /* 收集所有不以A开头的产生式右部 */; // 生成 A - βA // 生成 A - αA | ε } } }提取左因子解决的是FIRST集合冲突A - aB | aC两个产生式都以a开头递归下降没法决定走哪条。改写为A - aAA - B | C。判断文法是否LL(1)也可以自动化对每个非终结符检查任意两个产生式的FIRST集合是否有交集再检查如果有ε产生式FIRST与FOLLOW是否冲突。这三件事做下来文法问题处理器的功能就完整了。5.2 坑1解压后字节对不上多了乱码现象压缩再解压输出的C源码和原文件不一致末尾多了几个不可见字符。原因压缩时最后一个字节不满8位做了左移补零解压端把这些填充位也当成有效编码走树走到了某个叶子甚至可能停在错误节点。解决文件头里必须存totalBits最后一个字节的有效位数解压时走一位就数一位走到totalBits立即停止不再读取后面内容。5.3 坑2a b被切成了a b现象语法树里出现了两个赋值节点表达式的语义完全不对。原因转移表里没有给号后面跟号单独设状态DFA读到第一个时转移成功读到第二个转移失败于是回退产出了“”再把第二个当作新token重读。解决按第4章的方式给、、各设一个终态后面必须看一眼前瞻字符再决定产出什么。这个坑几乎每个做编译原理实验的人都会踩一遍踩完才能理解为什么需要前瞻。5.4 坑3FIRST/FOLLOW集合用肉眼推分析表冲突现象文法处理器报FIRST集合冲突但你对着文法看半天觉得没问题。原因含ε产生式的规则里FIRST(β)中的ε要往后传播到FOLLOW(A)这个传播经常被手算漏掉或者只传播一层就停了。解决把FIRST和FOLLOW的计算写成不动点循环反复扫描所有产生式直到集合不再变化为止。// 用不动点迭代算FOLLOW避免手算漏掉ε传播 bool changed true; while (changed) { changed false; for (auto rule : g.rules) { // 若整个rhs可空FOLLOW(lhs)要并进rhs末尾符号的FOLLOW // 若A - pBq 且q可空FOLLOW(B)需要并入FOLLOW(A) // 任何一步集合变大changed置true继续下一轮 } }这个过程有个学名叫“迭代到不动点”如果集合不再变大说明所有传播都完成了。依赖这个自动计算比手工推导可靠得多。5.5 坑4char有符号导致频率表越界现象压缩含中文注释的C文件时程序崩溃或者压缩率异常。原因char默认有符号UTF-8中文注释的每个字节都大于127转成char后变负数拿来当freq[256]的下标直接越界。解决全链路用unsigned char统计和索引读文件时用std::ios::binary模式打开避免文本模式的换行转换把字节流改掉。这个坑不踩一次很难意识到踩过之后就长记性了。5.6 坑5语法树打印挤成一团实验报告没东西可放现象printAST直接把value输出嵌套表达式全部连成一行答辩截图完全看不出树结构。原因递归打印时没有传深度参数每个节点都从第0列开始。解决打印函数加depth参数每层先输出depth*2个空格再输出节点内容子节点递归时depth1。实验报告里放一张带缩进的AST截图比一百行文字描述都管用。6. TINY扩充语言的语法树生成递归下降构造AST与缩进打印验证6.1 AST节点设计与递归下降的写法语法树生成是整条流水线的终点。AST节点不要设计得太复杂五个字段足够节点类型、节点值、子节点列表。struct ASTNode { std::string kind; // Program/Stmt/BinOp/Num/Id std::string value; // 运算符/变量名/数字字面量 std::vectorASTNode* children; ~ASTNode() { for (auto* c : children) delete c; } };递归下降的写法比LR分析表直观得多。每个非终结符对应一个Parse函数遇到什么token往下调哪个函数完全由文法决定。以表达式为例ASTNode* parseExpr() { ASTNode* left parseTerm(); // 先解析优先级低的一层 while (peek().kind Op (peek().value || peek().value -)) { Token op next(); ASTNode* n new ASTNode{BinOp, op.value}; n-children.push_back(left); n-children.push_back(parseTerm()); // 右操作数继续下降 left n; } return left; // while循环保证左结合 }注意这里用了while而不是递归调parseExpr这是为了避免右递归造成的结合性错误。TINY扩充语言里加减法都是左结合的这种写法生成的AST和预期完全一致。term和factor依次类推factor层处理括号和数字字面量。6.2 验证缩进打印AST比单测还好使写完语法树生成没出断言先别高兴。把AST按缩进打出来一眼能看出结构和文法是否匹配void printAST(const ASTNode* n, int depth) { std::cout std::string(depth * 2, ) n-kind; if (!n-value.empty()) std::cout ( n-value ); std::cout \n; for (auto* c : n-children) printAST(c, depth 1); }a b * 2应该打出类似下面的结构BinOp() Id(a) BinOp(*) Id(b) Num(2)如果打出的是BinOp(*)在上层说明parseTerm和parseExpr的先后关系写反了运算符优先级错了。这种缩进打印是我觉得整个项目里性价比最高的调试手段——它把黑盒子的内部结构直接摊在屏幕上。我自己的教训是第一次做完这整套作业时语法树输出只用一行cout答辩老师看了一眼说“你的树呢”。后来加上depth缩进生成、验证、报告截图全部一次通过。希望这套拆解和踩坑记录能帮你在编译原理实验上少走几步弯路把精力省下来放在真正有趣的文法设计和AST可视化上。本文还有配套的精品资源点击获取