grama.cpp

产生的DFA在屏幕上显示,分析表写到文件里面.

#include <fstream.h>
#include <stdlib.h>
#include <fstream.h>
#include "GRAMA.h"

CGRAMA::CGRAMA():start_symbol(-5)				//构造函数
{
	char *buf,ch;
	List<char> buflist;							
	int i=0;
	ifstream fin("grama.txt",ios::nocreate);	//打开文件
	if(!fin){
		cout<<"file not found!\n";
		exit(0);
	}
	fin>>vnnum>>vtnum>>gncount;
	vnstring=new char[vnnum];
	vtstring=new char[vtnum];
	vn=new int[vnnum];
	vt=new int[vtnum];
	for(i=0;i<vnnum;i++){						//对非终结符进行编码
		fin>>vnstring[i];
		vn[i]=-10-5*i;
	}
	for(i=0;i<vtnum;i++){						//对终结符进行编码
		fin>>vtstring[i];
		vt[i]=10+5*i;
	}
	Gener first_gener;							//对文法进行拓广		
	first_gener.vn=start_symbol;				//-5是文法开始符号				
	first_gener.sentence=new int[2];
	first_gener.sentence[0]=vn[0];				
	first_gener.sentence[1]=END;
	gn_list.Insert(first_gener);
	fin.get(ch);
	for(i=0;i<gncount;i++){
		while(1){	
			fin.get(ch);
			if(ch=='\n')	break;
			buflist.Insert(ch);
		}
		buflist.PutToArray(buf);
		buflist.MakeEmpty();
		Encode(buf);
	}
	fin.close();
}

CGRAMA::~CGRAMA()								//析构函数
{
	gn_list.MakeEmpty();
	item_list.MakeEmpty();
	convert_list.MakeEmpty();
	delete[]vt;
	delete[]vn;
	delete[]vtstring;
	delete[]vnstring;
}

void CGRAMA::Encode(char *&buf)
{
	char *pS=buf;								//搜索buf字符串的指针
	int temp,flag(0);							//temp是中转变量,
	Gener gener,g1,g2;
	List<Gener> temp_list;
	gener.vn=EncodeVn(*pS);						//产生式左部的编码
	pS=pS+3;									//跳过"->"
	int length=::GetStrLen(buf)-3;				//length为产生式右部的最大长度
	gener.sentence=new int[length+1];			//堆内存分配		
	for(int i=0;i<length;i++){
		if((temp=EncodeVt(*pS))==-1) 			//若在终结符中找不到就到非终结符中找
			temp=EncodeVn(*pS);
		gener.sentence[i]=temp;					//存入编码值
		pS++;
	}
	gener.sentence[length]=END;
	temp_list.Insert(gener);
	for(ListNode<Gener> *p=temp_list.first;p;p=p->link)
	{
		length=p->data.GetRightLength();
		flag=0;
		for(i=0;i<length;i++)
		{
			if(p->data.sentence[i]==-1)
			{
				flag=1;
				break;
			}
		}
		g1.vn=p->data.vn;
		if(flag==1)		g1.sentence=new int[i+1];
		else g1.sentence=new int[length];
		for(int j=0;j<i;j++)
			g1.sentence[j]=p->data.sentence[j];
		g1.sentence[i]=END;
		gn_list.Insert(g1);
		if(flag==1){
			g2.vn=p->data.vn;
			g2.sentence=new int[length-i];
			for(j=0;j<length-i-1;j++)
				g2.sentence[j]=p->data.sentence[j+i+1];
			g2.sentence[length-i-1]=END;
			temp_list.Insert(g2);
		}
	}
}


int CGRAMA::EncodeVn(char ch)							//查找非终结符号表
{
	for(int i=0;i<vnnum;i++)
		if(ch==vnstring[i])
			return vn[i];
	return -1;
}

int CGRAMA::EncodeVt(char ch)							//查找终结符号表
{
	for(int i=0;i<vtnum;i++)
		if(ch==vtstring[i])
			return vt[i];
	if(ch=='$') return 0;
	return -1;
}

