用c++设计LL(1)文法分析器的代码

以下是用C++实现的LL(1)文法分析器的代码：

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

// 定义文法符号类
class Symbol {
public:
    enum class Type {
        Terminal,   // 终结符
        Nonterminal // 非终结符
    };

    Symbol(const string& name, Type type) : name(name), type(type) {}

    const string& getName() const {
        return name;
    }

    Type getType() const {
        return type;
    }

private:
    string name;
    Type type;
};

// 定义产生式类
class Production {
public:
    Production(const Symbol& left, const vector<Symbol>& right) : left(left), right(right) {}

    const Symbol& getLeft() const {
        return left;
    }

    const vector<Symbol>& getRight() const {
        return right;
    }

private:
    Symbol left;
    vector<Symbol> right;
};

// 定义语法分析器类
class LL1Parser {
public:
    LL1Parser(const vector<Production>& productions, const Symbol& startSymbol)
        : productions(productions), startSymbol(startSymbol) {
        // 构造预测分析表
        for (auto& prod : productions) {
            auto& left = prod.getLeft();
            auto& right = prod.getRight();

            auto& predictSet = predictTable[{left.getName(), right[0].getName()}];
            if (right[0].getType() == Symbol::Type::Terminal) {
                predictSet.insert(right[0]);
            } else {
                for (auto& terminal : followSet[left.getName()]) {
                    predictSet.insert(terminal);
                }
            }
        }
    }

    bool parse(const vector<Symbol>& input) {
        vector<Symbol> symbolStack{Symbol{"$", Symbol::Type::Terminal}, startSymbol};
        vector<Symbol> inputStack{input};
        inputStack.push_back(Symbol{"$", Symbol::Type::Terminal});

        while (!symbolStack.empty() && !inputStack.empty()) {
            auto& topSymbol = symbolStack.back();
            auto& nextToken = inputStack.back();

            if (topSymbol.getName() == nextToken.getName()) {
                symbolStack.pop_back();
                inputStack.pop_back();
            } else if (topSymbol.getType() == Symbol::Type::Nonterminal) {
                auto& predictSet = predictTable[{topSymbol.getName(), nextToken.getName()}];
                if (predictSet.empty()) {
                    return false;
                }

                auto& predictSymbol = *predictSet.begin();
                symbolStack.pop_back();

                auto& prod = getProduction(topSymbol, predictSymbol);
                auto& right = prod.getRight();
                for (auto it = right.rbegin(); it != right.rend(); ++it) {
                    symbolStack.push_back(*it);
                }
            } else {
                return false;
            }
        }

        return symbolStack.empty() && inputStack.empty();
    }

private:
    vector<Production> productions;
    Symbol startSymbol;
    unordered_map<string, vector<Symbol>> followSet;
    unordered_map<pair<string, string>, unordered_set<Symbol>> predictTable;

    const Production& getProduction(const Symbol& left, const Symbol& right) const {
        for (auto& prod : productions) {
            if (prod.getLeft().getName() == left.getName() &&
                prod.getRight().size() == 1 &&
                prod.getRight()[0].getName() == right.getName()) {
                return prod;
            }
        }

        throw runtime_error("can't find production");
    }
};

int main() {
    // 构造文法
    Symbol E{"E", Symbol::Type::Nonterminal};
    Symbol T{"T", Symbol::Type::Nonterminal};
    Symbol F{"F", Symbol::Type::Nonterminal};
    Symbol plus{"+", Symbol::Type::Terminal};
    Symbol minus{"-", Symbol::Type::Terminal};
    Symbol star{"*", Symbol::Type::Terminal};
    Symbol slash{"/", Symbol::Type::Terminal};
    Symbol lparen{"(", Symbol::Type::Terminal};
    Symbol rparen{")", Symbol::Type::Terminal};
    Symbol id{"id", Symbol::Type::Terminal};
    vector<Production> productions{
        Production{E, {T}},
        Production{T, {F}},
        Production{T, {T, star, F}},
        Production{T, {T, slash, F}},
        Production{F, {lparen, E, rparen}},
        Production{F, {id}},
        Production{E, {E, plus, T}},
        Production{E, {E, minus, T}}
    };

    // 计算follow集合
    unordered_map<string, vector<Symbol>> followSet;
    followSet[E.getName()].push_back(Symbol{"$", Symbol::Type::Terminal});
    followSet[T.getName()].push_back(Symbol{"+", Symbol::Type::Terminal});
    followSet[T.getName()].push_back(Symbol{"-", Symbol::Type::Terminal});
    followSet[T.getName()].push_back(Symbol{"$", Symbol::Type::Terminal});
    followSet[F.getName()].push_back(Symbol{"*", Symbol::Type::Terminal});
    followSet[F.getName()].push_back(Symbol{"/", Symbol::Type::Terminal});
    followSet[F.getName()].push_back(Symbol{"+", Symbol::Type::Terminal});
    followSet[F.getName()].push_back(Symbol{"-", Symbol::Type::Terminal});
    followSet[F.getName()].push_back(Symbol{"$", Symbol::Type::Terminal});

    // 构造LL(1)语法分析器
    LL1Parser parser{productions, E};

    // 测试输入串
    vector<Symbol> input{Symbol{"id", Symbol::Type::Terminal}, Symbol{"+", Symbol::Type::Terminal},
                         Symbol{"(", Symbol::Type::Terminal}, Symbol{"id", Symbol::Type::Terminal},
                         Symbol{"/", Symbol::Type::Terminal}, Symbol{"id", Symbol::Type::Terminal},
                         Symbol{")", Symbol::Type::Terminal}, Symbol{"*", Symbol::Type::Terminal},
                         Symbol{"id", Symbol::Type::Terminal}, Symbol{"$", Symbol::Type::Terminal}};

    if (parser.parse(input)) {
        cout << "Accepted" << endl;
    } else {
        cout << "Rejected" << endl;
    }

    return 0;
}

该代码实现了一个简单的LL(1)文法分析器，使用了C++11的一些新特性，如unordered_map和unordered_set。它可以处理下面这个文法：

E -> T | E + T | E - T
T -> F | T * F | T / F
F -> ( E ) | id

这个文法是一个简单的四则运算表达式文法。在代码中，我们首先定义了Symbol类和Production类，用于表示文法符号和产生式。然后，我们定义了LL1Parser类，它包含了一个预测分析表和一个parse()方法。在构造LL1Parser对象时，我们会根据文法计算预测分析表。parse()方法接受一个输入串作为参数，返回一个布尔值表示输入串是否被该文法接受。在parse()方法中，我们使用两个栈来模拟语法分析过程，一个是符号栈，一个是输入栈。如果输入串被接受，则parse()方法返回true，否则返回false。