使用C语言求解first集合和follow集合

求解一个文法的 FIRST 集合和 FOLLOW 集合是编译原理中的重要内容之一。下面提供一些简单的代码来演示如何使用 C 语言求解 FIRST 集合和 FOLLOW 集合。

首先，我们需要定义一个结构体来表示一个终结符或非终结符。

typedef struct {
    int is_terminal;  // 是否为终结符，0 表示非终结符，1 表示终结符
    char symbol;      // 符号名称
} Symbol;

然后，我们需要定义一个函数来计算一个产生式的 FIRST 集合。

void compute_first_set(Symbol* production, int length, Symbol* first_set) {
    int i;
    for (i = 0; i < length; i++) {
        if (production[i].is_terminal) {  // 如果是终结符，将其加入 FIRST 集合
            add_to_set(first_set, production[i]);
            break;
        } else {  // 如果是非终结符，计算其 FIRST 集合
            compute_first_set(get_production(production[i]), get_production_length(production[i]), first_set);
            if (!has_epsilon(get_production(production[i]))) {  // 如果该非终结符不能推导出空串，退出循环
                break;
            }
        }
    }
}

上面的代码中，`production` 表示一个产生式，`length` 表示该产生式的长度，`first_set` 表示该产生式的 FIRST 集合。

函数中，我们遍历产生式中的每一个符号，如果是终结符，将其加入 FIRST 集合；如果是非终结符，计算其 FIRST 集合，并判断是否能够推导出空串。如果不能推导出空串，退出循环。

接下来，我们需要定义一个函数来计算一个非终结符的 FOLLOW 集合。

void compute_follow_set(Symbol* symbol, Symbol* follow_set) {
    int i, j;
    Symbol* production;
    int length;
    int index_of_symbol;

    if (is_start_symbol(symbol)) {  // 如果该非终结符是文法的起始符号，将 $ 加入其 FOLLOW 集合
        add_to_set(follow_set, create_terminal_symbol('$'));
    }

    for (i = 0; i < get_production_count(); i++) {  // 遍历文法的所有产生式
        production = get_production_by_index(i);
        length = get_production_length(production);
        index_of_symbol = find_symbol_in_production(symbol, production, length);
        if (index_of_symbol >= 0 && index_of_symbol < length - 1) {  // 如果该非终结符在产生式中，并且不是最后一个符号
            compute_first_set(production + index_of_symbol + 1, length - index_of_symbol - 1, follow_set);  // 计算其后面符号的 FIRST 集合
            for (j = 0; j < length - index_of_symbol - 1; j++) {  // 将其后面符号的 FIRST 集合加入其 FOLLOW 集合
                if (has_epsilon(production[index_of_symbol + j + 1])) {
                    continue;
                }
                add_to_set(follow_set, production[index_of_symbol + j + 1]);
            }
        } else if (index_of_symbol == length - 1) {  // 如果该非终结符是产生式的最后一个符号
            compute_follow_set(get_left_symbol(production), follow_set);  // 计算其左侧非终结符的 FOLLOW 集合，并将其加入其 FOLLOW 集合
            merge_set(follow_set, get_follow_set(get_left_symbol(production)));
        }
    }
}

上面的代码中，`symbol` 表示一个非终结符，`follow_set` 表示该非终结符的 FOLLOW 集合。

函数中，我们首先判断该非终结符是否为文法的起始符号，如果是，将 `$` 加入其 FOLLOW 集合。

然后，遍历文法的所有产生式，找到包含该非终结符的产生式。如果该非终结符不是产生式的最后一个符号，计算其后面符号的 FIRST 集合，并将其加入其 FOLLOW 集合。如果该非终结符是产生式的最后一个符号，计算其左侧非终结符的 FOLLOW 集合，并将其加入其 FOLLOW 集合。

最后，我们可以调用上述函数来求解某个文法的 FIRST 集合和 FOLLOW 集合。

int main() {
    init_grammar();  // 初始化文法
    compute_all_first_sets();  // 计算文法的所有产生式的 FIRST 集合
    compute_all_follow_sets();  // 计算文法的所有非终结符的 FOLLOW 集合
    print_all_first_sets();  // 输出文法的所有产生式的 FIRST 集合
    print_all_follow_sets();  // 输出文法的所有非终结符的 FOLLOW 集合
    return 0;
}