ll(1).cpp

学编译原理时写的一个语法分析程序

 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
	{ 
		for(j=0;;j++)
		if(v[j]==p[0])
			break;
		if(i>=0)
		{
			memcpy(first[i],first1[j],strlen(first1[j]));
			first[i][strlen(first1[j])]='\0';
		}
		else
		{
			memcpy(TEMP,first1[j],strlen(first1[j]));
			TEMP[strlen(first1[j])]='\0';
		}
    }
 }
 else                      /*如果右部为符号串*/
 {
	for(j=0;;j++)
	if(v[j]==p[0])
		break;
	if(i>=0)
        merge(first[i],first1[j],2);
	else
		merge(TEMP,first1[j],2);
	for(k=0;k<=length-1;k++)
	{
		empt[0]='\0';
		if(_emp(p[k])==1&&k<length-1)
		{ 
			for(m=0;;m++)
			if(v[m]==right[i][k+1])
				break;
            if(i>=0)
				merge(first[i],first1[m],2);
			else
				merge(TEMP,first1[m],2);
		}
        else if(_emp(p[k])==1&&k==length-1)
		{  
			temp[0]='^';
			temp[1]='\0';
			if(i>=0)
				merge(first[i],temp,1);   
			else
				merge(TEMP,temp,1);
		}
		else if(_emp(p[k])==0)
			break;
	}
 }
}
/*******************************************
 求各产生式左部的FOLLOW
********************************************/
void FOLLOW(int i)
{
 int j,k,m,n,result=1;
 char c,temp[20];
 c=non_ter[i];             /*c为待求的非终结符*/
 temp[0]=c;
 temp[1]='\0';
 merge(fo,temp,1);
 if(c==start)
 {                         /*若为开始符号*/
	temp[0]='#';
	temp[1]='\0';
	merge(follow[i],temp,1);
 }
 for(j=0;j<=count-1;j++)
 {
	if(in(c,right[j])==1)     /*找一个右部含有c的产生式*/
	{
		for(k=0;;k++)
			if(right[j][k]==c)
				break;       /*k为c在该产生式右部的序号*/
        for(m=0;;m++)
			if(v[m]==left[j])
				break;        /*m为产生式左部非终结符在所有符号中的序号*/
			if(k==strlen(right[j])-1)
			{              /*如果c在产生式右部的最后*/
				if(in(v[m],fo)==1)
				{
					merge(follow[i],follow[m],1);
					continue;
                }
				if(F[m]=='0')
				{
					FOLLOW(m);
					F[m]='1';
				}
				merge(follow[i],follow[m],1);
			}
			else 
			{              /*如果c不在产生式右部的最后*/
				for(n=k+1;n<=strlen(right[j])-1;n++)
				{ 
					empt[0]='\0';
					result*=_emp(right[j][n]);
				}
				if(result==1)
				{         /*如果右部c后面的符号串能推出^*/
                    if(in(v[m],fo)==1)
					{           /*避免循环递归*/
						merge(follow[i],follow[m],1);
						continue;
					}
					if(F[m]=='0')
					{
						FOLLOW(m);
						F[m]='1';
					}
					merge(follow[i],follow[m],1);
				}
				for(n=k+1;n<=strlen(right[j])-1;n++)
                    temp[n-k-1]=right[j][n];       
				temp[strlen(right[j])-k-1]='\0';
				FIRST(-1,temp);
				merge(follow[i],TEMP,2);
			}
	}
 }
 F[i]='1';
}

/*******************************************
 判断读入文法是否为一个LL(1)文法
********************************************/
int ll1()
{
 int i,j,length,result=1;
 char temp[50];
 for(j=0;j<=49;j++)
 {                            /*初始化*/
	first[j][0]='\0';
    follow[j][0]='\0';
	first1[j][0]='\0';
	select[j][0]='\0';
	TEMP[j]='\0';
	temp[j]='\0';
	f[j]='0';
	F[j]='0';
 }
 for(j=0;j<=strlen(v)-1;j++)
    first2(j);                /*求单个符号的FIRST集合*/
 printf("\nfirst1:");
 for(j=0;j<=strlen(v)-1;j++)
	printf("%c:%s  ",v[j],first1[j]);
 printf("\nempty:%s",empty);
 printf("\n:::\n_emp:");
 for(j=0;j<=strlen(v)-1;j++)
    printf("%d  ",_emp(v[j]));
 for(i=0;i<=count-1;i++)
    FIRST(i,right[i]);          /*求FIRST*/
 printf("\n");
 for(j=0;j<=strlen(non_ter)-1;j++)
 {                               /*求FOLLOW*/
	if(fo[j]==0)
	{
		fo[0]='\0';
		FOLLOW(j);
	}
 }
 printf("\nfirst:");
 for(i=0;i<=count-1;i++)
    printf("%s ",first[i]);
 printf("\nfollow:");
 for(i=0;i<=strlen(non_ter)-1;i++)
    printf("%s ",follow[i]);
 for(i=0;i<=count-1;i++)
 {                          /*求每一产生式的SELECT集合*/
    memcpy(select[i],first[i],strlen(first[i]));
    select[i][strlen(first[i])]='\0';
	for(j=0;j<=strlen(right[i])-1;j++)
		result*=_emp(right[i][j]);
	if(strlen(right[i])==1&&right[i][0]=='^')
		result=1;
	if(result==1)
	{ 
		for(j=0;;j++)
			if(v[j]==left[i])
				break;
		merge(select[i],follow[j],1);
	}
 }
 printf("\nselect:");
 for(i=0;i<=count-1;i++)
    printf("%s ",select[i]);
 memcpy(temp,select[0],strlen(select[0]));
 temp[strlen(select[0])]='\0';
 for(i=1;i<=count-1;i++)
 {                 /*判断输入文法是否为LL(1)文法*/
    length=strlen(temp);
	if(left[i]==left[i-1])
	{
		merge(temp,select[i],1);
		if(strlen(temp)<length+strlen(select[i]))
			return(0);
	}
	else
	{
		temp[0]='\0';
		memcpy(temp,select[i],strlen(select[i]));
		temp[strlen(select[i])]='\0';
	}
 }
 return(1);
}

