正规式.cpp

计算机科学与技术

//                   编译原理,正规式转化成NFA
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//Node为结点,Arrow为弧(箭头)
class Node;					
class Arrow
{
	char ch;
public:
	Node *next;
	Arrow(char c, Node* n2)
	{		
		ch=c;
		next=n2;
	}

	char get_c()
	{
		return ch;
	}

};
class Node					//一个节点有n个箭头
{							
	char data;	
public:
	vector <Arrow*> L;
	Node(char c){ data=c; }

	char getd()
	{
		return data;
	}

	void setnext(char c, Node * n2)
	{
		Arrow *X=new Arrow(c, &(*n2));
		L.push_back(X);
	}

	void display()
	{
		for(int i=0; i<L.size(); i++)
		{
			char Sdata=L[i]->next->getd();						
			cout<<data<<"-"<<L[i]->get_c()<<"->"<<Sdata<<"\t";		//当前节点---条件-->下一节点
		}
	}

};


char state[3]={ '0' , '0', '0'};						//每增加一个节点,state[0]++;
bool isLetter(char c);									//c是否为字符
void divide(string s, vector <Node*> *N, int begin, int end);	//将长字符串s细化成小s串
int insert(string s, vector <Node*> *N, int n1, int tail, char state[]);
//S<3,将s按规则转换,将新节点插入N结尾	n1为当前节点,n2:n1-s->n2

void DFA_sure(vector <Node*> *N, vector <Node*> *N2, vector < vector <char> > *tab);//NFA确定化
bool exist(vector <char> a, char c2);		//a中是否有c2，有返回true,否则返回false
void to_bibao(char c, char condition, vector <char> *Second, vector <Node*> *N);
//求一个状态c的~闭包
void Init_condition(vector <char> *condition, vector <Node*> *N);	//初始化condition数组
int exist_str(vector <char> Second, vector < vector <char> > *tab );
//判断数组Second是否在tab中,是返回-1,否则返回在tab中的下标,(Second,tab都不存在重复字符)

void DFA_min(vector <Node*> *N2, vector <Node*> *N3, vector < vector <char> > *tab);//DFA最小化
bool contain(vector <char> First, vector< vector<char> > csunset);//First是否为csunset的子集
void divideset(int key, int k, vector< vector<int> > *sunset, vector< vector<char> > *csunset, vector <Node*> *N2);
//susnet[i]划分子集
void Init_sonset(vector < vector <int> > *sunset, vector < vector <char> > *csunset, vector < vector <char> > *tab, vector <Node*> *N2);
//初始化sonset:即分终态和初态结点
void Display(vector <Node*> N);		//显示N
int main()
{
	cout<<"请输入正规式:";
//	string s;
//	cin>>s;
	string s="(a|b)*(aa|bb)(a|b)*";
//	string s="1(0|1)*101";

	vector <Node*> N1;
	Node n11('X');	
	Node n12('Y');
	N1.push_back(&n11);
	N1.push_back(&n12);
	divide(s, &N1, 0, 1);
	Display(N1);
	
cout<<"****************************************************************************"<<endl;

	vector < vector <char> > tab;
	vector <Node*> N2;
	DFA_sure(&N1, &N2, &tab);
	Display(N2);
	
cout<<"****************************************************************************"<<endl;

	vector <Node*> N3;
	DFA_min(&N2, &N3, &tab);
	Display(N3);

	return 0;
}

