简单的编程语言语法制导翻译和中间代码生成

1. 完善文法

𝑉𝑡 = {+, −,∗,/, , , (, ),[,], 𝑓, 𝑋} 其中 X 表示除了 f 之外的任意小写字母
𝑉𝑛 = {S, A, E, T, F},
G[S]:
S → f[A] = E
A → X | 𝑋,A
E → E + T | E − T | T
T → T ∗ F | T / F | F
F → (E) | X

2. 构造 SLR(1)分析表

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

// 定义文法符号
enum Symbol {
    PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN, LBRACKET, RBRACKET,
    F, X, S, A, E, T
};

// 定义文法符号对应的字符串
const vector<string> symbol_str = {
    '+', '-', '*', '/', '(', ')', '[', ']', 'f', 'X', 'S', 'A', 'E', 'T'
};

// 定义文法产生式
struct Production {
    Symbol left;
    vector<Symbol> right;

    Production(Symbol l, vector<Symbol> r) : left(l), right(r) {}
};

// 定义文法产生式集合
const vector<Production> productions = {
    Production(S, {F, A, E}),
    Production(A, {X}),
    Production(A, {X, COMMA, A}),
    Production(E, {E, PLUS, T}),
    Production(E, {E, MINUS, T}),
    Production(E, {T}),
    Production(T, {T, TIMES, F}),
    Production(T, {T, DIVIDE, F}),
    Production(T, {F}),
    Production(F, {LPAREN, E, RPAREN}),
    Production(F, {X})
};

// 定义 FIRST 集和 FOLLOW 集
map<Symbol, vector<Symbol>> first_set;
map<Symbol, vector<Symbol>> follow_set;

// 定义 SLR(1)分析表
map<pair<int, Symbol>, int> action_table;
map<pair<int, Symbol>, int> goto_table;

// 计算 FIRST 集
void compute_first_set() {
    // 初始化终结符的 FIRST 集
    for (int i = 0; i < symbol_str.size(); i++) {
        if (i < F || i > X) {
            first_set[(Symbol)i].push_back((Symbol)i);
        }
    }

    bool change;
    do {
        change = false;
        // 遍历所有产生式
        for (auto prod : productions) {
            int i = 0;
            // 依次计算右部所有符号的 FIRST 集
            while (i < prod.right.size()) {
                Symbol symbol = prod.right[i];
                // 如果是终结符，直接加入 FIRST 集并退出循环
                if (symbol < F || symbol > X) {
                    if (find(first_set[prod.left].begin(),
                             first_set[prod.left].end(), symbol) == first_set[prod.left].end()) {
                        first_set[prod.left].push_back(symbol);
                        change = true;
                    }
                    break;
                }
                // 如果是非终结符，加入其 FIRST 集（除了 EPSILON）
                for (auto s : first_set[symbol]) {
                    if (s != EPSILON && find(first_set[prod.left].begin(),
                                             first_set[prod.left].end(), s) == first_set[prod.left].end()) {
                        first_set[prod.left].push_back(s);
                        change = true;
                    }
                }
                // 如果该非终结符不含 EPSILON，退出循环
                if (find(first_set[symbol].begin(), first_set[symbol].end(), EPSILON) == first_set[symbol].end()) {
                    break;
                }
                // 否则继续计算下一个符号的 FIRST 集
                i++;
            }
            // 如果所有符号的 FIRST 集都含有 EPSILON，则将 EPSILON 加入左部的 FIRST 集
            if (i == prod.right.size() &&
                find(first_set[prod.left].begin(), first_set[prod.left].end(), EPSILON) == first_set[prod.left].end()) {
                first_set[prod.left].push_back(EPSILON);
                change = true;
            }
        }
    } while (change);
}

