• 日期: 2027-09-26
  • 标签: 常规

以下是完善后的文法和对应的 SLR(1) 分析表以及 C++ 实现：

完善后的文法：

𝑉𝑡 = {+, −,∗,/, , , (, ),[,], 𝑓, 𝑋} 𝑉𝑛 = {S, A, E, T, F}, G[S]: S → f[A] = E A → 𝑋|A, 𝑋 E → E + T|E − T|T T → T ∗ F|T/F|𝐹 F → (E)|𝑋

SLR(1) 分析表：

状态 0： S → ·f[A]=E, $ A → ·𝑋, ,/,$ A → ·A,𝑋, /,$ E → ·E+T, ),+,-,],$ E → ·E-T, ),+,-,],$ E → ·T, ),+,-,],$ T → ·T*F, *,/,(,𝑋,$ T → ·T/F, *,/,(,𝑋,$ T → ·𝐹, *,/,(,𝑋,$ F → ·(E), *,/,(,𝑋,$ F → ·𝑋, *,/,(,),+,-,],/$ 移入 f 到状态 1 移入 𝑋 到状态 3 移入 ( 到状态 6 移入 𝑋 到状态 7 移入 𝑋 到状态 9 移入 𝑋 到状态 10 移入 ) 到状态 11 移入 + 到状态 12 移入 - 到状态 13 移入 * 到状态 14 移入 / 到状态 15 移入 𝑋 到状态 17 移入 , 到状态 18 移入 ] 到状态 19 状态 1： S → f ·[A]=E, $ 移入 [ 到状态 2 状态 2： A → ·𝑋, ,/,$ A → ·A,𝑋, /,$ 移入 𝑋 到状态 3 移入 𝑋 到状态 7 移入 𝑋 到状态 9 移入 𝑋 到状态 10 状态 3： A → 𝑋·, ,/,$ 移入 , 到状态 4 移入 / 到状态 5 移入 $ 到状态 20 状态 4： A → A, ·𝑋, /,$ 移入 𝑋 到状态 3 移入 𝑋 到状态 7 移入 𝑋 到状态 9 移入 𝑋 到状态 10 状态 5： A → A,𝑋·, /,$ 移入 𝑋 到状态 3 移入 𝑋 到状态 7 移入 𝑋 到状态 9 移入 𝑋 到状态 10 状态 6： F → ·(E), *,/,(,𝑋,$ F → ·𝑋, *,/,(,),+,-,],/$ 移入 ( 到状态 6 移入 𝑋 到状态 7 状态 7： F → 𝑋·, ,/,(,),+,-,],/$ 移入 * 到状态 14 移入 / 到状态 15 移入 ( 到状态 6 移入 ) 到状态 21 移入 + 到状态 12 移入 - 到状态 13 移入 ] 到状态 22 状态 8： A → A, ·𝑋, /,$ 移入 𝑋 到状态 9 状态 9： A → A,𝑋·, /,$ 移入 / 到状态 5 移入 $ 到状态 23 状态 10： A → A,𝑋·, /,$ 移入 , 到状态 18 移入 ] 到状态 19 状态 11： E → E+·T, ),+,-,],$ E → E-·T, ),+,-,],$ E → ·T, ),+,-,],$ T → ·TF, *,/,(,𝑋,$ T → ·T/F, *,/,(,𝑋,$ T → ·𝐹, *,/,(,𝑋,$ F → ·(E), *,/,(,𝑋,$ F → ·𝑋, ,/,(,),+,-,],/$ 移入 ( 到状态 6 移入 𝑋 到状态 7 移入 𝐹 到状态 8 移入 𝑋 到状态 9 移入 𝑋 到状态 10 状态 12： E → E+T·, ),+,-,],$ 移入 𝐹 到状态 16 移入 𝑋 到状态 17 移入 ( 到状态 6 状态 13： E → E-T·, ),+,-,],$ 移入 𝐹 到状态 16 移入 𝑋 到状态 17 移入 ( 到状态 6 状态 14： T → T·F, *,/,(,𝑋,$ F → ·(E), *,/,(,𝑋,$ F → ·𝑋, *,/,(,),+,-,],/$ 移入 𝑋 到状态 7 移入 ( 到状态 6 状态 15： T → T/·F, *,/,(,𝑋,$ F → ·(E), *,/,(,𝑋,$ F → ·𝑋, *,/,(,),+,-,],/$ 移入 𝑋 到状态 7 移入 ( 到状态 6 状态 16： F → 𝐹·, *,/,(,),+,-,],/$ 移入 * 到状态 14 移入 / 到状态 15 移入 ) 到状态 24 移入 + 到状态 12 移入 - 到状态 13 移入 ] 到状态 25 状态 17： F → 𝑋·, ,/,(,),+,-,],/$ 移入 * 到状态 14 移入 / 到状态 15 移入 ) 到状态 21 移入 + 到状态 12 移入 - 到状态 13 移入 ] 到状态 22 状态 18： A → A, 𝑋·, /,$ 移入 𝑋 到状态 3 移入 𝑋 到状态 7 移入 𝑋 到状态 9 移入 𝑋 到状态 10 状态 19： S → f[A]=·E, $ E → ·E+T, ),+,-,],$ E → ·E-T, ),+,-,],$ E → ·T, ),+,-,],$ T → ·TF, *,/,(,𝑋,$ T → ·T/F, *,/,(,𝑋,$ T → ·𝐹, *,/,(,𝑋,$ F → ·(E), *,/,(,𝑋,$ F → ·𝑋, ,/,(,),+,-,],/$ 移入 + 到状态 12 移入 - 到状态 13 移入 𝐹 到状态 16 移入 𝑋 到状态 17 移入 ( 到状态 6 状态 20： S → f[A]=E·, $ 移入 $ 到状态 26 状态 21： E → E+T·, ),+,-,],$ E → E-T·, ),+,-,],$ T → T·F, *,/,(,𝑋,$ T → T/·F, *,/,(,𝑋,$ F → (E)·, *,/,(,),+,-,],/$ 移入 𝑋 到状态 7 移入 ( 到状态 6 状态 22： S → f[A]=E·, $ 移入 $ 到状态 27 状态 23： A → A,𝑋·, /,$ 移入 / 到状态 28 状态 24： F → (E)·, *,/,(,),+,-,],$移入 * 到状态 14 移入 / 到状态 15 移入 + 到状态 12 移入 - 到状态 13 移入 ] 到状态 29 状态 25： S → f[A]=E·, $ 移入 $ 到状态 30 状态 26： 接受 状态 27： 出错 状态 28： A → A, ·𝑋, /,$ 移入 𝑋 到状态 9 状态 29： 出错 状态 30： 出错

