lr(0)分析程序c语言,C语言编写源程序建立LR(1)分析器

以下是一个简单的 LR(0) 分析程序的 C 语言代码示例：

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

#define MAX_RULES 100
#define MAX_SYMBOLS 100
#define MAX_STATES 100

int num_rules = 0;
char rules[MAX_RULES][MAX_SYMBOLS];
char lhs[MAX_RULES];
int rhs_len[MAX_RULES];
char *rhs[MAX_RULES][MAX_SYMBOLS];
int num_symbols = 0;
char symbols[MAX_SYMBOLS];
int num_states = 0;
int goto_table[MAX_STATES][MAX_SYMBOLS];
int action_table[MAX_STATES][MAX_SYMBOLS];
int state_stack[MAX_STATES];
int symbol_stack[MAX_STATES];
int top = 0;

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

void add_rule(char *rule) {
    char *p = rule;
    int i;
    while (isupper(*p)) {
        p++;
    }
    lhs[num_rules] = *(p - 1);
    rhs_len[num_rules] = strlen(p);
    for (i = 0; i < rhs_len[num_rules]; i++) {
        if (isupper(p[i])) {
            rhs[num_rules][i] = malloc(sizeof(char));
            *rhs[num_rules][i] = p[i];
        } else {
            rhs[num_rules][i] = malloc(sizeof(char));
            *rhs[num_rules][i] = get_symbol_index(p[i]);
        }
    }
    num_rules++;
}

void add_state(int *state) {
    int i;
    for (i = 0; i < num_states; i++) {
        if (memcmp(goto_table[i], state, num_symbols * sizeof(int)) == 0) {
            return;
        }
    }
    memcpy(goto_table[num_states], state, num_symbols * sizeof(int));
    num_states++;
}

void closure(int *state) {
    int i, j, k, l;
    int changed = 1;
    while (changed) {
        changed = 0;
        for (i = 0; i < num_rules; i++) {
            for (j = 0; j < rhs_len[i]; j++) {
                if (isupper(*rhs[i][j])) {
                    for (k = 0; k < num_rules; k++) {
                        if (lhs[k] == *rhs[i][j]) {
                            int match = 1;
                            for (l = 0; l < j; l++) {
                                if (state[l] != *rhs[i][l]) {
                                    match = 0;
                                    break;
                                }
                            }
                            if (match) {
                                if (!state[j]) {
                                    state[j] = -1;
                                    changed = 1;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

void goto_state(int *state, int symbol, int *new_state) {
    int i;
    memcpy(new_state, state, num_symbols * sizeof(int));
    for (i = 0; i < num_rules; i++) {
        if (*rhs[i][0] == symbol) {
            new_state[0] = i + 1;
            closure(new_state);
            add_state(new_state);
        }
    }
}

void build_lr0_automaton() {
    int i, j;
    int initial_state[MAX_SYMBOLS] = {1};
    add_state(initial_state);
    closure(initial_state);
    for (i = 0; i < num_states; i++) {
        for (j = 0; j < num_symbols; j++) {
            if (isupper(symbols[j])) {
                int new_state[MAX_SYMBOLS] = {0};
                goto_state(goto_table[i], symbols[j], new_state);
                if (new_state[0]) {
                    if (symbols[j] == 'S') {
                        action_table[i][j] = 'A';
                    } else {
                        goto_table[i][j] = num_states;
                    }
                }
            }
        }
        for (j = 0; j < num_rules; j++) {
            if (goto_table[i][lhs[j] - 'A']) {
                action_table[i][lhs[j] - 'A'] = j + 1;
            }
        }
    }
}

int main() {
    char rule[MAX_SYMBOLS];
    int i, j;
    printf("Enter the rules (one per line, blank line to end):\n");
    while (fgets(rule, MAX_SYMBOLS, stdin) && rule[0] != '\n') {
        add_rule(rule);
    }
    build_lr0_automaton();
    printf("\nLR(0) automaton:\n");
    printf("  States:");
    for (i = 0; i < num_states; i++) {
        printf(" %d", i);
    }
    printf("\n  Symbols:");
    for (i = 0; i < num_symbols; i++) {
        printf(" %c", symbols[i]);
    }
    printf("\n  Goto table:\n");
    for (i = 0; i < num_states; i++) {
        printf("    %d:", i);
        for (j = 0; j < num_symbols; j++) {
            printf(" %d", goto_table[i][j]);
        }
        printf("\n");
    }
    printf("  Action table:\n");
    for (i = 0; i < num_states; i++) {
        printf("    %d:", i);
        for (j = 0; j < num_symbols; j++) {
            if (isupper(symbols[j])) {
                if (action_table[i][j]) {
                    printf(" %c%d", action_table[i][j] == 'A' ? 'A' : 'S', action_table[i][j] - 1);
                } else {
                    printf("  ");
                }
            } else {
                printf("  ");
            }
        }
        printf("\n");
    }
    return 0;
}

如果您想要建立 LR(1) 分析器，可以使用 Lex 和 Yacc 工具来生成 C 语言代码。以下是一个简单的示例：

Lex 文件（lexer.l）：

%{
#include "y.tab.h"
%}
%%
[ \t\n]+ ;
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
[-+*/] { return yytext[0]; }
. ;
%%

Yacc 文件（parser.y）：

%{
#include <stdio.h>
int yylex();
int yyerror(char *);
%}

%token NUMBER
%left '+' '-'
%left '*' '/'
%right UMINUS

%%
program: /* empty */
| program statement '\n'
;

statement: expression { printf("%d\n", $1); }
;

expression: NUMBER
| expression '+' expression { $$ = $1 + $3; }
| expression '-' expression { $$ = $1 - $3; }
| expression '*' expression { $$ = $1 * $3; }
| expression '/' expression { $$ = $1 / $3; }
| '-' expression %prec UMINUS { $$ = -$2; }
;

%%

int main() {
yyparse();
return 0;
}

然后使用以下命令生成分析器：

lex lexer.l
yacc -d parser.y
gcc lex.yy.c y.tab.c -o parser

这将生成一个名为 parser 的可执行文件，可以使用以下命令运行它：

./parser

您可以输入简单的算术表达式，并在按下 Enter 键后看到计算结果。