char CGRAMA::Decode(int num)
{
	char c;int i;
	for(i=0;i<vnnum;i++)
		if(num==vn[i])
			return vnstring[i];
	for(i=0;i<vtnum;i++)
		if(num==vt[i])
			return vtstring[i];
	if(num==-5)	c='X';
	if(num==1)	c='.';
	if(num==5)	c='#';
	if(num==0)	c='$';
	return c;
}

void CGRAMA::ToItemSet()								//产生式转化为项目并插入链表
{
	int gener_len;
	for(ListNode<Gener> *p=gn_list.first;p;p=p->link)
	{
		gener_len=p->data.GetRightLength();
		p->data.GenToItem(item_list,gener_len);
	}	
}

void CGRAMA::Closure(List<CItem> &kernel)				//CLOSURE(I)函数
{
	Queue<CItem> queue,item_q;
	ListNode<CItem> *p,*q;
	CItem item,mid_item;
	int code,pos;
	List<int> f_set;
	for(p=kernel.first;p;p=p->link)
	{
		if(p->data.vn==-5)
		{
			p->data.string.MakeEmpty();
			p->data.string.Insert(5);
		}
		queue.QInsert(p->data);
		item_q.QInsert(p->data);
	}
	kernel.MakeEmpty();	
	while(!queue.QueueEmpty())											
	{
		item.string.MakeEmpty();
		item=queue.QDelete();
		if(item.IsForReduce())
		{
			pos=item.GetDotPos();
			f_set.MakeEmpty();                   
			FirstX(item.sentence+pos+2,f_set);
			for(q=item_list.first;q;q=q->link)
			{
				if(q->data.vn==item.sentence[pos+1]&&q->data.sentence[0]==1)
				{
					mid_item=q->data;
					if(f_set.IsEmpty()) mid_item.string.Add(item.string);
					else mid_item.string.Add(f_set);
					item.string.MakeEmpty();
					code=item_q.GetCode(mid_item);
					if(code==0){
						queue.QInsert(mid_item);				
						item_q.QInsert(mid_item);
					}
					else if(!(mid_item.string==item_q.queue[code].string))
						item_q.queue[code].Merge(mid_item);
				}
			}//end for
		}//end if
	}
	for(int i=1;i<=item_q.rear;i++)	kernel.Insert(item_q.queue[i]);
	
}

void CGRAMA::FromItoJ(CItem &item,List<CItem> &J)		//由A->a.Br找出
{														//形如A->aB.r的式子
	int pos=item.GetDotPos();
	int temp=item.sentence[pos+1];
	for(ListNode<CItem> *p=item_list.first;p;p=p->link)
	{		
		if(p->data.vn==item.vn)
		{
			int pos1=p->data.GetDotPos();
			if(p->data.sentence[pos1-1]==temp&&pos1-pos==1){
				if(!p->data.string.IsEmpty())
					p->data.string.MakeEmpty();
				p->data.string.Add(item.string);
				J.Insert(p->data);
			}
		}
	}
}

int CGRAMA::GO(const List<CItem> &I,int X,List<CItem> &J)		//GO(I,X)函数
{
	int pos;
	for(ListNode<CItem> *p=I.first;p;p=p->link)
	{
		pos=p->data.GetDotPos();
		if(p->data.sentence[pos+1]==X)
			FromItoJ(p->data,J);
	}
	Closure(J);
	if(J.IsEmpty()) return 0;
	return 1;
}

void CGRAMA::GetSymbol(List<CItem> &item_set,List<int> &symbol_list)
{
	int pos,temp;
	symbol_list.MakeEmpty();
	for(ListNode<CItem> *q=item_set.first;q;q=q->link)
	{
		pos=q->data.GetDotPos();
		temp=q->data.sentence[pos+1];
		if(temp!=END) symbol_list.Insert(temp);
	}
	symbol_list.DelRepeated();							//必须放到For的外面!
}

void CGRAMA::OutPut(List<CItem> &list)
{
	List<char> char_list;
	char ch;
	for(ListNode<CItem> *p=list.first;p;p=p->link)
	{
		char_list.MakeEmpty();
		ch=Decode(p->data.vn);
		char_list.Insert(ch);
		char_list.Insert('-');
		char_list.Insert('>');
		if(p->data.sentence!=NULL){
		for(int i=0;p->data.sentence[i]!=END;i++)
		{
			ch=Decode(p->data.sentence[i]);
			char_list.Insert(ch);
		}
		}
		char_list.Print();
		cout<<"    \t";
		for(ListNode<int> *q=p->data.string.first;q;q=q->link)
			cout<<Decode(q->data)<<" ";
		cout<<endl;
	}
}

