mylex.cpp

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

#include<iostream>
#include<map>
#include<vector>
#include<fstream>
#include<string>
#include<utility>
#include<queue>

using namespace std;
struct TokenNode
{
	bool isAcceptable;
	int kindint;//kind表示token的类型，先用整型数试试
	string kindstr;//再设一个string类型的kind
	vector<pair<string,int> > list;//用来记录输入字符时转向的状态，相当于邻接表
};

vector<int> DFAstringToInt(string str)
{//用来做在DFA中状态标识是string类型的，在遍历NFA时，要把string还原成对应的NFA的int下标
//这种string格式为"0,2,4,10,12"，此函数就是把数从其中取出，存到vector中返回
	vector<int> stor;
	int temp=0;
	for(int i=0;i<str.size()-1;i++)
	{
		if(str[i]!=',') temp=temp*10+str[i]-'0';
		else
		{
			stor.push_back(temp);
			temp=0;
		}
	}
	stor.push_back(temp);//把到最后的那个数存起来
	return stor;
}
//s1和s2是状态的编号，通过DFAtable来对比
bool compareState(int s1,int s2,int **DFAtable,int now[],vector<string> &symbolString,int Scount)
{
	for(int i=0;i<Scount;i++)
	{
		if(symbolString[i]=="#") continue;//跳过ε这个符号，否则后面的下标后为-1
		int nexts1=DFAtable[s1][i],nexts2=DFAtable[s2][i];
		if(now[nexts1]!=now[nexts2]) return false;//只要有一个不是一组，就说明是不等价的
	}
	return true;//否则就说明是等价的
}

