编译原理求first集，代码，c++语言

以下是 C++ 代码实现，同样采用了递归计算的方式：

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

using namespace std;

// 文法符号类型
enum class SymbolType {
    Terminal,   // 终结符
    Nonterminal // 非终结符
};

// 文法符号
struct Symbol {
    string name;    // 符号名称
    SymbolType type; // 符号类型

    // 构造函数
    Symbol(string n, SymbolType t) : name(n), type(t) {}

    // 判断符号是否相等
    bool operator==(const Symbol& other) const {
        return name == other.name && type == other.type;
    }
};

// 哈希函数
namespace std {
    template<>
    struct hash<Symbol> {
        size_t operator()(const Symbol& s) const {
            return hash<string>()(s.name) ^ hash<int>()(static_cast<int>(s.type));
        }
    };
}

// 产生式
struct Production {
    Symbol left;    // 左部符号
    vector<Symbol> right;   // 右部符号

    // 构造函数
    Production(Symbol l, vector<Symbol> r) : left(l), right(r) {}
};

// 文法
class Grammar {
public:
    unordered_set<Symbol> terminals;    // 终结符集合
    unordered_set<Symbol> nonterminals; // 非终结符集合
    vector<Production> productions;     // 产生式集合
    Symbol epsilon;                     // 空串符号

    // 构造函数
    Grammar() {
        epsilon = Symbol("epsilon", SymbolType::Terminal);
    }

    // 添加终结符
    void add_terminal(Symbol s) {
        terminals.insert(s);
    }

    // 添加非终结符
    void add_nonterminal(Symbol s) {
        nonterminals.insert(s);
    }

    // 添加产生式
    void add_production(Production p) {
        productions.push_back(p);
    }

    // 获取某个符号能够推导出的 FIRST 集合
    unordered_set<Symbol> get_first_set(Symbol s) {
        unordered_set<Symbol> first_set;
        if (s.type == SymbolType::Terminal) {
            // 终结符的 FIRST 集合就是它本身
            first_set.insert(s);
        }
        else {
            // 非终结符的 FIRST 集合需要根据产生式进行计算
            for (auto& production : productions) {
                if (production.left == s) {
                    Symbol next_symbol;
                    // 循环计算产生式右部符号的 FIRST 集合
                    for (auto& right_symbol : production.right) {
                        auto right_first_set = get_first_set(right_symbol);
                        first_set.insert(right_first_set.begin(), right_first_set.end());
                        if (right_first_set.find(epsilon) == right_first_set.end()) {
                            // 如果当前符号不能推导出 epsilon，则停止计算
                            break;
                        }
                    }
                }
            }
        }
        return first_set;
    }
};

int main() {
    // 构造一个文法对象
    Grammar grammar;
    Symbol s("S", SymbolType::Nonterminal);
    Symbol a("a", SymbolType::Terminal);
    Symbol b("b", SymbolType::Terminal);
    Symbol c("c", SymbolType::Terminal);
    grammar.add_nonterminal(s);
    grammar.add_terminal(a);
    grammar.add_terminal(b);
    grammar.add_terminal(c);
    grammar.add_production(Production(s, {a, b}));
    grammar.add_production(Production(s, {a, s}));
    grammar.add_production(Production(s, {c}));
    grammar.add_production(Production(s, {grammar.epsilon}));

    // 计算 S 的 FIRST 集合
    auto first_set = grammar.get_first_set(s);
    for (auto& symbol : first_set) {
        cout << symbol.name << " ";
    }
    cout << endl;

    return 0;
}

这里的 `Grammar` 类表示一个文法对象，包含终结符、非终结符和产生式等信息。计算 `get_first_set` 方法中，我们使用递归的方式计算 FIRST 集合。对于终结符，它的 FIRST 集合就是它本身；对于非终结符，我们需要根据产生式进行计算，递归获取每个右部符号的 FIRST 集合，并将它们合并起来。如果一个符号能够推导出 epsilon，则需要继续考虑它后面的符号，直到找到一个不能推导出 epsilon 的符号为止。最后返回每个符号的 FIRST 集合即可。