从零构建LL(1)语法分析器：C++11实战指南

当你第一次翻开编译原理教材，看到那些晦涩的FIRST集、FOLLOW集和预测分析表时，是否感到一阵眩晕？别担心，这不是你一个人的困扰。本文将带你用C++11从零开始实现一个完整的LL(1)预测分析器，通过200行左右的代码，把抽象的理论转化为可运行的实践。我们会避开教科书的复杂证明，专注于"怎么做"和"为什么这么做"，让你在动手实践中真正理解语法分析的核心思想。

1. 环境准备与项目配置

1.1 工具链选择

我们选择现代C++开发环境，确保代码简洁且高效：

# 推荐环境配置 g++ --version # 需要8.3.0及以上版本 cmake --version # 推荐3.15+

1.2 项目结构设计

采用模块化设计，将不同功能分离到独立文件中：

ll1-parser/ ├── include/ │ ├── grammar.h # 文法相关数据结构 │ └── parser.h # 分析器接口 ├── src/ │ ├── grammar.cpp # 文法操作实现 │ └── parser.cpp # 分析器核心逻辑 └── main.cpp # 示例用法

关键依赖：我们仅使用C++11标准库中的几个关键组件：

• <unordered_set>用于高效集合操作
• <unordered_map>存储分析表
• <vector>管理产生式规则

2. 文法表示与初始化

2.1 文法数据结构设计

用结构体清晰表示文法要素：

struct Grammar { std::unordered_set<char> non_terminals; // 非终结符集合 std::unordered_set<char> terminals; // 终结符集合 std::vector<std::pair<char, std::string>> productions; // 产生式规则 char start_symbol; // 开始符号 char epsilon = '$'; // 空串表示 };

2.2 从文件加载文法

示例规则文件rules.txt格式：

E A T B F # 非终结符 + * ( ) i # 终结符 E TA # 产生式规则 A +TA A $ T FB B *FB B $ F (E) F i

对应的加载函数实现：

Grammar load_grammar(const std::string& filename) { Grammar g; std::ifstream file(filename); // 解析非终结符和终结符 // 解析产生式规则 return g; }

3. 核心算法实现

3.1 FIRST集计算

FIRST集的计算遵循递归规则：

1. 若X是终结符，FIRST(X) = {X}
2. 若X→ε是产生式，则ε ∈ FIRST(X)
3. 若X→Y₁Y₂...Yₖ，则：
   • 将FIRST(Y₁)的非ε元素加入FIRST(X)
   • 若Y₁能推导出ε，则继续考虑Y₂，依此类推

std::unordered_map<char, std::unordered_set<char>> compute_first(const Grammar& g) { std::unordered_map<char, std::unordered_set<char>> first_sets; bool changed; do { changed = false; for (const auto& prod : g.productions) { char lhs = prod.first; const auto& rhs = prod.second; // 实现上述算法规则 } } while (changed); return first_sets; }

3.2 FOLLOW集计算

FOLLOW集算法要点：

注意：计算FOLLOW集前必须先完成FIRST集计算

std::unordered_map<char, std::unordered_set<char>> compute_follow( const Grammar& g, const std::unordered_map<char, std::unordered_set<char>>& first_sets) { std::unordered_map<char, std::unordered_set<char>> follow_sets; // 初始化开始符号的FOLLOW集 follow_sets[g.start_symbol].insert('#'); bool changed; do { changed = false; for (const auto& prod : g.productions) { char lhs = prod.first; const auto& rhs = prod.second; // 实现FOLLOW集计算规则 } } while (changed); return follow_sets; }

4. 预测分析表构建

4.1 表结构设计

使用双层哈希表实现稀疏矩阵：

using PredictTable = std::unordered_map< char, std::unordered_map<char, std::string> >;

4.2 填表算法

对每个产生式A→α：

1. 对FIRST(α)中的每个终结符a，将A→α加入M[A,a]
2. 若ε ∈ FIRST(α)，则对FOLLOW(A)中的每个终结符b，将A→α加入M[A,b]

PredictTable build_predict_table( const Grammar& g, const std::unordered_map<char, std::unordered_set<char>>& first_sets, const std::unordered_map<char, std::unordered_set<char>>& follow_sets) { PredictTable table; for (const auto& prod : g.productions) { char A = prod.first; const std::string& alpha = prod.second; // 计算FIRST(alpha) auto first_alpha = compute_string_first(alpha, first_sets); // 规则1 for (char a : first_alpha) { if (a != g.epsilon) { table[A][a] = alpha; } } // 规则2 if (first_alpha.count(g.epsilon)) { for (char b : follow_sets.at(A)) { table[A][b] = alpha; } } } return table; }

5. 分析器实现与测试

5.1 总控程序算法

bool parse( const std::string& input, const Grammar& g, const PredictTable& table) { std::stack<char> stk; stk.push('#'); stk.push(g.start_symbol); size_t pos = 0; while (!stk.empty()) { char top = stk.top(); char lookahead = pos < input.size() ? input[pos] : '#'; if (g.terminals.count(top) || top == '#') { if (top == lookahead) { stk.pop(); pos++; } else { return false; // 匹配失败 } } else { if (!table.count(top) || !table.at(top).count(lookahead)) { return false; // 分析表无条目 } const std::string& production = table.at(top).at(lookahead); stk.pop(); if (production != "$") { // 非空产生式 for (auto it = production.rbegin(); it != production.rend(); ++it) { stk.push(*it); } } } } return true; }

5.2 测试案例验证

创建测试用例验证分析器：

void run_tests() { Grammar g = load_grammar("rules.txt"); auto first = compute_first(g); auto follow = compute_follow(g, first); auto table = build_predict_table(g, first, follow); assert(parse("i+i*i", g, table) == true); assert(parse("i*", g, table) == false); // 更多测试用例... }

6. 常见问题与调试技巧

6.1 典型错误排查

1. FIRST集计算不完整：

   • 现象：分析表缺失有效条目
   • 检查：确保递归计算所有可能的推导

2. FOLLOW集循环依赖：

   • 现象：程序陷入无限循环
   • 解决：使用changed标志控制迭代

3. 分析表冲突：

   • 现象：同一单元格有多个产生式
   • 原因：文法不是LL(1)文法

6.2 调试日志输出

在关键步骤添加日志输出：

void debug_print(const PredictTable& table) { for (const auto& [non_term, row] : table) { std::cout << non_term << ":\n"; for (const auto& [term, prod] : row) { std::cout << " " << term << " -> " << non_term << "→" << prod << "\n"; } } }

7. 性能优化与扩展

7.1 内存优化技巧

1. 使用std::string_view避免字符串拷贝
2. 用位集表示终结符集合
3. 预分配哈希表容量

7.2 扩展方向

1. 错误恢复机制
2. 语法树生成
3. 支持更复杂的文法类型

在实现过程中，最让我印象深刻的是预测分析表的构建过程。当第一次看到自己编写的分析器正确识别出复杂表达式时，那种成就感是单纯学习理论无法比拟的。建议读者尝试为这个基础版本添加错误恢复功能，这能让你更深入理解实际编译器的处理逻辑。