关于使用词法分析，语法分析将布尔表达式转换为逆波兰式的下了个程序看不太懂(页 1) - C++论坛 - C++教室

陈子风 发表于 2008-6-23 11:46

关于使用词法分析，语法分析将布尔表达式转换为逆波兰式的下了个程序看不太懂

#include<ctype.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<iostream.h>
struct danci
  {
   int id; //单词种别
   char name[10]; //单词属性值
  };
int fout[20];
int index=1;
int G_table[9][6];
int k[20];
int n=0;
danci word[20];
int boo(int);
int compare(int);
int not(int);
int forid(int);
typedef struct node{
int data;
   node* next;
}* link;
link insert(link stack,int n)//向前插入链表
{
link newnode;
newnode=new node;
if(!newnode)
{
cout<<"error!"<<endl;
exit(0);
}
newnode->data=n;
newnode->next=stack;
stack=newnode;
return stack;
}
link del(link stack,int &value)//删除链表元素
{
link top;
if(stack)
{
top=stack;
stack=stack->next;
value=top->data;
delete top;
return stack;
}
value=-1;
return NULL;
}
void error()
{
cout<<"词法错误,标志符不能以数字开头"<<endl;
exit(0);
}
void error1()
{
cout<<"语法错误,输入正确句子"<<endl;
exit(0);
}
int not(int i)
{
int ii;
i=forid(i);
while(word[i].id==3)
{
ii=i;
i++;
i=forid(i);
fout[index]=ii;
index++;
}
return i;
}
void init()//初始化文法矩阵
{
for(int i=0;i<9;i++)
for(int j=0;j<6;j++)
G_table[i][j]=-1;
G_table[0][0]=0;G_table[0][1]=1; //初始化文法表
G_table[1][0]=1;G_table[1][1]=1;G_table[1][2]=5;G_table[1][3]=2;
G_table[2][0]=1;G_table[2][1]=2;
G_table[3][0]=1;G_table[3][1]=1;G_table[3][2]=3;
G_table[4][0]=2;G_table[4][1]=3;
G_table[5][0]=3;G_table[5][1]=6;G_table[5][2]=3;
G_table[6][0]=3;G_table[6][1]=9;G_table[6][2]=1;G_table[6][3]=10;
G_table[7][0]=3;G_table[7][1]=7;
G_table[8][0]=3;G_table[8][1]=9;G_table[8][2]=7;G_table[8][3]=8;
G_table[8][4]=7;G_table[8][5]=10;
}
void print()//打印文法
{
char a0[]="E";char a1[]="S";
char a2[]="B";char a3[]="C";
char a4[]="and";char a5[]="or";
char a6[]="not";char a7[]="id";
char a8[]="relop";char a9[]="(";
char a10[]=")";
cout<<"本实验的文法为："<<endl;
cout<<a0<<"->"<<a1<<endl;
cout<<a1<<"->"<<a1<<' '<<a5<<a2<<endl;
cout<<a1<<"->"<<a2<<endl;
cout<<a2<<"->"<<a2<<' '<<a4<<' '<<a3<<endl;
cout<<a2<<"->"<<a3<<endl;
cout<<a3<<"->"<<a6<<' '<<a3<<endl;
cout<<a3<<"->"<<a9<<a1<<a10<<endl;
cout<<a3<<"->"<<a7<<endl;
cout<<a3<<"->"<<a9<<a7<<' '<<a8<<' '<<a7<<a10<<endl;
}
int  lex(char * buf)//词法分析
{
int i=0,j=0;
int n=0;
char Temp_name[10];
while(buf[i]!='\0')
{
if(buf[i]==' '||buf[i]=='\n')
i++;
else if(isalpha(buf[i])||buf[i]=='_')//标志符判断
{
Temp_name[j]=buf[i];
i++;
while(isalnum(buf[i]))
{
j++;
Temp_name[j]=buf[i];
i++;
}
   // if
memcpy(word[n].name,Temp_name,j+1);
word[n].name[j+1]='\0';
if(strcmp(word[n].name,"and")==0)
word[n].id=1;
else if(strcmp(word[n].name,"or")==0)
word[n].id=2;
else if(strcmp(word[n].name,"not")==0)
word[n].id=3;
else
word[n].id=0;
n++;
j=0;
}
else if(isdigit(buf[i]))//数字判断
{
while(isdigit(buf[i]))
{
Temp_name[j]=buf[i];
i++;
j++;
}
if(isalpha(buf[i]))
               error();
memcpy(word[n].name,Temp_name,j+1);
word[n].name[j]='\0';
n++;
j=0;
}
else//运算符号判断
{
switch(buf[i])
{
case '>':if(buf[i+1]=='=')
   {
   i++;
      word[n].id=8;
   strcpy(word[n].name,">=");
   }
   else
   {
   word[n].id=4;
   strcpy(word[n].name,">");
   }
   n++;break;
case '<':if(buf[i+1]=='=')
   {
   i++;
      word[n].id=9;
   strcpy(word[n].name,"<=");
   }
   else
   {
   word[n].id=5;
   strcpy(word[n].name,"<");
   }
   n++;break;
case '=': word[n].id=6;strcpy(word[n].name,"=");n++;break;
case '!': if(buf[i+1]=='=')
   {
   i++;
      word[n].id=7;strcpy(word[n].name,"!=");
   n++;
   }
   break;
case '(': word[n].id=10;strcpy(word[n].name,"(");n++;break;
case ')': word[n].id=11;strcpy(word[n].name,")");n++;break;
}
i++;
}
}
strcpy(word[n].name,"#");
word[n].id=999;
return n;//单词符号个数
}