C++实现：

#include <iostream>
#include <stack>
#include <map>
#include <vector>
#include <string>
using namespace std;

// 定义编程语言中的四元式
struct Quadruple {
    string op; // 操作符
    string arg1; // 源操作数1
    string arg2; // 源操作数2
    string result; // 目标操作数
};

// 定义符号类型
enum SymbolType {
    TERMINAL, // 终结符
    NONTERMINAL, // 非终结符
    END, // 字符串结尾
    ERROR // 错误
};

// 定义符号
struct Symbol {
    SymbolType type; // 符号类型
    int index; // 符号编号
};

// 定义状态
struct State {
    map<int, int> goTo; // 跳转表
    map<int, int> action; // 动作表
};

// 定义文法
SymbolType grammar[5][5] = {
    /*S A E T F*/
    {NONTERMINAL, TERMINAL, ERROR, TERMINAL, NONTERMINAL},
    {ERROR, TERMINAL, ERROR, ERROR, ERROR},
    {NONTERMINAL, TERMINAL, ERROR, TERMINAL, NONTERMINAL},
    {NONTERMINAL, TERMINAL, ERROR, TERMINAL, NONTERMINAL},
    {NONTERMINAL, TERMINAL, ERROR, TERMINAL, TERMINAL}
};

// 定义符号表
map<string, int> symbolTable;

// 定义四元式序列
vector<Quadruple> quadruples;

// 定义符号编号
int index = 0;

