frmmain.cs

这是一个完整的文法分析器

		#region 完成FIRST集计算,把未求出FIRST集的非终结符求出

		public ArrayList FinishFirst(ArrayList[] FirstList,Queue queueFirst)
		{
			//初始化标记数组
			bool [] FirstFinished=new bool[FirstList.Length];
			for(int i=0 ; i<FirstFinished.Length ; i++)
			{
				FirstFinished[i]=true;
			}
			//将队列中元素依次取出,将出现的元素标记为false,意为这个FIRST集未求出
			for(int i=0 ; i<queueFirst.Count ; i++)
			{
				string strQueue=queueFirst.Dequeue().ToString();
				int iLeftIndex=getLeftIndex(strQueue.Substring(0,1));
				FirstFinished[iLeftIndex]=false;
				queueFirst.Enqueue(strQueue);
			}
			//防止死循环,最高循环100次强行退出
			int iOutException=0;
			while(queueFirst.Count>0 && iOutException!=100)
			{
				iOutException++;
				//首先取出队列中的一个元素
				string strQueue=queueFirst.Dequeue().ToString();
				//获取队列元素相关信息
				int iPos1=getLeftIndex(strQueue.Substring(0,1));
				int iPos2=getLeftIndex(strQueue.Substring(1,1));
				//假如右部的FIRST集已经求出,那么就把右部的FIRST集加入到左部FIRST
				if(FirstFinished[iPos2])
				{
					ArrayList nextArray=FirstList[iPos2];
					if(strQueue.Length==3)
					{
						FirstList[iPos2].Remove("$");
					}
					FirstList[iPos1]=Tools.AddArrayList(FirstList[iPos1],FirstList[iPos2]);
					if(strQueue.Length==3 && this.CheckEmptySymbol(strQueue.Substring(1,1)))
					{
						FirstList[iPos2].Add("$");
					}
					//假如该元素不再在队列中元素左部出现,那么标记该元素FIRST集已经求出
					if(Tools.IsQueueElement(strQueue,0,1,queueFirst)==false)
						FirstFinished[iPos1]=true;
				}
				else
				{
					queueFirst.Enqueue(strQueue);
				}
			}
			ArrayList aryFirst=new ArrayList();
			foreach (ArrayList arylst in FirstList)
			{
				aryFirst.Add(arylst);

			}
			return aryFirst;
		}

		#endregion
	
		#region 得到FOLLOW集
		/// <summary>
		/// 得到FOLLOW集
		/// </summary>
		/// <param name="aryFirst">需要把FIRST集传入</param>
		/// <returns>ArrayList</returns>
		public ArrayList FollowSet(ArrayList aryFirst)
		{	
			if(LeftItem.Count==0) return null;

			ArrayList [] lstFollow = new ArrayList[LeftItem.Count];
			ArrayList [] lstFirst = Tools.ConvertToArray(aryFirst);
			ArrayList lstItems = new ArrayList();
			Stack [] RemoveList=new Stack[LeftItem.Count];
			Queue queueFollow=new Queue();
			string strStartLetter=this.listboxProducts.Items[0].ToString().Substring(0,1);
			
			bool [] iFollowFinished=new bool[LeftItem.Count];
			for(int i=0 ; i<LeftItem.Count ; i++ )
			{
				//初始化标记位
				iFollowFinished[i]=true;
				//初始化Follow集
				lstFollow[i]=new ArrayList();
				RemoveList[i]=new Stack();
			}
			//FOLLOW集的求法(规定第一个产生式的第一个字符式开始符)
			//1.如果 X 是开始符 那么把 # 加入到 FOLLOW(X)
			lstFollow[0].Add("#");

			//第一次进行扫描,把符合条件的符号和FIRST集,FOLLOW集全部加入
			for(int i=0 ; i<LeftItem.Count ; i++ )
			{
				Product product=(Product)LeftItem[i];
				lstFollow[i]=FollowLetter(product.LeftItem,lstFollow[i]);
				//扫描同时把能够替换FIRST集,FOLLOW集的先替换
				int FollowCount=lstFollow[i].Count;
				for(int j=0; j<FollowCount; j++)
				{
					string strNextFollow=lstFollow[i][j].ToString();
					

					if(strNextFollow.Length!=1)
					{
						//如果是FIRST集或FOLLOW集串先把串移除
						RemoveList[i].Push(strNextFollow);

						if(strNextFollow.IndexOf("FIRST")>=0)
						{
							int indexLeft=this.getLeftIndex(strNextFollow.Substring(6,1));
							lstFollow[i]=Tools.AddArrayList(lstFollow[i],lstFirst[indexLeft]);
						}
						else
						{
							string strNextLetter=strNextFollow.Substring(7,1);
							queueFollow.Enqueue(product.LeftItem + strNextLetter);
							Console.WriteLine("Queue\t" + product.LeftItem + strNextLetter);
						}//end first follow
						
					}//end if strNextFollow.Length!=1
				}//end for j
				while(RemoveList[i].Count>0)
				{
					string strRemove=(String)RemoveList[i].Pop();
					lstFollow[i].Remove(strRemove);
				}


			}//end for i

			//将队列中元素依次取出,将出现的元素标记为false,意为这个FOLLOW集未求出
			for(int i=0 ; i<queueFollow.Count ; i++)
			{
				string strQueue=queueFollow.Dequeue().ToString();
				int iLeftIndex=getLeftIndex(strQueue.Substring(0,1));
				iFollowFinished[iLeftIndex]=false;
				queueFollow.Enqueue(strQueue);
			}
			//检测队列
			//防止死循环,最高循环100次强行退出
			int iOutException=0;
			while(queueFollow.Count>0 && iOutException!=100)
			{
				iOutException++;
				//首先取出队列中的一个元素
				string strQueue=queueFollow.Dequeue().ToString();
				//获取队列元素相关信息
				int iPos1=getLeftIndex(strQueue.Substring(0,1));
				int iPos2=getLeftIndex(strQueue.Substring(1,1));
				//如果后续元素FOLLOW集已经求出那么就把它加入到前面元素的FOLLOW集
				if(iFollowFinished[iPos2])
				{
					lstFollow[iPos1]=Tools.AddArrayList(lstFollow[iPos1],lstFollow[iPos2]);
					//假如该元素不再在队列中元素左部出现,那么标记该元素FIRST集已经求出
					if(Tools.IsQueueElement(strQueue,0,1,queueFollow)==false)
						iFollowFinished[iPos1]=true;
				}
				else
				{
					queueFollow.Enqueue(strQueue);
				}
			}
			if(iOutException==100){
				//假如进入了死循环,强行把第一个FOLLOW集设置为已经求出,然后依次再计算一次
				iFollowFinished[0]=true;
				iOutException=0;
				while(queueFollow.Count>0 && iOutException!=100)
				{
					iOutException++;
					//首先取出队列中的一个元素
					string strQueue=queueFollow.Dequeue().ToString();
					//获取队列元素相关信息
					int iPos1=getLeftIndex(strQueue.Substring(0,1));
					int iPos2=getLeftIndex(strQueue.Substring(1,1));
					//如果后续元素FOLLOW集已经求出那么就把它加入到前面元素的FOLLOW集
					if(iFollowFinished[iPos2])
					{
						lstFollow[iPos1]=Tools.AddArrayList(lstFollow[iPos1],lstFollow[iPos2]);
						//假如该元素不再在队列中元素左部出现,那么标记该元素FIRST集已经求出
						if(Tools.IsQueueElement(strQueue,0,1,queueFollow)==false)
							iFollowFinished[iPos1]=true;
					}
					else
					{
						queueFollow.Enqueue(strQueue);
					}
				}
			}

			//把FOLLOW集拼装好并返回
			for(int i=0 ; i<LeftItem.Count ; i++)
			{
				//FOLLOW集中没有空串,移除所有空串
				while(Tools.IsInList("$",lstFollow[i]))
					lstFollow[i].Remove("$");
				lstItems.Add(lstFollow[i]);
			}
			return lstItems;
		}

		#endregion

		#region 辅助求FOLLOW集,返回所有产生式右部指定的字符后边的字母

		private ArrayList FollowLetter(string strChar,ArrayList arylstFollow)
		{
			for(int i=0 ; i<listboxProducts.Items.Count ; i++ )
			{
				string strRightItem=listboxProducts.Items[i].ToString().Substring(2);
				int iPos=strRightItem.IndexOf(strChar);
				string strFollow="FOLLOW(" + listboxProducts.Items[i].ToString().Substring(0,1) + ")";

				if(iPos>=0 )
				{
					//假如所求字符的下一个字符并不存在
					if(strRightItem.Length-1==iPos)
					{
						if(!Tools.IsInList(strFollow,arylstFollow))
							arylstFollow.Add(strFollow);
					}
						
					else
					{
						string strNextChar=strRightItem.Substring(iPos+1,1);
						//所求字符X的下一个字符如果是终结符,直接加入FOLLOW(X)集
						if(SymbolSet.getInstance().IsInEndSet(strNextChar))
						{
							if(!Tools.IsInList(strNextChar,arylstFollow))
								arylstFollow.Add(strNextChar);
						}
						else
						{
							//否则把下一个字符的FIRST集加入FOLLOW(X)集
							if(!Tools.IsInList("FIRST(" + strNextChar + ")",arylstFollow))
								arylstFollow.Add("FIRST(" + strNextChar + ")");						
						}

						//所求字符X的下一个字符如果能够星推导出空,就把产生式左部字符的FOLLOW集直接加入FOLLOW(X)集
						if(CheckEmptySymbol(strNextChar) )
						{
							if(!Tools.IsInList(strFollow,arylstFollow))
								arylstFollow.Add(strFollow);
						}					
					}
				}
			}
			return arylstFollow;
		}
		
		#endregion

		#region 得到SELECT集

		public ArrayList SelectSet(ArrayList aryFirst,ArrayList aryFollow)
		{
			ArrayList [] lstSellect = new ArrayList[listboxProducts.Items.Count];
			ArrayList lstItems = new ArrayList();
			bool []bNeedFollow = new bool[listboxProducts.Items.Count];
			for(int i=0 ; i<this.listboxProducts.Items.Count ; i++ )
			{
				string strFirstLetter=listboxProducts.Items[i].ToString().Substring(2,1);
				string strLeft=listboxProducts.Items[i].ToString().Substring(0,1);

				lstSellect[i]=new ArrayList();
				
				bNeedFollow[i]=false;
				//SELECT集算法三步:
				if(SymbolSet.getInstance().IsInEndSet(strFirstLetter))
				{
					//1.假如 X->a , a 属于终结符集,那么select(X->a)={a}
					lstSellect[i].Add(strFirstLetter);
				}
				else if(strFirstLetter=="$")
				{	//2.假如 X->$ 那么select(X->$)=FOLLOW(X)
					lstSellect[i]=Tools.AddArrayList(lstSellect[i],(ArrayList)aryFollow[getLeftIndex(strLeft)]);
				}
				else 
				{
					//3.如果 X->A 如果A是非终结符且A能星推导出$
					//那么 select(X->A)=FIRST(A)-{$} U FOLLOW(X)
					//否则 select(X->A)=FIRST(A)
					string strRight=listboxProducts.Items[i].ToString().Substring(2);
					//if(Tools.IsAllNotEnd(strRight))
					//{
						bool bNext=true;
						for(int j=0 ; j<strRight.Length ; j++)
						{	
							string strChar=strRight.Substring(j,1);
							if(CheckEmptySymbol(strChar) && bNext)
							{
								//Console.WriteLine(strChar + "asdfasdfsad");
								ArrayList firstlist=(ArrayList)aryFirst[getLeftIndex(strChar)];
								firstlist.Remove("$");
								lstSellect[i]=Tools.AddArrayList(lstSellect[i],firstlist);
								if(j==strRight.Length-1)bNeedFollow[i]=true;
							}
							else
							{
								if(bNext && SymbolSet.getInstance().IsInNotEndSet(strChar))
								{
									//Console.WriteLine(strChar + "asdfasdfsad");
									bNext=false;
							
									ArrayList firstlist=(ArrayList)aryFirst[getLeftIndex(strChar)];
									if(firstlist!=null)lstSellect[i]=Tools.AddArrayList(lstSellect[i],firstlist);
								}
							}
						
							
						}
					//}
					if(bNeedFollow[i])
						lstSellect[i]=Tools.AddArrayList(lstSellect[i],(ArrayList)aryFollow[getLeftIndex(strLeft)]);
					

				}	
			}

			//把select集拼装好并返回
			for(int i=0 ; i<lstSellect.Length ; i++)
			{

				lstItems.Add(lstSellect[i]);
			}
			return lstItems;
		}
		#endregion

		#region 检测是否是LL(1)文法

		public bool IsLL1(ArrayList select)
		{
			string strLeftItem="";
			ArrayList arylistRight= new ArrayList();
			ArrayList [] arrListSelect=Tools.ConvertToArray(select);
			ArrayList ListSelect=new ArrayList();
			if (listboxProducts.Items.Count<2) 
			{
				return false;		
			}
			for(int i=0 ; i < listboxProducts.Items.Count ; i++)
			{
				if(strLeftItem.Length==0)
				{
					strLeftItem=getProductLeft(i);
					arylistRight.Add(arrListSelect[i]);
				}
				else if (strLeftItem==getProductLeft(i))
				{
					arylistRight.Add(arrListSelect[i]);
				}
				else
				{
					ListSelect.Add(arylistRight);

					strLeftItem="";
					arylistRight=new ArrayList();
					//
					strLeftItem=getProductLeft(i);
					arylistRight.Add(arrListSelect[i]);
					//

					//Console.WriteLine(product.ToString() + i);
				}
				//防止丢失最后一个表达式
				if( i== listboxProducts.Items.Count-1)
				{
					ListSelect.Add(arylistRight);
					//Console.WriteLine(product.ToString() + i);
				}

			}
			//判断左部相同的产生式的SLECT集是否含有相同元素
			for(int i=0 ; i<ListSelect.Count ; i++)
			{
				//把左部相同的产生式的SLECT集取出
				ArrayList currentList=(ArrayList)ListSelect[i];
				//并转换为ArrayList的数组
				ArrayList [] arrList = Tools.ConvertToArray(currentList);
				//比较一组ArrayList中是否含有相同元素
				if(Tools.hasSameElement(arrList))
					return false;
			}
			return true;
		}

		#endregion

		#region 构建预测分析表
		/// <summary>
		/// 构建预测分析表
		/// </summary>
		/// <param name="select">SELECT集</param>
		/// <returns>Hashtable表格式的预测分析表</returns>
		public Hashtable BuildAnalysis(ArrayList select)
		{
			Hashtable hashAnalysis= new Hashtable();
			if(!IsLL1(select))return hashAnalysis;

			//用嵌套的循环来构建
			for(int i=0 ; i<select.Count ; i++ )
			{
				//取出产生式的左部
				string strNotSymbol=this.listboxProducts.Items[i].ToString().Substring(0,1);
				//取出当前的SELECT集
				ArrayList currentList=(ArrayList)select[i];
				for (int j=0 ; j<currentList.Count ; j++ )
				{
					//依次取出每个SELECT中的非终结符,然后和产生式的左部组成关键字存入哈希表
					hashAnalysis.Add( strNotSymbol + (string)currentList[j] , listboxProducts.Items[i].ToString());
				}
			}
			return hashAnalysis;
		}
		
		#endregion

		#region 分析字符串
		public bool CheckString(string strValue,string strat,Hashtable hashAnalysis)
		{
			Stack stackAnalysis=new Stack();			//分析栈
			Stack stackLeft=new Stack();				//剩余输入串
			int iCount=0;								//步骤计数器
			string left="";
			string right="";
			strAnalysisTable="";

			//初始化分析栈＆剩余输入串
			stackAnalysis.Push("#");
			stackAnalysis.Push(strat);
			strValue+="#";
			for(int i=strValue.Length-1 ; i>=0 ; i -- )
			{
				stackLeft.Push(strValue.Substring(i,1));
			}
			//Console.WriteLine(Tools.getStackStringqueueLeft.Count);

			while(stackAnalysis.Count>1 && stackLeft.Count>1)
			{
				left=(string)stackAnalysis.Pop();
				right=(string)stackLeft.Pop();
				iCount++;
				if(hashAnalysis.ContainsKey(left+right))
				{

					Console.WriteLine(iCount + "\t" +  Tools.getStackStringBT(stackAnalysis) + left  + "\t" 
						 + right+ Tools.getStackStringTB(stackLeft) + "\t" + hashAnalysis[left+right].ToString() );
					//输出到网页表格
					OutTableStep(iCount ,Tools.getStackStringBT(stackAnalysis) + left ,
						right+ Tools.getStackStringTB(stackLeft) , hashAnalysis[left+right].ToString() );

					string strProduct=hashAnalysis[left+right].ToString().Substring(2);
					for(int j=strProduct.Length-1 ; j>=0 ; j--)
					{
						//匹配就从右向左依次入栈
						string strChar=strProduct.Substring(j,1);
						if(strChar!="$")
							stackAnalysis.Push(strChar);
					}
					//把取出的字符串仍然送回
					stackLeft.Push(right);

				}
				else
				{
					if(left==right)
					{
						Console.WriteLine(iCount + "\t" + Tools.getStackStringBT(stackAnalysis)+ left + "\t" 
							+  right+Tools.getStackStringTB(stackLeft) + "\t" + "'" + left + "'匹配" );