myyacc.cpp

自己写的一个简易的YACC程序

				if(nonterminals.find(newit.getcurpath(producers))!=nonterminals.end())Q.push(newit);
			}
			else if(ii->lookhead!=newit.lookhead){//合并
				for(hash_set<int>::iterator k=newit.lookhead.begin();k!=newit.lookhead.end();++k)
				{
					if(ii->lookhead.find(*k)!=ii->lookhead.end())
					ii->lookhead.insert(*k);
				}
				if(nonterminals.find(newit.getcurpath(producers))!=nonterminals.end())Q.push(newit);
			}
		}
	}
}
void grammer::findlook(item& curitem,hash_set<int>& tlook)
{
	if(curitem.nextepsilon(producers[curitem.index])){
		tlook=curitem.lookhead;
	}
	else {
		int nextsym=curitem.getnextSym(producers);
		if(terminals.find(nextsym)!=terminals.end())//是终结符
			tlook.insert(nextsym);
		else{
			/*int pindexstart=ptoindex[nextsym];
			int num=ptosize[nextsym];
			hash_set<int> localNonterminals;
			for(int i=0;i<num;i++)
			{
				if(localNonterminals.find(i);)
			}*/
			for(hash_set<int>::iterator i=myfirst[nextsym].begin();i!=myfirst[nextsym].end();++i)
				tlook.insert(*i);
		
		}
	}
}
/*bool grammer::recurfirst(int producerNumber,hash_set<int>& look,hash_set<int>& Nont)
{
	int cursym=producers[producerNumber]->right[0];
	if(cursym==EPSILON)return true;//epsilon 要特殊处理，返回后在递归途中需要用到判断
	else if(terminals.find(cursym)!=terminals.end()){
		look.insert(cursym);
		return false;
	}
	else if(nonterminals.find(cursym)!=nonterminals.end())//写成else是可以的，我为了调试方便，我防止小错误
	{
		if(Nont.find(cursym)==Nont.end())//这个cursym没有处理过，或者准确的说没有遍历过他的生成式，进行处理
		{
			int j=1;
			Nont.insert(cursym);
			int num=ptosize[cursym];
			int startindex=ptoindex[cursym];
			for(int i=0;i<num;i++)
			{
				if(recurfirst(startindex+i,look,Nont))//返回true表示有epsilon出现，cursym下个一sym要考虑
				{
					while(j<producers[producerNumber]->right.size()){
					int loccursym=producers[producerNumber]->right[j];
					int locnum=ptosize[loccursym];
					int locstart;
					}
				}

			}
		}
	}
}*/
void grammer::first()
{
	check=new bool[numofleft+1];
	for(int i=0;i<=numofleft;++i){
		hash_set<int> temp;
		myfirst.push_back(temp);
		check[i]=false;
	}
	for(int i=0;i<=numofleft;++i)
	{
		if(!check[i]){
			computefirst(i);
			check[i]=true;
		}
	}
}
void grammer::computefirst(int left)
{
	int i=0;
	int index=ptoindex[left];
	int num=ptosize[left];
	bool mark=true;
	int sym;
	while(mark){

		for(int j=0;j<num;j++)
		{//for every producer derive from left
			sym=producers[j+index]->right[i];
			if(sym==EPSILON){
				myfirst[left].insert(EPSILON);
			}
			else if(terminals.find(sym)!=terminals.end()){
				myfirst[left].insert(sym);
				//mark=false;
			}
			else{
			
			/*if(check[sym])//已经求过first了
			{
				for(hash_set<int>::iterator k=myfirst[sym].begin();k!=myfirst[sym].end();++k)
				myfirst[left].insert(*k);
				//if(isepsilon[sym])mark=true;
			}
			else{
				getfirst(sym);
				myfirst[left].insert
				}*/
				if(!check[sym]){
					computefirst(sym);
					check[sym]=true;
				}
				for(hash_set<int>::iterator k=myfirst[sym].begin();k!=myfirst[sym].end();++k)
					myfirst[left].insert(*k);
				//if(isepsilon[sym])++i;
			}
			
		}
		if(nonterminals.find(sym)!=nonterminals.end()&&isepsilon[sym])++i;
		else mark=false;
	}
}
bool grammer::creattable()
{
	int i,j;
	FAstate* curstate;
	int row=finalstates.size();
	table=new int*[row];
	int s1=terminals.size();
	int s2=nonterminals.size();
	int s=s1+s2;
	for(i=0;i<row;i++)
		table[i]=new int[s];
	for(i=0;i<row;i++)
		for(j=0;j<s;j++)
			table[i][j]=-1;//初始化为-1，这样以后查表时也方便表示无效项（出错项）
	hash_map<int,int> toindex;
	int index=-1;
	hash_set<int>::iterator ii;
	for(ii=terminals.begin();ii!=terminals.end();++ii)toindex[*ii]=++index;
	for(ii=nonterminals.begin();ii!=nonterminals.end();++ii)toindex[*ii]=++index;
	int r=producers.size();
	//为了在表中明确表示出shift，reduce，和goto，goto处直接填入状态的号，reduce处填入s+producer的号，shift处填入s+r+状态号
	//这样很好的分开了，可以区分三种，而我们的accpet则用r+s+row表示
	int curID;
	for(i=0;i<row;i++)
	{
		//cout<<endl;
		curstate=finalstates[i];
		curID=curstate->stateID;
		//cout<<row<<endl;
		if(curstate->trans.size()==0)//reduce
		{
			//int id=curstate->stateID;;
			ItemSet itemset=statetoset[curID];
			ItemSet::iterator itr=itemset.begin();
			int destate=curstate->stateID;
			if(itemset.size()>1)return true;//调试时用
			for(hash_set<int>::iterator j=(*itr).lookhead.begin();j!=(*itr).lookhead.end();++j)
			{
				int token=(*j);
				index=toindex[token];
				table[curID][index]=s+(*itr).index;
				
			}
			
		}
			//这里认为无规约/规约冲突产生1
			/*for(;i!=itemset.end();++i)
			{
				//规约/规约冲突
			}*/

		else {
			for(hash_map<int,int>::iterator j=curstate->trans.begin();j!=curstate->trans.end();++j)
			{
				int path=(*j).first;
				index=toindex[path];
				int dstate=(*j).second;
				if(terminals.find(path)!=terminals.end())//it is a token
					table[curID][index]=s+r+dstate;
				else if(nonterminals.find(path)!=nonterminals.end())//nonterminal
					table[curID][index]=dstate;
				//cout<<i<<"\t"<<table[curID][index];
			}
		}
	}
	return true;
}


