ll1.cpp

LL(1)文法分析程序,输入一个写入了一个LL1文法的文件名,运行程序,根据提示执行

#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<malloc.h>
#define stack_size   100
#define stack_groupsize  10
char vnfh;
 static int count=1;
struct yf
	{char vnf;
	char s[5][10];
	};
struct yf yshuzu[10];//输入，存储

struct f  //存放FIRST(),FOLLOW()
{char vn;
 char ft[20];
 char fl[20];
};
struct f fst[10];//存放FIRST(P),follow(P)假定最多有10个(非)终结符号
int biao;
struct l1
{char vn;
 char s[10][20];
};
struct l1 ll1[10];

 struct strack
 {
	char *base;
	char *top;
	int stacksize;
 };
 typedef strack sqstack;
 sqstack q;
int creat_stack(sqstack  &S)
{S.base=(char *)malloc(stack_size*sizeof(char));
 if(!S.base)  cout<<"error to creat stack"<<endl;
 S.top=S.base;
 S.stacksize=stack_size;
 return 1;
}

int gettop(sqstack S,char &e)
{if(S.top==S.base) return 0;
 e=*(S.top-1);
 return 1;
}

int push(sqstack &S,char e)   //入栈
{if(S.top-S.base>=S.stacksize)
	{S.base=(char *)realloc(S.base,(S.stacksize+stack_groupsize)*sizeof(char));
	 if(!S.base)  cout<<"error to push stack"<<endl;
	 S.top=S.base+S.stacksize;
 	 S.stacksize+=stack_groupsize;
	}
 *S.top++=e;
 return 1;
}

int pop(sqstack &S,char &e)  //出栈
{if(S.top==S.base) return -1;
 e=*--S.top;
 return 1;
}

int is_biglet(char c)
{
	if(c>='A'&&c<='Z') return 1;
	return 0;
}

int  yfinput()
{int i,j,x;
 char a,b,c;
 FILE *file1;
 char filename[20];
	cout<<"输入一个txt文件的文件名"<<endl;
	cout<<"要求此文件内容是一个文法，且按如下方式写在此文件内。\n";
	cout<<"且不能有多余的字符,ε用$代替输入"<<endl;
	cout<<"E->TG"<<endl;
	cout<<"G->+TG|$"<<endl;
	cout<<"T->FH"<<endl;
	cout<<"H->*FH|$"<<endl;
	cout<<"F->(E)|i"<<endl;
	cout<<"此文法只是一个输入范例，可输入其他文法"<<endl<<endl;
    cin>>filename;
	if((file1=fopen(filename,"r"))==NULL)
	  cout<<"Can't Open This File"<<'\n'<<endl;
	c='$';

 for(x=0;x<10;x++)
 {if(c!=EOF)
  {a=fgetc(file1);
     b=fgetc(file1);
   if(is_biglet(a)) yshuzu[x].vnf=a;
   else {cout<<"这不是一个LL1文法"<<endl;return 0;}
   a=b;
   b=fgetc(file1);
    
   for(i=0;a!='\n';i++)
    { a=fgetc(file1);
      if(a==yshuzu[x].vnf) {cout<<"存在左递归，不是一个LL1文法"<<endl;return 0;}
      else
	  {
        for(j=0;a!='|';j++)
		{yshuzu[x].s[i][j]=a;
         a=fgetc(file1);
         if(a==EOF||a=='\n') break;
		} 
        if(a==EOF) break;
	  }
    }     
   c=a;
  }
 else yshuzu[x].vnf='\0';
 }
 fclose(file1);
 return 1;
}

int search(char a[],char c)
{int i;
 for(i=0;a[i]!='\0';i++)
    if(c==a[i]) 
	{if(c=='$') return 2;
       else return 1;
	 }
    else;
  return 0;
}

void concat(char *a,char x)
{int i,y,flag=0;
 y=strlen(a);
 a[strlen(a)+1]='\0';
 for(i=0;a[i]!='\0';i++)
  if(a[i]==x) flag=1;
  else ;
 if(flag==0) a[strlen(a)]=x;
  else flag=0;
 if(y!=strlen(a)) biao=1;
}

