LL（1）分析实验 c++代码

以下是一个简单的 LL(1) 分析实验的 C++ 代码示例：

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

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

// 定义产生式类型
struct Production {
    string left;        // 左部符号
    vector<string> right; // 右部符号
};

// 定义 LL(1) 分析表类型
typedef unordered_map<string, unordered_map<string, Production>> ParsingTable;

// 获取终结符和非终结符类型
SymbolType getSymbolType(string symbol) {
    if (isupper(symbol[0])) {
        return NONTERMINAL;
    }
    return TERMINAL;
}

// 构造 LL(1) 分析表
ParsingTable buildParsingTable(vector<Production>& productions, vector<string>& terminals, vector<string>& nonterminals) {
    ParsingTable table;
    // 初始化分析表
    for (auto nonterminal : nonterminals) {
        for (auto terminal : terminals) {
            table[nonterminal][terminal] = {"", {}};
        }
    }
    // 填充分析表
    for (auto production : productions) {
        string left = production.left;
        for (auto terminal : terminals) {
            if (production.right[0] == terminal) { // 预测分析表第一项
                table[left][terminal] = production;
            } else if (getSymbolType(production.right[0]) == NONTERMINAL) { // 预测分析表其他项
                for (auto follow : table[production.right[0]][terminal].right) {
                    if (follow != "#") {
                        table[left][follow] = production;
                    }
                }
            }
        }
    }
    return table;
}

// LL(1) 分析器
bool parse(string input, ParsingTable& table) {
    stack<string> stk;
    stk.push("$"); // 结束符
    stk.push(table.begin()->first); // 开始非终结符
    int i = 0;
    while (!stk.empty()) {
        string top = stk.top();
        stk.pop();
        if (top == "$") { // 输入串匹配完毕
            return true;
        }
        if (getSymbolType(top) == TERMINAL) { // 终结符
            if (top == input.substr(i, 1)) {
                i++;
            } else {
                return false;
            }
        } else { // 非终结符
            Production production = table[top][input.substr(i, 1)];
            if (production.left == "") { // 分析表中无对应产生式
                return false;
            } else {
                for (auto it = production.right.rbegin(); it != production.right.rend(); it++) {
                    if (*it != "#") { // 空产生式不入栈
                        stk.push(*it);
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    // 定义文法
    vector<Production> productions = {
        {"E", {"T", "E'"}},
        {"E'", {"+", "T", "E'"}},
        {"E'", {"#",}},
        {"T", {"F", "T'"}},
        {"T'", {"*", "F", "T'"}},
        {"T'", {"#",}},
        {"F", {"(", "E", ")"}},
        {"F", {"i"}},
    };
    // 获取终结符和非终结符
    vector<string> terminals = {"+", "*", "(", ")", "i"};
    vector<string> nonterminals = {"E", "E'", "T", "T'", "F"};
    // 构造 LL(1) 分析表
    ParsingTable table = buildParsingTable(productions, terminals, nonterminals);
    // 打印 LL(1) 分析表
    for (auto nonterminal : nonterminals) {
        for (auto terminal : terminals) {
            Production production = table[nonterminal][terminal];
            cout << nonterminal << ", " << terminal << ": ";
            if (production.left == "") {
                cout << "error" << endl;
            } else {
                cout << production.left << " -> ";
                for (auto symbol : production.right) {
                    cout << symbol << " ";
                }
                cout << endl;
            }
        }
    }
    // 输入串
    string input = "i+i*i$";
    // LL(1) 分析
    bool result = parse(input, table);
    if (result) {
        cout << "input " << input << " is accepted" << endl;
    } else {
        cout << "input " << input << " is rejected" << endl;
    }
    return 0;
}

该代码实现了一个简单的 LL(1) 分析器，包括以下功能：

- 构造文法符号类型的枚举类型 `SymbolType`。
- 定义产生式类型 `Production`，包括左部符号和右部符号序列。
- 定义 LL(1) 分析表类型 `ParsingTable`，使用 `unordered_map` 实现。
- 实现函数 `getSymbolType`，用于获取符号类型。
- 实现函数 `buildParsingTable`，用于构造 LL(1) 分析表。
- 实现函数 `parse`，用于进行 LL(1) 分析。
- 在 `main` 函数中定义文法、终结符和非终结符，构造 LL(1) 分析表，并对输入串进行 LL(1) 分析。

使用该代码，可以对输入串进行 LL(1) 分析，并输出分析结果。