/*******************************************
 构造分析表M
********************************************/
void MM()
{
 int i,j,k,m;
 for(i=0;i<=19;i++)
	for(j=0;j<=19;j++)
		M[i][j]=-1;
 i=strlen(termin);
 termin[i]='#';     /*将#加入终结符数组*/
 termin[i+1]='\0';
 for(i=0;i<=count-1;i++)
 {
    for(m=0;;m++)
		if(non_ter[m]==left[i])
			break;      /*m为产生式左部非终结符的序号*/
	for(j=0;j<=strlen(select[i])-1;j++)
	{
		if(in(select[i][j],termin)==1)
		{
			for(k=0;;k++)
				if(termin[k]==select[i][j])
					break;        /*k为产生式右部终结符的序号*/
            M[m][k]=i;
		}
	}
 }
}

/*******************************************
 总控算法
********************************************/
void syntax()
{
 int i,j,k,m,n,p,q;
 char ch;
 char S[50],str[50];
 printf("请输入该文法的句型：");
 scanf("%s",str);
 getchar();
 i=strlen(str);
 str[i]='#';
 str[i+1]='\0';
 S[0]='#';
 S[1]=start;
 S[2]='\0';
 j=0;
 ch=str[j];
 while(1)
 {
	if(in(S[strlen(S)-1],termin)==1)
	{
		if(S[strlen(S)-1]!=ch)
		{
			printf("\n该符号串不是文法的句型！");
            return;
		}
		else if(S[strlen(S)-1]=='#')
		{
            printf("\n该符号串是文法的句型.");
            return;
		}
		else
		{
            S[strlen(S)-1]='\0';
			j++;
			ch=str[j];
		}
	}
	else 
	{   
        for(i=0;;i++)
			if(non_ter[i]==S[strlen(S)-1])
				break;
		for(k=0;;k++)
		{ 
			if(termin[k]==ch)
				break;
			if(k==strlen(termin))
			{
				printf("\n词法错误！");
				return;
			}
		}
		if(M[i][k]==-1)
		{
			printf("\n语法错误！");
			return;
		}
		else
		{
            m=M[i][k];
            if(right[m][0]=='^')
			S[strlen(S)-1]='\0';
			else
			{
				p=strlen(S)-1;
				q=p;
				for(n=strlen(right[m])-1;n>=0;n--)
					S[p++]=right[m][n];
				S[q+strlen(right[m])]='\0';
			}
		}
	}
    printf("\nS:%s str:",S);
	for(p=j;p<=strlen(str)-1;p++)
	printf("%c",str[p]);
	printf(" ");
 }
}

/*******************************************
 一个用户调用函数
********************************************/
void menu()
{
 syntax();
 printf("\n是否继续？(y or n):");
 scanf("%c",&choose);
 getchar();
 while(choose=='y')
  { 
   menu();
  }
}


/*******************************************
 主函数
********************************************/
void main()
{
 int i,j;
 start=grammer(termin,non_ter,left,right);               /*读入一个文法*/
 printf("count=%d",count);
 printf("\nstart:%c",start);
 strcpy(v,non_ter);
 strcat(v,termin);
 printf("\nv:%s",v);
 printf("\nnon_ter:%s",non_ter);
 printf("\ntermin:%s",termin);
 printf("\nright:");
 for(i=0;i<=count-1;i++)
	printf("%s   ",right[i]); 
 printf("\nleft:");
 for(i=0;i<=count-1;i++)
	printf("%c   ",left[i]);            
 if(validity==1)
    validity=judge();
 printf("\nvalidity=%d",validity);
 if(validity==1)
 {
    printf("\n文法有效");
	ll=ll1();
	printf("\nll=%d",ll);
	if(ll==0)
		printf("\n该文法不是一个LL1文法！");
	else
	{
		MM();
        printf("\n");
		for(i=0;i<=19;i++)
			for(j=0;j<=19;j++)
				if(M[i][j]>=0)
					printf("M[%d][%d]=%d ",i,j,M[i][j]);
		printf("\n");
		menu();
	}
 }
}