void concat(char *a,char x,int p)
{int i,y,flag=0;
 y=strlen(a);
  if(p==0)
   {a[strlen(a)+1]='\0';
   for(i=0;a[i]!='\0';i++)
   if(a[i]==x) flag=1;
   else ;
   if(flag==0&&x!='$') a[strlen(a)]=x;
   else flag=0;


   }
  else
  {
   a[strlen(a)+1]='\0';
   for(i=0;a[i]!='\0';i++)
   if(a[i]==x) flag=1;
   else ;
   if(flag==0) a[strlen(a)]=x;
   else flag=0;
 }
 if(y!=strlen(a)) biao=1;
}

void concat(char *a,char *b)
{int i,j,x,flag=0;
 x=strlen(a);
 for(j=0;b[j]!='\0';j++)
 {a[strlen(a)+1]='\0';
  for(i=0;a[i]!='\0';i++)
   if(a[i]==b[j]) flag=1;
   else ;
  if(flag==0) a[strlen(a)]=b[j];
  else flag=0;
 }
  if(x!=strlen(a)) biao=1;
}    

void concat(char *a,char *b,int p)
{int i,j,x,flag=0;
 x=strlen(a);
 if(p==0) 
 {
 for(j=0;b[j]!='\0';j++)
 {a[strlen(a)+1]='\0';
  for(i=0;a[i]!='\0';i++)
   if(a[i]==b[j]) flag=1;
   else ;
  if(flag==0&&b[j]!='$') a[strlen(a)]=b[j];
  else flag=0;
 }
 }
 else
 { for(j=0;b[j]!='\0';j++)
  {a[strlen(a)+1]='\0';
   for(i=0;a[i]!='\0';i++)
    if(a[i]==b[j]) flag=1;
    else ;
   if(flag==0) a[strlen(a)]=b[j];
   else flag=0;
  }
 }
  if(x!=strlen(a)) biao=1;
} 

void first(char c,char (&a)[20])
{int i,j,flag,x,z;
 for(i=0;yshuzu[i].vnf!='\0';i++)
 {
  if(yshuzu[i].vnf==c)
	{fst[i].vn=yshuzu[i].vnf;
	 for(j=0;yshuzu[i].s[j][0]!='\0';j++)
	   if(is_biglet(yshuzu[i].s[j][0])) 
		{
		   for(flag=0;yshuzu[i].s[j][0]!=yshuzu[flag].vnf;flag++);
		   first(yshuzu[i].s[j][0],fst[flag].ft);
		   concat(a,fst[flag].ft);
		   if(search(fst[flag].ft,'$')==2)
		   {for(z=0;yshuzu[z].vnf!=yshuzu[i].s[j][1];z++);
		     for(x=1;x<strlen(yshuzu[i].s[j]);x++)
		      if(is_biglet(yshuzu[i].s[j][x]))
			{  for(z=0;yshuzu[z].vnf!=yshuzu[i].s[j][x];z++);
			   first(yshuzu[z].vnf,fst[z].ft);
			   if(is_biglet(yshuzu[i].s[j][x])&&search(fst[z].ft,'$')==2);

					
				 
			    else if(is_biglet(yshuzu[i].s[j][x])&&search(fst[z].ft,'$')!=2) 
					{
				    	 concat(a,fst[z].ft);break;
					}
			  
			}
		       else break;
			 if(x>(strlen(yshuzu[i].s[j])-1))  concat(a,'$');
		   }
		}
	   else concat(a,yshuzu[i].s[j][0]);
	}
 }
}



int nothing(char a[],int k)
{

  if(is_biglet(a[k]))
  {int flag=0;
    if(is_biglet(a[k+1]))
	{for(int z=0;yshuzu[z].vnf!=a[k+1];z++);
	 for(int h=0;yshuzu[z].s[h][0]!='\0'&&h<5;h++)
	 {if(yshuzu[z].s[h][0]=='$') flag=1;}
	 if(flag==1) return nothing(a,k+1);
	  else return 0;
	 }
    else if(a[k+1]=='\0') return 1;
          else return 0;
  }
 else return 0;

}



