package osa;
import java.util.Stack;
import java.lang.System.*;
import java.io.*;
import java.util.*;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: </p>
 * <p>Company: </p>
 * @author unascribed
 * @version
 */

public class LL1analysis
{
 public ArrayList RulesList=new ArrayList();
 public ArrayList Dictionary=new ArrayList();
 public ArrayList Selection=new ArrayList();
 public ArrayList Intersections=new ArrayList();
 public ArrayList FunctionsSheet=new ArrayList();
 public ArrayList IntersectionsSheet=new ArrayList();
 public Grammar OutGrammar;

 public ArrayList OptimizedFunctions=new ArrayList();
 public ArrayList GenericFunctions=new ArrayList();
 public ArrayList PopStackFunctions=new ArrayList();
 public ArrayList PopTerminalFunctions=new ArrayList();

 public LL1analysis(Grammar Gr)
  {
  OutGrammar=Gr;
  }

 public class Symbol
  {
  public boolean type;
  public String symbol_representation;
  public boolean isTerminal()
   {
   if(type==true)return true;
   else return false;
   }
  }

 public class NonTerminal extends Symbol
  {
  public boolean annuling;
  public boolean RightMost;
  private NonTerminal()
   {
   type=false;
   annuling=false;
   RightMost=false;
   }
  }

 public class Terminal extends Symbol
  {
  int out_index;
  boolean OnlyTheFirst;
  private Terminal()
   {
   type=true;
   OnlyTheFirst=true;
   }
  }

 public class Rule
  {
  public int LeftPart;
  public ArrayList RightPart;
  public int RightPartLen;
  public boolean annuling;
  private Rule()
   {
   RightPart=new ArrayList();
   }

  public Symbol GetSymbol(int num)
   {
   if(num<RightPart.size())
     return (Symbol)Dictionary.get(((Integer)RightPart.get(num)).intValue());
   else return null;
   }

  public int GetSymbolIndex(int num)
   {
   if(num<RightPart.size())
     return ((Integer)RightPart.get(num)).intValue();
   else return -1;
   }
  }

 public class Intersection
  {
  int FirstRule;
  int SecondRule;
  ArrayList IntersectSymb;
  public Intersection(int fr,int sr,ArrayList i)
   {
   FirstRule=fr;
   SecondRule=sr;
   IntersectSymb=i;
   }
  }

 public Symbol GetSymbol(int num)
  {
  if(num<Dictionary.size())
    return (Symbol)Dictionary.get(num);
  else return null;
  }

 public int GetSymbolPosition(String s)
  {
  int i;
  Symbol symb;
  for(i=0;i<Dictionary.size();i++)
     {
     if(((Symbol)Dictionary.get(i)).symbol_representation.equals(s))
       return i;
     }
  return -1;
  }

 private void ListsInit(Grammar.RTable SourceListOfRules)
  {
  NonTerminal temp_nt;
  Terminal temp_t;
  Rule temp_r;
  String buffer;
  int i,j,index;

  RulesList.clear();
  Dictionary.clear();
  int counter=0;
  for(i=0;i<SourceListOfRules.m_size;i++)
     {
     temp_r=new Rule();
     for(j=0;j<SourceListOfRules.m_rules[i].size();j++)
        {
        buffer=(String)SourceListOfRules.m_rules[i].get(j);
        if(!buffer.startsWith("$"))
          {
          index=GetSymbolPosition(buffer);
          if(index<0)
            {
            if(buffer.startsWith("<"))
              {
              temp_nt=new NonTerminal();
              temp_nt.symbol_representation=buffer;
              Dictionary.add(temp_nt);
              }
            else
              {
              temp_t=new Terminal();
              temp_t.symbol_representation=buffer;
              Dictionary.add(temp_t);
              }
            index=Dictionary.size()-1;
            }
          if(j==0)temp_r.LeftPart=index;
          else
            {
            temp_r.RightPart.add(new Integer(index));
            if(j>1&&GetSymbol(index).isTerminal()) ((Terminal)GetSymbol(index)).OnlyTheFirst=false;
            }
          }
          else
          {
          temp_r.annuling=true;
          ((NonTerminal)GetSymbol(temp_r.LeftPart)).annuling=true;
          }
        }
     if(temp_r.annuling)temp_r.RightPartLen=0;
     else temp_r.RightPartLen=j-1;
     RulesList.add(temp_r);
     }
  temp_t=new Terminal();
  temp_t.symbol_representation="\"-|\"";
  Dictionary.add(temp_t);
  }


 public Rule CutRule(Rule Source,int position)
  {
  Rule result=new Rule();
  int i;
  result.LeftPart=Source.LeftPart;

  for(i=position+1;i<Source.RightPartLen;i++)
     result.RightPart.add(new Integer(Source.GetSymbolIndex(i)));
  result.RightPartLen=result.RightPart.size();
  return result;
  }

