程序1.cpp

编译原理 语义分析 c++ vc6.0 可用作本科课程设计、毕业设计等

// 正则表达式_有穷自动机.cpp : Defines the entry point for the console application.
// 2005.9.21

#include "stdafx.h"
#include "stdlib.h"
#include "iostream.h"
#include "stdio.h"
#include "string.h"

#include "stack.h"

#define MAXCHILDREN 1000
#define MAXNODENUMBER 1000
#define MAXREG 1000
////////////////////////////////////////////////////////////////////////////
// 编写正则表达式计算程序，要求如下：
// 输入正则表达式串，输出计算结果。
const int OperatorNumber = 6;
int ProiTable[OperatorNumber][OperatorNumber] = 
{ // |  .  *  (  )  #                            1<   2=   3>   0X
	{1, 1, 0, 3, 0, 3}, // |
	{3, 1, 0, 3, 0, 3}, // .
	{0, 0, 0, 0, 0, 0}, // *
	{0, 3, 0, 0, 0, 0}, // (
	{1, 1, 0, 2, 0, 0}, // )
    {1, 1, 0, 0, 0, 2}  // #
};
int OperatorID( char op )
{   // 转换字符值
	switch( op )
	{
		case '|': return 0;
		case '.': return 1;
		case '*': return 2;
		case '(': return 3;
		case ')': return 4;
		case '#': return 5;
	}
	return -1;
}
int Proi( int op1, int op2 )
{   // 查表确定优先级
    return ProiTable[OperatorID(op1)][OperatorID(op2)];
}
////////////////////////////////////////////////////////////////////////////
int type( char p )
{   // 判断字符类型
	if(p>=48 && p<=57) // 数字
	    return 0;
	else if((p>=65 && p<=90)||(p>=97 && p<=122)) // 字母
	    return 1;
	else if( p==124 || p==46 || p==42 || p==40 || p==41 || p==35 )
	    return 2;                      // 运算符  |  .  *  (  )  #
    else  // 其它
		return 3;
}
////////////////////////////////////////////////////////////////////////////
int base ( char ch , nfapoin *&p )  // 由基本正则表达式构造基本自动机  
{                                   // 这里只考虑了 a 没考虑 epsilon 和 空集
	node *star = new node;
	node *end = new node;
	initnode(star);
	initnode(end);

	star->next[0]=end;
	star->throught[0]=ch;

	p->nodenumber=p->nodenumber+2;
	star->number=p->nodenumber-1;
	end->number=p->nodenumber;

	p->nodetable[p->nodenumber-2]=star;
	p->nodetable[p->nodenumber-1]=end;

	star->state='s';
	p->start=star;
	end->state='e';
	p->accept=end;
	return 1;
}
// 三种基本运算:
int connect ( node *&s1, node *&e1, node *&s2, node *&e2, nfapoin *&p )
{   // 连接运算
	e1->next[0]=s2;
	e1->throught[0]=' '; // space表示epsilon

	p->start=s1;
	p->accept=e2;
	e1->state='\0';
	s2->state='\0';

	return 1;
}
int choose ( node *&s1, node *&e1, node *&s2, node *&e2, nfapoin *&p )
{   // 选择运算
	node *s = new node;
	node *e = new node;
	initnode(s);
	initnode(e);

	s->next[0]=s1;
	s->throught[0]=' ';
	s->next[1]=s2;
	s->throught[1]=' ';

	e1->next[0]=e;
	e1->throught[0]=' ';
	e2->next[0]=e;
	e2->throught[0]=' ';

	s1->state='\0';
	s2->state='\0';
	s->state='s';
	e1->state='\0';
	e2->state='\0';
	e->state='e';

	p->start=s;
	p->accept=e;

	p->nodenumber=p->nodenumber+2;
	s->number=p->nodenumber-1;
	e->number=p->nodenumber;

	p->nodetable[p->nodenumber-2]=s;
	p->nodetable[p->nodenumber-1]=e;

	return 1;
}
int kleene ( node *&s1, node *&e1, nfapoin *&p )
{   // 闭包运算
	node *s = new node;
	node *e = new node;
	initnode(s);
	initnode(e);

	s->next[0]=s1;
	s->next[1]=e;
	s->throught[0]=' ';
	s->throught[1]=' ';

	e1->next[0]=e;
	e1->next[1]=s1;
	e1->throught[0]=' ';
	e1->throught[1]=' ';

	s1->state='\0';
	e1->state='\0';
	s->state='s';
	e->state='e';

	p->start=s;
	p->accept=e;

	p->nodenumber=p->nodenumber+2;
	s->number=p->nodenumber-1;
	e->number=p->nodenumber;

	p->nodetable[p->nodenumber-2]=s;
	p->nodetable[p->nodenumber-1]=e;

	return 1;
}
////////////////////////////////////////////////////////////////////////////
void print(nfapoin *nfa)
{
	cout<<"结点总数是"<<nfa->nodenumber<<endl;
	cout<<"node children"<<endl;
	for(int i=0;nfa->nodetable[i]!=NULL;i++){
		if(nfa->nodetable[i]->state!='\0'){
			cout<<nfa->nodetable[i]->number<<nfa->nodetable[i]->state<<"  ";}
		else{cout<<nfa->nodetable[i]->number<<"   ";}
		for(int k=0;nfa->nodetable[i]->next[k]!=NULL;k++){
			cout<<" -"<<nfa->nodetable[i]->throught[k]<<"->";
			cout<<nfa->nodetable[i]->next[k]->number<<"    ";
		}
		cout<<endl;
	}//cout<<endl;
}
///////////////////////////////////////////////////////////////
// 主转化函数1--------将输入的正则表达生成非确定有穷自动机NFA
nfapoin *TurnNFAiniteAutomata(char *re)
{
	int i=0;
	char RegularExpression[MAXREG];
	for(i=0;i<MAXREG;i++){
	    RegularExpression[i]='\0';
	}
	char *p=RegularExpression;
	for(i=0;*(re+i)!='\0';i++){
		RegularExpression[i]=*(re+i);
	}
	if(RegularExpression[0]=='\0'){return NULL;}
	//for(i=0;RegularExpression[i]!='\0';i++){
	//	cout<<RegularExpression[i];
	//}
	nfapoin *nfa = new nfapoin;
	nfapoin *basenfa = new nfapoin;
	initpoin(nfa);
	initpoin(basenfa);
	node *tmp1=new node;
	node *tmp2=new node;
	node *tmp3=new node;
	node *tmp4=new node;
	initnode(tmp1);
	initnode(tmp2);
	initnode(tmp3);
	initnode(tmp4);

	char tmpcout='\0';
//	E1：设立运算符栈和操作数栈；
	Stack poinstack;
	lStack coutstack;
	InitStack( poinstack );
	lInitStack( coutstack );
//	E2：开始运算符#入栈，并向表达式串尾添加结束运算符#
	lPush(coutstack,'#');
	for(char *c=RegularExpression;*c!='\0';c++);
	*c='#';c++;*c='\0';

	char ch=*p;
	while(1)
	{   // E3：逐词读入表达式，并处理：
		//cout<<"--------------------------------"<<endl;
		if(ch==' '){p++;} // 跳过空格
		if(type(ch)!=2)
		{	// E31：若读入为操作数(字符)，生成基本有穷自动机,将初始状态和接受状态的指针入栈;
			base(ch,basenfa);
			if( nfa->nodenumber==0 )
			{
		        nfa=basenfa;
			}
			Push(poinstack,basenfa->start);
			Push(poinstack,basenfa->accept);
			p++;
		}
		if(type(ch)==2)
		{   // E32：若读入为运算符
			if(ch=='*')
			{
				tmp1=Top(poinstack);Pop(poinstack);
				tmp2=Top(poinstack);Pop(poinstack);
				kleene(tmp2,tmp1,nfa);
				Push(poinstack,nfa->start);
				Push(poinstack,nfa->accept);
				p++;
			}
			if(ch=='(')
			{
				lPush(coutstack,ch);
				p++;
			}
			if(ch=='|'||ch=='.')
			{   // 则与栈顶运算符相比较：
				i=Proi(  ch,lTop(coutstack) );
				if(i==1)
				{   // 弹出运算符，弹出两个操作数，计算并将结果入栈；
					tmp1=Top(poinstack);Pop(poinstack);
					tmp2=Top(poinstack);Pop(poinstack);
					tmp3=Top(poinstack);Pop(poinstack);
					tmp4=Top(poinstack);Pop(poinstack);
					tmpcout=lTop(coutstack);
					lPop(coutstack);
					if(tmpcout=='.')
					{
						connect(tmp4,tmp3,tmp2,tmp1,nfa);
					}
					if(tmpcout=='|')
					{
						choose(tmp4,tmp3,tmp2,tmp1,nfa);
					}
					Push(poinstack,nfa->start);
					Push(poinstack,nfa->accept);
					//p++;
				}
				if(i==3)
				{   // 则将读入运算符入栈；
					lPush(coutstack,ch);
					p++;
				}
			}
			if(ch==')')
			{
				tmpcout=lTop(coutstack);
				if(tmpcout=='(')
				{   // 则弹出运算符
				    lPop(coutstack);
					p++;
				}
				else
				{   // 弹出运算符，弹出两个操作数，计算并将结果入栈
					tmp1=Top(poinstack);Pop(poinstack);
					tmp2=Top(poinstack);Pop(poinstack);
					tmp3=Top(poinstack);Pop(poinstack);
					tmp4=Top(poinstack);Pop(poinstack);
					tmpcout=lTop(coutstack);
					lPop(coutstack);
					if(tmpcout=='.')
					{
						connect(tmp4,tmp3,tmp2,tmp1,nfa);
					}
					if(tmpcout=='|')
					{
						choose(tmp4,tmp3,tmp2,tmp1,nfa);
					}
					Push(poinstack,nfa->start);
					Push(poinstack,nfa->accept);
				}
			}
			if(ch=='#')
			{
				tmpcout=lTop(coutstack);
				if( tmpcout=='#' )
				{   // 则运算结束
                    break;
				}
				if( tmpcout!='#' )
				{	
					tmp1=Top(poinstack);Pop(poinstack);
					tmp2=Top(poinstack);Pop(poinstack);
					tmp3=Top(poinstack);Pop(poinstack);
					tmp4=Top(poinstack);Pop(poinstack);
					tmpcout=lTop(coutstack);
					lPop(coutstack);
					if(tmpcout=='.')
					{
						connect(tmp4,tmp3,tmp2,tmp1,nfa);
					}
					if(tmpcout=='|')
					{
						choose(tmp4,tmp3,tmp2,tmp1,nfa);
					}
					Push(poinstack,nfa->start);
					Push(poinstack,nfa->accept);
				}
			}
		}
		ch=*p;
	}//print(nfa);
    return nfa;
}
////////////////////////////////////////////////////////////////////////////
void deletd(node *&p)
{   // 删除无效重复的边
	int flag=1;
	while(flag)
	{
		flag=0;
		for(int i=0;p->next[i]!=NULL;i++)
		{   // 扫描每一个子
			for(int j=i+1;p->next[j]!=NULL;j++)
			{
				if( p->next[i]==p->next[j] && p->throught[i]==p->throught[j] )
				{   // 找到了 删除j
					for(int k=j;p->next[k+1]!=NULL;k++)
					{
						//cout<<"------"<<p->number<<" through "<<p->throught[k]<<" to "<<p->next[k]->number<<endl;
						p->next[k]=p->next[k+1];
						p->throught[k]=p->throught[k+1];
					}
					p->next[k]=NULL;
					p->throught[k]='\0';
					flag=1;
					i=0;
					break;
				}
			}				
		}
	}
}
void deletn(node *&p)
{
	int flag=1;
	while(flag)
	{
		flag=0;
		for(int i=0;p->next[i]!=NULL;i++)
		{   // 扫描每一个子
			//cout<<"------"<<p->number<<" through "<<p->throught[i]<<" to "<<p->next[i]->number<<endl;
			if(p->next[i]==p&&p->throught[i]==' ')
			{
				for(int j=i;p->next[j+1]!=NULL;j++)
				{
					p->next[j]=p->next[j+1];
					p->throught[j]=p->throught[j+1];
				}
				p->next[j]=NULL;
				p->throught[j]='\0';
				flag=1;
				break;
			}
		}
	}
}
////////////////////////////////////////////////////////////////////////////
void merge(node *&p, node *&q,nfapoin *&nfa)
{   // 把q合并到p上	
	//cout<<"-----------"<<p->number<<" merge "<<q->number<<endl;	//if(p->number==0){print(nfa);}
	node *tmp=q;
	int i=0,j=0,k=0;
	if((p->state=='s'&&q->state=='e')||(p->state=='e'&&q->state=='s')||q->state=='d')
	{   //cout<<"---------------------------------------------------------------d"<<endl;
		p->state='d';
	}
	else {
		if(q->state=='e'){p->state='e';}
		if(q->state=='s'){p->state='s';}
	}
	for(i=0;p->next[i]!=q;i++);	
	while(p->next[i+1]!=NULL)
	{   // 删除epsilon链
		p->throught[i]=p->throught[i+1];
		p->next[i]=p->next[i+1];
		i++;
	}
	p->throught[i]='\0';
	p->next[i]=NULL;
	for(i=0;p->next[i]!=NULL;i++);
	for(j=0;tmp->next[j]!=NULL;j++)
	{   // 把q的每个子都给p	
		if(tmp->next[j]==tmp){
			p->next[i]=p;
		}
		else{
			p->next[i]=tmp->next[j];
		}
		p->throught[i]=tmp->throught[j];
		i++;
	}
	for(k=0;p->next[k]!=NULL;k++);
	for(i=0;nfa->nodetable[i]!=NULL;i++)
	{   // 操作每一个结点
		for(j=0;nfa->nodetable[i]->next[j]!=NULL;j++)
		{   // 扫描结点的每一个子
			if(nfa->nodetable[i]->next[j]==tmp)
			{   // 如果结点的子是q 并且该结点不是p
				if(nfa->nodetable[i]==tmp)