void follow(char c,char (&a)[20])
{int i,j,k,z,g;

 concat(fst[0].fl,'#');
 for(i=0;yshuzu[i].vnf!='\0';i++)
  
	{for(j=0;yshuzu[i].s[j][0]!='\0'&&j<5;j++)
		{for(k=0;yshuzu[i].s[j][k]!='\0';k++)
			{if(yshuzu[i].s[j][k]==c) 
				{if(is_biglet(yshuzu[i].s[j][k+1])) 
					{for(z=0;yshuzu[i].s[j][k+1]!=fst[z].vn;z++);
					 for(g=0;fst[g].vn!=yshuzu[i].s[j][k];g++);
						concat(fst[g].fl,fst[z].ft,0);
					 for( z=0;fst[z].vn!=yshuzu[i].vnf;z++);
					 
					 if(nothing(yshuzu[i].s[j],k)) concat(fst[g].fl,fst[z].fl,0);
					}
				else if(yshuzu[i].s[j][k+1]!='\0') 
					{for(g=0;fst[g].vn!=yshuzu[i].s[j][k];g++);
					 concat(fst[g].fl,yshuzu[i].s[j][k+1],0);
					}
					else{for(z=0;fst[z].vn!=yshuzu[i].vnf;z++);
						  for(g=0;fst[g].vn!=yshuzu[i].s[j][k];g++);
						  concat(fst[g].fl,fst[z].fl,0);
						}
				}
			}
		}
	}
							
}


int husu(char x,char B)
{int i,j,g,flag=0;
 for(i=0;yshuzu[i].vnf!=x;i++);
 for(g=0;yshuzu[i].s[g][0]!=B&&g<10;g++);
 if(yshuzu[i].s[g][0]=='\0'||g>=10)
   for(j=0;yshuzu[i].s[j][0]!='\0';j++)
         if(is_biglet(yshuzu[i].s[j][0]))  
			{flag=husu(yshuzu[i].s[j][0],B);
			 if(flag==1) return 1;
			}
		 else if(yshuzu[i].s[j][0]==B) return 1;
		      else;
		
  else return 1;
}
int con(char a[],char x,char b)
{int i,g,flag=0;
 for(i=0;yshuzu[i].vnf!=x;i++);
 for(g=0;yshuzu[i].s[g][0]!='\0';g++)
    if(is_biglet(yshuzu[i].s[g][0])&&husu(yshuzu[i].s[g][0],b)==1) 
	{ concat(a,yshuzu[i].s[g]);
	 return 1;
	}
	else if(yshuzu[i].s[g][0]==b)
			{a[strlen(a)+1]='\0';
			 a[strlen(a)]=a[strlen(a)-1];
				concat(a,yshuzu[i].s[g]); return 1;}
     else ;
 return 0;
   
}
 

void bidll1()
{int i,j,k;char a[10]={'\0'};
   for(i=0;yshuzu[i].vnf!='\0';i++)
	{for(j=0;yshuzu[i].s[j][0]!='\0'&&j<5;j++)
		{for(k=0;yshuzu[i].s[j][k]!='\0';k++)
		 if(!is_biglet(yshuzu[i].s[j][k])) concat(a,yshuzu[i].s[j][k],0);
		}
	}
   concat(a,'#');
 for(i=0;i<10;i++) 
   if(fst[i].vn!='\0')
    {ll1[i].vn=fst[i].vn;
     for(j=0;a[j]!='\0';j++)
      ll1[i].s[j][0]=a[j];
    }
   else ll1[i].vn='\0';

 for(i=0;ll1[i].vn!='\0';i++)
    {for(j=0;ll1[i].s[j][0]!='\0';j++)
      {if(search(fst[i].ft,ll1[i].s[j][0])==1) con(ll1[i].s[j],ll1[i].vn,ll1[i].s[j][0]);
       if(search(fst[i].ft,'$')==2 && search(fst[i].fl,ll1[i].s[j][0])==1) concat(ll1[i].s[j],'$');
      }
    } 
}
 void print()
 {int j,i;
	 cout<<endl<<endl<<endl;
	 cout<<"\t\t下面输出的是此文法的LL1分析表"<<endl<<endl;
	 cout<<'\t';
 for(i=0;ll1[0].s[i][0]!='\0';i++)
    cout<<ll1[0].s[i][0]<<'\t';
    cout<<endl;
	cout<<"_______________________________________________________________"<<endl;
   
 for(i=0;ll1[i].vn!='\0';i++)
   {cout<<ll1[i].vn<<'\t';
    for(j=0;ll1[i].s[j][0]!='\0';j++)
	if(ll1[i].s[j][1]!='\0')
    cout<<ll1[i].vn<<"->"<<ll1[i].s[j]+1<<'\t';
	else cout<<ll1[i].s[j]+1<<'\t';
	cout<<endl;
	cout<<"_______________________________________________________________"<<endl;
   }
 }

