liuziyan.cpp

本程序用于语法分析

     /*************************************************************/ 
     /*                                                           */
     /*    Name:Liu Ziyan;                                        */
     /*    Date:2005.1.9;                                         */
     /*    Function:for the first,follow and select collections;  */
     /*                                                           */
     /*************************************************************/
 

 # include <iostream.h>
 # include <ctype.h>
 # include <string.h>
 # include <windows.h>
	static int low=0; //记录文法的行数;
	static int first_temp_q=0; //存放first集的数组项的个数;
	static int follow_temp_q=0;//存放follow集的数组项的个数;
	static int select_temp_q=0;//存放select集的数组项的个数;
	static int  arry[sizeof(low)];//存放每个非终结符是否能推出ε的情况的数组;

    
    static char x[36][80];    //存放文法的数组;
	char first_temp[sizeof(first_temp_q)];//存放first集的数组;
	char follow_temp[sizeof(follow_temp_q)];//存放follow集的数组;
	char select_temp[sizeof(select_temp_q)];//存放select集的数组;

    void the_head(); //程序开头;
	void fill_char();//用字符 $ 填充x[36][80];
    void get_chars();//获取用户输入的文法;
    int  get_head_char(char cha);//获取用户输入的非终结符;
    void delete_team(char temp[],int q);//删除各集合中的多余组项;
    void find_zero() ;//将非终结符是否能推出ε的情况存于arry[]数组中;
	void display_char(int q,char temp[]);//显示各集合;
    void first(char temp[],char y,int q);//求first集;
    void follow(char temp[],char w,int q);//求follow集;
    void select(char temp[],int slow,int q);//求select集;

void main()
{
	 the_head();
	 fill_char();
	 cout<<"请输入您的上下文无关文法："<<endl;
	 get_chars();
	 find_zero();
     cout<<"请选择所要求解集合的类型："<<endl;
	 cout<<"   1  求first集;  "<<endl;
	 cout<<"   2  求follow集; "<<endl;
     cout<<"   3  求select集; "<<endl;
	 int i;
	 cin>>i;
	 cout<<"请输入您要求的字符:"<<endl;
	 char qjzf; //您输入的要求解的字符；
	 cin>>qjzf;
     switch(i)
	 {
	   case 1: first(first_temp,qjzf,first_temp_q);
		       display_char(first_temp_q,first_temp);
			   break;
	   case 2: follow(follow_temp,qjzf,follow_temp_q);
               display_char(follow_temp_q,follow_temp);
			   break; 
	 }
	/* for(int j=0;j<36;j++)
	 {
		 for(int i=0;i<80;i++)
		 {
			 //if(x[j][i]=='$')break;
			 cout<<x[j][i]<<" ";
		 }
		   cout<<endl;
	 }*/

}

void fill_char()
{
	for (int i=0;i<36;i++)
		for (int j=0;j<80;j++)
			x[i][j]='$';
}

void the_head()
{
	cout<<endl;
	cout<<endl;
	cout<<endl;
	for (int i=0;i<36;i++)
		cout<<"*";
	cout<<"使用须知";
	for (int j=0;j<36;j++)
		cout<<"*";
	cout<<endl;
	   cout<<"本程序用于求解您输入的上下文无关文法的first集,follow集和";
	   cout<<"select集，在这里我们假定您用所有的英文大写字母代表非终结符，";
       cout<<"所有的英文小写字母代表终结符。并用连续的两个@键代表上下";
	   cout<<"文文法输入完毕，进入求解……"<<endl;
	   cout<<endl;
		for (int k=0;k<80;k++)
			cout<<"*";
		cout<<endl;
		cout<<endl;

}

int  get_head_char(char cha)
{
	    if(isupper((int)cha)!=0)return 0;//若首符号为非终结符，则返回0；
        if(cha!='@')return 2;//若首符号为终结符且不为@时，则返回2；
		return 1;//若首符号为@，则返回1；		
}

void get_chars()
{ 
	char ch;
	for (int m=0;m<36;m++,low++)
	{
      for (int n=0;n<80;n++)
	  {
	       cin>>ch;
	   if  (n==0)
	   {
		  if(get_head_char(ch)==1)return;//若左部为@，则结束输入；
	      if( get_head_char(ch)==2)//若首符号不为非终结符且不为@时;
			{cout<<"对不起，请输入非终结符."<<endl;m=m-1;break;}
		  if(get_head_char(ch)==0)//若首符号为非终结符，则存入；
		  {x[m][n]=ch;continue;}
	   }
	   else
	   {	
        if(isupper((int)ch)!=0 || islower((int)ch)!=0)
		{ x[m][n]=ch;continue;}
	    if(n==1&&ch=='0'){x[m][n]='0';break;}
	    if(ch=='@')break;
	   }
	  }
	} 
}

void delete_team(char temp[],int q) 
{ //删除缓冲数组中的相同组项；
	for (int m=0;m<q;m++)
		for (int n=m+1;n<q;n++)
		{
			if (temp[m]==temp[n])
				for (int j=n;j<q;j++)
					temp[n]=temp[n+1];
		}
}

