531.txt

编译原理

#include "zht.h"
#include<stack> 
using namespace std; 

/*----main function--------*/
void main(void)
{

void Init();
InputVn();
InputVt();
InputP();
//getchar();
FirstFollow();
printf("所得first集为：");
ShowCollect(first);
printf("所得follow集为：");
ShowCollect(follow);
}

void Init()
{
 int i;
 vnNum = 0;
 vtNum = 0;
 PNum = 0;
 for(i = 0; i <= MaxVnNum; i++)
  Vn[i] = '\0';
 for(i = 0; i <= MaxVtNum; i++)
  Vt[i] = '\0';
 for(i = 0; i < MaxRuleNum; i++)
 {
  P[i].lCursor = NULL;
  P[i].rHead = NULL;
  P[i].rLength = 0;
 }
 PNum = 0;
 for(i = 0; i <= MaxPLength; i++)
  buffer[i] = '\0';
 for(i = 0; i < MaxVnNum; i++)
 {
  first[i] = NULL;
  follow[i] = NULL;
 }

}
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
int IndexCh(char ch) 
{
 int n;
 n = 0; /*is Vn?*/
 while(ch != Vn[n] && '\0' != Vn[n])
 n++;
 if('\0' != Vn[n])
 return 100 + n;
 n = 0; /*is Vt?*/
 while(ch != Vt[n] && '\0' != Vt[n])
 n++;
 if('\0' != Vt[n])
 return n;
 return -1;
}
/*输出Vn或Vt的内容*/
void ShowChArray(char* collect)
{
 int k = 0;
 while('\0' != collect[k])
 {
  printf(" %c ", collect[k++]);
 }
 printf("\n");
}
/*输入非终结符*/
void InputVn()
{
 int inErr = 1;
 int n,k;
 char ch;
 while(inErr)
 {
  printf("\n请输入所有的非终结符，注意：");
  printf("请将开始符放在第一位，并以#号结束:\n"); 
  ch = ' ';
  n = 0;
  /*初始化数组*/
  while(n < MaxVnNum)
  {
   Vn[n++] = '\0';
  }
  n = 0;
  while(('#' != ch) && (n < MaxVnNum))
  {
   if(' ' != ch && '\n' != ch && -1 == IndexCh(ch))
   {
    Vn[n++] = ch;
    vnNum++;
   }
   ch = getchar();
  }
  Vn[n] = '#'; /*以"#"标志结束用于判断长度是否合法*/
  k = n; /*k用于记录n以便改Vn[n]='\0'*/
  if('#' != ch)
  {
  if( '#' != (ch = getchar()))
   {
    while('#' != (ch = getchar()))
     ;
    printf("\n符号数目超过限制！\n");
    inErr = 1;
    continue;
   }
  }
  /*正确性确认，正确则，执行下下面，否则重新输入*/
  Vn[k] = '\0';
  ShowChArray(Vn);
  ch = ' ';
  while('y' != ch && 'n' != ch)
  {
  if('\n' != ch)
  {
    printf("输入正确确认?(y/n):");
   }
   scanf("%c", &ch);
  }
  if('n' == ch)
  {
   printf("录入错误重新输入！\n");
   inErr = 1;
  }
  else
  {
   inErr = 0;
  }
 }
}
/*输入终结符*/
void InputVt()
{
 int inErr = 1;
 int n,k;
 char ch;
 while(inErr)
 {
  printf("\n请输入所有的终结符，注意：");
  printf("以#号结束:\n"); 
  ch = ' ';
  n = 0;
  /*初始化数组*/
  while(n < MaxVtNum)
  {
   Vt[n++] = '\0';
  }
  n = 0;
  while(('#' != ch) && (n < MaxVtNum))
  {
  if(' ' != ch && '\n' != ch && -1 == IndexCh(ch))
   {
    Vt[n++] = ch;
    vtNum++;
   }
   ch = getchar();
  }
  Vt[n] = '#'; /*以"#"标志结束*/
  k = n; /*k用于记录n以便改Vt[n]='\0'*/
  if('#' != ch)
  {
   /*if( '#' != (ch = getchar()))
   {
    while('#' != (ch = getchar()))
     ;*/
    printf("\n符号数目超过限制！\n");
    inErr = 1;
    continue;
   
  }
  /*正确性确认，正确则，执行下下面，否则重新输入*/
  Vt[k] = '\0';
  ShowChArray(Vt);
  ch = ' ';
  while('y' != ch && 'n' != ch)
  {
   if('\n' != ch)
   {
    printf("输入正确确认?(y/n):");
   }
   scanf("%c", &ch);
  }
  if('n' == ch)
  {
   printf("录入错误重新输入！\n");
   inErr = 1;
  }
  else
  {
   inErr = 0;
  }
 }
}
/*产生式输入*/
void InputP()
{
 char ch;
 int i = 0, n,num;
 printf("请输入文法产生式的个数：");
 scanf("%d", &num);
 PNum = num;
 getchar(); /*消除回车符*/
 printf("\n请输入文法的%d个产生式,并以回车分隔每个产生式：", num);
 printf("\n");
 while(i < num)
 {
  printf("第%d个：", i);
  /*初始化*/
  for(n =0; n < MaxPLength; n++)
   buffer[n] = '\0';
  /*输入产生式串*/
  ch = ' ';
  n = 0;
  while('\n' != (ch = getchar()) && n < MaxPLength)
  {
   if(' ' != ch)
    buffer[n++] = ch;    
  }
  buffer[n] = '\0';
/*  printf("%s", buffer);*/
  if(CheckP(buffer))
  {
   /*填写入产生式结构体*/
   pRNode *pt, *qt;
   P[i].lCursor = IndexCh(buffer[0]);
   pt = (struct pRNode*)malloc(sizeof(struct pRNode));
   pt->rCursor = IndexCh(buffer[3]);
   pt->next = NULL;
   P[i].rHead = pt;
   n = 4;
   while('\0' != buffer[n])
   {
    qt = (struct pRNode*)malloc(sizeof(struct pRNode));
    qt->rCursor = IndexCh(buffer[n]);
    qt->next = NULL;
    pt->next = qt;
    pt = qt;
    n++;
   }
   P[i].rLength = n - 3;
   i++;
   /*调试时使用*/
  }
  else
   printf("输入符号含非法在成分，请重新输入！\n");
 }
}
/*判断产生式正确性*/
bool CheckP(char * st)
{
 int n;
 if(100 > IndexCh(st[0]))
  return false;
 if('-' != st[1])
  return false;
 if('>' != st[2])
  return false;
 for(n = 3; '\0' != st[n]; n ++)
 {
  if(-1 == IndexCh(st[n]))
   return false;
 }
 return true;
}
bool HaveEmpty(int nVn)
{
	if(nVn==NULL)
		return true;
	else
		return false;
}

