lastvt.txt

编译原理课程设计

#include<iostream.h>
#include<string.h>
#include<stdio.h>   //以上为三个头文件
typedef struct       //定义数据类型array
{char R;           //变量R为char型
char r;             //变量 r为char型
int flag;            //变量flag为int型
}array;
typedef struct       //定义数据类型charLode
{char E;           //变量E为char型
char e;            //变量e为char型
}charLode;
typedef struct       //定义数据类型charstack栈
{ charLode *base;   //字符指针base为栈底
    int top;        //变量tor为int型，为栈顶
}charstack;
char str[80][80],arr[80][80],brr[80][80];//定义三个字符数组
array F[20];       //定义一个数组array
int m,kk,p,ppp,FF=1;//定义四个int型变量，其中FF初值为1
char r[10];        //定义字符数组r[]
int crr[20][20],FLAG=0;//定义二维数组crr[][],并定义FLAG初值为1
char ccrr1[1][20],ccrr2[20][1];      //字符型二维数组crr1[][]和crr2[][]
void Initstack(charstack &s)        //定义一个空栈charstack
{s.base=new charLode[20];
    s.top=-1;}
void push(charstack &s,charLode w)    //入栈，插入元素w为栈顶元素
{s.top++;                          //栈顶地址+1
   s.base[s.top].E=w.E;
   s.base[s.top].e=w.e;}
void pop(charstack &s,charLode &w)   //出栈，删除栈顶元素w
{ w.E=s.base[s.top].E;
   w.e=s.base[s.top].e;
   s.top--;                //栈顶地址-1
}
int IsEmpty(charstack s)     //定栈是否为空
{if(s.top==-1) return 1; //若栈空，返回1
else return 0;        //若栈不为空，返回0
}
int IsLetter(char ch)//函数IsLetter是用来判断一个字符是否为非终结符
{ if(ch>='A'&&ch<='Z')
     return 1;    //若字符为非终结符，则返回1
 else return 0;    //否则返回0
}
int judge1(int n)        //judge1是判断文法是否是算符文法：若产生式中含有两个相继的非终结符则不是算符文法
{int j=3,flag=0;  //定义两个int型变量j,flag,并分别定义初值为3和0
for(int i=0;i<=n;i++)    //循环条件
   while(str[i][j]!='\0')  //字符不为空
   {char a=str[i][j];    //把str[i][j]的值赋给变量a
   char b=str[i][j+1];   //把str[i][j+1]的值赋给变量b
   if(IsLetter(a)&&IsLetter(b))  //若a,b都为非终结符
{flag=1;break;}
else j++;}
   if(flag==1)
   return 0;
   else
   return 1;}
void judge2(int n)    //judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法
{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;
}
int search1(char r[],int kk,char a)     //search1是查看存放终结符的数组r中是否含有重复的终结符
{for(int i=0;i<kk;i++)            //循环条件
   if(r[i]==a) break;
   if(i==kk) return 0;
   else  return 1;}
void createF(int n)    //createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;F数组是一个结构体
{int k=0,i=1;char g;   //定义两个int型变量，其中初值为k=0,i=1，一个型char变量g
char t[10];          //t数组用来存放非终结符
t[0]=str[0][0];       //把str[0][0]的值赋给变量t[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++;
   }}
void search(charLode w)      //search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1
{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++;}
     }}
   }}
int judge3(char s,char a)   //search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1
{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);   //归约成功
}
}