企业官网建设流程全解析

简介：这份资源面向计算机专业学生与编译原理学习者，提供一套基于C++实现的LL(1)文法分析器课程设计代码，解决从文法规则自动生成分析表并完成语法分析的问题。压缩包共11个文件，以8个cpp源文件为核心，配合1个头文件与说明文档，整体约12KB，涵盖文法预处理、FIRST集与FOLLOW集计算、分析表生成及主分析流程等模块，结构清晰便于按功能阅读。已有406人学习下载，适合作为编译原理实验参考。读者可从中获得完整的LL(1)分析器实现思路，理解FIRST集、FOLLOW集与预测分析表的构造方法，并借鉴C++中STL容器与面向对象方式组织文法规则、处理分析冲突与错误恢复的实践写法，对课程设计与编译器前端入门均有参考价值。

1. 从文法到分析表：LL(1) 分析器到底在解决什么问题

你手里有一份文法，比如E -> T E'、E' -> + T E' | ε这种，想让它自动变成能跑的语法分析器。手写递归下降当然可以，但文法一改就得重写代码，维护成本高得离谱。LL(1) 分析器的价值就在于：把文法当输入，程序自动算出 FIRST 集、FOLLOW 集和预测分析表，然后靠一张表加一个栈就能驱动分析。这套东西在编译器前端、DSL 解析、配置文件读取里都用得上，尤其适合文法不大但需要频繁调整的场景。用 C++ 实现的好处是性能可控、内存布局清晰，而且能直接嵌进现有工程。这篇文章会从数据结构设计讲到分析表构造，再到用栈跑通一个完整表达式，每一步都给可复现的代码和参数说明。适合有 C++ 基础、想搞懂语法分析器内部机制的人，也适合正在做编译原理课设但不想只交个玩具的人。

2. 文法表示与 FIRST/FOLLOW 集：用 C++ 把集合算对

2.1 文法怎么存：产生式结构体与符号表

先把文法从文本变成内存里的结构。常见做法是定义一个Production结构体，左边一个非终结符，右边一个符号序列。符号用字符串存，终结符和非终结符靠一个set区分。这里有个容易翻车的地方：空串 ε 不能直接当普通符号处理，得单独标记。

#include <iostream> #include <vector> #include <set> #include <map> #include <string> #include <sstream> const std::string EPSILON = "ε"; struct Production { std::string lhs; // 左部非终结符 std::vector<std::string> rhs; // 右部符号序列，空串用 EPSILON 表示 }; class Grammar { public: std::vector<Production> productions; std::set<std::string> nonTerminals; std::set<std::string> terminals; std::string startSymbol; void addProduction(const std::string& line) { // 输入格式: "E -> T E'" std::istringstream iss(line); std::string lhs, arrow; iss >> lhs >> arrow; Production p; p.lhs = lhs; nonTerminals.insert(lhs); if (startSymbol.empty()) startSymbol = lhs; std::string sym; while (iss >> sym) { if (sym == "|") { productions.push_back(p); p.rhs.clear(); continue; } p.rhs.push_back(sym); } productions.push_back(p); } void finalize() { for (auto& p : productions) { for (auto& s : p.rhs) { if (nonTerminals.find(s) == nonTerminals.end() && s != EPSILON) { terminals.insert(s); } } } } };

addProduction按行解析，遇到|就切分成多条产生式。finalize在所有产生式读完后统一扫描，把没出现在左部的符号归为终结符。参数上唯一要注意的是 ε 的写法，代码里用"ε"字符串，如果你从文件读，建议统一替换成"#"或"epsilon"，避免编码问题导致匹配失败。

2.2 FIRST 集计算：递归加记忆化，别用纯循环硬怼

FIRST 集的规则不复杂：对每个非终结符，看它每条产生式右部第一个符号。如果是终结符，直接加入；如果是非终结符，把它的 FIRST 集并进来，如果它能推出 ε，就继续看下一个符号。坑在于非终结符之间会相互依赖，纯循环要反复迭代到不动点，写起来容易漏。

我一般用递归加visited标记，配合一个map<string, set<string>>缓存结果。递归深度等于非终结符依赖链长度，文法不大时完全够用。

