myyacc.cpp

一个不算完整的编译器实现

					{
						int tempt=pro[thepro][i1].first;//这里的tempt是点后面非终极符号后的非终极符号
						for(int i3=0;i3<FIRST[tempt].size();i3++)
						{//加入所有FIRST集中的内容
							if(FIRST[tempt][i3]==eposition)
							{//搜索符中不能有ε
								hase=true;
								continue;
							}
							for(int i4=0;i4<bibaofirst[thent].size();i4++)
							{
								if(sid[bibaofirst[thent][i4]][FIRST[tempt][i3]]==false)
								{
									sid[bibaofirst[thent][i4]][FIRST[tempt][i3]]=true;
									haschanged=true;
								}
							}
						}
						if(!hase) break;//FIRST中没有ε的话搜索符就求完了
					}//else
				}//
				if(haschanged)
				{
					for(int i1=0;i1<bibaofirst[thent].size();i1++)
					{//加入其bibaofirst中所有项到队列
						itemqueue.push(bibaofirst[thent][i1]);
					}
				}
			}
		}
		/*
		//测试最后的一个项目的搜索符
		cout << eposition << endl;
		cout << "\t";
		for(int i=0;i<tCount;i++)
			cout << tToString[i] << "\t";
		cout << endl;
		for(int i=0;i<productionCount;i++)
		{
			cout << ntToString[pro[i][0].first] << "\t";
			for(int j=0;j<tCount;j++)
				cout << sid[i][j] << "\t";
			cout << endl;
		}
		*/
		for(int i=0;i<productionCount;i++)
		{
			if(isbibao[i])
			{//如果产生式是闭包项，就把算出来的搜索符给它
				item_struct temp;
				temp.pp=0;
				temp.pronum=i;
				for(int j=0;j<tCount;j++)
				{
					if(sid[i][j])
						temp.searchnum.push_back(j);
				}
				bibao_item.push_back(temp);
			}
		}
		delete []isbibao;
		for(int i=0;i<nownode.heart.size();i++)
		{//把核心项也加入到bibao_item，形成所有的状态中的项目集
			bibao_item.push_back(nownode.heart[i]);
		}
		/*//测试项目集的搜索符
		for(int i=0;i<bibao_item.size();i++)
		{
			cout << ntToString[pro[bibao_item[i].pronum][0].first] << "\t";
			for(int j=0;j<bibao_item[i].searchnum.size();j++)
				cout << tToString[bibao_item[i].searchnum[j]] << "\t";
			cout << endl;
		}
		*/
		//--------------------------------------------------------开始生成新的状态及其核心项了
		//所有当前的项目都在bibao_item中了，对这个集合进行点的后移
		//当点已经到了最后面的情况时，就算归约项了
		bool *ntOK=new bool[ntCount];
		bool *tOK=new bool[tCount];
		for(int i=0;i<ntCount;i++)
			ntOK[i]=false;
		for(int i=0;i<tCount;i++)
			tOK[i]=false;
		//上面的bool数组用来记录转移的时候项目的符号点后的符号是否已经用过了
		for(int i=0;i<bibao_item.size();i++)
		{
			item_struct &theitem=bibao_item[i];
			if(theitem.pp == pro[theitem.pronum].size()-1)//为归约项，跳过
				continue;

			int thet=pro[theitem.pronum][theitem.pp+1].first;
			if((pro[theitem.pronum][theitem.pp+1].second==false && tOK[thet]==false) || (pro[theitem.pronum][theitem.pp+1].second==true && ntOK[thet]==false))
			{//以前没算过的时候再去算
				vector<item_struct> newheart;
				for(int j=i;j<bibao_item.size();j++)
				{//从i后开始看就行了，因为前面的肯定已经做过了
					item_struct &theitemin=bibao_item[j];
					if(theitemin.pp == pro[theitemin.pronum].size()-1)//为归约项，跳过
						continue;
					if(pro[theitemin.pronum][theitemin.pp+1].second == pro[theitem.pronum][theitem.pp+1].second &&
						pro[theitemin.pronum][theitemin.pp+1].first == pro[theitem.pronum][theitem.pp+1].first)
					{
						item_struct nextitem=bibao_item[j];
						nextitem.pp++;//点向后移一位，搜索符已经带着了
						newheart.push_back(nextitem);
					}
				}
				//创建新的状结点，写入核心项和标识字符串
				string theid=cal_state_id(newheart);
				if(stateid.find(theid)==stateid.end())//没找到含有相同核心项的状态
				{
					stateid[theid]=DFACount++;
					DFAnode_struct newnode;
					newnode.heart=newheart;
					newnode.id=theid;
					DFAnode.push_back(newnode);
					if(pro[theitem.pronum][theitem.pp+1].second==false) 
						DFAnode[now_state].termin.push_back(make_pair(thet,DFACount-1));//！很奇怪，这里用nownode就不行
					else 
						DFAnode[now_state].nontermin.push_back(make_pair(thet,DFACount-1));
					//上面的是终极符或非终极符添加边的情况
				}
				else//找到了相同状态结点的时候
				{
					int next_state_num=stateid.find(theid)->second;
					if(pro[theitem.pronum][theitem.pp+1].second==false) DFAnode[now_state].termin.push_back(make_pair(thet,next_state_num));
					else DFAnode[now_state].nontermin.push_back(make_pair(thet,next_state_num));
				}
			}//if
			if(pro[theitem.pronum][theitem.pp+1].second==false) tOK[thet]=true;
			else ntOK[thet]=true;
		}//for_i
		now_state++;
		delete []ntOK;
		delete []tOK;
	}//while_算状态结点的
	bool *state_used=new bool[(int)DFAnode.size()];
	for(int i=0;i<(int)DFAnode.size();i++)
		state_used[i]=true;
	//state_used用来标记此状态是否是被合并了的，也就是是否还要使用
	//showDFA(DFAnode,pro,tToString,ntToString,state_used);
	//以上把所有LR(1)状态都求出来了，每个状态记录的都只是它的核心项
	//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
	//下面就要进行LR(1)状态的合并，合并同心项
	map<int,int> state_change;
	//用来表示两个状态合并时是哪两个状态，后面的是合并到的状态号，前面的是被合并的状态号，此map用来在合并后对状态的边进行修改，
	//也就是把被合并的状态的入度边指向改为合并到的状态
	for(int i=0;i<DFAnode.size();i++)
	{
		if(!state_used[i]) continue;
		for(int j=i+1;j<DFAnode.size();j++)
		{//每一个状态都和后面所有的状态去比较核心项，若相同就合并搜索符并相应更变边的指向
			if(!state_used[j]) continue;
			if(is_same_heart(DFAnode[i],DFAnode[j]))
			{//两个状态是同心的时候，进行合并：把后面的状态的搜索符合到前面的状态，并增加到后面的边，再建立两个状态的联系（map）
				combine_searchsymbol(DFAnode[j],DFAnode[i],tCount);
				/*//显示合并后的项目
				for(int k=0;k<DFAnode[i].heart.size();k++)
					show_item(DFAnode[i].heart[k],pro,tToString,ntToString);
				*/
				
				//！！！由于如果两个状态的核心项目（除搜索符）完全一样，那么它们通过符号到达的下一个状态的核心项目（除搜索符）也会完全一样，也就是最终由
				//由此这两个状态到达的状态也应该会合并，故没有必要再去把边加到前面去
				state_used[j]=false;
				state_change[j]=i;
			}
		}
	}
	//修改边，把无效的状态号改成合并到的状态号
	for(int i=0;i<DFAnode.size();i++)
	{
		if(!state_used[i]) continue;
		for(int j=0;j<DFAnode[i].nontermin.size();j++)
		{//对于非终极符号的
			int nextstate=DFAnode[i].nontermin[j].second;
			if(state_change.find(nextstate)!=state_change.end())//在状态合并项中找到
			{
				DFAnode[i].nontermin[j].second=state_change.find(nextstate)->second;//改变边
			}
		}
		for(int j=0;j<DFAnode[i].termin.size();j++)
		{//对于终极符号的
			int nextstate=DFAnode[i].termin[j].second;
			if(state_change.find(nextstate)!=state_change.end())
			{
				DFAnode[i].termin[j].second=state_change.find(nextstate)->second;
			}
		}
	}
	//showDFA(DFAnode,pro,tToString,ntToString,state_used);
	//-----------------------------------------------------------------------------------------------
	//用来生成分析表ACTION和GOTO
	//先生成ACTION表，规定：移入项目用正数，数为状态号；归约用负数，数为对应的产生式
	vector<int*> action_table;
	vector<int> yasuo;//因为状态集只用了state_used来标识状态是否是使用的，在做表的时候就不留空白空间了，要把状态压缩，无效的去掉，下标是原状态号，值是新的表项号（状态号）
	for(int i=0;i<DFAnode.size();i++)
	{
		yasuo.push_back(action_table.size());//记下来前后的序号对应关系
		if(!state_used[i]) continue;
		int *line=new int[tCount];//表示表中的一行，用0（错误）来初始化
		for(int j=0;j<tCount;j++)
			line[j]=0;
		for(int j=0;j<DFAnode[i].termin.size();j++)
		{//移入项目
			pair<int,int> temp=DFAnode[i].termin[j];
			line[temp.first]=temp.second;
		}
		for(int j=0;j<DFAnode[i].heart.size();j++)
		{//找有无归约项
			const item_struct temp=DFAnode[i].heart[j];
			if(temp.pp>=pro[temp.pronum].size()-1)//点到最后了
			{//在搜索符处归约
				for(int k=0;k<temp.searchnum.size();k++)
				{
					int snum=temp.searchnum[k];
					line[snum]=-temp.pronum;//在搜索符snum处归约产生式号为temp.pronum的产生式
					if(line[snum]==0)//此时归约的是0号产生式，即开始符号推出的产生式
						line[snum]=-productionCount-10;
				}
			}
		}
		action_table.push_back(line);
	}
	for(int i=0;i<action_table.size();i++)
	{//用来修改移入的状态号
		for(int j=0;j<tCount;j++)
		{
			if(action_table[i][j]>0)//为移入项时
			{
				action_table[i][j]=yasuo[action_table[i][j]];
			}
		}
	}
	//输出一下ACTION表
	//showACTION(action_table,tToString,productionCount);
	//再生成GOTO表
	vector<int*> goto_table;
	for(int i=0;i<DFAnode.size();i++)
	{
		if(!state_used[i]) continue;
		int *line=new int[ntCount];
		for(int j=0;j<ntCount;j++)
			line[j]=0;
		for(int j=0;j<DFAnode[i].nontermin.size();j++)
		{
			pair<int,int> temp=DFAnode[i].nontermin[j];
			line[temp.first]=temp.second;
		}
		goto_table.push_back(line);
	}
	for(int i=0;i<goto_table.size();i++)
	{//用来修改GOTO的状态号
		for(int j=0;j<ntCount;j++)
		{
			if(goto_table[i][j]>0)
			{
				goto_table[i][j]=yasuo[goto_table[i][j]];
			}
		}
	}
	//输出一下GOTO表
	//showGOTO(goto_table,ntToString);
	/*//输出来谁压缩谁
	for(int i=0;i<yasuo.size();i++)
	{
		cout << "状态" << i << "压缩成状态" << yasuo[i] << endl;
	}
	*/