/*=====first & follow====d11111111111111111111111111111111111111111e====*/
/*计算first集,U->xx...*/
void First(int U)
{
 stack<int> s;
 int i,j;
 for(i = 0; i < PNum; i++)
 {
  if(P[i].lCursor == U)
  {
   struct pRNode* pt;
   pt = P[i].rHead;
   j = 0;
   while(j < P[i].rLength)
   {
    if(pt->rCursor<100)
    {
     /*注:此处因编程出错,使空产生式时
     rlength同样是1,故此处同样可处理空产生式*/
     AddFirst(U, pt->rCursor);
     break;
    }
    else
    {
     if(NULL == first[pt->rCursor - 100])
     {
		 s.push(U);
		 First(pt->rCursor);
		 s.pop();
     }
	 AddFirst(U, pt->rCursor);
	 if(!HaveEmpty(pt->rCursor))
     {
      break;
     }
     else
     {
      pt = pt->next;
     }
    }
   j++;
   }
    
   if(j >= P[i].rLength) /*当产生式右部都能推出空时*/
    AddFirst(U, -1);
  }
 }
}
void AddFirst(int U, int nCh)
{
	struct collectNode *pt, *qt;
	//int ch; /*用于处理Vn00000000000000000000000000000000000000000000000000*/
	//p2 = NULL; 
	pt = NULL;
	qt = NULL;
	pt = first[U - 100];
	while(NULL != pt)
	{
		if(pt->nVt == nCh)
			break;
		else
		{
			qt = pt;
			pt = pt->next;
		}
	}
	if(NULL == pt)
	{
		pt = (struct collectNode *)malloc(sizeof(struct collectNode));
		pt->nVt = nCh;/*用于处理Vn0000000000000ssssssssssssssssssddddd*/
		pt->next = NULL;
		if(first[U- 100] ==NULL )
		{
			first[U- 100] =pt;
		}
		else
		{
			qt->next = pt;
			qt=pt;
		     /*qt指向first集的最后一个元素*/
		}
		//pt = pt->next;
	}

	
}
void Follow(int V)
{
int i,j,m;
for(i = 0; i < PNum; i++)
 {
  if(P[i].lCursor == V)
  {
	  
   struct pRNode *pt;
   pt = P[i].rHead;
   j = 0;
   while(j < P[i].rLength)
   {
	   if(pt->rCursor==V)
	   {
		   pt=pt->next;
		   if(pt->rCursor<100)
			   m=1;
	       else m=0;
	   }	   
	   AddFollow( V, pt->rCursor,m);
	   j++;
	  // pt=pt->next;
   }
}
}
}

