算符优先文法分析器

//文法为

//(0)E'→ #E#

//(1)E → E+T

//(2)E → T

//(3)T → T*F

//(4)T → F

//(5)F → P^F

//(6)F → P

//(7)P → (E)

//(8)P → i

//根据算符优先文法的分析规则求得终结符优先关系表

// + * ^ i ( ) #

// + > < < < < > >

// * > > < < < > >

// ^ > > < < < > >

// i > > > > >

// ( < < < < < =

// ) > > > > >

// # < < < < < =

#include<stdlib.h>

#include<stdio.h>

#include<dos.h>

#include<stdio.h>

#include<string.h>

#include<ctype.h>

#include<iostream.h>

#define SIZE 128

char youxian[7][7]; //算符优先关系数组

char lexbuf[SIZE]; //存放输入的要进行分析的句子

char lex[SIZE]; //存放剩余串

char fenxizhan[SIZE];//分析栈

void fenxi();

int panduanyou(char x);

void shengyuchuan();

int k;

void zengjia();

void main()

{

{ //将算符优先关系存放在算符优先关系数组里

youxian[0][0]='>';

youxian[0][2]='<';

youxian[0][3]='<';

youxian[0][4]='<';

youxian[0][5]='>';

youxian[0][6]='>';

//______________________________________________________________

youxian[1][0]='>';

youxian[1][1]='>';

youxian[1][2]='<';

youxian[1][3]='<';

youxian[1][4]='<';

youxian[1][5]='>';

youxian[1][6]='>';

//_______________________________________________________________

youxian[2][0]='>';

youxian[2][1]='>';

youxian[2][2]='<';

youxian[2][3]='<';

youxian[2][4]='<';

youxian[2][5]='>';

youxian[2][6]='>';

//_______________________________________________________________

youxian[3][0]='>';

youxian[3][1]='>';

youxian[3][2]='>';

youxian[3][3]='$';//无优先关系的用$表示

youxian[3][4]='$';

youxian[3][5]='>';

youxian[3][6]='>';

//_________________________________________________________________ youxian[4][0]='<';

youxian[4][1]='<';

youxian[4][2]='<';

youxian[4][3]='<';

youxian[4][4]='<';

youxian[4][5]='=';

youxian[4][6]='$';

//_________________________________________________________________ youxian[5][0]='>';

youxian[5][1]='>';

youxian[5][2]='>';

youxian[5][3]='$';

youxian[5][4]='$';

youxian[5][6]='>';

//__________________________________________________________________ youxian[6][0]='<';

youxian[6][1]='<';

youxian[6][2]='<';

youxian[6][3]='<';

youxian[6][4]='<';

youxian[6][5]='$';

youxian[6][6]='=';

//__________________________________________________________________ }

printf("现在就要进行算符优先分析，请做好准备 \n");

printf("***************************************************\n");

printf("请输入要进行分析的句子\n");

cin.get(lexbuf,SIZE); //将输入的字符串存到数组

printf("步骤 栈 优先关系 当前符号 剩余输入串 移进或归约\n"); k=0; fenxizhan[k]='#';

fenxizhan[k+1]='\0';

int lenth,i1; //初始化 剩余串数组为输入串

lenth=strlen(lexbuf);

for(i1=0;i1<lenth;i1++)

lex[i1]=lexbuf[i1];

lex[i1]='\0';

fenxi();

}

void fenxi()

{

int i,j,f,z,z1,n,n1,z4,n4;

int flag=0;//操作的步骤数

char a; //存放正在分析的字符

char p6,Q,p1,p4;

f=strlen(lexbuf); //测出数组的长度

for(i=0;i<f;i++)

{

a=lexbuf[i];

if(fenxizhan[k]=='+'||fenxizhan[k]=='*'||fenxizhan[k]=='^'||fenxizhan[k]=='i'||fenxizhan[k]=='('||fenxizhan[k]==')'||fenxizhan[k]=='#')

j=k;

else

j=k-1;

z=panduanyou(fenxizhan[j]);// 从优先关系表中查出s[j]和a的优先关系 if(a=='+'||a=='*'||a=='^'||a=='i'||a=='('||a==')'||a=='#')

n=panduanyou(a);

else //如果句子含有不是终结符集合里的其它字符，不合法

{

printf("error!不合法的句子");

break;

}

p6=youxian[z][n];

if(p6=='>')

{

loop: Q=fenxizhan[j];

if(fenxizhan[j-1]=='+'||fenxizhan[j-1]=='*'||fenxizhan[j-1]=='^'||fenxizhan[j-1]=='i'||fenxizhan[j-1]=='('||fenxizhan[j-1]==')'||fenxizhan[j-1]=='#') j=j-1;

else

j=j-2;

z1=panduanyou(fenxizhan[j]);

n1=panduanyou(Q);

p1=youxian[z1][n1];

if(p1=='<') //fenxizhan[j+1]…fenxizhan[k]归约为N

{

k=j+1;

shengyuchuan();

flag++;

printf("(%d) %s %c %c %s 归约

\n",flag,fenxizhan,p6,a,lex);

i--;

fenxizhan[k]='N';

int hou,hou1;

hou=strlen(fenxizhan);

for(hou1=k+1;hou1<hou;hou1++)

fenxizhan[hou1]='\0';//多个字符归约，把栈顶后面的舍弃

zengjia();//归约剩余串没变化

}

else

goto loop;

}

else

{

if(p6=='<') //移进 有一个问题就是如果上一步是不归约，剩余的字符串减少一个

{

shengyuchuan();

lexbuf[f]='\0';

flag=flag+1;

printf("(%d) %s %c %c %s 移进\n",flag,fenxizhan,p6,a,lex);

//printf("1 ");

//printf(" %s ",fenxizhan);

//printf(" %c ",p);

// printf(" %c ",a);

//printf(" %s",lex);

//printf(" 移进\n");

// printf("%s",lex);

//printf("(i)");

k=k+1;

fenxizhan[k]=a;

}

else

{

if(p6=='=')

{

z4=panduanyou(fenxizhan[j]);

n4=panduanyou('#');

p4=youxian[z4][n4];

if(p4=='=')

{

shengyuchuan();

flag++;

printf("(%d) %s %c %c %s \n",flag,fenxizhan,p6,a,lex);

printf("合法的句子");

break;

}

else

{

k=k+1;

fenxizhan[k]=a;

}

}

else

{

printf("出错"); 接受

break;

}

}

}

}

}

int panduanyou(char x) {int m;

if(x=='+')

m=0;

if(x=='*')

m=1;

if(x=='^')

m=2;

if(x=='i')

m=3;

if(x=='(')

m=4;

if(x==')')

m=5;

if(x=='#')

m=6;

return m;

}

void shengyuchuan()

{

int i4,i5;

i4=strlen(lex);

for(i5=0;i5<i4;i5++) lex[i5]=lex[i5+1];

lex[i4-1]='\0';

}

void zengjia()

{

int h1,h2;

h1=strlen(lex);

for(h2=0;h2<h1;h2++)

lex[h1-h2]=lex[h1-h2-1];

lex[0]='$';//存入一字符个特殊 }

本文来源：https://www.bwwdw.com/article/bxk1.html