C语言算符优先分析法实现表达式求值与四元式生成

C语言实现算符优先分析法进行表达式求值与四元式生成

本文将介绍如何使用C语言实现基于算符优先分析法的表达式求值器，并详细说明其原理、代码实现以及如何生成四元式。

实验原理

算符优先分析法是一种自底向上的语法分析方法，它根据算符之间的优先级关系对表达式进行分析，最终得到表达式的值。其核心在于构建一个优先分析表，表中记录了不同算符之间的优先级关系。

该代码实现的表达式求值器主要步骤如下：

初始化: 初始化语法栈、移进指针、语义栈等数据结构，并将结束符'#'压入语法栈。2. 读取字符: 从表达式中读取一个字符。3. 查表: 根据当前读取的字符和语法栈顶的符号，查阅优先分析表，确定操作是移进还是规约。4. 移进: 若分析表指示移进，则将当前字符压入语法栈，并将读取指针后移。5. 规约: 若分析表指示规约，则根据产生式对语法栈进行规约，并将规约后的结果压入语法栈。同时，生成相应的四元式。6. 重复步骤2-5: 直到语法栈中只剩下开始符号和结束符号，且输入缓冲区为空。

代码分析c#include 'string.h'#include <stdio.h>#define N 10

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[15]; //语法栈 int top; //栈顶指针 int top_in; //移进指针 int handle[10]; //<栈 int top_h; //<栈顶指针 char w; //当前单词 char exp[15]; //表达式区 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'}; //产生式 int count = 0; // 记录四元式编号 char result[100][10]; // 保存四元式

printf('请输入您的表达式：');    scanf('%s',exp);                             //输入表达式

syn[0]='#';                                  //初始化    top=0; top_in=1;    handle[0]=0;    top_h=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('err!');               break;           }           else           {               // 归约               if (i == 4) {                   // i                   char t[10];                   sprintf(t, 't%d', count);                   strcpy(result[count], exp + handle[top_h]);                   strcat(result[count], '  ');                   strcat(result[count], '=');                   strcat(result[count], '  ');                   strcat(result[count], t);                   count++;                   syn[handle[top_h]] = t[0];               } else {                   // E + E / E * E                   char t1[10], t2[10], t3[10];                   sprintf(t1, 't%d', count);                   count++;                   sprintf(t2, 't%d', count);                   count++;                   sprintf(t3, 't%d', count);                   count++;                   strcpy(result[count - 3], syn + handle[top_h]);                   strcpy(result[count - 2], exp + handle[top_h] + 2);                   strcpy(result[count - 1], exp + handle[top_h] + 1);                   strcat(result[count - 1], '  ');                   strcat(result[count - 1], t1);                   strcat(result[count - 1], '  ');                   strcat(result[count - 1], t2);                   strcat(result[count - 2], '  ');                   strcat(result[count - 2], t3);                   strcat(result[count - 3], '  ');                   strcat(result[count - 3], t2);                   syn[handle[top_h]] = t1[0];               }               top= handle[top_h]-1;               top_in= handle[top_h]+1;               top_h--;            }        }    }    if (code)    {        printf('OK!

'); // 输出四元式 printf('四元式： '); for (int i = 0; i < count; i++) { printf('(%s) ', result[i]); } } else { printf('err!'); } return 0;}

代码解释:

map函数: 用于将字符映射到优先分析表中对应的行或列。2. main函数: 程序入口，定义了语法分析过程中需要用到的数据结构。3. prio二维数组: 存储算符优先分析表。4. rules二维数组: 存储产生式。5. result二维数组: 存储生成的四元式。6. count变量: 记录四元式的个数。7. 代码中使用了一个循环来模拟语法分析的过程，根据优先分析表进行移进或规约操作，并生成相应的四元式。

总结

本文介绍了如何使用C语言实现基于算符优先分析法的表达式求值器，并详细解释了代码实现。算符优先分析法是一种常用的语法分析方法，在编译原理和程序设计语言领域有着广泛的应用。