/*#用-1表示,kind用于区分是并入符号的first集，还是follow集
kind = 0表加入follow集，kind = 1加入first集*/
void AddFollow(int V, int nCh, int kind)
{
 struct collectNode *pt, *qt;
 int ch; /*用于处理Vn*/
 pt = NULL;
 qt = NULL;
 if(nCh < 100) /*为终结符时*55555555555555555555555555555*/
 {
  pt = follow[V - 100];
  while(NULL != pt)
  {
   if(pt->nVt == nCh)
    break;
   else
   {
    qt = pt;
    pt = pt->next;
   }
  }
  if(NULL == pt)
  {
   pt = (struct collectNode *)malloc(sizeof(struct collectNode));
   pt->nVt = nCh;
   pt->next = NULL;
   if(NULL == follow[V - 100])
   {
    follow[V - 100] = pt;
   }
   else
   {
    qt->next = pt; /*qt指向follow集的最后一个元素*/
   }
   pt = pt->next;
  }
 }
 else /*为非终结符时，要区分是加first还是follow*/
 {
  if(0 == kind)
  {
   pt = follow[nCh - 100];
   while(NULL != pt)
   {
    ch = pt->nVt;
    AddFollow(V, ch, 0);
    pt = pt->next;
   }
  }
  else
  {
   pt = first[nCh - 100];
   while(NULL != pt)
   {
    ch = pt->nVt;
    if(-1 != ch)
    {
     AddFollow(V, ch, 1);
    }
    pt = pt->next;
   }
  }
 }
}
/*计算first和follow*/
void FirstFollow()
{
 int i;
 i = 0;
 while('\0' != Vn[i])
 {
  if(NULL == first[i])
   First(100 + i);
  i++;
 }
 /*i = 0;
 while('\0' != Vn[i])
 {
  if(NULL == follow[i])
   Follow(100 + i);
  i++;
 }*/
}
/*输出first或follow集*/
void ShowCollect(struct collectNode**collect)
{
 int i;
 struct collectNode *pt;
 i = 0;
 while(NULL != collect[i])
 {
  pt = collect[i];
  printf("\n%c:\t", Vn[i]);
  while(NULL != pt)
  {
   if(-1 != pt->nVt)
   {
    printf(" %c", Vt[pt->nVt]);
   }
   else
    printf(" #");
   pt = pt->next;
  }
  i++;
 }
 printf("\n");
}