c++.cpp

词法分析是编译程序的第一个处理阶段

#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <stdlib.h>
const int MAX=30;
const int MAXSIZE=80;
char css[MAX][MAXSIZE];//存放产生式，并以'#'结束
int F[MAX][MAXSIZE];//二维数组表示FirstVT(P)表
int L[MAX][MAXSIZE];//二维数组表示LastVT(P)表
char strVN[MAX];//存放非终结符
char strVT[MAXSIZE];//存放终结符
int Priority_Table[MAX][MAX];//优先表
char Sentence[MAXSIZE];//用以存放用户从键盘上读入一个句子,最大长度不超过MAXSIZE个字符
int CountVT;//存放终结符个数
int CountVN;//存放非终结符个数
int SCount;//存放句子长度
int Maxline;//存放输入产生式的个数
typedef struct
{
	char VN;//非终结符，均用大写英文字母表示
	char VT;//终结符，算符或小写英文字母或分隔符
}VNODE;
typedef struct
{
	VNODE *base;
	int top;//栈顶指针
}Stack;
void InitStack(Stack &S)
{
	S.base=new VNODE[MAXSIZE];
	S.top=-1;
}
int IsEmptyStack(Stack S)
{
	if(S.top<=-1)
		return 1;
	return 0;
}
void ClearStack(Stack &S)
{
	S.top=-1;
}
void Push(Stack &S,char P,char a)
{
	if(S.top>=MAXSIZE)
	{
		cerr<<"Stack is overflow!"<<endl;
		exit(0);
	}
    S.top++;
	S.base[S.top].VN=P;
	S.base[S.top].VT=a;
}
void Pop(Stack &S,char &Q,char &a)
{
	if(S.top<=-1)
	{
		cerr<<"Stack is empty!"<<endl;
		exit(0);
	}
	Q=S.base[S.top].VN;
	a=S.base[S.top].VT;
	S.top--;
}
int IsVN(char ch)
{
	if(ch>='A'&&ch<='Z')
		return 1;
	return 0;
}//IsVN()

int IsVT(char ch)
{
	if(!IsVN(ch)&&ch!='|')
		return 1;
	return 0;
}//IsVT()

void SearchVT()
{
	int i=0,j,k=0,l;
	while(strcmp(css[i],"#")!=0)
	{
		j=3;
		while(css[i][j]!='\0')
		{
			if(IsVT(css[i][j]))
			{
				if(k==0)
                   strVT[k++]=css[i][j];
				else{
				      for(l=0;l<k&&css[i][j]!=strVT[l];l++);
					    if(l>=k)
						strVT[k++]=css[i][j];
				}//else
			}
			j++;
		}
		i++;
	}
	strVT[k++]='#';
	CountVT=k;
}//SearchVT()

void SearchVN()
{
	int i=0,j=0,k;
	while(strcmp(css[i],"#")!=0)
	{
		if(j==0)
		  strVN[j++]=css[i][0];
		else{
			for(k=0;k<j&&css[i][0]!=strVN[k];k++);
			if(k>=j)
				strVN[j++]=css[i][0];
		}//else
		i++;
	}
	CountVN=j;
}//SearchVN()

int IsSFWF()//判断是否为算符文法
{
	int i=0,j,k;
	char *p;
	while(strcmp(css[i],"#")!=0)
	{
		p=css[i];j=3;//前三个分别存放非终结符和尖号，即"P->"
		while(*(p+j)!='\0')
		{
			k=j;
			if(IsVN(*(p+j)))
			{
				j++;
				if(*(p+j)!='\0'&&IsVN(*(p+j)))
					return 0;
				else if(*(p+j)=='\0') 
					   break;
				if(*(p+j)!='\0'&&(IsVT(*(p+j))||*(p+j)=='|'))
				{
					j=k+1;
					continue;
				}
			}
			j++;
		}
		i++;
	}
	return 1;
}//IsSFWF()

int Ch_to_Num(char ch)
{
	int i;
	if(IsVT(ch))
	{
	   for(i=0;i<CountVT;i++)
	      if(ch==strVT[i])
		    return i+1;
	}
	if(IsVN(ch))
	{
        for(i=0;i<CountVN;i++)
		   if(ch==strVN[i])
			  return i+1;
	}
	return 0;//表示不存在或没有找到
}//Ch_to_Num()

void Insert(Stack &S,char P,char a,int flag)//flag是标志，其中0代表置F表，1代表置L表
{
	int i,j;
	i=Ch_to_Num(P);
	j=Ch_to_Num(a);
	if(i>0&&j>0)
	{
	  switch(flag)
	  {
	  case 0: if(!F[i-1][j-1])
				  F[i-1][j-1]=1;break;
	  case 1: if(!L[i-1][j-1])
				  L[i-1][j-1]=1;break;
	  }
	Push(S,P,a);//入栈 
	}
}//Insert()

