mylex.cpp

编译器中词法分析部分

/*
符号@表示空字符，例如：输入格式为 d=(a|b)*|(a&b)*#
*///d=(a|b)*&a&(a|b)&(a|b)&(a|b)#
#include<iostream>
#include<conio.h>
#include<stack>
#include<vector>
#include<queue>
#include<fstream>
#include<string>

const int MAX=500;//定义最大节点数 
const int LEN=300;//定义正则表达式式的最大长度 
using namespace std;
typedef struct node* pnode;

static int count_num=1;//记录当前节点最大编号 
pnode list[MAX];
ofstream out("output.txt");//输出到文件
struct node
{
    int node_num;//节点编号
    char arc;//弧上元素
    int target;//目标节点
    bool status;//是否为终结状态
	char style;//终态时 正则表达式的类型
    node *next;
	node(){}
    node(int a,char b,int c,bool d):node_num(a),arc(b),target(c),status(d),next(list[a]){}    
};

int OR(int first1,int final1,int first2,int final2,int &a_first,int &a_final)
{//或运算操作
   list[count_num]=new node(count_num,'@',first1,0);
   list[count_num]=new node(count_num,'@',first2,0);
   a_first=count_num;//返回
   count_num++;
   list[final1]=new node(final1,'@',count_num,0);
   list[final2]=new node(final2,'@',count_num,0);
   a_final=count_num;//返回
   return 0;
} 

int Link(int first1,int final1,int first2,int final2,int &a_first,int &a_final)
{//连接运算操作 
    list[final2]=new node(final2,'@',first1,0);
	a_first=first2;
	a_final=final1;
	return 0;
}

int Closure(int &a_first,int &a_final)
{//星闭包运算操作 
	list[a_final]=new node(a_final,'@',a_first,0);
	count_num++;
	list[a_final]=new node(a_final,'@',count_num,0);
	a_final=count_num;
	count_num++;
	list[count_num]=new node(count_num,'@',a_first,0);
	a_first=count_num;
	list[a_first]=new node(a_first,'@',a_final,0);
	
	count_num++;
    return 0;       
}
int convert(char symbol)
{//将操作符转换为整数 
    switch(symbol)
    {
        case '|':return 0;break;
        case '&':return 1;break;
        case '(':return 2;break;
        case ')':return 3;break;
        case '*':return 4;break;
        case '#':return 5;break;
        default: return 6;     
    }             
}
char comp(char top_stack,char out_stack)
{//比较两操作符 
    int n1=convert(top_stack);
    int n2=convert(out_stack);
    char f[6][6]=
    {
		/* |  &   (   )   *   # */
        {'<','<','<','>','<','>'},
        {'>','<','<','>','<','>'},
        {'<','<','<','=','<','$'},
        {'>','>','$','<','>','$'},
        {'>','>','<','>','<','>'},
        {'<','<','<','$','<','+'}
    };
   return f[n1][n2];        
}
int closure_null(char argc,int q[],int c_first,int &num_of_q)
          //argc的闭包  存放状态的数组    开始状态   开始时状态的个数  
{//求DFA时，寻找新状态的过程
	int j=num_of_q;//q数组的实有个数
	q[0]=c_first;
	queue<int>state;//存放状态 依次寻找每个状态所能到达的状态
	while(!state.empty())//初始化
		state.pop();
	state.push(c_first);

	while(!state.empty())
	{//循环直到已经遍历所有的已达到的状态
		int start=state.front();
		state.pop();
		pnode p_list=list[start];
		while(p_list!=NULL)
		{
			if(p_list->arc==argc)
			{
				int tar=p_list->target;
				bool tr=true;
				for(int t=0;t<j;t++)
				{//排除重复的
					if(q[t]==tar)
					{
						tr=false;
						break;
					}
				}
				if(tr)
				{
					q[j]=tar;//记录符合条件的状态
					state.push(q[j]);//符合条件的状态入队
					j++;
				}
			}
			p_list=p_list->next;
		}
	}
	num_of_q=j;
	return 0;
}

