给出自底向上的语法分析程序的实验代码

下面是一个简单的自底向上的语法分析程序的实验代码，使用了C++语言和STL库：

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

// 定义文法符号类型
enum SymbolType {
    TERMINAL,   // 终结符
    NONTERMINAL // 非终结符
};

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

// 定义产生式结构体
struct Production {
    Symbol left;                // 产生式左部
    vector<Symbol> right;       // 产生式右部
    bool operator==(const Production &p) const {
        return left.name == p.left.name && left.type == p.left.type && right == p.right;
    }
};

// 定义状态结构体
struct State {
    int id;                     // 状态编号
    vector<Production> items;   // 项目集
    map<Symbol, int> gotos;     // GOTO函数
    map<Symbol, int> actions;   // ACTION函数
};

// 定义语法分析表类型
typedef vector<State> Table;

// 定义终结符集合
const vector<string> TERMINALS = {"id", "+", "-", "*", "/", "(", ")", "$"};

// 定义非终结符集合
const vector<string> NONTERMINALS = {"E", "T", "F"};

// 定义文法产生式集合
const vector<Production> PRODUCTIONS = {
    {{"E", NONTERMINAL}, {{"T", NONTERMINAL}, {"E'", NONTERMINAL}}},
    {{"E'", NONTERMINAL}, {{"+", TERMINAL}, {"T", NONTERMINAL}, {"E'", NONTERMINAL}}},
    {{"E'", NONTERMINAL}, {{"-", TERMINAL}, {"T", NONTERMINAL}, {"E'", NONTERMINAL}}},
    {{"E'", NONTERMINAL}, {}},
    {{"T", NONTERMINAL}, {{"F", NONTERMINAL}, {"T'", NONTERMINAL}}},
    {{"T'", NONTERMINAL}, {{"*", TERMINAL}, {"F", NONTERMINAL}, {"T'", NONTERMINAL}}},
    {{"T'", NONTERMINAL}, {{"/", TERMINAL}, {"F", NONTERMINAL}, {"T'", NONTERMINAL}}},
    {{"T'", NONTERMINAL}, {}},
    {{"F", NONTERMINAL}, {{"(", TERMINAL}, {"E", NONTERMINAL}, {")", TERMINAL}}},
    {{"F", NONTERMINAL}, {{"id", TERMINAL}}}
};

// 获取文法符号类型
SymbolType getSymbolType(const string &symbolName) {
    if (find(TERMINALS.begin(), TERMINALS.end(), symbolName) != TERMINALS.end()) {
        return TERMINAL;
    } else if (find(NONTERMINALS.begin(), NONTERMINALS.end(), symbolName) != NONTERMINALS.end()) {
        return NONTERMINAL;
    } else {
        return NONTERMINAL; // 默认为非终结符
    }
}

// 获取文法符号
Symbol getSymbol(const string &symbolName) {
    return {getSymbolType(symbolName), symbolName};
}

// 获取所有文法符号
vector<Symbol> getAllSymbols() {
    vector<Symbol> symbols;
    for (const auto &symbolName : TERMINALS) {
        symbols.push_back(getSymbol(symbolName));
    }
    for (const auto &symbolName : NONTERMINALS) {
        symbols.push_back(getSymbol(symbolName));
    }
    return symbols;
}

// 获取所有文法产生式左部符号
vector<Symbol> getAllProductionLefts() {
    vector<Symbol> lefts;
    for (const auto &production : PRODUCTIONS) {
        lefts.push_back(production.left);
    }
    return lefts;
}

// 获取所有文法产生式右部符号
vector<Symbol> getAllProductionRights() {
    vector<Symbol> rights;
    for (const auto &production : PRODUCTIONS) {
        for (const auto &symbol : production.right) {
            rights.push_back(symbol);
        }
    }
    return rights;
}

