自顶向下的语法分析程序c++代码

以下是一个简单的自顶向下的LL(1)语法分析程序的C++代码示例：

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

// 定义产生式结构体
struct Production {
    string left; // 产生式左部
    vector<string> right; // 产生式右部
};

// 定义LL(1)分析表结构体
struct AnalysisTable {
    map<string, map<string, vector<string>>> table; // 分析表
};

// 定义文法结构体
struct Grammar {
    vector<string> nonTerminals; // 非终结符集合
    vector<string> terminals; // 终结符集合
    string startSymbol; // 开始符号
    vector<Production> productions; // 产生式集合
};

// 初始化文法
Grammar initGrammar() {
    Grammar grammar;
    grammar.nonTerminals = {"S", "A", "B"};
    grammar.terminals = {"a", "b", "c", "$"};
    grammar.startSymbol = "S";
    grammar.productions = {
        {"S", {"A", "B"}},
        {"A", {"a", "A"}},
        {"A", {"b"}},
        {"B", {"c", "B"}},
        {"B", {"$"}}
    };
    return grammar;
}

// 构造LL(1)分析表
AnalysisTable buildAnalysisTable(Grammar grammar) {
    AnalysisTable analysisTable;
    // 初始化分析表
    for (string nonTerminal : grammar.nonTerminals) {
        map<string, vector<string>> row;
        for (string terminal : grammar.terminals) {
            row[terminal] = {};
        }
        analysisTable.table[nonTerminal] = row;
    }
    // 填充分析表
    for (Production production : grammar.productions) {
        string left = production.left;
        vector<string> right = production.right;
        string first = right[0];
        if (first != "$") {
            // 对于每个终结符a，将A -> α加入M[A, a]
            if (find(grammar.terminals.begin(), grammar.terminals.end(), first) != grammar.terminals.end()) {
                analysisTable.table[left][first].push_back(production.left + " -> " + production.right[0]);
            }
            // 对于每个非终结符B，将A -> α加入M[A, b]，其中b是FIRST(α)中的一个终结符
            else {
                for (string terminal : grammar.terminals) {
                    if (find(grammar.terminals.begin(), grammar.terminals.end(), terminal) != grammar.terminals.end()) {
                        if (find(right.begin(), right.end(), terminal) != right.end()) {
                            analysisTable.table[left][terminal].push_back(production.left + " -> " + production.right[0]);
                        }
                    }
                }
            }
        }
        // 对于每个终结符b，将A -> ε加入M[A, b]，其中b是FOLLOW(A)中的一个终结符
        else {
            for (string terminal : grammar.terminals) {
                if (find(grammar.terminals.begin(), grammar.terminals.end(), terminal) != grammar.terminals.end()) {
                    if (find(grammar.productions[0].right.begin(), grammar.productions[0].right.end(), terminal) != grammar.productions[0].right.end()) {
                        analysisTable.table[left][terminal].push_back(production.left + " -> " + production.right[0]);
                    }
                }
            }
        }
    }
    return analysisTable;
}

// LL(1)语法分析
bool LL1Analysis(string input, AnalysisTable analysisTable) {
    vector<string> stack = {"$", analysisTable.table.begin()->first}; // 初始化栈
    int index = 0; // 初始化输入串指针
    while (stack.size() > 0) {
        string top = stack.back();
        stack.pop_back();
        if (top == "$" && input[index] == '$') {
            return true;
        }
        else if (top == input.substr(index, 1)) {
            index++;
        }
        else if (analysisTable.table.find(top) != analysisTable.table.end() && analysisTable.table[top].find(input.substr(index, 1)) != analysisTable.table[top].end()) {
            vector<string> production = analysisTable.table[top][input.substr(index, 1)];
            stack.insert(stack.end(), production.rbegin(), production.rend());
        }
        else {
            return false;
        }
    }
    return false;
}

int main() {
    Grammar grammar = initGrammar();
    AnalysisTable analysisTable = buildAnalysisTable(grammar);
    string input = "abbc$";
    bool result = LL1Analysis(input, analysisTable);
    if (result) {
        cout << "输入串 " << input << " 符合文法规则" << endl;
    }
    else {
        cout << "输入串 " << input << " 不符合文法规则" << endl;
    }
    return 0;
}