判别ll(1)文法.txt

根据判断一个文法是LL(1)文法的三个条件

/// <summary>
/// 判断是否含有左递归
/// </summary>
/// <returns>
/// true 表示含有左递归
/// false 表示不含有左递归
///</returns>
public bool IsHaveLeftRecursion(){
    Stack  stkLeftRecursion=new Stack ();
    ArrayList newLeftItem = new ArrayList();
//处理所有的Product为一个左部和一个右部的格式
    for (int i = LeftItem.Count-1; i >= 0; i--){
     	for (int j = (LeftItem[i] as Product).RightItems.Count-1; j >= 0; j--){
       	string tmpright = ((LeftItem[i] as Product).RightItems[j] as string);
       	ArrayList tmpArrayList = new ArrayList();
           tmpArrayList.Add(tmpright );
         	Product aProduct=new Product ((LeftItem [i] as Product).LeftItem ,tmpArrayList );
          System.Console.WriteLine(i +"|"+j+ ":" + aProduct.ToString());
          newLeftItem.Add(aProduct);
          }
    }
//将所有的产生式倒序压入栈
   for (int i = 0; i < newLeftItem.Count; i++){
         stkLeftRecursion.Push((newLeftItem[i] as Product));
      }
      System.Console.WriteLine("输出判断左递归");
      int tmp = 0;
      //循环判断所有的左递归
      while (stkLeftRecursion.Count > 0){
         	Product aProduct = (Product)stkLeftRecursion.Pop();
           System.Console.WriteLine(tmp.ToString());
           tmp++;
           System.Console.WriteLine(aProduct.ToString ());
           if (aProduct.GetFirstRightItemNonTerminal ()!="false"){
            	string strNonTerminal = aProduct.GetFirstRightItemNonTerminal();
              System.Console.WriteLine("非终结符："+strNonTerminal );
              //判断是否为左递归
              if (aProduct.LeftItem == strNonTerminal){
                  return true ;
              }
              //替换第一个非终结符，并将新的产生式压入栈
              for (int i = 0; i < newLeftItem.Count; i++){
                  Product usedProduct = new Product();
                  usedProduct = (newLeftItem[i] as Product);
                  if (usedProduct.LeftItem.Equals (strNonTerminal )){
                       string strNewRight;
                       string strRight = (aProduct.RightItems[0] as string);
                       string wantRight = (usedProduct.RightItems[0] as string); 
                       //替换非终结符
                      strNewRight = strRight.Replace(strNonTerminal ,wantRight );
                      ArrayList tmpRightItem = new ArrayList();
                      tmpRightItem.Add(strNewRight);
                      Product tmpProduct = new Product(aProduct.LeftItem ,tmpRightItem );
                      newLeftItem.Add(tmpProduct);
                      stkLeftRecursion.Push(tmpProduct);
                    }
                }
           }             
       }
        //没有左递归返回
        return false;
}
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)
							{
								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))
								{
									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;
		}
		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;
		}