 public Rule SubstFirst(Rule ToSubst,Rule Source)
 {
 Rule result=new Rule();
 int i;
 result.LeftPart=ToSubst.LeftPart;
 for(i=0;i<Source.RightPartLen;i++)
    result.RightPart.add(new Integer(Source.GetSymbolIndex(i)));
 for(i=1;i<ToSubst.RightPartLen;i++)
    result.RightPart.add(new Integer(ToSubst.GetSymbolIndex(i)));
 result.RightPartLen=result.RightPart.size();
 return result;
 }

 public ArrayList SubstLast(ArrayList ToSubst,ArrayList Source)
 {
 ArrayList result=new ArrayList();
 int i,j;
 j=ToSubst.size()-1;
 for(i=0;i<j;i++)result.add(new Integer(((Integer)ToSubst.get(i)).intValue()));
 j=Source.size();
 for(i=0;i<j;i++)result.add(new Integer(((Integer)Source.get(i)).intValue()));
 return result;
 }

 public void CheckAnnulingRules()
 {
 int i,j;
 int RulesListSize;
 int RuleLen;
 boolean ListIsUpdated=false;
 RulesListSize=RulesList.size();
 boolean RulesMask[]=new boolean[RulesListSize];
 int LastPosition[]=new int[RulesListSize];
 Rule eye;
 Symbol symb;
 do{
   ListIsUpdated=false;
   for(i=0;i<RulesListSize;i++)
      {
      if(!RulesMask[i])
        {
        eye=(Rule)RulesList.get(i);
        if(eye.annuling)
          {
          RulesMask[i]=true;
          ListIsUpdated=true;
          }
        else
          {
          RuleLen=eye.RightPart.size();
          RuleScan:{
                   for(j=LastPosition[i];j<RuleLen;j++)
                      {
                      symb=eye.GetSymbol(j);
                      if(symb.isTerminal())
                        {
                        RulesMask[i]=true;
                        break RuleScan;
                        }
                      else
                        {
                        if(!((NonTerminal)symb).annuling)
                          {
                          LastPosition[i]=j;
                          break RuleScan;
                          }
                        }
                      }
                   eye.annuling=true;
                   ((NonTerminal)GetSymbol(eye.LeftPart)).annuling=true;
                   RulesMask[i]=true;
                   ListIsUpdated=true;
                   }
          }
        }
      }
   }while(ListIsUpdated);
 }


 public void CheckRightMost()
  {
  int i,j;
  int CurLeftPart;
  Rule CurRule;
  ArrayList DeriveList=new ArrayList();
  ArrayList Chain=new ArrayList();
  boolean SymbolsMask[]=new boolean[Dictionary.size()];
  Symbol symb;
  Chain.add(new Integer(0));
  DeriveList.add(Chain);
  do{
    Chain=(ArrayList)DeriveList.get(0);
    CurLeftPart=((Integer)Chain.get(Chain.size()-1)).intValue();
    symb=GetSymbol(CurLeftPart);
    if(!symb.isTerminal())
      {
      if(!SymbolsMask[CurLeftPart])
        {
        ((NonTerminal)symb).RightMost=true;
        SymbolsMask[CurLeftPart]=true;
        j=RulesList.size();
        for(i=0;i<j;i++)
           {
           CurRule=(Rule)RulesList.get(i);
           if(!CurRule.RightPart.isEmpty())
             if(CurRule.LeftPart==CurLeftPart)
               DeriveList.add(SubstLast(Chain,CurRule.RightPart));
           }
        }
      if(((NonTerminal)symb).annuling)
        {
        Chain.remove(Chain.size()-1);
        if(Chain.size()>0)DeriveList.add(Chain);
        }
      }
    DeriveList.remove(0);
    }while(!DeriveList.isEmpty());
  }

