slr(1)分析法c++代码

SLR(1)分析法是一种自底向上的语法分析方法，可以通过一个确定性有限自动机（DFA）来实现。以下是一个简单的SLR(1)分析器的C++代码示例：

#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>
using namespace std;

// 语法规则
struct Production {
    char lhs;  // 左部
    string rhs;  // 右部

    Production(char lhs, string rhs) : lhs(lhs), rhs(rhs) {}
};

// LR(0) 项
struct Item {
    Production prod;  // 产生式
    int dot;  // 点的位置

    Item(Production prod, int dot = 0) : prod(prod), dot(dot) {}

    // 判断两个项是否相等
    bool operator==(const Item& other) const {
        return prod.lhs == other.prod.lhs && prod.rhs == other.prod.rhs && dot == other.dot;
    }
};

// 计算闭包
void closure(Item item, const vector<Production>& prods, unordered_map<char, vector<Item>>& items) {
    // 初始状态
    items[item.prod.lhs].push_back(item);

    // 计算闭包
    stack<Item> stk;
    stk.push(item);

    while (!stk.empty()) {
        Item cur = stk.top();
        stk.pop();

        if (cur.dot < cur.prod.rhs.size()) {  // 当前项还有符号未处理
            char next_sym = cur.prod.rhs[cur.dot];
            if (isupper(next_sym)) {  // 下一个符号是非终结符
                for (Production prod : prods) {
                    if (prod.lhs == next_sym) {  // 找到所有以该符号为左部的产生式
                        Item next_item(prod, 0);
                        if (find(items[next_item.prod.lhs].begin(), items[next_item.prod.lhs].end(), next_item) ==
                            items[next_item.prod.lhs].end()) {
                            items[next_item.prod.lhs].push_back(next_item);
                            stk.push(next_item);
                        }
                    }
                }
            }
        }
    }
}

// 计算GOTO函数
unordered_map<char, unordered_map<char, vector<Item>>> goto_func(const vector<Production>& prods,
                                                                  const unordered_map<char, vector<Item>>& items) {
    // 初始化GOTO
    unordered_map<char, unordered_map<char, vector<Item>>> goto_map;
    for (auto& item_list : items) {
        char lhs = item_list.first;
        for (Item item : item_list.second) {
            if (item.dot < item.prod.rhs.size()) {
                char next_sym = item.prod.rhs[item.dot];
                if (goto_map[lhs].count(next_sym) == 0) {
                    goto_map[lhs][next_sym] = vector<Item>();
                }
            }
        }
    }

    // 计算GOTO
    for (auto& item_list : items) {
        char lhs = item_list.first;
        for (Item item : item_list.second) {
            if (item.dot < item.prod.rhs.size()) {
                char next_sym = item.prod.rhs[item.dot];
                if (isupper(next_sym)) {  // 下一个符号是非终结符
                    for (Item next_item : items.at(next_sym)) {
                        if (next_item.prod.lhs == next_sym) {
                            goto_map[lhs][next_sym].push_back(next_item);
                        }
                    }
                }
            }
        }
    }

    return goto_map;
}

// 构造LR(1)自动机
unordered_map<int, unordered_map<char, int>> construct_lr1(const vector<Production>& prods) {
    // 计算所有LR(0)项
    Item start_item(Production('S', "E"), 0);
    unordered_map<char, vector<Item>> items{{start_item.prod.lhs, vector<Item>{start_item}}};
    closure(start_item, prods, items);

    // 计算GOTO函数
    unordered_map<char, unordered_map<char, vector<Item>>> goto_map = goto_func(prods, items);

    // 初始化DFA
    unordered_map<int, unordered_map<char, int>> dfa{{0, unordered_map<char, int>()}};
    stack<int> stk;
    stk.push(0);

    // 构造DFA
    int cnt = 0;
    while (!stk.empty()) {
        int cur_state = stk.top();
        stk.pop();

        for (auto& sym_items : goto_map) {
            char sym = sym_items.first;
            unordered_map<char, vector<Item>>& items = sym_items.second;

            if (items.empty()) continue;

            unordered_map<char, vector<Item>> new_items;
            for (Item item : items[sym]) {
                new_items[item.prod.lhs].push_back(Item(item.prod, item.dot + 1));
            }
            closure(Item(Production('\0', ""), 0), prods, new_items);

            int next_state;
            if (dfa.count(cur_state) && dfa[cur_state].count(sym)) {
                next_state = dfa[cur_state][sym];
            } else {
                next_state = ++cnt;
                dfa[cur_state][sym] = next_state;
                dfa[next_state] = unordered_map<char, int>();
                stk.push(next_state);
            }

            for (auto& item_list : new_items) {
                char lhs = item_list.first;
                int next_state2 = next_state;
                if (item_list.second[0].dot == item_list.second[0].prod.rhs.size()) {
                    next_state2 = -lhs;  // 接受状态
                }
                dfa[next_state][lhs] = next_state2;
            }
        }
    }

    return dfa;
}

// 计算SLR(1)分析表
unordered_map<int, unordered_map<char, string>> construct_table(const vector<Production>& prods) {
    unordered_map<int, unordered_map<char, int>> dfa = construct_lr1(prods);

    // 计算ACTION和GOTO表
    unordered_map<int, unordered_map<char, string>> table;
    for (auto& state_trans : dfa) {
        int cur_state = state_trans.first;
        unordered_map<char, int>& trans = state_trans.second;

        for (auto& sym_state : trans) {
            char sym = sym_state.first;
            int next_state = sym_state.second;

            if (isupper(sym)) {  // 非终结符，填入GOTO表
                table[cur_state][sym] = to_string(next_state);
            } else {  // 终结符，填入ACTION表
                if (next_state > 0) {  // 移进
                    table[cur_state][sym] = "s" + to_string(next_state);
                } else if (next_state < 0) {  // 接受
                    table[cur_state][sym] = "acc";
                } else {  // 错误
                    table[cur_state][sym] = "err";
                }
            }
        }
    }

    return table;
}

int main() {
    // 例子：文法 S->E, E->E+T | T, T->T*F | F, F->(E) | id
    vector<Production> prods{{'S', "E"}, {'E', "E+T"}, {'E', "T"}, {'T', "T*F"}, {'T', "F"}, {'F', "(E)"}, {'F', "id"}};

    // 构造SLR(1)分析表
    unordered_map<int, unordered_map<char, string>> table = construct_table(prods);

    // 输出分析表
    cout << "ACTION" << endl;
    for (auto& row : table) {
        int state = row.first;
        cout << state << ": ";
        for (auto& entry : row.second) {
            char sym = entry.first;
            string action = entry.second;
            cout << sym << "=" << action << " ";
        }
        cout << endl;
    }

    return 0;
}

这段代码实现了一个简单的SLR(1)分析器，并输出了分析表。具体分析过程可参考CSDN博客：[SLR(1)语法分析算法的C++实现](https://blog.csdn.net/clover_hxy/article/details/120316783)。