lalr.cpp

为L语言设计一个语法分析器。 读入源程序

	List<CItem>	item_list;						
	int vtnum;									
	int vnnum;									
	const int start_symbol;						
	Queue<List<CItem> > state_queue;				
	List<CItem> convert_list;					
	List<CItem> rule_list;							
};

inline int GetStrLen(char *&buf)											
{
	char *pS=buf;
	for(int i=0;*pS!=-3;pS++,i++);
	return i;
}
//----------------------------------------------------------------------
//---------------------构造函数-----------------------------------------
CGRAMMAR::CGRAMMAR():start_symbol(-5)				
{
	char *buf,ch;
	List<char> buflist;							
	int i=0;
	ifstream fin("gramma.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;							
	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();
}
//----------------------------------------------------------------------
//---------------------析构函数-----------------------------------------
CGRAMMAR::~CGRAMMAR()							
{
	gn_list.MakeEmpty();
	item_list.MakeEmpty();
	convert_list.MakeEmpty();
	delete[]vt;
	delete[]vn;
	delete[]vtstring;
	delete[]vnstring;
}
//----------------------------------------------------------------------
//---------------------------编码---------------------------------------
void CGRAMMAR::Encode(char *&buf)
{
	char *pS=buf;								
	int temp,flag(0);						
	Gener gener,g1,g2;
	List<Gener> temp_list;
	gener.vn=EncodeVn(*pS);					
	pS=pS+3;									
	int length=::GetStrLen(buf)-3;				
	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 CGRAMMAR::EncodeVn(char ch)							
{
	for(int i=0;i<vnnum;i++)
		if(ch==vnstring[i])
			return vn[i];
	return -1;
}
//----------------------------------------------------------------------
//---------------------终结符编码---------------------------------------
int CGRAMMAR::EncodeVt(char ch)							
{
	for(int i=0;i<vtnum;i++)
		if(ch==vtstring[i])
			return vt[i];
	if(ch=='$') return 0;
	return -1;
}
//----------------------------------------------------------------------
//---------------------解码---------------------------------------------
char CGRAMMAR::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 CGRAMMAR::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);
	}	
}
//----------------------------------------------------------------------
//---------------------构造CLOSURE(J)函数-------------------------------
void CGRAMMAR::Closure(List<CItem> &kernel)			
{
	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 CGRAMMAR::FromItoJ(CItem &item,List<CItem> &J)		
{														
	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);
			}
		}
	}
}
//----------------------------------------------------------
//--------------构造GO(I,X)函数-----------------------------
int CGRAMMAR::GO(const List<CItem> &I,int X,List<CItem> &J)		
{
	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 CGRAMMAR::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 CGRAMMAR::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 CGRAMMAR::PrintDFA()									//相当于DFA
{
	Queue<List<CItem> > q;																
	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";
	cout<<"**********  王茜 0372283  **********\n";
	List<int> change_list;
	while(!q.QueueEmpty())								
	{
		temp_list.MakeEmpty();	
		temp_list=q.QDelete();
		GetSymbol(temp_list,sym_list);				
		for(ListNode<int> *p=sym_list.first;p;p=p->link)
		{
			if(GO(temp_list,p->data,go_list))			
			{	
				int code=state_queue.GetCode(go_list);
				if(code==0)
				{
					q.QInsert(go_list);					
					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);			
				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)
			{
				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<<"\nLR(1)项目集族C:\n[X为拓广文法开始符号]\n";
	for(int i=1;i<=state_queue.rear;i++)			
	{
		cout<<"I"<<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;
}
//---------------------------------------------------------------
//-------------------写规则列表----------------------------------
char LR_new[26][26];
void CGRAMMAR::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<<":";
		for(ListNode<char> *q=char_list.first;q;q=q->link)
			ofstr<<q->data;
		ofstr<<endl;
		int tx = 0;
		if(p != rule_list.first)
		{
		for(ListNode<char> *nq=char_list.first;nq;nq=nq->link)
		{
			if(nq->data == '.')
				LR_new[count-1][tx] = '#';
			else
				LR_new[count-1][tx++] = nq->data; 
		}
		//ofstr<<endl;
		}
	}
	ofstr.close();
}
//---------------------------------------------------------------
//-------------------求FIRST集-----------------------------------
void CGRAMMAR::First(int symbol,List<int> &first_set)	
{
	if(symbol>0)
	{									
		first_set.Insert(symbol);
		return;
	}
	List<int> temp,mid;
	for(ListNode<Gener> *p=gn_list.first;p;p=p->link)
		if(p->data.vn==symbol&&p->data.sentence[0]!=symbol)