void divide(string s, vector <Node*> *N, int begin, int end)
{		
	if(s.size()<=3)													//如果s长度小于等于3,直接处理
	{
		int n3=insert(s, N, begin, end, state);
	}

	else if(s.size()>3)											//如果s长度大于3
	{
		int kuohao=0;	//记录'('个数												
		int huo=0;		//记录'|'个数
		int flag=0;		//'|'标识,0为不存在,1为存在
		for(int i=0; i<s.size(); i++)				//判断是否存在有最后级运算符'|'
		{
			if(s[i]=='|'&&kuohao==0)
			{
				string s1=s.substr(0, i);
				string s2=s.substr(i+1, s.size()-i);
				flag=1;				
				divide(s1, N, begin, end);	
				divide(s2, N, begin, end);				
				break;
			}
			if(s[i]=='(')
			{
				kuohao++;
			}
			if(s[i]==')')
			{
				kuohao--;
			}
		}
		if(flag==0)												//无'|'有'('
		{
			int L_flag=s.find('(');	//查找'(',返回其位置,
			if(L_flag>0)
			{		
				string s1, s2, s3;					
				s1=s.substr(0, L_flag);
				s2=s.substr(L_flag, s.size()-L_flag);
				Node *new_node=new Node(state[0]++);
				N->push_back(new_node);
				int mid=N->size()-1;
				divide(s1, N, begin, mid);
				divide(s2, N, mid, end);
			}
			else if(L_flag==0)
			{
				int R_flag=s.find(')');
				int L_num=0, R_num=0;
				string y=s.substr(0, R_flag);       //查找第一个')'前的'('个数
				for(int j=0; j<y.size(); j++)
				{
					if(y[j]=='(') { L_num++; }
				}
				for(int k=R_flag; k<s.size(); k++) //查找与第一个'('对应的')'
				{
					if(L_num==R_num) break;
					if(s[k]==')' ) { R_num++; }
				}	
				string s1, s2;
				s1=s.substr(1, k-2);
				if(k==s.size() )	//s的最后一个字符为')'
				{
					divide(s1, N, begin, end);
				}
				else if(k<s.size())
				{
					if(s[k]=='*')
					{
						s2=s.substr(k+1, ( s.size()-(k+1) ) );
					}
					else 
					{
						s2=s.substr(k, s.size()-k );
					}
					if(s2.size()!=0)
					{
						Node *new_node=new Node(state[0]++);
						N->push_back(new_node);
						int mid=N->size()-1;
						divide(s2, N, mid, end);
						int mid2=0;
						if(s[k]=='*')
						{
							Node *new_node2=new Node(state[0]++);
							(*N)[begin]->setnext('~', new_node2);
							new_node2->setnext('~', (*N)[mid]);
							N->push_back(new_node2);
							mid2=N->size()-1;
							divide(s1, N, mid2, mid2);	
						}

						else
						{
							divide(s1, N, begin, mid);
						}

					}
					else if(s2.size()==0)
					{
						if(s[k]=='*')
						{									
							Node *new_node2=new Node(state[0]++);
							(*N)[begin]->setnext('~', new_node2);							
							N->push_back(new_node2);
							int mid2=N->size()-1;
							divide(s1, N, mid2, mid2);
							Node *nt=(*N)[end];
							(*N)[mid2]->setnext('~', nt);							
						}
						else
						{
							divide(s1, N, begin, end);
						}
					}
				}
			}
			else if(L_flag<0)					//无'|'无'('
			{
				int starFlag=0;
				starFlag=s.find('*');
				if(starFlag>0)
				{
					string s1, s2, s3;
					s2=s.substr(starFlag-1, 2);
					if(starFlag>2)
					{
						s1=s.substr(0, starFlag-1);
					}
					if(starFlag!=s.size() )
					{
						s3=s.substr(starFlag+1, s.size()-starFlag-1);
					}
	
					Node *new_node1=new Node(state[0]++);
					Node *new_node2=new Node(state[0]++);
				
					if(starFlag>2){	N->push_back(new_node1); }
		
					int mid1=N->size()-1;
					N->push_back(new_node2);
					int mid2=N->size()-1;
					divide(s1, N, begin, mid1);											
					divide(s2, N, mid1, mid2);
				
					if(starFlag!=s.size() )
					{
						divide(s3, N, mid2, end);
					}

					else { (*N)[mid2]->setnext('~', (*N)[end]); }
				}

				else if(starFlag<0)					//无'|'无'('无'('
				{
					for(int i=0; i<s.size()-1; i++)
					{
						string s1=s.substr(i, 1);
						Node *new_node=new Node(state[0]++);
						(*N)[begin]->setnext(s[i], new_node);
						N->push_back(new_node);
						begin=N->size()-1;
					}
					N->back()->setnext(s[i], (*N)[end]);
				}

			}												
		}			
	}	//end of "if(s.size()>3)"
}	//end of divide()