// 获取所有项目集
vector<vector<Production>> getAllItemSets() {
    // 计算所有产生式
    vector<Production> allProductions(PRODUCTIONS);
    for (const auto &left : getAllProductionLefts()) {
        allProductions.push_back({left, {Symbol{"$", TERMINAL}}});
    }

    // 计算所有项目集
    vector<vector<Production>> itemSets;
    for (const auto &production : allProductions) {
        for (size_t i = 0; i <= production.right.size(); i++) {
            vector<Symbol> lookaheads;
            if (i < production.right.size()) {
                lookaheads.push_back(production.right[i]);
            } else {
                lookaheads.push_back(Symbol{"$", TERMINAL});
            }
            Production item = {production.left, {production.right.begin(), production.right.begin() + i}};
            item.right.push_back(Symbol{"·", NONTERMINAL});
            item.right.insert(item.right.end(), production.right.begin() + i, production.right.end());
            itemSets.push_back({item});
        }
    }
    return itemSets;
}

// 计算CLOSURE函数
vector<Production> closure(const vector<Production> &items) {
    vector<Production> closureItems = items;
    bool flag = true;
    while (flag) {
        flag = false;
        for (const auto &item : closureItems) {
            auto dotPos = find(item.right.begin(), item.right.end(), Symbol{"·", NONTERMINAL});
            if (dotPos != item.right.end() - 1) {
                Symbol nextSymbol = *(dotPos + 1);
                if (nextSymbol.type == NONTERMINAL) {
                    for (const auto &production : PRODUCTIONS) {
                        if (production.left.name == nextSymbol.name) {
                            Production newItem = {production.left, {Symbol{"·", NONTERMINAL}}};
                            newItem.right.insert(newItem.right.end(), production.right.begin(), production.right.end());
                            if (find(closureItems.begin(), closureItems.end(), newItem) == closureItems.end()) {
                                closureItems.push_back(newItem);
                                flag = true;
                            }
                        }
                    }
                }
            }
        }
    }
    return closureItems;
}

// 计算GOTO函数
vector<Production> goTo(const vector<Production> &items, const Symbol &symbol) {
    vector<Production> resultItems;
    for (const auto &item : items) {
        auto dotPos = find(item.right.begin(), item.right.end(), Symbol{"·", NONTERMINAL});
        if (dotPos != item.right.end() - 1 && *(dotPos + 1) == symbol) {
            Production newItem = {item.left, item.right};
            swap(newItem.right[dotPos - item.right.begin()], newItem.right[dotPos - item.right.begin() + 1]);
            resultItems.push_back(newItem);
        }
    }
    return closure(resultItems);
}

// 计算文法的LR(0)自动机
Table buildLR0Table() {
    vector<vector<Production>> itemSets = getAllItemSets();
    Table table;
    int id = 0;
    stack<int> stateStack;
    stateStack.push(0);
    while (!stateStack.empty()) {
        int stateId = stateStack.top();
        stateStack.pop();
        if (stateId >= table.size()) {
            table.resize(stateId + 1);
        }
        auto &state = table[stateId];
        state.id = stateId;
        state.items = itemSets[stateId];
        for (const auto &symbol : getAllSymbols()) {
            if (symbol.type == TERMINAL) {
                auto it = find(TERMINALS.begin(), TERMINALS.end(), symbol.name);
                if (it == TERMINALS.end()) {
                    continue;
                }
            }
            auto itemSet = goTo(state.items, symbol);
            if (!itemSet.empty()) {
                auto it = find(itemSets.begin(), itemSets.end(), itemSet);
                int nextStateId;
                if (it != itemSets.end()) {
                    nextStateId = it - itemSets.begin();
                } else {
                    nextStateId = itemSets.size();
                    itemSets.push_back(itemSet);
                    stateStack.push(nextStateId);
                }
                if (symbol.type == TERMINAL) {
                    state.actions[symbol] = nextStateId;
                } else {
                    state.gotos[symbol] = nextStateId;
                }
            }
        }
    }
    return table;
}

