测试.cpp

算符文法分析器

//语法分析器实验
#include<iostream.h>
#include<string.h>
#include<stdio.h>
typedef struct
{
char R;
char r;
int flag;
}array;
typedef struct 
{
char E;
char e;
}charLode;
typedef struct
{
    charLode *base;
    int top;
}charstack;
char str[80][80],arr[80][80],brr[80][80];
array F[20];
int m,kk,p,ppp,FF=1;
char r[10];
int crr[20][20],FLAG=0;
char ccrr1[1][20],ccrr2[20][1];
void Initstack(charstack &s)//定义栈
{
s.base=new charLode[20];
    s.top=-1;
}
void push(charstack &s,charLode w)
{
   s.top++;
   s.base[s.top].E=w.E;
   s.base[s.top].e=w.e;
}
void pop(charstack &s,charLode &w)
{
   w.E=s.base[s.top].E;
   w.e=s.base[s.top].e;
   s.top--;
}
int IsEmpty(charstack s)
{
if(s.top==-1)
   return 1;
else return 0;
}
int IsLetter(char ch)
{
   if(ch>='A'&&ch<='Z')
     return 1;
   else return 0;
}
//judge1是判断是否是算符文法：若产生式中含有两个相继的非终结符则不是算符文法
int judge1(int n)
{
int j=3,flag=0;
for(int i=0;i<=n;i++)
   while(str[i][j]!='\0')
   {
   char a=str[i][j];
   char b=str[i][j+1];
   if(IsLetter(a)&&IsLetter(b))
   {flag=1;break;}
else j++;
   }
   if(flag==1)
   return 0;
   else
   return 1;
}
//judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法
void judge2(int n)
{
for(int i=0;i<=n;i++)
   if(str[i][3]=='~'||judge1(n)==0||FLAG==1)//'~'代表空字
   {cout<<"文法G不是算符优先文法!"<<endl;FF=0;break;}
   if(i>n)
   cout<<"文法G是算符优先文法!"<<endl;
}
//search1是查看存放终结符的数组r中是否含有重复的终结符
int search1(char r[],int kk,char a)
{
for(int i=0;i<kk;i++)
   if(r[i]==a)
    break;
   if(i==kk) return 0;
   else return 1;
}
//createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;F数组是一个结构体
void createF(int n)
{
int k=0,i=1;char g;
char t[10];//t数组用来存放非终结符
t[0]=str[0][0];
while(i<=n)
{
   if(t[k]!=str[i][0])
   {k++;t[k]=str[i][0];g=t[k];i++;}
   else i++;
}
kk=0;
    char c;
for(i=0;i<=n;i++)
{ int j=3;
   while(str[i][j]!='\0')
   {
    c=str[i][j];
    if(IsLetter(c)==0)
    {
     if(!search1(r,kk,c))
     r[kk]=c;kk++;//r数组用来存放终结符
    }
    j++;
   }
   }
m=0;
for(i=0;i<k;i++)
   for(int j=0;j<kk-1;j++)
   {
    F[m].R=t[i];
    F[m].r=r[j];
    F[m].flag=0;
    m++;
   }
}
//search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1
void search(charLode w)
{
for(int i=0;i<m;i++)
   if(F[i].R==w.E&&F[i].r==w.e)
   {F[i].flag=1;break;}
}
void FirstVT(int n)//求FirstVT
{
charstack sta;
charLode w;
int i=0;
Initstack(sta);
while(i<=n)
{
   int k=3;
   w.E=str[i][0];
   char a=str[i][k];
   char b=str[i][k+1];
   if(!IsLetter(a))//产生式的后选式的第一个字符就是终结符的情况
   {
    w.e=a;
    push(sta,w);
    search(w);
    i++;
   }
   else if(IsLetter(a)&&b!='\0'&&!IsLetter(b))//产生式的后选式的第一个字符是非终结符的情况
   {
    w.e=b;
    push(sta,w);
    search(w);
    i++;
   }
   else i++;
}
charLode ww;
while(!IsEmpty(sta))
{
   pop(sta,ww);
   for(i=0;i<=n;i++)
   {
    w.E=str[i][0];
    if(str[i][3]==ww.E&&str[i][4]=='\0')
    {
     w.e=ww.e;
     push(sta,w);
     search(w);
     break;
    }
   }
}
p=0;int k=1;i=1;
while(i<m)
{
   if(F[i-1].flag==1)
   {
    arr[p][0]=F[i-1].R;
    arr[p][k]=F[i-1].r;
   }
   while(F[i].flag==0&&i<m)
    i++;
   if(F[i].flag==1)
   {
    if(F[i].R==arr[p][0])
     k++;
      else {arr[p][k+1]='\0';p++;k=1;}
    i++;
   }
}   
}

