ll_1.cpp

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

// ***************************************************************
//  LL_1.CPP  version:  1.0   谢伟纯 05软件工程 date: 05/22/2008
//  -------------------------------------------------------------
//  程序名：LL(1) 语法分析程序 
//  -------------------------------------------------------------
//  Copyright (C) 2008 - All Rights Reserved
// ***************************************************************
// 说明：本程序可对用户输入的合法（无多余规则，无递归产生式）文法，
// 进行是否为LL(1)文法判断，并生成相应的文法预测分析表。在分析表产
// 生后，用户可输入要分析的字符串，进行分析。
// ***************************************************************

#include <iostream>
#include <string>
#include <conio.h> 
#include <stdio.h>
using namespace std;

//////////////////////////////////////////////////////////////////////////
//全局变量字典{

int i = 0, j = 0, t = 0, n = 0, m = 0, x = 0, y = 0;  //下标或临时变量
int len = 0;  //字符串长度
int isENum = 0;  //能推出e的终结符数量
bool isE = false; //标记是否能推出e
bool isUpdate = false;  //标记是否更新过结果集
bool isSame = false;  //标记是否有相同SELECT结果集
char strTemp[100] = "\0";  //临时字符串 或　要分析的字符串
char cTemp = '\0';  //临时字符

int grammarNum = 0;  //文法数量
char (*grammar)[32];  //文法  grammar[grammarNum][32]
char noEndSign[30];  //非终结符
char endSign[100];  //终结符
char (*grammarTemp)[32];  //临时文法  grammarTemp[grammarNum][32]
char (*isDerivation_e)[2];  //标记非终结符是否推出e数组  isDerivation_e[strlen(noEndSign)][2]
char (*frist)[100];  //每个文法符号的FRIST集  frist[strlen(noEndSign) + strlen(endSign)][100]
char (*bringFrist)[2][100];  //产生式的FRIST集  bringFrist[grammarNum][2][100]
char (*fllow)[100];  //非终结符的FLLOW集  fllow[strlen(noEndSign)][100]
char (*select)[2][100];  //select集  select[grammarNum][2][100]

char construeArray[100];  //分析栈
char bringStr[100];  //推导所用的产生式或匹配字符串
char stepNum[10];  //步聚数
char construeTop = '\0';  //栈顶字符
char strTempTop = '\0';  //剩余输入串头字符

//全局变量字典}
//////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////
//输入文法
void InputGrammar()
{
	//初始数据
	do 
	{
		n = 0;  //标记成功赋值的变量数
		fflush(stdin);  //清空输入缓存区
		cout<<"请输入文法数量（1<=n<=20）：";
		n = scanf("%d", &grammarNum);
	} while(!n || grammarNum < 1 || grammarNum > 20);
	
 	grammar = new char[grammarNum][32];

	//输入文法字符串
	cout<<"\n"<<"文法输入规则如下：\n\na、大写英文字母表示非终结符。\
		\nb、e表示空产生式。 \
		\nc、除大写字母、#、'、| 外的单字符表示终结符。\
		\nd、不能出现递归文法。（如 S->S或S->A, A->S;）\
		\ne、不能出现多余文法规则。（如 S->A，A不是非终结符；程序不检测）\
		\nf、文法产生式长度不超过10个字符。（程序不检测）"<<"\n"<<endl;
	
	for (i = 0; i < grammarNum; ++i)
	{
		cout<<i+1<<"　";
		
		//输入文法左部
		strTemp[0] = getch();
		if ( strTemp[0] >= 'A' && strTemp[0] <= 'Z')
		{
			grammar[i][0] = strTemp[0];
			cout<<grammar[i][0]<<"->";
		}
		else
		{
			cout<<"请输入非终结符！"<<endl;
			--i;
			continue;
		}
		
		//输入文法右部
		cin>>strTemp;
		for (j = 0; j < strlen(strTemp); ++j)
		{
			grammar[i][j+1] = strTemp[j];
		}
		grammar[i][++j] = '\0';
		
		//检测文法合法性
		len = strlen(grammar[i]);
		for (j = 1; j < len; ++j)
		{
			//是否为空串
			if (j == 1 && grammar[i][j] == 'e' && grammar[i][j+1] == '\0')
			{
				continue;
			}
			
			if(grammar[i][j] == '#' || grammar[i][j] == '|' || grammar[i][j] == 'e' || grammar[i][j] == '\'')
			{
				cout<<"产生式含有非法字符，请重新输入："<<endl;
				--i;
				break;
			}
		}
		
		//检测递归产生式
		for(j=1; j<len; ++j)
		{
			if (grammar[i][0] != grammar[i][j])
			{
				break;
			}
		}
		if (j == len)
		{
			cout<<"文法存在递归产生式，请重新输入："<<endl;
			--i;
		}
	}
	cout<<'\n'<<endl;
	
	//显示文法
	cout<<"你输入的文法是："<<'\n'<<endl;
	for (i = 0; i < grammarNum; ++i)
	{
		cout<<i+1<<" "<<grammar[i][0]<<"->";
		for (j = 1; j < strlen(grammar[i]); ++j)
		{
			cout<<grammar[i][j];
		}
		cout<<endl;
	}
	cout<<endl;
}

