lexdef.h

基于C++的编译器词法分析模块生成器[Lex]

#include<iostream>
#include<fstream>
#include<hash_map>
#include<string>
#include<list>
#include<map>
#include<stdlib.h>
#include<stack>
#include<vector>
#include<set>
#include<queue>
#include<deque>
#include<windows.h>

/*
由于第一部分处理lex头的代码基本是照抄的，所以这些宏被完整地搬了过来
除此之外还有主文件中int ChechSpecsign(char)，感谢09003209杨俊让
我知道这个程序应该如何入手，在此之前我对程序不知从何做起
*/
#define CHARSTATE_LAYER_ID		15	//标识%%
#define CHARSTATE_HEADER_BEGIN	16	//标识%{%}
#define CHARSTATE_HEADER_END	17	//
#define CHARSTATE_BEGIN			0
#define CHARSTATE_ERROR			-11
#define CHARSTATE_EPSLONG		-1

using namespace std;

//字符集
typedef struct _CHARSET{
	int count;	//字符集容量
	char* set;	//字符集数组
}CHARSET;

//NFA节点以及指向此节点的边
typedef struct _NFANODE{
	char transition;	//到达此状态的动作
	int state;			//状态编号
	bool istrmnl;		//是否为终结态
	bool iskeywd;		//终结态种类
	string action;		//动作
}NFANODE;

/*
定义状态集用于NFA->DFA
*/
typedef set<int> state_set;

/*
DFA节点，包含节点状态号，是否为终结态，还有
终结态对应的动作
*/
typedef struct _DFANODE{
	state_set	s_set;	//它所包含的NFA状态
	bool istrmnl;	//是否为终结态
	bool iskeywd;	//是否为关键字终态
	string action;		//动作
}DFANODE;

//正规表达式中字符串标号(例如alpha)到字符集数组的映射
/*
标号-字符集映射, 例如{alpha}->[a-zA-Z]
字符集就用一个CHARSET结构体(上面有定义)，很傻很强大~
*/
typedef hash_map<string, CHARSET> charset_map;

/*
to use map or to use hash_map, that is a question!
nfa，用邻接表表示，是NFA类的核心数据元素(NFA::this_map)
不知用map还是hash_map，斗争中，等全写好了做个性能测试
*/
typedef list<NFANODE> nfa_state_list;
typedef hash_map<int, nfa_state_list> nfa_map;
//果然上面的数据结构不怎么样，可是又不能改了，只好建个状态索引表补救
typedef hash_map<int, NFANODE> nfa_state_map;

/*
to use map or to use hash_map, that is a question!
dfa，散列映射，是DFA类的核心数据元素(NFA::this_map),
两重全用hash_map是因为hash_map可以直接用[]操作符，
帮助减少代码量。另外出于[]中的全是DFA中的transition，
也就是ASCII字元，所以我想用散列效率会高点，
等写好了做性能测试再做最终决定
*/
typedef hash_map<int, hash_map<char, int> > dfa_map;
//typedef hash_map<char, hash_map<char, DFANODE> > dfamap;

/*
DFA状态到NFA状态集的映射
*/
typedef hash_map<int, DFANODE> state_set_map;

class NFA;
class DFAStateMap;
class DFA;

state_set operator+(state_set &a, state_set &b);
bool operator==(state_set &a, state_set &b);

charset_map charset;

ifstream fin;
ofstream fout;

class NFA{
public:
	/*
	连接方式的枚举声明，这样写很帅，我们算法可以不是最好，但我们的
	代码风格一定要尽量好
	*/
	//连接NFA的方式枚举
	typedef enum _APPEND_MODE {
		APPEND, CYCLE_APPEND
	} APPEND_MODE;
	//输出NFA的方式枚举
	typedef enum _OUTPUT_MODE{
		OUT_TO_FILE, OUT_TO_CONSOLE
	}OUTPUT_MODE;