 public void Derive(int RuleNumber)
 {
 int i,j;
 int CurLeftPart;
 boolean RulesMask[]=new boolean[RulesList.size()];
 boolean FirstMask[]=new boolean[Dictionary.size()];
 boolean FollowMask[]=new boolean[Dictionary.size()];
 boolean AnnulRuleNotUsed=true;
 ArrayList DeriveList=new ArrayList();
 ArrayList CurSelection=new ArrayList();
 Symbol FirstSymb;
 Rule rule;
 Rule eye;

 DeriveList.add(CutRule((Rule)RulesList.get(RuleNumber),-1));
 RulesMask[RuleNumber]=true;
 do{
   rule=(Rule)DeriveList.get(0);
   if(rule.RightPart.isEmpty())
     {
     //FOLLOW
     if(!FollowMask[rule.LeftPart])
       {
       FollowMask[rule.LeftPart]=true;
       CurLeftPart=rule.LeftPart;
       for(i=0;i<RulesList.size();i++)
          {
          eye=(Rule)RulesList.get(i);
          for(j=0;j<eye.RightPartLen;j++)
             {
             if(eye.GetSymbolIndex(j)==CurLeftPart)
               DeriveList.add(CutRule(eye,j));
             }
          }
       }
     }
   else
     {
     //FIRST
     FirstSymb=rule.GetSymbol(0);
     if(FirstSymb.isTerminal())FirstMask[rule.GetSymbolIndex(0)]=true;
     else
       {
       if(!FirstMask[rule.GetSymbolIndex(0)])
         {
         for(i=0;i<RulesList.size();i++)
            {
            if(!RulesMask[i])
              {
              eye=(Rule)RulesList.get(i);
              if(eye.RightPart.isEmpty())
                RulesMask[i]=true;
              else
                if(eye.LeftPart==rule.GetSymbolIndex(0))
                  {
                  RulesMask[i]=true;
                  DeriveList.add(SubstFirst(rule,eye));
                  if(eye.annuling)AnnulRuleNotUsed=false;
                  }
              }
            }
         FirstMask[rule.GetSymbolIndex(0)]=true;
         }
       if(((NonTerminal)FirstSymb).annuling&&AnnulRuleNotUsed)
         DeriveList.add(CutRule(rule,0));
       AnnulRuleNotUsed=true;
       }
     }
   DeriveList.remove(0);
   }while(!DeriveList.isEmpty());

 for(i=0;i<Dictionary.size();i++)
    {
    if(FirstMask[i])
      {
      if(GetSymbol(i).isTerminal())
        CurSelection.add(new Integer(i));
      }
    }
 rule=(Rule)RulesList.get(RuleNumber);
 if(rule.annuling&&((NonTerminal)GetSymbol(rule.LeftPart)).RightMost)
   CurSelection.add(new Integer(Dictionary.size()-1));
 Selection.add(CurSelection);
 }

 public void IntersectionsCheck()
  {
  int i,j,k,l;
  int CurLeftPart;
  ArrayList result=new ArrayList();
  ArrayList S1,S2;
  for(i=0;i<RulesList.size();i++)
     {
     CurLeftPart=((Rule)RulesList.get(i)).LeftPart;
     for(j=i+1;j<RulesList.size();j++)
        {
        if(CurLeftPart==((Rule)RulesList.get(j)).LeftPart)
          {
          S1=(ArrayList)Selection.get(i);
          S2=(ArrayList)Selection.get(j);
          for(k=0;k<S1.size();k++)
             for(l=0;l<S2.size();l++)
                {
                if(((Integer)S1.get(k)).intValue()==((Integer)S2.get(l)).intValue())
                  result.add(new Integer(((Integer)S1.get(k)).intValue()));
                }
          if(!result.isEmpty())
            {
            Intersections.add(new Intersection(i+1,j+1,result));
            result=new ArrayList();
            }
          }
        }
     }
  }

