yacc.cpp

语法分析器lex和词法分析器yacc的C++语言实现 1.Lex （1）Lex输入文件的解析 （2）正规表达式的解析 （3）一个正规表达式到NFA的转换算法实现 （4）多个NFA的合并

#include<iostream>
#include<iomanip>
#include<fstream>
#include<string>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<hash_set>
#include<hash_map>
#include<map>
#include<set>
#include<conio.h>
#define ACCEPT 0
#define ERROR 40000
#define EPSLONG 39999
#define SEGMENT_DELIM 39998
#define DEF_SEG_BEGIN 39997
#define DEF_SEG_END 39996
#define TOKEN 39995
#define TYPE 39994
#define UNION 39993
#define LEFT 39992
#define TERMINATE 39991
#define NOMATCH 39000
#define RIGHT 38999
#define SEGMENT_REG 38998
#define SELF_DEF 38997
#define NONTERMINS 35000
#define TERMINS 30000
using namespace std;
struct Producer
{
	int left;
	vector<int> right;
};
ifstream fin;
ofstream fout;
ofstream sout;
ofstream hout;
char NO=1;
//一些常量的定义
vector<Producer> producerSet;//存储所有产生式的向量，在读入产生式时进行初始化！
hash_map<int,vector<int> > hpSet;//以产生式的左部为关键字，以对应产生式的编号为内容的哈希表。
hash_map<int,int> terminSet;//存储终结符,***并且要在其中加入结束符号#
hash_map<int,int> nonterminSet;//存储非终结符,并同时存储一个到action表头的对应关系
vector<vector<int> > actionTable;//存储动作表，其中第二维大小必须已知。
//目前打算人为规定，产生的非终态符的符号的数值范围。
hash_map<string,int> tsymTable;//这个表是终结符的串到相应数字编码的映射
hash_map<string,int> ntsymTable;
hash_map<int,int> precedenceTable;//优先级表
vector<int> producerPreTable;//产生式的优先级表，和上面的优先级表联合使用
hash_set<int> leftTable;//左结合表
hash_set<int> rightTable;//右结合表
hash_map<int,string> symclaTable;//存储语义值类型的表
vector<string> produceActionTable;//存储语义动作的表
//class ItemLess;//函数对象Item的小于算子
//关于类Item的定义
class Item
{
public:
	//friend class ItemLess;
	friend bool operator <(const Item &it1,const Item &it2);
	Item(int producerNum,int currentPos);
	int getCurrSym();//返回下一个将要移进的符号，如果已经到达最后，则返回-1，表示可归约。
	int getNextSym() const;//返回再一下要移进的符号，在求闭包运算中计算搜索符时使用。
	int getProdN();//返回产生式的编号。
	bool isEnd();//是否右部已经全部移进。
	bool nextIsEnd() const;//右部是否到达最后一个符号，求闭包运算时用。
	void setSearchSym(const hash_set<int> &searchSymbol);
	const hash_set<int> &getSearchSym() const;
	void move();
private:
	
	int pn;//存储产生式的编号。
	int pos;//存储此项目的移进位置。
	hash_set<int> searchSym;//存储此项目的搜索符，作为公共可以让外部函数first直接使用
};



//关于类Item的具体函数定义如下
//........
Item::Item(int producerNum,int currentPos)
{
	this->pn=producerNum;
	this->pos=currentPos;
}
int Item::getCurrSym()
{
	return producerSet[pn].right[pos];//返回产生式右部下一移进符号
}
int Item::getNextSym() const
{
	return producerSet[pn].right[pos+1];
}
int Item::getProdN()
{
	return this->pn;
}
bool Item::isEnd()
{
	if(producerSet[pn].right[0]==EPSLONG)
		return true;
	if(this->pos==producerSet[pn].right.size())
		return true;
	return false;
}
bool Item::nextIsEnd() const
{
	if(this->pos==producerSet[pn].right.size()-1)
		return true;
	return false;
}
void Item::setSearchSym(const hash_set<int> &searchSymbol)
{
	searchSym=searchSymbol;
}