	NFA();
	//根据一个字符集构造一个NFA，比如{alpha}->NFA
	NFA(const CHARSET &cset);
	/*
	根据一个正规表达式构造一个NFA，它循环调用NFA::NFA(const CHARSET &cset)
	和void NFA::Append(const NFA& nfa, APPEND_MODE mode)实现
	*/
	NFA(const string &re, const string &action);
	/*
	将后者合并到前者，这样做好似前者吞并了后者来实现NFA合并，我喜欢
	*/
	void operator+=(const NFA& nfa);
	/*
	获得这个NFA的字符集，也就是transition(状态转换边上的字符)的全体
	显然不包括EPSLONG，如果你不知道这一点，那你就是没学过编译的人
	*/
	void GetCharset(CHARSET *char_set);
	/*
	获得NFA的状态数,天啊我再也不敢用this_map.size()了……
	*/
	int GetStateCount();
	/*
	获得DFA的第一个状态
	*/
	DFANODE GetFirstDFANode();
	//根据给定状态和转换边得到下一个状态
	DFANODE GetNextDFANode(DFANODE &node, char transt);
	//输出，有3种方式，很强大……
	void Output(const string &title, OUTPUT_MODE mode);
	//建立状态映射集，为了提高生成DFA的效率
	void BuildStateMap();

protected:
	/*
	连接前后两个NFA，根据是否有*决定连接方式是正常连接还是循环连接
	*/
	void Append(const NFA& nfa, APPEND_MODE mode);
	/*
	初始化类属性的值，现在就只有state_count和terminal
	*/
	void InitAttributes();

	/*
	获得初状态集，这个函数不得不说是一个悲剧，因为它仅仅为DFA类服务
	并且只在DFA化的一开始调用一次
	真正“飞鸟尽兮良弓藏，狡兔死兮走狗烹”啊！
	p.s.对了GetFirstStateset()只是GetTranStateset(const state_set &s_set, char transt)
	的特殊情况，不用额外编写代码的，耶，完美解决~
	*/
	state_set GetFirstStateset();
	/*获得状态集经过transt转换边后到达状态的状态集，这个函数就靠调用楼下的两个函数然后合并集合，idiot.*/
	state_set GetTranStateset(state_set &s_set, char transt);
	/*获得状态集经过transt转换边后到达状态的状态集，不包括这些状态经过EPSLONG可以到达的状态*/
	state_set GetNonepslongTranStateset(state_set &s_set, char transt);
	/*获得状态集经过EPSLONG边转换后到达状态的状态集*/
	state_set GetEpslongTranStateset(state_set &s_set);
	/*将一个NFA状态的集合转换为DFA节点*/
	DFANODE GetDFANodeFromStateset(state_set &s_set);
	
private:
	nfa_map this_map;	//图的邻接映射表，核心数据元素
	nfa_state_map state_map;
	int terminal;		//终态编号
	int state_count;	//状态数
};
class DFAStateMap{
public:
	DFAStateMap();
	DFANODE operator[](int index);
	bool has(const DFANODE &node);
	void insert(DFANODE &node);
	int GetMapCount();
	int GetLastIndex();
protected:
private:
	state_set_map this_map;
	int map_count;
	int last_index;
};

class DFA{
public:
	//输出方式的枚举
	typedef enum _OUTPUT_MODE{
		OUT_TO_CODE, OUT_TO_FILE, OUT_TO_CONSOLE
	}OUTPUT_MODE;
	/*由一个NFA构造DFA，NFA确定化的核心所在*/
	DFA(NFA &nfa);
	//这个函数里什么都没有，忽略它吧
	void Minimize();
	void Output(const string &title, OUTPUT_MODE mode);
private:
	dfa_map this_map;
	DFAStateMap state_map;
};