bool grammer::dealtoken(char* curline)
{
	int i=7;//
	while(curline[i]!='\0')
	{
		string sub;//希望默认的回收有析构，否则会有错误
		while(curline[i]!=' '&&curline[i]!='\t'&&curline[i]!='\0')
		{
			sub.push_back(curline[i]);
			++i;
		}
		tokenmap[sub]=tokenstart;
		terminals.insert(tokenstart);
		++tokenstart;
		if(curline[i]=='\0')break;
		else
			++i;
	}
	return true;
}

void grammer::getabh()
{
	//ofstream out("yy.tab.h");

	//out.close();
}
void grammer::displaytab()
{
	ofstream out("table.txt");
	int row=finalstates.size();
	int s1=terminals.size();
	int s2=nonterminals.size();
	int s=s1+s2;
	int r=producers.size();
	char* temp=new char[100];
	for(int i=0;i<row;i++)
	{
		out<<endl;
		for(int j=0;j<s;j++)
		{
			int t=table[i][j];
			string sub;
			if(t==-1)sub="e";
			else if(t<s)//goto
				sub="gt "+string(itoa(t,temp,10));
			else if(t<s+r)//reduce
				sub="r "+string(itoa(t-s,temp,10));
			else //shift
				sub="s "+string(itoa(t-s-r,temp,10));
			out<<sub<<"\t";
		}
	}
}
void grammer::displayusetable()
{
	ofstream out("forusetable.txt");
	int row=finalstates.size();
	int s1=terminals.size();
	int s2=nonterminals.size();
	int s=s1+s2;
	int r=producers.size();
	char* temp=new char[100];
	for(int i=0;i<row;i++)
	{
		out<<endl;
		for(int j=0;j<s;j++)
		{
			out<<table[i][j]<<" ";
		}
	}
}
void grammer::displayfirst()
{
	ofstream out("firstcheck.txt");
	for(hash_map<string,int>::iterator i=lefts.begin();i!=lefts.end();++i)
	{
		out<<(*i).first<<": ";
		for(hash_set<int>::iterator j=myfirst[(*i).second].begin();j!=myfirst[(*i).second].end();++j)
			out<<(*j)<<"\t";
		out<<endl;
	}
}
		
bool grammer::dealunion(ifstream& input)
{
	return true;
	//暂时我不写，没时间了啊，可怜啊 我再也不相信女人了
}
bool grammer::dealleft(char* curline)
{
	return true;
	//同上
}
bool grammer::dealnonassoc(char* curline)
{
	return true;
	//同上
}
bool grammer::dealright(char* curline)
{
	return true;
}
bool grammer::dealtype(char* curline)
{
	return true;
	//同上
}
bool grammer::generatecode()
{
	return true;
}
int main()
{
	ifstream input("cminus.yy");
	grammer g;
	g.begin(input);
	g.displaytab();
	g.displayfirst();
	g.displayusetable();
	return 1;
}