void FirstVT(Stack S)//构造F[][]表
{
	int i,j;
	char Q,a;
	for(i=0;i<CountVN;i++)
		for(j=0;j<CountVT-1;j++)
			F[i][j]=0;
	i=0;
	while(strcmp(css[i],"#")!=0)
	{
		if(css[i][3]!='\0')
		{
		  if(IsVT(css[i][3]))//形如"P->a..."产生式
			Insert(S,css[i][0],css[i][3],0);
	      else if(IsVN(css[i][3]))
		  {
			if(css[i][4]!='\0'&&IsVT(css[i][4]))//形如"P->Qa..."产生式
				Insert(S,css[i][0],css[i][4],0);
		  }//else if
		}//if
		i++;
	}//while
	while(!IsEmptyStack(S))
	{
		Pop(S,Q,a);
		i=0;
		while(strcmp(css[i],"#")!=0)
		{
			if(css[i][3]==Q&&Q!=css[i][0])//注意！！！
				Insert(S,css[i][0],a,0);
			i++;
		}//while
	}//while
	//下面输出该表
	    cout<<"  ";
        for(i=0;i<CountVT-1;i++)
          cout<<strVT[i]<<"  ";
	    cout<<endl;
	    for(i=0;i<CountVN;i++)
		{
		cout<<strVN[i]<<" ";
		for(j=0;j<CountVT-1;j++)
			cout<<F[i][j]<<"  ";
		cout<<endl;
		}
	//输出FirstVT(P)
		for(i=0;i<CountVN;i++)
		{
			cout<<"FirstVT("<<strVN[i]<<")={ ";
			for(j=0;j<CountVT-1;j++)
				if(F[i][j]==1)
					cout<<strVT[j]<<" ";
			cout<<"}"<<endl;
		}
}//FirstVT()

void LastVT(Stack S)//构造L[][]表
{
	int i,j,k;
	char Q,a;
	for(i=0;i<CountVN;i++)
		for(j=0;j<CountVT-1;j++)
			L[i][j]=0;
	i=0;
	while(strcmp(css[i],"#")!=0)
	{
		k=strlen(css[i]);
		if(k>3)
		{
			if(IsVT(css[i][k-1]))//该产生式最后字符是终结符
				Insert(S,css[i][0],css[i][k-1],1);
			if(IsVN(css[i][k-1])&&k>4)//该产生式最后字符是非终结符,并且该产生式右部不止一个符号
			{
				if(IsVT(css[i][k-2]))
					Insert(S,css[i][0],css[i][k-2],1);
			}
		}
		i++;
	}//while
    while(!IsEmptyStack(S))
	{
		Pop(S,Q,a);
		i=0;
		while(strcmp(css[i],"#")!=0)
		{
			if(css[i][strlen(css[i])-1]==Q&&Q!=css[i][0])//注意！！！
				Insert(S,css[i][0],a,1);
			i++;
		}//while
	}//while
	//下面输出该表
	cout<<"  ";
        for(i=0;i<CountVT-1;i++)
          cout<<strVT[i]<<"  ";
	    cout<<endl;
	    for(i=0;i<CountVN;i++)
		{
		cout<<strVN[i]<<" ";
		for(j=0;j<CountVT-1;j++)
			cout<<L[i][j]<<"  ";
		cout<<endl;
		}
	//输出LastVT(P)
		for(i=0;i<CountVN;i++)
		{
			cout<<"LastVT("<<strVN[i]<<")={ ";
			for(j=0;j<CountVT-1;j++)
				if(L[i][j]==1)
					cout<<strVT[j]<<" ";
			cout<<"}"<<endl;
		}
}//LastVT()

