ll1.c

输入已经消除左递归的以及提取公共左因子的LL(1)文法

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
/*产生式类型定义*/
typedef struct type						
{
	char origin;						/*大写字符*/
	char array[5];						/*产生式右边字符*/
	int length;							/*字符个数*/
}type;

/*各个非终结符的信息*/
typedef struct info 
{
	int isNull;							/*能否推出"空"字符 1是 0否*/
	char firstSet[10];
	char followSet[10];
}info;

int n1;									/*文法中产生式的个数*/
int numOfVn,numOfVt;					/*记录VN和VT的个数*/

char VN[10],VT[10];						/*非终结符和终结符表*/

char select[10][10];					/*各个产生式的SELECT集*/

type table[10][10];						/*预测分析表*/

int j=0,b=0,top=0,l;					/*L为输入串长度*/

char A[20];								/*分析栈*/
char B[20];								/*剩余串*/

/* 获取由用户输入的文法的产生式,保存到所定义的数据结构中,在此过程中可以顺便搜集非终结符列表 */
void getLL1(type ll1[]);


void print()							/*输出分析栈*/
{
	int a;								/*指针*/
	for(a=0;a<=top+1;a++)
		printf("%c",A[a]);
	printf("\t\t");
}										/*print*/

void print1()							/*输出剩余串*/
{
	int j;
	for(j=0;j<b;j++)					/*输出对齐符*/
		printf(" ");
   	for(j=b;j<=l;j++)
		printf("%c",B[j]);
	printf("\t\t\t");
}/*print1*/

/*返回某一非终结符在表中的序号*/
int inVN(char c)
{
	int i;
	for (i=0;i<numOfVn;i++)
	{
		if (c==VN[i])
		{
			return i;
		}
	}
	return -1;
}

/*返回某一终结符在表中的序号*/
int inVT(char c)
{
	int i;
	for (i=0;i<numOfVt;i++)
	{
		if (c==VT[i])
		{
			return i;
		}
	}
	return -1;
}


/*辅助函数:若字符c不在s中，则将c加入s*/
void addIn1(char s[],char c,int *flag)
{
	int i,len,tag=1;
	len=strlen(s);
	for (i=0;i<len;i++)
	{
		if (s[i]==c)
		{
			tag=0;
			break;
		}
	}
	if (tag)
	{
		s[len]=c;
		s[len+1]='\0';
		*flag=1;
	}
}

/*辅助函数:将s2中不存在与s1中的字符加入到s1中*/
void addIn2(char s1[],char s2[],int *flag)
{
	int i,len;
	len=strlen(s2);
	for (i=0;i<len;i++)
	{
		addIn1(s1,s2[i],flag);
	}
}

/* 扫描每条产生式,求出能推出"空的" VN ,在此过程中可以顺便搜集终结符列表 */
void getNULL(type ll1[],info infoVn[]);


/* 计算各非终结符的First集 */
void getFirst(type ll1[],info infoVn[]);

/* 计算各非终结符的Follow集 */
void getFollow(type ll1[],info infoVn[]);

/* 根据计算出来的First,Follow集求解各个产生式的SELECT 
构造LL1的预测分析表
*/
void setTable(type ll1[],info infoVn[]);

/* 对输入的文法串进行分析扫描的主控程序 */
void doScan();


void main()
{
	int i,m,n;//m计算非终结符个数,n计算终结符个数
	type ll1[15];
	info infoVn[10];

	getLL1(ll1);
	getNULL(ll1,infoVn);//从终结符字符串中提取可推出空的字符



	getFirst(ll1,infoVn);
	getFollow(ll1,infoVn);

	for(m=0;m<numOfVn;m++)					/*初始化分析表*/
		for(n=0;n<numOfVt;n++)
			table[m][n].origin='N';			/*全部赋为空*/

	setTable(ll1,infoVn);

	printf("能推出空的非终结符有:");
	for (i=0;i<numOfVn;i++)
	{
		if (infoVn[i].isNull==1)
		{
			printf("%3c",VN[i]);
		}
	}
	printf("\n");

	for (i=0;i<numOfVn;i++)//输出FIRST集合
	{
		printf("FIRST(%c)=%s\n",VN[i],infoVn[i].firstSet);

	}
	printf("\n");

	for (i=0;i<numOfVn;i++)//输出FOLLOW集合
	{
		printf("FOLLOW(%c)=%s\n",VN[i],infoVn[i].followSet);

	}
	printf("\n");
	
	doScan();
}


