CFG消除空产生式C++代码

以下是一份使用 C++ 实现的消除空产生式的代码：

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

// 用于存储产生式
struct Production {
    string left;
    string right;

    Production(string l, string r) : left(l), right(r) {}
};

vector<Production> productions; // 存储 CFG 的所有产生式
set<char> nullable; // 存储所有可空的符号
set<string> visited; // 存储已经访问过的产生式，避免重复访问

// 判断一个符号是否可空
bool isNullable(char symbol) {
    return nullable.count(symbol) > 0;
}

// 判断一个产生式是否可空
bool isNullable(const string& str) {
    for (char c : str) {
        if (!isNullable(c)) {
            return false;
        }
    }
    return true;
}

// 判断一个产生式是否已经被访问过
bool hasVisited(const string& str) {
    return visited.count(str) > 0;
}

// 计算所有可空的符号
void calculateNullable() {
    bool changed = true;
    while (changed) {
        changed = false;
        for (auto& p : productions) {
            if (isNullable(p.right)) {
                if (!isNullable(p.left[0])) {
                    nullable.insert(p.left[0]);
                    changed = true;
                }
            }
        }
    }
}

// 将一个字符串中的所有可空符号去除
void removeNullable(string& str) {
    string result;
    for (char c : str) {
        if (!isNullable(c)) {
            result += c;
        }
    }
    str = result;
}

// 生成新的产生式，去除其中的可空符号
void generateNewProduction(const Production& p, const string& str, vector<Production>& newProductions) {
    string newStr = str;
    removeNullable(newStr);
    if (!newStr.empty()) {
        newProductions.emplace_back(p.left, newStr);
    }
}

// 处理可空产生式
void handleNullableProductions() {
    vector<Production> newProductions;
    for (auto& p : productions) {
        if (isNullable(p.right)) {
            generateNewProduction(p, "", newProductions);
            for (int i = 0; i < p.right.size(); i++) {
                if (isNullable(p.right[i])) {
                    string subStr = p.right.substr(0, i) + p.right.substr(i + 1);
                    generateNewProduction(p, subStr, newProductions);
                }
            }
        }
    }
    productions.insert(productions.end(), newProductions.begin(), newProductions.end());
}

// 消除 CFG 中的空产生式
void eliminateNullProductions() {
    calculateNullable();
    handleNullableProductions();
    set<string> newProductions;
    for (auto& p : productions) {
        if (hasVisited(p.right)) {
            continue;
        }
        visited.insert(p.right);
        newProductions.insert(p.right);
    }
    productions.clear();
    for (auto& p : newProductions) {
        productions.emplace_back("S", p);
    }
}

// 测试代码
int main() {
    productions.emplace_back("S", "ABCD");
    productions.emplace_back("A", "aA|a");
    productions.emplace_back("B", "bB|b");
    productions.emplace_back("C", "cC|c");
    productions.emplace_back("D", "dD|d|");

    eliminateNullProductions();

    for (auto& p : productions) {
        cout << p.left << " -> " << p.right << endl;
    }

    return 0;
}

该代码实现了从 CFG 中消除空产生式的算法。它首先计算出所有可空的符号，然后处理所有可空的产生式，生成新的产生式，并将其中的可空符号去除。最后，它将产生式中的重复项合并，并将它们存储到一个新的 vector 中。