topdown.cpp

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

#include"stdio.h"
#include"string.h"
#include"iostream.h"
#include"ctype.h"
#include"fstream.h"

class Syntax_analysis
{
 public:
	char stotax[30][20];          //存放文法规则
	char soudocu[1000];           //用于存放打开的文件内容
	int  sto_tax;                 //存放产生式总数
	char firstchars[30];          //某个串的first集(可能有重复)
	int  first_num;               //first集长度
	char followchars[1000];       //存放某个非终结符的follow集(如果有(间接)右递归,可能有较大重复)
	int  follow_num;              //follow集长度
	int  follownumkey;            //用于判断右递归或间接右递归
	char followkey;
	char selectchars[30][30];     //存放每条产生式的select集
	char colec0[30];              //存入所有能推导出0的非终结符
	int  colec0num;               //能推导出0的非终结符个数
	char capital;			      //第一个未被使用的大写字母
	char preanatab[130][130][20]; //存放预测分析表,分别为非终结符(将字母转化为数字)、终结符(将字母转化为数字)、产生式
    char _stotax[30][20];		  //临时的stotax备份
    int  _sto_tax;			      //临时的_sto_tax备份
	char startchar;				  //开始文法符号
	char keylr;
	char save[1000];              //保存结果到外存储器
	char lie[20];
	int  li;
	char hang[20];
	int  han;
	int  ll_key;
	int  input_key;
    Syntax_analysis(){}

	void openfile()               //打开文件
	{
	   input_key=0;
	   int i=0;
	   ifstream infile; 
	   char path[255];
	   cin>>path;
       infile.open(path); 
       if (infile.is_open()) 
	   { 
          while (infile.good()) 
          soudocu[i++]=(char)infile.get(); 
          infile.close(); 
		  soudocu[i]='#';
	   } 
       else 
	   { 
          cout<<"Error opening file"; 
	   } 
	}

	void getin()    //对读取出来的文件内容,推导式分解并保存在stotax数组中
	{
		int cout=0;
		char c;
		char interim[50];
		int i=0;
        sto_tax=0;
again:
		c=soudocu[cout++];
		while(c!='#')
		{
			if(c!='\n')
			{//把一行内容存放在interim数组里
				if(c!=' ') interim[i++]=c;
			    c=soudocu[cout++];
			}
			else
			{
				if(!isupper(interim[0])||interim[1]!=':'||interim[2]!='=')
				{//如果行首不是以大写字母:=这种格式,则输出错误信息
					printf("The Syntax is wrong! please enter again:\n"); 
					i=0;
					goto again;
				}
				else
				{   
					//字符数组加结束符
					interim[i]='\0';
					int m=0;
					for(int j=0;j<strlen(interim);j++)
					{//把后选式进行分解成一个个产生式
					 //如A:=a|b分解成A:=a,A:=b 
						if(interim[j]!='|')
						{
							stotax[sto_tax][m++]=interim[j];
							continue;
						}
						else
						{
                            stotax[sto_tax][m]='\0';
							sto_tax++;
							stotax[sto_tax][0]=stotax[sto_tax-1][0];
							stotax[sto_tax][1]=stotax[sto_tax-1][1];
							stotax[sto_tax][2]=stotax[sto_tax-1][2];
							m=3;
							continue;
						}
					}
					stotax[sto_tax][m]='\0';
					sto_tax++;
					i=0;
					c=soudocu[cout++];
				}
			}
		}
	startchar=stotax[0][0];
	}

	void disp()     //显示方法推导式
	{
		for(int i=0;i<sto_tax;i++)
			cout<<stotax[i]<<endl;
	}

