lex.cpp

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

#include<iostream>
#include<fstream>
#include<string>
#include<hash_map>
#include<stack>
#include<vector>
#include<list>
#include<set>
#include<queue>
#include<map>
#define LAYER_ID 15//标识%%
#define HEADER_BEGIN 16//标识%{%}
#define HEADER_END 17//
#define BEGIN 0
#define ERROR -11
#define EPSLONG -1
using namespace std;
//定义结点结构
struct Node
{
	unsigned int value;
	unsigned int state;
};
//定义一组常量
ifstream ifile;
ofstream ofile;
int lineno=0;
vector<list<Node> > nfa;
vector<list<Node> > dfa;
hash_map<string,string> id2reTable;//存储定义段中标识名到正则式的映射
hash_map<int,int> nfaTer2Action;//存储NFA终态到action表头对应内容。
hash_map<int,int> dfaTer2Action;//存储DFA终态到action表头对应内容，其中内容在Nfa2Dfa()时填充
vector<string> actionTable;//存储action内对应内容
vector<int> nfaIsTer;
map< set<int>,int > dfanodetable;
vector<int> dfaIsTer;//标记dfa中哪些是终结态。


//定义一些函数
int checkSpecsign(char c);
void compleRe(string &re);
void produceNfa(const string & re,vector<list<Node> > &tnfa,vector<int> &isTer,int index);
void modifyTer(vector<int> &is_t,unsigned int state,int value);
void joinNfa(vector<list<Node> > &nfa1,const vector<list<Node> > &nfa2);
void joinIster(vector<int> &is_t1,const vector<int> &is_t2);
void Nfa2Dfa();
void Eclosure(set<int> &T);
set<int> move(const set<int> &I,int value);
int dfaIsTerminated(set<int> &I);//返回终态对应动作，如果是非终态返回-1
void minidfa();
void genAnalysisCode();//生成词法分析部分的代码
bool cmpList(const list<Node> &l1,const list<Node> &l2);

void main()
{
	string s;
	cout<<"Please input the inputfile name!"<<endl;
	cin>>s;
	ifile.open(s.c_str(),ios::in);
	cout<<"Analysing source......"<<endl;
	ofile.open("yylex.cpp",ios::out);
	if(!ifile.good())
	{
		cerr<<"Open the file error!"<<endl;
		return;
	}
	char c=ifile.get();
	int state=checkSpecsign(c);
	//判断开头是不是%{
	if(state!=HEADER_BEGIN)
	{
		cout<<"The input file has no correct formation,Please try again!\n";
		return;
	}
	//判断到%}或到文件尾为止进行扫描
	while(!ifile.eof()&&state!=HEADER_END)
	{
		c=ifile.get();
		if(c=='\t') continue;//跳过\t字符不输出。
		if(c=='%') {state=checkSpecsign(c);continue;}//当接受到%时，注意判断是不是特殊符号
		if(c=='\n') lineno++;//让行号自增，用以判断错误行号。
		ofile.put(c);
	}
	//以上完成定义段中%{ %}之间的扫描
	//以下开始对定义好的关键字的正规表达式的扫描，并将其存储到表中
	ifile.get();
	pair<string,string> pi;
	state=BEGIN;
	
	while(!ifile.eof()&&state!=LAYER_ID)//此处的处理有问题，需要做进一步调整。
	{
		c=ifile.get();
		if(c=='%')
		{
			state=checkSpecsign(c);
			if(state==ERROR)//用户自定义的标识符不可以含有此特殊字符%。
			{
				cerr<<"There is an error in line "<<lineno<<" !"<<endl;
				return;
			}
			continue;//跳过下面的正常串的处理，因为已经到终结。
		}
		else
		{
			ifile.unget();//如果不是特殊字符%，把当前字符放回流中。
		}
		string id,re;
		ifile>>id>>re;
		pi.first=id;
		pi.second=re;
		id2reTable.insert(pi);
		lineno++;
		ifile.get();
	}
	//以上是对定义段的扫描
	//以下是对规则段的扫描解析
	state=BEGIN;
	actionTable.push_back("begin");//使action表从1号单元开始，便于处理。
	ifile.get();
	while(!ifile.eof()&&state!=LAYER_ID)
	{
		c=ifile.get();
		if(c=='%')
		{
			state=checkSpecsign(c);
			if(state==ERROR)//用户自定义的标识符不可以含有此特殊字符%。
			{
				cerr<<"There is an error in line "<<lineno<<" !"<<endl;
				return;
			}
			continue;//跳过下面的正常串的处理，因为已经到终结。
		}
		else
		{
			ifile.unget();//如果不是特殊字符%，把当前字符放回流中。
		}
		string onestr;
		string re,action;
		//假设一个动作只能写在一行内。
		getline(ifile,onestr);
		string delim=" \t";
		size_t offset=onestr.find_first_of(delim);
		re=onestr.substr(0,offset);
		while(onestr[offset]==' '||onestr[offset]=='\t') offset++;
		action=onestr.substr(offset,onestr.size()-offset);
		actionTable.push_back(action);
		//下面开始正则表达式的扫描替换,即把当中含有用户自定义标识符的地方替换成完整的正则式
		compleRe(re);
		//替换完毕，下面开始依据正则式构造NFA
		vector<list<Node> > nfa1;
		vector<int> isTer;
		int actionTableIndex=actionTable.size()-1;
		produceNfa(re,nfa1,isTer,actionTableIndex);//产生nfa，及相应的终态表
		joinNfa(nfa,nfa1);//合并nfa
		unsigned int adjustp=nfaIsTer.size();
		joinIster(nfaIsTer,isTer);//合并状态表
		//保存action的内容
		for(unsigned int i=adjustp;i<nfaIsTer.size();i++)
		{
			if(nfaIsTer[i])
			{
				pair<int,int> p;
				p.first=i;
				p.second=actionTable.size()-1;
				nfaTer2Action.insert(p);
			}
		}
	}
	//到此一个大的NFA完成了，存储在nfa中。
	Nfa2Dfa();//生成了dfa，放在dfa这个vector中。
	minidfa();//在这个函数中完成了对dfaTer2Action表的修改。
	cout<<"Generating code......"<<endl;
	genAnalysisCode();
	//下面开始是最后一段，即用户自定义子例程段的输出。
	c=1;
	while((c=ifile.get())!=-1)
	{
		ofile.put(c);
	}
	ifile.close();
	ofile.close();
	cout<<"Done!"<<endl;
}

