LL(1) 语法分析程序：识别算术表达式

LL(1) 语法分析程序：识别算术表达式

一、 题目

编制 LL(1) 分析法的语法分析程序

二、 目的

通过设计、编制、调试一个典型的语法分析程序，能识别由加'+'、乘'*'、括号'()'、操作数所组成的算术表达式，其文法如下：

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | i

三、 要求

1. 程序功能（举例）

   • 输入：# i1 * ( i2 + i3 ) #
   • 输出：SUCCESS
   • 输入：# i1 * ( i2 + i3 #
   • 输出：FOUND ERROR

2. 程序能够正确识别由加'+'、乘'*'、括号'()'、操作数所组成的算术表达式。

3. 程序能够检测输入的算术表达式是否符合文法规定，若不符合则输出错误信息。

4. 使用 C 语言编写程序。

四、 思路

1. 首先需要将文法转换为 LL(1) 文法。

2. 根据 LL(1) 文法，构造预测分析表。

3. 对输入的算术表达式进行语法分析，采用栈来存储符号串和状态。

4. 判断输入的算术表达式是否符合文法规定。

五、 代码实现

1. 将文法转换为 LL(1) 文法：

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | i

2. 构造预测分析表：

| | + | * | ( | ) | i | # | |-----|-----|-----|-----|-----|-----|-----| | E | NULL | NULL | E→TE' | NULL | E→TE' | NULL | | E' | +TE' | NULL | NULL | ε | ε | ε | | T | NULL | NULL | T→FT' | NULL | T→FT' | NULL | | T' | ε | *FT' | ε | ε | ε | ε | | F | NULL | NULL | (E) | NULL | i | NULL |

3. 代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100

typedef struct {
    char nonTerm; // 非终结符
    char term; // 终结符
    char rule[10]; // 产生式
} Prediction;

Prediction table[5][6] = {
    {{NULL, NULL, NULL}, {NULL, NULL, NULL}, {'E', 'i', "E→TE'"}, {NULL, NULL, NULL}, {'E', 'i', "E→TE'"}, {NULL, NULL, NULL}},
    {{'E', '+', "E'→+TE'"}, {NULL, NULL, NULL}, {NULL, NULL, NULL}, {'E', 'ε', "E'→ε"}, {NULL, NULL, NULL}, {'E', 'ε', "E'→ε"}},
    {{NULL, NULL, NULL}, {NULL, NULL, NULL}, {'T', 'i', "T→FT'"}, {NULL, NULL, NULL}, {'T', 'i', "T→FT'"}, {NULL, NULL, NULL}},
    {{'T', 'ε', "T'→ε"}, {'T', '*', "T'→*FT'"}, {NULL, NULL, NULL}, {'T', 'ε', "T'→ε"}, {NULL, NULL, NULL}, {'T', 'ε', "T'→ε"}},
    {{NULL, NULL, NULL}, {NULL, NULL, NULL}, {'F', '(', "F→(E)"}, {NULL, NULL, NULL}, {'F', 'i', "F→i"}, {NULL, NULL, NULL}}
};

int top = 0; // 栈顶指针
char stack[MAX] = {'#', 'E'}; // 栈
char input[MAX]; // 输入的算术表达式
int index = 0; // 输入串的指针

void push(char c) { // 入栈
    stack[++top] = c;
}

void pop() { // 出栈
    top--;
}

char getTop() { // 获取栈顶元素
    return stack[top];
}

char getNextInput() { // 获取下一个输入字符
    return input[index++];
}

void printStack() { // 输出栈中元素
    for(int i = 0; i <= top; i++) {
        printf("%c", stack[i]);
    }
    printf("\n");
}

void printInput() { // 输出输入串
    for(int i = index; i < strlen(input); i++) {
        printf("%c", input[i]);
    }
    printf("\n");
}

void error() { // 错误处理
    printf("FOUND ERROR\n");
    exit(0);
}

int main() {
    printf("请输入算术表达式：");
    scanf("%s", input);
    push('#');
    printf("步骤\t栈\t\t输入\t\t操作\n");
    while(1) {
        char X = getTop(); // 获取栈顶符号
        char a = getNextInput(); // 获取输入符号
        if(X == a) { // 如果栈顶符号和输入符号相同，则出栈
            if(X == '#') { // 如果栈顶符号为#，则语法分析成功
                printf("SUCCESS\n");
                exit(0);
            }
            pop();
        }
        else if(X == 'ε') { // 如果栈顶符号为ε，则出栈
            pop();
        }
        else if(X >= 'A' && X <= 'Z') { // 如果栈顶符号为非终结符
            int row = X - 'E' + 2; // 获取行
            int col = a == '+' ? 0 : a == '*' ? 1 : a == '(' ? 2 : a == ')' ? 3 : a == 'i' ? 4 : 5; // 获取列
            Prediction p = table[row][col]; // 获取预测分析表中的产生式
            if(p.rule[0] == NULL) { // 如果预测分析表中没有产生式，则出错
                error();
            }
            printf("%d\t", index - 1);
            printStack();
            printf("\t\t");
            printInput();
            printf("\t\t使用%s规约\n", p.rule);
            pop(); // 弹出栈顶符号
            if(p.rule[2] != 'ε') { // 如果产生式不是ε，则将产生式的右侧符号压入栈中
                for(int i = strlen(p.rule) - 1; i >= 2; i--) {
                    push(p.rule[i]);
                }
            }
        }
        else { // 如果栈顶符号为终结符，则出错
            error();
        }
    }
    return 0;
}