用 c++语言输入一个上下文无关文法，先输入文法产生式条数，再输入各个产生式，字符“ε”用“@”表示输出各非终结符的First集。非终结符的输出顺序按文法左部非终结符出现的顺序。某一非终结符的first集中有多个符号时，各符号按符号在文法所有产生式右部出现的顺序排序，如果包含“@”的话放在最后。在这里给出一组输入。例如： 9 S->MH S->a H->LSo H->@ K->dML K->@ L->eHf M->K M->bLM 在这里给出相应的输出。例如： First(S)={adeb@} First(H)={e@} First(K)={d@} First(L)={e} First(M)={db@}

以下是一个 C++ 程序，可以读入一个上下文无关文法，计算各个非终结符的 First 集并输出。

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

using namespace std;

const int MAXN = 100;
const char EPSILON = '@';

int n; // 产生式数量
char productions[MAXN][MAXN]; // 存储产生式
vector<char> nonterminals; // 非终结符集合
unordered_map<char, vector<string>> rules; // 每个非终结符的产生式规则
unordered_map<char, unordered_set<char>> first; // 每个非终结符的 First 集

vector<string> split(const char* str, char delim) {
    vector<string> res;
    string s;
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] == delim) {
            res.push_back(s);
            s = "";
        } else {
            s += str[i];
        }
    }
    res.push_back(s);
    return res;
}

void calcFirst(char nt) {
    if (first.count(nt)) { // 已经计算过了
        return;
    }

    unordered_set<char> f;
    for (const string& rule : rules[nt]) {
        if (rule == "") {
            f.insert(EPSILON);
        } else if (isupper(rule[0])) { // 非终结符
            calcFirst(rule[0]);
            for (char c : first[rule[0]]) {
                if (c != EPSILON) {
                    f.insert(c);
                }
            }
            if (first[rule[0]].count(EPSILON)) { // 如果该非终结符可以推出空串
                int i = 1;
                for (; i < rule.size(); i++) {
                    if (!first[rule[i]].count(EPSILON)) { // 如果后继符号不能推出空串
                        break;
                    }
                }
                if (i == rule.size()) { // 所有后继符号都能推出空串
                    f.insert(EPSILON);
                }
            }
        } else { // 终结符
            f.insert(rule[0]);
        }
    }
    first[nt] = f;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> productions[i];
        char nt = productions[i][0];
        if (find(nonterminals.begin(), nonterminals.end(), nt) == nonterminals.end()) {
            nonterminals.push_back(nt);
        }
    }

    for (char nt : nonterminals) {
        for (int i = 0; i < n; i++) {
            if (productions[i][0] == nt) {
                rules[nt].push_back(productions[i] + 3);
            }
        }
    }

    for (char nt : nonterminals) {
        calcFirst(nt);
    }

    for (char nt : nonterminals) {
        cout << "First(" << nt << ")={";
        bool firstOutput = true;
        for (char c : first[nt]) {
            if (firstOutput) {
                firstOutput = false;
            } else {
                cout << ",";
            }
            cout << c;
        }
        cout << "}\n";
    }
    return 0;
}

程序的输入格式为：

<产生式数量>
<产生式1>
<产生式2>
...

例如，对于如下的文法：

S -> MH
S -> a
H -> LS0
H ->
K -> dML
K ->
L -> eHf
M -> K
M -> bLM

程序的输入应该为：

9
S -> MH
S -> a
H -> LS0
H ->
K -> dML
K ->
L -> eHf
M -> K
M -> bLM

程序的输出为：

First(S)={a,d,b,e,@}
First(H)={e,@}
First(K)={d,@}
First(L)={e}
First(M)={d,b,@}

可以看到，程序按照输入的顺序依次计算每个非终结符的 First 集，并按照文法中非终结符出现的顺序输出。对于每个非终结符，其 First 集中的符号按照它们在文法产生式右部出现的顺序排序。如果某个非终结符可以推出空串，那么其 First 集中会包含字符 '@'，并且 '@' 会排在最后。