subg.cpp

消除文法左递规算法的实现(此为可执行源代码)

#include"subg.h"

void sub_G::read_G_from(ifstream &infile)
{ /*===================================================================================
	 主要变量说明:
      "ch" 存放从文本中读出的文法左部字符用右部字符串;
  	 "temp" 临时存放从文本中读出的单个字符;
  	 "leftvn" 存放文法产生式的左部非终节字符;
  	 注:各产生式以";"分隔;
  ===================================================================================*/
	char *ch;
	char temp,leftvn;
	int i;
	while(!infile.eof())
	{
		i=0;
		infile>>temp;
		if((temp<='Z'&&temp>='A')||(temp<='z'&&temp>='a')||temp=='('||temp==')'||temp=='+'||temp=='*'||temp=='^')
		{
			ch=new char;
			while((temp<='Z'&&temp>='A')||(temp<='z'&&temp>='a')||temp=='('||temp==')'||temp=='+'||temp=='*'||temp=='^')
			{
				*(ch+i)=temp;
				i++;
				infile>>temp;
			}
			*(ch+i)='\0';
			if(temp=='-'&&i>1)             //文法左部超过两个字符时报错;
			{
				cout<<"文法中产生式有误...\n";
				return;
			}
			if(temp=='-'&&*ch<='Z'&&*ch>='A')
			{
				leftvn=*ch;
				insert_into_vn(leftvn);
			}
			else insert_into_s(leftvn,ch);
		}
	}	
}

void sub_G::write_G_to(ofstream &outfile)
{
	Cnode *pc;
	Snode *ps;
	pc=vn;
	while(pc)
	{
		outfile<<pc->c<<"->";
	    ps=pc->define;
		while(ps)
		{
			outfile<<ps->s;
			ps=ps->nexts;
			if(ps) outfile<<"|";
		}
			outfile<<"\n";
			pc=pc->nextc;
	}
}
 
void sub_G::remove_leftDG()
{
	Snode *R,*temp;
	Cnode *L,*H;
	int i,counter;
	L=vn;
	counter=0;
	while(L!=NULL)
	{
		H=vn;
		i=0;
		while(i<counter)
		{
			R=L->define;
			while(R!=NULL)
			  if(H->c==R->s[0])
			  {
				  temp=R->nexts;
				  replace_vn(H,R);
				  R=temp;
			  }
			  else
				  R=R->nexts;
			  H=H->nextc;
			  i++;
		}
	    R=L->define;
        while(R!=NULL)
		 if(H->c==R->s[0])
		  remove_DG(L);
		 else
		  R=R->nexts;
		L=L->nextc;
		counter++;
	}

}

void sub_G::replace_vn(Cnode* H,Snode* R)
{
	Snode *H_Right,*temp_R,*temp;
	char *H_Right_s,*R_s;
	int i=0;
	temp_R=R;
	R_s=new char;
	while(R->s[i]!=NULL)
	{
		R_s[i]=R->s[i+1];
		i++;
	}
	H_Right=H->define;
	while(H_Right!=NULL)
	{
		H_Right_s=new char;
		strcpy(H_Right_s,H_Right->s);
		if(temp_R==R)
		{
			R->s=strcat(H_Right_s,R_s);
			temp_R=R->nexts;
		}
		else
		{
			temp=new Snode;
			temp->s=strcat(H_Right_s,R_s);
			temp->nexts=temp_R;
			R->nexts=temp;
			R=temp;
		}
		H_Right=H_Right->nexts;
	}
}

void sub_G::remove_DG(Cnode *L)
{
	Cnode *LNext,*temp;
	Snode *L_Right,*L_PRight,*LNext_Right,*LNext_temp;
	char *str;
	L_Right=L->define;
	temp=L->nextc;
	LNext=new Cnode;
	LNext->c='$';
	L->nextc=LNext;
	LNext->nextc=temp;
	LNext->define=L->define;
	while(L_Right->s[0]==L->c)
	{
		L_PRight=L_Right;
		L_Right=L_Right->nexts;
	}
	L->define=L_Right;
	L_PRight->nexts=NULL;
	while(L_Right!=NULL)
	{
		strcat(L_Right->s,"$");
		L_Right=L_Right->nexts;
	}
	LNext_Right=LNext->define;
	while(LNext_Right!=NULL)
	{
		str=new char;
		strcpy(str,LNext_Right->s);
		LNext_Right->s=strcat(str+1,"$");
		LNext_Right=LNext_Right->nexts;
	}
	LNext_temp=new Snode;
	LNext_temp->s="@";
	L_PRight->nexts=LNext_temp;
	LNext_temp->nexts=NULL;	
}