ll(1).cpp

ll(1)语法分析器 编译原理实验课 必须的实验

#include<iostream.h>
#include<string.h>
#include<string.h>
#include<stdlib.h>
char M[6][10],N[6][6][10];
int m,n,yb=0,ft1,yc=0,yd=0;
#define FT 10
#define MAX -1
#define MAXSIZE 100
typedef struct TNFirst
{
	char value;
	char exp[10];
}TNFirst;
struct TNFirst ft[FT][FT];//First集合
typedef struct TNCfw
{ int id;
  int exit;
}TNCfw;
int DataNum=0;//栈中元素的个数
int save_j=0;//记录输入串位置
char Instr[10];
struct TNCfw cfw[FT][FT];//cfw记录把Follow(A)加入Follow(B)中去
char fw[FT][FT],outfw[FT][FT],outft[FT][FT][10],fx[FT][FT][10];//fw记录follow集合,outfw[FT][FT]为了输出;
typedef char datatype;
typedef struct
{
	datatype data[MAXSIZE];
	int top;
}Stack;
Stack g;
void StackInit(Stack *s)
{
   s->top=-1;
}
int StackEmpty(Stack *s)
{
	if(s->top>=0)
		return 0;
	return 1;
}
int Push(Stack *s,datatype a)
{   
	if(s->top==MAXSIZE-1)
	  cout<<"堆栈已满";
	else
	{s->top++;
	 s->data[s->top]=a;
	 DataNum=s->top;
	}
	return DataNum;
}
int Pop(Stack *s)
{   
	if(StackEmpty(s))
	{cout<<"栈为空,不能出栈";
	 return NULL;
	}
	else
	{ s->top--;
      DataNum=s->top;
	}
	return DataNum;
}
datatype GetTop(Stack *s)
{
	if(StackEmpty(s))
	{ cout<<"栈为空!";
	  return NULL;
	}
	else
		return (s->data[s->top]);
}
void Ft_FwInit()
{
	for(int i=0;i<FT;i++)
		for(int j=0;j<FT;j++)
		{
			ft[i][j].value='\0';
			cfw[i][j].id=MAX;
			outfw[i][j]='\0';
			fw[i][j]='\0';
		  for(int k=0;k<FT;k++)
		  {
			  outft[i][j][k]='\0';
			  fx[i][j][k]='\0';
		  }
		}
}
void Init() 
{
	for(int i=0;i<FT;i++)
		for(int j=0;j<FT;j++)
		  cfw[i][j].id=MAX;
}
int Location(char a[],char c,int x)//查询方法位置
{
	for(int i=0;i<x;i++)
		if(a[i]==c)
		 return i;
		return -1;
		
}
int IsUcase(char a)//判断是不是标识符
{
	if(a>='A' && a<='Z')
		return 1;
    else
	    return 0;
}
void clear(char a[])//清空ft
{
	for(int i=0;i<6;i++)
	  a[i]='\0';
}
void separate()//把TEF|a分成TEF,a
{
	for(int i=0;i<m;i++)
	{ char *str=M[i];
	  for(int j=0;*str!='\0';j++)
	  { 
		for(int k=0;*str!='|' && *str!='\0';k++)
		{ N[i][j][k]=*str;
		   str++;
		}
		N[i][j][k]='\0';
		if(*str!='\0')
		str++;
	  }
	  N[i][j][0]='\0';
	}
}
void First(char a[],char b)//求First并赋给ft[][];
{
	int x;
	x=Location(a,b,m);
	for(int i=0;N[x][i][0]!='\0';i++)
	{ char *str=N[x][i];
	  if(x==ft1)
          yd=i;
	  if(IsUcase(*str))
		  First(a,*str);
	  else
	  {
		  ft[ft1][yb].value=*str;
		  strcpy(ft[ft1][yb].exp,N[ft1][yd]);
		  yb++;
	  }
	}
}
void AddFollow(char a[],char s,char e)//A->aB或A->aB@把follow(A)加入follow(B)中
{
	int x,y;
	int i=0;
	x=Location(a,e,m);
	y=Location(a,s,m);
	while(cfw[x][i].exit==1)
		i++;
	cfw[x][i].id=y;
	cfw[x][i].exit=1;
}
void follow1(char a[],char b)//A->aB或A->aB@把follow(A)加入follow(B)中
{         int x,y;
          x=Location(a,b,m);
		 for(int i=0;N[x][i][0]!='\0';i++)
		 { char *str=N[x][i];
		   while(*(str+1)!='\0')
			   str++;
            if(IsUcase(*str))
				AddFollow(a,b,*str);
			 while(*str!=N[x][i][0])
			 {
			     y=Location(a,*str,m);
				 for(int j=0;j<FT;j++)
				 {
				   if(ft[y][j].value=='#')
				   { AddFollow(a,b,*(str-1));
				     break;
				   }
				 }
				 str--;
			 }
			 
		 }
}

