基于算符优先分析法的表达式语法分析与中间代码生成

本文介绍如何利用算符优先分析法对算术表达式进行语法分析，并将其转化为四元式表示的中间代码。

1. 问题描述

给定算术表达式和赋值语句的文法：

S → i = EE → E + E | E - E | E * E | E / E | (E) | i

其中：

S 表示赋值语句* E 表示算术表达式* i 表示标识符 (例如变量名)* +, -, , / 分别表示加、减、乘、除运算符 () 表示括号

要求：

根据算符优先分析法，对输入的赋值语句进行语法分析。2. 将语法分析的结果转化为等价的一组基本操作，并用四元式表示。

2. 代码实现c#include <stdio.h>#include <string.h>

#define N 100#define M 100

// 将字符映射到优先级表中的索引int map(char ch) { char loca[7] = {'+', '*', 'i', '(', ')', '#'}; char *p = strchr(loca, ch); if (p == NULL) { return -1; } else { return p - loca; }}

int main(int argc, char* argv[]) { char syn[N]; // 语法栈 int top = 0; // 栈顶指针 int top_in = 1; // 移进指针 int handle[N]; // <栈 int top_h = -1; // <栈顶指针 char w; // 当前单词 char exp[N]; // 表达式区 int i_exp = 0; // 表达式指针 char basic_op[M][20]; // 基本操作数组 int top_op = -1; // 基本操作栈顶指针 // 优先级表 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('请输入表达式: ');    scanf('%s', exp);  // 输入表达式

syn[0] = '#';  // 初始化        w = exp[i_exp++];  // 读取第一个单词

while (1) {        // 查分析表 code = prio(i, j)        int i = map(syn[top]);  // 定位行        int j = map(w);  // 定位列        int 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] = '�';            int i = 0;            while (strcmp(rules[i], syn + handle[top_h]) && i < N) {  // 比较产生式                i++;            }            if (i == N) {                code = 0;                printf('表达式错误!

'); break; } else { syn[handle[top_h]] = ' '; // 归约 top = handle[top_h] - 1; top_in = handle[top_h] + 1; top_h--;

            // 生成基本操作                if (strcmp(rules[i], 'i') == 0) {                    sprintf(basic_op[++top_op], 'PUSH %c', syn[top_in]);                } else if (strcmp(rules[i], ' + ') == 0) {                    sprintf(basic_op[++top_op], 'POP R2');                    sprintf(basic_op[++top_op], 'POP R1');                    sprintf(basic_op[++top_op], 'ADD R1, R2');                    sprintf(basic_op[++top_op], 'PUSH R1');                } else if (strcmp(rules[i], ' * ') == 0) {                    sprintf(basic_op[++top_op], 'POP R2');                    sprintf(basic_op[++top_op], 'POP R1');                    sprintf(basic_op[++top_op], 'MUL R1, R2');                    sprintf(basic_op[++top_op], 'PUSH R1');                }                 // else if (strcmp(rules[i], '( )') == 0) {                //     // do nothing                // }            }        }    }

if (code) {        printf('语法分析成功!

');

    // 输出基本操作        printf('基本操作序列:

'); for (int i = 0; i <= top_op; i++) { printf('%s ', basic_op[i]); } } else { printf('语法分析失败! '); }

return 0