计算机0303-20号-唐亮-预测分析表.c

用C语言编写的编译预测分析程序,有通用性 进行自顶向下编译

			  goto outwhile1;            
		   }
		   else
		   { j=1;
			while((first[j][1]!=newp[m][n])&&(j<=ntnum))
             j++;
			first_get(first[j][1]);
			 a=2;
			while(first[j][a]!='\0')
			{ if(!search(first[j][a],first[i][1],0))
				{for(k=LEN;k>2;k--)
			     first[i][k]=first[i][k-1];
			     first[i][2]=first[j][a];
				}
              a++;
			}
			k=1;
			while((!((newp[k][1]==newp[m][n])&&(newp[k][3]=='$')))&&(k<=newp_count))
			{ k++;}
			if(k<=newp_count) {n++;goto while1;}
		    else goto outwhile1;
		   }
		  }
outwhile1: ;
		}
	  }
exit1: ;
}
/******************************************/
void getfollow()
{ int i,j,m,n;
  for(i=1;i<=ntnum;i++)
  { follow[i][1]=NT[i][1];
    follow[i][2]='\0';
  }
  for(i=1;i<=ntnum;i++)
  { for(j=1;j<=link_count;j++)
      follow_link[j]='\0';
    link_count=1;
    follow_get(follow[i][1]);
	follow[i][0]=1;
  }
}
void follow_get(char x)
{ int i,j,k,m,n,a,b;
  i=1;
  while((follow[i][1]!=x)&&(i<=ntnum))
   i++;
  if(i>ntnum) goto exit2;
  for(j=1;j<=link_count;j++)
  if(follow_link[j]==follow[i][1]) goto exit2;
  follow_link[link_count]=follow[i][1];
  link_count++;
  if(i==1) 
  {if(!search('#',follow[i][1],1))
    {for(j=LEN;j>2;j--)
     follow[i][j]=follow[i][j-1];
     follow[i][2]='#';      /*#加入开始符号FOLLOW集*/
     }  
  }
  for(m=1;m<=newp_count;m++)
  { n=3;
    while((newp[m][n]!=follow[i][1])&&(newp[m][n]!='\0'))
		n++;
	if(newp[m][n]!='\0')
	{ 
		if(newp[m][n+1]=='\0')
		{  j=1;
		   while(follow[j][1]!=newp[m][1])
		   j++;
		   if(follow[j][0]==0)
		     follow_get(follow[j][1]);
		   a=2;
	       while(follow[j][a]!='\0')
		   { if(!search(follow[j][a],follow[i][1],1))
		     {for(k=LEN;k>2;k--)
			 follow[i][k]=follow[i][k-1];
			 follow[i][2]=follow[j][a];		/*产生式开始符follow=>结尾非终极符的follow*/
		     }
			 a++;
		   }
		}
		else if((newp[m][n+1]>'Z')||(newp[m][n+1]<'A'))
		{  if(!search(newp[m][n+1],follow[i][1],1))
		    {for(j=LEN;j>2;j--)
		     follow[i][j]=follow[i][j-1];
		     follow[i][2]=newp[m][n+1];
		     }
		}
		else
		{ 
while2:	  n++;
		  while(newp[m][n]!='\0')
		  { 
		   if((newp[m][n]>'Z')||(newp[m][n]<'A'))
		   { if(!search(newp[m][n],follow[i][1],1))
		      {for(j=LEN;j>2;j--)
		       follow[i][j]=follow[i][j-1];
		       follow[i][2]=newp[m][n];
		       }
			 goto outwhile2;            
		   }
		   else
		   { j=1;
			while((first[j][1]!=newp[m][n])&&(j<=ntnum))
             j++;
			 a=2;
			while(first[j][a]!='\0')
			{ if(!search(first[j][a],follow[i][1],1)) 
			   {for(k=LEN;k>2;k--)
			   follow[i][k]=follow[i][k-1];
			   follow[i][2]=first[j][a];
			   }
               a++;
			}
			k=1;
			while((!((newp[k][1]==newp[m][n])&&(newp[k][3]=='$')))&&(k<=newp_count))
			{ k++;}
			if((k<=newp_count)&&(newp[m][n+1]!='\0'))  /*后继符号能推出空且不是最后符号则继续循环*/
				goto while2;
			else if((k<=newp_count)&&(newp[m][n+1]=='\0'))/*后继符号能推出空并是最后符号则求开始符的FOLLOW*/
			{
			   j=1;
		       while(follow[j][1]!=newp[m][1])
		       j++;
			   if(follow[j][0]==0)
		        follow_get(follow[j][1]);
		       a=2;
	           while(follow[j][a]!='\0')
			   { if(!search(follow[j][a],follow[i][1],1)) 
			      {for(k=LEN;k>2;k--)
		    	   follow[i][k]=follow[i][k-1];
			       follow[i][2]=follow[j][a];		/*产生式开始符follow=>结尾非终极符的follow*/
			       }
				  a++;
			   }
			   goto outwhile2;
			} /*end else if*/
			else goto outwhile2; /*后继符号不能推出空则进入下一循环*/
		   }/*end else*/
		  }/*while*/
		}   /*else*/
	}/*end if*/
outwhile2: ;
  }/*end for*/
exit2: ;
}
/*****************************************/
void getselect()
{
 int i,j,k,n,a;
 for(i=1;i<=newp_count;i++)
   select[i][1]=i;
 for(i=1;i<=newp_count;i++)
 { 
   if(newp[i][3]=='$')
   { 
	 j=1;
	 while(follow[j][1]!=newp[i][1])
   	 j++;
	 k=2;
	 while(follow[j][k]!='\0')
	 { 
	   select[i][k]=follow[j][k];
	   k++;
	 }
	 select[i][k]='\0';
   }
   else if((newp[i][3]>'Z')||(newp[i][3]<'A'))
   {
	select[i][2]=newp[i][3];select[i][3]='\0';
   }
   else
   { select[i][2]='\0';
	 n=2;
while3:	n++;
	 while(newp[i][n]!='\0')
	 { 
	   if((newp[i][n]>'Z')||(newp[i][n]<'A'))
	   { 
		 if(!search1(newp[i][n],select[i][1]))
		 { 
		   for(j=LEN;j>2;j--)
		   select[i][j]=select[i][j-1];
		   select[i][2]=newp[i][n];
		 }
		 goto outwhile3;            
	   }
	   else
	   { j=1;
	   	 while((first[j][1]!=newp[i][n])&&(j<=ntnum))
         j++;
	     a=2;
		 while(first[j][a]!='\0')
		 { 
		   if(!search1(first[j][a],select[i][1]))
		   { 
			for(k=LEN;k>2;k--)
			select[i][k]=select[i][k-1];
			select[i][2]=first[j][a];
		   }
           a++;
		 }
		 k=1;
		 while((!((newp[k][1]==newp[i][n])&&(newp[k][3]=='$')))&&(k<=newp_count))
		 { k++;}
			if((k<=newp_count)&&(newp[i][n+1]!='\0'))  /*后继符号能推出空且不是最后符号则继续循环*/
				goto while3;
			else if((k<=newp_count)&&(newp[i][n+1]=='\0'))/*后继符号能推出空并是最后符号则求开始符的FOLLOW*/
			{
			   j=1;
		       while(follow[j][1]!=newp[i][1])
		       j++;
		       a=2;
	           while(follow[j][a]!='\0')
			   { if(!search1(follow[j][a],select[i][1])) 
			      {for(k=LEN;k>2;k--)
		    	   select[i][k]=select[i][k-1];
			       select[i][2]=follow[j][a];		/*产生式开始符follow=>SELECT*/
			       }
				  a++;
			   }
			   goto outwhile3;
			} /*end else if*/
			else goto outwhile3; /*后继符号不能推出空则进入下一产生式*/
	   }  
	 }
   }   
outwhile3: ;
 }
}
/****************************************/
int examin()
{ int i,j,k,m,n,flag=0;
  for(i=1;i<=ntnum;i++)
  { for(j=1;j<=LEN;j++)
     select_link[j]='\0';
    for(m=1;m<=newp_count;m++)
	  if(newp[m][1]==NT[i][1])
	  {
		 k=2;
		 while(select[m][k]!='\0')
		 { if(!search2(select[m][k],select_link))
		     {select_link[k-1]=select[m][k];k++;}
		    else 
			{printf("非终极符%c的产生式可选集交集不为空\n",NT[i][1]);
			 flag=1;
			 goto nextNT;
			}
		 }
	  }
nextNT: ;
  }
  if(flag==1)
  {printf("该文法不是LL(1)型文法，不能进行确定的自顶向下分析\n");return(0);}
  else return(1);
}
/*******************************************/
void Establish_table()
{   int i,j,m,n;
  for(i=1;i<=ntnum;i++)
  { for(j=1;j<=tnum;j++)
	 {table[i][j].ntermin=NT[i][1];
	  table[i][j].termin=T[j];
	  for(m=1;m<=newp_count;m++)
	  {
		  if(newp[m][1]==table[i][j].ntermin)
		  {n=2;
		    while((select[m][n]!='\0')&&(select[m][n]!=table[i][j].termin))
			  n++;
			if(select[m][n]!='\0')
			{n=1;
			 while(newp[m][n]!='\0')
			 {table[i][j].value[n]=newp[m][n];n++;}
			  table[i][j].value[n]='\0'; table[i][j].value[0]=1;goto other;
			}			
		  }
	  }
	  if(m>newp_count) {table[i][j].value[0]=0;table[i][j].value[1]='N';table[i][j].value[2]='U';table[i][j].value[3]='L';table[i][j].value[4]='L';}
other: ;
	 }
  }
}
/*******************************************/
void display_table()
{
  int i,j;
  printf("___________________________预测分析表____________________________________\n");
  for(j=1;j<=tnum;j++)
	printf("      %-6c",T[j]);
    printf("\n");
  for(i=1;i<=ntnum;i++)
  { 
	printf("%-6c",NT[i][1]);
    for(j=1;j<=tnum;j++)
	   printf("%-12s",&table[i][j].value[1]);
	printf("\n");
  }
  printf("_________________________________________________________________________\n");
}
/***************************************************/
void analyz()
{ int i,j,k,m,num=1,flag;
  char ch;
  char str[LEN]; char *p=&str[1];
  char *q;
  analyzer stack,*ps; 
  initstack(&stack);
  push(&stack,'#');
  push(&stack,NT[1][1]);
  printf("请输入测试字符串(以#结束):\n");
   for(i=0;;i++)
   { 
     scanf("%c",&ch);
	 if(ch=='#') break;
	  str[i]=ch;
   }
  str[i]='#';
  str[i+1]='\0';
  printf("步骤  分析栈    栈顶符，当前符   所用产生式   剩余输入串\n");
  ch=gettop(&stack);
  while(ch!='#')
  {   printf("%-4d  ",num);
      q=stack.base;
		  printf("%-10s",q);
	  printf("(%c,%c)   ",ch,*p);
	  flag=0;
	  if((ch<='Z')&&(ch>='A'))
	  {  for(i=1;i<=ntnum;i++)
	      for(j=1;j<=tnum;j++)
			  if((table[i][j].ntermin==ch)&&(table[i][j].termin==*p))
			  {flag=1;goto out;}
out:     if(flag==1)
		 { if(table[i][j].value[0]==0) {printf("     不接受\n");goto end;}
		   else
		   { 
			 pop(&stack);
		     k=3;
			 while(table[i][j].value[k]!='\0')
			 k++;
			 if(table[i][j].value[k-1]!='$')
			 {for(m=k-1;m>=3;m--)
			 push(&stack,table[i][j].value[m]);}
			 printf("  查表   %-13s",&table[i][j].value[1]);
		   }
		 }
		 else {printf("非法字符   不匹配\n");goto end;}
	  }
	  else if(ch==*p)
	  { printf("  匹配                ");
		pop(&stack);
	    p++;
	  }
	  else {printf("    不接受\n");goto end;}
      ch=gettop(&stack);
	 printf("%s\n",p);
	 num++;
  }
  if(ch==*p) printf("成功接收\n");
  else printf("不接受\n");
end: ;
}
/************************************************/

