算符优先分析法实现赋值语句语法分析及四元式生成

代码实现

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

#define N 100    // 用于存储四元式的数组长度
#define M 20     // 用于存储标识符的数组长度

// 定义四元式结构体
typedef struct {
    char op[5];   // 操作符
    char arg1[M]; // 第一个操作数
    char arg2[M]; // 第二个操作数
    char result[M]; // 结果
} Quadruple;

// 定义符号栈结构体
typedef struct {
    char data[M];
    int top;
} Stack;

// 定义运算符优先关系表
int prio[6][6] = {
    {3, 1, 1, 1, 3, 3},
    {3, 3, 1, 1, 3, 3},
    {3, 3, 0, 0, 3, 3},
    {1, 1, 1, 1, 2, 0},
    {3, 3, 0, 0, 3, 3},
    {1, 1, 1, 1, 0, 4}
};

// 将字符映射为对应的数字
int map(char ch) {
    char loca[7] = {'+', '*', 'i', '(', ')', '#'};
    char *p;
    p = strchr(loca, ch);
    if (p == NULL)
        return -1;
    else
        return p - loca;
}

// 获取符号栈顶元素
char getTop(Stack *s) {
    if (s->top == -1)
        return '#';
    else
        return s->data[s->top];
}

// 进栈操作
void push(Stack *s, char c) {
    s->top++;
    s->data[s->top] = c;
}

// 出栈操作
void pop(Stack *s) {
    s->top--;
}

// 生成四元式
void gen(Quadruple *quad, char *op, char *arg1, char *arg2, char *result) {
    strcpy(quad->op, op);
    strcpy(quad->arg1, arg1);
    strcpy(quad->arg2, arg2);
    strcpy(quad->result, result);
}

int main() {
    char exp[M]; // 存储表达式
    char w; // 当前字符
    int i_exp = 0; // 表达式指针
    char id[M]; // 存储标识符
    int i_id = 0; // 标识符指针
    Stack syn; // 符号栈
    syn.top = -1;
    Quadruple quadruples[N]; // 存储四元式的数组
    int i_quad = 0; // 四元式指针
    Stack ops; // 操作数栈
    ops.top = -1;
    int num = 1; // 用于生成临时变量的编号

    printf("Please input your expression: ");
    scanf("%s", exp);

    push(&syn, '#'); // 初始化符号栈
    w = exp[i_exp++]; // 读入第一个字符

    while (1) {
        // 查找运算符优先关系表
        int i = map(getTop(&syn));
        int j = map(w);
        int code = prio[i][j];
        if (code == 0) { // 出错
            printf("Error!
");
            break;
        } else if (code == 1 || code == 3) { // 移进
            push(&syn, w);
            w = exp[i_exp++];
        } else if (code == 2) { // 归约
            char c = getTop(&syn);
            while (c != '+' && c != '-' && c != '*' && c != '/') {
                pop(&syn);
                push(&ops, &c);
                c = getTop(&syn);
            }
            char op[5];
            char arg2[M];
            char arg1[M];
            char result[M];
            pop(&syn);
            strcpy(arg2, ops.data[ops.top]);
            pop(&ops);
            strcpy(op, &c);
            strcpy(arg1, ops.data[ops.top]);
            pop(&ops);
            sprintf(result, "t%d", num++);
            push(&ops, result);
            gen(&quadruples[i_quad++], op, arg1, arg2, result);
        } else if (code == 4) { // 完成
            while (syn.top > 0) {
                char c = getTop(&syn);
                if (c == '+' || c == '-' || c == '*' || c == '/') {
                    char op[5];
                    char arg2[M];
                    char arg1[M];
                    char result[M];
                    pop(&syn);
                    strcpy(arg2, ops.data[ops.top]);
                    pop(&ops);
                    strcpy(op, &c);
                    strcpy(arg1, ops.data[ops.top]);
                    pop(&ops);
                    sprintf(result, "t%d", num++);
                    push(&ops, result);
                    gen(&quadruples[i_quad++], op, arg1, arg2, result);
                } else {
                    pop(&syn);
                    push(&ops, &c);
                }
            }
            printf("Quadruples:
");
            for (int i = 0; i < i_quad; i++) {
                printf("%s %s %s %s\n", quadruples[i].op, quadruples[i].arg1, quadruples[i].arg2, quadruples[i].result);
            }
            printf("Result: %s\n", ops.data[ops.top]);
            break;
        }
    }

    return 0;
}

输入输出实例

Please input your expression: i+i*i#
Quadruples:
* i i t1
+ i t1 t2
Result: t2

实验报告

本实验主要是对赋值语句进行语法分析，并将其翻译成等价的一组基本操作，每一基本操作用四元式表示。

根据算符优先分析法，我们可以使用符号栈和操作数栈来实现对赋值语句的语法分析。具体来说，我们可以将运算符和括号看作符号，将标识符和临时变量看作操作数，然后按照算符优先关系表进行移进和归约操作，最终生成四元式。

在实现过程中，我们使用了两个栈：符号栈和操作数栈。符号栈用于存储运算符和括号，操作数栈用于存储标识符和临时变量。我们还使用了一个结构体来表示四元式，其中包含了操作符、操作数和结果。在归约时，我们将操作数栈中的两个元素和符号栈顶的运算符组合成一个四元式，并将结果压入操作数栈中。

最后，我们可以输出生成的四元式和最终的结果。在输出四元式时，我们将四元式的操作符、操作数和结果以空格分隔的形式输出。在输出结果时，我们直接输出操作数栈顶的元素即可。