//////////////////////////////////////////////////////////////////////////
//获取，显示终结符和非终结符
void Count_noEndSign_endSign()
{
	//初始数据
	strcpy(noEndSign, "\0");
	strcpy(endSign, "\0");
	
	for (i = 0; i < grammarNum ; ++i)
	{
		//非终结符判断
		if (!strchr(noEndSign, grammar[i][0]))
		{
			len = strlen(noEndSign);
			noEndSign[len] = grammar[i][0];
			noEndSign[len+1] = '\0';
		}
		
		//终结符判断
		for (j = 1, m = 0; j < strlen(grammar[i]); ++j)
		{
			if (!strchr(endSign, grammar[i][j]) && (grammar[i][j] < 'A' || grammar[i][j] > 'Z') && grammar[i][j] != 'e')
			{
				len = strlen(endSign);
				endSign[len] = grammar[i][j];
				endSign[len+1] = '\0';
			}
		}
	}
	
	//显示终结符和非终结符
	n = 0;
	cout<<"非终结符是：";
	while (noEndSign[n] != '\0')
	{
		cout<<noEndSign[n++]<<" ";
	}
	cout<<endl;
	n = 0;
	cout<<"终结符是：";
	while (endSign[n] != '\0')
	{
		cout<<endSign[n++]<<" ";
	}
	cout<<'\n'<<endl;
}

