c++求first集和follow集

C++语言的First集和Follow集如下：

First集：

1. 对于终结符号，它的First集就是它本身。

2. 对于非终结符号，它的First集就是它所能推导出的所有终结符号的集合。

Follow集：

1. 对于开始符号，它的Follow集就是$EOF$。

2. 对于非开始符号$A$，它的Follow集就是所有能够推导出$A$的右部的非终结符号的First集，以及$A$所在产生式左部的非终结符号的Follow集。如果$A$是某个产生式的最后一个符号，那么还要加上该产生式左部的Follow集。

希望能对你有所帮助。

相关问题

c++求first和follow集代码

以下是C++代码实现First和Follow集合的算法：

First集合算法：

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

using namespace std;

map<string, set<string>> first;

void compute_first(string non_terminal, vector<vector<string>> productions) {
    for (auto production : productions) {
        if (production[0] == non_terminal) {
            if (production[1] == "epsilon") {
                first[non_terminal].insert("epsilon");
            } else if (islower(production[1][0])) {
                first[non_terminal].insert(production[1]);
            } else {
                compute_first(production[1], productions);
                for (auto element : first[production[1]]) {
                    first[non_terminal].insert(element);
                }
            }
        }
    }
}

int main() {
    vector<vector<string>> productions = {
        {"S", "AB"},
        {"A", "aA"},
        {"A", "epsilon"},
        {"B", "bB"},
        {"B", "epsilon"}
    };

    for (auto production : productions) {
        compute_first(production[0], productions);
    }

    for (auto element : first) {
        cout << "First(" << element.first << ") = { ";
        for (auto value : element.second) {
            cout << value << " ";
        }
        cout << "}" << endl;
    }

    return 0;
}

Follow集合算法：

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

using namespace std;

map<string, set<string>> follow;

void compute_follow(string non_terminal, vector<vector<string>> productions) {
    if (non_terminal == productions[0][0]) {
        follow[non_terminal].insert("$");
    }

    for (auto production : productions) {
        for (int i = 1; i < production.size(); i++) {
            if (production[i] == non_terminal) {
                if (i == production.size() - 1) {
                    compute_follow(production[0], productions);
                    for (auto element : follow[production[0]]) {
                        follow[non_terminal].insert(element);
                    }
                } else {
                    if (islower(production[i + 1][0])) {
                        follow[non_terminal].insert(production[i + 1]);
                    } else {
                        compute_first(production[i + 1], productions);
                        for (auto element : first[production[i + 1]]) {
                            if (element != "epsilon") {
                                follow[non_terminal].insert(element);
                            } else {
                                compute_follow(production[0], productions);
                                for (auto element : follow[production[0]]) {
                                    follow[non_terminal].insert(element);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

int main() {
    vector<vector<string>> productions = {
        {"S", "AB"},
        {"A", "aA"},
        {"A", "epsilon"},
        {"B", "bB"},
        {"B", "epsilon"}
    };

    for (auto production : productions) {
        compute_follow(production[0], productions);
    }

    for (auto element : follow) {
        cout << "Follow(" << element.first << ") = { ";
        for (auto value : element.second) {
            cout << value << " ";
        }
        cout << "}" << endl;
    }

    return 0;
}

C++求FIRST和FOLLOW集合的代码

以下是求解FIRST集合和FOLLOW集合的C++代码示例：

// 计算产生式的FIRST集合
set<string> first(string symbol)
{
    set<string> result;
    // 如果是终结符，直接返回
    if (is_terminal(symbol)) {
        result.insert(symbol);
        return result;
    }
    // 如果是非终结符，遍历所有产生式
    for (int i = 0; i < productions.size(); i++) {
        if (productions[i].left == symbol) {
            // 如果产生式右部第一个符号是空串
            if (productions[i].right.size() == 1 && productions[i].right[0] == "") {
                result.insert("");
            }
            // 如果产生式右部第一个符号是终结符
            else if (is_terminal(productions[i].right[0])) {
                result.insert(productions[i].right[0]);
            }
            // 如果产生式右部第一个符号是非终结符
            else {
                set<string> right_first = first(productions[i].right[0]);
                result.insert(right_first.begin(), right_first.end());
            }
        }
    }
    return result;
}

// 计算非终结符的FOLLOW集合
set<string> follow(string symbol)
{
    set<string> result;
    // 如果是文法开始符号，加入结束符号$
    if (symbol == start_symbol) {
        result.insert("$");
    }
    // 遍历所有产生式
    for (int i = 0; i < productions.size(); i++) {
        vector<string> right = productions[i].right;
        for (int j = 0; j < right.size(); j++) {
            // 如果该符号为当前非终结符
            if (right[j] == symbol) {
                // 如果该符号在产生式右部不是最后一个符号
                if (j != right.size() - 1) {
                    // 如果下一个符号是终结符，直接加入FOLLOW集合
                    if (is_terminal(right[j + 1])) {
                        result.insert(right[j + 1]);
                    }
                    // 如果下一个符号是非终结符，加入该非终结符的FIRST集合
                    else {
                        set<string> next_first = first(right[j + 1]);
                        // 如果该非终结符的FIRST集合包含空串，还需加入该非终结符的FOLLOW集合
                        if (next_first.count("")) {
                            next_first.erase("");
                            set<string> follow_set = follow(productions[i].left);
                            next_first.insert(follow_set.begin(), follow_set.end());
                        }
                        result.insert(next_first.begin(), next_first.end());
                    }
                }
                // 如果该符号在产生式右部是最后一个符号，加入该非终结符的FOLLOW集合
                else {
                    set<string> follow_set = follow(productions[i].left);
                    result.insert(follow_set.begin(), follow_set.end());
                }
            }
        }
    }
    return result;
}

其中，is_terminal函数用于判断一个符号是否为终结符。productions为产生式集合，每个产生式包含左部和右部。start_symbol为文法开始符号。