// 获取符号编号
int getSymbolIndex(string symbol) {
    if (symbolTable.find(symbol) == symbolTable.end()) {
        symbolTable[symbol] = index++;
    }
    return symbolTable[symbol];
}

// 获取符号类型
SymbolType getSymbolType(string symbol) {
    if (symbol == "+") {
        return TERMINAL;
    } else if (symbol == "-") {
        return TERMINAL;
    } else if (symbol == "*") {
        return TERMINAL;
    } else if (symbol == "/") {
        return TERMINAL;
    } else if (symbol == "(") {
        return TERMINAL;
    } else if (symbol == ")") {
        return TERMINAL;
    } else if (symbol == "[") {
        return TERMINAL;
    } else if (symbol == "]") {
        return TERMINAL;
    } else if (symbol == "f") {
        return TERMINAL;
    } else if (symbol.size() == 1 && symbol[0] >= 'a' && symbol[0] <= 'z') {
        return TERMINAL;
    } else if (symbol == "S") {
        return NONTERMINAL;
    } else if (symbol == "A") {
        return NONTERMINAL;
    } else if (symbol == "E") {
        return NONTERMINAL;
    } else if (symbol == "T") {
        return NONTERMINAL;
    } else if (symbol == "F") {
        return NONTERMINAL;
    } else if (symbol == "$") {
        return END;
    } else {
        return ERROR;
    }
}

// 获取符号
Symbol getSymbol(string symbol) {
    Symbol s;
    s.type = getSymbolType(symbol);
    s.index = getSymbolIndex(symbol);
    return s;
}

// SLR(1)分析表
State states[31];