std::map<std::string, std::set<std::string>> firstSets; std::set<std::string> computeFirst(const std::string& sym, Grammar& g, std::set<std::string>& visiting) { if (g.terminals.count(sym) || sym == EPSILON) { return {sym}; } if (firstSets.count(sym)) return firstSets[sym]; if (visiting.count(sym)) return {}; // 防左递归死循环 visiting.insert(sym); std::set<std::string> result; for (auto& p : g.productions) { if (p.lhs != sym) continue; if (p.rhs.empty()) { result.insert(EPSILON); continue; } bool allNullable = true; for (auto& s : p.rhs) { auto fs = computeFirst(s, g, visiting); result.insert(fs.begin(), fs.end()); if (fs.find(EPSILON) == fs.end()) { allNullable = false; break; } } if (allNullable) result.insert(EPSILON); } visiting.erase(sym); firstSets[sym] = result; return result; }

visiting集合是后悔药，防止文法有左递归时栈溢出。allNullable控制是否继续往后看：只要当前符号不能推出 ε，后面的符号就不该进 FIRST 集。这个逻辑写错的话，FIRST 集会多出不该有的终结符，后面分析表跟着全错。

2.3 FOLLOW 集计算：从起始符的$开始推

FOLLOW 集解决的是「非终结符后面可能跟什么」。起始符号的 FOLLOW 里先放一个结束符$。然后遍历所有产生式，对右部每个非终结符 B，看它后面的符号 β：把 FIRST(β) 去掉 ε 加进 FOLLOW(B)；如果 β 能推出 ε 或者 B 在末尾，就把 FOLLOW(左部) 加进 FOLLOW(B)。

std::map<std::string, std::set<std::string>> followSets; void computeFollow(Grammar& g) { followSets[g.startSymbol].insert("$"); bool changed = true; while (changed) { changed = false; for (auto& p : g.productions) { for (size_t i = 0; i < p.rhs.size(); ++i) { std::string B = p.rhs[i]; if (!g.nonTerminals.count(B)) continue; std::set<std::string> trailer; bool nullable = true; for (size_t j = i + 1; j < p.rhs.size(); ++j) { auto fs = firstSets[p.rhs[j]]; for (auto& x : fs) if (x != EPSILON) trailer.insert(x); if (fs.find(EPSILON) == fs.end()) { nullable = false; break; } } if (nullable) { for (auto& x : followSets[p.lhs]) trailer.insert(x); } for (auto& x : trailer) { if (followSets[B].insert(x).second) changed = true; } } } } }

这里用while(changed)迭代到不动点，因为 FOLLOW 集可能因为其他非终结符的更新而需要重新传播。参数上注意$是结束标记，别和文法里的终结符重名。如果文法里有$这个终结符，换成#或EOF。

3. 预测分析表构造：把集合变成一张可查的表

3.1 分析表的数据结构与填充规则

预测分析表是一个二维表，行是非终结符，列是终结符加$，格子里放产生式编号。规则很直接：对每条产生式A -> α，对 FIRST(α) 里每个终结符 a，把这条产生式填进M[A][a]；如果 α 能推出 ε，就对 FOLLOW(A) 里每个符号 b，把A -> ε填进M[A][b]。

std::map<std::string, std::map<std::string, int>> parseTable; void buildParseTable(Grammar& g) { for (size_t idx = 0; idx < g.productions.size(); ++idx) { auto& p = g.productions[idx]; std::set<std::string> firstAlpha; bool nullable = true; for (auto& s : p.rhs) { auto fs = firstSets[s]; for (auto& x : fs) if (x != EPSILON) firstAlpha.insert(x); if (fs.find(EPSILON) == fs.end()) { nullable = false; break; } } if (p.rhs.empty()) nullable = true; for (auto& a : firstAlpha) { parseTable[p.lhs][a] = (int)idx; } if (nullable) { for (auto& b : followSets[p.lhs]) { parseTable[p.lhs][b] = (int)idx; } } } }

idx是产生式在productions里的下标，后面分析时靠它取右部。如果同一个格子被填了两次，说明文法有冲突，不是 LL(1)。实际工程里我会在填充时检查parseTable[lhs][a]是否已存在，存在就打印冲突信息，方便定位是哪两条产生式打架。

3.2 冲突检测：LL(1) 到底能不能用

LL(1) 的硬性条件是：对每个非终结符，任意两条产生式的 FIRST 集不相交；如果某条能推出 ε，那它的 FIRST 集和另一条的 FOLLOW 集也不能相交。检测代码就加在填充循环里：

if (parseTable[p.lhs].count(a)) { std::cerr << "冲突: 非终结符 " << p.lhs << " 在符号 " << a << " 上有多条产生式\n"; }

常见冲突来源是左递归和公共左因子。左递归比如E -> E + T | T，FIRST 集直接和自己撞。解决办法是改写成右递归：E -> T E'，E' -> + T E' | ε。公共左因子比如S -> if E then S | if E then S else S，需要提取左因子。这两步不做，分析表根本填不出来，别硬上。

3.3 用表驱动分析：栈 + 输入指针跑通表达式

分析器主体是一个栈，初始放$和起始符号。每次看栈顶和当前输入符号，查表决定展开哪条产生式。如果是终结符就匹配并前进，如果是非终结符就弹栈并把右部逆序压入。

bool parse(const std::string& input, Grammar& g) { std::vector<std::string> stack = {"$", g.startSymbol}; std::vector<std::string> tokens; std::istringstream iss(input); std::string tok; while (iss >> tok) tokens.push_back(tok); tokens.push_back("$"); size_t pos = 0; while (!stack.empty()) { std::string top = stack.back(); std::string cur = tokens[pos]; if (top == "$" && cur == "$") return true; if (g.terminals.count(top) || top == "$") { if (top == cur) { stack.pop_back(); pos++; } else return false; } else { if (!parseTable[top].count(cur)) return false; int idx = parseTable[top][cur]; stack.pop_back(); auto& rhs = g.productions[idx].rhs; for (auto it = rhs.rbegin(); it != rhs.rend(); ++it) { if (*it != EPSILON) stack.push_back(*it); } } } return false; }

输入按空格分词，$是结束标记。压栈时逆序是因为栈是后进先出，逆序压入才能保证左部先被处理。如果返回 false，先检查输入串是不是按空格分好了，再检查分析表对应格子是不是空的。空表示当前状态没有合法动作，要么输入有误，要么文法不是 LL(1)。

4. 避坑与排查：LL(1) 实现里最容易翻车的 5 个点

4.1 现象：FIRST 集算出来少了终结符，分析表大片空白

原因通常是递归计算时visiting集合没清干净，或者allNullable逻辑写反了。比如A -> B c，B 能推出 ε，那 c 应该进 FIRST(A)。如果代码在 B 的 FIRST 里看到 ε 就 break，c 就丢了。解决方法是确保只有当前符号的 FIRST 不含 ε 时才停止往后看，含 ε 就继续。

4.2 现象：FOLLOW 集迭代不收敛，程序卡死

原因一般是产生式右部有自身递归，且更新逻辑没有去重。followSets[B].insert(x).second返回 false 表示没插入新元素，changed就不会置 true。如果忘了用返回值判断，每次都置 true，循环永远不停。检查所有insert调用，确保只在真正新增元素时标记变化。

4.3 现象：分析表冲突，但文法看起来没问题

先查左递归。E -> E + T这种直接左递归会让 FIRST(E) 包含 FIRST(E)，自己和自己冲突。改成E -> T E'，E' -> + T E' | ε。再查公共左因子，比如两条产生式右部开头相同，需要提取成新非终结符。这两步是 LL(1) 的硬门槛，绕不过去。

4.4 现象：分析时栈顶是终结符但和输入不匹配，直接失败

常见原因是输入分词没处理好。比如输入id + id，如果按字符读，i、d会被拆开。必须按词法单元分词，id作为一个整体。另外检查$是不是只加了一次，重复加会导致提前匹配结束。建议在parse入口打印 tokens 列表，肉眼确认一遍。

4.5 现象：ε 产生式导致栈操作异常

如果产生式右部是 ε，压栈时不能把"ε"压进去，否则栈顶永远匹配不上。代码里if (*it != EPSILON)就是干这个的。另外分析表填充时，ε 产生式要填在 FOLLOW 集对应的列上，不是 FIRST 集。这两处搞混，分析器要么死循环，要么直接报错。

5. 进阶技巧：用文件驱动文法并做批量验证

把文法硬编码在main里只能算 demo。实际用的时候，我会把文法写成文本文件，每行一条产生式，|分隔候选式，ε用epsilon代替避免编码问题。读入后先做左递归消除和左因子提取，再算集合、建表、跑测试用例。

// grammar.txt 示例 // E -> T E' // E' -> + T E' | epsilon // T -> F T' // T' -> * F T' | epsilon // F -> ( E ) | id void loadGrammarFromFile(const std::string& path, Grammar& g) { std::ifstream fin(path); std::string line; while (std::getline(fin, line)) { if (line.empty() || line[0] == '/') continue; // 把 epsilon 统一替换成 ε size_t pos; while ((pos = line.find("epsilon")) != std::string::npos) { line.replace(pos, 7, EPSILON); } g.addProduction(line); } g.finalize(); }

批量验证的做法是准备一组「合法输入」和「非法输入」，合法输入必须全部返回 true，非法输入必须全部返回 false。我一般会写一个简单的测试循环：

std::vector<std::string> valid = {"id + id", "id * id", "( id + id ) * id"}; std::vector<std::string> invalid = {"id +", "+ id", "id id"}; for (auto& s : valid) { if (!parse(s, g)) std::cerr << "合法输入被拒: " << s << "\n"; } for (auto& s : invalid) { if (parse(s, g)) std::cerr << "非法输入被收: " << s << "\n"; }

参数上唯一要调的是分词逻辑。如果文法里的终结符包含多字符，比如==、<=，分词时得按最长匹配来，不能简单按空格切。我习惯在parse之前先跑一遍词法分析，把输入转成 token 序列再送进去，这样分析器只关心 token 类型，不关心原始字符。

最后说个血泪经验：LL(1) 的调试成本主要在集合计算阶段，分析表一旦建对，后面基本不会错。所以每算完一个集合，打印出来和手算结果对一遍，比后面拿着错误分析表到处找 bug 省事得多。希望帮到你。

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