void gram(int * kind)
{
int n=0;
link state;
link lex;
link operate;
link ID;
state=new node[30];lex=new node[15];
if(!state||!lex)
{
cout<<"over stack! "<<endl;
exit(0);
}
int trace=0;
int G[9][5];
int Stable[16][11]; //SLR分析表
int i,j;
for(i=0;i<9;i++)
for(j=0;j<5;j++)
G[i][j]=-1;
for(i=0;i<18;i++)
for(j=0;j<11;j++)
Stable[i][j]=0; //初始化SLR表，其中表的初值为0，表示出错！
//设置SLR表 1-17表示移进，n进状态栈;21-29表示按N-20个产生式规约；0表示出错
Stable[0][2]=4;Stable[0][3]=5;Stable[0][6]=6;
Stable[0][8]=1;Stable[0][9]=2;Stable[0][10]=3;
Stable[1][0]=7;Stable[1][7]=111;
Stable[2][0]=23;Stable[2][1]=8;Stable[2][4]=23;Stable[2][7]=23;
Stable[3][0]=25;Stable[3][1]=25;Stable[3][4]=25;
Stable[3][7]=25;
Stable[4][2]=4;Stable[4][3]=5;Stable[4][6]=6;Stable[4][10]=9;
Stable[5][2]=4;Stable[5][3]=5;Stable[5][6]=11;
Stable[5][8]=10;Stable[5][9]=2;Stable[5][10]=3;
Stable[6][0]=28;Stable[6][1]=28;Stable[6][4]=28;Stable[6][7]=28;
Stable[7][2]=4;Stable[7][3]=5;Stable[7][6]=6;
Stable[7][9]=12;Stable[7][10]=3;
Stable[8][2]=4;Stable[8][3]=5; Stable[8][6]=6;Stable[8][10]=13;
Stable[9][0]=26;Stable[9][7]=26;Stable[9][4]=26;Stable[9][1]=26;
Stable[10][0]=7;Stable[10][4]=14;
Stable[11][0]=28;Stable[11][1]=28;
Stable[11][4]=28;Stable[11][5]=15;Stable[11][7]=28;
Stable[12][0]=22;Stable[12][1]=8;Stable[12][4]=22;Stable[12][7]=22;
Stable[13][1]=4;Stable[13][2]=4;Stable[13][3]=4;
Stable[13][0]=24;Stable[13][1]=24;Stable[13][4]=24;Stable[13][7]=24;
Stable[14][0]=27;Stable[14][1]=27;Stable[14][4]=27;Stable[14][7]=27;
Stable[15][6]=16;Stable[16][6]=17;
Stable[17][0]=29;Stable[17][1]=29;Stable[17][4]=29;Stable[17][7]=29;
kind[n]=7; //输入串最后字符为#
n++;
state=insert(state,0);
lex=insert(lex,7);
int a;
int staTop; //存放状态栈的栈顶元素
int operater;int ch1=0;int ch2;
for(a=0;a<n;a++) //进行SLR分析
{
staTop=state->data;
   if(Stable[staTop][kind[a]]==0)
{

break;

}
   else if(Stable[staTop][kind[a]]<20)
{ //规约
int sta1;
int letter1;
if(state!=NULL)
state=del(state,sta1);
else
{
         error1();
}
int num=0; //出栈次数
int b;
for(b=1;b<G_table[Stable[staTop][kind[a]]][4];b++)
{ //规约式右部出栈
lex=del(lex,letter1);
num++;
}
lex=insert(lex,G_table[Stable[staTop][kind[a]]][0]);//规约式左部进栈
for(b=1;b<num;b++) //状态栈中再出栈num-1个状态
state=del(state,sta1);
int staTop1;
staTop1=state->data;
state=insert(state,Stable[staTop1][G_table[Stable[staTop][kind[a]]][0]]-50);
a--;
if(num>1)
{
if(ch1==0)//总结符
{
ID=del(ID,ch1);
ch1=trace;trace--;
}
else
ch1=-1;
operate=del(operate,operater);
ID=del(ID,ch2);
ch2=trace;trace--;
ch1--;
}
}
else if(Stable[staTop][kind[a]]<50)
{//移进一个符号
state=insert(state,Stable[staTop][kind[a]]-20);
lex=insert(lex,kind[a]);
if(kind[a]==0)
{
trace++;
ID=insert(ID,kind[a]);
}
else
operate=insert(operate,kind[a]);
}
else if(Stable[staTop][kind[a]]==99)
{
cout<<endl;
cout<<"ACCEPT!"<<endl;
break;
}

}
}
void forboland(int length)
{

int i=0;
while((i<length)&&(word[i].id!=99))
{
i=boo(i);
if(word[i].id==99)
{
      error1();
}
}

}
int boo (int i)
{
int ii;
i=compare(i);
while (word[i].id==1||word[i].id==2)
{
ii=i;
i++;
i=compare(i);
fout[index]=ii;//
index++;
}
return i;
}