// 计算 FOLLOW 集
void compute_follow_set() {
    // 初始化开始符号的 FOLLOW 集
    follow_set[S].push_back(END);

    bool change;
    do {
        change = false;
        // 遍历所有产生式
        for (auto prod : productions) {
            // 依次计算右部所有符号的 FOLLOW 集
            for (int i = 0; i < prod.right.size(); i++) {
                Symbol symbol = prod.right[i];
                // 非终结符才有 FOLLOW 集
                if (symbol < F || symbol > X) {
                    // 如果该符号不是最后一个符号，则将其后继符号的 FIRST 集（除了 EPSILON）加入 FOLLOW 集
                    for (int j = i + 1; j < prod.right.size(); j++) {
                        Symbol next_symbol = prod.right[j];
                        if (next_symbol < F || next_symbol > X) {
                            for (auto s : first_set[next_symbol]) {
                                if (s != EPSILON && find(follow_set[symbol].begin(),
                                                         follow_set[symbol].end(), s) == follow_set[symbol].end()) {
                                    follow_set[symbol].push_back(s);
                                    change = true;
                                }
                            }
                            // 如果后继符号的 FIRST 集含有 EPSILON，则将该产生式左部的 FOLLOW 集加入 FOLLOW 集
                            if (find(first_set[next_symbol].begin(), first_set[next_symbol].end(), EPSILON) !=
                                first_set[next_symbol].end()) {
                                for (auto s : follow_set[prod.left]) {
                                    if (find(follow_set[symbol].begin(), follow_set[symbol].end(), s) == follow_set[symbol].end()) {
                                        follow_set[symbol].push_back(s);
                                        change = true;
                                    }
                                }
                            }
                            break;
                        } else {
                            for (auto s : first_set[next_symbol]) {
                                if (s != EPSILON && find(follow_set[symbol].begin(),
                                                         follow_set[symbol].end(), s) == follow_set[symbol].end()) {
                                    follow_set[symbol].push_back(s);
                                    change = true;
                                }
                            }
                            if (find(first_set[next_symbol].begin(), first_set[next_symbol].end(), EPSILON) == first_set[next_symbol].end()) {
                                break;
                            }
                        }
                    }
                    // 如果该符号是最后一个符号或所有后继符号的 FIRST 集都含有 EPSILON，则将该产生式左部的 FOLLOW 集加入其 FOLLOW 集
                    if (i == prod.right.size() - 1 ||
                        find(first_set[prod.right[i + 1]].begin(), first_set[prod.right[i + 1]].end(), EPSILON) !=
                        first_set[prod.right[i + 1]].end()) {
                        for (auto s : follow_set[prod.left]) {
                            if (find(follow_set[symbol].begin(), follow_set[symbol].end(), s) == follow_set[symbol].end()) {
                                follow_set[symbol].push_back(s);
                                change = true;
                            }
                        }
                    }
                }
            }
        }
    } while (change);
}

// 计算 SLR(1)分析表
void compute_table() {
    // 初始化 action 表和 goto 表
    for (int i = 0; i < productions.size(); i++) {
        Production prod = productions[i];
        for (auto symbol : first_set[prod.right[0]]) {
            if (symbol != EPSILON) {
                action_table[{i, symbol}] = i;
            }
        }
        if (find(first_set[prod.right[0]].begin(), first_set[prod.right[0]].end(), EPSILON) !=
            first_set[prod.right[0]].end()) {
            for (auto symbol : follow_set[prod.left]) {
                action_table[{i, symbol}] = i;
            }
        }
    }
    for (int i = 0; i < productions.size(); i++) {
        Production prod = productions[i];
        for (int j = 0; j < prod.right.size(); j++) {
            Symbol symbol = prod.right[j];
            if (symbol >= F && symbol <= X) {
                goto_table[{i, symbol}] = i + 1;
            }
        }
    }
}

// SLR(1)分析器
void slr_parser(const string& input) {
    stack<int> state_stack;
    stack<Symbol> symbol_stack;
    state_stack.push(0);
    symbol_stack.push(END);
    int i = 0;
    while (true) {
        int state = state_stack.top();
        Symbol symbol = symbol_stack.top();
        if (action_table.find({state, symbol}) != action_table.end()) {
            int action = action_table[{state, symbol}];
            if (action == ACCEPT) {
                cout << 'ACCEPT' << endl;
                break;
            } else if (action >= 0 && action < productions.size()) {
                Production prod = productions[action];
                cout << prod.left << ' ->';
                for (auto s : prod.right) {
                    cout << ' ' << symbol_str[s];
                }
                cout << endl;
                state_stack.push(action + 1);
                for (int j = prod.right.size() - 1; j >= 0; j--) {
                    symbol_stack.push(prod.right[j]);
                }
            } else {
                cout << 'ERROR' << endl;
                break;
            }
        } else if (goto_table.find({state, symbol}) != goto_table.end()) {
            int next_state = goto_table[{state, symbol}];
            state_stack.push(next_state);
            symbol_stack.push(input[i]);
            i++;
        } else {
            cout << 'ERROR' << endl;
            break;
        }
    }
}