//--------------------------------------------------------------------------------------------
	//用来把分析表输出到文件（格式：第一行：终极符号名称；第二行：非终极符号名称；第三行：状态数；后面就分别是ACTION表和GOTO表，每个状态为一行）
	ofstream outfile;
	outfile.open("system\\action_goto_tables.txt");
	for(int i=0;i<tCount;i++)
	{
		outfile << tToString[i] << " ";
	}
	outfile << endl;
	for(int i=0;i<ntCount;i++)
	{
		outfile << ntToString[i] << " ";
	}
	outfile << endl;
	outfile << action_table.size() << endl;
	for(int i=0;i<action_table.size();i++)
	{
		for(int j=0;j<tCount;j++)
		{
			outfile << action_table[i][j] << " ";
		}
		outfile << endl;
	}
	for(int i=0;i<goto_table.size();i++)
	{
		for(int j=0;j<ntCount;j++)
		{
			outfile << goto_table[i][j] << " ";
		}
		outfile << endl;
	}
	system("system\\compile3.exe");
}
//动态分配的内存FIRST,first,bibao,bibaofirst
//闭包项传递的搜索符退出while循环的方法，用一个bool数组记下来用过哪些产生式，再想想吧

/*所有变量名
DFAcount：DFA状态数
DFAnode：vector<DFAnode_struct> DFAnode表示状态结点
map<int,int> state_change;//用来表示两个状态合并时是哪两个状态，后面的是合并到的状态号，前面的是被合并的状态号，此map用来在合并后对状态的边进行修改，也就是把被合并的状态的入度边指向改为合并到的状态
bool state_used[]表示状态是否是有用的

函数：
showDFA：用来显示当前vector<DFAnode_struct>中的树形结构
*/