算符优先分析法实现及四元式生成 - C语言代码示例 - 常规

算符优先分析法实现及四元式生成 - C语言代码示例

本代码使用 C 语言实现算符优先分析法，并根据输入的表达式生成对应的四元式。

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

#define N 4
#define MAX_EXP_LEN 15
#define MAX_STACK_SIZE 15

typedef struct {
    char op;  // 运算符
    int arg1; // 第一个操作数在表达式中的位置
    int arg2; // 第二个操作数在表达式中的位置
    int result; // 结果在表达式中的位置
} Quad; // 四元式

int map(char ch) {
    char loca[7] = {'+', '*', 'i', '(', ')', '#', '\0'};
    char *p = strchr(loca, ch);
    if (p == NULL) {
        return -1;
    } else {
        return p - loca;
    }
}

int main(int argc, char* argv[]) {
    char syn[MAX_STACK_SIZE]; // 语法栈
    int top = 0; // 栈顶指针
    int top_in = 1; // 移进指针
    int handle[MAX_STACK_SIZE]; // <栈
    int top_h = 0; // <栈顶指针
    char exp[MAX_EXP_LEN]; // 表达式区
    int i_exp = 0; // 表达式指针
    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 i, j; // 表行和列
    int code; // 表项
    char rules[N][10] = {' + ', ' * ', 'i', '( )'}; // 产生式
    Quad quads[MAX_STACK_SIZE]; // 存放四元式的数组
    int quad_cnt = 0; // 已生成的四元式数量

    printf('please input your expression:');
    scanf('%s', exp); // 输入表达式

    syn[0] = '#'; // 初始化
    top = 0;
    top_in = 1;
    handle[0] = 0;
    top_h = 0;

    char w = exp[i_exp++]; // read(w)
    while (1) {
        // 查分析表code=prio(i,j)
        i = map(syn[top]); // 定位行和列
        j = map(w);
        code = prio[i][j]; // 查表
        // 空或OK
        if (code == 0 || code == 4) {
            break;
        }
        // 栈操作 and 输入操作
        if (code < 3) { // < or =,push(w)
            syn[top_in] = w; // 进栈
            if (code == 1) { // 记录句柄的左端位置
                handle[++top_h] = top + 1; 
            }
            top = top_in++;
            w = exp[i_exp++];
        } else { // >,REDUCE(SYN)
            syn[top_in] = '\0';
            i = 0;
            while (strcmp(rules[i], syn + handle[top_h]) && i < N) { // 比较产生式
                i++;
            }
            if (i == N) {
                code = 0;
                printf('err!');
                break;
            } else {
                // 归约
                Quad q = {syn[handle[top_h] + 1], handle[top_h] - 1, handle[top_h] + 1, handle[top_h] + 2};
                quads[quad_cnt++] = q;
                syn[handle[top_h]] = ' ';
                top = handle[top_h] - 1;
                top_in = handle[top_h] + 1;
                top_h--;
            }
        }
    }

    if (code) {
        printf('OK!\n');
        // 输出四元式
        printf('Quads:\n');
        for (i = 0; i < quad_cnt; i++) {
            Quad q = quads[i];
            printf('(%c, %d, %d, %d)\n', q.op, q.arg1, q.arg2, q.result);
        }
    } else {
        printf('err!\n');
    }

    return 0;
}

实验目的

掌握算符优先分析法的基本原理和方法。
熟悉算符优先分析法的实现过程。
学会使用算符优先分析法生成四元式。

实验结果分析

该代码实现了算符优先分析法，并能够根据输入的表达式生成对应的四元式。在实验结果分析中，我们可以发现该代码的实现过程较为简单，主要是利用一个语法栈和一个移进指针来模拟算符优先分析法的过程。同时，该代码还使用了一个优先分析表和一些产生式来辅助进行分析。

在实验结果中，我们可以看到该代码的输出结果包括两部分，一部分是“OK!”或“err!”，表示输入的表达式是否符合语法规则；另一部分是生成的四元式，其中每个四元式都包括一个运算符、两个操作数和一个结果。通过这些四元式，我们可以进一步分析表达式的计算过程。

心得体会

算符优先分析法是一种重要的语法分析方法，对于理解计算机编译原理中的语法分析过程具有重要意义。在实现过程中，需要仔细理解算符优先分析法的原理和方法，并且需要熟练掌握相关的数据结构和算法。同时，生成四元式也是算符优先分析法的重要应用之一，对于理解程序的计算过程也具有重要意义。