ll(1)分析法c++实现

LL(1)分析法是一种自顶向下的语法分析方法，它使用一个分析表来帮助确定应该使用哪个产生式来扩展当前的非终结符。下面是一个简单的LL(1)分析法的C++实现：

#include <iostream>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

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

// 定义文法符号类
class Symbol {
public:
    SymbolType type;
    string name;

    Symbol(SymbolType t, const string& n) : type(t), name(n) {}
};

// 定义产生式类
class Production {
public:
    Symbol nonterminal;  // 非终结符
    vector<Symbol> rhs;  // 产生式右部

    Production(const Symbol& n, const vector<Symbol>& r) : nonterminal(n), rhs(r) {}
};

// 定义LL(1)分析表类
class LL1Table {
public:
    unordered_map<string, unordered_map<string, Production>> table;

    // 添加一条表项
    void addEntry(const string& nonterminal, const string& terminal, const Production& p) {
        table[nonterminal][terminal] = p;
    }

    // 获取一条表项
    Production getEntry(const string& nonterminal, const string& terminal) const {
        auto it1 = table.find(nonterminal);
        if (it1 == table.end()) {
            throw "Invalid nonterminal symbol.";
        }

        auto it2 = it1->second.find(terminal);
        if (it2 == it1->second.end()) {
            throw "Invalid terminal symbol.";
        }

        return it2->second;
    }
};

// 定义LL(1)分析器类
class LL1Parser {
public:
    vector<Symbol> input;  // 输入串
    stack<Symbol> stack;  // 符号栈
    LL1Table table;        // LL(1)分析表

    LL1Parser(const vector<Symbol>& i, const LL1Table& t) : input(i), table(t) {
        stack.push(Symbol(TERMINAL, "$"));  // 栈底
        stack.push(Symbol(NONTERMINAL, "S"));  // 初始状态
    }

    // LL(1)分析
    void parse() {
        int ip = 0;
        while (!stack.empty()) {
            Symbol s = stack.top();
            if (s.type == TERMINAL) {  // 终结符
                if (s.name == input[ip].name) {
                    stack.pop();
                    ip++;
                } else {
                    throw "Syntax error.";
                }
            } else {  // 非终结符
                Production p = table.getEntry(s.name, input[ip].name);
                stack.pop();
                for (auto it = p.rhs.rbegin(); it != p.rhs.rend(); ++it) {
                    stack.push(*it);
                }
            }
        }
        cout << "Syntax is correct." << endl;
    }
};

int main() {
    // 构造LL(1)分析表
    LL1Table table;
    table.addEntry("S", "a", Production(Symbol(NONTERMINAL, "A"), {Symbol(TERMINAL, "a")}));
    table.addEntry("S", "b", Production(Symbol(NONTERMINAL, "B"), {Symbol(TERMINAL, "b")}));
    table.addEntry("A", "b", Production(Symbol(NONTERMINAL, "S"), {Symbol(TERMINAL, "b")}));    
    table.addEntry("B", "a", Production(Symbol(NONTERMINAL, "S"), {Symbol(TERMINAL, "a")}));    

    // 构造输入串
    vector<Symbol> input = {Symbol(TERMINAL, "a"), Symbol(TERMINAL, "b"), Symbol(TERMINAL, "$")};

    // 构造LL(1)分析器
    LL1Parser parser(input, table);

    // 进行LL(1)分析
    parser.parse();

    return 0;
}

这个例子是对文法S->aA | bB, A->bS, B->aS的LL(1)分析，在代码中构造了LL(1)分析表，并使用输入串进行了分析。在实际应用中，需要根据具体的文法和输入串，构造相应的LL(1)分析表。