ll1文法分析器 c语言

LL(1)文法分析器是一种自顶向下的语法分析器，其输入是一个 LL(1)文法和一个待分析的句子，输出是一个语法分析树。C语言可以用来实现LL(1)文法分析器。下面是一个简单的LL(1)文法分析器的C语言代码示例：

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

#define MAX_STACK_SIZE 100
#define MAX_INPUT_SIZE 100

char stack[MAX_STACK_SIZE];
char input[MAX_INPUT_SIZE];
char *grammar[4] = {"E->E+T", "E->T", "T->T*F", "T->F"};

int top = -1;

char pop() {
    if (top == -1) {
        printf("Stack underflow!\n");
        exit(1);
    }
    return stack[top--];
}

void push(char c) {
    if (top == MAX_STACK_SIZE - 1) {
        printf("Stack overflow!\n");
        exit(1);
    }
    stack[++top] = c;
}

int is_terminal(char c) {
    if (c == '+' || c == '*' || c == '(' || c == ')' || c == 'i') {
        return 1;
    }
    return 0;
}

int get_terminal_index(char c) {
    if (c == '+') {
        return 0;
    } else if (c == '*') {
        return 1;
    } else if (c == '(') {
        return 2;
    } else if (c == ')') {
        return 3;
    } else if (c == 'i') {
        return 4;
    }
    return -1;
}

int get_grammar_index(char *production) {
    int i;
    for (i = 0; i < 4; i++) {
        if (strcmp(grammar[i], production) == 0) {
            return i;
        }
    }
    return -1;
}

void print_stack() {
    int i;
    for (i = 0; i <= top; i++) {
        printf("%c", stack[i]);
    }
    printf("\n");
}

void print_input(int index) {
    int i;
    for (i = index; i < strlen(input); i++) {
        printf("%c", input[i]);
    }
    printf("\n");
}

void parse() {
    int table[3][5][2] = {
        {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {1, 3}},
        {{2, 4}, {0, 0}, {0, 0}, {0, 0}, {2, 4}},
        {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {3, 3}}
    };
    push('$');
    push('E');
    int i = 0;
    while (stack[top] != '$') {
        if (is_terminal(stack[top])) {
            if (stack[top] == input[i]) {
                pop();
                i++;
            } else {
                printf("String not accepted!\n");
                return;
            }
        } else {
            int row = get_grammar_index(stack[top]);
            int col = get_terminal_index(input[i]);
            if (row == -1 || col == -1) {
                printf("String not accepted!\n");
                return;
            }
            int prod = table[row][col][0];
            if (prod == 0) {
                printf("String not accepted!\n");
                return;
            }
            int len = strlen(grammar[prod - 1]) - 3;
            pop();
            if (len > 0) {
                int j;
                for (j = len - 1; j >= 0; j--) {
                    push(grammar[prod - 1][j]);
                }
            }
            print_stack();
            print_input(i);
        }
    }
    printf("String accepted!\n");
}

int main() {
    printf("Enter the input string: ");
    scanf("%s", input);
    parse();
    return 0;
}

这个LL(1)文法分析器采用了一个手动构建的LL(1)分析表，并且只能分析一个简单的表达式语法。在实际的应用中，需要根据具体的文法构建分析表，并且需要使用更高级的算法来处理更复杂的语法。