mylex.cpp

实现输入正则表达式的词法分析程序

									nowstate=savestate.front();
									savestate.pop();
									for(int a4=0;a4<ebibao[nowstate].size();a4++)
									{//看此状态的e闭包中所有的状态
										int xiabiao1=ebibao[nowstate][a4];
										if(has[xiabiao1]==false)
										{//如果e闭包中的状态还没遍历到，加入队列，等待遍历
											has[xiabiao1]=true;
											savestate.push(xiabiao1);
										}
									}
								}//while(1)
							}
						}//if(a3)
					}//for(a1)
					//状态a1通过输入字符a2到达的所有状态已经算出
					string newState="";
					for(int a3=0;a3<Tcount;a3++)
					{
						char temp[10];   
						sprintf(temp,"%d",a3);//用这个函数可以规格化到char数组
						if(has[a3]==true) newState=newState+temp+",";
					}
					if(newState=="") continue;//注意：这里可能出错，当此输入字符时到不了任何状态
					/*//输出newState，检测一下是否正确
					outfile << str << "\t" << str1 << "\t" << newState << endl;
					*/
					if(DFAstate.find(newState)==DFAstate.end())
					{
						DFAstate[newState]=DFAcount++;
						DFAnoToString.push_back(newState);//如果是新状态就加入DFA中
					}
					nowUse.list.push_back(make_pair(str1,DFAstate[newState]));
					//上面的for是得出一个string，包含到达结点数的信息，可当作DFA结点信息
				}//for(a2)
				DFAtran++;
				if(DFAtran==DFAcount) break;
				DFAnode.push_back(DFAtemp);
			}//转DFA的while
			/*输出DFA进行检测
			for(int i=0;i<DFAcount;i++)
			{//用来检测一下DFA是否正确
				outfile << i << ":";
				if(DFAnode[i].isAcceptable==true) outfile << "isAcceptable";
				outfile << endl;
				for(int j=0;j<DFAnode[i].list.size();j++)
				{
					outfile << j << ":";
					outfile << DFAnode[i].list[j].first << "\t" << DFAnode[i].list[j].second << endl;
				}
				outfile << endl;
			}//初步检测，NFA->DFA可以了，可能还有BUG
			*/