void printfit(sqstack q,char a[],char b[])
{
 int i;
 if(b[0]=='\0')
 {
  cout<<count<<'\t';
  for(i=0;q.base+i!=q.top;i++)
  cout<<*(q.base+i);
  cout<<"\t\t";
  cout<<a<<"\t\t\t"<<b<<endl;
  cout<<"_______________________________________________________________"<<endl;
 }
 else 
 {cout<<count<<'\t';
   for(i=0;q.base+i!=q.top;i++)
   cout<<*(q.base+i);
   cout<<"\t\t";
   cout<<a<<"\t\t\t"<<vnfh<<"->"<<b<<endl;
   cout<<"_______________________________________________________________"<<endl;
 }

count++;
}

int fit(char a[])
{cout<<endl<<endl<<"————————————下面输出预测分析过程—————————————"<<endl;
 cout<<"步骤\t"<<"符号栈\t\t"<<"输入串\t\t\t"<<"产生式"<<endl;
  cout<<"_______________________________________________________________"<<endl;
 cout<<"0\t#"<<ll1[0].vn<<"\t\t"<<a<<endl;
  cout<<"_______________________________________________________________"<<endl;
	int i,j,z,g;
 char e,*p=a;
 char kong[10]={'\0'};


 if(!creat_stack(q)) 
   cout<<"建站栈不成功"<<endl;
    
   
 push(q,'#');
 push(q,yshuzu[0].vnf);
 for(i=0;a[i]!='\0';i++)
   {p=a+i;
	 gettop(q,e);
	 if(e==a[i]){pop(q,e);printfit(q,p,kong);}
	 else
	 {for(j=0;q.top!=q.base+1;j++)
		{gettop(q,e);
      for(z=0;ll1[z].vn!=e;z++);
		 
      for(g=0;ll1[z].s[g][0]!=a[i]&&g<10;g++);
      if(g<10&&ll1[z].s[g][1]!='\0') 
			{pop(q,e);vnfh=e;
             for(int k=1;ll1[z].s[g][k]!='\0';k++);
			 for(int d=k-1;d>0;d--)
             push(q,ll1[z].s[g][d]);
			 gettop(q,e);
			 if(e=='$')  pop(q,e);
             printfit(q,p,ll1[z].s[g]+1);
			 
			 gettop(q,e);
             if(e==a[i]) 
               {p++;
                pop(q,e);
				vnfh=e;
				printfit(q,p,kong);
                break;
               }
             else if(e=='$')
					{pop(q,e);
			         vnfh=e;
			         printfit(q,p,ll1[z].s[g]+1);
				     break;
					}
                  else if(!is_biglet(e)) cout<<"error";
                       else ;
			}
	 }
	}
   }
  return 1;
}


void main()
{int i,j;
 char a[20];
 if(yfinput()==1)
	{ for(i=0;yshuzu[i].vnf!='\0';i++)
		 if(fst[i].vn=='\0') first(yshuzu[i].vnf,fst[i].ft);

		for(;biao==1;)
		{biao=0;
		 for(i=0;yshuzu[i].vnf!='\0';i++)
		 follow(yshuzu[i].vnf,fst[i].fl);
		}

	   cout<<'P'<<'\t'<<"FIRST(P)"<<"\t\tFOLLOW(P)"<<endl;
	  for(j=0;fst[j].vn!='\0';j++)
	  cout<<fst[j].vn<<'\t'<<fst[j].ft<<"\t\t\t"<<fst[j].fl<<endl;
 		bidll1();
	  print();
	  cout<<endl<<endl<<"____________输入一个句子，以#结尾，检查是否匹配__________"<<endl<<endl<<endl;
	  gets(a);
	  cout<<endl<<endl;
	  fit(a);
	 }
  else;
 }