mylex.cpp

编译器中词法分析部分

		{
			bool find=false;
			for(int j1=0;j1<front_state[MAX-1];j1++)
			{
				if(front_state[j1]==accept_state[j2])
				{
					style1=final_style[j2];
					find_final=true;
					find=true;
					break;
				}
			}
			if(find==true) break;
		}

		if(find_final) 
		{//是终态
			DFA[count_DFA][funct.size()]=1;//将判断结果放在表中
			fin_sty[count_DFA]=style1;
		}
		else
		{//不是终态
			DFA[count_DFA][funct.size()]=0;
		}

		for(int h2=0;h2<num_of_funct;h2++)	
		{//循环记录的字符集
			vector <int> state_other;
			if(!state_other.empty())
				state_other.clear();
			num_of_state=0;//初始化新一个状态集合的个数
			for(int h1=0;h1<front_state[MAX-1];h1++)
			{//对前一集合中的每个状态遍历，以产生新的状态
				pnode pointer=list[front_state[h1]];
				while(pointer!=NULL)
				{
					if(pointer->arc==funct[h2])
					{										
						//要判断pointer->target是否已经存在
						bool tar=true;
						for(int ta=0;ta<num_of_state-1;ta++)
						{//排除重复的
							if(pointer->target==state[index][ta])
							{
								tar=false;
								break;
							}
						}
						if(tar==true)
						{
							state[index][num_of_state]=pointer->target;
							num_of_state++;
							closure_null('@',state[index],pointer->target,num_of_state);
						}
					}
					pointer=pointer->next;
				}
			}
			state[index][MAX-1]=num_of_state;//将该状态所对应的状态数放入该数组的最后元素
			
			for(int h3=0;h3<num_of_state;h3++)
			{//将的到的新状态放入vector中排序
				state_other.push_back(state[index][h3]);
			}	
			sort(state_other.begin(),state_other.end());
			for(int h3=0;h3<num_of_state;h3++)
			{//将排序后的状态重新放回数组state[][]中
				state[index][h3]=state_other[h3];
			}		

			//判断该状态集合是否已经存在
			int repeat_state=-1;//存放重复的是哪个状态
			bool exit=1;
			for(int j1=0;j1<index;j1++)
			{
				if(state[j1][MAX-1]==num_of_state)
				{
					for(int j2=0;j2<num_of_state;j2++)
					{
						if(state[index][j2]!=state[j1][j2])
						{	
							break;
						}
						if(j2==num_of_state-1)
						{
							exit=0;
							repeat_state=j1;
							j1=index;//退出
						}
					}			
				}
				else
				{
					continue;	
				}				
			}
	
			if( exit )
			{//将不重复的入队
				if(num_of_state!=0)//空状态不入队
					state_convert.push(state[index]);

				if(num_of_state!=0)
				{//如果包含NFA中的终态		
					DFA_state++;//状态数加一
					DFA[count_DFA][h2]=DFA_state;			
				}
				else
				{
					index--;
				}
				index++;
			}
			else
			{//如果该状态是重复的状态		  
				DFA[count_DFA][h2]=repeat_state;	
			}
		}
		count_DFA++;//每次每个节点 经过所有的funct以后 节点数才加一
	}
/**********测试DFA是否正确***********************************/
	/*
	out<<"输出DFA的结果"<<endl;
	//cout<<"输出DFA的结果"<<endl;
	for(int i=0;i<count_DFA;i++)
	{
		for(int j=0;j<=funct.size();j++)
			out<<DFA[i][j]<<" ";
		out<<fin_sty[i]<<endl;
		out<<endl;
	}*/
	