int main() {
    // 计算 FIRST 集和 FOLLOW 集
    compute_first_set();
    compute_follow_set();

    // 输出 FIRST 集和 FOLLOW 集
    for (int i = F; i <= X; i++) {
        cout << 'FIRST(' << symbol_str[i] << ') = { ';
        for (auto s : first_set[(Symbol)i]) {
            cout << symbol_str[s] << ' ';
        }
        cout << '}' << endl;
        cout << 'FOLLOW(' << symbol_str[i] << ') = { ';
        for (auto s : follow_set[(Symbol)i]) {
            cout << symbol_str[s] << ' ';
        }
        cout << '}' << endl;
    }

    // 计算 SLR(1)分析表
    compute_table();

    // 输出 SLR(1)分析表
    cout << 'ACTION TABLE:' << endl;
    for (int i = 0; i < productions.size(); i++) {
        for (int j = F; j <= X; j++) {
            if (action_table.find({i, (Symbol)j}) != action_table.end()) {
                cout << '  [' << i << ', ' << symbol_str[j] << '] = ' << action_table[{i, (Symbol)j}] << endl;
            }
        }
    }
    cout << 'GOTO TABLE:' << endl;
    for (int i = 0; i < productions.size(); i++) {
        for (int j = F; j <= X; j++) {
            if (goto_table.find({i, (Symbol)j}) != goto_table.end()) {
                cout << '  [' << i << ', ' << symbol_str[j] << '] = ' << goto_table[{i, (Symbol)j}] << endl;
            }
        }
    }

    // 输入测试字符串并进行语法分析
    string input;
    cout << 'Input: ';
    cin >> input;
    slr_parser(input);

    return 0;
}

3. 语法制导翻译过程

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

// 定义文法符号
enum Symbol {
    PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN, LBRACKET, RBRACKET,
    F, X, S, A, E, T
};

// 定义文法符号对应的字符串
const vector<string> symbol_str = {
    '+', '-', '*', '/', '(', ')', '[', ']', 'f', 'X', 'S', 'A', 'E', 'T'
};

// 定义文法产生式
struct Production {
    Symbol left;
    vector<Symbol> right;

    Production(Symbol l, vector<Symbol> r) : left(l), right(r) {}
};

// 定义文法产生式集合
const vector<Production> productions = {
    Production(S, {F, A, E}),
    Production(A, {X}),
    Production(A, {X, COMMA, A}),
    Production(E, {E, PLUS, T}),
    Production(E, {E, MINUS, T}),
    Production(E, {T}),
    Production(T, {T, TIMES, F}),
    Production(T, {T, DIVIDE, F}),
    Production(T, {F}),
    Production(F, {LPAREN, E, RPAREN}),
    Production(F, {X})
};

// 定义语法制导翻译时需要用到的数据结构
struct Token {
    Symbol symbol;
    int value;

    Token(Symbol s, int v) : symbol(s), value(v) {}
};

// 语法制导翻译时需要用到的全局变量
map<string, int> var_map; // 变量名和值的映射表

// 执行语义动作：将变量名存入栈中
void push_var(Token token, stack<string>& var_stack) {
    var_stack.push(string(1, 'a' + token.value));
}

// 执行语义动作：将常量存入栈中
void push_const(Token token, stack<int>& const_stack) {
    const_stack.push(token.value);
}

// 执行语义动作：将两个常量相加并存入栈中
void add(stack<int>& const_stack) {
    int b = const_stack.top();
    const_stack.pop();
    int a = const_stack.top();
    const_stack.pop();
    const_stack.push(a + b);
}

// 执行语义动作：将两个常量相减并存入栈中
void sub(stack<int>& const_stack) {
    int b = const_stack.top();
    const_stack.pop();
    int a = const_stack.top();
    const_stack.pop();
    const_stack.push(a - b);
}

// 执行语义动作：将两个常量相乘并存入栈中
void mul(stack<int>& const_stack) {
    int b = const_stack.top();
    const_stack.pop();
    int a = const_stack.top();
    const_stack.pop();
    const_stack.push(a * b);
}

// 执行语义动作：将两个常量相除并存入栈中
void div(stack<int>& const_stack) {
    int b = const_stack.top();
    const_stack.pop();
    int a = const_stack.top();
    const_stack.pop();
    const_stack.push(a / b);
}

