LR分析器实现：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;

}

实验步骤：

定义结构体Quad，存放四元式的信息。
定义map函数，将字符映射为对应的数字，用于查找优先分析表中的表项。
定义语法栈syn、<栈handle和存放四元式的数组quads。
输入表达式exp，并初始化语法栈、栈顶指针、移进指针、<栈和<栈顶指针。
读取表达式中的第一个字符w。
进入循环，查找优先分析表中的表项code，根据code进行栈操作或输入操作。
如果code为0或4，跳出循环。
如果code小于3，将w进栈，如果code为1，记录句柄的左端位置。
如果code大于等于3，将语法栈中句柄位置到栈顶的字符串与产生式进行比较，如果匹配成功，则进行归约操作，生成对应的四元式，更新语法栈、移进指针和<栈顶指针。
循环结束后，根据code输出OK或err，并输出生成的四元式。

心得体会：

这个实验让我更加深入地理解了LR分析表的构造和LR分析过程。LR分析表是根据文法的产生式和终结符集合构造出来的，可以通过查表的方式快速地进行语法分析。在实现LR分析器的过程中，需要使用语法栈、<栈和移进指针等数据结构，对栈进行相应的操作，同时还需要生成对应的四元式。这个实验让我更加熟悉了C语言的语法和数据结构，同时也让我更加深入地理解了编译原理中的一些重要概念和算法。