	void get_in()     //输入推导式,并保存stotax数组中
	{
		char c;
		if(input_key==0) c=getchar();
		input_key=1;
		char interim[50];
		int i=0;
        sto_tax=0;
again:
		c=getchar();
		while(c!='#')
		{
			if(c!='\n')
			{
				if(c!=' ') interim[i++]=c;
			    c=getchar();
			}
			else
			{
				if(!isupper(interim[0])||interim[1]!=':'||interim[2]!='=')
				{
					printf("The Syntax is wrong! please enter again:\n"); 
					i=0;
					goto again;
				}
				else
				{   
					interim[i]='\0';
					int m=0;
					for(int j=0;j<strlen(interim);j++)
					{
						if(interim[j]!='|')
						{
							stotax[sto_tax][m++]=interim[j];
							continue;
						}
						else
						{
                            stotax[sto_tax][m]='\0';
							sto_tax++;
							stotax[sto_tax][0]=stotax[sto_tax-1][0];
							stotax[sto_tax][1]=stotax[sto_tax-1][1];
							stotax[sto_tax][2]=stotax[sto_tax-1][2];
							m=3;
							continue;
						}
					}
					stotax[sto_tax][m]='\0';
					sto_tax++;
					i=0;
					c=getchar();
				}
			}
		}
		startchar=stotax[0][0];
		int sav=0;
		save[sav]='\0';
		printf("save it? press 'y' to save or other to continue\n");
		char command[30];
		cin>>command;
		if(!strcmp(command,"y"))
		{
			for(int i=0;i<sto_tax;i++)
			{
				strcat(save,stotax[i]);
				sav=strlen(save);
				save[sav]='\n';
				save[sav+1]='\0';
			}
			save_file(save);		
		}
		char g;
		g=getchar();
	}

	void save_file(char p[])      //保存到外存储器
	{
		char filepath[30];
        cout<<"Please enter the path and file name"<<endl;
		cin>>filepath;
	    ofstream ofs(filepath); 
		ofs.write(p,strlen(p));
     	ofs.close();
	}

	void Delpare()      //消除左递归
	{
		ll_key=0;
		keylr=0;
		//复制推导式数组
		for(int i=0;i<sto_tax;i++) strcpy(_stotax[i],stotax[i]);
		_sto_tax=sto_tax;
		int key;
		char p[30];
		char key_c;
		for(i=0;i<_sto_tax;i++)
		{//消除直接左递归
			key_c=_stotax[i][0];
			if(_stotax[i][0]==_stotax[i][3])
			{//如果存在直接左递归,则消除
				//查找未被使用的大写之母
                findcapital();
	    		for(int j=0;j<_sto_tax;j++)
				{
					if(_stotax[j][0]==key_c)
					{
						keylr=1;
						if(_stotax[j][3]==_stotax[j][0])
						{
							strcpy(&_stotax[j][3],&_stotax[j][4]);
							_stotax[j][strlen(_stotax[j])]=capital;
							_stotax[j][0]=capital;
                            _stotax[j][strlen(_stotax[j])+1]='\0';
							_stotax[_sto_tax][0]=capital;
							_stotax[_sto_tax][1]=':';
							_stotax[_sto_tax][2]='=';
							_stotax[_sto_tax][3]='0';
                            _stotax[_sto_tax][4]='\0';
							_sto_tax++;
						}
						else if(_stotax[j][3]!='0')
						{
							int d;
							d=strlen(_stotax[j]);
							_stotax[j][d]=capital;
                            _stotax[j][d+1]='\0';
						}
					}
				}
			}
		}
		char keyc[30];
		for(i=0;i<_sto_tax;i++)
		{//消除间接左递归
			key=0;
			strcpy(keyc,_stotax[i]);
			if(isupper(_stotax[i][3]))
			{
				for(int j=0;j<=_sto_tax;j++)
				{
		    		if(keyc[0]!=_stotax[j][0])
						if(_stotax[j][0]==keyc[3])
						{
							if(key==0)
							{
    							strcpy(p,&_stotax[i][4]);
	    						strcpy(&_stotax[i][3],&_stotax[j][3]);
		    					strcpy(&_stotax[i][strlen(_stotax[i])],p);
								key=1;
							}
							else
							{
								_stotax[_sto_tax][0]=_stotax[i][0];
								_stotax[_sto_tax][1]=':';
								_stotax[_sto_tax][2]='=';
	    						strcpy(&_stotax[_sto_tax][3],&_stotax[j][3]);
		    					strcpy(&_stotax[_sto_tax][strlen(_stotax[_sto_tax])],p);
								_sto_tax++;
							}
						}
				}
			}
		    for(int n=0;n<_sto_tax;n++)
			{
				key_c=_stotax[n][0];
			    if(_stotax[i][0]==_stotax[i][3])
				{
					keylr=1;
                    findcapital();
	    	    	for(int j=0;j<_sto_tax;j++)
					{
						if(_stotax[j][0]==key_c)
						{
							if(_stotax[j][3]==_stotax[j][0])
							{
								strcpy(&_stotax[j][3],&_stotax[j][4]);
							    _stotax[j][strlen(_stotax[j])]=capital;
						    	_stotax[j][0]=capital;
                                _stotax[j][strlen(_stotax[j])+1]='\0';
						    	_stotax[_sto_tax][0]=capital;
							    _stotax[_sto_tax][1]=':';
						    	_stotax[_sto_tax][2]='=';
						    	_stotax[_sto_tax][3]='0';
                                _stotax[_sto_tax][4]='\0';
						    	_sto_tax++;
							}
						    else if(_stotax[j][3]!='0')
							{
								int d;	
						        d=strlen(_stotax[j]);
							    _stotax[j][d]=capital;
                                _stotax[j][d+1]='\0';
							}
						}
					}
				}
			}
		}
		if(keylr==1)
		{
			printf("该文法有直接或间接左递归,消除左递归后的文法为:\n");
            for(i=0;i<_sto_tax;i++)
			{
				{
		        	printf("%s",_stotax[i]);
		        	printf("\n");
				}
			}
        	for(i=0;i<_sto_tax;i++) strcpy(stotax[i],_stotax[i]);
        	sto_tax=_sto_tax;
		}
	}