// 初始化状态
void initState() {
    // 状态0
    states[0].goTo[getSymbolIndex("S")] = 1;
    states[0].goTo[getSymbolIndex("A")] = 2;
    states[0].goTo[getSymbolIndex("E")] = 3;
    states[0].goTo[getSymbolIndex("T")] = 4;
    states[0].goTo[getSymbolIndex("F")] = 5;
    states[0].action[getSymbolIndex("f")] = 6;
    states[0].action[getSymbolIndex("(")] = 13;
    states[0].action[getSymbolIndex("x")] = 12;
    states[0].action[getSymbolIndex("$")] = 26;
    // 状态1
    states[1].action[getSymbolIndex("[")] = 7;
    // 状态2
    states[2].action[getSymbolIndex(",")] = 8;
    states[2].action[getSymbolIndex("]")] = 9;
    // 状态3
    states[3].action[getSymbolIndex("+")] = 14;
    states[3].action[getSymbolIndex("-")] = 15;
    states[3].action[getSymbolIndex(")")] = 14;
    states[3].action[getSymbolIndex("*")] = 14;
    states[3].action[getSymbolIndex("/")] = 14;
    states[3].action[getSymbolIndex("[")] = 14;
    states[3].action[getSymbolIndex(",")] = 14;
    states[3].action[getSymbolIndex("]")] = 14;
    states[3].action[getSymbolIndex("$")] = 14;
    // 状态4
    states[4].action[getSymbolIndex("+")] = 14;
    states[4].action[getSymbolIndex("-")] = 14;
    states[4].action[getSymbolIndex(")")] = 14;
    states[4].action[getSymbolIndex("*")] = 14;
    states[4].action[getSymbolIndex("/")] = 14;
    states[4].action[getSymbolIndex("[")] = 14;
    states[4].action[getSymbolIndex(",")] = 14;
    states[4].action[getSymbolIndex("]")] = 14;
    states[4].action[getSymbolIndex("$")] = 14;
    // 状态5
    states[5].action[getSymbolIndex("+")] = 14;
    states[5].action[getSymbolIndex("-")] = 14;
    states[5].action[getSymbolIndex(")")] = 14;
    states[5].action[getSymbolIndex("*")] = 14;
    states[5].action[getSymbolIndex("/")] = 14;
    states[5].action[getSymbolIndex("[")] = 14;
    states[5].action[getSymbolIndex(",")] = 14;
    states[5].action[getSymbolIndex("]")] = 14;
    states[5].action[getSymbolIndex("$")] = 14;
    // 状态6
    states[6].goTo[getSymbolIndex("A")] = 10;
    // 状态7
    states[7].goTo[getSymbolIndex("E")] = 11;
    // 状态8
    states[8].goTo[getSymbolIndex("A")] = 16;
    // 状态9
    states[9].goTo[getSymbolIndex("E")] = 17;
    // 状态10
    states[10].action[getSymbolIndex(",")] = 8;
    states[10].action[getSymbolIndex("]")] = 9;
    // 状态11
    states[11].action[getSymbolIndex("=")] = 18;
    // 状态12
    states[12].goTo[getSymbolIndex("E")] = 19;
    states[12].goTo[getSymbolIndex("T")] = 20;
    states[12].goTo[getSymbolIndex("F")] = 21;
    states[12].action[getSymbolIndex("(")] = 13;
    states[12].action[getSymbolIndex("x")] = 12;
    // 状态13
    states[13].goTo[getSymbolIndex("E")] = 22;
    states[13].goTo[getSymbolIndex("T")] = 20;
    states[13].goTo[getSymbolIndex("F")] = 21;
    states[13].action[getSymbolIndex("(")] = 13;
    states[13].action[getSymbolIndex("x")] = 12;
    // 状态14
    states[14].goTo[getSymbolIndex("F")] = 23;
    states[14].action[getSymbolIndex("(")] = 13;
    states[14].action[getSymbolIndex("x")] = 12;
    // 状态15
    states[15].goTo[getSymbolIndex("F")] = 24;
    states[15].action[getSymbolIndex("(")] = 13;
    states[15].action[getSymbolIndex("x")] = 12;
    // 状态16
    states[16].action[getSymbolIndex(",")] = 8;
    states[16].action[getSymbolIndex("]")] = 9;
    // 状态17
    states[17].action[getSymbolIndex("=")] = 18;
    // 状态18
    states[18].goTo[getSymbolIndex("E")] = 25;
    states[18].goTo[getSymbolIndex("T")] = 20;
    states[18].goTo[getSymbolIndex("F")] = 21;
    states[18].action[getSymbolIndex("(")] = 13;
    states[18].action[getSymbolIndex("x")] = 12;
    // 状态19
    states[19].action[getSymbolIndex("+")] = 27;
    states[19].action[getSymbolIndex("-")] = 28;
    states[19].action[getSymbolIndex("*")] = 27;
    states[19].action[getSymbolIndex("/")] = 27;
    states[19].action[getSymbolIndex(")")] = 27;
    states[19].action[getSymbolIndex("[")] = 27;
    states[19].action[getSymbolIndex(",")] = 27;
    states[19].action[getSymbolIndex("]")] = 27;
    states[19].action[getSymbolIndex("$")] = 27;
    // 状态20
    states[20].action[getSymbolIndex("+")] = 27;
    states[20].action[getSymbolIndex("-")] = 28;
    states[20].action[getSymbolIndex("*")] = 29;
    states[20].action[getSymbolIndex("/")] = 30;
    states[20].action[getSymbolIndex(")")] = 27;
    states[20].action[getSymbolIndex("[")] = 27;
    states[20].action[getSymbolIndex(",")] = 27;
    states[20].action[getSymbolIndex("]")] = 27;
    states[20].action[getSymbolIndex("$")] = 27;
    // 状态21
    states[21].action[getSymbolIndex("+")] = 27;
    states[21].action[getSymbolIndex("-")] = 28;
    states[21].action[getSymbolIndex("*")] = 29;
    states[21].action[getSymbolIndex("/")] = 30;
    states[21].action[getSymbolIndex(")")] = 31;
    states[21].action[getSymbolIndex("[")] = 27;
    states[21].action[getSymbolIndex(",")] = 27;
    states[21].action[getSymbolIndex("]")] = 27;
    states[21].action[getSymbolIndex("$")] = 27;
    // 状态22
    states[22].action[getSymbolIndex("+")] = 27;
    states[22].action[getSymbolIndex("-")] = 28;
    states[22].action[getSymbolIndex("*")] = 29;
    states[22].action[getSymbolIndex("/")] = 30;
    states[22].action[getSymbolIndex(")")] = 31;
    states[22].action[getSymbolIndex("[")] = 27;
    states[22].action[getSymbolIndex(",")] = 27;
    states[22].action[getSymbolIndex("]")] = 27;
    states[22].action[getSymbolIndex("$")] = 27;
    // 状态23
    states[23].action[getSymbolIndex("+")] = 27;
    states[23].action[getSymbolIndex("-")] = 28;
    states[23].action[getSymbolIndex("*")] = 29;
    states[23].action[getSymbolIndex("/")] = 30;
    states[23].action[getSymbolIndex(")")] = 31;
    states[23].action[getSymbolIndex("[")] = 27;
    states[23].action[getSymbolIndex(",")] = 27;
    states[23].action[getSymbolIndex("]")] = 27;
    states[23].action[getSymbolIndex("$")] = 27;
    // 状态24
    states[24].action[getSymbolIndex("+")] = 27;
    states[24].action[getSymbolIndex("-")] = 28;
    states[24].action[getSymbolIndex("*")] = 29;
    states[24].action[getSymbolIndex("/")] = 30;
    states[24].action[getSymbolIndex(")")] = 31;
    states[24].action[getSymbolIndex("[")] = 27;
    states[24].action[getSymbolIndex(",")] = 27;
    states[24].action[getSymbolIndex("]")] = 27;
    states[24].action[getSymbolIndex("$")] = 27;
    // 状态25
    states[25].action[getSymbolIndex("+")] = 27;
    states[25].action[getSymbolIndex("-")] = 28;
    states[25].action[getSymbolIndex("*")] = 29;
    states[25].action[getSymbolIndex("/")] = 30;
    states[25].action[getSymbolIndex(")")] = 31;
    states[25].action[getSymbolIndex("[")] = 27;
    states[25].action[getSymbolIndex(",")] = 27;
    states[25].action[getSymbolIndex("]")] = 27;
    states[25].action[getSymbolIndex("$")] = 27;
}

