acfl.cpp

给定一个上下文无关文法的n条产生式规则

********************************************************************************/
#include <fstream.h>
#include <string.h>
#include <ctype.h>

void main()
{
	int n,i;

	//**非终结符只有26个大写字母，所以总共只有26种可能****
	//如果值为1 表示该非终结符在下面的规则下可以转化为终结符
	//如果值为0 表示该非终结符在下面的规则下可以转化为终结符
    short int flag[26];
	
	ifstream input("input.txt");
	ofstream output("output.txt");
	input>>n;
	//用来存储规则的左边
	char *left=new char [n+1]; 
	
	//用来存储规则的右边
	char** right=new char* [n+1];

	//用来处理读取数据的中间过渡变量
	char tmp[500];
	
	//读取文本数据处理过程
	for(i=1;i<=n;i++)
	{
		input>>tmp;
		left[i]=tmp[0];
		input>>tmp;
		right[i]=new char [strlen(tmp)+1];
		strcpy(right[i],tmp);
	}

	//初始化为0，表示不能转化为终结符
	for(i=0;i<=25;i++)
		flag[i]=0;
	
	char* temp;
	
	//**用来表示每完成一次扫描，是否有一个新的非终结符号可以转化为
	//***非终结符，如果有则继续新的扫描，没有的话则退出整个扫描过程
	bool pd=true;
	
	while (pd)
	{
		pd=false;
	    for(i=1;i<=n;i++)
		{
            //指针指向规则右部的第一字符
			temp=right[i];
			//先判断该规则左部的非终结符是否已经可以化为终结符，可以的话扫描
			//下一条规则，不可以的话继续扫描该规则，判断是否可以转化为终结符
			if (flag[left[i]-65]==0)
			{
			    while (*temp) 
				{
				    //如果该字符是非终结符，则判断该非终结符
					//如果该字符是终结符，则判断规则的下一个字符
					if ( isupper(*temp) )
					{
					    //该字符如果不可以化为非终结符，则跳出
				        //可以的话则判断该规则的下一个字符
						if (flag[*temp-65]==0)
						    break;
					    else	
						    temp++;
					}
				    else
					    temp++;
				}
			    //如果这个时候指针指向的时候是空的时候，代表该规则左部的非终结符可以化为终结符
				//如果非空，代表该规则左部的非终结符在这一次扫描中没办法化为终结符
				if (!(*temp))
				{
				    flag[left[i]-65]=1;
				    pd=true;
				}
			}
		}
		//如果S可以化为终结符，则跳出整个扫描过程
		if (flag[18]==1)
			pd=false;
	}
	if (flag[18]==0)
		output<<"yes";
	else
		output<<"no";
    
	//释放空间
	delete  []left;
    
	for(i=1;i<=n;i++)
	{
      delete []  right[i];
	}
    delete [] right;

}