void CGRAMA::PrintDFA()									//输出DFA
{
	Queue<List<CItem> > q;								//q1是分析中用										
	List<CItem> start_set;								
	start_set.Insert(item_list.first->data);
	Closure(start_set);
	q.QInsert(start_set);
	state_queue.QInsert(start_set);
	List<int> sym_list;
	List<CItem> go_list;
	List<CItem> temp_list;
	CItem item;	
	cout<<"********* LALR(1)文法分析程序 *********:\n";
	List<int> change_list;
	while(!q.QueueEmpty())								//用队列来实现			
	{
		temp_list.MakeEmpty();	
		temp_list=q.QDelete();
		GetSymbol(temp_list,sym_list);					//把求的的 X 存入链表
		for(ListNode<int> *p=sym_list.first;p;p=p->link)//对项目集中各个文法符号X用GO(I,X)
		{
			if(GO(temp_list,p->data,go_list))			
			{	
				int code=state_queue.GetCode(go_list);
				if(code==0)
				{
					q.QInsert(go_list);					//如果Ix还未出现过则进队列
					state_queue.QInsert(go_list);
				}
				else{
					state_queue.queue[code].MergeString(go_list);
					change_list.Insert(code);
				}
				item.vn=state_queue.GetCode(temp_list);
				item.sentence=new int[2];
				item.sentence[0]=p->data;
				item.sentence[1]=state_queue.GetCode(go_list);
				convert_list.Insert(item);				//convert_list记录转换关系
				go_list.MakeEmpty();
			}
		}
	}
	for(int k=1;k<state_queue.rear;k++)
	{
		if(change_list.Contains(k))
		{
			sym_list.MakeEmpty();
			GetSymbol(state_queue.queue[k],sym_list);					
			for(ListNode<int> *p=sym_list.first;p;p=p->link)//对项目集中各个文法符号X用GO(I,X)
			{
				go_list.MakeEmpty();
				if(GO(state_queue.queue[k],p->data,go_list))			
				{	
					int code=state_queue.GetCode(go_list);
					state_queue.queue[code].MergeString(go_list);
				}
			}
		}
	}
	cout<<"\nDFA中所有状态列表:\n[X代表拓广文法开始符号]\n";
	for(int i=1;i<=state_queue.rear;i++)				//把DFA中所有状态输出
	{
		cout<<"STATE "<<i<<":\n";
		OutPut(state_queue.queue[i]);
		cout<<endl;
	}
	ListNode<CItem> *p;
	int newline=0;
	cout<<"\n状态间转换关系:\n";
	for(p=convert_list.first;p;p=p->link)				//打印转换关系
	{
		cout<<"I"<<p->data.vn<<"--- "<<Decode(p->data.sentence[0])
			<<" --> "<<"I"<<p->data.sentence[1]<<"    "<<"\t";
		newline++;
		if(newline%2==0)
			cout<<endl;
	}
	if(newline%2!=0) cout<<endl;
	cout<<endl;
}

void CGRAMA::PrintRuleTable()							//把规则列表写到文件中
{
	List<char> char_list;
	char ch;
	int count=0;
	for(ListNode<CItem> *p=item_list.first;p;p=p->link)
	{
		if(p->data.IsReduce())
			rule_list.Insert(p->data);
	}
	ofstream ofstr("rule.txt");
	ofstr<<"规则列表:"<<endl;
	for(p=rule_list.first;p;p=p->link,count++)
	{
		char_list.MakeEmpty();
		ch=Decode(p->data.vn);
		char_list.Insert(ch);
		char_list.Insert('-');
		char_list.Insert('>');
		for(int i=0;p->data.sentence[i]!=END;i++)
		{
			ch=Decode(p->data.sentence[i]);
			char_list.Insert(ch);
		}
		ofstr<<count<<":\t";
		for(ListNode<char> *q=char_list.first;q;q=q->link)
			ofstr<<q->data;
		ofstr<<endl;
	}
	ofstr.close();
}

