文法First集Follow集求解算法c++代码

以下是文法First集和Follow集求解的算法代码示例（基于LL(1)文法）：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

// 定义文法符号类型
enum SymbolType {
    TERMINAL,
    NON_TERMINAL
};

// 定义文法符号结构体
struct Symbol {
    string name;        // 符号名称
    SymbolType type;    // 符号类型
};

// 定义产生式结构体
struct Production {
    Symbol left;                // 左部符号
    vector<Symbol> right;       // 右部符号序列
};

// 定义文法结构体
struct Grammar {
    vector<Production> productions;    // 产生式序列
    Symbol start;                      // 文法起始符号
};

// 计算文法符号的First集
unordered_set<Symbol> computeFirst(const Symbol& symbol, const Grammar& grammar, unordered_map<string, unordered_set<Symbol>>& firstMap) {
    unordered_set<Symbol> firstSet;

    // 如果该符号为终结符，则其First集只包含该符号本身
    if (symbol.type == TERMINAL) {
        firstSet.insert(symbol);
    }
    // 如果该符号为非终结符
    else if (symbol.type == NON_TERMINAL) {
        // 如果该符号的First集已经计算过，则直接返回缓存结果
        if (firstMap.count(symbol.name)) {
            return firstMap[symbol.name];
        }

        // 遍历该符号对应的所有产生式
        for (const auto& production : grammar.productions) {
            // 如果该产生式的左部符号与该符号相同，则计算该产生式右部符号序列的First集
            if (production.left.name == symbol.name) {
                for (const auto& rightSymbol : production.right) {
                    // 计算该符号的右部符号的First集
                    auto rightFirstSet = computeFirst(rightSymbol, grammar, firstMap);
                    // 将该符号的右部符号的First集并入该符号的First集
                    firstSet.insert(rightFirstSet.begin(), rightFirstSet.end());
                    // 如果该符号的右部符号的First集不包含空串，则退出循环
                    if (!rightFirstSet.count(Symbol{"", NON_TERMINAL})) {
                        break;
                    }
                }
            }
        }

        // 缓存该符号的First集
        firstMap[symbol.name] = firstSet;
    }

    return firstSet;
}

// 计算文法符号的Follow集
unordered_set<Symbol> computeFollow(const Symbol& symbol, const Grammar& grammar, unordered_map<string, unordered_set<Symbol>>& firstMap, unordered_map<string, unordered_set<Symbol>>& followMap) {
    unordered_set<Symbol> followSet;

    // 如果该符号为文法起始符号，则将$加入其Follow集
    if (symbol.name == grammar.start.name) {
        followSet.insert(Symbol{"$", TERMINAL});
    }

    // 遍历所有产生式
    for (const auto& production : grammar.productions) {
        // 遍历该产生式右部符号序列，查找该符号的Follow集
        for (auto it = production.right.begin(); it != production.right.end(); it++) {
            // 如果当前符号与目标符号相同
            if (it->name == symbol.name) {
                // 如果目标符号不是该产生式的最后一个符号，则将其后继符号的First集并入其Follow集
                if (next(it) != production.right.end()) {
                    auto nextSymbol = *next(it);
                    auto nextFirstSet = computeFirst(nextSymbol, grammar, firstMap);
                    followSet.insert(nextFirstSet.begin(), nextFirstSet.end());
                    // 如果后继符号的First集包含空串，则将该产生式的左部符号的Follow集加入其Follow集
                    if (nextFirstSet.count(Symbol{"", NON_TERMINAL})) {
                        auto leftFollowSet = computeFollow(production.left, grammar, firstMap, followMap);
                        followSet.insert(leftFollowSet.begin(), leftFollowSet.end());
                    }
                }
                // 如果目标符号是该产生式的最后一个符号，则将该产生式的左部符号的Follow集加入其Follow集
                else {
                    auto leftFollowSet = computeFollow(production.left, grammar, firstMap, followMap);
                    followSet.insert(leftFollowSet.begin(), leftFollowSet.end());
                }
            }
        }
    }

    // 缓存该符号的Follow集
    followMap[symbol.name] = followSet;

    return followSet;
}

int main() {
    // 定义文法
    Grammar grammar{
        {
            {"S", {Symbol{"a", TERMINAL}, Symbol{"B", NON_TERMINAL}}},
            {"B", {Symbol{"S", NON_TERMINAL}, Symbol{"c", TERMINAL}}},
            {"B", {Symbol{"d", TERMINAL}}}
        },
        Symbol{"S", NON_TERMINAL}
    };

    // 计算文法符号的First集
    unordered_map<string, unordered_set<Symbol>> firstMap;
    for (const auto& production : grammar.productions) {
        for (const auto& symbol : production.right) {
            computeFirst(symbol, grammar, firstMap);
        }
    }

    // 输出文法符号的First集
    for (const auto& [name, firstSet] : firstMap) {
        cout << "First(" << name << ") = { ";
        for (const auto& symbol : firstSet) {
            cout << symbol.name << " ";
        }
        cout << "}" << endl;
    }

    // 计算文法符号的Follow集
    unordered_map<string, unordered_set<Symbol>> followMap;
    for (const auto& production : grammar.productions) {
        computeFollow(production.left, grammar, firstMap, followMap);
    }

    // 输出文法符号的Follow集
    for (const auto& [name, followSet] : followMap) {
        cout << "Follow(" << name << ") = { ";
        for (const auto& symbol : followSet) {
            cout << symbol.name << " ";
        }
        cout << "}" << endl;
    }

    return 0;
}