//--------------------------------------------------------------------------------------上面就是NFA->DFA的的过程

			//用二维表把DFA重新排一下，到达不了的状态用-1表示
			int **DFAtable=new int*[DFAcount];
			for(int i=0;i<DFAcount;i++)
			{//初始化
				DFAtable[i]=new int[Scount];
				for(int j=0;j<Scount;j++)
					DFAtable[i][j]=-1;
			}
			for(int i=0;i<DFAcount;i++)
			{
				for(int j=0;j<DFAnode[i].list.size();j++)
				{
					int fuhao=symbol[DFAnode[i].list[j].first];
					DFAtable[i][fuhao]=DFAnode[i].list[j].second;
				}
			}
			/*检测重排后的DFA
			outfile << "\t";
			for(int i=0;i<Scount;i++)
				outfile << symbolString[i] << "\t";
			outfile << endl;
			for(int i=0;i<DFAcount;i++)
			{//初始化
				outfile << i << ":\t";
				for(int j=0;j<Scount;j++)
					outfile << DFAtable[i][j] << "\t";
				outfile << endl;
			}
			*/
			//最小化DFA，用两个整数数组表示组，数组值相同的两个下标代表的状态是等价的
			int *old=new int[DFAcount];
			int *now=new int[DFAcount];//old代表第一个组，now代表第二个组
			bool *lock=new bool[DFAcount];//锁住某些状态 
			//初始化时，把终极状态定为1,非终极状态定为0，作为最初的分组
			for(int i=0;i<DFAcount;i++)
			{
				if(DFAnode[i].isAcceptable==true)
				{
					old[i]=1;
					now[i]=1;
				}
				else
				{
					old[i]=0;
					now[i]=0;
				}
			}
			int miniCount=2;//用来作为分新集合时的数值，来区别以前的集合KEY
			while(1)
			{
				int temp=miniCount;//当miniCount不变时，就是不会分出新的组的时候就可以退出了
				for(int i=0;i<DFAcount;i++)
					lock[i]=false;
				for(int i=0;i<DFAcount;i++)
				{
					for(int j=i+1;j<DFAcount;j++)//后面的和前面固定的i对比
					{
						if(lock[j]) continue;//用把锁来锁住本次循环已经判断有等价关系的
						if(old[j]==old[i])//开始这两个状态是一个组的时候，可以去比较，如果不是，完全没必要比了
						{
							if(compareState(i,j,DFAtable,now,symbolString,Scount))//等价就是两个状态通过相同输入符号到达的状态属于同一个组（等价）
							{
								now[j]=now[i];
								lock[j]=true;
							}
							else now[j]=miniCount++;
							/*用来测试此步输出结果，单步输出
							for(int i=0;i<DFAcount;i++)
								outfile << old[i] << " ";
							outfile << endl << "---------------------------\n";
							for(int i=0;i<DFAcount;i++)
								outfile << now[i] << " ";
							outfile << endl;
							*/
						}
					}
				}
				for(int i=0;i<DFAcount;i++)
					old[i]=now[i];
				if(temp==miniCount) break;
			}
			/*输入最小化后等价情况
			for(int i=0;i<DFAcount;i++)
				outfile << old[i] << " ";
			outfile << endl;
			*/
			//后面就是整理上面结果成最终的最小化DFA状态转移矩阵

			for(int i=0;i<DFAcount;i++)
				lock[i]=false;//再利用一下这个变量，这里用做消除DFA中等价状态的进程标识
			int deleteCount=0;
			for(int i=0;i<DFAcount;i++)
			{
				if(lock[i]) continue;//如果lock为true，说明这个状态已经被其它状态所代替了！！！
				for(int j=i+1;j<DFAcount;j++)
				{
					if(lock[i]) continue;
					if(old[i]==old[j])//表明是等价的，下面就是在DFAtable中把等价状态后面的用第一个代替
					{
						for(int a1=0;a1<DFAcount;a1++)
						{
							for(int a2=0;a2<Scount;a2++)
							{
								if(DFAtable[a1][a2]==j) DFAtable[a1][a2]=i;
							}
						}
						lock[j]=true;
						deleteCount++;
					}
				}
			}

			/*检测DFA*/
			outfile << "\t";
			for(int i=0;i<Scount;i++)
				outfile << symbolString[i] << "\t";
			outfile << endl;
			for(int i=0;i<DFAcount;i++)
			{//初始化
				if(lock[i]) outfile << "* ";//表示删除的状态行
				else if(DFAnode[i].isAcceptable==true) outfile << "AC ";//表示是接收状态
				outfile << i << ":\t";
				for(int j=0;j<Scount;j++)
					outfile << DFAtable[i][j] << "\t";
				outfile << endl;
			}
			
			//miniDFAtable一起用的是lock表示删除的等价状态,DFAnode有AC数据

			//下面生成词法生成器中关于Token的代码
			outfile << "if(whichToken==" << tokenCount << ")\n{\n";
			//outfile << "publicStr.push_back(c);\n";//publicStr是当前连续输入得到的字符串，在主程序中清空
			for(int i=0;i<DFAcount;i++)
			{
				if(lock[i]) continue;
				for(int j=0;j<Scount;j++)
				{
					if(symbolString[j]=="#") continue;
					if(DFAtable[i][j]!=-1)
					{
						int nextState=DFAtable[i][j];
						outfile << "if(";
						if(symbolString[j].size()==1 || symbolString[j][0]=='\\')
						{//输入符号为单字符的时候，判断的时候用c=='字符'
							outfile << "c=='" << symbolString[j] << "'";
						}
						else
						{//输入符号为一组字符的标号时，判断的时候用函数，函数也是LEX自动生成的
							outfile << "is" << symbolString[j] << "(c)";
						}
						outfile << " && publicState==" << i << ") {publicState=" << nextState << "; publicAC=" << (DFAnode[nextState].isAcceptable==true) << "; publicStr.push_back(c);return 1;}";
						outfile << endl;
					}
				}
			}
			//outfile << "}" << endl;//这句放到结束符语句输出完的后面
		}//if(input=="token start")，表明这一个if是用来处理token的
		else if(input=="finish start")
		{
			outfile << "if((";
			bool first=true;
			while(1)
			{
				getline(infile,input);
				if(input=="finish end") break;
				else
				{//进行结束符的分词
					input.push_back(' ');//为了下面能把最后一个符号简单的取出来，就人为的加一个空格
					string aWord="";
					for(int i=0;i<input.size();i++)
					{
						if(input[i]!=' ') aWord.push_back(input[i]);
						else if(aWord.empty()) continue;
						else
						{
							if(first) {first=false;}
							else outfile << " || ";
							if(aWord.size()==1)
							{//输入符号为单字符的时候，判断的时候用c=='字符'
								outfile << "c=='" << aWord << "'";
							}
							else
							{//输入符号为一组字符的标号时，判断的时候用函数，函数也是LEX自动生成的
								outfile << "is" << aWord << "(c)";
							}
							aWord="";
						}
					}
				}
			}
			outfile << ") && publicAC==true)\n{\n";
			outfile << "TokenName=\"" << tokenName << "\";\npublicAC=0;\n";//这句是输出匹配后词法分析器中给全局变量tokenName赋值，为识别出来的token类别
		}
		else if(input=="name start")
		{//这个部分用来输入一个token中进行名字匹配，例如<匹配成LT，再把LT赋给publicStr
			while(1)
			{
				getline(infile,input);
				if(input=="name end") break;
				if(input=="self")
				{//表示publicStr就是自己本身，直接返回
					outfile << "return 0;\n}\n";
				}
				else
				{
					string s1="",s2="";//s1表示要转换的原publicStr，s2表示转换后的字符串
					int temp=1;
					for(int i=0;i<input.size();i++)
					{
						if(input[i]==' ') temp++;
						else if(temp==1) s1.push_back(input[i]);
						else if(temp==2) s2.push_back(input[i]);
					}
					outfile << "if(publicStr==\"" << s1 << "\")";
					outfile << "\n{\nTokenName=\"" << s2 << "\";\n}\n";
				}
			}
			outfile << "return 0;\n}\n";
			outfile << "publicStr.push_back(c);\nreturn -1;\n}\n";
		}
	}//while(1)
	system("pause");
}//main