// 输出文法
void printGrammar() {
    cout << "Grammar:" << endl;
    for (const auto &production : PRODUCTIONS) {
        cout << production.left.name << " ->";
        for (const auto &symbol : production.right) {
            cout << " " << symbol.name;
        }
        cout << endl;
    }
}

// 输出所有项目集
void printItemSets(const vector<vector<Production>> &itemSets) {
    cout << "Item sets:" << endl;
    for (size_t i = 0; i < itemSets.size(); i++) {
        cout << "I" << i << ":" << endl;
        for (const auto &item : itemSets[i]) {
            cout << "  " << item.left.name << " ->";
            for (const auto &symbol : item.right) {
                cout << " " << symbol.name;
            }
            cout << endl;
        }
    }
}

// 输出LR(0)自动机
void printLR0Table(const Table &table) {
    cout << "LR(0) table:" << endl;
    cout << "State\t";
    for (const auto &symbol : getAllSymbols()) {
        cout << symbol.name << "\t";
    }
    cout << endl;
    for (const auto &state : table) {
        cout << state.id << "\t";
        for (const auto &symbol : getAllSymbols()) {
            if (symbol.type == TERMINAL) {
                auto it = state.actions.find(symbol);
                if (it != state.actions.end()) {
                    cout << "s" << it->second << "\t";
                } else {
                    cout << "\t";
                }
            } else {
                auto it = state.gotos.find(symbol);
                if (it != state.gotos.end()) {
                    cout << it->second << "\t";
                } else {
                    cout << "\t";
                }
            }
        }
        cout << endl;
    }
}

// 分析输入串
bool analyzeInput(const string &input, const Table &table) {
    stack<int> stateStack;
    stateStack.push(0);
    size_t i = 0;
    while (true) {
        int stateId = stateStack.top();
        auto &state = table[stateId];
        auto it = find(TERMINALS.begin(), TERMINALS.end(), state.actions.begin()->first.name);
        if (it == TERMINALS.end()) {
            break;
        }
        if (state.actions.empty() || i > input.size()) {
            return false;
        }
        auto action = state.actions.begin()->second;
        if (action > 0) {
            stateStack.push(action);
            i++;
        } else if (action < 0) {
            auto production = PRODUCTIONS[-action - 1];
            for (size_t j = 0; j < production.right.size(); j++) {
                stateStack.pop();
            }
            stateId = stateStack.top();
            auto &newState = table[stateId];
            auto gotoIt = newState.gotos.find(production.left);
            if (gotoIt == newState.gotos.end()) {
                return false;
            }
            stateStack.push(gotoIt->second);
            cout << production.left.name << " ->";
            for (const auto &symbol : production.right) {
                cout << " " << symbol.name;
            }
            cout << endl;
        } else {
            return i == input.size();
        }
    }
    return false;
}

// 测试
void test() {
    printGrammar();
    auto itemSets = getAllItemSets();
    printItemSets(itemSets);
    auto table = buildLR0Table();
    printLR0Table(table);
    string input;
    cout << "Input a string to analyze: ";
    cin >> input;
    if (analyzeInput(input, table)) {
        cout << "The input string can be recognized." << endl;
    } else {
        cout << "The input string cannot be recognized." << endl;
    }
}

int main() {
    test();
    return 0;
}

该程序实现了一个LR(0)语法分析器，使用了自底向上的语法分析方法，包括以下功能：

- 定义文法符号和文法产生式类型；
- 定义LR(0)自动机状态类型；
- 定义语法分析表类型；
- 定义终结符集合、非终结符集合和文法产生式集合；
- 计算所有项目集和GOTO函数；
- 计算CLOSURE函数；
- 计算LR(0)自动机；
- 对输入串进行语法分析。

需要注意的是，该程序只适用于简单的算术表达式文法，对于其他文法需要进行相应的修改。