企业官网建设流程全解析

简介：一份编译原理课程设计完整资料，涵盖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::vector<Token> tokenize(const std::string& srcText); // grammar.h 阶段3：文法问题处理，消除左递归/提取左因子 GrammarTable prepareGrammar(const Grammar& g); // ast.h 阶段4：TINY扩充语言语法树生成与打印 ASTNode* parse(const std::vector<Token>& 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++命令就够了，不需要引入CMake：

g++ -std=c++17 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或LZ77

C++源码的字节分布很典型：小写字母、空格、换行、大括号、分号出现频率极高，数字和生僻符号很少。对这种分布，变长编码能压掉30%到40%；而RLE只对连续重复数据有效（比如位图），C++源码里很少有连续重复的字符；LZ77/LZW效果好但实现量至少翻倍，写进实验报告很难讲清楚。Huffman是最匹配课程设计定位的算法——原理好讲、代码量可控、能体现自动机思想。

STL里的priority_queue可以直接当最小堆用，这也是为什么用C++写这个模块最顺手：堆、编码表、位运算都有现成支撑，不用自己造数据结构。

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_map<unsigned char, std::string>& codes) { long long freq[256] = {0}; for (unsigned char c : text) freq[c]++; // 按字节统计 std::priority_queue<HuffNode*, std::vector<HuffNode*>, 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::function<void(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_iterator<char>(in)), std::istreambuf_iterator<char>()); std::unordered_map<unsigned 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_cast<char*>(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_cast<char>(bitBuf)); bitBuf = 0; bitCount = 0; } totalBits++; } } if (bitCount) out.put(static_cast<char>(bitBuf << (8 - bitCount))); out.write(reinterpret_cast<char*>(&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_cast<char*>(freq), sizeof(freq)); // 用freq重建与压缩端完全相同的Huffman树 std::unordered_map<unsigned char, std::string> codes; // ... 构造字符串后再buildHuffman，或直接重构树 ... int totalBits = 0; in.read(reinterpret_cast<char*>(&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码各做一列，只需要对七八个类别做列。

我给DFA设计的状态含义如下：

状态4、5、6的目的是实现最长匹配：读到=号时不急着产出，再看下一个字符是不是=，是就组成==，不是再回退产出单字符。这正是自动机里有别于简单分词的细节。

4.2 DFA转移表与驱动循环

转移表用二维数组表示，行是当前状态，列是字符类别，值是下一状态，-1表示无路可走。

// 字符类: 0=Letter 1=Digit 2=Op 3=Rel 4=Space 5=End 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::vector<Token> tokenize(const std::string& src) { std::vector<Token> 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 -> aA'，A' -> B | C。

判断文法是否LL(1)也可以自动化：对每个非终结符，检查任意两个产生式的FIRST集合是否有交集；再检查如果有ε产生式，FIRST与FOLLOW是否冲突。这三件事做下来，文法问题处理器的功能就完整了。

5.2 坑1：解压后字节对不上，多了乱码

现象：压缩再解压，输出的C++源码和原文件不一致，末尾多了几个不可见字符。原因：压缩时最后一个字节不满8位做了左移补零，解压端把这些填充位也当成有效编码走树，走到了某个叶子甚至可能停在错误节点。解决：文件头里必须存totalBits（最后一个字节的有效位数），解压时走一位就数一位，走到totalBits立即停止，不再读取后面内容。

5.3 坑2：a == b被切成了a = = b

现象：语法树里出现了两个赋值节点，表达式的语义完全不对。原因：转移表里没有给=号后面跟=号单独设状态，DFA读到第一个=时转移成功，读到第二个=转移失败，于是回退产出了“=”，再把第二个=当作新token重读。解决：按第4章的方式给==、<=、>=各设一个终态，=后面必须看一眼前瞻字符再决定产出什么。这个坑几乎每个做编译原理实验的人都会踩一遍，踩完才能理解为什么需要前瞻。

5.4 坑3：FIRST/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 坑4：char有符号导致频率表越界

现象：压缩含中文注释的C++文件时程序崩溃，或者压缩率异常。原因：char默认有符号，UTF-8中文注释的每个字节都大于127，转成char后变负数，拿来当freq[256]的下标直接越界。解决：全链路用unsigned char统计和索引；读文件时用std::ios::binary模式打开，避免文本模式的换行转换把字节流改掉。这个坑不踩一次很难意识到，踩过之后就长记性了。

5.6 坑5：语法树打印挤成一团，实验报告没东西可放

现象：printAST直接把value输出，嵌套表达式全部连成一行，答辩截图完全看不出树结构。原因：递归打印时没有传深度参数，每个节点都从第0列开始。解决：打印函数加depth参数，每层先输出depth*2个空格再输出节点内容，子节点递归时depth+1。实验报告里放一张带缩进的AST截图，比一百行文字描述都管用。

6. TINY扩充语言的语法树生成：递归下降构造AST与缩进打印验证

6.1 AST节点设计与递归下降的写法

语法树生成是整条流水线的终点。AST节点不要设计得太复杂，五个字段足够：节点类型、节点值、子节点列表。

struct ASTNode { std::string kind; // Program/Stmt/BinOp/Num/Id std::string value; // 运算符/变量名/数字字面量 std::vector<ASTNode*> 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可视化上。

本文还有配套的精品资源，点击获取