#include<stdlib.h>
#include<stdio.h>
#include<string.h>
/*******************************************/
int count=0;              /*產生式的總個數*/
int number;               /*所有終結符和非終結符的總數*/
char start;               /*開始符號*/
char zhongjie[50];          /*終結符號串*/
char fzhongjie[50];         /*非終結符號串*/
char fh[50];               /*所有符號串*/
char left[50];            /*左部*/
char right[50][50];       /*右部*/
char first[50][50],follow[50][50];       /*各產生式右部的FIRST和左部的FOLLOW集合*/
char first1[50][50];      /*所有單個符號的FIRST集合*/
char select[50][50];      /*各單個產生式的SELECT集合*/
char f[50],F[50];         /*記錄各符號的FIRST和FOLLOW是否已求過*/
char empty[20];           /*記錄可直接推出^的符號*/
char TEMP[50];            /*求FOLLOW時存放某一符號串的FIRST集合*/
int youxiao=1;           /*表示輸入文法是否有效*/
int ll=1;                 /*表示輸入文法是否為LL(1)文法*/
int M[20][20];            /*分析表*/
char choose;              /*用戶輸入時使用*/
char empt[20];            /*求_emp()時使用*/
char fo[20];              /*求FOLLOW集合時使用*/


/*******************************************/

int in(char c,char *p)/*判斷字符是否在指定字符串中*/
{
 int i;
 if(strlen(p)==0)
  return(0);
 for(i=0;;i++)
 { 
  if(p[i]==c)
   return(1);       
  if(i==strlen(p))
      return(0);      
 }
}

/*******************************************/

char c()/*得到一個不是非終結符的符號，用于消除左遞歸*/
{
 char c='A';
    while(in(c,fzhongjie)==1)
  c++;
 return(c);
}


/*******************************************/

void recur(char *point)/*分解含有左遞歸的產生式*/
{                     
    int j,m=0,n=3,k;
 char temp[20],ch;
 ch=c();           /*得到一個非終結符*/
 k=strlen(fzhongjie);
 fzhongjie[k]=ch;
 fzhongjie[k+1]='\0';
 for(j=0;j<=strlen(point)-1;j++)
 { 
  if(point[n]==point[0])
  {                          /*如果‘|’后或者頭個的首符號和左部相同*/
   for(j=n+1;j<=strlen(point)-1;j++)
   {
       while(point[j]!='|'&&point[j]!='\0')
        temp[m++]=point[j++];
    left[count]=ch;
    memcpy(right[count],temp,m);
    right[count][m]=ch;
    right[count][m+1]='\0';
    m=0;
    count++;
    if(point[j]=='|')
    {
     n=j+1;
     break;
    }
   }
  }
  else
  {                          /*如果‘|’后或者頭個的首符號和左部不同*/
   left[count]=ch;
   right[count][0]='^';
   right[count][1]='\0';
   count++;
   for(j=n;j<=strlen(point)-1;j++)
   {
       if(point[j]!='|')
           temp[m++]=point[j];
       else
    {
        left[count]=point[0];
        memcpy(right[count],temp,m);
        right[count][m]=ch;
        right[count][m+1]='\0';
     printf(" count=%d ",count);
     m=0;
        count++;
    }
   }
            left[count]=point[0];
      memcpy(right[count],temp,m);
      right[count][m]=ch;
        right[count][m+1]='\0';
   count++;
      m=0;
  }
 }
}
/*******************************************/

void non_re(char *point)/*分解不含有左遞歸的產生式*/
{
    int m=0,j;
 char temp[20];
 for(j=3;j<=strlen(point)-1;j++) 
 {
     if(point[j]!='|')  /*判斷是否有|*/
      temp[m++]=point[j];
  else
  {
      left[count]=point[0];
      memcpy(right[count],temp,m);
      right[count][m]='\0';
   m=0;
   count++;
  }
 }
    left[count]=point[0];
    memcpy(right[count],temp,m);
    right[count][m]='\0';
    count++;
  
 m=0;

}
/*******************************************/

char grammer(char *t,char *n,char *left,char right[50][50])/*讀入文法*/
{
 char vn[50],vt[50];
 char s;
 char p[50][50];
 int i,j,k;
 printf("請輸入文法的非終結符號串：");
    scanf("%s",vn);
 getchar();/*吞吃回車*/
    i=strlen(vn);/*計算長度*/
    memcpy(n,vn,i);/*復制字符串*/
 n[i]='\0';

 printf("請輸入文法的終結符號串：");
    scanf("%s",vt);
 getchar();
    i=strlen(vt);
    memcpy(t,vt,i);
 t[i]='\0';
 
printf("請輸入文法的開始符號：");
 scanf("%c",&s);
 getchar();
 printf("請輸入文法產生式的條數：");
    scanf("%d",&i);
 getchar();
for(j=1;j<=i;j++)/*i=3*/
{
  printf("請輸入文法的第%d條（共%d條）產生式：",j,i);
  scanf("%s",p[j-1]);
  getchar();
 }
for(j=0;j<=i-1;j++)
  if(p[j][1]!='-'&&p[j][2]!='>')/*檢測輸入是否符合“->”*/
  { printf("\ninput error!");
      youxiao=0;
   return('\0'); }            

   for(k=0;k<=i-1;k++)
   {                        /*分解輸入的各產生式*/
        if(p[k][3]==p[k][0])
            recur(p[k]); /*符合左遞歸條件*/
  else
      non_re(p[k]);/*不符合條件*/
 }
 return(s);
}
/*******************************************/