int main()
{
	ifstream infile;
	ofstream outfile;
	infile.open("lextext.txt");//打开lex词法文件，里面是正则文法
	outfile.open("out.cpp");//打开词法分析器的输出部分
	if(!infile)
	{//打开lex正则方法文件失败就退出
		printf("Unable to open the LexText file.\n");
		return -1;
	}
	int tokenCount=0;//用来表示token的种类数
	string tokenName="";
	while(1)
	{
		string input;
		getline(infile,input);
		if(input=="end input") break;
		if(input=="symbol start")
		{
			while(1)
			{
				getline(infile,input);
				if(input=="symbol end") break;
				//对每一个都生成一个函数
				input.push_back(' ');//加一个空格好处理
				string symbolName="";
				string symbol="";
				int flag=0;
				for(int i=0;i<input.size();i++)
				{
					if(flag==0 && input[i]!=' ')
						symbolName.push_back(input[i]);
					else if(flag==0 && input[i]==' ')
					{//取函数名
						flag=1;
						outfile << "bool is" << symbolName << "(char c)\n";
						outfile << "{\n if(";
					}
					else if(flag==1 && input[i]!=' ') symbol.push_back(input[i]);
					else if(flag==1 && input[i]==' ')
					{
						bool hascon=false;
						for(int j=0;j<symbol.size();j++)
							if(symbol[j]=='-')
							{
								hascon=true;
								break;
							}
						if(hascon==false)
						{//没有中间的连接符
							outfile << "c==" << symbol << " || ";
						}
						else
						{
							outfile << "(c>=";
							for(int j=0;j<symbol.size();j++)
							{
								if(symbol[j]!='-')
									outfile << symbol[j];
								else
								{
									outfile << " && c<=";
								}
							}
							outfile << ") || ";
						}
						symbol="";
					}
				}
				outfile << "false) return true;\nelse return false;\n}\n";
			}
		}
		else if(input=="token start")
		{
			tokenCount++;
			vector<string> sen;//用来存放正则文法，一个sen做一个DFA
			while(1)
			{//这里就是一个判断token的所有正则文法的语句
				getline(infile,input);
				if(input=="") continue;
				if(input=="token end") break;
				sen.push_back(input);
			}
			tokenName=sen[0];//当前token的名称
			map<string,int> nonterminal;//定义非终极符号的map
			int Tcount=0;//非终极状态个数
			map<string,int> symbol;//定义输入符号表的map
			int Scount=0;//输入符号的个数
			vector<string> symbolString;//用来存放map标号对应的输入符号名称，用下标来对应，就是把map的S-Num变成Num-S
			for(int i=1;i<sen.size();i++)
			{
				string temp="";
				for(int j=0;j<sen[i].size();j++)
				{//用来提取文法中的非终极符号
					if(sen[i][j]==' ')
					{
						if(nonterminal.find(temp)==nonterminal.end()) nonterminal[temp]=Tcount++;
						//相等的时候表明在MAP中没找到到应的非终极状态，此时要加入
						break;
					}
					temp.push_back(sen[i][j]);
				}
			}
			TokenNode *NFAnode = new TokenNode[Tcount+1];//创建NFA的状态数组
			for(int i=0;i<Tcount;i++)
				NFAnode[i].isAcceptable=false;//把非终极状态的可接受设为false，就是初始化

			NFAnode[Tcount].isAcceptable=true;//自己加一个终极状态
			NFAnode[Tcount].kindstr=tokenName;
			nonterminal["#"]=Tcount;//把终极状态放到转换的MAP中
			Tcount++;//状态数包括终极状态
			for(int i=1;i<sen.size();i++)
			{//读正则文法，转为NFA结点
				string a1="",a2="",a3="";
				int status=0;
				for(int j=0;j<sen[i].size();j++)
				{//把lex文件中的变形正则表达式转化为三个string，第一个为非终极状态，第二个为输入字符，第三个为转换为的非终极状态
					if(sen[i][j]==' ') {status++;continue;}
					if(status==0) a1.push_back(sen[i][j]);
					else if(status==1) a2.push_back(sen[i][j]);
					else if(status==2) a3.push_back(sen[i][j]);
				}
				int c1=nonterminal.find(a1)->second;//c1就是非终极状态转换成的状态结点下标
				int c3=nonterminal.find(a3)->second;//c3就是转换到的状态下标
				NFAnode[c1].list.push_back(make_pair(a2,c3));
				//记录输入字符，并映射到symbol的MAP中
				if(symbol.find(a2)==symbol.end()) {symbol[a2]=Scount++; symbolString.push_back(a2);}
			}
			/*
			//用来检测一下NFA是否正确
			for(int i=0;i<Tcount;i++)
			{
				outfile << i << ":";
				if(NFAnode[i].isAcceptable==true) outfile << "isAcceptable";
				outfile << endl;
				for(int j=0;j<NFAnode[i].list.size();j++)
				{
					outfile << j << ":";
					outfile << NFAnode[i].list[j].first << "\t" << NFAnode[i].list[j].second << endl;
				}
				outfile << endl;
			}
			for(int i=0;i<Scount;i++)//检测输入符号的存储是否正常
				outfile << i+1 << ": " << symbolString[i] << endl;
			*/

//--------------------------------------------------------------------------------------上面是从我的正则文法转为NFA的过程

			vector<TokenNode> DFAnode;//DFA的状态结点数组
			int DFAcount=0;//表示DFA状态结点数
			TokenNode DFAtemp;//DFA中的临时状态
			DFAnode.push_back(DFAtemp);
			map<string,int> DFAstate;//用来记录DFA状态的string标识和DFAnode中下标的对应关系
			vector<string> DFAnoToString;//把DFA中状态结点下标转回string标识，!!!不知道用不用的着!!!
			//求出每个NFA结点的e闭包，这里e只能用#表示
			vector<int> *ebibao=new vector<int>[Tcount];
			for(int i=0;i<Tcount;i++)
			{//真正的求e闭包，原来的只求了一部分
				bool *ehas=new bool[Tcount+1];
				for(int j=0;j<Tcount;j++)
					ehas[j]=false;
				queue<int> s;//记录经历过并要算e闭包的状态
				s.push(i);
				while(1)
				{//这里用的是队列，来遍历每一个可能的结点 
					if(s.empty()) break;
					int ss=s.front();
					s.pop();
					for(int j=0;j<NFAnode[ss].list.size();j++)
					{
						if(NFAnode[ss].list[j].first=="#")
						{
							int num=NFAnode[ss].list[j].second;
							
							if(ehas[num]==false)
							{
								ehas[num]=true;
								s.push(num);
								//outfile << "number=" << num << endl;
							}
						}
					}
				}
				for(int j=0;j<Tcount;j++)
					if(ehas[j]==true) ebibao[i].push_back(j);
				delete []ehas;
			}
			/*用来测试求e闭包结果是否正确
			for(int i=0;i<Tcount;i++)
			{
				outfile << "结点为" << i << ": ";
				for(int j=0;j<ebibao[i].size();j++)
					outfile << ebibao[i][j] << " ";
				outfile << endl;
			}
			*/
			string beginstate="0,";
			for(int i=0;i<ebibao[0].size();i++)
			{
				char temp[10];
				sprintf(temp,"%d,",ebibao[0][i]);
				beginstate+=temp;
			}
			//outfile << beginstate<< endl;检测初始状态
			DFAstate[beginstate]=DFAcount++;//初始状态应该为0状态的e闭包，我在这开始的时候曾出错了
			DFAnoToString.push_back(beginstate);
			int DFAtran=0;
			while(1)
			{
				TokenNode &nowUse=DFAnode[DFAtran];//取没做的第一个状态
				string str=DFAnoToString[DFAtran];
				vector<int> states=DFAstringToInt(str);
				for(int a2=0;a2<Scount;a2++)
				{//对一个状态求对应输入字符所能到达的状态
					string str1=symbolString[a2];
					if(str1=="#") continue;
					bool *has=new bool[Tcount];//该NFA状态通过各输入字符到达的状态
					for(int j=0;j<Tcount;j++)
						has[j]=false;
					for(int a1=0;a1<states.size();a1++)
					{//a1循环是从DFA标识中把各状态扫描一下
						int state=states[a1];//取出状态
						if(NFAnode[state].isAcceptable==true) nowUse.isAcceptable=true;
						queue<int> savestate;//用来记录要访问的结点号
						for(int a3=0;a3<NFAnode[state].list.size();a3++)
						{
							if(NFAnode[state].list[a3].first==str1)
							{
								int nowstate=NFAnode[state].list[a3].second;
								if(!has[nowstate])//当前的输入符号和NFA中状态输入符号匹配时
								{
									savestate.push(nowstate);
									has[nowstate]=true;
								}
								while(!savestate.empty())
								{//把e闭包中的状态记下来