void CGRAMA::First(int symbol,List<int> &first_set)		//递归求FIRST集合
{
	if(symbol>0){										//symbol为终结符的情况
		first_set.Insert(symbol);
		return;
	}
	List<int> temp,mid;
	for(ListNode<Gener> *p=gn_list.first;p;p=p->link)	//先不考虑A->A…的情况
		if(p->data.vn==symbol&&p->data.sentence[0]!=symbol)							//找到形如A->…的产生式
		{
			if(p->data.sentence[0]>=0){					//A->a…的情况
				first_set.Insert(p->data.sentence[0]);
				continue;
			}//end if
			else{										//A->X1…Xn的情况
				for(int i=0;p->data.sentence[i]!=END;i++)
				{
					temp.MakeEmpty();
					First(p->data.sentence[i],temp);
					mid=temp;
					if(p->data.sentence[i+1]!=END)	mid.Remove(0);
					first_set.Add(mid);					//First(Xi)=>First(symbol)
					mid.MakeEmpty();
					if(temp.Contains(0)) continue;		//First(Xi)包含ε则继续求	
					else break;					
				}
			}//end else
		}
	for(p=gn_list.first;p;p=p->link)
	{
		if(p->data.vn==symbol&&p->data.sentence[0]==symbol){
			if(first_set.Contains(0)){
				FirstX(p->data.sentence+1,mid);
				first_set.Add(mid);
				mid.MakeEmpty();
			}
		}
	}
	first_set.DelRepeated();
}

void CGRAMA::FirstX(int *array,List<int> &first_set)	//First(X1…Xn)
{
	first_set.MakeEmpty();
	if(*array==END) return;
	List<int> temp;
	First(*array,temp);
	if(!temp.Contains(0)){
		first_set.Add(temp);
		return;
	}
	temp.Remove(0);
	first_set.Add(temp);
	FirstX(array+1,first_set);
	first_set.DelRepeated();
}

void CGRAMA::PrintTable()								//打印分析表
{
	int i;
	ListNode<CItem> *p;
	ofstream ofstr("table.txt");
  	ofstr<<"LALR(1)分析表:\n";
	for(i=0;i<(vtnum+vnnum+1);i++)	ofstr<<"________";
	ofstr<<"__"<<endl;
	for(i=0;i<vtnum;i++)	ofstr<<"\t"<<Decode(vt[i]);
	ofstr<<"\t#";
	for(i=0;i<vnnum;i++)	ofstr<<"\t"<<Decode(vn[i]);
	ofstr<<endl;
	for(i=0;i<(vtnum+vnnum+1);i++)	ofstr<<"________";
	ofstr<<"__"<<endl;
	ListNode<CItem> *pItem;
	for(i=1;i<=state_queue.count;i++)
	{
		ofstr<<"I"<<i<<"\t";
		pItem=state_queue.queue[i].first;

		/***********ACTION部分************/

		for(int j=0;j<vtnum;j++)					
		{
			if(pItem->data.IsReduce()&&pItem->data.string.Contains(vt[j]))
				ofstr<<"r"<<rule_list.GetCode(pItem->data);
			for(p=convert_list.first;p;p=p->link)
				if(p->data.sentence[0]==vt[j]&&p->data.vn==i)					
					ofstr<<"s"<<p->data.sentence[1];
			ofstr<<"  \t";
		}
		if(pItem->data.IsReduce()&&pItem->data.string.Contains(5))
		{
			if(pItem->data.IsAccept())	ofstr<<"acc";
			else ofstr<<"r"<<rule_list.GetCode(pItem->data);
		}
		ofstr<<"\t";

		/************GOTO部分************/

		for(j=0;j<vnnum;j++)						
		{
			for(p=convert_list.first;p;p=p->link)
				if(p->data.sentence[0]==vn[j]&&p->data.vn==i)					
					ofstr<<p->data.sentence[1];//<<"\t";
			ofstr<<"\t";
		}
		ofstr<<endl;
	}//end for
	for(i=0;i<(vtnum+vnnum+1);i++)	ofstr<<"________";
	ofstr<<"__"<<endl;
	ofstr<<"\n规则列表已经写入文件rule.txt中"<<endl;
	ofstr.close();
}