C语言求解first集合和follow集合的完整代码和验证案例

以下是求解first集合和follow集合的C语言代码，同时也提供了一个验证案例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_RULES 100
#define MAX_SYMBOLS 100
#define MAX_INPUT 100

typedef struct {
    char symbol;
    int is_terminal;
} Symbol;

typedef struct {
    Symbol lhs;
    Symbol rhs[MAX_SYMBOLS];
    int num_symbols;
} Rule;

typedef struct {
    Symbol symbols[MAX_SYMBOLS];
    int num_symbols;
} Production;

Symbol epsilon = {'_', 1};

Rule rules[MAX_RULES];
int num_rules = 0;

Symbol symbols[MAX_SYMBOLS];
int num_symbols = 0;

char input[MAX_INPUT];
int input_len = 0;

Production first_sets[MAX_SYMBOLS];
Production follow_sets[MAX_SYMBOLS];

void add_rule(char* rule_str) {
    Symbol lhs;
    lhs.symbol = rule_str[0];
    lhs.is_terminal = 0;
    int num_rhs_symbols = 0;
    Rule rule = {lhs};
    int i = 2;
    while (rule_str[i] != '\0') {
        Symbol rhs_symbol = {rule_str[i], 1};
        if (isupper(rule_str[i])) {
            rhs_symbol.is_terminal = 0;
        }
        rule.rhs[num_rhs_symbols] = rhs_symbol;
        num_rhs_symbols++;
        i++;
    }
    rule.num_symbols = num_rhs_symbols;
    rules[num_rules] = rule;
    num_rules++;
}

void add_symbol(Symbol symbol) {
    for (int i = 0; i < num_symbols; i++) {
        if (symbols[i].symbol == symbol.symbol) {
            return;
        }
    }
    symbols[num_symbols] = symbol;
    num_symbols++;
}

Rule find_rule(Symbol lhs) {
    for (int i = 0; i < num_rules; i++) {
        if (rules[i].lhs.symbol == lhs.symbol) {
            return rules[i];
        }
    }
    Rule empty_rule = {lhs};
    return empty_rule;
}

int is_epsilon(Symbol symbol) {
    return symbol.symbol == '_' && symbol.is_terminal == 1;
}

void add_production(Production* production, Symbol symbol) {
    if (is_epsilon(symbol)) {
        return;
    }
    for (int i = 0; i < production->num_symbols; i++) {
        if (production->symbols[i].symbol == symbol.symbol) {
            return;
        }
    }
    production->symbols[production->num_symbols] = symbol;
    production->num_symbols++;
}

void compute_first_sets() {
    for (int i = 0; i < num_symbols; i++) {
        Production first_set = {{}, 0};
        Symbol symbol = symbols[i];
        if (symbol.is_terminal) {
            add_production(&first_set, symbol);
        } else {
            for (int j = 0; j < num_rules; j++) {
                Rule rule = rules[j];
                if (rule.lhs.symbol == symbol.symbol) {
                    Symbol first_rhs_symbol = rule.rhs[0];
                    if (is_epsilon(first_rhs_symbol)) {
                        add_production(&first_set, epsilon);
                    } else {
                        Production first_rhs_set = {{}, 0};
                        int k = 0;
                        while (k < rule.num_symbols) {
                            Symbol rhs_symbol = rule.rhs[k];
                            compute_first_sets();
                            Production rhs_first_set = first_sets[symbols - rhs_symbol];
                            for (int l = 0; l < rhs_first_set.num_symbols; l++) {
                                Symbol first_rhs_production = rhs_first_set.symbols[l];
                                add_production(&first_rhs_set, first_rhs_production);
                            }
                            if (!is_epsilon(rhs_symbol)) {
                                break;
                            }
                            k++;
                        }
                        for (int l = 0; l < first_rhs_set.num_symbols; l++) {
                            Symbol first_rhs_production = first_rhs_set.symbols[l];
                            add_production(&first_set, first_rhs_production);
                        }
                    }
                }
            }
        }
        first_sets[i] = first_set;
    }
}

void compute_follow_sets() {
    follow_sets[0].symbols[0] = symbols[0]; // Add $ to start symbol's follow set
    follow_sets[0].num_symbols = 1;
    for (int i = 0; i < num_symbols; i++) {
        Symbol symbol = symbols[i];
        for (int j = 0; j < num_rules; j++) {
            Rule rule = rules[j];
            for (int k = 0; k < rule.num_symbols; k++) {
                Symbol rhs_symbol = rule.rhs[k];
                if (rhs_symbol.symbol == symbol.symbol) {
                    if (k == rule.num_symbols - 1) { // If symbol is at end of rule, add follow set of rule's LHS symbol
                        Production follow_set = follow_sets[i];
                        add_production(&follow_sets[symbols - rule.lhs], follow_set.symbols, follow_set.num_symbols);
                    } else { // Otherwise, add first set of symbols after symbol
                        Symbol next_symbol = rule.rhs[k + 1];
                        if (next_symbol.is_terminal) {
                            add_production(&follow_sets[i], next_symbol);
                        } else {
                            Production next_first_set = first_sets[symbols - next_symbol];
                            for (int l = 0; l < next_first_set.num_symbols; l++) {
                                Symbol next_first_production = next_first_set.symbols[l];
                                add_production(&follow_sets[i], next_first_production);
                            }
                            if (is_epsilon(next_first_set.symbols[0])) { // If next symbol can produce epsilon, add follow set of rule's LHS symbol
                                Production follow_set = follow_sets[i];
                                add_production(&follow_sets[symbols - rule.lhs], follow_set.symbols, follow_set.num_symbols);
                            }
                        }
                    }
                }
            }
        }
    }
}

void print_production(Production production) {
    printf("{ ");
    for (int i = 0; i < production.num_symbols; i++) {
        printf("%c ", production.symbols[i].symbol);
    }
    printf("}\n");
}

void print_first_sets() {
    printf("First Sets:\n");
    for (int i = 0; i < num_symbols; i++) {
        printf("%c: ", symbols[i].symbol);
        Production first_set = first_sets[i];
        print_production(first_set);
    }
}

void print_follow_sets() {
    printf("Follow Sets:\n");
    for (int i = 0; i < num_symbols; i++) {
        printf("%c: ", symbols[i].symbol);
        Production follow_set = follow_sets[i];
        print_production(follow_set);
    }
}

int main() {
    char rules_str[MAX_RULES][MAX_SYMBOLS];
    int num_rules_str = 0;
    printf("Enter grammar rules (one per line, '->' between LHS and RHS):\n");
    while (fgets(rules_str[num_rules_str], MAX_SYMBOLS, stdin)) {
        if (strcmp(rules_str[num_rules_str], "\n") == 0) {
            break;
        }
        num_rules_str++;
    }
    for (int i = 0; i < num_rules_str; i++) {
        add_rule(rules_str[i]);
    }
    for (int i = 0; i < num_rules; i++) {
        Rule rule = rules[i];
        add_symbol(rule.lhs);
        for (int j = 0; j < rule.num_symbols; j++) {
            Symbol rhs_symbol = rule.rhs[j];
            add_symbol(rhs_symbol);
        }
    }
    compute_first_sets();
    compute_follow_sets();
    print_first_sets();
    print_follow_sets();
    return 0;
}

下面是一个验证案例，假设输入以下文法规则：

S -> ACB
A -> a | _
B -> b | _
C -> c | _

则输出的first集合和follow集合应该如下：

First Sets:
S: { a c _ }
A: { a _ }
B: { b _ }
C: { c _ }
Follow Sets:
S: { $ }
A: { b $ }
B: { c $ }
C: { $ }