c语言实现LL(1)分析器

下面是一个简单的C语言实现LL(1)分析器的代码示例，用于对输入的符号串进行语法分析。

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

#define MAX_PROD 20
#define MAX_NT 10
#define MAX_T 10

char prod[MAX_PROD][MAX_NT+MAX_T+1];
char nt[MAX_NT];
char t[MAX_T];
char first[MAX_NT][MAX_T];
char follow[MAX_NT][MAX_T];
char select[MAX_PROD][MAX_T];
char table[MAX_NT][MAX_T+1][MAX_PROD+1];
int nnt, ntlen, ntstart, nprod, nterm;

int is_nt(char c)
{
    int i;
    for (i = 0; i < nnt; i++)
        if (nt[i] == c)
            return 1;
    return 0;
}

int is_t(char c)
{
    int i;
    for (i = 0; i < nterm; i++)
        if (t[i] == c)
            return 1;
    return 0;
}

int find_nt(char c)
{
    int i;
    for (i = 0; i < nnt; i++)
        if (nt[i] == c)
            return i;
    return -1;
}

int find_t(char c)
{
    int i;
    for (i = 0; i < nterm; i++)
        if (t[i] == c)
            return i;
    return -1;
}

void print_table()
{
    int i, j, k;
    printf("LL(1) Parsing Table:\n");
    printf("NT/T\t");
    for (j = 0; j < nterm; j++)
        printf("%c\t", t[j]);
    printf("$\t\n");
    for (i = 0; i < nnt; i++) {
        printf("%c\t", nt[i]);
        for (j = 0; j <= nterm; j++) {
            for (k = 0; k < strlen(table[i][j]); k++)
                printf("%s ", prod[atoi(&table[i][j][k])]);
            printf("\t");
        }
        printf("\n");
    }
}

void parse(char *input)
{
    char stack[MAX_NT+MAX_T];
    int top = 0;
    stack[top] = '$';
    stack[++top] = ntstart;
    char *p = input;
    while (*p != '\0') {
        char X = stack[top--];
        if (is_t(X) || X == '$') {
            if (X == *p) {
                p++;
            } else {
                printf("Error: unexpected symbol %c\n", *p);
                return;
            }
        } else if (is_nt(X)) {
            int j = find_t(*p);
            int i = find_nt(X);
            if (table[i][j][0] == '\0') {
                printf("Error: no production for %c on input %c\n", X, *p);
                return;
            } else if (table[i][j][1] != '\0') {
                printf("Error: multiple productions for %c on input %c\n", X, *p);
                return;
            } else {
                char *q = prod[atoi(&table[i][j][0])];
                int len = strlen(q);
                while (len > 0) {
                    stack[++top] = q[--len];
                }
            }
        } else {
            printf("Error: unknown symbol %c\n", X);
            return;
        }
    }
    char X = stack[top--];
    if (X == ntstart && *p == '$') {
        printf("Parsing successful!\n");
    } else {
        printf("Parsing failed!\n");
    }
}

int main()
{
    int i, j, k, l;
    printf("Enter the number of non-terminals: ");
    scanf("%d", &nnt);
    printf("Enter the non-terminals: ");
    for (i = 0; i < nnt; i++)
        scanf(" %c", &nt[i]);
    printf("Enter the start symbol: ");
    scanf(" %c", &ntstart);
    printf("Enter the number of terminals: ");
    scanf("%d", &nterm);
    printf("Enter the terminals: ");
    for (i = 0; i < nterm; i++)
        scanf(" %c", &t[i]);
    printf("Enter the number of productions: ");
    scanf("%d", &nprod);
    printf("Enter the productions:\n");
    for (i = 0; i < nprod; i++) {
        scanf("%s", prod[i]);
        int idx = find_nt(prod[i][0]);
        for (j = 2; j < strlen(prod[i]); j++) {
            if (is_nt(prod[i][j])) {
                int k = find_nt(prod[i][j]);
                for (l = 0; l < nterm; l++) {
                    if (first[k][l] == '1')
                        select[i][l] = '1';
                }
                if (first[k][nterm] == '1') {
                    for (l = 0; l < nterm; l++)
                        if (follow[idx][l] == '1')
                            select[i][l] = '1';
                }
                break;
            } else if (is_t(prod[i][j])) {
                int k = find_t(prod[i][j]);
                select[i][k] = '1';
                break;
            }
        }
    }
    for (i = 0; i < nnt; i++) {
        for (j = 0; j < nterm; j++) {
            int flag = 0;
            for (k = 0; k < nprod; k++) {
                if (prod[k][0] == nt[i] && select[k][j] == '1') {
                    if (flag == 1) {
                        table[i][j][0] = '\0';
                        table[i][j][1] = '\0';
                        break;
                    } else {
                        table[i][j][0] = k + '0';
                        flag = 1;
                    }
                }
            }
            if (flag == 0)
                table[i][j][0] = '\0';
        }
    }
    for (i = 0; i < nnt; i++) {
        int flag = 0;
        for (k = 0; k < nprod; k++) {
            if (prod[k][0] == nt[i] && select[k][nterm] == '1') {
                if (flag == 1) {
                    table[i][nterm][0] = '\0';
                    table[i][nterm][1] = '\0';
                    break;
                } else {
                    table[i][nterm][0] = k + '0';
                    flag = 1;
                }
            }
        }
        if (flag == 0)
            table[i][nterm][0] = '\0';
    }
    print_table();
    char input[100];
    printf("Enter the input string: ");
    scanf("%s", input);
    parse(input);
    return 0;
}

在实现过程中，我们需要先读入文法规则，然后根据文法规则计算FIRST集合、FOLLOW集合和SELECT集合，并构造预测分析表。接下来，我们可以对输入的符号串进行语法分析。

在这个示例中，我们使用了一个简单的错误处理机制，对于一些无法识别的符号、无法找到产生式和多个可能的产生式等情况，都会返回一个错误信息。如果符号串符合文法规则，我们会输出一条“Parsing successful!”的信息。

总之，这个示例可以帮助我们深入理解LL(1)分析法的实现过程，以及对文法规则的转换和处理。