 public void TransFunctGen()
  {
  int i,j,k,l;
  Rule CurRule;
  Symbol Symb;
  ArrayList CurSelection;

  String Function;
  for(i=0;i<RulesList.size();i++)
     {
     CurRule=(Rule)RulesList.get(i);
     CurSelection=(ArrayList)Selection.get(i);
     if(CurRule.RightPart.isEmpty())
       {
       for(j=0;j<CurSelection.size();j++)
          {
          Function=new String();
          Function=Function+"*(S,";
          Function=Function+GetSymbol(((Integer)CurSelection.get(j)).intValue()).symbol_representation+",";
          Function=Function+GetSymbol(CurRule.LeftPart).symbol_representation+")=(S,$,$)";
          l=50-Function.length();
          for(k=0;k<l;k++)Function=Function+" ";
          Function=Function+" -- для правила "+(i+1);
          PopStackFunctions.add(Function);
          }
       }
     else
       if(CurRule.GetSymbol(0).isTerminal())
         {
         for(j=0;j<CurSelection.size();j++)
            {
            Function=new String();
            Function=Function+" (S,";
            Function=Function+GetSymbol(((Integer)CurSelection.get(j)).intValue()).symbol_representation+",";
            Function=Function+GetSymbol(CurRule.LeftPart).symbol_representation+")=(S,";
            if(CurRule.RightPartLen>1)
            for(k=CurRule.RightPartLen-1;k>0;k--)
               Function=Function+CurRule.GetSymbol(k).symbol_representation;
            else Function=Function+"$";
            Function=Function+",$)";
            l=50-Function.length();
            for(k=0;k<l;k++)Function=Function+" ";
            Function=Function+" -- для правила "+(i+1);
            OptimizedFunctions.add(Function);
            }
         }
       else
         {
         for(j=0;j<CurSelection.size();j++)
            {
            Function=new String();
            Function=Function+"*(S,";
            Function=Function+GetSymbol(((Integer)CurSelection.get(j)).intValue()).symbol_representation+",";
            Function=Function+GetSymbol(CurRule.LeftPart).symbol_representation+")=(S,";
            for(k=CurRule.RightPartLen-1;k>=0;k--)
               Function=Function+CurRule.GetSymbol(k).symbol_representation;
            Function=Function+",$)";
            l=50-Function.length();
            for(k=0;k<l;k++)Function=Function+" ";
            Function=Function+" -- для правила "+(i+1);
            GenericFunctions.add(Function);
            }
         }
     }

  for(i=0;i<Dictionary.size();i++)
     {
     Symb=GetSymbol(i);
     if(Symb.isTerminal())
       if(!((Terminal)Symb).OnlyTheFirst)
         {
         Function=new String();
         Function=Function+" (S,"+Symb.symbol_representation+","+Symb.symbol_representation+")=(S,$,$)";
         PopTerminalFunctions.add(Function);
         }
     }

  FunctionsSheet.add("-- Оптимизированные функции для правил, правая часть которых начинается с терминала");
  FunctionsSheet.add("-- сдвиг, вытолкнуть, заменить");
  for(i=0;i<OptimizedFunctions.size();i++)FunctionsSheet.add((String)OptimizedFunctions.get(i));

  FunctionsSheet.add("-- Функции общего вида");
  FunctionsSheet.add("-- нет сдвига, заменить");
  for(i=0;i<GenericFunctions.size();i++)FunctionsSheet.add((String)GenericFunctions.get(i));

  FunctionsSheet.add("-- Функции для аннулирующих правил");
  FunctionsSheet.add("-- нет сдвига, вытолкнуть");
  for(i=0;i<PopStackFunctions.size();i++)FunctionsSheet.add((String)PopStackFunctions.get(i));

  FunctionsSheet.add("-- Функции выталкивания терминалов");
  FunctionsSheet.add("-- сдвиг, вытолкнуть");
  for(i=0;i<PopTerminalFunctions.size();i++)FunctionsSheet.add((String)PopTerminalFunctions.get(i));

  FunctionsSheet.add("-- Функция перехода в заключительное состояние");
  FunctionsSheet.add(" (S,\"-|\",\"[]\")=(S,$,$)");
  }


 public void FillOutIntersectionsList()
  {
  int i,j,k,l;
  int renum;
  ArrayList OutTerminalsList=OutGrammar.TT.m_Ttable;
  ArrayList CurSelection;
  ArrayList RenumCurSelection;
  Symbol symb;
  String str;
  int RenumerationTable[]=new int[Dictionary.size()];
  k=OutTerminalsList.size();
  l=Dictionary.size();
  for(i=0;i<k;i++)
     {
     str=(String)OutTerminalsList.get(i);
     for(j=0;j<l;j++)
        {
        symb=(Symbol)Dictionary.get(j);
        if(symb.isTerminal())
          if(str.equals(symb.symbol_representation))RenumerationTable[j]=i;
        }
     }

  OutGrammar.GMainFrame.alSelection.clear();
  k=RulesList.size();
  for(i=0;i<k;i++)
     {
     CurSelection=(ArrayList)Selection.get(i);
     l=CurSelection.size();
     RenumCurSelection=new ArrayList();
     for(j=0;j<l;j++)
        {
        renum=RenumerationTable[((Integer)CurSelection.get(j)).intValue()];
        RenumCurSelection.add(new Integer(renum));
        }
     OutGrammar.GMainFrame.alSelection.add(RenumCurSelection);
     }
  }


 public boolean Analyse(Grammar.RTable SourceListOfRules)
  {
  int i,j,k;
  Rule r;
  Intersection conflict;
  String str;
  ListsInit(SourceListOfRules);
  CheckAnnulingRules();
  CheckRightMost();
  for(i=0;i<RulesList.size();i++)Derive(i);
  IntersectionsCheck();
  FillOutIntersectionsList();
  if(Intersections.isEmpty())
    {
    TransFunctGen();
    return true;
    }
  if(Intersections.size()<=200) k=Intersections.size(); else k=200;
  for(i=0;i<k;i++)
     {
     conflict=(Intersection)Intersections.get(i);
     str=new String();
     str=str+"Пересечение множеств ВЫБОР для правил "+conflict.FirstRule+" и "+conflict.SecondRule+" : ";
     for(j=0;j<conflict.IntersectSymb.size();j++)
        {
        str=str+GetSymbol(((Integer)conflict.IntersectSymb.get(j)).intValue()).symbol_representation;
        if(j!=conflict.IntersectSymb.size()-1)str=str+",";
        }
     IntersectionsSheet.add(str);
     }
  OutGrammar.GMainFrame.alGeneratedFinctions=IntersectionsSheet;
  return false;
  }
}