// 分析函数
void parse(string program) {
    stack<Symbol> stack;
    stack.push(getSymbol("$"));
    stack.push(getSymbol("S"));
    int state = 0;
    int i = 0;
    string currentSymbol = program[i];
    while (true) {
        Symbol topSymbol = stack.top();
        Symbol currentSymbolSymbol = getSymbol(currentSymbol);
        if (currentSymbolSymbol.type == ERROR) {
            cout << "错误：非法符号 " << currentSymbol << endl;
            break;
        }
        if (states[state].action.find(currentSymbolSymbol.index) != states[state].action.end()) {
            int action = states[state].action[currentSymbolSymbol.index];
            if (action == 0) {
                cout << "错误：语法错误" << endl;
                break;
            } else if (action > 0) {
                // 移入
                stack.push(currentSymbolSymbol);
                state = action;
                i++;
                currentSymbol = program[i];
            } else if (action < 0) {
                // 归约
                int rule = -action;
                int len = 0;
                switch (rule) {
                    case 1:
                        len = 3;
                        break;
                    case 2:
                        len = 1;
                        break;
                    case 3:
                        len = 3;
                        break;
                    case 4:
                        len = 3;
                        break;
                    case 5:
                        len = 3;
                        break;
                    case 6:
                        len = 1;
                        break;
                    case 7:
                        len = 3;
                        break;
                    case 8:
                        len = 3;
                        break;
                    case 9:
                        len = 3;
                        break;
                    case 10:
                        len = 1;
                        break;
                }
                for (int j = 0; j < len; j++) {
                    stack.pop();
                }
                Symbol reducedSymbol;
                switch (rule) {
                    case 1:
                        reducedSymbol = getSymbol("S");
                        break;
                    case 2:
                        reducedSymbol = getSymbol("A");
                        break;
                    case 3:
                        reducedSymbol = getSymbol("A");
                        break;
                    case 4:
                        reducedSymbol = getSymbol("E");
                        break;
                    case 5:
                        reducedSymbol = getSymbol("E");
                        break;
                    case 6:
                        reducedSymbol = getSymbol("E");
                        break;
                    case 7:
                        reducedSymbol = getSymbol("T");
                        break;
                    case 8:
                        reducedSymbol = getSymbol("T");
                        break;
                    case 9:
                        reducedSymbol = getSymbol("T");
                        break;
                    case 10:
                        reducedSymbol = getSymbol("F");
                        break;
                }
                stack.push(reducedSymbol);
                state = states[state].goTo[reducedSymbol.index];
            }
        } else if (states[state].goTo.find(topSymbol.index) != states[state].goTo.end()) {
            // 跳转
            state = states[state].goTo[topSymbol.index];
            stack.pop();
        } else {
            cout << "错误：语法错误" << endl;
            break;
        }
    }
    if (currentSymbol == "$" && stack.top().index == getSymbolIndex("$")) {
        cout << "程序解析成功！" << endl;
    }
}

