LL(1) 语法分析实战：C++ 实现 First/Follow 集与预测分析表（附 500 行源码）

LL(1) 语法分析器从理论到 C 工程实践在编译器的构建过程中语法分析器扮演着至关重要的角色。LL(1) 作为最经典的自顶向下分析方法以其清晰的逻辑结构和高效的线性时间复杂度成为许多编译器前端的选择。本文将带你深入 LL(1) 分析器的实现细节通过 500 行 C 代码的完整实现揭示 First/Follow 集计算与预测分析表构建的核心算法。1. LL(1) 分析器的核心架构LL(1) 分析器的实现可分为三个关键模块文法预处理处理文法中的空产生式、左递归等问题集合计算构建 First 集和 Follow 集分析引擎基于预测分析表的语法分析典型的类设计如下class Grammar { setstring nonTerminals; // 非终结符集合 setstring terminals; // 终结符集合 string startSymbol; // 开始符号 mapstring, vectorvectorstring productions; // 产生式规则 void eliminateLeftRecursion(); void leftFactor(); }; class LL1Analyzer { mapstring, setstring firstSets; mapstring, setstring followSets; mappairstring, string, vectorstring parsingTable; void computeFirstSets(); void computeFollowSets(); void buildParsingTable(); public: bool parse(const vectorstring input); };2. First 集计算的两种实现范式2.1 递归求解法递归方法直接根据 First 集的定义实现setstring LL1Analyzer::computeFirst(const string symbol) { if (isTerminal(symbol)) { return {symbol}; // 终结符的 First 集是其本身 } setstring first; for (auto production : productions[symbol]) { bool allNullable true; for (auto s : production) { auto sFirst computeFirst(s); first.insert(sFirst.begin(), sFirst.end()); if (sFirst.find(ε) sFirst.end()) { allNullable false; break; } } if (allNullable) { first.insert(ε); } } return first; }2.2 迭代求解法迭代法通过不断传播 First 元素直到收敛void LL1Analyzer::computeFirstSets() { // 初始化 for (auto nt : nonTerminals) { firstSets[nt] {}; } bool changed; do { changed false; for (auto [head, bodies] : productions) { for (auto body : bodies) { size_t oldSize firstSets[head].size(); bool nullable true; for (auto symbol : body) { if (isTerminal(symbol)) { firstSets[head].insert(symbol); nullable false; break; } firstSets[head].insert( firstSets[symbol].begin(), firstSets[symbol].end() ); if (firstSets[symbol].find(ε) firstSets[symbol].end()) { nullable false; break; } } if (nullable) { firstSets[head].insert(ε); } if (firstSets[head].size() oldSize) { changed true; } } } } while (changed); }两种方法的对比特性递归法迭代法实现复杂度简单直观需要显式处理收敛条件性能可能重复计算效率更高适用场景小型文法大型复杂文法空产生式处理需要额外标记自然融入迭代过程3. Follow 集计算的关键技巧Follow 集计算需要特别注意文法开始符号和产生式右部末尾的情况void LL1Analyzer::computeFollowSets() { // 初始化 for (auto nt : nonTerminals) { followSets[nt] {}; } followSets[startSymbol].insert($); // 结束符号 bool changed; do { changed false; for (auto [head, bodies] : productions) { for (auto body : bodies) { for (size_t i 0; i body.size(); i) { if (!isNonTerminal(body[i])) continue; string A body[i]; size_t oldSize followSets[A].size(); // 情况1A后面跟着符号B if (i 1 body.size()) { string B body[i1]; auto firstB firstSets[B]; followSets[A].insert(firstB.begin(), firstB.end()); followSets[A].erase(ε); // 如果B可推出空串需要加上Follow(head) if (firstB.find(ε) ! firstB.end()) { followSets[A].insert( followSets[head].begin(), followSets[head].end() ); } } // 情况2A是产生式最后一个符号 else { followSets[A].insert( followSets[head].begin(), followSets[head].end() ); } if (followSets[A].size() oldSize) { changed true; } } } } } while (changed); }注意Follow 集计算必须等待 First 集完全计算完成后才能开始且需要多次迭代直到不再变化。4. 预测分析表的构建策略预测分析表是 LL(1) 分析器的核心数据结构我们使用unordered_map实现高效的二维查找void LL1Analyzer::buildParsingTable() { for (auto [head, bodies] : productions) { for (auto body : bodies) { auto firstAlpha computeSequenceFirst(body); // 规则1对于First(α)中的每个终结符a加入M[A,a] for (auto a : firstAlpha) { if (a ! ε) { parsingTable[{head, a}] body; } } // 规则2如果ε在First(α)中对Follow(A)的每个b加入M[A,b] if (firstAlpha.find(ε) ! firstAlpha.end()) { for (auto b : followSets[head]) { parsingTable[{head, b}] body; } } } } // 处理错误条目可选 for (auto nt : nonTerminals) { for (auto t : terminals) { if (parsingTable.find({nt, t}) parsingTable.end()) { parsingTable[{nt, t}] {error}; // 同步记号 } } } }预测分析表的可视化表示以简单算术表达式文法为例非终结符id*()$EE→TEE→TEEE→TEE→εE→εTT→FTT→FTTT→εT→*FTT→εT→εFF→idF→(E)5. 语法分析引擎的实现分析引擎使用栈结构管理推导过程bool LL1Analyzer::parse(const vectorstring input) { stackstring stk; stk.push($); stk.push(startSymbol); size_t inputPtr 0; string a input[inputPtr]; while (!stk.empty()) { string X stk.top(); stk.pop(); if (isTerminal(X)) { if (X a) { inputPtr; a inputPtr input.size() ? input[inputPtr] : $; } else { return false; // 不匹配 } } else if (X $) { if (X a) { return true; // 成功 } else { return false; } } else { auto it parsingTable.find({X, a}); if (it parsingTable.end() || it-second[0] error) { return false; // 分析表无条目 } // 逆序压栈 const auto production it-second; if (!(production.size() 1 production[0] ε)) { for (auto it production.rbegin(); it ! production.rend(); it) { stk.push(*it); } } } } return false; }分析过程的追踪输出示例步骤 栈 输入 动作 1 $E idid*id$ E → TE 2 $ET idid*id$ T → FT 3 $ETF idid*id$ F → id 4 $ETid idid*id$ 匹配id 5 $ET id*id$ T → ε 6 $E id*id$ E → TE 7 $ET id*id$ 匹配 8 $ET id*id$ T → FT ...6. 工程实践中的优化技巧6.1 避免递归死循环在计算 First/Follow 集时需要特别处理左递归文法void detectLeftRecursion() { for (auto [head, bodies] : productions) { for (auto body : bodies) { if (!body.empty() body[0] head) { throw runtime_error(直接左递归: head); } } } }6.2 内存优化策略对于大型文法可以采用以下优化// 使用位集表示First/Follow集 class FastSet { bitset256 bits; // 假设终结符不超过256个 public: void add(char c) { bits.set(c); } bool contains(char c) const { return bits.test(c); } // ... 其他集合操作 }; // 生产式编号替代完整产生式 mappairint, int, int compactParsingTable;6.3 错误恢复机制增强分析器的容错能力bool parseWithRecovery(const vectorstring input) { // ... while (!stk.empty()) { // ... 正常分析逻辑 if (分析表无条目) { // 恐慌模式恢复 skipUntil(inputPtr, followSets[X]); stk.pop(); // 弹出X continue; } } // ... }7. 完整项目结构与测试案例项目目录结构建议LL1-Parser/ ├── include/ │ ├── grammar.h # 文法定义与处理 │ ├── ll1_analyzer.h # 核心分析器类 │ └── utils.h # 工具函数 ├── src/ │ ├── main.cpp # 测试程序 │ └── ll1_analyzer.cpp ├── test/ │ ├── arithmetic.txt # 算术表达式文法 │ └── test_cases/ # 测试用例 └── CMakeLists.txt测试文法示例arithmetic.txtE - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id编译与运行mkdir build cd build cmake .. make ./ll1_parser ../test/arithmetic.txt idid*id8. 扩展与进阶方向语法树生成在分析过程中构建具体/抽象语法树错误诊断增强错误定位与提示能力自动化测试构建文法测试框架性能分析对大型文法进行性能剖析// 语法树节点示例 class ASTNode { string type; string value; vectorASTNode children; void print(int indent 0) const { cout string(indent, ) type; if (!value.empty()) cout : value; cout endl; for (auto child : children) { child.print(indent 2); } } };实现完整的 LL(1) 分析器不仅需要理解形式语言理论还需要考虑工程实践中的各种边界条件和性能因素。本文展示的代码框架已在 GitHub 开源项目中经过验证能够正确处理教材中的典型文法案例。