NFA::NFA(){
	InitAttributes();
}
NFA::NFA(const CHARSET &cset){
	InitAttributes();
	this->state_count = 2;
	this->terminal = 1;
	for (int i = 0; i < cset.count; i ++){
		NFANODE node;
		node.transition = cset.set[i];
		node.state = 1;
		node.istrmnl = false;
		node.iskeywd = false;
		this_map[0].push_back(node);
	}
	/*
	以字符集为单位构造一段NFA，这就是臭名昭著的人为给damned fucking shitty terminal添加
	空的自回路的那段代码，现在它就是garbage, now put it into ass of a bull!
	NFANODE node;
	node.transition = CHARSTATE_EPSLONG;
	node.state = 1;
	node.istrmnl = true;
	node.iskeywd = false;
	this_map[terminal].insert(this_map[1].end(), node);
	*/
}
NFA::NFA(const string &re, const string &action){
	InitAttributes();
	switch(re[0]){
	case '{':
		{
			int begin = 0, end = 0;
			while(begin<re.size()&&end<re.size()){
				while(begin<re.size()&&re[begin]!='{') begin++;
				begin++;
				if (begin >= re.size()) break;
				end = begin;
				while(re[end]!='}') end++;
				end++;

				CHARSET char_set = charset[re.substr(begin, end-begin-1)];
				if (end < re.size()){
					NFA temp(char_set);
					if (re[end] == '*') {
						//表示识别循环，并且以循环方式连接到到已有NFA之后
						//cout<<"*append...\n";
						Append(temp, CYCLE_APPEND);
					}
					else {
						//直接方式连接
						//cout<<"normal append...\n";
						Append(temp, APPEND);
					}
				}
				else{
					NFA temp(char_set);
					//直接方式连接，这是当最后一个正规式元素没有循环*的时候，这时候游标已经越界了, omg...
					//cout<<"normal append...\n";
					Append(temp, APPEND);
				}
				begin = end;
			}
			for (int i = 0; i < GetStateCount(); i ++){
				for (nfa_state_list::iterator p = this_map[i].begin(); 
					p!=this_map[i].end(); p++){
						if (p->state == terminal){
							p->iskeywd = false;
							p->istrmnl = true;
							p->action = action;
						}
					}
			}
		}
		break;
	default:
		{
			for (int i = 1; i < re.size()-1; i ++){
				NFANODE node;
				node.transition = re[i];
				node.state = i;
				if (i == re.size()-2){
					node.istrmnl = true;
					node.iskeywd = true;
					node.action = action;
				}
				this_map[i-1].push_back(node);
				state_count++;
			}
			terminal = i-1;
		}
		break;
	}
	/*
	NFA输出到控制台的代码
	Output("traditional output", OUT_TO_CONSOLE);
	NFA没错，这段代码保留为注释
	*/

	/*
	测试GetNonepslongTranStateset(const state_set &s_set)的代码
	Output("traditional output", OUT_TO_CONSOLE);
	state_set s_set;
	s_set.insert(s_set.end(), 0);
	s_set.insert(s_set.end(), 2);
	this->GetNonepslongTranStateset(s_set, '0');
	it works~
	*/

	/*
	测试GetEpslongTranStateset(state_set &s_set)的代码
	Append(*this, NFA::CYCLE_APPEND);
	Output("after self combination", OUT_TO_CONSOLE);
	state_set s_set;
	s_set.insert(s_set.end(),1);
	s_set.insert(s_set.end(),3);
	this->GetEpslongTranStateset(s_set);
	it works~
	*/

	/*
	测试GetDFANodeFromStateSet(state_set &s_set)的代码
	state_set s_set;
	s_set.insert(s_set.end(),1);
	s_set.insert(s_set.end(),3);
	this->GetDFANodeFromStateset(s_set);
	alright~!
	*/

}
/*
把一个非空NFA并入已有的非空NFA，注意是非空，非空，非空！
*/
void NFA::operator+=(const NFA& nfa){
	for (int i = GetStateCount(); i > 0; i --){
		this_map[i] = this_map[i-1];
		for (nfa_state_list::iterator p = this_map[i].begin(); p != this_map[i].end(); p++){
			p->state ++;
		}
	}
	this_map[0].clear();
	NFANODE node;
	node.state = 1;
	node.transition = CHARSTATE_EPSLONG;
	this_map[0].push_back(node);
	this->state_count ++;
	this->terminal ++;
	nfa_map mapping = nfa.this_map;
	int new_terminal = nfa.state_count+state_count;
	node.state = new_terminal;
	node.transition = CHARSTATE_EPSLONG;
	this_map[terminal].push_back(node);
	node.state = state_count;
	node.transition = CHARSTATE_EPSLONG;
	this_map[0].push_back(node);
	for (i = 0; i < nfa.state_count; i ++){
		this_map[i+state_count] = mapping[i];
		for (nfa_state_list::iterator p = this_map[i+state_count].begin();
			p!=this_map[i+state_count].end(); p++){
				p->state+=state_count;
			}
	}
	node.state = new_terminal;
	node.transition = CHARSTATE_EPSLONG;
	this_map[state_count+nfa.terminal].push_back(node);
	terminal = new_terminal;
	state_count += nfa.state_count+1;
	/*
	输出合并后的NFA，看看是否正确
	cout<<"after combination"<<endl;
	for (i = 0; i < GetStateCount(); i ++){
		cout.width(5);cout.setf(ios::left);cout<<i;
		for (nfa_state_list::iterator p = this_map[i].begin(); p != this_map[i].end(); p++){
			cout<<p->transition<<','<<p->state<<' ';
		}
		cout<<endl;
	}
	cout<<"state count: "<<state_count<<endl;
	cout<<"terminal: "<<terminal<<endl;
	事实上输出正确了 oh cool
	*/
}
void NFA::Append(const NFA& nfa, NFA::APPEND_MODE mode){
	switch(mode){
		/*
		这个耗费了我绝大多数时间呢，做LEX大多数时间都跟这个NFA连接较劲ING
		实在是非常畸形
		*/
		case APPEND:
			{
				int states = GetStateCount();
				nfa_map mapping = nfa.this_map;
				if (states==1){
					this_map = mapping;
					terminal = nfa.terminal;
					this->state_count = nfa.state_count;
				}
				else{
					for (nfa_state_list::iterator p = mapping[0].begin();
						p != mapping[0].end(); p++){
							p->state += states-1;
							this_map[terminal].push_back(*p);
					}
					for (int i = 1; i < nfa.state_count; i ++){
						this_map[i+states-1] = mapping[i];
						for (nfa_state_list::iterator p = this_map[i+states-1].begin(); 
							p != this_map[i+states-1].end(); p++){
								p->state += states-1;
						}
					}
					terminal = nfa.terminal+states-1;
					this->state_count += nfa.state_count-1;
				}
			}
			break;
		case CYCLE_APPEND:
			{
				int states = GetStateCount();
				nfa_map mapping = nfa.this_map;
				NFANODE node;
				node.transition = CHARSTATE_EPSLONG;
				node.state = states;
				node.istrmnl = false;
				this_map[terminal].push_back(node);
				for (int i = 0; i < nfa.state_count; i++){
					this_map[i+states] = mapping[i];
					for (nfa_state_list::iterator p = this_map[i+states].begin();
						p != this_map[i+states].end(); p++){
							p->state += states;
					}
				}
				node.transition = CHARSTATE_EPSLONG;
				node.state = terminal;
				node.istrmnl = false;
				this_map[nfa.terminal+states].push_back(node);

				this->state_count += nfa.state_count;
				/*
				用state_count取代this_map.size()的另一个好处就是循环方式插入减少了50%
				的代码量，因为不用分两种该死的情况讨论了，可能一对if..else..不怎么影响性能，
				但看起来着实让人不爽，既简化了逻辑(去掉if..else..)又提高了性能(用GetStateCount()
				代替this_map.size())，何乐不为。。。
				int states = this_map.size();
				nfamap mapping = nfa.this_map;
				if (!states){
					NFANODE node;
					node.transition = CHARSTATE_EPSLONG;
					node.state = states+1;
					node.istrmnl = false;
					this_map[terminal].insert(this_map[terminal].end(), node);
					for (int i = 0; i < mapping.size(); i++){
						this_map[i+states+1] = mapping[i];
						for (nfa_state_list::iterator p = this_map[i+states+1].begin();
							p != this_map[i+states+1].end(); p++){
								p->state += states+1;
						}
					}
					node.transition = CHARSTATE_EPSLONG;
					node.state = terminal;
					node.istrmnl = false;
					this_map[i+states].insert(this_map[i+states].end(), node);
				}
				else{
					NFANODE node;
					node.transition = CHARSTATE_EPSLONG;
					node.state = states;
					node.istrmnl = false;
					this_map[terminal].insert(this_map[terminal].end(), node);
					for (int i = 0; i < mapping.size()-1; i++){
						this_map[i+states] = mapping[i];