lexanalysis.cpp

词法分析程序（完整） 实现对C语言的词法分析

				dfaState.desState = product;
				StateForDFA1.push_back(dfaState);
			}
		}
		currentState++;
		MulState.pop();
		delete []tag; tag=NULL;
	}

	DFAStateNum = (int)IsAlreadyHave.size();
	cout << "NFA->DFA End!\n";

	out << "\n新状态对应该表:\n\n";
	out << "新状态\t旧状态\n"; 
	for(map<int,vector<int> >::iterator it = OpoHave.begin(); it!=OpoHave.end(); ++it)
	{
		out << it->first << "\t";
		for(int i = 0; i< (int)it->second.size(); ++i) {
			out << it->second[i] << ',';
		}
		out << endl;
	}
	remarkDFA();
	sortDFA();
	FillDFATable();
}

//　对DFA重新编号
void remarkDFA() 
{
	int len = (int)StateForDFA1.size();
	DFANewState temp;
	for(int i = 0; i< len; ++i) {
		temp.destination = IsAlreadyHave[StateForDFA1[i].desState];
		temp.source = IsAlreadyHave[StateForDFA1[i].sourceState];
		temp.terminal = StateForDFA1[i].terminal;
		NewDFA.push_back(temp);
	}
	return ;
}

//　状态的排序
void sortDFA()
{
	sort(NewDFA.begin(),NewDFA.end(),MyCmp);
}

//　DFA转换状态过程的排序比较方法
bool MyCmp(DFANewState a,DFANewState b) {
	if(a.source < b.source)	return true;
	if(a.source > b.source)	return false;
	if(a.terminal < b.terminal)	return true;
	if(a.terminal > b.terminal)	return false;
	if(a.destination < b.destination)	return true;
	else return false;
}

//　将DFA的一条条记录形式存入DFA二维表
void FillDFATable()
{
	for(int i = 0; i< (int)NewDFA.size(); ++i) {
		DFA[NewDFA[i].source][NewDFA[i].terminal] = NewDFA[i].destination;
	}
}

//　显示DFA表
int ShowDFA()
{
	vector<int> temp;
	cout << "ShowDFA begin\n";
	out << "\n输出DFA:\n";
	int t = NewDFA[1].source;
	out << t << "->\t";
	int len = (int)NewDFA.size();
	for(int i = 1; i< len; ++i) {
		if(NewDFA[i].source>t) {
			DFAChange[t] = temp;
			t = NewDFA[i].source;
			out << endl;
			out << t << "->\t";
			temp.clear();
			
		}
		out << NewDFA[i].destination << ',';
		temp.push_back(NewDFA[i].destination);
	}
	out << "\n DFA　END\n";
	return 0;
}

//　设置DFA状态是否为可接受,并记录接受状态的类别
void SetDFA() {
	dfaAccepted temp;
	for(int i = 1; i<= DFAStateNum; ++i) {
		bool isAccepted = false  ;
		for(int j = 0; j< (int)OpoHave[i].size(); ++j) {
			if(allState[OpoHave[i][j]].isAcceptable == true) {
				isAccepted = true;
				temp.Name = allState[OpoHave[i][j]].tokenKindName;
				break;
			}
		}
		if(isAccepted == true)	{
			temp.IsAccepted = true;
			
		}
		else {//　如果是不可接受状态,将其Name设为空,因为后面也用不到
			temp.IsAccepted = false;
			temp.Name = "";
		}
		DFAIsAccepted.push_back(temp);
	}
	out << "\nDFA 状态可接受情况:\n";	
	for(int i = 0; i< (int)DFAIsAccepted.size(); ++i) {
		out << i+1 << '\t' << DFAIsAccepted[i].IsAccepted << '\t' << DFAIsAccepted[i].Name << endl;
	}
}