	void findcapital()   //查找未被使用的大写字母,把第一个未被使用的大写字母保存在capital中
	{
		int key;
		for(int i=65;i<=90;i++)
		{
			key=0;
			for(int j=0;j<_sto_tax;j++)
			{
				if(_stotax[j][0]==char(i)) key=1;
			}
			if(key==0)
			{
				capital=char(i);
				break;
			}
		}
	}

	void First_Collection(char p[])      //求字符串p的first集,把结果保存在数组firstchars[30]中
	{
		if(islower(p[0])) firstchars[first_num++]=p[0];
		else if(isupper(p[0]))
		{
			for(int i=0;i<sto_tax;i++)
				if(stotax[i][0]==p[0])
					if(islower(stotax[i][3])) firstchars[first_num++]=stotax[i][3];
		    for(i=0;i<strlen(p);i++)
			{
				if(isupper(p[i]))
				{
					char *q;
					for(int n=0;n<sto_tax;n++)
						if(p[i]==stotax[n][0])
						{
							q=&stotax[n][3];
							First_Collection(q);
						}
				    int key=0;
				    for(int j=0;j<colec0num;j++)
					    if(colec0[j]==p[i])
						{
							key=1;
						    break;
						}
				    if(key==0) break;
				}
		    	else if(islower(p[i]))
				{
    				firstchars[first_num++]=p[i];
	    			break;
				}
			}
		}
	}
	
	void Follow_Collection(char p)    //求字符p的follow集,把结果保存在数组followchars中
	{
		if(p==stotax[0][0]) followchars[follow_num++]='#';
		for(int i=0;i<sto_tax;i++)
		{
			for(int j=3;j<strlen(stotax[i]);j++)
				if(p==stotax[i][j])
				{
					if(islower(stotax[i][j+1]))
					{
						followchars[follow_num++]=stotax[i][j+1];
				    	break;
					}
					else if(stotax[i][j+1]=='\0')
					{
						if(follownumkey>=30)   
						//如果follownumkey大于某个值,则可认定求follow集陷入死循环,即有右递归或间接右递归,此时跳出去,终止死循环
						{
							follownumkey=0;
							break;
						}
                        follownumkey++;
						Follow_Collection(stotax[i][0]);
						break;
					}
					else if(isupper(stotax[i][j+1]))
					{
						char *q;
						q=&stotax[i][j+1];
						first_num=0;
						First_Collection(q);
						for(int m=0;m<first_num;m++) followchars[follow_num++]=firstchars[m];
						int key1=0;
						for(int n=j+1;n<strlen(stotax[i]);n++)
						{
							int key2=0;
							for(int r=0;r<colec0num;r++)
								if(stotax[i][n]==colec0[r]) key2=1;
                            if(key2==0)
							{
								key1=1;
								break;
							}
						}
						if(key1==0)
						{
							if(follownumkey>=30)    
							//如果follownumkey大于某个值,则可认定求follow集陷入死循环,即有右递归或间接右递归,此时跳出去,终止死循环
							{
					    		follownumkey=0;
						    	break;
							}
                            follownumkey++;
							Follow_Collection(stotax[i][0]);