const hash_set<int> &Item::getSearchSym() const
{
	return searchSym;
}

void Item::move()
{
	pos++;
	return;
}


bool operator <(const Item &it1,const Item &it2)
{//此处的<算子定义很关键，一定要满足偏序性
	if(it1.pn==it2.pn)
	{
		if(it1.pos==it2.pos)
			return it1.getSearchSym()<it2.getSearchSym();
		else return it1.pos<it2.pos;
	}
	else return it1.pn<it2.pn;
}
//

//函数的声明
void closure(set<Item> &itemSet);
//下面是求first的函数,参数为产生式编号，first符号集，已出现非终结符号集
//此为递归函数，为外部不可调用
void first(const Item &item,hash_set<int> &searchSymbol);
//下面是外部可调的first函数
bool getfirstSet(int producerNum, hash_set<int> &firstSet, hash_set<int> &isUsed);
bool produce();//产生项目集之间的转换关系
void generateTableCode();
void generateParseCode();
void generateSemanticActionCode();//生成语义动作函数
void generateMainCode();
void generateHead();
void generateSVCode();//产生给终结符赋默认值 的代码:void getvalue();
int readInputFile();//前段输入部分的主要函数，用于读入文件并处理
int specSymParse();
bool readReg();//规则段的扫描程序
bool readAproducer();//读取一个产生式
void genhpSet();
void outSignalTable();
void displayI(Item & item);
////////////////////////////////////////////////////////////////////
//主函数　　
///////////////////////////////////////////////////////////////////
void main() 
{
	string inputname;
	cout<<"Please input the file name:\n";
	cin>>inputname;
	fin.open(inputname.c_str());

	//fin.open("test2.txt");
	fout.open("yyparse.cpp");
	sout.open("signal_table.txt");//生成符号表的头文件
	hout.open("yytab.h");//生成全局符号语义值变量的类型
	if(fout.fail()||fin.fail()||sout.fail()||hout.fail())
	{
		cout<<"Cannot open output file!"<<endl;
		return;
	}
	//初始化
	Producer ap;
	producerSet.push_back(ap);//首先把拓展方法开始符号放入
	readInputFile();
	generateMainCode();
	outSignalTable();
	cout<<"Finish!\n";
}
void outSignalTable()
{
	hout<<"\n#ifndef YYTAB_H\n";
	hout<<"#define YYTAB_H\n";
	sout<<setw(20)<<"SIGNAL"<<setw(20)<<"VALUE"<<endl;
	sout<<setfill('=')<<setw(41)<<" "<<setfill(' ')<<endl;
	int num=0;
	for(hash_map<string,int>::iterator pi=tsymTable.begin();pi!=tsymTable.end();pi++)
	{
		string delim("~!@#$%^&*()-=+`{}[]\|'\":;/?.,<>");
		int x=pi->first.find_first_of(delim);
		if(x<0||x>=pi->first.size())
		{
			hout<<"#define"<<setw(20)<<pi->first<<setw(20)<<pi->second<<endl;
		}
		sout<<setw(20)<<pi->first<<setw(20)<<pi->second<<endl;
		num++;
	}
	sout<<setfill('=')<<setw(41)<<" "<<setfill(' ')<<endl;
	sout<<setw(20)<<"TOTAL:"<<num<<endl;
	hout<<"#endif\n";
}


void closure(set<Item> &itemSet)
{
	queue<Item> Q;
	//首先要把当前项目集中所有状态放入到队列中。(除去不会产生新项的项)
	for(set<Item>::iterator ps=itemSet.begin();ps!=itemSet.end();ps++)
	{
		//cout<<"in closure "<<ps->getCurrSym()<<endl;
		if(!ps->isEnd()&&nonterminSet.count(ps->getCurrSym()))
			Q.push(*ps);
	}
	//进入循环判断。
	hash_set<int> isU;
	hash_set<int> isE;
	while(!Q.empty())
	{
		Item citem=Q.front();
		Q.pop();
		vector<int> vpi=hpSet[citem.getCurrSym()];
		hash_set<int> searchSym;
		first(citem,searchSym);//此步完成搜索符的计算	
		for(int i=0;i<vpi.size();i++)
		{
			Item tp(vpi[i],0);
			tp.setSearchSym(searchSym);
			if(!itemSet.count(tp))//如果此项目不在项目集中，则需将它加入到项目集中去。
			{                //同时需要进行相应的搜索符的计算。
				itemSet.insert(tp); 
				if(nonterminSet.count(tp.getCurrSym()))
				{
					Q.push(tp);
				}
			}
		}
	}
}

