classpt.cpp

LL(1)文法

#include "StdAfx.h"
#include "ClassPt.h"


CString Compare(CString,CString);

void ClassPt::Empty()
{
	int i;
	Count=0;
	NewNonTerminator='A';
	for(i=0;i<50;i++)
	{
		pleft[i].Empty();
		pright[i].Empty();
		priority[i]=9;     //优先级设置为最大，用于文法排序
	}
}



bool ClassPt::RecordDel(CString left,CString right)
{
	int i,j;
	for(i=0;i<Count;i++)
	{
		if(left==pleft[i] && right==pright[i])
		{
			for(j=i;j<Count-1;j++)
			{
				pleft[j]=pleft[j+1];
				pright[j]=pright[j+1];								
			}
			pleft[j].Empty();
			pright[j].Empty();
			priority[j]=9;
			Count--;
			return(true);
		}
	}
	return(false);
}

int ClassPt::RecordDel(CString left)
{
	int i,j;
	int num=0;
	for(i=0;i<Count;i++)
	{
		if(left==pleft[i])
		{
			for(j=i;j<Count-1;j++)
			{
				pleft[j]=pleft[j+1];
				pright[j]=pright[j+1];								
			}
			pleft[j].Empty();
			pright[j].Empty();
			priority[j]=9;
			Count--;
			i--;
			num++;
		}
	}
	return(num);
}

bool ClassPt::RecordFind(CString left)
{
	int i;
	for(i=0;i<Count;i++)
	{
		if(left==pleft[i])
			return(true);
	}
	return(false);
}

void ClassPt::RecordApp(CString left,CString right)
{
	pleft[Count]=left;
	pright[Count]=right;
	Count++;
}

void ClassPt::GetInVn(CString str)          //录入原始非终结符集
{
	Vn.Empty();
	Vn=str;

}

void ClassPt::GetInVnPrimal(CString str)
{
	VnPrimal.Empty();
	VnPrimal=str;
}

CString ClassPt::GetNewVn()                //得到ClassPt类的所有非终结符集
{
	int i;
	CString Vnn;
//	Vn.Empty();
	Vnn.Empty();
	for(i=0;i<Count;i++)
	{
		if(VnPrimal.Find(pleft[i][0])!=-1 && Vnn.Find(pleft[i][0])==-1)
			Vnn+=pleft[i][0];
	}
	for(i=0;i<Count;i++)
	{
		if(Vnn.Find(pleft[i][0])==-1)
			Vnn+=pleft[i][0];

	}
	Vn=Vnn;
	return(Vn);
}

void ClassPt::SetStarter()                        //设置文法开始符号
{
	Starter=pleft[0][0];
}

void ClassPt::GetNewNonTerminator()             //得到一个新的非终结符
{
	GetNewVn();	
	while(Vn.Find(NewNonTerminator)!=-1)
		NewNonTerminator++;
	Vn+=NewNonTerminator;
	

}

void ClassPt::RemoveDirectLeftRecursion(CString left)     //消除直接左递归
{
	int i;
	GetNewNonTerminator();
	for(i=0;i<Count;i++)
	{
		if(pleft[i]==left)
		{
			if(pright[i][0]==left)
			{
				pleft[i]=NewNonTerminator;
				pright[i].Delete(0,1);
				pright[i]+=NewNonTerminator;
			}
			else
			{
				pright[i]+=NewNonTerminator;
			}			
		}
	}
	RecordApp(NewNonTerminator,"ε");
	

}

void ClassPt::InsteadOf(CString ToInstead,CString BeInstead)
{
	int i,j,jmax;
	CString buffer[10];
	CString BufferLeft,BufferRight;
	CString left,right;
	for(i=0;i<10;i++)
		buffer[i].Empty();
	j=0;
	for(i=0;i<Count;i++)            //将ToInstead的右部存入buffer
	{
		if(pleft[i]==ToInstead)
		{
			buffer[j]=pright[i];
			if(buffer[j]=="ε")
				buffer[j].Empty();
			j++;
		}
	}
	jmax=j;
	for(i=0;i<Count;i++)
	{
		if(pleft[i]==BeInstead && pright[i][0]==ToInstead)
		{
			BufferLeft=pleft[i];
			BufferRight=pright[i];
			BufferRight.Delete(0,1);
			
			pright[i]=BufferRight;
			pright[i].Insert(0,buffer[0]);
			if(pright[i]=="")
				pright[i]="ε";
			for(j=1;j<jmax;j++)
			{
				left=BufferLeft;
				right=BufferRight;
				right.Insert(0,buffer[j]);
				if(right=="")
					right="ε";
				RecordApp(left,right);
			}
		}
	}

}

