myyacc.cpp

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

	delete []production;
	//开始求FIRST集，我只用求非终极符号的FIRST就可以了
	bool **first=new bool*[ntCount];
	for(int i=0;i<ntCount;i++)
	{//用一个bool型的二维数组表示nonterminal的FIRST集，为1时表明FIRST集里有对应terminal元素
		first[i]=new bool[tCount];
		for(int j=0;j<tCount;j++)
			first[i][j]=false;
	}
	while(1)
	{
		bool haschanged=false;//用来判断是否有新的变化产生，退出while的判断
		for(int i1=0;i1<productionCount;i1++)
		{//对于每一个产生式
			int see=1;//这是比较重要的一位，这一位表明应该看到产生式右部哪位的符号了，用来对ε进行处理
			int nsig=pro[i1][0].first;//nsig为产生式左部非终极符号的下标
			while(1)
			{
				if(see==pro[i1].size())//也就是当产生式最终推出来只有ε时
				{
					if(first[nsig][eposition]==false) haschanged=true;
					first[nsig][eposition]=true;//产生式左部非终极符号FIRST集包含ε
					break;
				}
				else if(!pro[i1][see].second && pro[i1][see].first!=eposition)
				{//为假时说明此为终极符号并且其不是ε时
					if(first[nsig][pro[i1][1].first]==false) haschanged=true;
					first[nsig][pro[i1][1].first]=true;//此产生式右部第一个终极符号属于产生式左部非终极符号的FIRST集
					break;
				}
				if(!pro[i1][see].second && pro[i1][see].first==eposition) see++;//当前符号为ε时
				else
				{//pro[i1][see].second为真的时候说明此为非终极符号
					bool hase=false;//表明FIRST集里是否包含有ε
					int thesig=pro[i1][see].first;//是当前要看的非终极符号的下标
					for(int i2=0;i2<tCount;i2++)
					{
						if(first[thesig][i2] && i2!=eposition)//如果thesig非终极符号在i2终极符号处FIRST为1
						{
							if(first[nsig][i2]==false) haschanged=true;
							first[nsig][i2]=true;
						}
						else if(first[thesig][i2] && i2==eposition)
						{
							hase=true;
						}
					}
					if(hase) see++;
					else break;
				}
			}
		}//for
		if(haschanged==false) break;
	}
	/*
	//用来检测FIRST集，基本测试没什么问题
	for(int i=0;i<ntCount;i++)
	{
		cout << "FIRST(" << ntToString[i] << ")={";
		for(int j=0;j<tCount;j++)
		{
			if(first[i][j]) cout << tToString[j] << "\t";
		}
		cout << "}\n";
	}
	*/
	//把FIRST集改为紧凑形式的
	vector<int> *FIRST = new vector<int>[ntCount];
	for(int i=0;i<ntCount;i++)
	{
		for(int j=0;j<tCount;j++)
			if(first[i][j]) FIRST[i].push_back(j);
	}
	/*
	for(int i=0;i<ntCount;i++)
	{
		cout << "FIRST(" << ntToString[i] << ")={";
		for(int j=0;j<FIRST[i].size();j++)
			cout << tToString[FIRST[i][j]] << " ";
		cout << "}" << endl;
	}
	*/
	//
	//------------------------------------------------------------------------
	//然后就是构造LR(1)的识别活前缀的DFA，这是个难点

	//首先，求各非终极符号的完全闭包项（存产生式号）
	//我的闭包项是两部分的总合，一部分是产生式左部为此非终极符号，一部分是产生式右部第一个符号是非终极符号时再加入的item
	vector<int> *bibao=new vector<int>[ntCount];
	vector<int> *bibaofirst=new vector<int>[ntCount];//这是记录闭包第一部分的，很有用
	bool **haspro=new bool*[ntCount];
	for(int i=0;i<ntCount;i++)
	{//初始化一下记录非终极符号闭包的bool数组
		haspro[i]=new bool[productionCount];
		for(int j=0;j<productionCount;j++)
			haspro[i][j]=false;
	}
	for(int i=0;i<productionCount;i++)
	{//把闭包第一部分写进来
		int ter=pro[i][0].first;
		haspro[ter][i]=true;
	}
	for(int i=0;i<ntCount;i++)
	{//把bool数组中的值给bibaofirst变量
		for(int j=0;j<productionCount;j++)
		{
			if(haspro[i][j]) bibaofirst[i].push_back(j);
		}
	}
	while(true)
	{//算闭包的第二部分，反复扫描产生式，看右部第一个非终极符号
		bool ischanged=false;
		for(int i=0;i<productionCount;i++)
		{
			int ter=pro[i][0].first;
			if(pro[i][1].second)
			{
				int ter2=pro[i][1].first;
				for(int j=0;j<productionCount;j++)
					if(haspro[ter][j]==false && haspro[ter2][j]==true)
					{
						haspro[ter][j]=true;
						ischanged=true;
					}
			}
		}
		if(!ischanged) break;
	}
	for(int i=0;i<ntCount;i++)
	{//把bool数组中的值给bibao变量
		for(int j=0;j<productionCount;j++)
		{
			if(haspro[i][j]) bibao[i].push_back(j);
		}
	}