void first(const Item &item,hash_set<int> &searchSymbol)
{
	if(item.nextIsEnd())
	{
		searchSymbol=item.getSearchSym();
	}
	else 
	{
		int sym=item.getNextSym();
		if(terminSet.count(sym))
			searchSymbol.insert(sym);
		else
		{
			vector<int> tv=hpSet[sym];
			hash_set<int> isused;
			for(int i=0;i<tv.size();i++)
			{
				getfirstSet(tv[i],searchSymbol,isused);
			}
		}
	}
}
bool getfirstSet(int producerNum, hash_set<int> &firstSet, hash_set<int> &isUsed)
{
	if ( producerSet.at(producerNum).right[0] == EPSLONG )
		return 0;
	else {
		int i = 0;
		if ( terminSet.count ( producerSet.at(producerNum).right[i] ) )
			firstSet.insert( producerSet.at(producerNum).right[i] );
		else if ( nonterminSet.count ( producerSet.at(producerNum).right[i] ) )
			{
			if ( !isUsed.count( producerSet.at(producerNum).right[i]) )
				{
				isUsed.insert ( producerSet.at(producerNum).right[i] );
				vector < int > tv;
				tv = hpSet[ producerSet.at(producerNum).right[i] ] ;
				vector < int >::const_iterator p1;
				int c = 1;  // 
				for ( p1 = tv.begin(); p1 != tv.end(); p1++ )
				{  
					if(!getfirstSet ( *p1, firstSet, isUsed ))
						{
						c=0;
						}
				}
				while( c == 0 ) 
					{
					i++;
					if ( producerSet.at(producerNum).right[i]!=0 &&
						 nonterminSet.count ( producerSet.at(producerNum).right[i]) &&
						 isUsed.count ( producerSet.at(producerNum).right[i] ) == 0)
						 {
						vector < int > tv2;
						tv2 = hpSet [ producerSet.at(producerNum).right[i] ] ;
						vector < int >::const_iterator p2;
						for (p2 = tv2.begin(); p2 != tv2.end(); p2++ )
							if(!getfirstSet ( *p2, firstSet,isUsed ))
								c=0;
					}
					else if ( terminSet.count ( producerSet.at(producerNum).right[i] ) )
						firstSet.insert ( producerSet.at(producerNum).right[i] );
				}
			}
		}
		return 1;
	}
}

void display(set<Item> & i0)
{
	cout<<"\n----------------ItemSet ---------------------"<<endl;
	for(set<Item>::iterator pi=i0.begin();pi!=i0.end();pi++)
	{
		cout<<pi->getProdN()<<"--"<<pi->getCurrSym()<<"  SEARCH:";
		for(hash_set<int>::const_iterator i=pi->getSearchSym().begin();i!=pi->getSearchSym().end();i++)
			cout<<*i<<" ";
		cout<<"||"<<endl;
	}
	cout<<"\n------------------------\n";
}