/*　最小化ＤＦＡ过程
　　　采用的算法:
	就是将队列中第一个状态分解成尽可能多的不等价状态集合
	如果新产生的状态只有一个则不变,直接移至队列尾部
	在实现过程中却没有用队列,而是用向量代替模拟,
    这样可以比较方便的标记每个状态对应该所在状态集的号
*/
void MinDFA() {
	cout << "MinDFA Start\n";
	vector<int> accepted; //终态
	vector<int> notAccepted; // 非终态
	allDFAState.push_back(accepted);//　加入一个空状态,用以在最小化过程中,那些能过终极符不能到达另一个状态的集合的状态标记
	//　tag是每个标记每个状态对应它应该在的状态集的号
	int *tag = new int[DFAStateNum+1];
	memset(tag,0,sizeof(tag));
	// 分为可接受状态和不可接受状态
	for(int i = 0; i< DFAStateNum; ++i) {
		if(DFAIsAccepted[i].IsAccepted == true) {
			accepted.push_back(i+1);
			tag[i+1] = 1;
		}
		else {
			notAccepted.push_back(i+1);
			tag[i+1] = 2;
		}
	}
	allDFAState.push_back(accepted);
	allDFAState.push_back(notAccepted);

	//　如果刚开始中的可接受状态中,哪个状态都不能通过任何的终极符到达另一个状态,
    //  则它必定不会与其他状态等价
	//　所以以下的一段程序是筛选出这样的状态
	bool *Keep = new bool[(int)accepted.size()];
	for(int i = 0; i< (int)accepted.size(); ++i) {
		Keep[i] = true;
		bool next = false;
		for(int j = 0; j< terminalNum; ++j) {
			if(DFA[accepted[i]][j] != 0)	{	//　表明有可能到达的状态,则它不是被筛选的对象
				next = true;
				break;
			}
		}
		if(next == false) {	//　表明该状态是不可能与其他可接受状态等价的,直接分离出来
			Keep[i] = false;
			vector<int> temp;
			temp.push_back(accepted[i]);
			allDFAState.push_back(temp);
			tag[accepted[i]] = (int)(allDFAState.size());
		}
	}
	allDFAState[1].clear();
	for(int i = 0; i< (int)accepted.size(); ++i) {
		if(Keep[i] == true) {
			allDFAState[1].push_back(accepted[i]);
		}
	}
	// 筛选结束

	out << "最小化DFA前的状态集合：\n";
	for(int i = 1; i< (int)allDFAState.size(); ++i) {
		out << "{ ";
		for(int j = 0; j< (int)allDFAState[i].size(); ++j) {
			out << allDFAState[i][j] << ' ';
		}
		out << "}" << endl;
	}

	// 最小化开始
	int len = (int)allDFAState.size(); // 目前所有状态数
	int T = 0;
	bool done = false;
	vector<vector<int> > p;	// 用来标记一个状态转化成目前多个状态的情况
	while(T<DFAStateNum)
	{
		vector<int> front = allDFAState[1];//　每一次都取向量的第二个进行分解
		if((int)front.size() == 1) {
			allDFAState.push_back(allDFAState[1]);
			allDFAState.erase(allDFAState.begin());
			for(int i = 1; i< (int)allDFAState.size(); ++i) {
				for(int j = 0; j< (int)allDFAState[i].size(); ++j) {
					tag[allDFAState[i][j]] = i;
				}
			}
			T++;
			continue;
		}
		allDFAState[0].clear();
		int size = (int)front.size();
		bool isFrontOk = true;
		int current = 0;
		for(int i = 0; i< terminalNum; ++i) {
			if(terminal2[i] == "@")	continue;
			p.clear();
			vector<int> temp;
			temp.clear();
			len = (int)allDFAState.size();
			front = allDFAState[1];
			// 初始化p
			for(int t = 0; t< len; ++t)	p.push_back(temp);
			for(int j = 0; j< size; ++j) {
				// 把第j个front中的对应通过i到达的状态赋值给front[j]所在的状态标号
				// p[tag[front[j]]].push_back(DFA[front[j]][i]);
				if(DFA[front[j]][i] == 0)	// 若没有后继,则p[0]++;
					p[0].push_back(front[j]);
				else 
					p[tag[DFA[front[j]][i]]].push_back(front[j]);	
			}
			int lencopy = len;
			int breakToNum = 0;//　front分解成的个数
			for(int k = 0; k< lencopy; ++k) {
				if((int)p[k].size()>0)
				{
					breakToNum++;
				}
			}
			if(breakToNum == 1) {
				current++;
			}
			else current = 0;
			//　当front分解成多于一个vector时才用分解后的代替front,不然就不变
			if((breakToNum > 1)||current==(terminalNum-1)) {
				for(int k = 0; k< lencopy; ++k) {
					if((int)p[k].size()>0)
					{
						allDFAState.push_back(p[k]);
						//重新定位p[k]中所有的tag.
						for(int h = 0; h< (int)p[k].size(); ++h) tag[p[k][h]] = len;
						len ++;
					}
				}
				// 修正tag
				for(int k = 1; k< lencopy; ++k) {
					for(int g = 0; g< (int)allDFAState[k].size(); ++g) {
						tag[allDFAState[k][g]]--;
					}
				}
				allDFAState.erase(allDFAState.begin());
				len--;
				if(breakToNum>1)	{
					isFrontOk = false;
					break;
				}
			}
		}
		if(isFrontOk)	T++;
		else T = 0;
	}
	cout << "MinDFA End\n";

	out << "最小化DFA后的结果\n";
	for(int i = 0; i< (int)allDFAState.size(); ++i) {
		out << "{ ";
		for(int j = 0; j< (int)allDFAState[i].size(); ++j) {
			out << allDFAState[i][j] << ' ';
		}
		out << "}" << endl;
	}
	//合并等价的状态
	int *keep = new int[DFAStateNum+2];
	for(int i = 0; i<= DFAStateNum+1; ++i)	keep[i] = 0;
	for(int i = 0; i< (int)allDFAState.size(); ++i) {
		for(int j = 0; j< (int)allDFAState[i].size(); ++j) {
			keep[allDFAState[i][j]] = allDFAState[i][0];
		}
	}
	// 等价状态的替换
	for(int i = 1; i<= DFAStateNum; ++i) {
		for(int j = 0; j< terminalNum; ++j)
			if(DFA[i][j]>0) DFA[i][j] = keep[DFA[i][j]];
	}
	for(int i = 0; i< (int)NewDFA.size(); ++i) {
		NewDFA[i].destination = keep[NewDFA[i].destination];
	}
	out << "DFA 状态转换表\n";
	for(int i = 1; i<= DFAStateNum; ++i) {
		out << i << '\t';
		for(int j = 0; j< terminalNum; ++j) {
			out << DFA[i][j] << '\t';
		}
		out << endl;
	}
	out << "END！！！\n";
}

