用C++手搓一个LL(1)语法分析器：从文法文件到预测分析表的完整实现

用C手搓一个LL(1)语法分析器从文法文件到预测分析表的完整实现当你在IDE里敲下g compiler.cpp -o parser时终端输出的可能不只是二进制文件——而是一个正在成形的语言翻译官。LL(1)分析器就像编译器的语法质检员用栈和表格默默检查每个代码语句是否遵守编程语言的语法规则。今天我们要用C从零构建这个质检系统过程中你会看到教科书上的First/Follow集如何变成递归函数预测分析表怎样用STL的map巧妙实现。1. 工程化设计五大核心类的封装艺术好的架构是成功的一半。我们采用面向对象思想将文法要素封装成五个高度内聚的类class VN { // 非终结符管家 private: setstring symbols; // 用红黑树存储自动排序去重 public: void addSymbol(const string sym) { symbols.insert(sym); } bool isVN(const string str) const { return symbols.find(str) ! symbols.end(); } };VT类的设计暗藏玄机——终结符需要特殊处理空串εclass VT { private: setstring symbols; public: void addEpsilon() { symbols.insert(ε); } bool isTerminal(const string str) const { return str ε || symbols.find(str) ! symbols.end(); } };产生式类P采用双容器设计左部用vector保持顺序右部用vectorvector支持多候选class P { private: vectorstring leftParts; // 产生式左部 vectorvectorstring rightParts; // 右部候选集 public: void addProduction(const string left, const vectorstring right) { leftParts.push_back(left); rightParts.push_back(right); } };预测分析表Table是核心大脑我们用嵌套map实现高效查找class Table { private: mappairstring, string, int predictionTable; // 非终结符, 终结符 → 产生式编号 public: void addEntry(const string vn, const string vt, int prodIndex) { predictionTable[{vn, vt}] prodIndex; } };2. 文法文件的智能读取策略处理输入文件时采用状态模式解析不同区段。关键技巧是用istringstream分割字符串配合getline的换行检测void loadGrammar(const string filename) { ifstream file(filename); string line; int state 0; // 0:VN数 1:VN集 2:VT数... while(getline(file, line)) { istringstream iss(line); string token; switch(state) { case 0: vn.setCount(stoi(line)); break; case 1: while(iss token) vn.addSymbol(token); break; // 其他状态处理... } } }常见坑点警示编码问题会导致读取失败建议用file.imbue(locale(en_US.UTF-8))显式指定UTF-8 Windows换行符(\r\n)可能引发解析错误可用line.erase(line.find_last_not_of(\r)1)处理3. First集计算的递归魔法计算First集时递归下降算法是最直观的实现方式。注意处理ε传播的特殊情况setstring computeFirst(const string symbol) { setstring result; if(vt.isTerminal(symbol)) { // 终结符的First就是它自身 result.insert(symbol); return result; } for(int i0; iproductions.count(); i) { if(productions.leftAt(i) symbol) { auto right productions.rightAt(i); bool canEpsilon true; for(auto s : right) { auto first computeFirst(s); result.insert(first.begin(), first.end()); if(!first.count(ε)) { canEpsilon false; break; } } if(canEpsilon) result.insert(ε); } } return result; }优化技巧使用memoization缓存已计算结果对左递归文法需要特殊检测避免无限递归4. Follow集构建的依赖追踪Follow集计算需要处理三种传播场景开始符号包含#产生式A→αBβ时Follow(B)包含First(β)当β可推导出ε时Follow(B)还要包含Follow(A)setstring computeFollow(const string symbol) { setstring result; if(symbol startSymbol) result.insert(#); for(auto prod : productions) { auto right prod.right; for(int i0; iright.size(); i) { if(right[i] symbol) { if(i1 right.size()) { // 情况2 auto firstBeta computeFirst(right[i1]); result.insert(firstBeta.begin(), firstBeta.end()); if(firstBeta.count(ε)) { // 情况3 auto followA computeFollow(prod.left); result.insert(followA.begin(), followA.end()); } } else { // A→αB型 auto followA computeFollow(prod.left); result.insert(followA.begin(), followA.end()); } } } } result.erase(ε); // Follow集不包含ε return result; }5. 预测分析表的黄金构建法则构建预测表时Select集的计算是关键枢纽。我们采用两阶段填充法确保正确性void buildPredictionTable() { // 第一阶段处理非ε产生式 for(int i0; iproductions.count(); i) { auto first computeFirst(productions.rightAt(i)[0]); for(auto term : first) { if(term ! ε) { table.addEntry(productions.leftAt(i), term, i); } } } // 第二阶段处理ε产生式 for(int i0; iproductions.count(); i) { if(productions.rightAt(i)[0] ε) { auto follow computeFollow(productions.leftAt(i)); for(auto term : follow) { table.addEntry(productions.leftAt(i), term, i); } } } }冲突检测在添加表项时检查是否已存在条目这是判断文法是否LL(1)的重要依据。6. 分析栈驱动的语法检查引擎分析器核心是一个双指针有限状态机用栈结构实现推导过程void parse(const vectorstring input) { stackstring stk; stk.push(#); stk.push(startSymbol); int ip 0; // 输入指针 while(!stk.empty()) { string top stk.top(); stk.pop(); if(top #) { // 终止条件 if(input[ip] #) cout Accept!; else cout Error: unexpected end; break; } if(vt.isTerminal(top)) { // 终结符匹配 if(top input[ip]) ip; else { /* 错误处理 */ } } else { // 非终结符推导 int prodIdx table.getEntry(top, input[ip]); if(prodIdx -1) { /* 错误处理 */ } auto right productions.rightAt(prodIdx); if(right[0] ! ε) { // 逆序压栈 for(auto it right.rbegin(); it ! right.rend(); it) { stk.push(*it); } } } } }调试技巧在每次栈操作后打印当前栈内容和剩余输入可以清晰观察分析过程。7. 实战中的性能优化策略当处理复杂文法时可能需要这些优化手段符号索引化用整型ID代替字符串存储mapstring, int symbolToId; // 符号→唯一ID vectorstring idToSymbol; // ID→符号并行计算First/Follow集的计算可多线程处理vectorfuturesetstring futures; for(auto vn : vnSet) { futures.push_back(async(computeFirst, vn)); }增量更新当文法修改时只重新计算受影响的部分可视化调试生成DOT语言描述的分析过程图digraph parse { node [shapebox]; Stack: S# - Stack: aT# [label输入a]; }在实现这个分析器的过程中最让我惊喜的是STL容器的强大表现——set自动去重特性完美契合集合运算需求map的O(1)查找让预测表查询效率极高。记得第一次看到分析器成功识别嵌套括号表达式时那种我创造了语言规则的成就感至今难忘。