void merge(char *d,char *s,int type)/*將單個符號或符號串并入另一符號串*/
{									/*d是目標符號串，s是源串*/ 
									/*type＝1，源串中的‘ ^ ’一并并入目串*/
									/*type＝2，源串中的‘ ^ ’不并入目串*/
    int i,j;
 for(i=0;i<=strlen(s)-1;i++)
 {
        if(type==2&&s[i]=='^') ;
  else
  {
   for(j=0;;j++)
   {
       if(j<strlen(d)&&s[i]==d[j])
       break;
                if(j==strlen(d))
    {
        d[j]=s[i];
        d[j+1]='\0';
        break;
    }
   }
  }
 }
}
/*******************************************/

 void emp(char c)/*求所有能直接推出^的符號*/
{                   /*即求所有由‘ ^ ’推出的符號*/
 char temp[10];
 int i;
 for(i=0;i<=count-1;i++)
 {
  if(right[i][0]==c&&strlen(right[i])==1)
  {
   temp[0]=left[i];
   temp[1]='\0';
   merge(empty,temp,1);
   
  }
 }
}


/*******************************************/


int _emp(char c)/*求某一符號能否推出‘ ^ */
{                  /*若能推出，返回1；否則，返回0*/
 int i,j,k,result=1,mark=0;
 char temp[20];
 temp[0]=c;
 temp[1]='\0';
 merge(empt,temp,1);
 if(in(c,empty)==1)
  return(1);
 for(i=0;;i++)
 {
  if(i==count)
            return(0);
  if(left[i]==c)         /*找一個 左部為c的產生式*/
  {
    j=strlen(right[i]);    /*j為右部的長度*/
   if(j==1&&in(right[i][0],empty)==1)
   return(1);
   else if(j==1&&in(right[i][0],zhongjie)==1)
    return(0);
   else 
   {
 for(k=0;k<=j-1;k++)        
 
	 if(in(right[i][k],empt)==1)
     mark=1;
   if(mark==1)
    continue;
 
    else
    {
     for(k=0;k<=j-1;k++)
     {
      result*=_emp(right[i][k]);
      temp[0]=right[i][k];
      temp[1]='\0';
     merge(empt,temp,1);
     }
    }
   }
      if(result==0&&i<count)
       continue;
      else if(result==1&&i<count)
       return(1);
  }
 }
}

/*******************************************/

int judge()/*判斷文法是否正確*/
{
    int i,j;
 for(i=0;i<=count-1;i++)
 {
  if(in(left[i],fzhongjie)==0)
  {                    /*若左部不在非終結符中，報錯*/
   printf("\nerror1!");
   youxiao=0;
   return(0);
  }
  for(j=0;j<=strlen(right[i])-1;j++)
  {
   if(in(right[i][j],fzhongjie)==0&&in(right[i][j],zhongjie)==0&&right[i][j]!='^')
   {               /*若右部某一符號不在非終結符、終結符中且不為‘ ^ ’，報錯*/
    printf("\nerror2!");
    youxiao=0;
    return(0);
   }
  }
 }
 return(1);
}


/*******************************************/

void first2(int i)/*求單個符號的FIRST*/
{                     /*i為符號在所有輸入符號中的序號*/
char c,temp[20];
 int j,k,m;
 c=fh[i];
 char ch='^';
 emp(ch);
 if(in(c,zhongjie)==1)       /*若為終結符*/
 {
        first1[i][0]=c;
     first1[i][1]='\0';
 }   
 else if(in(c,fzhongjie)==1)       /*若為非終結符*/
 {
  for(j=0;j<=count-1;j++)
	{
            if(left[j]==c)
		{
                if(in(right[j][0],zhongjie)==1||right[j][0]=='^')/*右部首個為終結符或為空*/
			{
                    temp[0]=right[j][0];
					temp[1]='\0';
					merge(first1[i],temp,1);
			}
		else if(in(right[j][0],fzhongjie)==1)
			{
			if(right[j][0]==c)/*判斷是否右部頭一個是自己本身 非終結符*/
			continue;
			 for(k=0;;k++)
			 if(fh[k]==right[j][0])
			 break;
			if(f[k]=='0')
				{   
				first2(k);
				f[k]='1';
				}
			merge(first1[i],first1[k],2);
			for(k=0;k<=strlen(right[j])-1;k++)
				{
				 empt[0]='\0';
				 if(_emp(right[j][k])==1&&k<strlen(right[j])-1)/*求某一符號能否推出‘ ^ */
					 {
					 for(m=0;;m++)
					 if(fh[m]==right[j][k+1])
					  break;
						if(f[m]=='0')
						{
						 first2(m);
						 f[m]='1';
						}
					merge(first1[i],first1[m],2);
					}
					else if(_emp(right[j][k])==1&&k==strlen(right[j])-1)
					{
					temp[0]='^';
					temp[1]='\0';
					merge(first1[i],temp,1);
					}
					else 
					break;
				}
			}
		}
	}
 }
 f[i]='1';
}


/*******************************************/


void FIRST(int i,char *p)/*求各產生式右部的FIRST*/
{
 int length;
 int j,k,m;
 char temp[20];
 length=strlen(p);
 if(length==1)                  /*如果右部為單個符號*/
 {
  if(p[0]=='^')
        {   
   if(i>=0)
            {
       first[i][0]='^';
       first[i][1]='\0';
   }
   else
   {
    TEMP[0]='^';
    TEMP[1]='\0';
   }
  }
  else /*如果長度大于1*/
  { 
   for(j=0;;j++)
    if(fh[j]==p[0])
     break;
   if(i>=0)
   {
       memcpy(first[i],first1[j],strlen(first1[j]));
       first[i][strlen(first1[j])]='\0';