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

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

#define LEN 20
#define N 15
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char p[N][LEN];
char newp[N][LEN];
char NT[N][3];
char T[LEN];
int  ntnum=0;
int  tnum=0;
char first[N][LEN];
char follow[N][LEN];
char select[N][LEN];
char select_link[LEN];
char newnt[14]={'H','J','K','L','O','P','Q','R','U','V','W','X','Y','Z'};
int  newnum=0;
int p_count=0;
char first_link[N];
int link_count=1;
char follow_link[N];
int newp_count=0;
struct tables{
	char ntermin;
	char termin;
	char value[LEN];
} table[N][LEN];
/************分析栈**************************/
/*#include "alloc.h"*/
#include "process.h"     /*exit头文件*/
#define ERROR 0
#define OVERFLOW -2
#define SIZE 100
#define ADD 10
typedef struct{
   char *base;
   char *top;
   int stacksize;
 }analyzer;
void initstack(analyzer *s){
  s->base=(char*)malloc(SIZE*sizeof(char));
   if(!s->base) {printf("overflow");exit(OVERFLOW);}
  s->top=s->base;
  *(s->top)='\0';
  s->stacksize=SIZE;
}
char gettop(analyzer *s){
 char e;
 if(s->top==s->base) {printf("ERROR");exit(ERROR);}
 e=*(s->top-1);
 return(e);
}
void push(analyzer *s,char e){
 if(s->top-s->base>=s->stacksize){
   s->base=(char*)realloc(s->base,(s->stacksize+ADD)*sizeof(char));
   if(!s->base) {printf("overflow");exit(OVERFLOW);}
    s->top=s->base+s->stacksize;
    s->stacksize+=ADD;
  }
 *s->top++=e;
 *(s->top)='\0';
}
char pop(analyzer *s){
  char e;
 if(s->top==s->base) {exit(ERROR);printf("ERROR");}
 e=*--s->top;
 *(s->top)='\0';
 return(e);
}
/**********主要函数说明**************************/
void Indicate();
void InputP();
void Error(int a);
void clear();
void getfirst();
void first_get(char x);
void getfollow();
void follow_get();
void getselect();
void print();
int examin();
void Establish_table();
void display_table();
void analyz();
/**************************/
int search(char x,char y,int flag)
{ int i,m=0,j=1;
  if(flag==0)
  {
	while(first[j][1]!=y)
	    j++;
	for(i=2;i<=LEN;i++)
		if(first[j][i]==x) m=1;
	return(m);
  }
  else
  {	
	while(follow[j][1]!=y)
	    j++;
	for(i=2;i<=LEN;i++)
		if(follow[j][i]==x) m=1;
	return(m);
  }
}
int search1(char x,int y)
{ int i,m=0,j=1;
  while(select[j][1]!=y)
	j++;
  for(i=2;i<=LEN;i++)
	if(select[j][i]==x) m=1;
  return(m);
}
int search2(char x,char array[LEN])
{ int i,m=0;
  for(i=1;i<=LEN;i++)
	  if(x==array[i]) m=1;
  return(m);
}
/******************************/
main()
{ int flag;char ch;
 Indicate();/*提示*/
 InputP();/*输入文法*/
 clear();/*消除左递归*/
 getfirst();/*求FIRST集*/
 getfollow();/*求FOLLOW集*/
 getselect();/*求可选集*/
 print();/*输出等价后的文法和文法信息*/
 flag=examin();/*测试是否为LL(1)文法*/
 if(flag)
 { Establish_table();/*建立预测分析表*/
   display_table();/*显示表*/
again:   
   analyz();/*分析符号串*/
   printf("继续分析?(Y/N):");
input0:
   scanf("%c",&ch);
   scanf("%c",&ch);    //不知道为什么要用两次才能正确输入!!
   if((ch=='Y')||(ch=='y')) goto again;
   else if((ch=='N')||(ch=='n')) goto exit;
   else {printf("Wrong input,input again!\n");goto input0;}
 }
exit:;
}
/***************************************************/
void InputP()
{
 int i,j;
 int m,n;
 char ch;
 char temp[LEN];
 for(i=1;;i++)
 {
  i1:j=1;
	for(m=1;m<=LEN;m++)
     temp[m]=temp[0];
   scanf("%c",&ch);
   if(ch==10) goto i1;
   if(ch==35) break;
   temp[j]=ch;
   for(;;)
   { j++;
     scanf("%c",&ch);
	 if(ch==10) break;
	 else temp[j]=ch;
   }
   if((temp[1]>'Z')||(temp[1]<'A'))
      { Error(1);
        goto i1;
      }
   if(temp[2]!='=')
	  { Error(2);
        goto i1;
      }
   if((temp[3]=='|')||(temp[j-1]=='|'))
	  { Error(3);
        goto i1;
      }
   for(m=1;m<=j-2;m++)
      if((temp[m]=='|')&&(temp[m+1]=='|'))
       { Error(4);
         goto i1;
       }
   n=1;
   ntnum++;
   NT[ntnum][1]=temp[1];
   for(m=1;m<=j-1;m++)
     if(temp[m]!='|')
	 { p[i][n]=temp[m];
            n++;
     }
      else
	  { i++;
        n=2;
        p[i][1]=temp[1];
        p[i][2]=temp[2];
        n++;
        p_count++;
      }
	  p[i][j]='\0';
   p_count++;
  }
 for(i=1;i<=ntnum;i++)
 { 
	for(j=1;j<=ntnum;j++)
    if((NT[i][1]==NT[j][1])&&(i!=j))	/*有相同非终极符*/
	{ 
	  for(m=j;m<=ntnum;m++)
	  {NT[m][1]=NT[m+1][1];
	   NT[m][2]=NT[m+1][2];
	  }
	  ntnum--;
	}
 }
}
/*****************************************************/
void Indicate()
{
 printf("        *******************************\n");
 printf("        *        LL预测分析法         *\n");
 printf("        *******************************\n");
 printf("1.非终极符必须大写,推导符号为'='\n2.产生式右部的开始和结束符不能为'|'\n");
 printf("3.产生式中不能有连续'|'\n");
 printf("4.以下为消除左递归所引入的非终极符，请不要在文法中使用到\n");
 printf(" .{'H','J','K','L','O','P','Q','R','U','V','W','X','Y','Z'}.\nthe model like: A=aA|aB\n");
 printf("请输入文法，以'#'结束(产生式表示):\n");
}
/*********************************************/
void clear()
{ int a,b,c,d,m,n,f,i,j,k,p1,p2;
  char temp[LEN];
  for(i=1;i<=ntnum;i++)
  {  p2=0;
	 for(j=1;j<=i-1;j++)
    {for(a=1;a<=p_count;a++)
      if((NT[i][1]==p[a][1])&&(NT[j][1]==p[a][3]))
	   {  p[a][1]=10;
	   	  b=4;
		  while(p[a][b]!='\0')
		  { temp[b]=p[a][b];
		    b++;
		  }
		  for(m=1;m<=p_count;m++)
		  if(p[m][1]==NT[j][1])
		  { p_count++;
			p[p_count][1]=NT[i][1];
			p[p_count][2]='=';
			n=3;
			while(p[m][n]!='\0')
			{ p[p_count][n]=p[m][n];
			  n++;
			}
			for(c=4;c<b;c++)
			{ p[p_count][n]=temp[c];
			  n++;
			}
			p[p_count][n]='\0';
		  }
	  }
    }
   for(m=1;m<=p_count;m++)
    if((p[m][1]==NT[i][1])&&(p[m][3]==NT[i][1]))
	  NT[i][2]=1;
   for(k=1;k<=p_count;k++)
     if((p[k][1]==NT[i][1])&&(NT[i][2]==1))
	 { 
	  if(p[k][1]==p[k][3])
	  { p1=1;
	    while((!((p[p1][1]==NT[i][1])&&(p[p1][3]!=NT[i][1])))&&(p1<=p_count))
		{p1++;}
	    if(p1<=p_count)
		{d=3;
	     p[k][1]=newnt[newnum];
	     while(p[k][d+1]!='\0')
		 {p[k][d]=p[k][d+1];
	      d++;
		 }
	     p[k][d]=newnt[newnum];
	     p[k][d+1]='\0';
		 p2=1;
		}
		else
		{d=3;
	     while(p[k][d+1]!='\0')
		 {p[k][d]=p[k][d+1];
	      d++;
		 }
	     p[k][d]=p[k][1];
	     p[k][d+1]='\0';
		}
	  }
	  else
	  {f=1;
	    while(p[k][f]!='\0')
		{f++;}
		p[k][f]=newnt[newnum];
		p[k][f+1]='\0';
	  }
	 }
   if((NT[i][2]==1)&&(p2==1))
   {
    ntnum++;
    NT[ntnum][1]=newnt[newnum];
    p_count++;
    p[p_count][1]=newnt[newnum];
    p[p_count][2]='=';
    p[p_count][3]='$';
	newnum++;
    if(newnum>14)
	{printf("not enough NT! over flow");
     exit(1);
	}
   }
   else if((NT[i][2]==1)&&(p2==0))
   {p_count++;
    p[p_count][1]=p[i][1];
    p[p_count][2]='=';
    p[p_count][3]='$';
   }
 }
 for(i=1;i<=ntnum;i++)		/*消除无用非终极符*/
 { j=1;
   while((NT[i][1]!=p[j][1])&&(j<=p_count))
   {j++;}
   if(j>p_count)		/*有无用非终极符*/
   { 
	 for(m=i;m<=ntnum;m++)
	 {NT[m][1]=NT[m+1][1];
	  NT[m][2]=NT[m+1][2];
	 }
	 ntnum--;
   }
 }
 for(i=1;i<=p_count;i++)
 {
   if(p[i][1]!=10)
   { m=3;
     while(p[i][m]!='\0')
	 {
	   if((p[i][m]>='A')&&(p[i][m]<='Z'))
	   {k=1;
		while((p[i][m]!=NT[k][1])&&(k<=ntnum))
		{k++;}
	    if(k>ntnum) goto nextp;  /*有无效非终极符*/
	   }
	   m++;
	 }
	 j=1;n=1;newp_count++;
	 while(p[i][j]!='\0')
	 {
	  if((p[i][j]=='$')&&(p[i][j+1]!='\0'))
	  j++;
	  else
	  {newp[newp_count][n]=p[i][j];
	   n++;j++;}
	 }
     newp[newp_count][n]='\0';
   }
nextp: ;
 }				/*去除无效产生式*/
 for(i=1;i<=newp_count;i++)
 {	 j=3;
      while((newp[i][j]!='\0')&&(newp[i][j]!='$'))
	  {if(((newp[i][j]>'Z')||(newp[i][j]<'A'))&&(!search2(newp[i][j],T)))
		{ tnum++;
  	      T[tnum]=newp[i][j];
		  j++;
	     }
		else j++;
	  }
 }
 tnum++;T[tnum]='#';
}
/****************************************/
void getfirst()
{ int i,j,m,n;
  for(i=1;i<=ntnum;i++)
  { first[i][1]=NT[i][1];
    first[i][2]='\0';
  }
  for(i=1;i<=ntnum;i++)
  {for(j=1;j<=link_count;j++)
     first_link[j]='\0';
   link_count=1;
   first_get(first[i][1]);
  }
}
void first_get(char x)
{ int i,j,k,m,n,a;
  i=1;
  while((first[i][1]!=x)&&(i<=ntnum))
   i++;
  if(i>ntnum) goto exit1;
  for(j=1;j<=link_count;j++)
  if(first_link[j]==first[i][1]) goto exit1;
  first_link[link_count]=first[i][1];
  link_count++;
  for(m=1;m<=newp_count;m++)
	  if(newp[m][1]==first[i][1])
	  { if(newp[m][3]=='$')
	        ;
	    else if((newp[m][3]>'Z')||(newp[m][3]<'A'))
		{  if(!search(newp[m][3],first[i][1],0))
		    {for(j=LEN;j>2;j--)
		     first[i][j]=first[i][j-1];
		     first[i][2]=newp[m][3];
		    }
		}
		else
		{ n=3;
while1:	  while(newp[m][n]!='\0')
		  { 
		   if((newp[m][n]>'Z')||(newp[m][n]<'A'))
		   { if(!search(newp[m][n],first[i][1],0))
		      {for(j=LEN;j>2;j--)
		       first[i][j]=first[i][j-1];
		       first[i][2]=newp[m][n];
		      }