char isalpha(char input)
{//将字母归为一类
	if(input<='z'&&input>='a'||input>='A'&&input<='Z')
	{
		return 'L';//约定L表示字母
	}
	else
		return input;
}
char isdigit(char input)
{//将所有数字归为一类
	if(input>='0'&&input<='9')
		return 'D';//约定D表示数字
	else
		return input;
}
string isKey(string input)
{//判断是否是关键字
	if(input=="if"||input=="else"||input=="while"||input=="main"||
		input=="int"||input=="float"||input=="char"||input=="return"||
		input=="break"||input=="true"||input=="false"||input=="switch"
		||input=="for"||input=="case"||input=="double"||input=="default"
		||input=="void")
	{//关键字
		return "KEY";
	}
	else
		return "ID";
}
void getToken(char style,string input)
{//分词并将类型和该词输出
	switch(style)
	{
		case 'I':out<<isKey(input)<<"  "<<input<<endl; //正则表达式中I表示标示符
				break;
		case 'N':out<<"NUM"<<"  "<<input<<endl;//在正则表达式中N表示数字
				break;
		case 'P':out<<"OPER"<<"  ";//在正则表达式中表示操作符
				out<<input<<endl;
				break;//{+,-,/,%,.}注意.表示乘
		case 'C':out<<"COMPARE_OPE"<<"  "<<input<<endl;//表示比较运算符
				break;//{<=,>=,!=,==,<,>}
		case 'B':out<<"BOUND"<<"  "<<input<<endl;//表示界符
				break;//{(,),{,},[,]}
		case 'D':out<<"PUNCTUATION  "<<input<<endl;
				break;//{;,:}
		case 'R':out<<"RELATION  "<<input<<endl; 
				break;
		default: break;
	}
}

