topdown.cpp

编译原理中的自顶向下的语法分析

						}
						break;
					}
				}
		}
	}

	void Select_Collection()       //求每条产生式的select集,存放在数组selectchars[30][30]中
	{
		for(int i=0;i<sto_tax;i++)
		{
			int select_num=0;
			int key1=0;
			int key2=0;
			for(int j=3;j<strlen(stotax[i]);j++)
			{
				for(int m=0;m<colec0num;m++)
					if(colec0[m]==stotax[i][j]) key1=1;
                if(key1==0)
				{
					key2=1;
					break;
				}
			}
			if(stotax[i][3]=='0')      //产生式右边为0,则把follow集加入select集中
			{
				follownumkey=0;
				follow_num=0;
				Follow_Collection(stotax[i][0]);
				for(int r=0;r<follow_num;r++)
				{
					int key5=0;
					for(int v=0;v<select_num;v++)
						if(followchars[r]==selectchars[i][v]) key5=1;
					if(key5==0) selectchars[i][select_num++]=followchars[r];
				}
                selectchars[i][select_num]='\0';
				break;
			}
			if(key2==0)     //表示产生式右边能推出0,则把first集和follow集加入select集中
			{
				first_num=0;
				First_Collection(&stotax[i][3]);
				for(int q=0;q<first_num;q++)
				{
					int key3=0;
					for(int s=0;s<select_num;s++)
						if(firstchars[q]==selectchars[i][s]) key3=1;
					if(key3==0) selectchars[i][select_num++]=firstchars[q];
				}
				follownumkey=0;
				follow_num=0;
				Follow_Collection(stotax[i][0]);
				for(int p=0;p<follow_num;p++)
				{
					int key4=0;
					for(int t=0;t<select_num;t++)
						if(followchars[p]==selectchars[i][t]) key4=1;
					if(key4==0)
						selectchars[i][select_num++]=followchars[p];
				}
                selectchars[i][select_num]='\0';
			}
			else    //表示产生式右边不能推出0,则把first集加入select集中
			{
				first_num=0;
				First_Collection(&stotax[i][3]);
				for(int q=0;q<first_num;q++)
				{
					int key3=0;
					for(int s=0;s<select_num;s++)
						if(firstchars[q]==selectchars[i][s]) key3=1;
					if(key3==0) selectchars[i][select_num++]=firstchars[q];
				}
				selectchars[i][select_num]='\0';
			}
		}  
	}

	void Estab_preanatab()    //创建预测分析表
	{
		int i,j;
        //如果分析表中有一项有两个产生式,则可确认该文法为非LL(1)文法,也不能改写为LL(1)文法,不能进行确定的自顶向下分析
		for(i=0;i<130;i++)
			for(j=0;j<130;j++)
				for(int m=0;m<20;m++)
					preanatab[i][j][m]='$';   //初始化分析表,以便重复建立
		for(i=0;i<sto_tax;i++)
		{
			for(j=0;j<strlen(selectchars[i]);j++)
			{
				int p=int(stotax[i][0]);
				int q=int(selectchars[i][j]);
				if(preanatab[p][q][0]=='$') strcpy(preanatab[p][q],stotax[i]);
				else
				{
					printf("该文法为非LL(1)文法,也不能改写为LL(1)文法,不能进行确定的自顶向下分析!\n");
                    ll_key=1;
					goto notll1;
				}
			}
		}
notll1:{}
	}

	void dispselect()     //显示选择
	{
		for(int i=0;i<sto_tax;i++)
		{
			cout<<"SELECT("<<stotax[i]<<")={";
			cout<<selectchars[i];
			cout<<"}"<<endl;
		}
	}

	void base_()
	{
		li=0;
		han=0;
		for(int q=0;q<20;q++)
		{
			lie[q]=' ';
			hang[q]=' ';
		}
		for(int i=0;i<130;i++)
		{
			for(int j=0;j<130;j++)
				if(preanatab[i][j][0]!='$')
				{
					int key1=1;
					for(int m=0;m<li;m++)
						if(lie[m]==char(j)) key1=0;
					if(key1) lie[li++]=char(j);
 	        		int key2=1;
	        		for(int n=0;n<han;n++)
	    	    		if(hang[n]==char(i)) key2=0;
		        	if(key2)
		        		hang[han++]=char(i); 
				}
		}
	}

	void disp_table()     //打印预测分析表
	{
	    base_();
		printf("预测分析表为:\n");
		cout<<"       ";
		for(int i=0;i<li;i++)  cout<<lie[i]<<"         ";
		cout<<endl;
		for(i=0;i<han;i++)
		{
			printf("%-5c",hang[i]);
			for(int j=0;j<li;j++)
				if(preanatab[int(hang[i])][int(lie[j])][0]!='$')
	    			printf("%-10s",preanatab[int(hang[i])][int(lie[j])]);
				else 
					printf("          ");
			cout<<endl;
		}
	}

	void Analyse_course()      //分析过程
	{
		char inputchars[100];  //存放要分析的字符
		int  inpoint;          //输入串指针
		char anastack[100];    //分析栈
		int  anapoint;         //分析栈指针
		int  i=1;
again:
		anastack[0]='#';
		anastack[1]=startchar;
		anastack[2]='\0';
		anapoint=1;
		printf("请输入要分析的字符串:\n");
   		char c=getchar();
        inpoint=0;
		int key=0;
		while(c!='#')
		{
			if(isupper(c)) key=1;
			inputchars[inpoint++]=c;
			c=getchar();
		}
		if(key==1)
		{
			printf("输入的字符串不能有大写字母:\n");
			goto again;
		}
		inputchars[inpoint++]='#';
		inputchars[inpoint]='\0';
		inpoint=0;
		printf("步骤　分析栈　　     (栈顶符号，当前输入符)　    剩余输入串　   所用产生式\n");
		while(!(anastack[anapoint]=='#' && inputchars[inpoint]=='#'))
		{ 
			if(anastack[anapoint]!=inputchars[inpoint])
			{
				if(preanatab[int(anastack[anapoint])][int(inputchars[inpoint])][0]!='$')
				{
					if(preanatab[int(anastack[anapoint])][int(inputchars[inpoint])][3]=='0')
					{
			    		printf("%-6d",i);
				    	printf("%-15s",anastack);
			    		printf("     (%c,%c)   查表",anastack[anapoint],inputchars[inpoint]);
			    		printf("%20s",&inputchars[inpoint]);
			     		printf("      %s",preanatab[int(anastack[anapoint])][int(inputchars[inpoint])]);
			    		printf("\n");
			    		i++;
						anastack[anapoint]='\0';
						anapoint--;
					}
					else
					{
			    		printf("%-6d",i);
				    	printf("%-15s",anastack);
			    		printf("     (%c,%c)   查表",anastack[anapoint],inputchars[inpoint]);
			    		printf("%20s",&inputchars[inpoint]);
			     		printf("      %s",preanatab[int(anastack[anapoint])][int(inputchars[inpoint])]);
			    		printf("\n");
			    		i++;
			    		char s[30];
			    		strcpy(s,preanatab[int(anastack[anapoint])][int(inputchars[inpoint])]);
                        for(int j=strlen(s)-1;j>=3;j--)
		    				anastack[anapoint++]=s[j];
			    		anastack[anapoint]='\0';
				    	anapoint--;
					}
				}
				else
				{
					printf("该输入串不是文法的句子!\n");
					goto nosent;
				}
			}
			else
			{
				printf("%-6d",i);
				printf("%-15s",anastack);
				printf("     (%c,%c)  %c匹配",anastack[anapoint],inputchars[inpoint],inputchars[inpoint]);
                inpoint++;
				printf("%20s",&inputchars[inpoint]);
				printf("\n");
				anastack[anapoint]='\0';
				anapoint--;
				i++;
			}
		}
		printf("%-6d",i);
		printf("%-15s",anastack);
		printf("     (%c,%c)  成功接收",anastack[anapoint],inputchars[inpoint],inputchars[inpoint]);
		printf("%17s",&inputchars[inpoint]);
		printf("\n");
nosent:{}
	}

	void deduce0_colec()       //将所有能推导出0的非终符放在数组colec0[30]中
	{
		colec0num=0;
		char d0colec[30][20];
		for(int i=0;i<sto_tax;i++) strcpy(d0colec[i],stotax[i]);
		for(i=0;i<sto_tax;i++)
			if(stotax[i][3]=='0') colec0[colec0num++]=stotax[i][0];
		int key1;
next:
		key1=0;
		for(i=0;i<sto_tax;i++)
		{
			d0colec[i][0]=stotax[i][0];
			d0colec[i][1]=stotax[i][1];
			d0colec[i][2]=stotax[i][2];
			for(int j=3;j<strlen(d0colec[i]);j++)
				for(int m=0;m<colec0num;m++)
					if(d0colec[i][j]==colec0[m])
					{
						d0colec[i][j]='0';
						key1=1;
					}
		}
		int key2=0;
		if(key1==1)
		{
			for(i=0;i<sto_tax;i++)
			{
				for(int j=3;j<strlen(d0colec[i]);j++)
					if(d0colec[i][j]!='0')
					{
						key2=1;
						break;
					}
				if(key2==0) colec0[colec0num++]=d0colec[i][0];
			}
			goto next;
		}
	}

	void dispfirst()     //显示First集
	{
fi_again:
		first_num=0;
		cout<<"请输入字符串,以求该串的First集,长度不小于1"<<endl;
        char p[20];
		cin>>p;
        First_Collection(p);
		cout<<"FIRST ( "<<p<<" )={ ";
		for(int i=0;i<first_num;i++)
		{
			int key=1;
			for(int j=0;j<i;j++)
				if(firstchars[j]==firstchars[i]) key=0;
			if(key) cout<<firstchars[i];
		}
		cout<<"}";
		cout<<endl;
		cout<<"would you try another? press y to try again,other to exit"<<endl;
		char c;
		cin>>c;
		if(c=='y') goto fi_again;
	}

	void dispfollow()
	{
fo_again:
		follow_num=0;
		cout<<"请输入一个非终结符"<<endl;
        char p;
		cin>>p;
        Follow_Collection(p);
		cout<<"FOLLOW ( "<<p<<" )={ ";
		for(int i=0;i<follow_num;i++)
		{
			int key=1;
			for(int j=0;j<i;j++)
				if(followchars[j]==followchars[i])
					key=0;
			if(key)
	    		cout<<followchars[i];
		}
		cout<<"}";
		cout<<endl;
		cout<<"would you try another? press y to try again,other to exit"<<endl;
		char c;
		cin>>c;
		if(c=='y') goto fo_again;
	}
};

