用C++写SLR(1)分析器

SLR(1)语法分析器是一种基于状态转换的自底向上语法分析器。下面是一个简单的C++实现示例：

首先，我们需要定义一些数据结构来表示文法、状态和分析表：

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

using namespace std;

// 文法符号结构体
struct Symbol {
    string name;    // 符号名称
    bool is_terminal;   // 是否为终结符
    Symbol(string n, bool t) : name(n), is_terminal(t) {}
};

// 产生式结构体
struct Production {
    Symbol left;    // 产生式左部
    vector<Symbol> right;   // 产生式右部
    Production(Symbol l, vector<Symbol> r) : left(l), right(r) {}
};

// 状态结构体
struct State {
    int id; // 状态ID
    set<Production> kernel; // 内核
    set<Symbol> lookahead;  // 向前看符号
    map<Symbol, int> gotos; // GOTO表
    map<Symbol, int> actions;   // ACTION表
    State(int i) : id(i) {}
};

// 分析表结构体
struct Table {
    map<int, map<Symbol, int>> gotos;   // GOTO表
    map<int, map<Symbol, string>> actions; // ACTION表
};

接下来，我们需要定义一些函数来读入文法、构造状态和分析表：

// 读入文法
vector<Production> read_grammar() {
    vector<Production> grammar;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        int m;
        cin >> m;
        vector<Symbol> right;
        for (int j = 0; j < m; j++) {
            string s;
            cin >> s;
            if (s == "eps") {
                right.push_back(Symbol("", false));
            } else if (s[0] >= 'a' && s[0] <= 'z') {
                right.push_back(Symbol(s, true));
            } else {
                right.push_back(Symbol(s, false));
            }
        }
        grammar.push_back(Production(Symbol(name, false), right));
    }
    return grammar;
}

// 构造闭包
set<Production> closure(set<Production> kernel, vector<Production> grammar) {
    set<Production> closure = kernel;
    bool changed = true;
    while (changed) {
        changed = false;
        for (auto p : closure) {
            if (!p.right.empty() && !p.right[0].is_terminal) {
                for (auto prod : grammar) {
                    if (prod.left.name == p.right[0].name) {
                        Production new_prod = Production(prod.left, prod.right);
                        new_prod.right.insert(new_prod.right.begin(), Symbol("", true));
                        if (closure.find(new_prod) == closure.end()) {
                            closure.insert(new_prod);
                            changed = true;
                        }
                    }
                }
            }
        }
    }
    return closure;
}

// 构造GOTO集合
set<Production> goto_set(set<Production> kernel, Symbol sym, vector<Production> grammar) {
    set<Production> goto_kernel;
    for (auto p : kernel) {
        if (!p.right.empty() && p.right[0].name == sym.name) {
            Production new_p = Production(p.left, vector<Symbol>(p.right.begin() + 1, p.right.end()));
            new_p.right.insert(new_p.right.begin(), Symbol("", true));
            goto_kernel.insert(new_p);
        }
    }
    return closure(goto_kernel, grammar);
}

// 构造状态
State make_state(int id, set<Production> kernel, vector<Production> grammar) {
    State state(id);
    state.kernel = kernel;
    for (auto p : kernel) {
        if (!p.right.empty() && p.right[0].name != "") {
            Symbol sym = p.right[0];
            set<Production> goto_kernel = goto_set(kernel, sym, grammar);
            int goto_id = -1;
            for (auto s : state.kernel) {
                if (s == *goto_kernel.begin()) {
                    goto_id = state.id;
                    break;
                }
            }
            if (goto_id == -1) {
                goto_id = id + 1;
                state.gotos[sym] = goto_id;
            }
        } else {
            state.actions[Symbol("$", true)] = 0;
        }
    }
    for (auto p : closure(kernel, grammar)) {
        if (p.right.empty()) {
            for (auto sym : state.lookahead) {
                state.actions[sym] = -p.left.name.length();
            }
        } else if (p.right.size() == 1 && p.right[0].name == "") {
            for (auto sym : state.lookahead) {
                state.actions[sym] = -p.left.name.length();
            }
        } else if (p.right.empty() || p.right[0].is_terminal) {
            Symbol sym = p.right.empty() ? Symbol("", true) : p.right[0];
            state.actions[sym] = -p.left.name.length();
        } else {
            Symbol sym = p.right[0];
            set<Production> goto_kernel = goto_set(kernel, sym, grammar);
            int goto_id = -1;
            for (auto s : state.kernel) {
                if (s == *goto_kernel.begin()) {
                    goto_id = state.id;
                    break;
                }
            }
            if (goto_id == -1) {
                goto_id = id + 1;
                state.gotos[sym] = goto_id;
            }
        }
    }
    return state;
}

