pre_table.cpp

本程序主要实现预测分析表的构造

#include "pre_table.h"
/*
求FIRST集合和FOLLOW集合 
*/
void Pre_Analysis_Table::First_And_Follow()
{
	LTerm *p=head;
	while(p!=NULL)     //求FIRST集合
	{
		First(p);
		p=p->next;
	}
	p=head;
	head->follow+='#'; //求FOLLOW集合 
	while(p!=NULL)
	{
		Follow(p);
		p=p->next;
	}
}

/*
判断ch是否在集合str中
*/
bool Pre_Analysis_Table::is_exist(char ch,string &str)
{
	for(int i=0;i<str.length();i++)
		if(ch==str[i])return true;
	return false;
}

/*
将集合from中的满足条件的元素假如集合to中
*/
void Pre_Analysis_Table::add(string &from,string &to,int fg)
{
	int len=to.length();
	for(int i=0;i<from.length();i++)
	{
		if(fg==1&&from[i]=='$')continue;  //判断空串是否加入：fg==0时加入
		for(int j=0;j<len;j++)			  //否则 fg==1时不加入。
			if(from[i]==to[j])break;
		if(j==len)to+=from[i];
	
	}
}

/*
寻找以非终结符ch为左部的规则的起始结点指针
*/
LTerm * Pre_Analysis_Table::go(char ch)
{
	LTerm *p=head;
	while(p!=NULL)
		if(p->gram[0]==ch)return p;
		else p=p->next;
	return NULL;
}

/*
输入文法并构造存储
*/
 void Pre_Analysis_Table::construct()
{
	string left,right;
	LTerm *pn,*qn;
	Term *pl,*ql;
	int i=0,size;
	cout<<"Input size:";
	cin>>size;
	while(i<size)
	{
		cout<<"left:";
		cin>>left;
		cout<<"right:";
		cin>>right;
		pn=new LTerm(left);
		if(i==0)			//当i==0表示处理的是第一条规则
		{
			head=pn;
			qn=pn;}
		else 
		{
			qn->next=pn;
			qn=pn;
		}
		for(int t=0,j=0;j<right.length();j++)
		{
			string tem;
			while(j<right.length()&&right[j]!='|')tem+=right[j++];
			pl=new Term(tem);
			if(t==0)		//当t==0表示处理的是规则的第一个右部
			{
				pn->link=pl;
				ql=pl;
			}
			else
			{
				ql->link=pl;
				ql=pl;
			}
			t++;     
		}
		i++;
	}
}
/*
求FIRST集合
*/
void Pre_Analysis_Table::First(LTerm *ptr)
{
	if(ptr==NULL||ptr->flag!=false)return;  //如果flag不为false表示当前规则的first集合已求得。
	Term *p=ptr->link;
	string str;
	while(p!=NULL)
	{
    Again:int i=0;
		  if(!isupper(p->gram[i]))    //若为非终结符号或空串
		  {
			  string tem;
			  tem+=p->gram[i];
			  add(tem,p->first);
		  }
		  else							//若为终结符号
		  {
			  LTerm *q=go(p->gram[i]);  //找p->gram[i]所在结点指针
			  First(q);					//求p->gram[i]的first集合
			  add(q->first,p->first);	
			  if(is_exist('$',q->first))
			  { 
				  i++;
				  goto Again;
			  }
		  }
		  add(p->first,str);
		  p=p->link;
	}
	ptr->first+=str;
	ptr->flag=true;
}

/*
求FOLLOW集合
*/
void Pre_Analysis_Table::Follow(LTerm *ptr)
{
	if(ptr==NULL||ptr->flag!=true)return;  //如果flag不为true表示当前规则的follow集合已求得。
	LTerm *p=head;			 //遍历规则的指针
	while(p!=NULL)
	{
		Term *q=p->link;	//遍历规则右部多种选择的指针
		while(q!=NULL)
		{
			for(int i=0;i<q->gram.length();i++)
				if(ptr->gram[0]==q->gram[i])    //若某一右部存在当前终结符号（正求其follow集合）。
				{
					int j=i+1;
					while(j<q->gram.length())
					{
						if(!isupper(q->gram[j]))  //若为终结符号，加入当前终结符号的follow后退出。	
						{
							string tem;
							tem+=q->gram[j];
							add(tem,ptr->follow);
							break;
						}
						else				//若为非终结符号,将其first集合(除空串外)加入当前非终结符号的follow.
						{
							LTerm *pt=go(q->gram[j]);
							add(pt->first,ptr->follow,1);
							if(!is_exist('$',pt->first))break;//若有空串，继续查看后续字符；否则退出。
							j++;
						}
					}
					if(j==q->gram.length()&&ptr!=p) //若当前非终结符号位于规则最后或其右部符号串的first集合
					{								//中存在空串，求相应左部的follow集合并加入当前非终结符
													//号的follow集合中。
						Follow(p);
						add(p->follow,ptr->follow);
					}
				}
				q=q->link;
		}
		p=p->next;
	}
	ptr->flag=false;
}


void Pre_Analysis_Table::print_First_And_Follow()
{
	LTerm *p=head;
	while(p!=NULL)
	{
		Term *q=p->link;
		cout<<"First("<<p->gram<<")=";
		print_set(p->first);
		cout<<endl;
		while(q!=NULL)
		{
			cout<<"First("<<q->gram<<")=";
			print_set(q->first);
			cout<<endl;
			q=q->link;
		}
		p=p->next;
	}
	p=head;
	while(p!=NULL)
	{
		cout<<"Follow("<<p->gram<<")=";
		print_set(p->follow);
		cout<<endl;
		p=p->next;
	}
}

void Pre_Analysis_Table::print_table()
{
	LTerm *p=head;
	while(p!=NULL)
	{
		Term *q=p->link;
		while(q!=NULL)
		{
			for(int i=0;i<q->first.length();i++)
				if(q->first[i]!='$')
					cout<<"["<<p->gram<<","<<q->first[i]<<"]="
					    <<p->gram<<"::="<<q->gram<<endl;
				else
				{
					for(int j=0;j<p->follow.length();j++)
						cout<<"["<<p->gram<<","<<p->follow[j]<<"]="
					        <<p->gram<<"::="<<q->gram<<endl;
				}
				q=q->link;
		}
		p=p->next;
	}
}




void Pre_Analysis_Table::print_set(string &str)
{
	cout<<" { ";
	for(int i=0;i<str.length();i++)
		cout<<str[i]<<" ";
	cout<<" }";
}

Pre_Analysis_Table::~Pre_Analysis_Table()
{
	LTerm *pn,*qn;
	Term *pl,*ql;
	pn=qn=head;
	while(pn!=NULL)
	{
		ql=pl=pn->link;
		while(pl!=NULL)
		{
			ql=pl;
			pl=pl->link;
			delete ql;
		}
		qn=pn;
		pn=pn->next;
		delete qn;
	}
}