void displayI(Item & item)
{
	cout<<"\nitem -----------------------------\n";
	cout<<"PID:"<<item.getProdN()<<endl;
	cout<<"LEFT:"<<producerSet[item.getProdN()].left<<endl;
	cout<<"RIGHT:";
	for(int i=0;i<producerSet[item.getProdN()].right.size();i++)
	{
		cout<<producerSet[item.getProdN()].right[i]<<"  ";
	}
	cout<<"\nSEARCH:";
	for(hash_set<int>::const_iterator i=item.getSearchSym().begin();i!=item.getSearchSym().end();i++)
	{
		cout<<*i<<"  ";
	}
	cout<<"\n-----------------------------------\n";
}
void genhpSet()
{
	for(int i=1;i<producerSet.size();i++)//0号产生式不用管
	{
		if(!hpSet.count(producerSet[i].left))
		{
			pair<int,vector<int> > tp;
			tp.first=producerSet[i].left;
			vector<int> vt;
			tp.second=vt;
			hpSet.insert(tp);
		}
		hpSet[producerSet[i].left].push_back(i);
	}
}
bool produce()
{
	/**
	 *  此处考虑图的表示方法为二维数组，因为在输出时也是以二维数组的形式。
	 *  在此数组中，用正数表示要跳转的状态号，用负数表示某一待归约的产生式号。
	 *  DONE!
	 */
	//首先是一组要用到的常量定义
	int curState=0;//存储项目集的状态号。随项目集的产生动态更新
	int widgeN=nonterminSet.size()+terminSet.size();//表示所有可能的项目集的边
	queue<set<Item> > Q;
	map<set<Item>,int> itemsetTable;//从项目集到某一数字标识的映射
	hash_map<int, set<Item> > moveItemset;//以边为关键字，以进行分类的项目的项目集为内容。
	set<Item> I0;

	Item firstitem(0,0);//定义初始项目集中的项目。
	hash_set<int> searchs;
	searchs.insert(NONTERMINS-1);//表示结束状态
	firstitem.setSearchSym(searchs);

	I0.insert(firstitem);

	firstitem.move();//修改其移进位，因为在后面输出正确状态时要用

	closure(I0);
	Q.push(I0);

	display(I0);
	pair<set<Item>,int> te;//将项目集0放入到项目集的表中
	te.first=I0;
	te.second=curState;
	itemsetTable.insert(te);

	while(!Q.empty())
	{
		set<Item> itemset=Q.front();
		Q.pop();//从队列中取得一个项目集。
		moveItemset.clear();//清空，以进行新一轮循环

		vector<int> f(widgeN);//数组第二维的大小必须预先定义好
		for(int i=0;i<f.size();i++)
		{
			f[i]=ERROR;//以ERROR值对vector进行初始化。
		}

		actionTable.push_back(f);

		int column,row;
		row=itemsetTable[itemset];
		cout<<"\n===================================================================\n";
		//display(itemset);
		cout<<"state = "<<row<<endl;
		cout<<"\n===================================================================\n";

		//开始求它的所有项目的move后的项目集。te
		for(set<Item>::iterator ps=itemset.begin();ps!=itemset.end();ps++)
		{
			if(ps->isEnd())//出现可归约项目，需进行处理。
			{
				for(hash_set<int>::const_iterator pi=ps->getSearchSym().begin();pi!=ps->getSearchSym().end();pi++)
				{
					//对可归约项目，对其中每个搜索符都填入表中
					column=terminSet[*pi];
					if(actionTable[row][column]<=0&&ps->getProdN()!=actionTable[row][column]*(-1))
					{
						cout<<"Reduction & Reduction Confliction"<<endl;
						cout<<"row="<<row<<" column="<<column<<" old="<<actionTable[row][column]
					       <<" new="<<ps->getProdN()<<endl;
						return false;
					}
					actionTable[row][column]=ps->getProdN()*(-1);//变成负数以表示此为归约项,如果为0用于表示accept
					//cout<<"actionTable row="<<row<<" column="<<column<<endl;
				}
			}
			else
			{
				Item tp=*ps;
				tp.move();
				moveItemset[ps->getCurrSym()].insert(tp);
			}
		}
		//对所有新产生的项目集求闭包并判断是否需要加入到队列中去。
		for(hash_map<int,set<Item> >::iterator ph=moveItemset.begin();ph!=moveItemset.end();ph++)
		{
			if(curState==75)
			{
				cout<<"wa";
			}
			closure(ph->second);