void Prio_Table()//构造算符优先表
{
	int i,j,k,m,n;
	for(i=0;i<CountVT;i++)//优先表中1代表从横向看，横向算符优先级高于纵向算符
		for(j=0;j<CountVT;j++)//0表示优先级相同，－1表示横向算符优先级低于纵向算符
			Priority_Table[i][j]=2;//2表示两者不可比，初始化全为不可比
	i=0;
	while(strcmp(css[i],"#")!=0)
	{
		for(j=3;j<(strlen(css[i])-1);j++)//在每行中一个一个的寻找
		{
			if(IsVT(css[i][j]))
			{
				if(IsVT(css[i][j+1]))
				{
					m=Ch_to_Num(css[i][j]);
					n=Ch_to_Num(css[i][j+1]);
					if(m>0&&n>0)
					{
						if(Priority_Table[m-1][n-1]==2)
					       Priority_Table[m-1][n-1]=0;
						else {//有多重入口
							  cerr<<"Error! This isn't a SFYXWF!!"<<endl;
							  exit(0);
						}
					}//if
				}
				else if(IsVN(css[i][j+1]))
				{
					m=Ch_to_Num(css[i][j]);
					n=Ch_to_Num(css[i][j+1]);
					for(k=0;k<CountVT&&n>0;k++)
					{
						if(F[n-1][k]&&m>0)
						{
							if(Priority_Table[m-1][k]==2)
					           Priority_Table[m-1][k]=-1;
						    else {//有多重入口
							      cerr<<"Error! This isn't a SFYXWF!!"<<endl;
							      exit(0);
							}
						}//if
					}//for
				}//else if
				if((j<=(strlen(css[i])-3))&&IsVT(css[i][j+2]))
				{
					m=Ch_to_Num(css[i][j]);
					n=Ch_to_Num(css[i][j+2]);
					if(IsVN(css[i][j+1])&&m>0&&n>0)
					{
						if(Priority_Table[m-1][n-1]==2)
					       Priority_Table[m-1][n-1]=0;
						else {//有多重入口
							cerr<<"Error! This isn't a SFYXWF!!"<<endl;
							exit(0);
						}
					}//if
				}
			}//第一个if
			else if(IsVN(css[i][j]))
			{
				if(IsVT(css[i][j+1]))
				{
					m=Ch_to_Num(css[i][j]);
					n=Ch_to_Num(css[i][j+1]);
					for(k=0;k<CountVT;k++)
					{
						if(m>0&&n>0&&L[m-1][k])
						{
							if(Priority_Table[k][n-1]==2)
                               Priority_Table[k][n-1]=1;
						    else {//有多重入口
							      cerr<<"Error! This isn't a SFYXWF!!"<<endl;
							      exit(0);
							}
						}//if
					}//for
				}//if
			}//else if
		}//for
	i++;
	}//while
	for(i=0;i<CountVT;i++)
	{
		if(strVT[i]!=')')
			Priority_Table[CountVT-1][i]=-1;
	}
	for(i=0;i<CountVT;i++)
	{
		if(strVT[i]!='(')
			Priority_Table[i][CountVT-1]=1;
	}
	Priority_Table[CountVT-1][CountVT-1]=0;//两个＃号的优先级约定为相同
	//下面输出该表
	cout<<" ";
        for(i=0;i<CountVT;i++)
          cout<<setw(4)<<strVT[i];
	    cout<<endl;	
		for(i=0;i<CountVT;i++)
		{
			cout<<strVT[i];
			for(j=0;j<CountVT;j++)
				cout<<setw(4)<<Priority_Table[i][j];
			cout<<endl;
		}
}//Prio_Table()

int Is_SFYXWF()
{
	int i,j;
	for(i=0;i<CountVN;i++)
		for(j=0;j<CountVT;j++)
			if(Priority_Table[i][j]!=-1&&Priority_Table[i][j]!=0&&
				Priority_Table[i][j]!=1&&Priority_Table[i][j]!=2)
				return 0;
	return 1;
}//Is_SFYXWF()

void Analysis_Prog()//构造分析程序
{
	int i,j,k,m,n,l,t,tt;
	char S[MAXSIZE];//符号栈
	char Q,a;//接收字符变量
	k=1;l=0;
	S[k]='#';//首先把＃号压入栈低
	while(l<SCount)
	{   
		a=Sentence[l++];
		if(IsVT(S[k]))
			 j=k;
		else j=k-1;
		m=Ch_to_Num(S[j])-1;
		n=Ch_to_Num(a)-1;
		while(Priority_Table[m][n]==1)
		{
			do
			{
				Q=S[j];
				m=Ch_to_Num(Q)-1;
				if(IsVT(S[j-1]))
					 j=j-1;
				else j=j-2;
				if(j<=0)//表明句子输入有错误
				{
					cerr<<"Fail! The sentence is illegal!"<<endl;
					return;
				}
				n=Ch_to_Num(S[j])-1;
			}while(Priority_Table[n][m]!=-1);//找到在该算符前的第一个比它优先级低的算符的位置
            for(m=j+1;m<=k;m++)//在即将归约串中寻找终结符
				if(IsVT(S[m]))
					tt=S[m];
			i=0;
			while(strcmp(css[i],"#")!=0)//归约
			{
				n=3;
				while(n<=(strlen(css[i])-1))
					if(css[i][n]==tt&&((k-j)==strlen(css[i])-3))
					{	
						for(t=j+1;t<=k;t++)
						    cout<<S[t];
					    cout<<"-->";
					    k=j+1;
					    S[k]=css[i][0];
					    cout<<css[i][0]<<endl;
						break;
					}
					else n++;
				i++;
			}//while归约
			if(i>Maxline)//在所有产生式中没有一个符合归约要求
			{
				cerr<<"Fail! The sentence is illegal!!"<<endl;
				return;
			}		
			m=Ch_to_Num(S[j])-1;
			n=Ch_to_Num(a)-1;
		}//while
		if((Priority_Table[m][n]==-1)||(Priority_Table[m][n]==0))
		{
			k=k+1;
			S[k]=a;
		}//if
		else{
				cerr<<"The sentence is illegal!!!"<<endl;
				return;
		}
	}//第一个while
	if(k==3&&S[3]=='#')//出口,当栈中是＃开始符号＃,表明归约成功
	{
		cout<<"Success!!!"<<endl;
		return;
	}
	else{//出口,归约失败
		 cout<<"Fail! The sentence is illegal!!!"<<endl;
		 return;
	}
}//Analysis_Prog()

