ll_1.cpp

LL_1文法分析 个人感觉不怎么好用 大家一起来看看

									bringFrist[i][1][len] = frist[t][m];
									bringFrist[i][1][len+1] = '\0';
								}
							}
							break;
						}
					}
				}
			}
		    //一部分能推出e
			else
			{
				for (j=0; j<isENum; ++j)  //遍历产生式
				{
					for (t=0; t<strlen(noEndSign); ++t)  //遍历FRIST集
					{
						if (bringFrist[i][0][j] == frist[t][0])  //是否为非终结符的FRIST集
						{
							for (m=1; m<strlen(frist[t]); ++m)  //遍历FRIST集
							{
								if (!strchr(bringFrist[i][1], frist[t][m]) && frist[t][m] != 'e')
								{
									len = strlen(bringFrist[i][1]);
									bringFrist[i][1][len] = frist[t][m];
									bringFrist[i][1][len+1] = '\0';
								}
							}
							break;
						}
					}
				}
				for (t=0; t<strlen(noEndSign); ++t)  //遍历FRIST集
				{
					if (bringFrist[i][0][isENum] == frist[t][0])  //是否为非终结符的FRIST集
					{
						for (m=1; m<strlen(frist[t]); ++m)  //遍历FRIST集
						{
							if (!strchr(bringFrist[i][1], frist[t][m]))
							{
								len = strlen(bringFrist[i][1]);
								bringFrist[i][1][len] = frist[t][m];
								bringFrist[i][1][len+1] = '\0';
							}
						}
						break;
					}
				}
			}
		} 
		else
		{
			len = strlen(noEndSign) + strlen(endSign);
			for (j=0; j<len; ++j)
			{
				if (bringFrist[i][0][0] == 'e')
				{
					bringFrist[i][1][0] = 'e';
					bringFrist[i][1][1] = '\0';
				}

				if (bringFrist[i][0][0] == frist[j][0])
				{
					for (n=1; n<strlen(frist[j]); ++n)
					{
						bringFrist[i][1][n-1] = frist[j][n];
					}
					bringFrist[i][1][n-1] = '\0';
				}
			}
		}
		
	}
	
	//显示FRIST集结果
	cout<<"Frist集:"<<"\n"<<endl;
	for (i=0; i<strlen(noEndSign); ++i)
	{
		cout<<"Frist("<<frist[i][0]<<"):  ";
		for (j=1; j<strlen(frist[i]); ++j)
		{
			cout<<frist[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}

//////////////////////////////////////////////////////////////////////////
//计算FLLOW集
void Count_Fllow()
{
	//初始数据
	fllow = new char[strlen(noEndSign)][100];
	
	for (i=0; i<strlen(noEndSign); ++i)
	{
		fllow[i][0] = noEndSign[i];
		fllow[i][1] = '\0';
	}
	
	//1、文法开始文法处理
	fllow[0][1] = '#';
	fllow[0][2] = '\0';
	
	//2、产生式处理
	do 
	{
		isUpdate = false;  //标记是否更新过FLLOW集
		isE = false;  //标记非终结符能否推出e
		
		for (i=0; i<strlen(noEndSign); ++i)  //遍历非终结符fllow[i][0]
		{
			for (j=0; j<grammarNum; ++j)  //遍历文法grmmar[j]
			{
				for (t=1; t<strlen(grammar[j]); ++t)  //遍历文法产生式grmmar[j][t]
				{
					if (fllow[i][0] == grammar[j][t])  //是否找到非终结符
					{
						//当前非终结符后一字符存在，情况处理
						if (grammar[j][t+1] != '\0')
						{
							for (n=0; n<strlen(noEndSign)+strlen(endSign); ++n)  //遍历所有符号FRIST集frist[n][0]
							{
								if (grammar[j][t+1] == frist[n][0])
								{
									for (m=1; m<strlen(frist[n]); ++m)  //遍历当前FRIST集的结果集frist[n][m]
									{
										if (!strchr(fllow[i], frist[n][m]) && frist[n][m] != 'e')
										{
											len = strlen(fllow[i]);
											fllow[i][len] = frist[n][m];
											fllow[i][len+1] = '\0';
											
											isUpdate = true;
										}
									}
								}
							}
						}
						
						//判断是否后一字符能否推出e
						for (n=0; n<strlen(noEndSign); ++n)  //遍历非终结符能否推出e情况表
						{
							if (grammar[j][t+1] == isDerivation_e[n][0] && isDerivation_e[n][1] == '1')
							{
								isE = true;
							}
						}
						
						//当前非终结符后一字符能推出e或字符为空，情况处理
						if (grammar[j][t+1] == '\0' || isE == 1)
						{
							for (n=0; n<strlen(noEndSign); ++n)  //遍历FLLOW集fllow[n][0]
							{
								if (grammar[j][0] == fllow[n][0])
								{
									for (m=1; m<strlen(fllow[n]); ++m)  //遍历FLLOW集结果集fllow[n][m]
									{
										if (!strchr(fllow[i], fllow[n][m]))
										{
											len = strlen(fllow[i]);
											fllow[i][len] = fllow[n][m];
											fllow[i][len+1] = '\0';
											
											isUpdate = true;  //已经更新
										}
									}
								}
							}
							isE = false;
						}
					}
				}
			}
		}
	} while(isUpdate);
	
	//显示FLLOW集结果
	cout<<"FLLOW集："<<"\n"<<endl;
	for (i=0; i<strlen(noEndSign); ++i)
	{
		cout<<"Fllow("<<fllow[i][0]<<"):  ";
		for (j=1; j<strlen(fllow[i]); ++j)
		{
			cout<<fllow[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}

//////////////////////////////////////////////////////////////////////////
//计算SELECT集并判断是否为LL_1文法
bool Count_Select()
{
	//初始数据
	select = new char[grammarNum][2][100];

	for (i=0; i<grammarNum; ++i)
	{
		strcpy(select[i][0], grammar[i]);
		strcpy(select[i][1], "\0");
	}

	//判断，确定SELECT集的计算公式

	//准备数据
	char (*DerivationTemp)[100];  //产生式的FRIST集
	DerivationTemp = new char[grammarNum][100];

	for (i=0; i<grammarNum; ++i)
	{
		strcpy(DerivationTemp[i], bringFrist[i][0]);
	}

	//判断文法产生式能否推出e
	isENum = 0;  //标记产生式能否推出e

	for (i=0; i<grammarNum; ++i)  //遍历DerivationTemp[i]
	{
		for (j=0; j<strlen(DerivationTemp[i]); ++j)  //遍历DerivationTemp[i][j]
		{
			if (DerivationTemp[i][j] == 'e')
			{
				++isENum;
				continue;
			}

			for (t=0; t<strlen(noEndSign); ++t)  //遍历isDerivation_e[t]
			{
				if (DerivationTemp[i][j] == isDerivation_e[t][0] && isDerivation_e[t][1] == '1')
				{
					++isENum;
					break;
				}
			}
		}

		//产生式能推出e
		if (isENum == strlen(DerivationTemp[i]))
		{
			for (j=0; j<grammarNum; ++j)  //遍历bringFrist[j][0]
			{
				if (!strcmp(DerivationTemp[i], bringFrist[j][0]))
				{
					for (t=0; t<strlen(bringFrist[j][1]); ++t)  //遍历bringFrist[j][1][t]
					{
						if (!strchr(select[i][1], bringFrist[j][1][t]) && bringFrist[j][1][t] != 'e')
						{
							len = strlen(select[i][1]);
							select[i][1][len] = bringFrist[j][1][t];
							select[i][1][len+1] = '\0';
						}
					}
				}
			}
			for (j=0; j<strlen(noEndSign); ++j)  //遍历fllow[j][0]
			{
				if (grammar[i][0] == fllow[j][0])
				{
					for (t=1; t<strlen(fllow[j]); ++t)  //遍历fllow[j][t]
					{
						if (!strchr(select[i][1], fllow[j][t]))
						{
							len = strlen(select[i][1]);
							select[i][1][len] = fllow[j][t];
							select[i][1][len+1] = '\0';
						}
					}
				}
			}
		}
		//产生式不能推出e
		else
		{
			for (j=0; j<grammarNum; ++j)  //遍历bringFrist[j][0]
			{
				if (!strcmp(DerivationTemp[i], bringFrist[j][0]))
				{
					for (t=0; t<strlen(bringFrist[j][1]); ++t)  //遍历bringFrist[j][1][t]
					{
						if (!strchr(select[i][1], bringFrist[j][1][t]))
						{
							len = strlen(select[i][1]);
							select[i][1][len] = bringFrist[j][1][t];
							select[i][1][len+1] = '\0';
						}
					}
				}
			}
		}
		isENum = 0;
	}

	//显示SELECT集结果
	cout<<"SELECT集："<<"\n"<<endl;
	for (i=0; i<grammarNum; ++i)
	{
		cout<<"SELECT(";
		for (j=0; j<strlen(select[i][0]); ++j)
		{
			if (j == 1)
			{
				cout<<"->";
			}
			cout<<select[i][0][j];
		}
		cout<<"):  ";
		
		for (j=0; j<strlen(select[i][1]); ++j)
		{
			cout<<select[i][1][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
	
	//判断是否为LL（1）文法
	isSame = false;  //标记是否有相同SELECT结果集
	len = 0;

	for (i=0; i<grammarNum; ++i)  //遍历所有文法select[i][0][0]
	{
		strcpy(strTemp, select[i][1]);  //保存第一条文法的SELECT集

		for (j=i+1; j<grammarNum; ++j)  //向下遍历相同非终结符的文法select[j][0][0]
		{
			if (select[i][0][0] == select[j][0][0])
			{
				for (t=0; t<strlen(select[j][1]); ++t)  //遍历相同非终结符的文法select结果集select[j][1][t]
				{
					if (!strchr(strTemp, select[j][1][t]))
					{
						len = strlen(strTemp);
						strTemp[len] = select[j][1][t];
						strTemp[len+1] = '\0';
					}
					else
					{
						isSame = true;
						break;
					}
				}
			}
			if (isSame == 1)
			{
				break;
			}
		}
		if (isSame == 1)
		{
			break;
		}
	}

	if (isSame == 1)
	{
		return false;
	}
	else
	{
		return true;
	}
}

//////////////////////////////////////////////////////////////////////////
//显示LL(1)分析表
void Show_LL_1_Table()
{
	cout<<"LL(1)分析表："<<endl;
	cout<<"------------------------------------------------------------------"<<endl;
	
	//终结符加入'#'
	len = strlen(endSign);
	endSign[len] = '#';
	endSign[len+1] = '\0';
	
	//输出表头
	printf("%-10s", " ");
	for (i=0; i<strlen(endSign); ++i)
	{
		printf("%-10c", endSign[i]);
	}
	cout<<endl;
	
	//输出各行
	bool isHave = false;  //是否存相应产生式
	
	for (i=0; i<strlen(noEndSign); ++i)  //遍历noEndSign[i]
	{
		printf("%-10c", noEndSign[i]);
		for (j=0; j<strlen(endSign); ++j)  //遍历endSign[j]
		{
			for (t=0; t<grammarNum; ++t)  //遍历select[t][0]
			{
				if (select[t][0][0] == noEndSign[i] && strchr(select[t][1], endSign[j]))
				{
					strcpy(strTemp, bringFrist[t][0]);
					isHave = true;
					break;
				}
			}
			if (isHave == true)
			{
				isHave = false;
				printf("->%-8s", strTemp);
			}
			else
			{
				printf("%-10s", " ");
			}
		}
		cout<<endl;
	}
	
	cout<<"------------------------------------------------------------------"<<"\n"<<endl;
}

//////////////////////////////////////////////////////////////////////////
//分析字符串
void construeStr()
{
	//初始数据

	//初始要分析的字符串 strTemp[100]

	cout<<"请输入要分析的字符串（不用#字符结尾）：";
	cin>>strTemp;
	len = strlen(strTemp);
	strTemp[len] = '#';
	strTemp[len+1] = '\0';
	cout<<endl;

	//初始分析栈  construeArray[100]
	construeArray[0] = '#';
	construeArray[1] = grammar[0][0];
	construeArray[2] = '\0';

	//初始推导所用的产生式或匹配字符串 bringStr[100]
	strcpy(bringStr, "\0");

	//输出符号串分析过程

	//输出表头
	cout<<"对符号串"<<strTemp<<"的分析过程："<<endl;
	cout<<"------------------------------------------------------------------"<<endl;
	printf("%-10s", "步骤");
	printf("%-18s", "分析栈");
	printf("%-18s", "剩余输入串");
	printf("%-18s", "推导所用产生式或匹配");
	cout<<"\n"<<"------------------------------------------------------------------"<<endl;

	//输出分析过程
	n = 0;  //初始步骤数

	do 
	{
		++n;
		itoa(n, stepNum, 10);  //更新步骤数

		//输出步骤，分析栈，剩余输入串
		printf("%-10s", stepNum);
		printf("%-18s", construeArray);
		printf("%-18s", strTemp);

		//获取栈顶及剩余输入串头字符
		construeTop = construeArray[strlen(construeArray)-1];
		for (i=0; i<strlen(strTemp); ++i)
		{
			if (strTemp[i] != 32)
			{
				strTempTop = strTemp[i];
				break;
			}
		}

		//计算推导所用产生式或匹配

		//若字符匹配，但已完成分析
		if (construeTop == strTempTop && strTempTop == '#')
		{
			strcpy(bringStr, "接受");
			
			*strchr(strTemp, strTempTop) = 32;
			
			cout<<bringStr<<endl;
			break;
		}

		//若字符匹配，但未完成分析
		if (construeTop == strTempTop && strTempTop != '#' && !strchr(noEndSign, strTempTop))
		{
			bringStr[0] = '\'';
			bringStr[1] = strTempTop;
			bringStr[2] = '\0';
			strncat(bringStr, "\'匹配", 10);

			construeArray[strlen(construeArray)-1] = '\0';
			*strchr(strTemp, strTempTop) = 32;

			cout<<bringStr<<endl;
			continue;
		}

		//判断[construeTop, strTempTop]是否为产生式

		//搜索相应产生式
		for (i=0; i<grammarNum; ++i)  //遍历select[i]
		{
			if (construeTop == select[i][0][0] && strchr(select[i][1], strTempTop))  //是产生式
			{
				strcpy(bringStr, select[i][0]);
				
				for (j=strlen(bringStr)-1; j>0; --j)  //遍历bringStr[j]
				{
					if (j == strlen(bringStr)-1)
					{
						if (bringStr[j] == 'e')
						{
							len = strlen(construeArray);
							construeArray[len-1] = '\0';
						}
						else
						{
							len = strlen(construeArray);
							construeArray[len-1] =  bringStr[j];
							construeArray[len] = '\0';
						}				
					}
					else
					{
						len = strlen(construeArray);
						construeArray[len] =  bringStr[j];
						construeArray[len+1] = '\0';
					}
				}
				break;
			}
		}
		//若不是产生式,退出
		if (i == grammarNum)
		{
			strcpy(bringStr, "出错终止");
			cout<<bringStr<<endl;
			break;
		}
		//是产生式
		else
		{
			//输出所用的产生式或匹配
			for (i=0; i<strlen(bringStr); ++i)
			{
				if (i == 1)
				{
					cout<<"->";
					cout<<bringStr[i];
				}
				else
				{
					cout<<bringStr[i];
				}
			}
			cout<<endl;
		}

	} while(strTemp[strlen(strTemp)-1] != 32);
	cout<<"------------------------------------------------------------------"<<endl;
}

//////////////////////////////////////////////////////////////////////////
//主函数{

int main()
{
	do 
	{
		cTemp = '\0';  //标记是否继续使用

		//输入文法
		InputGrammar();
		
		//获取，显示终结符和非终结符
		Count_noEndSign_endSign();
		
		//求出能推出e的非终结符
		Count_isDerivation_e();
		
		//计算FRIST集
		Count_Frist();
		
		//计算FLLOW集
		Count_Fllow();
		
		//计算SELECT集
		if (Count_Select())
		{
			cout<<"该文法是LL(1)文法！"<<endl;
		}
		else
		{
			cout<<"该文法不是LL(1)文法！"<<endl;
			cout<<"\n"<<"是否继续使用? (Y/N)　";
			cTemp = getch();
			cout<<"\n"<<endl;
			continue;
		}
		cout<<endl;
		
		//显示LL(1)分析表
		Show_LL_1_Table();
		
		//分析字符串
		construeStr();
		
		//是否继续使用
		cout<<"\n"<<"是否继续使用? (Y/N)　";
		cTemp = getch();
		cout<<"\n"<<endl;

	} while(cTemp == 'y' || cTemp == 'Y');
	
	cout<<"谢谢使用，有意见请与我联系! ([e-mail])"<<"\n"<<endl;
	system("PAUSE");  //程序暂停
	return 0;
}