算符优先分析法实现算术表达式语法分析并生成四元式

// 使用算符优先分析法实现算术表达式语法分析并生成四元式 #include <stdio.h> #include <string.h> #define N 4 #define MAX_EXP_LEN 15 #define MAX_STACK_SIZE 15 #define MAX_HANDLE_SIZE 10

// 定义四元式结构体 typedef struct { char op; char arg1; char arg2; char result; } Quad;

// 定义语法栈和移进栈 char syn[MAX_STACK_SIZE]; char input[MAX_EXP_LEN]; int top_syn = 0; int top_in = 1;

// 定义句柄栈和栈顶指针 int handle[MAX_HANDLE_SIZE]; int top_handle = -1;

// 定义表达式区和表达式指针 char exp[MAX_EXP_LEN]; int exp_ptr = 0;

// 定义四元式区和四元式指针 Quad quad_table[MAX_STACK_SIZE]; int quad_ptr = 0;

// 根据字符返回其在优先分析表中的位置 int map(char ch) { char loca[7] = {'+', '*', 'i', '(', ')', '#'}; char *p = strchr(loca, ch); if (p == NULL) { return -1; } else { return p - loca; } }

// 根据句柄生成四元式 void gen_quad(int handle_start, int handle_end) { char op = syn[handle_end]; char arg1 = syn[handle_end - 2]; char arg2 = syn[handle_end - 1]; char result = syn[handle_end + 1]; quad_table[quad_ptr++] = (Quad){op, arg1, arg2, result}; }

int main() { 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} }; char rules[N][10] = {' + ', ' * ', 'i', '( )'}; printf('Please input your expression: '); scanf('%s', exp);

syn[top_syn] = '#';
char w = exp[exp_ptr++];  // 读入第一个字符
while (1) {
    int i = map(syn[top_syn]);
    int j = map(w);
    int code = prio[i][j];
    if (code == 0 || code == 4) {  // 空或OK
        break;
    } else if (code < 3) {  // < or =, push(w)
        syn[top_in] = w;
        if (code == 1) {  // 记录句柄的左端位置
            handle[++top_handle] = top_syn + 1;
        }
        top_syn = top_in++;
        w = exp[exp_ptr++];
    } else {  // >, REDUCE(SYN)
        syn[top_in] = '\0';
        int i = 0;
        while (strcmp(rules[i], syn + handle[top_handle]) && i < N) {  // 比较产生式
            i++;
        }
        if (i == N) {
            code = 0;
            printf('Error: Invalid expression!\n');
            break;
        } else {
            if (i == 3) {  // 生成四元式
                gen_quad(handle[top_handle], top_syn);
            }
            syn[handle[top_handle]] = ' ';
            top_syn = handle[top_handle] - 1;
            top_in = handle[top_handle] + 1;
            top_handle--;
        }
    }
}

if (code) {
    printf('OK!\n');
    // 输出四元式
    printf('The quadruple table is:\n');
    printf('OP\tARG1\tARG2\tRESULT\n');
    for (int i = 0; i < quad_ptr; i++) {
        printf('%c\t%c\t%c\t%c\n', quad_table[i].op, quad_table[i].arg1, quad_table[i].arg2, quad_table[i].result);
    }
}
return 0;

}

// 输入输出实例： // Please input your expression: i+i*i# // OK! // The quadruple table is: // OP ARG1 ARG2 RESULT // * i i t0 // + i t0 t1 // = t1 i