//////////////////////////////////////////////////////////////////////////
//求出能推出e的非终结符
void Count_isDerivation_e()
{
	//初始数据
	grammarTemp = new char[grammarNum][32];
	for (i = 0; i < grammarNum; ++i)
	{
	   strcpy(grammarTemp[i], grammar[i]);
	}

	isDerivation_e = new char[strlen(noEndSign)][2];

	//1、初始标记数组，全部设为'2'（'0'表示不能推出e，'1'表示能推出e，'2'表示未定）
	for (i = 0; i < len; ++i)
	{
		isDerivation_e[i][0] = noEndSign[i];
		isDerivation_e[i][1] = '2';
	}
	
	//2、扫描文法中的产生式
	for (i = 0; i < grammarNum; ++i)
	{
		//是否推出e的非终结符
		if (grammarTemp[i][1] == 'e')
		{
			for (j = 0; j < strlen(noEndSign); ++j)
			{
				if (isDerivation_e[j][0] == grammarTemp[i][0])
				{
					isDerivation_e[j][1] = '1';
				}
			}
			continue;
		}

		//是否含有终结符
		len = strlen(grammarTemp[i]);
		for (j = 1; j < len; ++j)
		{
			if (strchr(endSign, grammarTemp[i][j]))
			{
				grammarTemp[i][0] = '\0';
				break;
			}
		}
	}

	//标记不能推出e的非终结符
	for (i=0; i<strlen(noEndSign); ++i)
	{
		for (j=0; j<grammarNum; ++j)
		{
			if (isDerivation_e[i][0] == grammarTemp[j][0])
			{
				break;
			}
		}
		if (j == grammarNum)
		{
			isDerivation_e[i][1] = '0';
		}
	}

	//3、扫描产生式右部的每一符号
	//是
	do 
	{
		isUpdate = false;  //标记此次操作是否有更新过数据

		for (i=0; i<grammarNum; ++i)
		{
			for (j=1; j<strlen(grammarTemp[i]); ++j)
			{
				if (strchr(noEndSign, grammarTemp[i][j]))
				{
					for (t=0; t<strlen(noEndSign); ++t)
					{
						if (isDerivation_e[t][0] == grammarTemp[i][j] && isDerivation_e[t][1] == '1')
						{
							grammarTemp[i][j] = 32;
						}
					}
				}
			}
		}
		for (i=0; i<strlen(noEndSign); ++i)
		{
			for (j=0; j<grammarNum; ++j)
			{
				if (isDerivation_e[i][0] == grammarTemp[j][0])
				{
					for (t=1; t<strlen(grammarTemp[j]); ++t)
					{
						if (grammarTemp[j][t] != 32)
						{
							break;
						}
					}
					if (t == strlen(grammarTemp[j]))
					{
						isDerivation_e[i][1] = '1';
						isUpdate = true;
						//删除该非终结符在左部的所有产生式
						for (n=0; n<grammarNum; ++n)
						{
							if (grammarTemp[j][0] == grammarTemp[n][0] && j!= n)
							{
								grammarTemp[n][0] = '\0';
							}
						}
						grammarTemp[j][0] = '\0';
					}
				}
			}
		}
		
		//否
		for (i=0; i<grammarNum; ++i)
		{
			for (j=1; j<strlen(grammarTemp[i]); ++j)
			{
				if (strchr(noEndSign, grammarTemp[i][j]))
				{
					for (t=0; t<strlen(noEndSign); ++t)
					{
						if (isDerivation_e[t][0] == grammarTemp[i][j] && isDerivation_e[t][1] == '0')
						{
							grammarTemp[i][0] = '\0';
						}
					}
				}
			}
		}
		for (i=0; i<strlen(noEndSign); ++i)
		{
			if (isDerivation_e[i][1] != '2')
			{
				continue;
			}
			for (j=0; j<grammarNum; ++j)
			{
				if (isDerivation_e[i][0] ==grammarTemp[j][0])
				{
					break;
				}
			}
			if (j == grammarNum)
			{
				isDerivation_e[i][1] = '0';
				isUpdate = true;
			}
		}
		
	} while(isUpdate);

	//显示结果
	cout<<"非终结符能否推导出e的表"<<endl;
	cout<<"------------------------------------------------------------------"<<endl;
	for (i=0; i<strlen(noEndSign); ++i)
	{
		cout<<"  "<<isDerivation_e[i][0]<<" ";
	}
	cout<<"\n"<<endl;
	for (i=0; i<strlen(noEndSign); ++i)
	{
		switch(isDerivation_e[i][1])
		{
		case '0':
			cout<<" 否 ";
			break;
		case '1':
			cout<<" 是 ";
			break;
		default:
		    break;
		}
	}
	cout<<"\n"<<"------------------------------------------------------------------"<<endl;
	cout<<endl;
}