void main()
{
	Syntax_analysis s;
	printf("=======================自顶向下语法分析器=====================================\n");
	printf("适应的文法类型:\n");
	printf("1.一切LL(1)文法\n");
    printf("2.含有直接左递归但可以转化为LL(1)文法的文法\n");
	printf("3.含有间接左递归但可以转化为LL(1)文法的文法\n\n");
	printf("说明:\n");
	printf("1.文法表达方式:\n");
    printf("  例如:S:=Aa|Bb,其中空串用数字0代替,每输入一个表达式换行写下一表达式\n");
	printf("2.文法输入结束后,换行再按'#'结束\n");
	printf("3.需要输入命令来执行所需要的功能\n\n");
    printf("命令说明:\n");
    printf("open---------从外存储器打开某文法\n");
	printf("input--------从键盘输入文法\n");
	printf("lltab--------查看预测分析表\n");
	printf("select-------查看每条产生式的SELECT集\n");
    printf("first--------求所输串的FIRST集\n");
	printf("follow-------求所输非终结符的FOLLOW集\n");
	printf("ll-----------对某个输入句子进行分析\n");
	printf("exit---------退出程序\n");
    printf("------------------------------------------------------------------------------\n\n");
	int key=0;
	int _key=0;
entercmd:
	char cmd[30];
	printf("cmd>>");
	cin>>cmd;
	if(!strcmp(cmd,"open"))
	{
		if(key==0) _key=1;
		key=1;
		cout<<"请输入文件所在路径和文件名:"<<endl;
		s.openfile();
		s.getin();
		s.disp();
    	s.Delpare();
    	s.deduce0_colec();
    	s.Select_Collection();
        s.Estab_preanatab();
	}
    else if(!strcmp(cmd,"input"))
	{
		if(key==1) s.input_key=0;
		_key=1;
		key=1;
		cout<<"请输入文法,以'#'结束:"<<endl;
    	s.get_in();
    	s.Delpare();
    	s.deduce0_colec();
    	s.Select_Collection();
        s.Estab_preanatab();
	}
    else if(!strcmp(cmd,"ll"))
	{
		char c;
		if(_key==0) c=getchar();
		_key=0;
		if(key==1)
		{ 
    		if(s.ll_key==0) s.Analyse_course();
	    	else printf("该文法为非LL(1)文法,也不能改写为LL(1)文法,不能进行确定的自顶向下分析!\n");
 		}
		else printf("您还没打开或输入文法!\n");
		s.input_key=1;
	}
	else if(!strcmp(cmd,"lltab"))
	{
		if(key==1) s.disp_table();
		else printf("您还没打开或输入文法!\n");
		s.input_key=1;
	}
	else if(!strcmp(cmd,"select"))
	{
		if(key==1) s.dispselect();
		else printf("您还没打开或输入文法!\n");
		s.input_key=1;
	}
	else if(!strcmp(cmd,"first"))
	{
		if(key==1) s.dispfirst();
		else printf("您还没打开或输入文法!\n");
		s.input_key=1;
	}
	else if(!strcmp(cmd,"follow"))
	{
		if(key==1) s.dispfollow();
		else printf("您还没打开或输入文法!\n");
		s.input_key=1;
	}
	else if(!strcmp(cmd,"exit")) goto exitpro;
	else printf("the cmd is not exist!\n");
	goto entercmd;
exitpro:{}
}