void ClassPt::SetPriority()             //设置文法优先级
{
	int i;                              
	int pos;
	for(i=0;i<Count;i++)
	{
		if(pleft[i]==Starter)          //开始符号优先级设置为0
			priority[i]=0;
		if(Vn.Find(pleft[i])!=-1 && pleft[i]!=Starter)
		{
			pos=Vn.Find(pleft[i]);                 //得到非终结符在Vn中位置,
			priority[i]=pos;                       //并设置为其优先级
		}
		if(Vn.Find(pleft[i])==-1)                  //新增加的非终结符
			priority[i]=8;                         //优先级设置为8

	}

}

void ClassPt::Sort()    //根据优先级对文法进行冒泡排序
{
	int i,j;
	CString buffer;
	for(i=0;i<Count;i++)         //将优先级插入文法左部第一位，准备排序
	{
		pleft[i].Insert(0,priority[i]);
	}
	for(i=0;i<Count-1;i++)
		for(j=i+1;j<Count;j++)
		{
			if(pleft[i]>pleft[j])
			{
				buffer=pleft[i];           //交换左部
				pleft[i]=pleft[j];
				pleft[j]=buffer;

				buffer=pright[i];          //交换右部
				pright[i]=pright[j];
				pright[j]=buffer;
			}
		}
	for(i=0;i<Count;i++)       //排序结束，将优先级从文法左部去除，还原文法
	{
		pleft[i].Delete(0,1);
	}

}

void ClassPt::ClearUselessSentence()     //清除无效文法
{
	GetNewVn();
	int i,j,k;
	int pos;
	bool CanReach[50];                   //CanReach记录各终结符是否可以达到,可以则赋值true
	for(i=0;i<50;i++)                    //数组初始化
		CanReach[i]=false;
	//////////////////////////////////////////
	//下面是计算文法是否可以达到算法的具体实现
	//////////////////////////////////////////
	pos=Vn.Find(Starter);              //设置文法开始符号为可到达
	CanReach[pos]=true;
	for(j=0;j<Count;j++)
	{
		for(i=0;i<Count;i++)
		{
			pos=Vn.Find(pleft[i][0]);
			if(CanReach[pos])             //如果左部可到达,则产生式中的非终结符都可以到达
			{
				for(k=0;k<pright[i].GetLength();k++)
				{
					pos=Vn.Find(pright[i][k]);
					if(pos!=-1)
					{
						CanReach[pos]=true;
					}
				}

			}

		}
	}


	//删除无效文法
	CString left,right;
	for(i=0;i<Count;i++)
	{
		pos=Vn.Find(pleft[i][0]);
		if(!CanReach[pos])
		{
			left=pleft[i];
			right=pright[i];
			RecordDel(left,right);
			i--;                   //删除一条语句后,Count自减,因此这里i也应该减1
		}
	}


}

bool ClassPt::PickupCommonFactor(char Letter,int length)
{
	int i,j;
	int pos;
	CString buffer1,buffer2;
	CString resemblance;
	bool Flag;
	pos=0;
	Flag=false;
	while(pleft[pos][0]!=Letter)
		pos++;

	for(i=pos;i<pos+length-1;i++)
		for(j=i+1;j<pos+length;j++)
		{
			resemblance=Compare(pright[i],pright[j]);     //比较两字符串是否有公因子
			if(!resemblance.IsEmpty())
			{
				pright[i].Delete(0,resemblance.GetLength());
				buffer1=pright[i];
				if(buffer1.IsEmpty())
					buffer1="ε";
				pright[j].Delete(0,resemblance.GetLength());
				buffer2=pright[j];
				if(buffer2.IsEmpty())
					buffer2="ε";
                pright[i].Empty();
				pright[i]=resemblance;
				GetNewNonTerminator();                //得到一个新的非终结符
				pright[i]+=NewNonTerminator;
				RecordDel(pleft[j],pright[j]);
				length--;
				RecordApp(NewNonTerminator,buffer1);
				RecordApp(NewNonTerminator,buffer2);
				j--;
				Flag=true;
				if(pleft[j][0]!=Letter)
					break;
				
			}
		}
		return(Flag);
}

int ClassPt::GetLength()
{
	return(Count);
}

int ClassPt::GetNum(char Letter)
{
	int Num=0;
	for(int i=0;i<Count;i++)
	{
		if(pleft[i][0]==Letter)
			Num++;
	}
	return(Num);
}

CString Compare(CString str1,CString str2)
{
	int pos=0;
	CString resemblance;
	resemblance.Empty();
	while(str1[pos]==str2[pos])
	{
		resemblance+=str1[pos];
		if(pos==str1.GetLength()-1 || pos==str2.GetLength()-1)
			return(resemblance);
		pos++;
	}
	return(resemblance);
}