int main()
{
/***************************正则表达式到NFA部分****************************/
    memset(list,0,sizeof(list));//初始化list[]
    //char *Regu=new char[LEN];
    string Regu;
	int a_first=1;//表示所构造的整个图的头部
	int a_final=1;//表示所构造的整个图的尾部
	int count_of_regular=0;//用来记录尚未连接的正则表达式
	int b_first=1;

	vector <char> funct;//用来存放正则表达式中出现的字符，为NFA-DFA做准备
	int num_of_funct=0;//用来记录vector中的字符数目

	vector <int> accept_state;//用来存放终态所对应的节点号
	vector<char> final_style;//对应的存放终态类型的数组
	if(!final_style.empty()) //为DFA做准备
		final_style.clear();

	ifstream   fin("in.txt");
	
    while( getline(fin, Regu) )//有问题
    {
		b_first=a_first;//用来记录上一条正则表达式生成的图的头节点编号
        stack<char> oper;//符号栈
        while(!oper.empty())
            oper.pop();//初始化 
		oper.push('#');
		 
		stack<int>first_final;
		while(!first_final.empty())//存放每个字符构成的图的头节点和尾节点
			first_final.pop();
            
		int len=Regu.length();
		//if(len==0) break;//当为空时退出循环
		char ac_style=Regu[0];//表示输入的正则表达式的类型
		
        for(int i=1;i<len;i++)
        {
			/*************检测该元素是否已经在funct中，若不在，则加入****/
			bool if_exsit=1;
			if(Regu[i]!='|' && Regu[i]!='&' && Regu[i]!='*' && Regu[i]!='('
				&& Regu[i]!=')'&&Regu[i]!='#'&&Regu[i]!=' '&&Regu[i]!='\t'
				&&Regu[i]!='='&&Regu[i]!='@')
			{//有个前提是输入的是这些元素和其它认可的字符
				for(int h=0;h<num_of_funct;h++)
				{
					if(funct[h]==Regu[i])
						if_exsit=0;
				}
				if(if_exsit)
				{//表示如果不在funct中，则加入
					funct.push_back(Regu[i]);
					num_of_funct++;
				}
			}
			/***************************************/
			//除去空格和tab和等号
            if(Regu[i]==' '||Regu[i]=='\t'||Regu[i]=='=')
                continue; 
            if(Regu[i]!='|' && Regu[i]!='&' && Regu[i]!='*' && Regu[i]!='(' && Regu[i]!=')'&&Regu[i]!='#')
            {//如果不是操作符，则opnd入栈 
				a_first=count_num;
				count_num++;
				list[a_first]=new node(a_first,Regu[i],count_num,0);
			    a_final=count_num;
				count_num++;
				first_final.push(a_final);//压入Regu[i]所对应的首尾节点序号
				first_final.push(a_first);
            }    
            else
            {				
					char relation=comp(oper.top(),Regu[i]);
					if(relation=='<')
					{//栈中元素小于串中元素 则入栈 
						oper.push(Regu[i]);
					}    
					else if(relation=='>')
					{//应该弹出栈顶元素和操作数 
                    
						if(oper.top()=='|')
						{//或运算
							int first1=first_final.top();
							first_final.pop();
							int final1=first_final.top();
							first_final.pop();
					
							int first2=first_final.top();
							first_final.pop();
							int final2=first_final.top();
							first_final.pop();
							OR(first1,final1,first2,final2,a_first,a_final);//或操作 
							 
							first_final.push(a_final);//压入Regu[i]所对应的首尾节点序号
							first_final.push(a_first);
						}
						else if(oper.top()=='&')
						{//与运算 
							int first1=first_final.top();
							first_final.pop();
							int final1=first_final.top();
							first_final.pop();
							
							int first2=first_final.top();
							first_final.pop();
							int final2=first_final.top();
							first_final.pop();

							Link(first1,final1,first2,final2,a_first,a_final);//与操作
							first_final.push(a_final);
							first_final.push(a_first);
						}
						else if(oper.top()=='*')
						{//闭包运算 
							a_first=first_final.top();
							first_final.pop();
							a_final=first_final.top();
							first_final.pop();
							Closure(a_first,a_final);
							
							first_final.push(a_final);
							first_final.push(a_first);
						}
						oper.pop();
						i--;

					}
					else if(relation=='$')
					{//不可能出现的情况，为错误 
						cerr<<"输入错误6!";
						return 1;  
					}
					else if(relation=='=')
					{//拖括号 
						oper.pop();
						continue;
					}
					else 
					{//两个'#'相遇，输入结束 
						oper.pop();
						list[a_final]=new node();
						list[a_final]->status=1;//为终态 
						list[a_final]->style=ac_style;
						list[a_final]->target=a_final;/////有问题  暂时令它的目标为final
						list[a_final]->next=NULL;
						accept_state.push_back(a_final);//将终态的节点号放入accept_state中
						final_style.push_back(ac_style);//将类型存放
						//break;
					}
				}
			
        }        
		count_of_regular++;//已完成的正则表达式加一
		if(count_of_regular>=2)
		{//用公共头节点0指向每条正则表达式的头节点
			list[0]=new node(0,'@',a_first,0);
			list[0]=new node(0,'@',b_first,0);
			count_of_regular--;
		}
	}
/********************检测构造的NFA是否正确***********************/
	/*	cout<<"输出NFA的结果"<<endl;
	pnode p_list;
	for(int k1=0;k1<=count_num;k1++)
	{
		p_list=list[k1];
		while(p_list!=NULL)
		{
			cout<<p_list->target<<" "<<p_list->arc<<" ";
			p_list=p_list->next;
		}
		cout<<endl;
	}
	count_num++;//为输入下一条正则表达式做准备*/
	
/****************检测DFA准备工作是否成功***************************/
	//DFA的前期准备包括 输入正则表达式中的状态转换字符funct集、终态的集合final_style、
	//和终态的节点号
	/*cout<<"转换函数"<<endl;
	for(int y1=0;y1<funct.size();y1++)
		cout<<funct[y1]<<" ";
	cout<<endl;
	cout<<"输出终态类型"<<endl;
	for(int y2=0;y2<final_style.size();y2++)
		cout<<final_style[y2]<<" ";
	cout<<endl;
	cout<<"输出终态对应的节点号"<<endl;
	for(int y3=0;y3<accept_state.size();y3++)
		cout<<accept_state[y3]<<" ";
	cout<<endl;*/
	
/**************************NFA到DFA部分*****************************/
	int start_state;
	if(final_style.size()>1)//终态数大于1时从0节点开始
		start_state=0;
	else 
		start_state=a_first;
	int **state=new int* [MAX];//这样定义可能存在溢出问题
	for(int st=0;st<MAX;st++)
		state[st]=new int[MAX];
	state[0][0]=start_state;
	int num_of_state=1;
    closure_null('@',state[0],start_state,num_of_state);
	
	state[0][MAX-1]=num_of_state;//将该状态集合的个数存放在该数组的最后一个状态
	                             //存在隐含的漏洞
	vector <int> state_another;
	for(int index_state=0;index_state<state[0][MAX-1];index_state++)
		state_another.push_back(state[0][index_state]);
	sort(state_another.begin(),state_another.end());//将state[0]数组中的元素排序
	for(int index_state=0;index_state<state[0][MAX-1];index_state++)
	{//将排过序的重新放入state[][]中
		state[0][index_state]=state_another[index_state];
	}

	queue<int *> state_convert;
	state_convert.push(state[0]);//将初态入队
	int index=1;
	
	int* DFA[MAX];
	for(int df=0;df<MAX;df++)
		DFA[df]=new int [funct.size()+1];
	for(int d1=0;d1<MAX;d1++)
		for(int d2=0;d2<=funct.size();d2++)
			DFA[d1][d2]=-1;//初始化为-1

	int count_DFA=0;//DFA的状态序号
	int DFA_state=0;//DFA的新状态数
	char fin_sty[MAX];//存放终态类型

	while(!state_convert.empty())
	{//当没有新状态产生时结束
		int *front_state=state_convert.front();
		state_convert.pop();//出队		
		
		bool find_final=false;//判断是否是终节点
		char style1;//如果是终结点则表示其类型
		for(int j2=0;j2 <accept_state.size();j2++)