int insert(string s, vector <Node*> *N, int head, int tail, char state[])
{
	Node *n1=(*N)[head];
	Node *n4=(*N)[tail];
	if(s.size()==1)							//a
	{	
		n1->setnext(s[0], (*N)[tail]);
	}
	else if(s.size()==2)					//2字符
	{
		if(s[1]=='*')						//a*
		{
			Node *new_node=new Node(state[0]++);
			n1->setnext('~', new_node);
			new_node->setnext(s[0], new_node);
			N->push_back(new_node);
			Node *n3=(*N)[tail];
			N->back()->setnext('~', n3);			
		}
		else										//ab
		{		
			Node *new_node=new Node(state[0]++);
			n1->setnext(s[0], new_node);
			N->push_back(new_node);
			Node *n3=(*N)[tail];
			new_node->setnext(s[1], n3);
		}
	}
	else if(s.size()==3)								//3字符
	{
		if(s[1]=='|')								//a|b
		{
			n1->setnext(s[0], n4);
			n1->setnext(s[2], n4);			
		}
		else if(s[0]=='('&&s[2]==')')				//(a)
		{
			n1->setnext(s[1], (*N)[tail]);
		}
		else if(s[1]=='*')							//a*b
		{
			Node *new_node1=new Node(state[0]++);
			Node *new_node2=new Node(state[0]++);
			n1->setnext('~', new_node1);
			new_node1->setnext(s[0], new_node1);
			new_node1->setnext('~', new_node2);
			N->push_back(new_node1);
			N->push_back(new_node2);
			Node *n3=(*N)[tail];

			N->back()->setnext(s[2], n3);		
		}
		else if(s[2]=='*')							//ab*
		{
			Node *new_node2=new Node(state[0]++);
			Node *new_node1=new Node(state[0]++);			
			n1->setnext(s[0], new_node2);
			new_node2->setnext('~', new_node1);
			N->push_back(new_node2);
			new_node1->setnext(s[1], new_node1);			
			N->push_back(new_node1);			
			Node *n3=(*N)[tail];	
			N->back()->setnext('~', n3);		
		}
		else										//abc
		{
			Node *new_node1=new Node(state[0]++);
			Node *new_node2=new Node(state[0]++);
			n1->setnext(s[0], new_node1);				
			new_node1->setnext(s[1], new_node2);
			N->push_back(new_node1);
			N->push_back(new_node2);
			if(tail==1)
			{
				(*N)[N->size()-1]->setnext(s[2], (*N)[tail]);
			}
			else
			{
				Node *new_node3=new Node(state[0]++);
				(*N)[N->size()-1]->setnext(s[2], new_node3);	
				N->push_back(new_node3);
			}					
		}
	}
	else {}	

	return (N->size()-1);
}

bool isLetter(char c)
{
	if( (c>='A'&&c<='Z')||(c>='a'&&c<='z') )	{	return true; }
	else return false;
}


void DFA_sure(vector <Node*> *N, vector <Node*> *N2, vector < vector <char> > *tab)
{
	vector <char> First;			//某个字符的闭包
	vector <char> Second;			//某个字符数组的闭包
	First.push_back( (*N)[0]->getd() );
	Second.push_back(First[0]);
	to_bibao(First[0], '~', &Second, N);
	
	vector<char> condition;
	Init_condition(&condition, N);

	tab->push_back(Second);
	
	Node *new_node=new Node(state[1]++); 
	N2->push_back(new_node);

	for(int i=0; i<tab->size(); i++)	//状态表层
	{	
		for(int j=0; j<condition.size(); j++)	//条件层
		{
			Second.clear();
			for(int k=0; k<(*tab)[i].size(); k++)		//字符表层
			{
				First.clear();				
				to_bibao((*tab)[i][k], condition[j], &First, N);
				for(int m=0; m<First.size(); m++)
				{
					if(!exist(Second, First[m] ) )
					{
						Second.push_back(First[m]);
					}