/* 获取由用户输入的文法的产生式,保存到所定义的数据结构中 */
void getLL1(type ll1[])
{    
	int n,i,k=0,flag=0;//n记录当前输入产生式个数
	char l,r[10];//将输入的字符存到l中
	printf("请输入文法的产生式个数:\n");
	scanf("%d",&n);
	getchar();
	n1=n;
	for (i=0;i<n;i++)
	{
		flag=0;//未输入标志符置为零
		printf("输入第%d条产生式的左部:\n",i+1);
		scanf("%c",&l);

		getchar();
		ll1[i].origin=l;
		printf("输入第%d条产生式的右部(默认不超过10个字符，^表示ε):\n",i+1);
		scanf("%s",r);
		getchar();
		strcpy(ll1[i].array,r);//将字符串存放在数组
		ll1[i].length=strlen(ll1[i].array);

		addIn1(VN,l,&flag);//将输入的产生式左部加到非终结符字符集
	}
	numOfVn=strlen(VN);//获得当前非终结符个数
	
	printf("所输入的文法为:\n");
	for (i=0;i<n;i++)
	{
		printf("%c->%s\n",ll1[i].origin,ll1[i].array);
	}
}

/* 扫描每条产生式,求出能推出"空的" VN ,在此过程中可以顺便搜集终结符列表 */
//递结规约过程
void getNULL(type ll1[],info infoVn[])
{
	int i,j,m,flag[10],flag1=0,flag2=1,flag3=1,k=0,len;
	int isModified[10];//扫描
	for (i=0;i<10;i++)
	{
		flag[i]=1;
	}
	/*将每一非终结符能否推出"空"的标记置为未定*/
	for (i=0;i<numOfVn;i++)
	{
		infoVn[i].isNull=-1;
	}
	/*第一遍扫描，删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的产生式都被删除，则该非终结符不能推出空*/
	/*在此过程中可以搜集终结符表*/
	for (i=0;i<n1;i++)
	{
		/*产生式右部为空的非终结符当然可以推出空*/
		if( ll1[i].array[0]=='^' )
		{
			infoVn[inVN(ll1[i].origin)].isNull=1;

			/*删除该非终结符的所有产生式*/
			for (m=0;m<n1;m++)
			{
				if (ll1[i].origin == ll1[m].origin)
				{
					flag[m]=0;
				}
			}
		}
		for(j=0;j<ll1[i].length;j++)
		{
			flag1=0;
			if ( (!isupper(ll1[i].array[j])) && ll1[i].array[j]!='^' )
			{
				flag[i]=0;					/*删除所有右部含有终结符的产生式,将对应的标志置0*/
				infoVn[inVN(ll1[i].origin)].isNull=0;
				
				/*搜集终结符*/
				addIn1(VT,ll1[i].array[j],&flag1);//构造终结符集
			}
		}

	}
	addIn1(VT,'#',&flag1);//得到终结符集
	numOfVt=strlen(VT);
	for (i=0;i<numOfVn;i++)
	{
		isModified[i]=infoVn[i].isNull;
	}

	/*flag3用来标记是否停止扫描(到非终结符对应的特征没有变化为止)*/
	while(flag3)
	{
		/*扫描产生式右部的每一符号*/
		flag3=0;
		

		for (i=0;i<n1;i++)
		{
			len=ll1[i].length;
			for (j=0;j<ll1[i].length;j++)
			{
				
				if (isupper(ll1[i].array[j]))
				{
					if (infoVn[inVN(ll1[i].array[j])].isNull==1)//如果非终结符的产生式为空，那么将该产生式字符删除
					{
						len--;
					}
					else if (infoVn[inVN(ll1[i].array[j])].isNull==0)
					{
						flag[i]=0;
						for (k=0;k<n1;k++)
						{
							/*某一VN的产生式在扫描过程中是否都被删除*/
							if ( inVN(ll1[i].array[j]) == inVN(ll1[k].origin) )
							{
								if(flag[k]==1)
									flag2=0;
							}
						}
						if (flag2)
						{
							infoVn[inVN(ll1[i].array[j])].isNull=0;
						}
					}
				}
			}
			
			/*某项产生式长度能减为0*/
			if (len==0)
			{
				infoVn[inVN(ll1[i].origin)].isNull=1;
				/*删除该非终结符的所有产生式*/
				for (m=0;m<n1;m++)
				{
					if (ll1[i].origin == ll1[m].origin)
					{
						flag[m]=0;
					}
				}
			
			}
		}

		for (i=0;i<numOfVn;i++)
		{
			if ( isModified[i]!=infoVn[i].isNull )
			{
				flag3=1;
				isModified[i]=infoVn[i].isNull;
				//break;
			}
		}
	}
}

/* 计算各非终结符的First集 */
void getFirst(type ll1[],info infoVn[])
{
	int i,j,k,l,m,length,flag1=1;

	/*将各非终结符的FIRST集合初始化为空串*/
	for (i=0;i<numOfVn;i++)
	{
		infoVn[i].firstSet[0]='\0';
	}