// 构造分析表
Table make_table(vector<Production> grammar) {
    Table table;
    vector<State> states;
    set<Production> kernel = {grammar[0]};
    State start_state = make_state(0, kernel, grammar);
    start_state.lookahead.insert(Symbol("$", true));
    states.push_back(start_state);
    int id = 0;
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < states.size(); i++) {
            State state = states[i];
            for (auto sym : state.lookahead) {
                if (state.actions.find(sym) != state.actions.end()) {
                    continue;
                }
                set<Production> kernel = state.kernel;
                for (auto p : kernel) {
                    if (!p.right.empty() && p.right[0].name == sym.name) {
                        Production new_p = Production(p.left, vector<Symbol>(p.right.begin() + 1, p.right.end()));
                        new_p.right.insert(new_p.right.begin(), Symbol("", true));
                        kernel.insert(new_p);
                    }
                }
                set<Production> closure = make_state(-1, kernel, grammar).kernel;
                if (closure.empty()) {
                    continue;
                }
                bool found = false;
                for (int j = 0; j < states.size(); j++) {
                    if (states[j].kernel == closure) {
                        found = true;
                        state.actions[sym] = j;
                        break;
                    }
                }
                if (!found) {
                    id++;
                    State new_state = make_state(id, closure, grammar);
                    states.push_back(new_state);
                    state.actions[sym] = id;
                    changed = true;
                }
            }
        }
    }
    for (int i = 0; i < states.size(); i++) {
        for (auto sym_goto : states[i].gotos) {
            table.gotos[i][sym_goto.first] = sym_goto.second;
        }
        for (auto sym_action : states[i].actions) {
            if (sym_action.second >= 0) {
                table.actions[i][sym_action.first] = "S" + to_string(sym_action.second);
            } else {
                int r = -sym_action.second;
                table.actions[i][sym_action.first] = "R" + to_string(r);
            }
        }
    }
    return table;
}

最后，我们可以使用上面定义的数据结构和函数来实现分析器：

// SLR(1)分析器
void slr_parser(Table table, vector<Production> grammar, string input) {
    input += "$";
    vector<Symbol> stack = {Symbol("", true), grammar[0].left};
    int pos = 0;
    while (!stack.empty() && pos < input.length()) {
        Symbol top = stack.back();
        if (top.is_terminal) {
            if (top.name == input.substr(pos, top.name.length())) {
                stack.pop_back();
                pos += top.name.length();
            } else {
                cout << "Error!" << endl;
                return;
            }
        } else {
            map<Symbol, string> actions = table.actions[stack[stack.size() - 2].name == "" ? 0 : stoi(stack[stack.size() - 2].name)];
            if (actions.find(Symbol(input.substr(pos), true)) != actions.end()) {
                string action = actions[Symbol(input.substr(pos), true)];
                if (action[0] == 'S') {
                    int state = stoi(action.substr(1));
                    stack.push_back(Symbol(input.substr(pos, 1), true));
                    stack.push_back(Symbol(to_string(state), false));
                    pos++;
                } else {
                    int rule = stoi(action.substr(1));
                    Production prod = grammar[rule - 1];
                    for (int i = 0; i < prod.right.size(); i++) {
                        stack.pop_back();
                        stack.pop_back();
                    }
                    map<Symbol, int> gotos = table.gotos[stoi(stack.back().name)];
                    stack.push_back(prod.left);
                    stack.push_back(Symbol(to_string(gotos[prod.left]), false));
                    cout << prod.left.name << "->";
                    for (auto sym : prod.right) {
                        cout << sym.name << " ";
                    }
                    cout << endl;
                }
            } else {
                cout << "Error!" << endl;
                return;
            }
        }
    }
}

最后，我们可以在main函数中使用这个SLR(1)分析器：

int main() {
    vector<Production> grammar = read_grammar();
    Table table = make_table(grammar);
    string input;
    cin >> input;
    slr_parser(table, grammar, input);
    return 0;
}