//　利用最小化后的DFA进行词法分析
void LexAnalysis()
{
	char ch;
	string str = "";
	int line = 0;
    cout<< "Lexical Analysis Start:\tToken\n"; 
	while(in1.get(ch))	{
		str += ch;
		if(ch == '\n')	{//　一行一行的分析
			line ++;
			int it = 0;
			while(str[it] == ' ' || str[it] == '\t')	it++;//　跳过间隔符等
			string substr;
			for(int i = it; i< (int)str.length(); ++i) {
				if(str[i] == ' ' || str[i] == '\t') {
					substr = str.substr(it,i-it);
					Prase(substr,line);//　截得一段连续的源代码

					while(str[i] == ' ' || str[i] == '\t')	i++;
					it = i;
					i--;
				}
			}
			Prase(str.substr(it,str.length()-it-1),line);
			str.clear();
		}		
	}
	Prase(str,line);
	cout<<"Lexical Analysis End!\n";
	return ;
}

//　对截得的一段源代码进行词法分析 ，输出Token序列 
void Prase(string str,int line) {
	int nowState = 1;//　初始化当前状态
	int i = 0;
	int leng = (int)str.length();
	string token = "";
	bool Acceptable = false;
	while(i<=leng) {
		if(i == leng) {
			if(Acceptable == true)	{//　如果当前的接受情况是可接受的,则一个token产生
				out1 << token << "\t->\t";
				cout << token << "\t->\t";
				if(reverseconst.find(token)!=reverseconst.end()) {//　如果是保留字,则输出是保留字
					out1 << "Reverse\n";
					cout << "Reverse\n";
                }
				else {
					out1 << DFAIsAccepted[nowState-1].Name<< "\n";//　输出类型
					cout << DFAIsAccepted[nowState-1].Name<< "\n";
                }
			}
			else {
				out1 << "ERROR: 出错行:\t" << line << "\n"; //　如果当前的接受情况是不可接受,那么出错
				cout << "ERROR: 出错行:\t" << line << "\n";
			}
			break;
		}
		//i<leng的情况 
		if(DFA[nowState][PointToTerminal[str[i]]]!=0) { //　不等于0表明可以继续下一个状态
			token += str[i];
			nowState = DFA[nowState][PointToTerminal[str[i]]];
			if(DFAIsAccepted[nowState-1].IsAccepted == true)	Acceptable = true;
			else Acceptable = false;
		}
		else { //　一个token结束或者出错
			if(Acceptable == false)	{
				out1 << "ERROR: 出错行:\t" << line << "\n"; //　如果当前的接受情况是不可接受,那么出错
				cout << "ERROR: 出错行:\t" << line << "\n";
				return ;
			}
			else {	//　如果当前的接受情况是可接受的,则一个token产生
				out1 << token <<  "\t->\t";
				cout << token <<  "\t->\t";
				if(reverseconst.find(token)!=reverseconst.end()){ //　如果是保留字,则输出是保留字
					out1 << "Reverse\n";
					cout << "Reverse\n";
                }
				else {
					out1 << DFAIsAccepted[nowState-1].Name<< "\n"; //　输出类型
					cout << DFAIsAccepted[nowState-1].Name<< "\n";
                }
			}
			token = ""; //　token清零
			nowState = 1; //　复位超始状态
			i--;
		}
		i++; //　向后扫描一个字符
	}
}

//******************主函数*****************

int main() {
	//  初始化一些变量和常量等
	InitString();
	//  输入文法
	InputGrammar();
	//获取所有状态
	GetState();
	//　获取所有终极符
	GetTerminal();
	//　从正则文法到NFA
	ChangeToNFA();
	//　显示NFA
	ShowNFA();
	//　获取各个状态的*闭包
	GetClosure();
	//　从NFA到DFA
	NFAToDFA();
	//  显示DFA
	ShowDFA();
	//　设置DFA状态是否为可接受,并记录接受状态的类别
	SetDFA();
	//　最小化DFA
	MinDFA();
	//　利用最小化后的DFA进行词法分析
	LexAnalysis();
	system("pause");
	return 0;
}