// 生成四元式
void generateQuadruple(string program) {
    stack<Symbol> stack;
    stack.push(getSymbol("$"));
    stack.push(getSymbol("S"));
    int state = 0;
    int i = 0;
    string currentSymbol = program[i];
    while (true) {
        Symbol topSymbol = stack.top();
        Symbol currentSymbolSymbol = getSymbol(currentSymbol);
        if (currentSymbolSymbol.type == ERROR) {
            cout << "错误：非法符号 " << currentSymbol << endl;
            break;
        }
        if (states[state].action.find(currentSymbolSymbol.index) != states[state].action.end()) {
            int action = states[state].action[currentSymbolSymbol.index];
            if (action == 0) {
                cout << "错误：语法错误" << endl;
                break;
            } else if (action > 0) {
                // 移入
                stack.push(currentSymbolSymbol);
                state = action;
                i++;
                currentSymbol = program[i];
            } else if (action < 0) {
                // 归约
                int rule = -action;
                int len = 0;
                switch (rule) {
                    case 1:
                        len = 3;
                        break;
                    case 2:
                        len = 1;
                        break;
                    case 3:
                        len = 3;
                        break;
                    case 4:
                        len = 3;
                        break;
                    case 5:
                        len = 3;
                        break;
                    case 6:
                        len = 1;
                        break;
                    case 7:
                        len = 3;
                        break;
                    case 8:
                        len = 3;
                        break;
                    case 9:
                        len = 3;
                        break;
                    case 10:
                        len = 1;
                        break;
                }
                for (int j = 0; j < len; j++) {
                    stack.pop();
                }
                Symbol reducedSymbol;
                switch (rule) {
                    case 1:
                        reducedSymbol = getSymbol("S");
                        break;
                    case 2:
                        reducedSymbol = getSymbol("A");
                        break;
                    case 3:
                        reducedSymbol = getSymbol("A");
                        break;
                    case 4:
                        reducedSymbol = getSymbol("E");
                        break;
                    case 5:
                        reducedSymbol = getSymbol("E");
                        break;
                    case 6:
                        reducedSymbol = getSymbol("E");
                        break;
                    case 7:
                        reducedSymbol = getSymbol("T");
                        break;
                    case 8:
                        reducedSymbol = getSymbol("T");
                        break;
                    case 9:
                        reducedSymbol = getSymbol("T");
                        break;
                    case 10:
                        reducedSymbol = getSymbol("F");
                        break;
                }
                stack.push(reducedSymbol);
                state = states[state].goTo[reducedSymbol.index];
            }
        } else if (states[state].goTo.find(topSymbol.index) != states[state].goTo.end()) {
            // 跳转
            state = states[state].goTo[topSymbol.index];
            stack.pop();
        } else {
            cout << "错误：语法错误" << endl;
            break;
        }
    }
    if (currentSymbol == "$" && stack.top().index == getSymbolIndex("$")) {
        cout << "程序解析成功！" << endl;
    }
}

int main() {
    initState();
    string program;
    cout << "请输入程序：" << endl;
    cin >> program;
    parse(program);
    generateQuadruple(program);
    return 0;
}
实现一个简单的编程语言的语法制导翻译和中间代码生成

原文地址: http://www.cveoy.top/t/topic/osDB 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录