myyacc.h

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

#include<vector>
#include<hash_set>
#include<hash_map>
#include<set>
#include<string>
#include<fstream>
#include<string>
#include<vector>
#include<iostream>
using namespace stdext;
using namespace std;
#define TOKENSTART 2000//我大概写的，估计应该够用了吧，不够再改，寒阿，这叫拆东墙补西墙
#define ERROR -1
#define EPSILON 1000
#define SEGMENT_DELIM 998
#define DEF_SEG_BEGIN 997
#define DEF_SEG_END 996
#define TOKEN 995
#define TYPE 994
#define UNION 993
#define LEFT 992
#define RIGHT 989
#define ENDMARK 984
#define BUFSIZE 400000
#define LSIZE 100
#define HSIZE 10000
#define NONASSOC 983 
//using namespace std;//remenber that the hash_set and hash_map is not contained in the C++ standard library
struct producer{
	int left;
	vector<int> right;
};
class item{	
public:
	item(int producerIndex,int pointPos){
		index=producerIndex;
		pp=pointPos;
		//end=false;
	};
	bool nextepsilon(producer*p){if(pp==p->right.size()-1)return true;else return false;};
	int getcurpath(vector<producer*>&);
	int getnextSym(vector<producer*>&);
	bool end(vector<producer*>&);//如果point位置在结尾，则为true；
	int pp;//point position;
	int index;//the index of production;
	hash_set<int> lookhead;//规约时需要用的
	int stateID;//这样加实在是浪费了空间，我估算了一下，浪费3*4*N B空间，但换来了时间的O（1）定位，其实我定义好结构也可以，来不及了啊
	
	
};
struct FAstate{
	FAstate(int id){stateID=id;};
	int stateID;
	hash_map<int,int> trans;
};
bool operator <(const item &it1,const item &it2)
{
	if(it1.index==it2.index)
	{
		if(it1.pp==it2.pp)
			return it1.lookhead<it2.lookhead;
		else return it1.pp<it2.pp;
	}
	else 
		return it1.index<it2.index;
}
bool operator!=(const item &it1,const item& it2)
{
	if(it1<it2||it2<it1)return true;
	else return false;
}
struct mycompare
{
	bool operator()(const item& it1,const item& it2)const
	{
		if(it1.index==it2.index)
			return it1.pp<it2.pp;
		else 
			return it1.index<it2.index;//这样定义为了closure节省了合并相同p和pp但lookhead不同的项
	}
};
typedef set<item,mycompare> ItemSet;
/*bool operator<(const ItemSet& itemSet1,const ItemSet& itemSet2)
{
	if(itemSet1.size()==itemSet2.size())
	{
		ItemSet::const_iterator i=itemSet1.begin();
		ItemSet::const_iterator j=itemSet2.begin();
		while(i!=itemSet1.end())
		{
			if((*i)<(*j))return true;
			
			++i;
			++j;
		}
		return false;
	}
			
	else
		return itemSet1.size()<itemSet2.size();
}*/

struct mycompare2
{
	bool operator()(const ItemSet& itemSet1,const ItemSet& itemSet2)const
	{
		if(itemSet1.size()==itemSet2.size())
		return itemSet1<itemSet2;
		else return itemSet1<itemSet2;
	}
};


class grammer{
private:
	int** table;
	int realstart;
	int tokenstart;
	vector<bool> isepsilon;//为了生成first时方便所以记录了生成epsilon的表达式
	//vector<itme*> items;
	ItemSet itemSet;//LR核生成时用到
	//map<int,ItemSet,mycompare2> stateToSet;
	vector<ItemSet> finalStateSet;
	vector<FAstate*> finalstates;
	set<ItemSet> stateSet;
	hash_map<int,ItemSet> statetoset;
	int curleft;
	hash_map<int,int> ptoindex;//将对应的left映射为在producers中的位置，第一个位置
	hash_map<int,int> ptosize;//将对应的left与其所拥有的producer的数量建立映射，可直接访问
	hash_map<string,int> lefts;//将读入的left的串声称为一个代表其的int字段
	hash_map<string,int> tokenmap;//将token的串映射到对应的值
	//hash_map<ItemSet,int> settostate;//临时加的，寒阿
	hash_set<int> terminals;
	hash_set<int> nonterminals;//将yacc文件中所有的终结符合非终结符的存下来，做first时用到 
	vector<hash_set<int>> myfirst;//这样映射很直接，我不想用太多的hash映射，能从最直接的最好

	//hash_map<int,ItemSet> pathtoset;//将path对应到itemSet去，为了找到已经存在的itemSet，move动作时用到
	vector<producer*> producers;
	int numofproducers;
	int numofleft;
	int nextStateID;
	bool* check;
	hash_map<int,int> toindex;//构造表时用，为了能将nonterminal和terminal与表的列下表对应上
public:
	grammer(){table=0;producers=vector<producer*>(0);tokenstart=TOKENSTART;};
	bool begin(ifstream&);
	bool dealproducer(int,string,int);
	void display();
	void erro(int linenumber){cout<<"erro happen in line: "<<linenumber<<endl;};
	int strtoint(string curstr);//将当前string转换为对应的int用来生成producer时用到
	bool dealunion(ifstream&);
	bool dealtoken(char*);
	bool dealleft(char*);
	bool dealright(char*);
	bool dealnonassoc(char*);
	bool dealtype(char*);
	void getabh();
	bool generatecode();
	//void creatLRK();
	//void creatLALR();
	bool creatLR();
	bool creattable();
	void closure(ItemSet& curSet);
	ItemSet& move(ItemSet& s,int trans);
	void findlook(item& curitem,hash_set<int>& tlook);
	bool recurfirst(int producerNumber,hash_set<int>&look,hash_set<int>& Nont);//递归去寻找某个left对应的某个producer所对应fisrt（left）
	//bool isterminal(int);
	bool isnonterminal(int);//写两个浪费了，但调试时方便，防止出现处理不到的整数值
	void first();//把所有的first处理好，以备在闭包时用
    void computefirst(int left);
	void displaytab();
	void displayfirst();
	void displayusetable();

};