void find_zero() 
{ //求解非终结符是否能够推出ε;
  //并置标志位于数组arry[]中；
	int m,n,k;
	//int arry[sizeof(low)];

	for(m=0;m<low;m++)        //初始化标志数组arry[]；
		arry[m]=-1;

	for (m=0;m<low;m++)       
	{//第一遍扫描，若能推出第一个字符为ε则置0；
	 //若第一个字符为终结符则置1；	                      
		for (n=1;n<80;n++)
		{
			if(x[m][n]=='$')break;
			if(x[m][n]=='0')
			{
				arry[m]=0;
				break;
			}
			if(islower((int)x[m][n])!=0)
			{
				arry[m]=1;
				break;
			}
		}
	}
 /*	for (m=0;m<low;m++)       
	{ //第二遍扫描，若右部第一个是非终结符并且都能推出空，则置0；
		int j=0;
		if(arry[m]==-1)//若左部在表中的ε值仍为-1，则执行如下:
		{
			for (n=1;n<80;n++)
			{
				for(k=0;k<low;k++)
				{
					if(x[m][n]==x[k][0])
					{
						if(arry[k]==1)
						 //若左部推出的第n个字符是非终结符，
				         //且此符号不能推出ε；
						  arry[m]=1;//只要首符号所推出的符号串中有
						            //一个非终结符不能推出ε，就将
						            //其表中相映的数组置1；
						   break;
					}
				}
						
			}
			 arry[m]=0; //若左部所推出的符号串中所有
					    //非终结符都能推出ε，就将
					    //其表中相映的数组置0；
		}
	}*/
	
	for(m=0;m<low;m++)     
	{//一次扫描arry[]数组，若数组中存在多个非终结符相同	
	 //且致少有一个非终结符可以推出ε，则都置0；		            
		for(n=m+1;n<low;n++)
		{
			if(x[m][n]==x[n][0]&&(arry[m]==0||arry[n]==0))
			{
				arry[n]=0;
				arry[m]=0;
			}
		}
	}
	for(m=0;m<low;m++)        //否则就置1；
		if(arry[m]!=0)
			arry[m]=1;
}

void first(char temp[],char y,int q)
{//求字符的first集；
	if(islower((int)y)!=0)       //若为终结符，则加入集中；
	{
		temp[q]=y;
		q++;
		return;
	}
	if (isupper((int)y)!=0)       //若为非终结符，则求first集；
	{
		for (int i=0;i<low;i++)   //在非终结符中寻找匹配；
		{
			if(x[i][0]==y)        //找到匹配；
			{
				    //并且能够推出ε则；	
			
				if(islower((int)x[i][1])!=0)//推出的第一个字符为终结符则；
				{
					temp[q]=x[i][1];
					q++;
					return;
				}
				if(x[i][1]=='0')//推出的第一个字符为ε则；
				{
					temp[q]='0';
					q++;
					return;
				}
				for (int n=1;n<80;n++)
				{
					if (x[i][n]=='$')break;
					if(isupper((int)x[i][n])!=0)//推出第一个字符为非终结符则；
					{
						for (int j=0;j<low;j++)//寻找匹配以便递归调用；
						{
							if(x[i][n]==x[j][0]&&arry[j]==0)//若能推出ε则；
							{
                                temp[q]='0';
					             q++;
								first(temp,x[i][n],q);
							  if(x[i][n+1]!='$')
								first(temp,x[i][n+1],q);
							}
							else //若不能推出ε则；
							first(temp,x[i][n],q);
						}
					}
				}
			}
		}
	
	}
	 delete_team(temp,q);//整理集全中的多余项；
}

void follow(char temp[],char w,int q)
{
	//求解follow集；
	if (isupper((int)w)!=0)
	{
		for (int m=0;m<low;m++)
			for (int n=1;n<80;n++)
			{if(x[m][n]=='$')break;
				if (((x[m][1])=='0'&&w==(x[m][0]))||((w==(x[0][0]))))
				{
					temp[q]='#';
					q++;
				}
				if(x[m][n]==w)        
				{
					for (int j=0;j<low;j++)
					{
						if(x[m][n]==x[j][0])
						{
							first(temp,x[m][n+1],q);
							//上面的一行为求字符串的first集；
						}
					}
				}
			}
	}
	delete_team(temp,q); 
}

void select(char temp[],int slow,int q)
{
	for (int m=0;m<low;m++)
	{
		if(m==low)
		{
		 for (int n=1;n<80;n++)
		 {if(x[m][n]=='$')break;
			 for (int j=0;j<low;j++)
				if(x[m][n]==x[j][0])
				{
					first(temp,x[m][1],q);
                 if(arry[j]==0)
				    follow(temp,x[m][0],q);
				}
		 }
		}
	}
	delete_team(temp,q);
}



void display_char(int q,char temp[])
{
	for (int i=0;i<=q;i++)
	{
		cout<<"{ ";
		if(i<q)cout<<temp[q]<<',';
		else cout<<temp[q]<<" }"<<endl;
	}
}

int fun_find_zero(arry[],int m)
{ //第二遍扫描，若右部第一个符号是非终结符；       
 for (int n=1;n<80;n++)
 {
	for(int k=0;k<low;k++)
	{
	 if(x[m][n]==x[k][0])
	 {
		if(arry[k]==0)break;
		if(arry[k]==1)return arry[m]=1;				 				   
		if(arry[k]==-1)
		{
			if(fun_find_zero(arry[],k)==0)break;
			if(fun_find_zero(arry[],k)==1)return arry[k]=1;
            if(fun_find_zero(arry[],k)==-1)
			{
				for (int i=0;i<low;i++)
				{
					for(int j=0;j<80;j++)
					{
						if(x[i][j]=='$')break;
						if(x[m][n]==x[i][0])
							fun_find_zero(arry[],i);



						
					}
				}
						
			}
			 arry[m]=0; //若左部所推出的符号串中所有
					    //非终结符都能推出ε，就将
					    //其表中相映的数组置0；
		}
	}