用c++编程实现基于【ll(1)预测分析表】语法分析器

LL(1)预测分析表是一种自上而下的语法分析方法，它通过构造预测分析表来实现对输入串的分析。预测分析表的构造需要经过以下步骤：

1. 对于每个非终结符A，求出FIRST(A)和FOLLOW(A)集合。
2. 对于每个文法产生式A -> α，对于FIRST(α)中的每个终结符a，将A -> α加入M[A, a]中。
3. 如果ε∈FIRST(α)，则对于FOLLOW(A)中的每个终结符b，将A -> α加入M[A, b]中。
4. 如果A -> ε是一个产生式，则对于FOLLOW(A)中的每个终结符b，将A -> ε加入M[A, b]中。

其中，M[A, a]表示预测分析表的表项，表示在非终结符A和终结符a的情况下，选择产生式A -> α进行分析。

下面是一个基于LL(1)预测分析表的语法分析器的实现，使用C语言编写：

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

#define MAX_SIZE 100
#define MAX_SYMBOL 10

char nonterminals[MAX_SIZE][MAX_SYMBOL];  // 非终结符
int num_nonterminals = 0;  // 非终结符数量

char terminals[MAX_SIZE][MAX_SYMBOL];  // 终结符
int num_terminals = 0;  // 终结符数量

char production[MAX_SIZE][MAX_SYMBOL][MAX_SIZE];  // 产生式
int num_productions = 0;  // 产生式数量

char prediction_table[MAX_SIZE][MAX_SIZE][MAX_SIZE];  // 预测分析表

// 判断是否为终结符
int is_terminal(char symbol[]) {
    for (int i = 0; i < num_terminals; i++) {
        if (strcmp(terminals[i], symbol) == 0) {
            return 1;
        }
    }
    return 0;
}

// 判断是否为非终结符
int is_nonterminal(char symbol[]) {
    for (int i = 0; i < num_nonterminals; i++) {
        if (strcmp(nonterminals[i], symbol) == 0) {
            return 1;
        }
    }
    return 0;
}

// 求FIRST集合
void first_set(char symbol[], char first[]) {
    if (is_terminal(symbol)) {
        sprintf(first, "%s", symbol);
    } else {
        for (int i = 0; i < num_productions; i++) {
            if (strcmp(production[i][0], symbol) == 0) {
                if (strcmp(production[i][1], "ε") == 0) {
                    first_set(production[i][1], first);
                } else {
                    first_set(production[i][1], first);
                    if (is_nonterminal(production[i][1])) {
                        char temp[MAX_SIZE];
                        first_set(production[i][1], temp);
                        strcat(first, temp);
                    }
                }
            }
        }
    }
}

// 求FOLLOW集合
void follow_set(char symbol[], char follow[]) {
    if (strcmp(symbol, nonterminals[0]) == 0) {
        strcat(follow, "$");
    }
    for (int i = 0; i < num_productions; i++) {
        int j = 1;
        while (j < strlen(production[i][1])) {
            if (strcmp(production[i][1] + j, symbol) == 0) {
                char temp[MAX_SIZE];
                if (j + 1 < strlen(production[i][1])) {
                    first_set(production[i][1] + j + 1, temp);
                    strcat(follow, temp);
                }
                if (j + 1 >= strlen(production[i][1]) || is_nonterminal(production[i][1] + j + 1)) {
                    char temp[MAX_SIZE];
                    follow_set(production[i][0], temp);
                    strcat(follow, temp);
                }
            }
            j++;
        }
    }
}

// 构造预测分析表
void construct_prediction_table() {
    for (int i = 0; i < num_productions; i++) {
        char first[MAX_SIZE] = "";
        first_set(production[i][1], first);
        for (int j = 0; j < strlen(first); j++) {
            if (strcmp(first + j, "ε") == 0) {
                char follow[MAX_SIZE] = "";
                follow_set(production[i][0], follow);
                for (int k = 0; k < strlen(follow); k++) {
                    sprintf(prediction_table[i][follow[k]][0], "%d", i);
                }
            } else {
                sprintf(prediction_table[i][first[j]][0], "%d", i);
            }
        }
    }
}

// 打印预测分析表
void print_prediction_table() {
    printf("%-10s", "");
    for (int i = 0; i < num_terminals; i++) {
        printf("%-10s", terminals[i]);
    }
    printf("\n");
    for (int i = 0; i < num_productions; i++) {
        printf("%-10s", production[i][0]);
        for (int j = 0; j < num_terminals; j++) {
            printf("%-10s", prediction_table[i][terminals[j]][0]);
        }
        printf("\n");
    }
}

// 语法分析
void parse(char input[]) {
    int stack[MAX_SIZE];
    int top = -1;
    stack[++top] = 0;
    int i = 0;
    while (i < strlen(input)) {
        int j = 0;
        while (j < num_productions && strcmp(production[j][0], nonterminals[stack[top]]) != 0) {
            j++;
        }
        if (j == num_productions) {
            printf("Error!\n");
            exit(1);
        }
        char prediction[MAX_SIZE] = "";
        sprintf(prediction, "%s", prediction_table[j][input[i]][0]);
        if (strcmp(prediction, "") == 0) {
            printf("Error!\n");
            exit(1);
        }
        if (strcmp(prediction, "ε") != 0) {
            for (int k = strlen(prediction) - 1; k >= 0; k--) {
                stack[++top] = atoi(prediction + k);
            }
        } else {
            top--;
        }
        i += strcmp(prediction, "ε") == 0 ? 0 : 1;
    }
    if (strcmp(nonterminals[stack[top]], nonterminals[0]) == 0) {
        printf("Success!\n");
    } else {
        printf("Error!\n");
    }
}

int main() {
    // 读入文法
    printf("请输入文法，每个产生式一行，以“#”结束：\n");
    char input[MAX_SIZE];
    while (1) {
        scanf("%s", input);
        if (strcmp(input, "#") == 0) {
            break;
        }
        sscanf(input, "%s -> %s", production[num_productions][0], production[num_productions][1]);
        num_productions++;
        if (!is_nonterminal(production[num_productions - 1][0])) {
            sprintf(nonterminals[num_nonterminals++], "%s", production[num_productions - 1][0]);
        }
        for (int i = 0; i < strlen(production[num_productions - 1][1]); i++) {
            char symbol[MAX_SYMBOL];
            sprintf(symbol, "%c", production[num_productions - 1][1][i]);
            if (!is_nonterminal(symbol) && !is_terminal(symbol) && strcmp(symbol, "ε") != 0) {
                sprintf(terminals[num_terminals++], "%s", symbol);
            }
            if (is_nonterminal(symbol)) {
                sprintf(nonterminals[num_nonterminals++], "%s", symbol);
            }
        }
    }
    // 构造预测分析表
    construct_prediction_table();
    // 打印预测分析表
    printf("预测分析表：\n");
    print_prediction_table();
    // 输入待分析串
    printf("请输入待分析串：\n");
    scanf("%s", input);
    // 语法分析
    parse(input);
    return 0;
}

该程序首先读入文法，然后通过求FIRST集合、FOLLOW集合和预测分析表来实现对输入串的语法分析。程序中使用了三个全局数组（nonterminals、terminals和production）来存储文法中的非终结符、终结符和产生式，使用了另一个全局数组（prediction_table）来存储预测分析表。函数first_set和follow_set分别用于求FIRST集合和FOLLOW集合，函数construct_prediction_table用于构造预测分析表，函数print_prediction_table用于打印预测分析表，函数parse用于对输入串进行语法分析。