ll1文法分析器 c语言

LL(1)文法分析器是一种自顶向下的语法分析器，它可以用来检查一个输入的程序是否符合给定的文法规则。下面是一个简单的LL(1)文法分析器的C语言实现：

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

#define MAX_TOKEN_LEN 100
#define MAX_INPUT_LEN 1000

/* 文法规则 */
typedef struct {
    char *left;
    char *right[10];
    int len;
} Rule;

/* 分析表 */
typedef struct {
    char *nonterm;
    char *term[10];
    int len;
    int action[10];
} TableEntry;

/* 词法分析器 */
typedef struct {
    char token[MAX_TOKEN_LEN];
    char type[MAX_TOKEN_LEN];
} Token;

/* 全局变量 */
Rule rules[10];
TableEntry table[10];
int num_rules = 0;
int num_table_entries = 0;

/* 辅助函数 */
void error(char *msg) {
    fprintf(stderr, "Error: %s\n", msg);
    exit(1);
}

void add_rule(char *left, char **right, int len) {
    rules[num_rules].left = left;
    rules[num_rules].len = len;
    for (int i = 0; i < len; i++) {
        rules[num_rules].right[i] = right[i];
    }
    num_rules++;
}

void add_table_entry(char *nonterm, char **term, int len, int action) {
    table[num_table_entries].nonterm = nonterm;
    table[num_table_entries].len = len;
    for (int i = 0; i < len; i++) {
        table[num_table_entries].term[i] = term[i];
    }
    table[num_table_entries].action[0] = action;
    num_table_entries++;
}

int is_nonterm(char *symbol) {
    for (int i = 0; i < num_rules; i++) {
        if (strcmp(rules[i].left, symbol) == 0) {
            return 1;
        }
    }
    return 0;
}

int find_rule(char *nonterm, char *term) {
    for (int i = 0; i < num_rules; i++) {
        if (strcmp(rules[i].left, nonterm) == 0) {
            for (int j = 0; j < rules[i].len; j++) {
                if (strcmp(rules[i].right[j], term) == 0) {
                    return i;
                }
            }
        }
    }
    return -1;
}

/* 语法分析器 */
void parse(char *input) {
    Token tokens[100];
    char *p = strtok(input, " \t\n");
    int num_tokens = 0;
    while (p != NULL) {
        strcpy(tokens[num_tokens].token, p);
        if (is_nonterm(p)) {
            strcpy(tokens[num_tokens].type, "nonterm");
        } else {
            strcpy(tokens[num_tokens].type, "term");
        }
        num_tokens++;
        p = strtok(NULL, " \t\n");
    }
    tokens[num_tokens].type[0] = '\0';

    char *stack[100];
    int top = 0;
    stack[top] = "$";
    stack[top + 1] = rules[0].left;

    int i = 0;
    while (i < num_tokens) {
        if (strcmp(stack[top + 1], tokens[i].token) == 0) {
            top++;
            i++;
        } else if (is_nonterm(stack[top + 1])) {
            int rule_idx = find_rule(stack[top + 1], tokens[i].token);
            if (rule_idx == -1) {
                error("Invalid input");
            }
            top++;
            for (int j = rules[rule_idx].len - 1; j >= 0; j--) {
                top--;
                stack[top + 1] = rules[rule_idx].right[j];
            }
        } else {
            error("Invalid input");
        }
    }

    if (strcmp(stack[top + 1], "$") == 0 && tokens[i].type[0] == '\0') {
        printf("Input is valid\n");
    } else {
        error("Invalid input");
    }
}

/* 主函数 */
int main() {
    // 添加规则
    char *left;
    char *right[10];
    int len;
    left = "E";
    right[0] = "T";
    right[1] = "E'";
    len = 2;
    add_rule(left, right, len);
    left = "E'";
    right[0] = "+";
    right[1] = "T";
    right[2] = "E'";
    len = 3;
    add_rule(left, right, len);
    right[0] = "-";
    right[1] = "T";
    right[2] = "E'";
    len = 3;
    add_rule(left, right, len);
    right[0] = "epsilon";
    len = 1;
    add_rule(left, right, len);
    left = "T";
    right[0] = "F";
    right[1] = "T'";
    len = 2;
    add_rule(left, right, len);
    left = "T'";
    right[0] = "*";
    right[1] = "F";
    right[2] = "T'";
    len = 3;
    add_rule(left, right, len);
    right[0] = "/";
    right[1] = "F";
    right[2] = "T'";
    len = 3;
    add_rule(left, right, len);
    right[0] = "epsilon";
    len = 1;
    add_rule(left, right, len);
    left = "F";
    right[0] = "(";
    right[1] = "E";
    right[2] = ")";
    len = 3;
    add_rule(left, right, len);
    right[0] = "id";
    len = 1;
    add_rule(left, right, len);

    // 添加分析表
    char *nonterm;
    char *term[10];
    int len;
    nonterm = "E";
    term[0] = "(";
    term[1] = "id";
    len = 2;
    add_table_entry(nonterm, term, len, 0);
    term[0] = "+";
    term[1] = "-";
    term[2] = "$";
    len = 3;
    add_table_entry(nonterm, term, len, 1);
    nonterm = "E'";
    term[0] = "+";
    len = 1;
    add_table_entry(nonterm, term, len, 2);
    term[0] = "-";
    len = 1;
    add_table_entry(nonterm, term, len, 3);
    term[0] = ")";
    term[1] = "$";
    len = 2;
    add_table_entry(nonterm, term, len, 4);
    nonterm = "T";
    term[0] = "(";
    term[1] = "id";
    len = 2;
    add_table_entry(nonterm, term, len, 5);
    nonterm = "T'";
    term[0] = "+";
    term[1] = "-";
    term[2] = ")";
    term[3] = "$";
    len = 4;
    add_table_entry(nonterm, term, len, 6);
    term[0] = "*";
    len = 1;
    add_table_entry(nonterm, term, len, 7);
    term[0] = "/";
    len = 1;
    add_table_entry(nonterm, term, len, 8);
    term[0] = "+";
    term[1] = "-";
    term[2] = "*";
    term[3] = "/";
    term[4] = ")";
    term[5] = "$";
    len = 6;
    add_table_entry(nonterm, term, len, 9);

    // 测试输入
    char input[MAX_INPUT_LEN];
    printf("Enter input string: ");
    fgets(input, MAX_INPUT_LEN, stdin);
    parse(input);

    return 0;
}

这个实现中，我们先定义了一个规则结构体和一个分析表结构体。规则结构体定义了一个产生式的左部和右部，分析表结构体定义了一个非终结符和一个终结符之间的关系以及对应的动作。然后我们定义了一个词法分析器，它将输入的字符串分割成一个一个的单词，并判断每个单词是一个终结符还是一个非终结符。最后，我们定义了一个语法分析器，它使用一个栈来模拟语法分析的过程，根据分析表中的关系和动作来决定下一步该怎么做。如果最终栈顶是$，并且所有输入都已被处理，那么说明输入符合文法规则。否则，就是输入有误。

这个实现只是一个简单的示例，实际上LL(1)文法分析器的实现要更为复杂，需要考虑很多细节问题。