// 执行语义动作：将变量的值存入映射表
void assign(stack<string>& var_stack, stack<int>& const_stack) {
    int value = const_stack.top();
    const_stack.pop();
    string var = var_stack.top();
    var_stack.pop();
    var_map[var] = value;
}

// 语法制导翻译函数
void translate(const string& input) {
    stack<Token> token_stack;
    stack<string> var_stack;
    stack<int> const_stack;
    int i = 0;
    while (i < input.size()) {
        char ch = input[i];
        if (ch >= 'a' && ch <= 'z') {
            token_stack.push(Token(X, ch - 'a'));
            i++;
        } else if (ch == '+') {
            token_stack.push(Token(PLUS, 0));
            i++;
        } else if (ch == '-') {
            token_stack.push(Token(MINUS, 0));
            i++;
        } else if (ch == '*') {
            token_stack.push(Token(TIMES, 0));
            i++;
        } else if (ch == '/') {
            token_stack.push(Token(DIVIDE, 0));
            i++;
        } else if (ch == '(') {
            token_stack.push(Token(LPAREN, 0));
            i++;
        } else if (ch == ')') {
            token_stack.push(Token(RPAREN, 0));
            i++;
        } else if (ch == '[') {
            token_stack.push(Token(LBRACKET, 0));
            i++;
        } else if (ch == ']') {
            token_stack.push(Token(RBRACKET, 0));
            i++;
        } else if (ch == '=') {
            token_stack.push(Token(ASSIGN, 0));
            i++;
        } else if (ch == ',') {
            token_stack.push(Token(COMMA, 0));
            i++;
        } else {
            i++;
        }
    }

    // 构建语法树
    stack<int> state_stack;
    state_stack.push(0);
    while (!token_stack.empty()) {
        Token token = token_stack.top();
        token_stack.pop();
        int state = state_stack.top();
        if (action_table.find({state, token.symbol}) != action_table.end()) {
            int action = action_table[{state, token.symbol}];
            if (action == ACCEPT) {
                cout << 'ACCEPT' << endl;
            } else if (action >= 0 && action < productions.size()) {
                Production prod = productions[action];
                cout << prod.left << ' ->';
                for (auto s : prod.right) {
                    cout << ' ' << symbol_str[s];
                }
                cout << endl;
                state_stack.push(action + 1);
                for (int j = prod.right.size() - 1; j >= 0; j--) {
                    if (prod.right[j] == X) {
                        push_var(token, var_stack);
                    } else if (prod.right[j] == PLUS) {
                        add(const_stack);
                    } else if (prod.right[j] == MINUS) {
                        sub(const_stack);
                    } else if (prod.right[j] == TIMES) {
                        mul(const_stack);
                    } else if (prod.right[j] == DIVIDE) {
                        div(const_stack);
                    } else if (prod.right[j] == ASSIGN) {
                        assign(var_stack, const_stack);
                    }
                }
            } else {
                cout << 'ERROR' << endl;
            }
        } else if (goto_table.find({state, token.symbol}) != goto_table.end()) {
            int next_state = goto_table[{state, token.symbol}];
            state_stack.push(next_state);
            if (token.symbol == X) {
                push_var(token, var_stack);
            } else if (token.symbol == PLUS) {
                add(const_stack);
            } else if (token.symbol == MINUS) {
                sub(const_stack);
            } else if (token.symbol == TIMES) {
                mul(const_stack);
            } else if (token.symbol == DIVIDE) {
                div(const_stack);
            } else if (token.symbol == LPAREN) {
                push_const(token, const_stack);
            } else if (token.symbol == RPAREN) {
                push_const(token, const_stack);
            } else if (token.symbol == LBRACKET) {
                push_const(token, const_stack);
            } else if (token.symbol == RBRACKET) {
                push_const(token, const_stack);
            } else if (token.symbol == ASSIGN) {
                assign(var_stack, const_stack);
            }
        } else {
            cout << 'ERROR' << endl;
        }
    }

    // 输出变量的值
    for (auto it : var_map) {
        cout << it.first << ': ' << it.second << endl;
    }
}

int main() {
    // 计算 FIRST 集和 FOLLOW 集
    compute_first_set();
    compute_follow_set();

    // 计算 SLR(1)分析表
    compute_table();

    // 输入测试字符串并进行语法分析
    string input;
    cout << 'Input: ';
    cin >> input;
    translate(input);

    return 0;
}