void Input_Example()
{
	int i=0;
	char str[MAXSIZE];//限定产生式的最大长度不超过MAXSIZE个字符
	cout<<"*********************Input Example!************************"<<endl; 
	cout<<"Input the wenfa(end in '#'):                              *"<<endl;
	cout<<"E->E+T                                                    *"<<endl;
    cout<<"E->T                                                      *"<<endl;
	cout<<"T->T*F                                                    *"<<endl;
	cout<<"T->F                                                      *"<<endl;
	cout<<"F->(E)                                                    *"<<endl;
	cout<<"F->i                                                      *"<<endl;
	cout<<"#                                                         *"<<endl;
	cout<<"**********************Example End!!************************"<<endl;
	cout<<"Input the wenfa(end in '#'):"<<endl;
	while(1)
	{
		cin>>str;
		if(strcmp(str,"#")==0)
			break;
		else strcpy(css[i++],str);
	}
	strcpy(css[i],"#");//'#'放在产生式最后，即放在css[]的最后一行;作为输入结束标志
	Maxline=i;//记下当前产生式个数
}//Input_Example
	
void main()
{
	int i;
	char ch;
	Stack S;//定义栈
	Input_Example();//从键盘上读入
	cout<<"---------------------------文法分析开始----------------------------"<<endl;
	if(!IsSFWF())
	{
		cout<<"This is a illegal SfWF!!"<<endl;
		return;
	}
		cout<<"This is a legal SFWF!"<<endl;
	    cout<<"***************************************************"<<endl; 
	    InitStack(S);//初始化栈
	    SearchVT();//寻找终结符，并存放在数组strVT[]中
		cout<<"终结符数组strVT[]:"<<endl;
        for(i=0;i<CountVT;i++)
         cout<<strVT[i]<<"  ";
	    cout<<endl;
        SearchVN();//寻找非终结符，并存放在数组strVN[]中
		cout<<"非终结符数组strVN[]:"<<endl;
        for(i=0;i<CountVN;i++)
		 cout<<strVN[i]<<"  ";
	    cout<<endl;
		cout<<"***************************************************"<<endl; 
        cout<<"(数1代表FirstVT(P)包含此终结符,0 则不包括!)"<<endl;
        cout<<"The FirstVT_Table is"<<endl;
        FirstVT(S);//生成FirstVT表,并存放在二维数组F[][]中
	    cout<<"***************************************************"<<endl;
        ClearStack(S);//清空栈
        cout<<"(数1代表LastVT(P)包含此终结符,0则不包括!)"<<endl;
     	cout<<"The LastVT_Table is:"<<endl;
	    LastVT(S);//生成LastVT表,并存放在二维数组L[][]中
	    cout<<"***************************************************"<<endl;    
		cout<<"(以横向看，数1代表前者优先级高,0代表相同,"<<endl;
		cout<<" 而－1代表前者优先级低,2代表不可比!)"<<endl;
		cout<<"The Priority_Table is:"<<endl;
		Prio_Table();//生成算符优先表，并存放在Priority_Table[][]中
		if(!Is_SFYXWF())
		{
			cout<<"This isn't a SFYXWF!!!"<<endl;
			return;
		}
		cout<<"This is a SFYXWF!!!"<<endl;
        cout<<"***************************************************"<<endl;
		cout<<"Please input a sentence(end in '#'):"<<endl;
		i=0;
        cin>>ch;
		while(ch!='#')//句子将以＃号作为结束
		{
			Sentence[i++]=ch;
			cin>>ch;
		}
		Sentence[i++]='#';//最后将＃号放在句子最后面
		SCount=i;//句子长度
		cout<<"归约过程如下:"<<endl;
		Analysis_Prog();//构造分析程序,并输出产生式归约的过程
        cout<<"***************************************************"<<endl;
		cout<<"---------------------------文法分析结束----------------------------"<<endl;
}