/*
	//用来检测一下闭包项
	for(int i=0;i<ntCount;i++)
	{//第一部分
		cout << ntToString[i] << "\t";
		for(int j=0;j<bibaofirst[i].size();j++)
			cout << bibaofirst[i][j] << " ";
		cout << endl;
	}
	cout << endl;
	for(int i=0;i<ntCount;i++)
	{
		cout << ntToString[i] << "\t";
		for(int j=0;j<productionCount;j++)
			if(haspro[i][j]==true) cout << j << "  ";
		cout << endl;
	}
*/
	for(int i=0;i<ntCount;i++)
		delete []haspro[i];
	delete []haspro;
	
	terminal["$"]=tCount++;
	tToString.push_back("$");
	//把界符加入到终极符号中
	vector<DFAnode_struct> DFAnode;
	int DFACount=0;

	item_struct start;
	start.pronum=0; start.pp=0; start.searchnum.push_back(tCount-1);//开始符号的产生式S'->S
	DFAnode_struct newnode;
	newnode.heart.push_back(start);//给第一个状态赋核心项，即为开始产生式
	//计算开始状态的核心项唯一标识
	map<string,int> stateid;//用来存放状态核心项标识
	string caledid=cal_state_id(newnode.heart);
	stateid[caledid]=DFACount++;
	newnode.id=caledid;
	DFAnode.push_back(newnode);
	//对第一个结点的核心写入工作完成，现在开始进行LR(1)DFA的整体计算
	int now_state=0;
	while(now_state<DFAnode.size())
	{
		vector<item_struct> bibao_item;//用来存放当前状态核心项产生的所有闭包项，后来又把核心项也放进去了，放了方便
		DFAnode_struct &nownode=DFAnode[now_state];
		bool *isbibao=new bool[productionCount];//用来记录产生式是不是闭包项，然后都算完了再给bibao_item
		bool **sid = new bool*[productionCount];//用sid来记录闭包项的搜索符
		for(int i=0;i<productionCount;i++)
		{
			sid[i]=new bool[tCount];
			for(int j=0;j<tCount;j++)
				sid[i][j]=false;
		}
		for(int i=0;i<productionCount;i++)
			isbibao[i]=false;
		for(int i=0;i<nownode.heart.size();i++)
		{
			item_struct &theheart = nownode.heart[i];
			if(theheart.pp == pro[theheart.pronum].size()-1)//这时就是归约项了，点到了产生式的最右端
				continue;
			if(pro[theheart.pronum][theheart.pp+1].second)
			{//当核心项目点后为非终极符时，看它的闭包
				int tempnt=pro[theheart.pronum][theheart.pp+1].first;//把非终极符号先记下来
				for(int j=0;j<bibao[tempnt].size();j++)
					isbibao[bibao[tempnt][j]]=true;
			}
		}

		//求核心项传递给闭包项的搜索符
		for(int i=0;i<nownode.heart.size();i++)
		{
			item_struct &theheart = nownode.heart[i];
			//这里要对核心项中的归约项进行处理，否则后面会下标越界退出
			if(theheart.pp == pro[theheart.pronum].size()-1)//这时就是归约项了，点到了产生式的最右端
				continue;

			if(pro[theheart.pronum][theheart.pp+1].second)
			{//只有点后是非终极符的时候才有闭包项
				int tempnt=pro[theheart.pronum][theheart.pp+1].first;//把非终极符号先记下来
				for(int i2=theheart.pp+2;i2<=pro[theheart.pronum].size();i2++)
				{
					bool hase=false;
					if(i2==pro[theheart.pronum].size())
					{
						for(int j=0;j<bibaofirst[tempnt].size();j++)
						{
							for(int k=0;k<theheart.searchnum.size();k++)
								sid[bibaofirst[tempnt][j]][theheart.searchnum[k]]=true;//如果到产生式最右端了就把自己的搜索符加入到目的搜索符中
						}
						break;
					}
					if(pro[theheart.pronum][i2].second==false)//表示点后面的非终极符号的右面是终极符号时，就把这个终极符号加入搜索符
					{
						int tempt=pro[theheart.pronum][i2].first;
						for(int j=0;j<bibaofirst[tempnt].size();j++)
						{
							sid[bibaofirst[tempnt][j]][tempt]=true;
						}
						break;
					}
					else//为非终极符号的情况，把FIRST集放到搜索符中，要注意有ε的时候
					{
						int tempt=pro[theheart.pronum][i2].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[tempnt].size();i4++)
							{
								sid[bibaofirst[tempnt][i4]][FIRST[tempt][i3]]=true;
							}
						}
						if(!hase) break;//FIRST中没有ε的话搜索符就求完了
					}//else
				}//for_i2
			}//if是非终极符号
		}//for_i
		//闭包项传递给闭包项的搜索符
		queue<int> itemqueue;//用来存放要传递搜索符的闭包项，记录的是闭包产生式
		for(int i=0;i<nownode.heart.size();i++)
		{
			item_struct &theheart = nownode.heart[i];
			if(theheart.pp == pro[theheart.pronum].size()-1)//这时就是归约项了，点到了产生式的最右端
				continue;
			if(pro[theheart.pronum][theheart.pp+1].second)
			{//当核心项目点后为非终极符时，看它的闭包
				int tempnt=pro[theheart.pronum][theheart.pp+1].first;//把非终极符号先记下来
				for(int j=0;j<bibaofirst[tempnt].size();j++)
				{
					itemqueue.push(bibaofirst[tempnt][j]);
				}
			}
		}
		//---------------------------------搜索符计算可以了
		while(!itemqueue.empty())//没有更新就退出
		{
			bool haschanged=false;
			int thepro=itemqueue.front();
			itemqueue.pop();
			if(pro[thepro][1].second)
			{//这个闭包产生式右部第一个为非终极符号时{计算搜索符}{若搜索符有改变才加入其bibaofirst中所有项到队列中}
				int thent=pro[thepro][1].first;
				for(int i1=2;i1<=pro[thepro].size();i1++)
				{//计算搜索符
					bool hase=false;
					if(i1==pro[thepro].size())
					{//相等的时候把此产生式的搜索传给闭包项
						for(int i2=0;i2<tCount;i2++)
						{
							if(sid[thepro][i2])
							{
								for(int i3=0;i3<bibaofirst[thent].size();i3++)
								{
									if(sid[bibaofirst[thent][i3]][i2]==false)
									{
										sid[bibaofirst[thent][i3]][i2]=true;
										haschanged=true;
									}
								}
							}
						}
						break;
					}
					if(pro[thepro][i1].second==false)//表示点后面的非终极符号的右面是终极符号时，就把这个终极符号加入搜索符
					{
						int tempt=pro[thepro][i1].first;
						for(int j=0;j<bibaofirst[thent].size();j++)
						{
							if(sid[bibaofirst[thent][j]][tempt]==false)
							{
								sid[bibaofirst[thent][j]][tempt]=true;
								haschanged=true;
							}
						}
						break;
					}
					else//为非终极符号的情况，把FIRST集放到搜索符中，要注意有ε的时候