//////////////////////////////////////////////////////////////////////////
//计算FRIST集
void Count_Frist()
{
	//初始数据
	len = strlen(noEndSign) + strlen(endSign);
	frist = new char[len][100];  

	n = 0;
	for (i=0; i<strlen(noEndSign); ++i)
	{
		frist[n][0] = noEndSign[i];
		frist[n++][1] = '\0';
	}
	for (i=0; i<strlen(endSign); ++i)
	{
		frist[n][0] = endSign[i];
		frist[n++][1] = '\0';
	}

	//计算每个符号的FRIST集
	
	//1、属于终结符情况
	for (i=0; i<len; ++i)
	{
		if (strchr(endSign, frist[i][0]))
		{
			frist[i][1] = frist[i][0];
			frist[i][2] = '\0';
		}
	}

	//2、属于非终结符，产生式首字符为终结符
	for (i=0; i<strlen(noEndSign); ++i)  //遍历非终结符的FRIST集frist[i][0]
	{
		for (j=0; j<grammarNum; ++j)  //遍历文法grammar[j][0]
		{
			if (frist[i][0] == grammar[j][0] && strchr(endSign, grammar[j][1]))
			{
				len = strlen(frist[i]);
				frist[i][len] = grammar[j][1];
				frist[i][len+1] = '\0';
			} 
		}
	}

	//3、能推出e的非终结符
	for (i=0; i<strlen(noEndSign); ++i)  //遍历非终结符的FRIST集frist[i][0]
	{
		for (j=0; j<strlen(noEndSign); ++j)  //遍历能否推出e情况表
		{
			if (frist[i][0] == isDerivation_e[j][0] && isDerivation_e[j][1] == '1' && !strchr(frist[i], 'e'))
			{
				len = strlen(frist[i]);
				frist[i][len] = 'e';
				frist[i][len+1] = '\0';
				break;
			}
		}
	}
	
	//4、5、产生中的非终结符能推出e的情况处理
	do 
	{
		isE = true;
		isENum = 0;
		isUpdate = false;
	
		for (i=0; i<strlen(noEndSign); ++i)  //遍历frist[i]
		{
			for (j=0; j<grammarNum; ++j)  //遍历grammar[j]
			{
				if (frist[i][0] == grammar[j][0])
				{
					for (t=1; t<strlen(grammar[j]); ++t)  //遍历grammar[j][t]
					{
						//是否为非终结符
						if (strchr(endSign, grammar[j][t]))
						{
							break;
						}
	
						//判断是否能推出e
						for (n=0; n<strlen(noEndSign); ++n)  //遍历isDerivation_e[n]
						{
							if (grammar[j][t] == isDerivation_e[n][0])
							{
								if (isDerivation_e[n][1] == '1')
								{
									++isENum;
									break;
								}
								else
								{
									isE = false;
									break;
								}
							}
						}
	
						if (isE == 0)
						{
							isE = true;
							break;
						}
					}  
	
					//判断产生式中字符的推出e数量，并处理
					len = strlen(grammar[j]);
	
					//前部分能推出e
					if (isENum != len -1)
					{
						for (t=1; t<=isENum+1; ++t)  //遍历grammar[j][t]
						{
							for (n=0; n<strlen(noEndSign); ++n)  //遍历frist[n]
							{
								if (grammar[j][t] == frist[n][0])
								{
									for (m=1; m<strlen(frist[n]); ++m)  //遍历frist[n][m]
									{
										if (t != isENum+1)
										{
											if (!strchr(frist[i], frist[n][m]) && frist[n][m] != 'e')
											{
												x = strlen(frist[i]);
												frist[i][x] = frist[n][m];
												frist[i][x+1] = '\0';
	
												isUpdate = true;
											}
										}
										else
										{
											if (!strchr(frist[i], frist[n][m]))
											{
												x = strlen(frist[i]);
												frist[i][x] = frist[n][m];
												frist[i][x+1] = '\0';
	
												isUpdate = true;
											}
										}							
									}
								}
							}
						}
					}
	
					//全部都能推出e
					if (isENum == len - 1)
					{
						for (t=1; t<=isENum+1; ++t)  //遍历grammar[j][t]
						{
							for (n=0; n<strlen(noEndSign); ++n)  //遍历frist[n]
							{
								if (grammar[j][t] == frist[n][0])
								{
									for (m=1; m<strlen(frist[n]); ++m)  //遍历frist[n][m]
									{
										if (!strchr(frist[i], frist[n][m]))
										{
											x = strlen(frist[i]);
											frist[i][x] = frist[n][m];
											frist[i][x+1] = '\0';
	
											isUpdate = true;
										}
									}
								}
							}
						}
	
						//并e
						if (!strchr(frist[i], 'e'))
						{
							x = strlen(frist[i]);
							frist[i][x] = frist[n][m];
							frist[i][x+1] = '\0';
							
							isUpdate = true;
						}
					}
				}
	
				isENum = 0;
				}
		}
	} while(isUpdate);
		
	//求字符串FRIST集

	//初始数组
	bringFrist = new char[grammarNum][2][100];
	
	for (i=0; i<grammarNum; ++i)
	{
		bringFrist[i][0][0] = '\0';
		for (j=1; j<strlen(grammar[i]); ++j)
		{
			len = strlen(bringFrist[i][0]);
			bringFrist[i][0][len] = grammar[i][j];
			bringFrist[i][0][len+1] = '\0';
		}
	}

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

	//产生式首字符能否推出e情况处理
	for (i=0; i<grammarNum; ++i)
	{
		isENum = 0;
		len = strlen(noEndSign);
		for (j=0; j<len; ++j)
		{
			if (bringFrist[i][0][0] == isDerivation_e[j][0] && isDerivation_e[j][1] == '1')
			{
				isENum = 1;
				break;
			}
		}
		if (1 == isENum)
		{
			for (j=1; j<strlen(bringFrist[i][0]); ++j)  //遍历产生式字符
			{
				for (t=0; t<strlen(noEndSign); ++t)  //判断是否能推出e
				{
					if (bringFrist[i][0][j] == isDerivation_e[t][0] && isDerivation_e[t][1] == '1')
					{
						++isENum;
					}
				}
				if (t == strlen(noEndSign))
				{
					break;
				}
			}

			//产生式全部字符能推出e
			if (isENum == strlen(bringFrist[i][0]))
			{
				for (j=0; j<strlen(bringFrist[i][0]); ++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]))
								{
									len = strlen(bringFrist[i][1]);