基于算符优先分析法的表达式语法分析与四元式生成

1. 概述

本文介绍如何使用C语言实现一个简单的表达式语法分析器，该分析器基于算符优先分析法，并将分析结果转换为等价的四元式序列。

2. 算法描述

2.1 文法

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

2.2 算符优先分析表

| | + | * | i | ( | ) | # ||-----|-----|-----|-----|-----|-----|-----|| + | > | < | < | < | > | > || * | > | > | < | < | > | > || i | > | > | | | > | > || ( | < | < | < | < | = | || ) | > | > | | | > | > || # | < | < | < | < | | = |

2.3 四元式结构ctypedef struct { char op; // 操作符 int arg1; // 第一个操作数的地址 int arg2; // 第二个操作数的地址 int result; // 存放结果的地址} Quaternary;

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

#define N 10#define M 15

typedef struct { char op; // 操作符 int arg1; // 第一个操作数的地址 int arg2; // 第二个操作数的地址 int result; // 存放结果的地址} Quaternary;

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

int main(int argc, char* argv[]) { char syn[M]; // 语法栈 int top = 0; // 栈顶指针 int top_in = 1; // 移进指针 int handle[N]; // <栈 int top_h = -1; // <栈顶指针 char w; // 当前单词 char exp[M]; // 表达式区 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 = E', 'E + E', 'E - E', 'E * E', 'E / E' }; // 产生式 Quaternary q[N]; // 存放四元式的数组 int q_cnt = 0; // 四元式计数器 int temp_var = 0; // 临时变量计数器

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

syn[0] = '#';       // 初始化    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] = '�';            i = 0;            while (strcmp(rules[i], syn + handle[top_h]) && i < N) {                i++;            }            if (i == N) {                code = 0;                printf('error!

'); break; } else { // 归约并生成四元式 if (i == 0) { // i = E q[q_cnt].op = '='; q[q_cnt].arg1 = syn[handle[top_h] - 1]; // i q[q_cnt].arg2 = -1; q[q_cnt].result = syn[handle[top_h] + 1]; // E q_cnt++; } else { // E + E, E - E, E * E, E / E q[q_cnt].op = syn[handle[top_h] + 1]; q[q_cnt].arg1 = syn[handle[top_h] - 1]; q[q_cnt].arg2 = syn[handle[top_h] + 2]; q[q_cnt].result = temp_var++; syn[handle[top_h]] = 'E'; syn[handle[top_h] + 1] = q[q_cnt].result + '0'; top = handle[top_h] + 1; top_in = top + 1; top_h--; q_cnt++; } } } } if (code) { printf('OK! '); // 打印四元式序列 for (i = 0; i < q_cnt; i++) { printf('%c %d %d %d ', q[i].op, q[i].arg1, q[i].arg2, q[i].result); } } else { printf('error! '); } return 0