int forid(int i)
{
if (word[i].id==0)
{
fout[index]=i;
index++;
i++;
}
else
{
if(word[i].id==10)
{
i++;
i=boo(i);
if (word[i].id==11)
i++;
else
word[i].id=99;
}
else if(word[i].id==3)
{;}
else
{
         error1();
word[i].id=99;
}
}
return i;
}
void boland()
{
for(int i=1;i<index;i++)
{
if(word[fout[i]].id==0)
cout<<word[fout[i]].name<<" ";
else
{
switch (word[fout[i]].id)
{
case 1: cout<<"and ";break;
case 2: cout<<"or ";break;
case 3: cout<<"not ";break;
case 4: cout<<"> ";break;
case 5: cout<<"< ";break;
case 6: cout<<"= ";break;
case 7: cout<<"!= ";break;
case 8: cout<<">= ";break;
case 9: cout<<"<= ";break;
}
}
}
index=0;
}
int compare(int i)
{
int ii;
i=not(i);
while(word[i].id==4||word[i].id==5||word[i].id==6
||word[i].id==7||word[i].id==8||word[i].id==9)
{
ii=i;
i++;
i=not(i);
fout[index]=ii;
index++;
}
return i;
}
void main()
{
char buffer[30];
int i=0;
int length;
char *inword;
init();
print();
cout<<"输入布尔表达式，以#结束 :"<<endl;
cin>>buffer[i];
while(buffer[i]!='#')
{
i++;
cin.get(buffer[i]);
}
buffer[i]='\0';
length=i+1;
inword=new char[length];
memcpy(inword,buffer,length);
length=lex(inword);
cout<<"词法分析结果如下："<<endl;
cout<<'('<<"属性"<<' '<<"值"<<')';
for( i=0;i<length;i++)
{ cout<<'('<<word[i].id<<' '<<word[i].name<<')'; cout<<' ';}
cout<<endl;

n=length;
forboland(length);
gram(k);
cout<<"逆波兰式为：\n"<<endl;
//逆波兰式翻译
boland();
cout<<endl;
}

zjl138 发表于 2008-6-23 11:54

你这样贴出来神仙也看不懂的,自已写一下不就什么都懂了.

mcgradyzj 发表于 2008-6-25 21:52

看来只有我顶你啊！王鹏！！！！！[tk05]

晨曦的朝阳 发表于 2008-6-28 21:31

晕死，我扫了十秒，从上到下，呵呵！

页: [1]

关于 使用词法分析，语法分析将布尔表达式转换为逆波兰式 的下了个程序看不太懂

关于使用词法分析，语法分析将布尔表达式转换为逆波兰式的下了个程序看不太懂