上下文无关文法的化简C++代码

以下是一个基于递归下降分析法的上下文无关文法化简的C++代码示例：

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

// 定义产生式结构体
struct Production {
    char left; // 左部非终结符
    string right; // 右部符号串
};

string input; // 存储输入的字符串
vector<Production> productions; // 存储所有产生式
unordered_set<char> nullable; // 存储所有可空非终结符

bool isNullable(char c) {
    return nullable.find(c) != nullable.end();
}

void eliminateNullable() {
    // 找出所有可以直接推导出空串的产生式，将它们从产生式集合中删除
    for (auto it = productions.begin(); it != productions.end(); ) {
        if (it->right.empty()) {
            it = productions.erase(it);
        } else {
            ++it;
        }
    }

    // 对于剩下的产生式集合中的每个非终结符，找出所有可以通过一系列推导过程得到空串的产生式，将这些产生式中该非终结符的出现位置全部替换成空串
    bool updated = true;
    while (updated) {
        updated = false;
        for (auto& p : productions) {
            if (isNullable(p.left)) {
                continue;
            }
            bool allNullable = true;
            for (char c : p.right) {
                if (!isNullable(c)) {
                    allNullable = false;
                    break;
                }
            }
            if (allNullable) {
                nullable.insert(p.left);
                updated = true;
            }
        }
        for (auto& p : productions) {
            string newRight = "";
            for (char c : p.right) {
                if (!isNullable(c)) {
                    newRight += c;
                }
            }
            if (newRight != p.right) {
                p.right = newRight;
                updated = true;
            }
        }
    }
}

void printProductions() {
    cout << "产生式集合：" << endl;
    for (auto& p : productions) {
        cout << p.left << " -> " << p.right << endl;
    }
}

int main() {
    // 输入产生式数量和每个产生式
    int n;
    cout << "请输入产生式数量：" << endl;
    cin >> n;
    cout << "请依次输入每个产生式（左部非终结符和右部符号串之间用 -> 分隔）：" << endl;
    for (int i = 0; i < n; i++) {
        char left;
        string right;
        cin >> left;
        cin.ignore(2, '>');
        getline(cin, right);
        productions.push_back({left, right});
    }

    eliminateNullable();
    printProductions();

    return 0;
}

在这个示例中，我们先读入产生式数量和每个产生式，然后通过 eliminateNullable 函数进行文法化简，最后输出化简后的产生式集合。在 eliminateNullable 函数中，我们首先找出所有可以直接推导出空串的产生式，将它们从产生式集合中删除；然后对于剩下的产生式集合中的每个非终结符，找出所有可以通过一系列推导过程得到空串的产生式，将这些产生式中该非终结符的出现位置全部替换成空串；最后重复这个过程，直到没有新的产生式可以替换。