ll(11).cpp

LL（1）方法

void FIRST(int i,char *p)
{
	int length;
	int j,k,m;
	char temp[20];
	length=strlen(p);
	if(length==1)                  /*如果alw我右anb部为wfn单个符号*/
	{
		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_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*/
	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 error()
{

	printf("\n你输入的句子不符合当前的文法！\n请确认后重新输入一遍。\n");
	exit(1);
}

void main()
{
	int i,j,x;
	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)
	{
        ll=ll1();
		printf("\nll=%d\n相应的LL(1)分析表如下： \n",ll);
		if(ll==0)
			printf("\n该文法不是一个LL1文法！");
		else
		{
		    MM();
		    for(x=0;x<=strlen(termin);x++)
                  	 printf("\t%c",termin[x]);
                 	 printf("\n");
                         
		    for(i=0;i<=strlen(non_ter);i++)
		      	{  
		      		printf("%c",non_ter[i]);
		      		for(j=0;j<=19;j++)
		        	{
		        	 	
			        	if(M[i][j]>=0)
				        {
				        	printf("\t%s",right[M[i][j]]);
				        	continue;
				        }
				        printf("\t");
					}
				 printf("\n");
				}		
		}

	}
	else  exit(1);
	char str[15],tmp;
	NODE *tt;
	
	int tno=0,flag=0,rno=0;
aa:	printf("**********句子分析开始*******************\n");
	printf("请输入句子(以'#'结束)：");
	gets(str);
	SNODE   *T;
	T=(SNODE   *)malloc(sizeof(SNODE)); 
	tt=(NODE   *)malloc(sizeof(NODE)); 
	InitStack(T);
	StackPush(T,start);
	printf("\n");
	printf("\t\t\t输入串%s的分析过程\n",str);
	printf("符号串\t当前输入符号\t输入串\t\t说明\n");
	for(i=0;i<15;i++)
	{
		PrintStack(T);
		printf("\t%c\t\t%s\t   ",str[i],str+i+1);
		StackPop(T,tt);
		tmp=tt->data;
		//printf("%c\t",tmp);
		if(in(tmp,termin))
		    {
				//printf("termin.");
					if(tmp=='#'&&str[i]=='#')	
					break; 				
					else if(tmp==str[i])
		             {
					printf("匹配，弹出%c 并读入下一个字符.\n",tmp);
		    		continue;
					}
		    	else error();
		    }
		else 	     
				{	
					    	  for(j=0;j<strlen(non_ter);j++)
							 	  if(tmp==non_ter[j])
								  {flag=1;
								  break;}
							if(flag==1)
							{	flag=0;
								for(tno=0;tno<strlen(termin);tno++)
									  if(str[i]==termin[tno])
									  {flag=1;
									  break;}
							}
								 if(M[j][tno]>=0&&flag==1)
								 {      rno=M[j][tno];
								 
										if(right[rno][0]=='^')
											printf("由%c->^仅弹出栈%c\n",tmp,tmp);
										else
										printf("弹出%c,并将%c->%s反序压栈.\n",tmp,tmp,right[rno]);
										if(right[rno][0]!='^')
										for(tno=strlen(right[rno])-1;tno>=0;tno--)
										{	
											//printf("%c\t",right[rno][tno]);
											 StackPush(T,right[rno][tno]); 
											
										}
										i--;
										//printf("%s为非终结符\n",right[rno]);
									    
								 }
								else	  error();
							
					
						
								
						}
		     		      	

	//system("PAUSE");
	}
	printf("成功匹配置！\n");
	free(T);
	free(tt);
	system("PAUSE");
    printf("是否要继续分析句子?(Y|N):  ");
	scanf("%c",&tmp);
	getchar();
	if(tmp=='Y')
		goto aa;

	system("PAUSE");
}