/***************************DFA最小化过程********************************/
	int *min_state=new int [count_DFA];
	int count=2;
	for(int i=0;i<count_DFA;i++)
	{//初始时终态、非终态存入数组
		if(DFA[i][funct.size()]==1)
			min_state[i]=1;
		else
			min_state[i]=0;
	}

	int num=0;
	while(num!=count)
	{//当没有新状态产生时结束
		num=count;
		bool ch_count=false;
		int temp_count=0;//从0到count开始对每个集合拆分
		while(temp_count<num)
		{		
			for(int i=0;i<funct.size();i++)
			{
				bool b=true;
				int temp_state;	
				for(int j=0;j<count_DFA;j++)
				{
					if(min_state[j]!=temp_count)
						continue;
					else
					{
						if(b==true)
						{//取比较因子
							temp_state=j;
							b=false;
							continue;
						}
						else
						{						
							if(min_state[DFA[j][i]]!=min_state[DFA[temp_state][i]])
							{//如果经转换函数后不一样	，则划分				
								ch_count=true;
								min_state[j]=count;
							}
						}
					}			
				}	
			}
			if(temp_count<num)//依次划分每个集合，相同的集合，有相同的min_state[]值
				temp_count++;
			if(ch_count==true)
			{	//当有新状态产生时count加一
				count++;
				ch_count=false;
			}
		}
			
	}
	/*********************检测最小化的正确性***************************/
    /*out<<"输出最小化DFA的结果"<<endl;  
	for(int i=0;i<count_DFA;i++)
	{
		out<<min_state[i]<<" ";
	}
	out<<endl;*/
	/****************************************************************/
	//将多余状态删除并重新构造DFA
	int num_of_DFA=count_DFA;//DFA的节点数
	int num_of_min=count;//最小化DFA的节点数
	int index_of_min=0;//最小化DFA重新编号
	char *min_final_style=new char [num_of_min];//存放终态的类型
	int **min_DFA = new int* [num_of_min];//存放最小化后的结果的表
	for(int i=0;i<num_of_min;i++)
	{
		min_DFA[i]=new int [funct.size()+1];
	}
	
	bool *b_dfa=new bool [count_DFA];//用来存放转换时该行是否赋值给min_DFA，
	                                 //若为true则赋值
	int *delete_state=new int [count_DFA];//存放要删除元素该被哪个元素替换
	for(int i=0;i<num_of_DFA;i++)//初始化
		delete_state[i]=-1;

	
	
	int temp_of_state=0;
	for(int i=0;i<num_of_min;i++)
	{
		bool b=true;
		for(int j=0;j<count_DFA;j++)
		{		
			if(min_state[j]==i)
			{
				if(b==true)
				{
					b=false;
					b_dfa[j]=true;
					delete_state[j]=temp_of_state;
					
				}
				else
				{
					b_dfa[j]=false;
					delete_state[j]=temp_of_state;//被删除元素被替换元素赋值
				}
			}
		}
		if(b==false)
			temp_of_state++;	
	}
    
	num_of_min=temp_of_state;//重新给最小化DFA的节点数赋值

	//检测状态重新编号是否正确
	/*for(int i=0;i<count_DFA;i++)
		cout<<delete_state[i]<<" ";
	cout<<endl;*/

	//for(int i=0;i<count_DFA;i++)
		//cout<<b_dfa[i]<<" ";
	/**********复制并替换多余状态************/
	int temp_min=0;	
	for(int i=0;i<count_DFA;i++)
	{//将DFA中非删除状态复制到min_DFA中
		bool b_copy=true;
		if(b_dfa[i]==true)
		{		
			for(int j=0;j<=funct.size();j++)
			{
				if(j<funct.size())
				{
					//若到达状态需被删除则修改为替换状态
					if(DFA[i][j]!=-1)
						min_DFA[temp_min][j]=delete_state[DFA[i][j]];
					else
						min_DFA[temp_min][j]=-1;
				}
				else
					min_DFA[temp_min][j]=DFA[i][j];
				b_copy=false;
			}
			if(min_DFA[temp_min][funct.size()]==1)
				min_final_style[temp_min]=fin_sty[i];//将终态类型赋值给最小化后的DFA
		}	
		if(b_copy==false)
			temp_min++;
	}
	
	/**********检测删除相同状态后的最小化DFA*****************************/
	out<<"DFA最小化后的结果："<<endl;
	for(int i=0;i<temp_of_state;i++)
	{
		for(int j=0;j<=funct.size();j++)
			out<<min_DFA[i][j]<<" ";
		if(min_DFA[i][funct.size()]==1)
			out<<min_final_style[i];
		out<<endl;
	}
/************************************************************************/
/*********************词法分析程序************************************/
	out<<endl;
	out<<"输出分词结果："<<endl;

	FILE *finput;
	char input;
	if((finput=fopen("source.txt","r"))==NULL)
	{
		cerr<<"The file can not be opened!"<<endl;
		return 1;
	}
	else
	{
		string record="";
		input=fgetc(finput);
		if(input=='*')//乘号特殊处理因为在正则表达式中*表示闭包运算
			input='×';
		int row_of_source=1;
		int start=0;
		bool wether_token=0;
		char style;
		while(input!=EOF)
		{
			char in=input;
			//if(in=='\n')
				//row_of_source++;//行数加一

			if(input<='z'&&input>='a'||input>='A'&&input<='Z')
				in=isalpha(input);
			else if(input>='0'&&input<='9')
				in=isdigit(input);
		
			int y_min=-1;
			for(int i=0;i<funct.size();i++)
			{//在转换函数数组中 查询 该函数是在哪个序列
				if(funct[i]==in)
				{
					y_min=i;
					break;
				}
			}
			if(y_min==-1)
			{//没有该转换函数
				if(wether_token==0)
				{
					out<<"ERROR  occured at the "<<row_of_source<<"th row."<<endl;
					input=fgetc(finput);
					while(input==' '||input=='\n'||input=='\t')
					{
						if(input=='\n')
							row_of_source++;
						input=fgetc(finput);
					}
					if(input==EOF) break;
					fseek(finput,-1,SEEK_CUR);
					start=0;
					
				}
				else
				{//输出
					if(record==";;")
						record=";";
					getToken(style,record);
					wether_token=0;
					while(input==' '||input=='\n'||input=='\t')
					{
						if(input=='\n')
							row_of_source++;
						input=fgetc(finput);
					}
					if(input==EOF)break;
					fseek(finput,-1,SEEK_CUR);
					start=0;
				}
				record="";
				
			}
			else
			{
				if(min_DFA[start][y_min]==-1)
				{//该状态经过转换函数 不可以 到达别的状态
					
					if(wether_token==0)
					{
						out<<"ERROR  occured at the "<<row_of_source<<"th row."<<endl;
						input==fgetc(finput);
						while(input==' '||input=='\n'||input=='\t')
						{
							if(input=='\n')
								row_of_source++;
							input=fgetc(finput);
						}
						if(input==EOF)break;
						fseek(finput,-1,SEEK_CUR);
						start=0;
					}
					else
					{
						if(record==";;")
							record=";";
						getToken(style,record);
						wether_token=0;
						while(input==' '||input=='\n'||input=='\t')
						{
							if(input=='\n')
								row_of_source++;
							input=fgetc(finput);		
						}
						if(input==EOF)break;
						fseek(finput,-1,SEEK_CUR);
						start=0;
					}
					record="";
					
				}
				else
				{//该状态经过转换函数还可以到达别的状态
					start=min_DFA[start][y_min];
					if(min_DFA[start][funct.size()]==1)
					{
						style=min_final_style[start];
						wether_token=1;
					}
				}
				record+=input;//将字符添加到记录字符串中
			}
			input=fgetc(finput);
		}

	}
	fclose(finput);
	/*********************************************************/
	getch();
	return 0;
}