int checkSpecsign(char c)
{
	if(c=='%')
	{
		char cc=ifile.get();
		switch(cc)
		{
		case '%':
			return LAYER_ID;
		case '{':
			return HEADER_BEGIN;
		case '}':
			return HEADER_END;
		default:
			ifile.unget();
			break;
		}
	}
	return ERROR;
}

void compleRe(string &re)
{
	//此处应当注意一个问题，即如何避免死循环的出现
	//当用户自定义的标识符出现循环嵌套定义时，如何进行识别处理或报错。
	stack<int> status;//状态栈
	status.push(-1);
	unsigned int i=0;
	while(i<re.size())
	{
		if(re[i]=='{')
			status.push(i);//记录下此时的位置
		if(re[i]=='}')
		{
			int prei=status.top();
			if(prei<0) 
			{
				i++;
				continue;//表示此时的}并无配对，因此直接输出
			}
			int length=i-prei-1;
			string id=re.substr(prei+1,length);
			string replacestr=id2reTable[id];
			if(replacestr.empty()) continue;//表示其中的内容不是标识符，忽略不处理
			re.replace(prei,length+2,replacestr);//+2表示包括{}一起处理
			i=prei-1;
		}
		i++;
	}
	//处理完毕，此时该正规式中应当没有用户自定义的标识符了
}

