C语言实现算术表达式语法分析器与四元式生成

本文介绍如何使用C语言实现一个简单的算术表达式语法分析器，该分析器采用算符优先分析法，并能够生成相应的四元式。

代码实现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[7][7]={{3,1,1,1,3,3,1}, //优先分析表，增加了'-'的处理 {3,3,1,1,3,3,1}, {3,3,0,0,3,3,0}, {1,1,1,1,2,0,1}, {3,3,0,0,3,3,0}, {1,1,1,1,0,4,1}, {3,1,1,1,3,3,1}}; 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 函数： - 定义语法栈、栈顶指针、移进指针、<栈、<栈顶指针、当前单词、表达式区、表达式指针、优先分析表、表行和列、表项、产生式、四元式编号、保存四元式的数组等变量。 - 初始化语法栈、栈顶指针、移进指针、<栈和<栈顶指针。 - 读取第一个字符，进入循环。 - 在循环中： - 查表得到操作码。 - 根据操作码进行进栈或归约操作。 - 如果进行归约操作，则根据产生式生成相应的四元式。 - 根据最终的操作码输出结果，如果分析成功，则输出四元式；否则输出错误信息。

测试数据

输入以下表达式：

i+i*i#

输出结果：

OK!四元式：(i = t0)(i = t1)(* t1 t2)(+ t0 t3)

总结

本文介绍了如何使用C语言实现一个简单的算术表达式语法分析器，并讲解了如何生成四元式。代码示例清晰易懂，方便读者理解和学习。