编译原理实战：DFA自动机、Huffman压缩与TINY语法树生成全解析

简介这是一份编译原理课程综合设计资料包涵盖C源程序压缩与解压、自动机、文法问题处理器、TINY扩充语言语法树生成等典型任务适合计算机相关专业学生用于课程设计、作业参考或毕设预研也适合有基础的同学对照案例进阶。压缩包共272个文件、约72.55MB包含52个cpp源文件与23个h头文件11个tny测试样例、11个exe可执行程序以及docx实验报告、pdf文档和pro/ui工程文件等从源码、工程配置到运行结果均有覆盖。已有144人学习下载。代码均测试通过作者课程设计答辩平均分96分压缩解压部分按关键字、注释、ASCII等维度设计了多种压缩bin样例文法处理器与TINY语法树生成模块可独立运行配合文档说明和可执行程序便于逐模块复现与理解。作者还提供答疑支持可协助新手快速跑通整个项目。1. 编译原理作业里的压缩、自动机与TINY语法树这套组合题到底在考什么编译原理作业最容易被做成五个独立小程序的就是C源程序的压缩和解压、自动机、文法问题处理器、TINY扩充语言的语法树生成这一串。其实它们是一条完整的编译前端链路自动机负责给源码做词法切分切出来的令牌流既撑起压缩模块又作为文法处理器的输入文法处理器把TINY扩充文法改造成可判定的LL(1)形式递归下降解析器再按改造后的文法生成语法树。这套东西值得照着做一遍尤其是要交实验报告和可执行文件的人以及想一次性打通词法到语法那条路的人。我按处理这类课设的顺序展开先压缩、再文法、最后上语法树每个模块都给能直接抄的代码和参数。2. 压缩模块的词法地基DFA转移表与Huffman编码如何把C源码压成令牌流拿到这个组合题我一般先做压缩模块。不是因为它简单而是它能把自动机、自定义文件格式、二进制读写和解压器一次练完后面文法模块的代码风格也会跟着干净。2.1 为什么压缩要挂在自动机下面zlib做不了模式级压缩如果直接调zlibC源码只是被当成普通字节流压了一遍它看不出while、return、这些模式在源码里反复出现。课程设计把压缩和解压跟自动机放在一起真正想练的是模式级压缩先用有限自动机把源码切成令牌流把高频保留字和运算符映射成单字节编号然后再对编号流做一次Huffman编码。两段压下来压缩比通常比直接zlib还好看报告里也能写出“两层压缩”的设计。手写方案要先解决一个问题令牌流不是纯字节数组里面有类型编号、有标识符原文。我的做法是把令牌流拆成两类数据词法单元类型和高频符号编号走Huffman真正的标识符原文、数字、字符串字面量以及空白换行走原样透传。这样解压器的逻辑就变成“先还原令牌流再把透传字节按位置填回去”不用做语法级别的重建正确性容易保证。2.2 DFA识别保留字与运算符转移表、最长匹配与回退这一版DFA用字符类压缩表规模状态只有5个初始、标识符、数字、字符串、运算符。把ascii字符先归类成5类再查表比在每个字节上做十几个if清晰得多。// dfa_table.h用字符类压缩DFA转移表 enum CharClass : uint8_t { C_SPACE, // 空白、换行 C_LETTER, // a-z A-Z _ C_DIGIT, // 0-9 C_QUOTE, // 单双引号 C_OTHER, // 运算符、界符、其他 C_MAX }; static const int8_t dfa[5][C_MAX] { // 空格 字母 数字 引号 其他 { 0, 1, 2, 3, 4 }, // 0 初始 { 0, 1, 1, 0, 0 }, // 1 标识符 { 0, 0, 2, 0, 0 }, // 2 数字 { 0, 0, 0, 3, 0 }, // 3 字符串 { 0, 0, 0, 0, 0 }, // 4 运算符入口由最长匹配接管 };状态3的字符串识别在表里只能处理结束引号真实源码里a\n这种转义会让“下一个引号即结束”的判断出错。我一般把转义检查放在状态迁移外单独判断进入字符串状态后每次遇到引号先看前一个字符是不是反斜杠是反斜杠就继续留在状态3。这是词法器里相对独立的细节不硬塞进表里。识别循环的关键不是查表本身而是“最长匹配回退”。和这类多字符运算符DFA走到一半会先到达一个可接受状态如果后面还有能继续匹配的字符就得记录上一次接受的位置等彻底走不通再回退。// tokenizer.cppDFA驱动 最长匹配回退 size_t i 0, n src.size(); int state 0; size_t tok_start 0, last_accept 0; while (i n) { int ns dfa[state][char_class(src[i])]; if (ns 0 state ! 0) { // 状态归0从最近一次接受位置切出一个token i last_accept; emit_token(src, tok_start, i, out); state 0; tok_start i; last_accept i; continue; } if (is_accept(state)) { last_accept i 1; // 记录本次接受允许继续贪心 } state ns; i; } if (tok_start n) emit_token(src, tok_start, n, out);逻辑说明last_accept保存的是最近一次接受状态的下一个字符位置。当匹配到时状态4是接受态然后看到仍可继续留在状态4直到遇到空格才归0此时last_accept已经指向i2的位置切出来的是完整的。如果没有回退会被切成和两个token后面写表达式解析器时全是坑。参数说明is_accept(state)只对状态1和2返回true状态4的“可接受”实际上由运算符匹配表决定。我的做法是在状态4里先试3字符运算符、再试2字符运算符表都不中就把当前字符当单字符界符处理。这里要注意一个死循环保护如果last_accept等于tok_start比如遇到无法归类的乱码字符必须强制i否则外循环会卡死。这个问题我用血泪换来的代码里一定要加。2.3 第二级Huffman压缩码表怎么写进文件头解压怎么还原DFA切出来的令牌流里;、)、else这类符号频率极高分布很不均匀非常适合再压一层。Huffman树用小顶堆构建C标准库里priority_queue配合pair就能省掉手写堆的功夫。// huffman.cpp用小顶堆构建Huffman树 using QItem std::pairuint32_t, HuffNode*; std::priority_queueQItem, std::vectorQItem, std::greaterQItem minq; for (const auto pr : freq) { auto* leaf new HuffNode{pr.second, pr.first, nullptr, nullptr}; minq.push({pr.second, leaf}); } while (minq.size() 1) { auto a minq.top(); minq.pop(); auto b minq.top(); minq.pop(); auto* inner new HuffNode{a.first b.first, 0, a.second, b.second}; minq.push({inner-freq, inner}); }逻辑说明pair的比较会先比频率频率相同再比节点指针地址这让结果具备确定性不会因为堆排序不稳定导致码表每次都变。解压时先读文件头里的码表逐比特从根节点往下走走到叶子就输出一个符号再回到根节点。参数说明一份压缩文件头我通常这样设计字段字节数含义magic4固定TPK1解压器第一眼校验src_len4原始文件长度token_count4令牌总数huff_symbol_count2Huffman符号种数huff_table变长每个符号的码长和码字payload变长Huffman编码后的比特流压缩比的经验值注释和字符串较多的源码压到原体积的35%到45%纯代码块逼近30%。如果压缩后比这个区间高先查空白是不是也被当作高频token送进了Huffman。空白其实是原文透传compress后再还原是逐字节一致不能压。解压器的还原顺序是读文件头 → 还原令牌流 → 遇T_BYTE原样写字节 → 遇编号查保留字表写回保留字这样源码格式和注释一字不差。3. 文法问题处理器FIRST/FOLLOW集合、消左递归与提取左因子的判定顺序压缩模块给文法模块留下的东西叫“令牌流”。TINY扩充语言的解析器要靠文法驱动而大部分学生自己设计的文法并不是拿来就能用的。3.1 文法问题处理器到底处理什么从LL(1)判定到文法改造“文法问题处理器”处理的是文法本身的瑕疵不是源码。常见任务是这样的你给出一组产生式处理器先计算FIRST集和FOLLOW集然后判断它是不是LL(1)文法。如果产生式里有expr - expr term这种左递归或者if_stmt - if expr then stmt else stmt和if_stmt - if expr then stmt这种公共前缀处理器要自动改写文法直到预测分析表没有冲突。这一步的价值在报告里体现得最明显。很多同学拿着教科书里的TINY文法直接写递归下降结果运行几个测试用例就栈溢出原因就是文法还带着左递归。把“文法改造”做成一个独立模块解析器吃进去的就是经过验证的LL(1)文法跑挂的概率低很多。3.2 FIRST集与FOLLOW集的计算不动点迭代与std::set的实现FIRST/FOLLOW计算最容易写错的地方是“只算一遍就结束”。教科书上的算法本来就要求迭代到不动点实际写代码时我用std::setchar存集合靠insert的返回值判断本轮是否有新元素加入。// first_follow.cpp不动点迭代直到集合不再增长 bool changed true; while (changed) { changed false; for (const Production p : gram) { // 1) 计算 FIRST(p.lhs) bool all_nullable true; for (char sym : p.rhs) { if (is_nonterminal(sym)) { for (char c : first[sym]) if (c ! EPS) changed | first[p.lhs].insert(c).second; if (!first[sym].count(EPS)) { all_nullable false; break; } } else { if (sym ! EPS) changed | first[p.lhs].insert(sym).second; all_nullable false; break; } } if (all_nullable) changed | first[p.lhs].insert(EPS).second; // 2) 计算 FOLLOW对产生式右部每个非终结符 for (size_t j 0; j p.rhs.size(); j) { char B p.rhs[j]; if (!is_nonterminal(B)) continue; bool rest_nullable true; for (size_t k j 1; k p.rhs.size(); k) { char x p.rhs[k]; if (is_nonterminal(x)) { for (char c : first[x]) if (c ! EPS) changed | follow[B].insert(c).second; if (!first[x].count(EPS)) { rest_nullable false; break; } } else { if (x ! EPS) changed | follow[B].insert(x).second; rest_nullable false; break; } } if (rest_nullable) { for (char c : follow[p.lhs]) changed | follow[B].insert(c).second; } } } }逻辑说明changed | first[p.lhs].insert(c).second是这样工作的set::insert返回pairiterator,boolbool为true说明确实插入了新元素本轮集合有变化需要继续迭代。用位或累积这个标志比每轮重新比较整个集合快代码也短。参数说明EPS我习惯用字符#表示因为真正的文法和源码里不会出现#开头的内容。终结符的first集合要在跑算法前全部预置为自身否则is_nonterminal(x)为假时去查first[x]会拿到空集合FOLLOW传播就会静默丢失信息。这个坑的表现是“程序不报错但预测表缺了一堆终结符”很难定位。3.3 消除左递归与提取左因子从公式到预测表的代价消除直接左递归的公式大家都知道但放进代码里容易忽略一点提取左公因子要“先提干净再做左递归消除”。两类变换长这样原产生式改造后产生式备注A - Aα1Aα2βA - αβ1αβ2A - αA且 A - β1A - Bα, B - Aβ先代入B得到A - Aβ…顺序上的常见做法是先做间接左递归代入再做直接左递归消除最后提左因子。如果顺序反过来公共前缀会被左递归循环重新引入白做一遍。3.4 用TINY扩充文法走一遍处理前后的文法与预测表变化TINY语言的基础文法里表达式部分必然带左递归。下面是通常见到的样子和处理结果类别原文法片段改造后文法片段表达式expr - expr termterm关系比较rel - rel cmp termterm语句序列stmt_list - stmt_list ; stmtstmt改造完成后expr_tail的预测表现在是lookahead为时走 term expr_taillookahead为)、else、end或$时走ε产生式。这里没有任何冲突这套文法才算合格。这一步如果发现预测表有冲突优先怀疑两件事一是else悬空问题二是stmt_list_tail的FIRST集跟FOLLOW集重叠。TINY扩充语言里if语句和while语句都以end收尾;作分隔符这种设计本身就是为了避免分号跟end的归属问题。但只要你加了else就得按“最近嵌套的if匹配else”改写文法这是TINY扩充里最常见的冲突源。4. TINY扩充语言的语法树生成递归下降解析器与AST节点设计的落地代码文法处理器输出的LL(1)文法到了这一章要真正长成树。语法树生成有两条路一条用yacc/bison自动生成一条手写递归下降。课程设计我一般推荐手写理由有三个一是不依赖外部工具链交可执行文件方便二是报错信息可控能带上源码行号三是报告里能贴的代码量大答辩时有东西讲。4.1 TINY扩充了什么文法规格与AST节点的对应关系TINY是一种很克制的教学语言扩充的方向通常是函数定义、布尔表达式和新的语句类型。我按常见扩充方式给出这组对应关系文法产生式AST节点说明program - stmt_listProgramNode根节点持有语句列表stmt - if expr then stmt_list else stmt_list endIfStmtNode必须带else否则悬空else难处理stmt - while expr do stmt_list endWhileStmtNodeTINY里布尔表达式单独一类stmt - id : exprAssignNode左值是标识符expr - term expr_tailExprNode改造后的表达层次func - func id ( params ) stmt_list endFuncDefNode扩充功能参数列表加类型AST的设计原则是贴近文法但不要1:1复制。比如expr_tail是文法改造出来的辅助非终结符它在AST里不应该有自己的节点 term expr_tail应该直接折叠成BinExprNode让expr_tail变透明。不然语法树里全是一堆Tail节点打印出来不好看老师也会怀疑你没理解AST的抽象层次。4.2 递归下降解析器骨架表达式、语句与函数定义的解析递归下降解析器是围绕文法写的每个非终结符对应一个函数。下面这段处理表达式用循环代替左递归正好跟第3章的文法改造对上。// parser.cpp表达式解析循环替代左递归 ASTNode* Parser::parseExpr() { ASTNode* left parseTerm(); // 先解析一个项 while (peek().type TT_PLUS || peek().type TT_MINUS) { Token op peek(); advance(); ASTNode* right parseTerm(); // 右操作数仍然是一整个项 left new BinExprNode(op, left, right); } return left; }逻辑说明文法里expr_tail - term expr_tail | ε是右递归递归下降会一层层往右嵌套解析很长的表达式时栈可能撑不住而且AST会长成一串右链。改用循环后同一层级的和-都挂在同一个左节点上树的形状就是教科书里的标准表达式树。参数说明我一直先把expr、term、factor三层优先级关系定死再写代码。factor处理括号、数字、标识符term处理乘除和取模expr处理加减。如果任务书里还有布尔表达式就再往上加一层bool_expr处理and、or不要在expr里跟算术混在一起。优先级一乱语法树画出来违反结合律测试用例一秒现原形。语句解析的骨架比表达式简单核心是看当前token类型分发ASTNode* Parser::parseStatement() { Token t peek(); if (t.type TT_IF) { advance(); ASTNode* cond parseExpr(); expect(TT_THEN); ASTNode* thenBody parseStmtList(); expect(TT_ELSE); ASTNode* elseBody parseStmtList(); expect(TT_END); return new IfStmtNode(cond, thenBody, elseBody, t.line); } if (t.type TT_WHILE) { /* while do stmt_list end */ } if (t.type TT_IDENT) { advance(); expect(TT_ASSIGN); ASTNode* rhs parseExpr(); return new AssignNode(t.lexeme, rhs, t.line); } throw ParseError(t.line, unexpected token t.lexeme); }逻辑说明expect函数负责吞掉期望的token吞不到就抛异常异常里带行号和期望内容。这一层是报错体验的分水岭写了的解析器失败时能告诉你是end丢了还是then写错不写的只能看到一句“segmentation fault”。4.3 AST节点设计与DOT输出把语法树画成图片放进报告AST节点的实现用继承结构每种节点存自己的专属字段再加一个统一的打印接口。// ast.h节点基类与两种典型节点 struct ASTNode { NodeKind kind; int line; virtual ~ASTNode() default; virtual std::string label() const 0; virtual std::vectorASTNode* children() const 0; }; struct BinExprNode : ASTNode { Token op; // 运算符token里面带lexeme和type ASTNode* left; ASTNode* right; std::string label() const override { return op.lexeme; } std::vectorASTNode* children() const override { return {left, right}; } }; struct IfStmtNode : ASTNode { ASTNode* cond; ASTNode* thenBody; ASTNode* elseBody; std::string label() const override { return if; } std::vectorASTNode* children() const override { return {cond, thenBody, elseBody}; } };DOT输出只需要遍历这棵树每个节点分配一个编号打印父子关系。Graphviz的dot -Tpng一行命令就能出图。// ast_dot.cpp输出Graphviz可识别的dot文本 void toDot(ASTNode* node, std::ostream os, int id) { int cur id; os n cur [label\ node-label() \];\n; for (ASTNode* ch : node-children()) { toDot(ch, os, id); os n cur - n id ;\n; } }这个函数用了一个小技巧递归先画子节点返回后子节点的id已经分配好了父节点再补一条边。顺序反过来的话边会指向还没生成的节点DOT图虽然能渲染但会有警告。4.4 CMake组织与命令行设计一个可执行交付物怎么对外提供交付物是一个命令行工具我习惯把它设计成子命令风格tinya pack 源码.cpp 输出.tpk做压缩tinya unpack 输入.tpk 还原.cpp做解压tinya ast 测试.tiny打印语法树。所有模块编译成一个可执行文件实验报告里写命令和输出截图老师验证成本低。cmake_minimum_required(VERSION 3.16) project(tiny_playground CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) add_executable(tinya src/main.cpp src/compress/tokenizer.cpp src/compress/huffman.cpp src/grammar/first_follow.cpp src/parser/parser.cpp src/ast/ast.cpp )逻辑说明这个CMakeLists把模块之间的依赖关系暴露得很清楚任何一个文件缺失编译助手会直接告诉你。很多同学在VSCode配置c/c环境时翻车本质上是tasks.json只编译了当前打开的文件多文件工程必须让cmake接管或者把全部cpp文件写进编译参数。参数说明命令行参数我建议用argv[1]做子命令名argv[2]和argv[3]做输入输出文件。不要用交互式菜单因为实验报告的自动化测试脚本不喜欢等输入。输出路径统一放到build/目录避免把中间文件弄脏源码目录也是报告里能写一笔的工程习惯。5. 避坑压缩还原不一致、文法死循环与语法树野指针的5个真实教训这里把动手做这一整套方案最容易翻车的5个位置列出来每条都是现象、原因、解决的顺序照着检查能省下一整晚。5.1 还原出来的源码变了空白被吃掉的连锁反应现象解压后的int a;变成inta;else if变成elseif程序没法编译。原因DFA把空白和换行归到C_SPACE后就丢弃了而保留字被编号替代编号之间没有空白还原时拼不出来。解决空白与换行不参与模式压缩统一走T_BYTE透传路径。词法阶段对空白单独保留原文压缩阶段对它们不做Huffman解压时T_BYTE原样写回。判断压缩是否正确第一关就应该是“源码逐字节一致”而不是“意思一样”。5.2被切成两个最长匹配的回退没做对现象a 2被解析成a 2表达式树结构直接错。原因DFA遇到第二个时状态归0立刻把第一个作为token提交了没有记录这个位置其实还在可匹配状态。解决运算符匹配器按长度分级尝试先试再试都失败才切单字符。DFA循环里必须维护last_accept并把回退逻辑写进状态归0分支同时加上if (last_accept tok_start) i;防死循环。这一步后所有多字符运算符都要重新跑测试。5.3 FIRST/FOLLOW死循环或算错EPS集合没处理干净现象程序跑起来卡死或者预测表里少了终结符但不报错。原因A - B C里B和C都可空时EPS传播没有正确完成或者对终结符调用了first[x]拿到空集合之后还继续遍历。解决终结符的first集合先预置为自身EPS用一个不会出现在文法里的字符表示不动点迭代每轮判断“是否插入了新元素”没有新元素才能退出。调试时把每轮集合大小打印出来如果连续多轮不变但changed还是true基本就是EPS比较写错。5.4 文法改造后预测表还有冲突只消直接左递归不够现象左递归消除完一跑LL(1)判定if语句相关产生式照样冲突。原因悬空else本质是文法的二义性不是左递归问题。只提左因子会反复提取同一个公共前缀但else归属内层还是外层if仍然没有定论。解决改写if文法强制else匹配最近的未匹配if这也意味着stmt里单独一条if不带else的产生式要从文法里拿掉或者接受这里需要回溯。TINY扩充语言一般直接规定“必须有else”避开这个经典问题。5.5 AST野指针与内存泄漏解析器异常路径上的double free现象调试器报堆损坏或者程序退出时析构崩溃Visual Studio的Debug模式在退出时弹一堆红色警告。原因子节点是用裸new创建的解析中途抛异常后已经创建的部分节点没人释放另一种是移动或拷贝时两个父节点指向同一个子节点。解决解析函数统一返回std::unique_ptrASTNode或者把所有节点挂到一个ASTContext对象池里统一释放。我后来偏向后者因为课程设计的AST不需要长时间存活解析完打DOT直接全部释放省脑子。6. 进阶验证round-trip一致性测试与AST可视化复盘整套方案跑通后我习惯加一个自动化回归脚本把压缩解压和语法树生成都圈在里面。压缩链路的正确性只有一个标准round-trip后源码逐字节一致。语法树生成有没有必要用图片辅助我的经验是必须哪怕只是给自己看。# round_trip.sh压缩解压一致性回归 ./tinya pack tests/sample.cpp build/sample.tpk ./tinya unpack build/sample.tpk build/sample.restored.cpp if cmp -s tests/sample.cpp build/sample.restored.cpp; then echo round-trip OK else echo round-trip FAILED fi单字节一致性通过后还要加一层token级比较把原始文件重新做词法分析把还原文件的token序列也跑一遍两个token流应该完全相同。这一层能告诉你问题出在DFA还是Huffman而不是笼统的一句“不匹配”。AST的验证我用两步。第一步把第4章的DOT输出集成进来./tinya ast tests/sample.tiny | dot -Tpng -o build/ast.png人工看图确认每棵子树的位置正确。第二步写一个归一化打印把树按照“左括号、节点标签、子树、右括号”的格式展开成一行文本存成golden文件放进tests目录。以后改文法或解析逻辑跑一下git diff就知道哪棵子树变了。这一步对实验报告尤其有用因为答辩被问“你怎么证明语法树是对的”时能拿出来的是回归记录不是一句“我调过”。我自己第一次做这类题目时把时间全花在压缩比上反复调Huffman码表最后答辩老师只问了一句“文法处理器怎么证明自己正确”我愣了。后来才明白压缩比是锦上添花压缩解压一致性和AST正确性才是这套作业的骨架。把这套验证脚本留到项目一开始就写能少走很多夜路。希望帮到你。本文还有配套的精品资源点击获取