void produceNfa(const string & re,vector<list<Node> > &tnfa, vector<int> & isTer,int index)
{
	stack<Node> status;//状态栈，用于存储当前状态
	stack<int> tstatus;
	bool is_reduce=false;//判断是不是已经归约了。
	bool isNonSpec=false;
	unsigned int next_state=0;
	Node a;
	a.state=-1;
	a.value=-1;
	status.push(a);
	unsigned int i=0;
	list<Node> p;
	//tnfa.push_back(p);//初始时，先往tnfa内放入一个list<Node>
	while(i<re.size())
	{
 		char c=re[i];
		if(c=='}')
		{

		}
		switch(c)
		{
		case '\\':
			{
				isNonSpec=true;
				break;
			}
		case '[':
			{
				if(isNonSpec)
				{
					++next_state;
					a.state=next_state;
					a.value=re[i];
					list<Node> p;
					p.push_back(a);
					tnfa.push_back(p);
					isNonSpec=false;
					break;
				}
				tstatus.push(next_state);
				a.state=re[i];//用state表示状态字符
				a.value=i;//用value表示当时的索引值
				status.push(a);
				is_reduce=false;
				break;
			}
		case '(':
			{
				if(isNonSpec)
				{
					++next_state;
					a.state=next_state;
					a.value=re[i];
					list<Node> p;
					p.push_back(a);
					tnfa.push_back(p);
					isNonSpec=false;
					break;
				}
				a.state=re[i];
				a.value=tnfa.size()-1;//使value内存储当前nfa中的最高状态值。
				status.push(a);
				break;
			}
		case '*':
			{
				if(isNonSpec)
				{
					++next_state;
					a.state=next_state;
					a.value=re[i];
					list<Node> p;
					p.push_back(a);
					tnfa.push_back(p);
					isNonSpec=false;
					break;
				}
				a=status.top();
				while(a.state=='|')//如果栈内是｜,进行最终态的调整
				{
					int prestate=a.value;
					prestate--;//此时的值表示将要修改的状态点。
					for(list<Node>::iterator p=tnfa[prestate].begin();p!=tnfa[prestate].end();p++)
					{
						if(p->value!=EPSLONG&&p->state==prestate+1)
						{
							p->state=next_state;
						}
					}
					status.pop();
					a=status.top();
				}
				if(a.state=='[')
				{
					int b=tstatus.top();
					a.state=b;
					a.value=EPSLONG;

					list<Node> p;
					tnfa.push_back(p);
					tnfa.back().push_back(a);

					tstatus.pop();
					status.pop();
					if(i==re.size()-1)
						modifyTer(isTer,b,index);
				}
				else if(a.state=='(')
				{
					int prei=a.value;//取得的是当时nfa中的状态值。
					a.state=prei;
					a.value=EPSLONG;
					list<Node> p;
					tnfa.push_back(p);
					tnfa.back().push_back(a);
					status.pop();
					if(i==re.size()-1)
						modifyTer(isTer,prei,index);
				}
				break;

			}
		case '|':
			{
				if(isNonSpec)
				{
					++next_state;
					a.state=next_state;
					a.value=re[i];
					list<Node> p;
					p.push_back(a);
					tnfa.push_back(p);
					isNonSpec=false;
					break;
				}
				a=status.top();
				int prestate=0;
				if(a.state=='|'||a.state=='(')
				{
					prestate=a.value;
				}
				else if(a.state=='[')
				{
					prestate=tstatus.top();
				}
				a.state=next_state;//向nfa内存储一条空边，为了方便进行构造。
				a.value=EPSLONG;

				tnfa[prestate].push_back(a);
				a.state='|';
				a.value=next_state;//存储此时｜符号前一状态的值
				status.push(a);
				break;
			}
		case ')':
			{
				if(isNonSpec)
				{
					++next_state;
					a.state=next_state;
					a.value=re[i];
					list<Node> p;
					p.push_back(a);
					tnfa.push_back(p);
					isNonSpec=false;
					break;
				}
				a=status.top();
				while(a.state=='|')//如果栈内是｜,进行最终态的调整
				{
					int prestate=a.value;
					prestate--;//此时的值表示将要修改的状态点。
					for(list<Node>::iterator p=tnfa[prestate].begin();p!=tnfa[prestate].end();p++)
					{
						if(p->value!=EPSLONG&&p->state==prestate+1)
						{
							p->state=next_state;
						}
					}
					status.pop();
					a=status.top();
				}
				if(i==re.size()-1)
					modifyTer(isTer,next_state,index);
				if(i<re.size()-1&&re[i+1]!='*') status.pop();
				break;
			}
		case ']':
			{
				if(isNonSpec)
				{
					++next_state;
					a.state=next_state;
					a.value=re[i];
					list<Node> p;
					p.push_back(a);
					tnfa.push_back(p);
					isNonSpec=false;
					break;
				}
				a=status.top();
				if(is_reduce)
				{				
					if(re[i+1]!='*')
					{	
						list<Node> p;
						tnfa.push_back(p);