自顶向下语法分析通用程序源程序.cpp

编译原理的一个课程设计

#include<stdio.h>
#include<string.h>
#include<iostream.h>
#include<ctype.h>
#include <fstream.h>
class Syntax_analysis
{
	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];
    int  _sto_tax;
	char startchar;
	char keylr;
	char save[1000];     //保存结果到外存储器
	char lie[20];
	int  li;
	char hang[20];
	int  han;
public:
	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()
	{
		int cout=0;
		char c;
		char interim[50];
		int i=0;
        sto_tax=0;
again:
		c=soudocu[cout++];
		while(c!='#')
		{
			if(c!='\n')
			{
				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++)
					{
						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()
	{
		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);		
		}
		else 
		{
		}
		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()
	{
		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;
			}
		}

	}
	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;
				}
			}
		}
	}
	
	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]);

						}
						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;
				}