/*******************************************
 語法分析程序
 作者：龔勛         劉棟         羅曉波
 學號：200131500342 200131500350 200131500351
 計科系 13班
********************************************/
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
/*******************************************/
int count=0;              /*分解的產生式的個數*/
int number;               /*所有終結符和非終結符的總數*/
char start;               /*開始符號*/
char termin[50];          /*終結符號*/
char non_ter[50];         /*非終結符號*/
char v[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 validity=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);       /*若在，返回1*/
		if(i==strlen(p))
		    return(0);       /*若不在，返回0*/
	}
}

/*******************************************
 得到一個不是非終結符的符號
********************************************/
char c()
{
	char c='A';
    while(in(c,non_ter)==1)
		c++;
	return(c);
}

/*******************************************
 分解含有左遞歸的產生式
********************************************/
void recur(char *point)
{                     /*完整的產生式在point[]中*/
    int j,m=0,n=3,k;
	char temp[20],ch;
	ch=c();           /*得到一個非終結符*/
	k=strlen(non_ter);
	non_ter[k]=ch;
	non_ter[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++)
	{
		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!");
		    validity=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);
			emp(left[i]);
		}
	}
}

/*******************************************
 求某一符號能否推出‘ ^ ’
********************************************/
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],termin)==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],non_ter)==0)
		{                    /*若左部不在非終結符中，報錯*/
			printf("\nerror1!");
			validity=0;
			return(0);
		}
		for(j=0;j<=strlen(right[i])-1;j++)
		{
			if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]!='^')
			{               /*若右部某一符號不在非終結符、終結符中且不為‘ ^ ’，報錯*/
				printf("\nerror2!");
				validity=0;
				return(0);
			}
		}
	}
	return(1);
}

/*******************************************
 求單個符號的FIRST
********************************************/
void first2(int i)
{                     /*i為符號在所有輸入符號中的序號*/
    char c,temp[20];
	int j,k,m;
	c=v[i];
	char ch='^';
	emp(ch);
	if(in(c,termin)==1)       /*若為終結符*/
    {
        first1[i][0]=c;
	    first1[i][1]='\0';
	}   
	else if(in(c,non_ter)==1)       /*若為非終結符*/
	{
		for(j=0;j<=count-1;j++)
		{
            if(left[j]==c)
			{
                if(in(right[j][0],termin)==1||right[j][0]=='^')
				{
                    temp[0]=right[j][0];
				    temp[1]='\0';
					merge(first1[i],temp,1);
				}
				else if(in(right[j][0],non_ter)==1)
				{
					if(right[j][0]==c)
						continue;
					for(k=0;;k++)
						if(v[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(v[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';
}

/*******************************************
 求各產生式右部的FIRST
********************************************/