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

#include 'stdio.h'#include 'string.h'#define N 6 // 产生式数量

// 将字符映射到优先分析表中的行列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[8][8]={ {3,1,1,1,3,3,5,0}, // 优先分析表 {3,3,1,1,3,3,5,0}, {3,3,2,2,3,3,5,0}, {3,3,2,2,3,3,5,0}, {3,3,3,3,3,3,5,0}, {3,3,3,3,3,3,5,0}, {1,1,1,1,2,2,0,4}, {1,1,1,1,0,0,4,0}}; int i,j; //表行和列 int code; //表项 char rules[N][10]={' + ',' - ',' * ',' / ','( )','i'}; //产生式 int count = 0; // 记录四元式的数量 char op[10]; // 运算符栈 int top_op = -1; // 运算符栈顶指针 char arg1[10]; // 操作数1栈 int top_arg1 = -1; // 操作数1栈顶指针 char arg2[10]; // 操作数2栈 int top_arg2 = -1; // 操作数2栈顶指针 char result[10]; // 结果栈 int top_result = -1; // 结果栈顶指针

printf('please input your expression:');    scanf('%s',exp);                             //输入表达式    strcat(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 == 0 || i == 1 || i == 2 || i == 3) {  // E+E, E-E, E*E, E/E                    top_op--;                    strcpy(arg2, result[top_result--]);                    strcpy(arg1, result[top_result--]);                    strcpy(result[++top_result], 't');                    sprintf(result[top_result] + 1, '%d', ++count);                    printf('(%s,%s,%s,%s)\n', i == 0 ? 'ADD' : (i == 1 ? 'SUB' : (i == 2 ? 'MUL' : 'DIV')), arg1, arg2, result[top_result]);                } else if (i == 4) {  // (E)                    top_op--;                    top_arg1--;                    top_arg2--;                    top_result--;                } else {  // i                    strcpy(result[++top_result], &syn[handle[top_h]]);                }                syn[handle[top_h]]=' ';                            //归约                top= handle[top_h]-1;                top_in= handle[top_h]+1;                top_h--;            }        }        // 移进过程中生成四元式        if (w == '+' || w == '-' || w == '*' || w == '/') {            op[++top_op] = w;        } else if (w == 'i') {            strcpy(result[++top_result], &exp[i_exp - 1]);        }     }    if (code)        printf('OK!');    else        printf('err!');    return 0;}