从FIRST/FOLLOW到预测分析表LL(1)文法C实现核心代码解析在编译器构建的领域中语法分析器扮演着至关重要的角色。它如同一位严谨的语法检察官负责检查源代码是否符合编程语言的语法规则。而LL(1)分析器作为自顶向下分析的代表以其高效和直观的特点成为许多编译器前端的选择。本文将深入探讨如何用C实现LL(1)文法的核心算法从基础集合计算到预测分析表的构建最终完成一个可运行的语法分析器。1. 文法表示与数据结构设计实现LL(1)分析器的第一步是设计合适的数据结构来表示文法。在C中我们可以利用STL容器来高效地存储和操作文法规则。#include iostream #include vector #include unordered_map #include unordered_set #include string using namespace std; // 文法产生式结构体 struct Production { char left; // 左部非终结符 string right; // 右部符号串 Production(char l, string r) : left(l), right(r) {} }; class Grammar { private: vectorProduction productions; // 所有产生式 unordered_setchar nonTerminals; // 非终结符集合 unordered_setchar terminals; // 终结符集合 char startSymbol; // 开始符号 public: // 添加产生式 void addProduction(char left, string right) { productions.emplace_back(left, right); nonTerminals.insert(left); for (char c : right) { if (isupper(c)) nonTerminals.insert(c); else if (c ! ε) terminals.insert(c); } } // 设置开始符号 void setStartSymbol(char start) { startSymbol start; } // 获取所有产生式 const vectorProduction getProductions() const { return productions; } // 获取非终结符集合 const unordered_setchar getNonTerminals() const { return nonTerminals; } // 获取终结符集合 const unordered_setchar getTerminals() const { return terminals; } // 获取开始符号 char getStartSymbol() const { return startSymbol; } };这个Grammar类提供了文法的基本表示包括产生式存储使用vector存储所有产生式符号分类用unordered_set分别存储非终结符和终结符开始符号标记明确文法的入口点提示在实际应用中ε(空串)通常用特殊符号表示这里我们使用ε字符。注意在计算时需要特别处理这种情况。2. FIRST集合的计算算法FIRST集合是LL(1)分析的基础它告诉我们每个非终结符可能推导出的首个终结符是什么。以下是计算FIRST集合的核心代码class LL1Analyzer { private: Grammar grammar; unordered_mapchar, unordered_setchar firstSets; unordered_mapchar, bool nullable; // 计算哪些非终结符可以推导出空串 void calculateNullable() { bool changed; do { changed false; for (const auto prod : grammar.getProductions()) { if (prod.right ε) { if (!nullable[prod.left]) { nullable[prod.left] true; changed true; } continue; } bool allNullable true; for (char c : prod.right) { if (!isupper(c) || !nullable[c]) { allNullable false; break; } } if (allNullable !nullable[prod.left]) { nullable[prod.left] true; changed true; } } } while (changed); } // 计算FIRST集合 void calculateFirstSets() { // 初始化终结符的FIRST集合 for (char c : grammar.getTerminals()) { firstSets[c].insert(c); } bool changed; do { changed false; for (const auto prod : grammar.getProductions()) { char left prod.left; const string right prod.right; if (right ε) continue; size_t oldSize firstSets[left].size(); // 处理产生式右部的每个符号 bool breakLoop false; for (char c : right) { // 如果是终结符直接加入并停止 if (!isupper(c)) { firstSets[left].insert(c); breakLoop true; break; } // 加入非终结符的FIRST集(除ε外) for (char terminal : firstSets[c]) { if (terminal ! ε) { firstSets[left].insert(terminal); } } // 如果当前符号不能推导出ε停止 if (!nullable[c]) { breakLoop true; break; } } // 如果所有符号都能推导出ε加入ε if (!breakLoop) { firstSets[left].insert(ε); } if (firstSets[left].size() ! oldSize) { changed true; } } } while (changed); } public: LL1Analyzer(const Grammar g) : grammar(g) { // 初始化nullable表 for (char nt : grammar.getNonTerminals()) { nullable[nt] false; } calculateNullable(); calculateFirstSets(); } // 获取FIRST集合 const unordered_mapchar, unordered_setchar getFirstSets() const { return firstSets; } // 获取nullable表 const unordered_mapchar, bool getNullable() const { return nullable; } };这段代码实现了两个关键算法calculateNullable()确定哪些非终结符可以推导出空串calculateFirstSets()计算所有符号的FIRST集合算法采用迭代方式直到集合不再变化为止。对于产生式A → BCDFIRST(A)包含FIRST(B)中所有非ε符号如果B可推导出ε则继续加入FIRST(C)的非ε符号以此类推如果所有符号都可推导出ε则加入ε3. FOLLOW集合的计算方法FOLLOW集合告诉我们哪些终结符可能出现在某个非终结符的后面。以下是计算FOLLOW集合的实现class LL1Analyzer { // ... 前面的代码不变 private: unordered_mapchar, unordered_setchar followSets; // 计算FOLLOW集合 void calculateFollowSets() { // 初始化开始符号加入结束符$ followSets[grammar.getStartSymbol()].insert($); bool changed; do { changed false; for (const auto prod : grammar.getProductions()) { const string right prod.right; for (size_t i 0; i right.size(); i) { char current right[i]; if (!isupper(current)) continue; // 只处理非终结符 size_t oldSize followSets[current].size(); // 情况1A → αBβ将FIRST(β)-{ε}加入FOLLOW(B) if (i 1 right.size()) { char next right[i1]; if (!isupper(next)) { // β是终结符 followSets[current].insert(next); } else { // β是非终结符 for (char c : firstSets.at(next)) { if (c ! ε) { followSets[current].insert(c); } } // 如果β可推导出ε还需要加入FOLLOW(A) if (nullable.at(next)) { for (char c : followSets.at(prod.left)) { followSets[current].insert(c); } } } } // 情况2A → αB将FOLLOW(A)加入FOLLOW(B) else { for (char c : followSets.at(prod.left)) { followSets[current].insert(c); } } if (followSets[current].size() ! oldSize) { changed true; } } } } while (changed); } public: LL1Analyzer(const Grammar g) : grammar(g) { // ... 前面的初始化代码 calculateNullable(); calculateFirstSets(); calculateFollowSets(); // 新增 } // 获取FOLLOW集合 const unordered_mapchar, unordered_setchar getFollowSets() const { return followSets; } };FOLLOW集合的计算需要考虑两种主要情况非终结符后有符号将后面符号的FIRST集(除ε外)加入当前非终结符的FOLLOW集非终结符在末尾将产生式左部的FOLLOW集加入当前非终结符的FOLLOW集算法同样采用迭代方式直到所有FOLLOW集不再变化。4. SELECT集合与预测分析表构建SELECT集合结合了FIRST和FOLLOW集合用于确定在特定情况下应该使用哪个产生式。以下是实现代码class LL1Analyzer { // ... 前面的代码不变 private: unordered_mapint, unordered_setchar selectSets; unordered_mapchar, unordered_mapchar, int parsingTable; // 计算SELECT集合 void calculateSelectSets() { for (size_t i 0; i grammar.getProductions().size(); i) { const auto prod grammar.getProductions()[i]; unordered_setchar firstOfRight; bool allNullable true; // 计算产生式右部的FIRST集 for (char c : prod.right) { if (c ε) break; if (!isupper(c)) { // 终结符 firstOfRight.insert(c); allNullable false; break; } // 加入非终结符的FIRST集(除ε外) for (char terminal : firstSets.at(c)) { if (terminal ! ε) { firstOfRight.insert(terminal); } } if (!nullable.at(c)) { allNullable false; break; } } if (allNullable || prod.right ε) { // SELECT(A→α) (FIRST(α)-{ε}) ∪ FOLLOW(A) for (char c : firstOfRight) { selectSets[i].insert(c); } for (char c : followSets.at(prod.left)) { selectSets[i].insert(c); } } else { // SELECT(A→α) FIRST(α) selectSets[i] firstOfRight; } } } // 构建预测分析表 void buildParsingTable() { for (const auto entry : selectSets) { int prodIndex entry.first; const auto selectSet entry.second; char left grammar.getProductions()[prodIndex].left; for (char terminal : selectSet) { // 检查冲突 if (parsingTable[left].count(terminal) parsingTable[left][terminal] ! prodIndex) { cerr 文法不是LL(1)文法存在冲突 endl; return; } parsingTable[left][terminal] prodIndex; } } } public: LL1Analyzer(const Grammar g) : grammar(g) { // ... 前面的初始化代码 calculateNullable(); calculateFirstSets(); calculateFollowSets(); calculateSelectSets(); buildParsingTable(); } // 获取预测分析表 const unordered_mapchar, unordered_mapchar, int getParsingTable() const { return parsingTable; } // 打印预测分析表 void printParsingTable() const { cout 预测分析表 endl; cout 非终结符\\终结符\t; // 收集所有终结符(包括$) unordered_setchar allTerminals grammar.getTerminals(); allTerminals.insert($); // 打印表头 for (char t : allTerminals) { cout t \t; } cout endl; // 打印表内容 for (char nt : grammar.getNonTerminals()) { cout nt \t\t; for (char t : allTerminals) { if (parsingTable.at(nt).count(t)) { int prodIndex parsingTable.at(nt).at(t); const auto prod grammar.getProductions()[prodIndex]; cout prod.left → prod.right \t; } else { cout \t; } } cout endl; } } };SELECT集合的计算规则对于产生式A→α如果α不能推导出ε则SELECT(A→α) FIRST(α)如果α可以推导出ε则SELECT(A→α) (FIRST(α)-{ε}) ∪ FOLLOW(A)预测分析表的构建则是将每个产生式根据其SELECT集合放入相应的表项中。如果发现冲突(同一表项有多个产生式)则说明文法不是LL(1)文法。5. 语法分析器的实现有了预测分析表我们就可以实现语法分析器了。以下是基于栈的LL(1)分析器实现class Parser { private: const Grammar grammar; const unordered_mapchar, unordered_mapchar, int parsingTable; public: Parser(const Grammar g, const unordered_mapchar, unordered_mapchar, int table) : grammar(g), parsingTable(table) {} // 分析输入字符串 bool parse(const string input) { stackchar stk; stk.push($); stk.push(grammar.getStartSymbol()); size_t inputPos 0; char lookahead inputPos input.size() ? input[inputPos] : $; cout 分析过程 endl; printStep(stk, input, inputPos); while (!stk.empty()) { char top stk.top(); if (top $) { if (lookahead $) return true; else break; } if (!isupper(top)) { // 终结符 if (top lookahead) { stk.pop(); inputPos; lookahead inputPos input.size() ? input[inputPos] : $; } else { break; } } else { // 非终结符 if (parsingTable.at(top).count(lookahead)) { int prodIndex parsingTable.at(top).at(lookahead); const auto prod grammar.getProductions()[prodIndex]; stk.pop(); if (prod.right ! ε) { for (auto it prod.right.rbegin(); it ! prod.right.rend(); it) { stk.push(*it); } } } else { break; } } printStep(stk, input, inputPos); } return false; } private: // 打印分析步骤 void printStep(const stackchar stk, const string input, size_t pos) { stackchar temp stk; string stackStr; while (!temp.empty()) { stackStr temp.top(); temp.pop(); } string inputStr input.substr(pos); if (inputStr.empty()) inputStr $; cout 栈: stackStr \t输入: inputStr endl; } };分析器的工作流程初始化栈压入开始符号和结束符$读取输入的下一个字符作为lookahead根据栈顶元素和lookahead决定下一步操作栈顶是终结符匹配则弹出否则报错栈顶是非终结符查预测分析表用对应产生式右部替换栈顶重复直到栈为空或发现错误6. 完整示例与测试让我们用一个完整的例子来测试我们的实现int main() { // 定义文法E → TE // E → TE | ε // T → FT // T → *FT | ε // F → (E) | id Grammar g; g.setStartSymbol(E); g.addProduction(E, TX); g.addProduction(X, TX); g.addProduction(X, ε); g.addProduction(T, FY); g.addProduction(Y, *FY); g.addProduction(Y, ε); g.addProduction(F, (E)); g.addProduction(F, id); // 构建LL(1)分析器 LL1Analyzer analyzer(g); // 打印FIRST和FOLLOW集合 cout FIRST集合 endl; for (const auto entry : analyzer.getFirstSets()) { cout entry.first : {; for (char c : entry.second) { cout c ; } cout } endl; } cout \nFOLLOW集合 endl; for (const auto entry : analyzer.getFollowSets()) { cout entry.first : {; for (char c : entry.second) { cout c ; } cout } endl; } // 打印预测分析表 analyzer.printParsingTable(); // 测试分析器 Parser parser(g, analyzer.getParsingTable()); string input1 idid*id; cout \n分析输入: input1 endl; bool result1 parser.parse(input1); cout (result1 ? 接受 : 拒绝) endl; string input2 id*id; cout \n分析输入: input2 endl; bool result2 parser.parse(input2); cout (result2 ? 接受 : 拒绝) endl; return 0; }这个示例展示了如何定义算术表达式的LL(1)文法计算并打印FIRST和FOLLOW集合构建和显示预测分析表测试语法分析器对合法和非法输入的分析7. 工程实践中的优化与扩展在实际编译器项目中LL(1)分析器的实现还可以进行以下优化和扩展错误恢复当遇到语法错误时可以尝试跳过错误部分并继续分析更高效的数据结构对于大型文法可以使用更紧凑的数据结构存储分析表自动文法转换实现左递归消除和左公因子提取的自动化语义动作在分析过程中嵌入语义分析代码生成抽象语法树在规约时构建语法树而非仅仅验证语法以下是一个简单的错误恢复实现示例bool Parser::parseWithRecovery(const string input) { stackchar stk; stk.push($); stk.push(grammar.getStartSymbol()); size_t inputPos 0; char lookahead inputPos input.size() ? input[inputPos] : $; bool hasError false; while (!stk.empty()) { char top stk.top(); if (top $) { if (lookahead $) return !hasError; else { // 错误输入未结束但栈已空 cerr 错误输入未结束 endl; inputPos; lookahead inputPos input.size() ? input[inputPos] : $; hasError true; continue; } } if (!isupper(top)) { // 终结符 if (top lookahead) { stk.pop(); inputPos; lookahead inputPos input.size() ? input[inputPos] : $; } else { // 错误不匹配的终结符 cerr 错误期望 top 但找到 lookahead endl; inputPos; lookahead inputPos input.size() ? input[inputPos] : $; hasError true; } } else { // 非终结符 if (parsingTable.at(top).count(lookahead)) { int prodIndex parsingTable.at(top).at(lookahead); const auto prod grammar.getProductions()[prodIndex]; stk.pop(); if (prod.right ! ε) { for (auto it prod.right.rbegin(); it ! prod.right.rend(); it) { stk.push(*it); } } } else { // 错误无可用产生式 cerr 错误非终结符 top 无法处理输入 lookahead endl; inputPos; lookahead inputPos input.size() ? input[inputPos] : $; hasError true; } } } return !hasError; }这个改进版本在遇到错误时会输出错误信息跳过当前输入符号并继续分析最后返回是否发现错误。