用C语言代码写一个lr分析程序

下面是一个简单的 LR(0) 分析器，使用 C 语言编写：

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

#define MAX_PRODUCTIONS 100
#define MAX_SYMBOLS 100
#define MAX_STATES 100

char productions[MAX_PRODUCTIONS][MAX_SYMBOLS];
int num_productions = 0;
char symbols[MAX_SYMBOLS];
int num_symbols = 0;
int start_symbol = 0;
int num_states = 0;

int closure[MAX_STATES][MAX_PRODUCTIONS];
int num_items[MAX_STATES] = {0};
int goto_table[MAX_STATES][MAX_SYMBOLS] = {-1};

struct action {
    char type;
    int state;
};
struct action action_table[MAX_STATES][MAX_SYMBOLS];

void add_production(char *prod) {
    strcpy(productions[num_productions], prod);
    num_productions++;
}

int find_symbol(char sym) {
    for (int i = 0; i < num_symbols; i++) {
        if (symbols[i] == sym) {
            return i;
        }
    }
    return -1;
}

void add_symbol(char sym) {
    if (find_symbol(sym) == -1) {
        symbols[num_symbols] = sym;
        num_symbols++;
    }
}

void add_item(int state, int prod) {
    for (int i = 0; i < num_items[state]; i++) {
        if (closure[state][i] == prod) {
            return;
        }
    }
    closure[state][num_items[state]] = prod;
    num_items[state]++;
}

void closure_operation(int state) {
    for (int i = 0; i < num_items[state]; i++) {
        char *prod = productions[closure[state][i]];
        if (prod[2] == '\0') {
            continue;
        }
        char sym = prod[2];
        int sym_index = find_symbol(sym);
        if (sym_index == -1) {
            add_symbol(sym);
            sym_index = num_symbols - 1;
        }
        for (int j = 0; j < num_productions; j++) {
            if (productions[j][0] == sym) {
                add_item(state, j);
            }
        }
    }
}

void goto_operation(int state, char sym) {
    int new_state = num_states;
    num_states++;
    for (int i = 0; i < num_items[state]; i++) {
        char *prod = productions[closure[state][i]];
        if (prod[2] == sym) {
            add_item(new_state, closure[state][i]+1);
        }
    }
    goto_table[state][find_symbol(sym)] = new_state;
}

void build_LR0_parser() {
    add_production("S->E");
    add_production("E->E+T");
    add_production("E->T");
    add_production("T->T*F");
    add_production("T->F");
    add_production("F->(E)");
    add_production("F->i");

    add_symbol('S');
    add_symbol('E');
    add_symbol('T');
    add_symbol('F');
    add_symbol('+');
    add_symbol('*');
    add_symbol('(');
    add_symbol(')');
    add_symbol('i');

    start_symbol = find_symbol('S');

    add_item(0, 0);
    closure_operation(0);

    for (int i = 0; i < num_states; i++) {
        for (int j = 0; j < num_symbols; j++) {
            char sym = symbols[j];
            if (goto_table[i][j] == -1) {
                goto_operation(i, sym);
            }
        }
    }

    for (int i = 0; i < num_states; i++) {
        for (int j = 0; j < num_symbols; j++) {
            char sym = symbols[j];
            int goto_state = goto_table[i][j];
            if (goto_state != -1) {
                action_table[i][j].type = 's';
                action_table[i][j].state = goto_state;
            } else {
                for (int k = 0; k < num_items[i]; k++) {
                    char *prod = productions[closure[i][k]];
                    if (prod[2] == '\0') {
                        if (prod[0] == symbols[j]) {
                            action_table[i][j].type = 'r';
                            action_table[i][j].state = closure[i][k];
                        }
                    }
                }
            }
        }
    }

    action_table[0][find_symbol('$')].type = 'a';
}

void print_parser() {
    printf("Productions:\n");
    for (int i = 0; i < num_productions; i++) {
        printf("%d: %s\n", i, productions[i]);
    }
    printf("Symbols:\n");
    for (int i = 0; i < num_symbols; i++) {
        printf("%d: %c\n", i, symbols[i]);
    }
    printf("Start symbol: %c\n", symbols[start_symbol]);
    printf("States:\n");
    for (int i = 0; i < num_states; i++) {
        printf("State %d:\n", i);
        for (int j = 0; j < num_items[i]; j++) {
            printf("%d: %s\n", j, productions[closure[i][j]]);
        }
    }
    printf("GOTO Table:\n");
    for (int i = 0; i < num_states; i++) {
        for (int j = 0; j < num_symbols; j++) {
            if (goto_table[i][j] != -1) {
                printf("GOTO(%d, %c) = %d\n", i, symbols[j], goto_table[i][j]);
            }
        }
    }
    printf("Action Table:\n");
    for (int i = 0; i < num_states; i++) {
        for (int j = 0; j < num_symbols; j++) {
            if (action_table[i][j].type == 's') {
                printf("ACTION(%d, %c) = S%d\n", i, symbols[j], action_table[i][j].state);
            } else if (action_table[i][j].type == 'r') {
                printf("ACTION(%d, %c) = R%d\n", i, symbols[j], action_table[i][j].state);
            } else if (action_table[i][j].type == 'a') {
                printf("ACTION(%d, $) = accept\n", i);
            }
        }
    }
}

int main() {
    build_LR0_parser();
    print_parser();
    return 0;
}

这个程序实现了一个 LR(0) 分析器，它使用了一个简单的文法：

S -> E
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> i

程序输出了一些有关文法、状态、GOTO 表和 ACTION 表的信息。这些信息可以用来分析输入的句子并确定它是否是文法的句子。