当前位置：首页 > news >正文

从FIRST/FOLLOW到预测分析表：LL(1)文法C++实现核心代码解析

news 2026/7/13 23:36:40

从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: vector<Production> productions; // 所有产生式 unordered_set<char> nonTerminals; // 非终结符集合 unordered_set<char> 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 vector<Production>& getProductions() const { return productions; } // 获取非终结符集合 const unordered_set<char>& getNonTerminals() const { return nonTerminals; } // 获取终结符集合 const unordered_set<char>& 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_map<char, unordered_set<char>> firstSets; unordered_map<char, 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_map<char, unordered_set<char>>& getFirstSets() const { return firstSets; } // 获取nullable表 const unordered_map<char, bool>& getNullable() const { return nullable; } };

这段代码实现了两个关键算法：

calculateNullable()：确定哪些非终结符可以推导出空串
calculateFirstSets()：计算所有符号的FIRST集合

算法采用迭代方式，直到集合不再变化为止。对于产生式A → BCD，FIRST(A)包含：

FIRST(B)中所有非ε符号
如果B可推导出ε，则继续加入FIRST(C)的非ε符号
以此类推，如果所有符号都可推导出ε，则加入ε

3. FOLLOW集合的计算方法

FOLLOW集合告诉我们哪些终结符可能出现在某个非终结符的后面。以下是计算FOLLOW集合的实现：

class LL1Analyzer { // ... 前面的代码不变 private: unordered_map<char, unordered_set<char>> 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(); // 情况1：A → αBβ，将FIRST(β)-{ε}加入FOLLOW(B) if (i + 1 < right.size()) { char next = right[i+1]; 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); } } } } // 情况2：A → α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_map<char, unordered_set<char>>& getFollowSets() const { return followSets; } };

FOLLOW集合的计算需要考虑两种主要情况：

非终结符后有符号：将后面符号的FIRST集(除ε外)加入当前非终结符的FOLLOW集
非终结符在末尾：将产生式左部的FOLLOW集加入当前非终结符的FOLLOW集

算法同样采用迭代方式，直到所有FOLLOW集不再变化。

4. SELECT集合与预测分析表构建

SELECT集合结合了FIRST和FOLLOW集合，用于确定在特定情况下应该使用哪个产生式。以下是实现代码：

class LL1Analyzer { // ... 前面的代码不变 private: unordered_map<int, unordered_set<char>> selectSets; unordered_map<char, unordered_map<char, int>> parsingTable; // 计算SELECT集合 void calculateSelectSets() { for (size_t i = 0; i < grammar.getProductions().size(); ++i) { const auto& prod = grammar.getProductions()[i]; unordered_set<char> 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_map<char, unordered_map<char, int>>& getParsingTable() const { return parsingTable; } // 打印预测分析表 void printParsingTable() const { cout << "预测分析表：" << endl; cout << "非终结符\\终结符\t"; // 收集所有终结符(包括$) unordered_set<char> 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_map<char, unordered_map<char, int>>& parsingTable; public: Parser(const Grammar& g, const unordered_map<char, unordered_map<char, int>>& table) : grammar(g), parsingTable(table) {} // 分析输入字符串 bool parse(const string& input) { stack<char> 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 stack<char>& stk, const string& input, size_t pos) { stack<char> 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 = "id+id*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) { stack<char> 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; }

这个改进版本在遇到错误时会输出错误信息，跳过当前输入符号并继续分析，最后返回是否发现错误。

查看全文

http://www.jsqmd.com/news/1183520/