/*******************************************************/
void print()
{ int m,n;
  printf("等价文法为:\n");
  for(m=1;m<=newp_count;m++)
  { n=1;
    while(newp[m][n]!='\0')
	{printf("%c",newp[m][n]);
	  n++;
	}
      printf("\n");
   }

  for(m=1;m<=ntnum;m++)
  { printf("FIRST(%c)=%-8s",first[m][1],&first[m][2]);
	if(m%3==0) printf("\n");
  }
  printf("\n");
  for(m=1;m<=ntnum;m++)
  { printf("FOLLOW(%c)=%-8s",follow[m][1],&follow[m][2]);
    if(m%3==0) printf("\n");
  }
  printf("\n");
  for(m=1;m<=newp_count;m++)
  { n=2;
    printf("SELECT[%s]={",&newp[m][1]);
    while(select[m][n]!='\0')
	{printf("%c ",select[m][n]);
	  n++;
	}
      printf("}\n");
   } 
}
/*******************************************/
void Error(int a)
{ switch(a){
   case 1: printf("非终极符必须大写,input again!!\n");
           printf("the model like: A=aA|aB\n");
		   break;
   case 2: printf("推导符号要为'=',input again!!\n");
           printf("the model like: A=aA|aB\n");
		   break;
   case 3: printf("产生式右部的开始和结束符不能为'|',input again!!\n");
           printf("the model like: A=aA|aB\n");
		   break;
   case 4: printf("产生式中不能有连续'|',input again!!\n");
           printf("the model like: A=aA|aB\n");
		   break;
   default: break;	   
		   }
   return;
}