void LastVT(int n)//求LastVT
{
charstack sta;
charLode w;
for(int i=0;i<m;i++)
   F[i].flag=0;
i=0;
Initstack(sta);
while(i<=n)
{
   int k=strlen(str[i]);
   w.E=str[i][0];
   char a=str[i][k-1];
   char b=str[i][k-2];
   if(!IsLetter(a))
   {
    w.e=a;
    push(sta,w);
    search(w);
    i++;
   }
   else if(IsLetter(a)&&!IsLetter(b))
   {
    w.e=b;
    push(sta,w);
    search(w);
    i++;
   }
   else i++;
}
charLode ee;
while(!IsEmpty(sta))
{
   pop(sta,ee);
   for(i=0;i<=n;i++)
   {
    w.E=str[i][0];
    if(str[i][3]==ee.E&&str[i][4]=='\0')
    {
     w.e=ee.e;
     push(sta,w);
     search(w);
    }
   }
}
int k=1;i=1;
ppp=0;
while(i<m)
{
   if(F[i-1].flag==1)
   {
    brr[ppp][0]=F[i-1].R;
    brr[ppp][k]=F[i-1].r;
   }
   while(F[i].flag==0&&i<m)
    i++;
   if(F[i].flag==1)
   {
    if(F[i].R==arr[ppp][0])
     k++;
      else {brr[ppp][k+1]='\0';ppp++;k=1;}
    i++;
   }
}   
}
void createYXB(int n)//构造优先表
{
int i,j;
    for(j=1;j<=kk;j++)
        ccrr1[0][j]=r[j-1];
for( i=1;i<=kk;i++)
   ccrr2[i][0]=r[i-1];
for(i=1;i<=kk;i++)
   for(j=1;j<=kk;j++)
    crr[i][j]=0;
   int I=0,J=3;
   while(I<=n)
   {
    if(str[I][J+1]=='\0')
    {I++;J=3;}
    else
    {
     while(str[I][J+1]!='\0')
     {
      char aa=str[I][J];
      char bb=str[I][J+1];
      if(!IsLetter(aa)&&!IsLetter(bb))//优先及等于的情况，用1值表示等于
      {  
       for(i=1;i<=kk;i++)
       { 
                            if(ccrr2[i][0]==aa)
            break; 
                        }
       for(j=1;j<=kk;j++)
       {
                            if(ccrr1[0][j]==bb)
            break;  
                        }
       if(crr[i][j]==0)
        crr[i][j]=1;
       else {FLAG=1;I=n+1;}
       J++;
      }
      if(!IsLetter(aa)&&IsLetter(bb)&&str[I][J+2]!='\0'&&!IsLetter(str[I][J+2]))//优先及等于的情况
      {  
       for(i=1;i<=kk;i++)
       { 
                            if(ccrr2[i][0]==aa)
          break;
                        }
       for(int j=1;j<=kk;j++)
       { 
                            if(ccrr1[0][j]==str[I][J+2])
             break;
                        }
       if(crr[i][j]==0)
        crr[i][j]=1;
       else {FLAG=1;I=n+1;}
      }
      if(!IsLetter(aa)&&IsLetter(bb))//优先及小于的情况，用2值表示小于
      {  
       for(i=1;i<=kk;i++)
       { 
                             if(aa==ccrr2[i][0])
            break;
                         }
        for(j=0;j<=p;j++)
        { 
                                if(bb==arr[j][0])
           break;
                            }
         for(int mm=1;arr[j][mm]!='\0';mm++)
         { 
          for(int pp=1;pp<=kk;pp++)
          {
           if(ccrr1[0][pp]==arr[j][mm])
                  break;
          }
          if(crr[i][pp]==0)
          crr[i][pp]=2;
          else {FLAG=1;I=n+1;}
         }
         J++;
      }
      if(IsLetter(aa)&&!IsLetter(bb))//优先及大于的情况，用3值表示大于
      { 
       for(i=1;i<=kk;i++)
       { 
        if(ccrr1[0][i]==bb)
         break;
       }
       for(j=0;j<=ppp;j++)
       {
        if(aa==brr[j][0])
         break;
       }
       for(int mm=1;brr[j][mm]!='\0';mm++)
       {  
        for(int pp=1;pp<=kk;pp++)
        {
         if(ccrr2[pp][0]==brr[j][mm])
               break;
        }
        if(crr[pp][i]==0)
        crr[pp][i]=3;
                            else {FLAG=1;I=n+1;}
       }
       J++;
      }
     }
    }
   }
}
//judge3是用来返回在归约过程中两个非终结符相比较的值
int judge3(char s,char a)
{
int i=1,j=1;
while(ccrr2[i][0]!=s)
   i++;
while(ccrr1[0][j]!=a)
   j++;
if(crr[i][j]==3) return 3;
else if(crr[i][j]==2) 
   return 2;
else if(crr[i][j]==1)
   return 1;
else return 0;
}
void print(char s[],char STR[][20],int q,int u,int ii,int k)//打印归约的过程
{
cout<<u<<"        ";
for(int i=0;i<=k;i++)
   cout<<s[i];
cout<<"         ";
for(i=q;i<=ii;i++)
   cout<<STR[0][i];
cout<<"        ";
}
void process(char STR[][20],int ii)//对输入的字符串进行归约的过程
{ 
cout<<"步骤"<<"    "<<"符号栈"<<"    "<<"输入串"<<"       "<<"动作"<<endl;
int k=0,q=0,u=0,b,i,j;
char s[40],a;
s[k]='#';
print(s,STR,q,u,ii,k);
cout<<"预备"<<endl;
k++;u++;
    s[k]=STR[0][q];
q++;
print(s,STR,q,u,ii,k);
cout<<"移进"<<endl;
while(q<=ii)
{
   a=STR[0][q];
   if(!IsLetter(s[k])) j=k;
   else j=k-1;
   b=judge3(s[j],a);
   if(b==3)//大于的情况进行归约
   {
    while(IsLetter(s[j-1]))
     j--;
    for(i=j;i<=k;i++)
     s[i]='\0';
    k=j;s[k]='N';u++;
    print(s,STR,q,u,ii,k);
    cout<<"归约"<<endl;
   }
   else if(b==2||b==1)//小于或等于的情况移进
   {
    k++;
    s[k]=a;
    u++;
    q++;
    print(s,STR,q,u,ii,k);
    if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')
        cout<<"接受"<<endl;
      else cout<<"移进"<<endl;
   }
   else 
   {cout<<"出错"<<endl;break;}
}
if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')
   cout<<"归约成功"<<endl;
else cout<<"归约失败"<<endl;
}
void main()
{
int n,i,j;
cout<<"请输入你要定义的文法G的产生式的个数n:";
    cin>>n;
for(i=0;i<n;i++)
{
   gets(str[i]);
   j=strlen(str[i]);
   str[i][j]='\0';
}
str[i][0]='Q';
str[i][1]='-';
str[i][2]='>';
str[i][3]='#';
str[i][4]=str[0][0];
str[i][5]='#';
    str[i][6]='\0';
cout<<"你定义的产生式如下:"<<endl;
    for(i=0;i<=n;i++)
   cout<<str[i]<<endl;
if(judge1(n)==0)//判断文法G是否为算符文法
   cout<<"文法G不是算符文法!"<<endl;
if(judge1(n)==1)
{
cout<<"文法G是算符文法!"<<endl;
     createF(n);
FirstVT(n);
LastVT(n);
createYXB(n);
}
judge2(n);//判断文法G是否为算符优先文法
   if(FLAG==0)
   {
    for(i=0;i<=p;i++)//打印FirstVT
    {
       cout<<"FirstVT("<<arr[i][0]<<")={";
       for(int l=1;arr[i][l+1]!='\0';l++)
    cout<<arr[i][l]<<",";
    cout<<arr[i][l]<<"}"<<endl;
    }
       cout<<"FirstVT(Q)={#}"<<endl; 
   for(i=0;i<=ppp;i++)//打印LastVT
   {
      cout<<"LastVT("<<arr[i][0]<<")={";
         for(int l=1;brr[i][l+1]!='\0';l++)
         cout<<brr[i][l]<<",";
      cout<<brr[i][l]<<"}"<<endl;
   }
       cout<<"LastVT(Q)={#}"<<endl;
   cout<<"优先表如下:"<<endl;
   for(i=1;i<kk;i++)//打印优先关系表
   {
    cout<<"   ";
    cout<<ccrr1[0][i];
   }
   cout<<endl;
   for(i=1;i<kk;i++)
   {
    cout<<ccrr2[i][0]<<" ";
    for(j=1;j<kk;j++)
    {
    if(crr[i][j]==0)
     cout<<" ";
    else if(crr[i][j]==1)
     cout<<"=";
    else if(crr[i][j]==2)
     cout<<"<";
    else if(crr[i][j]==3)
     cout<<">";
    cout<<"   ";
    }
    cout<<endl;
   }
   }
if(FF==1)
{
char STR[1][20];
cout<<"请输入要规约的字符串:"<<endl;
gets(STR[0]);
   int ii=strlen(STR[0]);
STR[0][ii]='#';
   cout<<"下面是规约的过程:"<<endl;
process(STR,ii);
}
}