LR语法分析器c++

LR语法分析器是一种自底向上的语法分析器，可以用于分析上下文无关文法。下面是一个使用C++实现的LR语法分析器的示例：

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

using namespace std;

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

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

// 定义产生式结构体
struct Production {
    Symbol left;                // 产生式左部
    vector<Symbol> right;       // 产生式右部
};

// 定义LR分析表项结构体
struct LRTableItem {
    char action;                // 动作类型
    int state;                  // 转移状态
};

// 定义LR语法分析器类
class LRParser {
public:
    LRParser(vector<Production> grammar, Symbol startSymbol, map<Symbol, map<Symbol, int>> actionTable, map<int, map<Symbol, int>> gotoTable, Symbol endSymbol);
    bool parse(vector<Symbol> input);

private:
    vector<Production> grammar_;                // 文法
    Symbol startSymbol_;                        // 起始符号
    map<Symbol, map<Symbol, int>> actionTable_;  // 动作表
    map<int, map<Symbol, int>> gotoTable_;      // 转移表
    Symbol endSymbol_;                          // 结束符号
};

// LR语法分析器构造函数
LRParser::LRParser(vector<Production> grammar, Symbol startSymbol, map<Symbol, map<Symbol, int>> actionTable, map<int, map<Symbol, int>> gotoTable, Symbol endSymbol) {
    grammar_ = grammar;
    startSymbol_ = startSymbol;
    actionTable_ = actionTable;
    gotoTable_ = gotoTable;
    endSymbol_ = endSymbol;
}

// LR语法分析器解析函数
bool LRParser::parse(vector<Symbol> input) {
    stack<int> stateStack;      // 状态栈
    stack<Symbol> symbolStack;  // 符号栈
    stateStack.push(0);         // 初始状态为0
    symbolStack.push(endSymbol_); // 符号栈初始为$（结束符号）

    int i = 0;
    while (i < input.size()) {
        int state = stateStack.top();
        Symbol symbol = input[i];
        if (actionTable_[state][symbol] > 0) { // 移进
            stateStack.push(actionTable_[state][symbol]);
            symbolStack.push(symbol);
            i++;
        } else if (actionTable_[state][symbol] < 0) { // 规约
            int productionIndex = -actionTable_[state][symbol];
            Production production = grammar_[productionIndex];
            for (int j = 0; j < production.right.size(); j++) {
                stateStack.pop();
                symbolStack.pop();
            }
            Symbol nonterminal = production.left;
            state = stateStack.top();
            stateStack.push(gotoTable_[state][nonterminal]);
            symbolStack.push(nonterminal);
        } else { // 错误
            return false;
        }
    }

    return true;
}

int main() {
    // 定义文法符号
    Symbol E = {NONTERMINAL, "E"};
    Symbol T = {NONTERMINAL, "T"};
    Symbol F = {NONTERMINAL, "F"};
    Symbol plus = {TERMINAL, "+"};
    Symbol minus = {TERMINAL, "-"};
    Symbol times = {TERMINAL, "*"};
    Symbol divide = {TERMINAL, "/"};
    Symbol lparen = {TERMINAL, "("};
    Symbol rparen = {TERMINAL, ")"};
    Symbol id = {TERMINAL, "id"};
    Symbol num = {TERMINAL, "num"};

    // 定义产生式
    vector<Production> grammar = {
        {E, {E, plus, T}},
        {E, {E, minus, T}},
        {E, {T}},
        {T, {T, times, F}},
        {T, {T, divide, F}},
        {T, {F}},
        {F, {lparen, E, rparen}},
        {F, {id}},
        {F, {num}}
    };

    // 定义LR分析表
    map<Symbol, map<Symbol, int>> actionTable = {
        {{0, plus}, {{TERMINAL, 4}}},
        {{0, minus}, {{TERMINAL, 5}}},
        {{0, id}, {{TERMINAL, 6}}},
        {{0, num}, {{TERMINAL, 7}}},
        {{1, plus}, {{TERMINAL, 0}, {NONTERMINAL, 2}}},
        {{1, minus}, {{TERMINAL, 0}, {NONTERMINAL, 2}}},
        {{1, rparen}, {{TERMINAL, 0}, {NONTERMINAL, 2}}},
        {{1, endSymbol}, {{TERMINAL, 0}, {NONTERMINAL, 2}}},
        {{2, plus}, {{TERMINAL, -1}}},
        {{2, minus}, {{TERMINAL, -1}}},
        {{2, times}, {{TERMINAL, 8}, {NONTERMINAL, 3}}},
        {{2, divide}, {{TERMINAL, 9}, {NONTERMINAL, 3}}},
        {{2, rparen}, {{TERMINAL, -1}}},
        {{2, endSymbol}, {{TERMINAL, -1}}},
        {{3, plus}, {{TERMINAL, -3}}},
        {{3, minus}, {{TERMINAL, -3}}},
        {{3, times}, {{TERMINAL, -3}}},
        {{3, divide}, {{TERMINAL, -3}}},
        {{3, rparen}, {{TERMINAL, -3}}},
        {{3, endSymbol}, {{TERMINAL, -3}}},
        {{4, id}, {{TERMINAL, 6}}},
        {{4, num}, {{TERMINAL, 7}}},
        {{5, id}, {{TERMINAL, 6}}},
        {{5, num}, {{TERMINAL, 7}}},
        {{6, plus}, {{TERMINAL, -6}}},
        {{6, minus}, {{TERMINAL, -6}}},
        {{6, times}, {{TERMINAL, -6}}},
        {{6, divide}, {{TERMINAL, -6}}},
        {{6, rparen}, {{TERMINAL, -6}}},
        {{6, endSymbol}, {{TERMINAL, -6}}},
        {{7, plus}, {{TERMINAL, -7}}},
        {{7, minus}, {{TERMINAL, -7}}},
        {{7, times}, {{TERMINAL, -7}}},
        {{7, divide}, {{TERMINAL, -7}}},
        {{7, rparen}, {{TERMINAL, -7}}},
        {{7, endSymbol}, {{TERMINAL, -7}}}
    };

    map<int, map<Symbol, int>> gotoTable = {
        {0, {{E, 1}, {T, 2}, {F, 3}}},
        {2, {{T, 5}, {F, 3}}},
        {3, {{F, 6}}},
        {8, {{F, 9}}},
        {9, {{F, 10}}}
    };

    // 定义LR语法分析器
    LRParser parser(grammar, E, actionTable, gotoTable, endSymbol_);

    // 进行语法分析
    vector<Symbol> input = {id, plus, id, times, id, endSymbol_};
    bool result = parser.parse(input);
    if (result) {
        cout << "Input is valid." << endl;
    } else {
        cout << "Input is invalid." << endl;
    }

    return 0;
}