void follow2(char a[],char b)//求A->Aa或A->AB，则Follow(A)={a},或Follow(A)={First(B)}
{
    int x;
	x=Location(a,b,m);
	for(int i=0;i<m;i++)
	{	for(int j=0;N[i][j][0]!='\0';j++)
		{	char *str=N[i][j];
		     while(*str!='\0')
			 { 
				if(*str==b)
				{	if(*(str+1)!='\0')
					{	if(IsUcase(*(str+1)))
						{
							int y;
							y=Location(a,*(str+1),m);
							for(int k=0;ft[y][k].value!='\0';k++)
							{  int y1=0;
							   while(ft[y][k].value=='#' && ft[y][k].value!='\0')
							    k++;
							  if(ft[y][k].value=='\0')
								  break;
							  for(int k1=0;fw[x][k1]!='\0';k1++)
							  {
								  if(fw[x][k1]==ft[y][k].value)
                                        y1=1;
							  }
							  if(y1!=1)
							  {fw[x][yc]=ft[y][k].value;
							  yc++;
							  }
							}
						}
						else
						{ 
							fw[x][yc]=*(str+1);
						    yc++;
							
						}
					}
					else
					{   int t=0;
						for(int k2=0;k2<yc;k2++)
						{if(fw[x][k2]=='$')
                                t=1;
						}
						if(t!=1)
						{
						fw[x][yc]='$';
					    yc++;
						}
					}
				}
					str++;
			 }
		}
						  
	}                     
}
void follow3()//如果A->@B或A->@B&且&->#,把Follow(A)加入到Follow(B)中去
{ int x,z;
  for(int i=0;i<m;i++)
  {
	for(int j=0;cfw[i][j].id>=0;j++)
	{  
	   x=cfw[i][j].id;
	   for(int k=0;fw[x][k]!='\0';k++)
	   {    
	        z=0;
	       for(int l=0;fw[i][l]!='\0';l++)
		   { if(fw[i][l]==fw[x][k])
		       z=1;
		   }
		   if(z==0)
			  fw[i][l]=fw[x][k];
	   }
	 }
  }
}
void Start_$()//把$加入到follow[S],S是起始字符
{   int x;
	for(int i=0;fw[0][i]!='\0';i++)
	{	if(fw[0][i]=='$')
			x=1;
	}
		if(x!=1)
			fw[0][i]='$';
}
void follow4(char b[])//在First中A->#把#加入到fw[A]对应的outfw[][]中去;为了输出！
{
   for(int i=0;i<m;i++)
   {  
	   for(int j=0;N[i][j][0]!='\0';j++)
	   {
		   if(N[i][j][0]=='#')
	      {
		     for(int k=0;fw[i][k]!='\0';k++)
			 {
			  int x=fw[i][k];
			  x=Location(b,x,n+1);
			  outfw[i][x]='#';
			 }
		   }
		}
   }
   for(int i1=0;i1<m;i1++)
   {  
	   for(int j1=0;ft[i1][j1].value!='\0';j1++)
	   {
		    int x;
			x=Location(b,ft[i1][j1].value,n+1);
			if(x>=0)
            strcpy(outft[i1][x],ft[i1][j1].exp);
		}
   }
}
void Output(char Vn[],char Vt[])
{
	cout<<"  ";
	for(int i=0;i<=n;i++)
	{ cout<<Vt[i]<<'\t'<<"   ";
	}
	cout<<endl;
	for(int j=0;j<m;j++)
	{ cout<<Vn[j]<<" ";
	  for(int k=0;k<=n;k++)
	  {   
		  if(outft[j][k][0]=='\0')
	         cout<<outft[j][k]<<'\t';
		  else
		     cout<<Vn[j]<<"->"<<outft[j][k]<<'\t';
	  }
	   cout<<"     "<<endl;
	   for(int k1=0;k1<=n;k1++)
	   { 
		   if(outfw[j][k1]=='\0')
			  cout<<outfw[j][k1]<<'\t';
		   else
		       cout<<Vn[j]<<"->"<<outfw[j][k1]<<'\t';
	   }
	   cout<<endl;
	}
}
void Union()//归并outft和outfw到fx[][]中去;
{
	for(int i=0;i<m;i++)
		for(int j=0;j<=n;j++)
			strcpy(fx[i][j],outft[i][j]);
   for(int i1=0;i1<m;i1++)
		for(int j1=0;j1<=n;j1++)
		{
		  if(outfw[i1][j1]!='\0'&&fx[i1][j1][0]!='\0')
		  {
			cout<<"该文法不是LL(1)文法！";
			exit(0);
		  }
		  if(outfw[i1][j1]!='\0')
			  fx[i1][j1][0]=outfw[i1][j1];

		}
		   
}
void LL1Action(char a[],char b[])//分析动作序列
{   char c;
    c=GetTop(&g);
	while(g.top>=0 && Instr[save_j]!='\0')
	{   int x,y,t=1;
		c=GetTop(&g);
		if(c==Instr[save_j])
		{ Pop(&g);
		  save_j++;
          for(int i=0;i<=DataNum;i++)
		  {
	         cout<<g.data[i];
		  }
		  cout<<"                   ";
		  for(int j=save_j;Instr[j]!='\0';j++)
			  cout<<Instr[j];
		  cout<<"                   "<<a[x]<<"->"<<fx[x][y]<<endl;
		}
		else
		{ Pop(&g);
		  x=Location(a,c,m);
		  y=Location(b,Instr[save_j],n+1);
          char *str=fx[x][y];
		  while(*(str+1)!='\0')
		  { str++;
		    t++;
		  }
		  while(t>0)
		  {   if(*str!='#')
			    Push(&g,*str);
			  str--;
			  t--;
		  }
		  for(int i=0;i<=DataNum;i++)
		  {
	         cout<<g.data[i];
		  }
		  cout<<"                   ";
		  for(int j=save_j;Instr[j]!='\0';j++)
			  cout<<Instr[j];
		  cout<<"                   "<<a[x]<<"->"<<fx[x][y]<<endl;
		}
	
	}
}
void main()
{ while(1)
{ Init();
  Ft_FwInit();
  cout<<"本分析器暂单个字母方法，#代表空串,#不要输入:"<<endl;
  cout<<"请输入非终结符的个数m:";
	 cin>>m;
  cout<<"请输入终结符的个数n:";
  cin>>n;
  char *Vn=new char[m];
  for(int i=0;i<m;i++)
  {cout<<"请输入非终结符";
	  cin>>Vn[i];
  }
  char *Vt=new char[n+1];
  for(int j=0;j<n;j++)
  { cout<<"请输入终结符";
	  cin>>Vt[j];
  }
   Vt[n]='$';
  
  for(int k=0;k<m;k++)
  {cout<<"请输入非终结符"<<Vn[k]<<"右部产生式:";
	  cin>>M[k];
  }
  separate();
  for(int k1=0;k1<m;k1++)
  {   yb=0;
      ft1=k1;
	  First(Vn,Vn[k1]);
	  

  }
  
  for(int k2=0;k2<m;k2++)
  {   yc=0;
	  follow1(Vn,Vn[k2]);//A->aB或A->aB@把follow(A)加入follow(B)中
	  follow2(Vn,Vn[k2]);//求A->Aa或A->AB
  }
  Start_$();
  follow3();
  for(int x=0;ft[x][0].value!='\0';x++)//输出First集合
  {  cout<<"First["<<Vn[x]<<"]: ";
	for(int y=0;ft[x][y].value!='\0';y++)
	  { cout<<ft[x][y].value;
	  }
	  cout<<endl;
  }
  cout<<endl;

  for(int x1=0;fw[x1][0]!='\0';x1++)//输出Follow集合
  {  cout<<"Follow["<<Vn[x1]<<"]: ";
	for(int y1=0;fw[x1][y1]!='\0';y1++)
	  { 
		cout<<fw[x1][y1];
	  }
	  cout<<endl;
  }
  follow4(Vt);
  cout<<"该方法预测分析表如下:"<<endl;
  Output(Vn,Vt);
  Union();
  cout<<endl;
  cout<<"================================以下是LL(1)分析动作序列:"<<endl;
  cout<<"请输入需要分析的词法串并以$结束:"<<endl;
  cin>>Instr;
  StackInit(&g);
  if(StackEmpty(&g))
  { Push(&g,'$');
    Push(&g,Vn[0]);
  }
  cout<<"栈                  "<<"输入                       "<<"输出"<<endl;
  for(int i3=0;i3<=DataNum;i3++)
  {
	  cout<<g.data[i3];
  }
  cout<<"                   "<<Instr<<endl;
  LL1Action(Vn,Vt);
}
}