013chenxiaorong语法分析实验代码.cpp

用VC++实现的编译原理中的语法分析程序,内容详尽具体,可执行程序齐全!

#include<stdio.h>
#include<string.h>
void first(char a[][20],int num[],int i,int k);
void follow(char a[][20],int num[],int i,int k);
void fun(int num[],int i);
void fun0(int num[],int i);
void move(char ch[]);
int m;
char FIRST[26][20],FOLLOW[26][20];//用来存放非终结符的FIRST集和FOLLOW集
main()
{
	char  a[26][20],b[20],chnT[20]; //chnT用来存放终结符

	int i,j,k=0,num[10],r;
	int len;
	for(i=0;i<26;i++)
	{
		a[i][0]='\0';
	    FIRST[i][0]='\0';
		FOLLOW[i][0]='\0';
	}
    printf("LL(1)文法分析实验\n");
    printf("制作者：05软件：013陈小荣 006冯金花 097杨德勇\n");
	printf("\n\n");
	printf("*****请输入文法的条数:****\n  r=");
	scanf("%d",&r);
	//接受文法
	printf("输入文法表达式(遇到像T与T'这样的字母,请将T'换成其他大写字母再输入):\n");
	for(j=0;j<r;j++)  
	{
		scanf("%s",b);
		num[k]=b[0]-65;
		k++;
    	for(i=0;i<strlen(b);i++)
			a[b[0]-65][i]=b[i];	    
        a[b[0]-65][i]='\0';
	}
	printf("******显示文法:******\n");
    for(i=0;i<k;i++)
	   printf("%s\n",a[num[i]]);
	//将文法中出现的所有非终结符存放在字符串chnT中，方便以后使用
	len=0;
    for(i=0;i<k;i++)
		for(j=3;j<strlen(a[num[i]]);j++)
			if((a[num[i]][j]<'A'||a[num[i]][j]>'Z')&&a[num[i]][j]!='|'&&a[num[i]][j]!='e')
			{
				chnT[len]=a[num[i]][j];
				len++;
			}
	chnT[len]='#';
	len++;
	chnT[len]='\0';
	//定义分析表的矩阵
	char M[20][26][10];
	int error; //定义出错标志
	for(i=0;i<len;i++)
		for(j=0;j<k;j++)
			 strcpy(M[i][num[j]],"ERROR");	
    //求FIRST集
	for(i=0;i<k;i++)
	{
		m=0;
		first(a,num,i,3); 
        fun(num,i);         //处理集合中相同的终结符
	}
	//处理FIRST相同的集合	
	for(i=k-1;i>=0;i--)
	{ 
		len=strlen(FIRST[num[i]]);
		if(a[num[i]][3]>='A'&&a[num[i]][3]<='Z')
			for(j=len;FIRST[a[num[i]][3]-65][j-len]!='\0';j++)
                FIRST[num[i]][j]=FIRST[a[num[i]][3]-65][j-len];
	}
	//输出FIRST集
    printf("********输出FIRST集合:********\n");
	for(i=0;i<k;i++)
       printf("%c: %s \n",a[num[i]][0],FIRST[num[i]]);

    for(i=0;i<k;i++)
	{
		m=0;
		for(j=3;j<strlen(a[num[i]]);j++)
		     follow(a,num,i,j);
	}
	//对于产生式 将FIRST 加到FOLLOW
	for(i=0;i<k;i++)
	{
		for(j=3;j<strlen(a[num[i]]);j++)
            if(a[num[i]][j]>='A'&&a[num[i]][j]<='Z'&&a[num[i]][j+1]>='A'&& a[num[i]][j+1]<='Z')
				strcat(FOLLOW[a[num[i]][j]-65],FIRST[a[num[i]][j+1]-65]);
	}
    //对于FOLLOW相同的,将已求出来的赋给另外一个
	for(i=0;i<k;i++)
	{
		if(a[num[i]][strlen(a[num[i]])-1]>='A'&&a[num[i]][strlen(a[num[i]])-1]<='Z')
			strcat(FOLLOW[a[num[i]][strlen(a[num[i]])-1]-65],FOLLOW[num[i]]);
		for(j=3;j<strlen(a[num[i]]);j++)
            if(a[num[i]][j]>='A'&&a[num[i]][j]<='Z'&&a[num[i]][j+1]>='A'&& a[num[i]][j+1]<='Z')
				strcat(FOLLOW[a[num[i]][j]-65],FOLLOW[a[num[i]][j+1]-65]);
	}
	for(i=0;i<k;i++)
		FOLLOW[num[i]][strlen(FOLLOW[num[i]])]='#';
	//消除FOLLOW中的e
	for(i=0;i<k;i++)
	{
		len=strlen(FOLLOW[num[i]]);
		for(j=0;j<len;j++)
			if(FOLLOW[num[i]][j]=='e')
			{
				for(int t=j;t<len;t++)
			    	FOLLOW[num[i]][t]=FOLLOW[num[i]][t+1];
				len--;
			}
	}
	for(i=0;i<k;i++)
		fun0(num,i);//消除FOLLOW中相同的终结符       
    printf("********输出FOLLOW集合:********\n");
	for(i=0;i<k;i++)
       printf("%c: %s\n",a[num[i]][0],FOLLOW[num[i]]);
    //构造分析表
	len=strlen(chnT);
    for(j=0;j<k;j++)
		for(i=0;i<len;i++)
		{
			for(r=0;r<strlen(FIRST[num[j]]);r++)
				if(chnT[i]==FIRST[num[j]][r])
				{
					error=0;
					for(int s=3;s<strlen(a[num[j]]);s++)
					    if(chnT[i]==a[num[j]][s])
						{
							M[i][num[j]][0]=a[num[j]][0];
                			M[i][num[j]][1]='-';
	                		M[i][num[j]][2]='>';
							M[i][num[j]][3]=chnT[i];
							if(a[num[j]][s+1]!='|'&&a[num[j]][s+1]!='\0')
							{	
								for(m=s+1;a[num[j]][m]!='|';m++)
									M[i][num[j]][m]=a[num[j]][m];
							    M[i][num[j]][m]='\0';
							}
                            else 
                                 M[i][num[j]][4]='\0';
							error=1;
							break;
						}
					if(error!=1)
					{
						M[i][num[j]][0]=a[num[j]][0];
                		M[i][num[j]][1]='-';
	                	M[i][num[j]][2]='>';
						for(int s=3;s<strlen(a[num[j]])&&a[num[j]][s]!='|';s++)
						   M[i][num[j]][s]=a[num[j]][s];
						M[i][num[j]][s]='\0';
					}
				}
			for(r=3;r<strlen(a[num[j]]);r++)
			{
				if(a[num[j]][r]=='e')
					for(int s=0;s<strlen(FOLLOW[num[j]]);s++)
						if(chnT[i]==FOLLOW[num[j]][s])
						{
							M[i][num[j]][0]=a[num[j]][0];
                			M[i][num[j]][1]='-';
	                		M[i][num[j]][2]='>';
							M[i][num[j]][3]='e';
							M[i][num[j]][4]='\0';
						}
			}
		}
	printf("********输出所有的终结符:********\n");
	printf("%s\n",chnT);
	printf("********输出分析表:********\n");
	for(j=0;j<k;j++)
	{	
		for(i=0;i<len;i++)
			printf("%s  ",M[i][num[j]]);
		printf("\n");
	}
	//构造分析器
	char cin[10],chr[20];  //cin表示符号栈,chr表示输入串
	printf("****请输入要分析的句子:\n");
	scanf("%s",chr);
	len=strlen(chr);
	chr[len]='#';
	chr[len+1]='\0';
	for(i=0;i<10;i++)
		cin[i]='\0';
	cin[0]='#';
	cin[1]=a[num[0]][0];
	printf("%s %s\n",cin,chr);
	len=strlen(chnT);
	m=0;
	error=0;
    while(chr[0]!=cin[0]||cin[1]!='\0')
	{
		if(chr[0]==cin[strlen(cin)-1])
		{
			move(chr);
			cin[strlen(cin)-1]='\0';
			printf("%s %s\n",cin,chr);
		}
    	for(i=0;i<len;i++)
			if(chnT[i]==chr[0]){
				error=0;
				break;
			}
	    if(cin[strlen(cin)-1]=='#'){
		    printf("匹配不成功!\n");
			error=1;
			goto loop;
		
		}
		for(j=0;j<k;j++)
		{
			if(a[num[j]][0]!=cin[strlen(cin)-1])continue;//该语句的功能是让以下句子处理符号栈栈顶元素
			if(M[i][num[j]][1]=='-')
			{
				if(M[i][num[j]][3]=='e')
				{
					cin[strlen(cin)-1]='\0';
					printf("步骤%d用到的产生式:%s\n",m,M[i][num[j]]);
					m++;
					break;
				}
				int t=strlen(cin)-1;
				printf("查看t是不是指向符号栈的栈顶元素:%c\n",cin[t]);
				printf("步骤%d用到的产生式:%s\n",m,M[i][num[j]]);
				m++;//用来控制执行到哪第几步
				for(int s=strlen(M[i][num[j]])-1;s>2;s--,t++)	
					cin[t]=M[i][num[j]][s];			
				printf("%s %s\n",cin,chr);
			}
		}
	   loop: if(error==1){
		        printf("输出ERROR,该语句不属于LL(1)文法!\n");
		        break;
			 }
	}
	if(cin[0]==chr[0])printf("分析成功!\n");
}
//函数功能求非终结符的FIRST集
void first(char a[][20],int num[],int i,int k)
{
	if(a[num[i]][k]<'A' || a[num[i]][k]>'Z')
	{
		FIRST[num[i]][m]=a[num[i]][k];
		m=m+1;
	}
	for(int j=k+1;j<strlen(a[num[i]]);j++)//  a[num[i]][j]!='\0'			
    	if(a[num[i]][j]=='|')first(a,num,i,j+1);	
} 
//求FOLLOW集合
void follow(char a[][20],int num[],int i,int k)
{ 
	//if(m==0){FOLLOW[num[i]][m]='#';m++;}
	if(a[num[i]][k]>='A'&&a[num[i]][k]<='Z'&&(a[num[i]][k+1]<'A' 
		|| a[num[i]][k+1]>'Z')&&a[num[i]][k+1]!='|')
	{
		FOLLOW[a[num[i]][k]-65][m]=a[num[i]][k+1];
		m++;
	}
}
//这个函数的功能是消除FIRST集合中重复的终结符
void fun(int num[],int i)
{
	int k,j;
	for(k=0;k<m-1;k++)
		for(j=k+1;j<m;j++)
			if(FIRST[num[i]][k]==FIRST[num[i]][j])
			{
				FIRST[num[i]][j]='\0';
				m--;
			}
}
//这个函数的功能是消除FOLLOW集合中重复的终结符
void fun0(int num[],int i)
{
	int k,j,len,t;
    len=strlen(FOLLOW[num[i]]);
	for(k=0;k<len-1;k++)
		for(j=k+1;j<len;j++)	
			if(FOLLOW[num[i]][k]==FOLLOW[num[i]][j])
			{   
				for(t=j;t<len;t++)
			    	FOLLOW[num[i]][t]=FOLLOW[num[i]][t+1];
				len--;
				j=k;
			}
}
void move(char ch[])
{
	int i=0;
	for(;i<strlen(ch);i++)
		ch[i]=ch[i+1];
}