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

 /**
  * Класс предназначен для анализа и внутреннего представления грамматики,
  * вводимой пользователем. Содержит классы описывающие символы и правила
  * грамматики и методы для её анализа.
 */

 public class Grammar
 {
 /**
   *  Число правил в грамматике.
 */
   private int size=2000;
   MainFrame GMainFrame;
   public Grammar(MainFrame wFrame)
   {
   GMainFrame=wFrame;
   }

 LL1analysis LL;

 /**
  * @param sz задает максимальное число правил, которые могут быть в грамматике.
 */
  // public Grammar(int sz){
  // if(sz>size)size=sz;
  // }

 /**
   * Класс предназаначен для описания списка терминальных символов грамматики.
 */
   public class TTable{
    public ArrayList m_Ttable=new ArrayList();
 /**
   * Функция добавляет в список символов грамматики новый символ @param t
   * если такого нет символа t в списке нет
 */
    public void addnew(String t){
      if(m_Ttable.contains(t)==false)
         m_Ttable.add(t);
    }
   };
 /**
   * Класс предназаначен для описания списка нетерминальных символов грамматики.
   *
 */
   public class NTable{
    public ArrayList m_Ntable=new ArrayList();
 /**
   * Функция добавляет в список символов грамматики новый символ @param t
   * если такого нет символа t в списке нет.
 */
    public void addnew(String t){
      if(m_Ntable.contains(t)==false)
         m_Ntable.add(t);
    }
   };
 /**
   * Класс предназаначен для описания списка правил грамматики.
   *
 */
   public class RTable{
 /** Список правил, индекс в списке является номером правила. **/
    public  ArrayList[] m_rules=new ArrayList[size];
 /** Число правил в списке **/
    public  int m_size;
   };

 /**
   * Класс предназаначен для описания ошибки в синтаксисе описания грамматики.
   *
 */
   class RuleError{
 /**  Позиция (номер строки в редакторе грамматики) ошибки. **/
    public int str;
 /**  Тип ошибки. **/
    public int type;
   };
 /**
   *  Число ошибок в грамматике.
 */
    public int err=0;
 /**  Список правил грамматики. **/
   public RTable RT=new RTable();
 /**  Список нетерминальных символов грамматики. **/
   public NTable NT=new NTable();
 /**  Список терминальных символов грамматики. **/
   public TTable TT=new TTable();

 /**  Список достижимых символов грамматики. **/
   public ArrayList D_1=new ArrayList();
 /**  Список производящих символов грамматики (нетерминалов). **/
   public ArrayList N_1=new ArrayList();
 /**  Список недостижимых символов грамматики. **/
   public ArrayList D_2=new ArrayList();
 /** Список непроизводящих символов грамматики (нетерминалов). **/
   public ArrayList N_2=new ArrayList();

 /** Список ошибок. **/
   RuleError[] RE=new RuleError[size];
 /** Список строк с укзанием типа правила, если nu не равно null значит правило с индексом строки аннулирующее. **/
   public String[] nu=new String[size];

 /**
   * Функция удаляет пробелы из строки с правилом грамматики, вводимой пользователем
   * @param in исходная строка,  возвращает  преобразованную строку
 */
  public String Clear(String in)
  {
    String out="";int i=0,s=0;
    if(in.startsWith("--"))return "";
    if(in.indexOf("--")>0) in=in.substring(0,in.indexOf("--"));
      do{if(in.length()==0)return "";
         if(in.charAt(i)=='"')                   // Если начинаем читать многосимвольный
         do{out+=in.charAt(i);i++;
           if(in.length()==i)return in;          // Если есть ошибка
         }while(in.charAt(i)!='"');
         if(in.charAt(i)=='<'&&s==0)s=2;         // Если начинаем читать нетерминал
         if(in.charAt(i)=='>'&&s==2)s=0;         // Если зак читать нетерминал
         if(in.charAt(i)==' '&&s==2)
         out+=in.charAt(i);
         if(in.charAt(i)!=' ')out+=in.charAt(i);i++;
       }while(i<in.length());
     return out;
  }

  /**
   * Функция заносит ошибку в список ошибок
   * @param str номер строки в редакторе грамматики,
   * @param type тип ошибки,
   * возвращает общее число ошибок.
 */

  public int AddError(int str,int type) // Функция заносит ошибку в список ошибок
  {
   if(err!=size){
   RE[err]=new RuleError();
   RE[err].str=str;RE[err].type=type;
   err++;}return err;
  }

  /**
   * Функция анализирует грамматику, строит списки правил и символов грамматики,
   * @param s грамматика, введенная пользователем в редакторе грамматики.
   * Возращает: 0 - если правил в грамматике нет,
   *            1 - если в грамматике обнаружены ошибки,
   *            2 - если грамматике не приведена,
   *            3 - если грамматика не относиться к классу LL(1),
   *            4 - если грамматика отноиться к классу LL(1),
 */

  public int GrammarInit(ArrayList s)
   {
    int i=0;                                          // Cчетчик строк
    int r=0;                                          // Счетчик символов в правиле
    int j=0;                                          // Счетчик символов в правиле грамматики
    int q=-1;                                         // Счетик  правил грамматике
    int t=0;                                          // Переменная для буферизации индекса подстроки с правилом
    int es=0;                                         // Флаг ошибки, =1 если в правиле обнаружена ошибка

    int sem=0;                                        // Флаги состояний анализа правила, необходимы для проверки
    int sem2=0;                                       // правильности синтаксиса правила
    int sem3=0;
    int sem4=0;
    int sem5=0;

    String w;                                         // Строка содержит правило грамматики, которое будет анализироваться
    char c;                                           // Отдельный символ анализируемой строки

    TT.addnew("\"-|\"");                              // Первым в списке терминальных символов должен быть всегда символ "-|"

    if(s.size()==0)return 0;

    do{
      j=0;
      sem=0;sem3=0;sem4=0;sem5=0;
      do{
         w=Clear(s.get(i).toString());     // Удаляем пробелы из строки
         if(w.length()==0)break;           // Если полученная строка пустая то переходим к следующей
         c=w.charAt(j);
         if(c=='<'){                       // Начинаем чтение левой части правила
                   t=j;r=0;
                   do{j++;r++;if(j>=w.length()){sem=1;AddError(i,3);break;}}while(w.charAt(j)!='>');
                   if(sem==1)break;
                   NT.addnew(w.substring(t,r+t+1));q++;            // Заносим нетерминал в список
                   if(q==size){AddError(i,6);return 1;}
                   RT.m_rules[q]=new ArrayList();
                   RT.m_rules[q].add(w.substring(t,r+t+1));j++;    // Заносим левую часть правила
                   if(j>=w.length()){AddError(i,7);break;}
                   if(w.charAt(j)!=':'){AddError(i,7);break;}j++;
                   if(j>=w.length()){AddError(i,7);break;}
                   if(w.charAt(j)!=':'){AddError(i,7);break;}j++;
                   if(j>=w.length()){AddError(i,8);break;}
                   if(w.charAt(j)!='='){AddError(i,8);break;}j++;
                   if(j>=w.length()){AddError(i,2);break;}sem2=0;
                   do{c=w.charAt(j);
                     switch(w.charAt(j)){
                      case ' ':break;
                      case '<':t=j;r=0;if(sem4==1){sem2=1;AddError(i,4);break;}
                               if(sem5==1){sem2=1;AddError(i,4);break;}
                               do{j++;r++;if(j>=w.length()){sem=1;AddError(i,1);break;}}while(w.charAt(j)!='>');
                               if(sem==1){sem2=1;break;}sem3=1;
                               NT.addnew(w.substring(t,r+t+1));             // Заносим нетерминал в список
                               RT.m_rules[q].add(w.substring(t,r+t+1));     // Заносим правую часть правила
                                   break;
                     case '"':t=j;r=0;if(sem4==1){sem2=1;AddError(i,4);break;}
                              if(sem5==1){sem2=1;AddError(i,4);break;}
                              do{j++;r++;if(j>=w.length()){sem=1;AddError(i,0);break;}}while(w.charAt(j)!='"');
                              if(sem==1){sem2=1;break;}sem3=1;
                              TT.addnew(w.substring(t,r+t+1));             // Заносим терминал в список
                              RT.m_rules[q].add(w.substring(t,r+t+1));     // Заносим правую часть правила
                                   break;
                     case '|':if(sem4==1){sem2=1;AddError(i,4);break;}
                              if(w.charAt(j-1)=='='){sem2=1;sem3=1;AddError(i,2);break;}
                              if(w.charAt(j-1)=='|'){sem2=1;sem3=1;AddError(i,2);break;}
                              j++;sem4=0;
                              if(j>=w.length()){sem2=1;AddError(i,2);break;}
                              if(w.charAt(j)==' '){sem2=1;AddError(i,2);break;}j--;
                              q++;if(q==size){AddError(i,6);return 1;}
                              RT.m_rules[q]=new ArrayList();RT.m_rules[q].add(RT.m_rules[q-1].get(0));
                              sem5=0;
                                   break;
                     default :t=j;r=0;sem3=1;if(c=='>'||c=='('||c==')'||c==':'||c==',')
                              {sem3=1;sem2=1;AddError(i,3);break;}
                              if(sem4==1){sem2=1;AddError(i,4);break;}
                              if(sem5==1){sem2=1;AddError(i,4);break;}
                              if(w.substring(j,j+1).compareTo("$")==0){sem4=1;sem5=1;
                              if(RT.m_rules[q].size()>1){sem2=1;AddError(i,4);break;}
                              else {sem4=0;}
                              }
                              TT.addnew(w.substring(j,j+1));               // Заносим нетерминал в список
                              RT.m_rules[q].add(w.substring(j,j+1));       // Заносим правую часть правила
                              break;
                       }j++;
                      if(sem2==1)break;
                   }while(j<w.length());
                  if(sem3==1)break;
          }else if(c!=' '){AddError(i,3);break;}
          j++;
        }while(j<w.length());
      i++;
     }while(i<s.size());

 if(err > 0)return 1;      // Если были ошибки, то возвращаем 1

 TT.m_Ttable.remove("$");

 RT.m_size=q+1;

 if(RT.m_size==0)return 0; // Если нет ни одного правила, то возвращаем 0

 int k=0;
// Помечаем те нетерминалы, которые являются аннулирующими
 for(i=0;i<RT.m_size;i++)
   nu[i]=new String("");
 for(i=0;i<RT.m_size;i++){
   if(RT.m_rules[i].get(1).toString().compareTo("$")==0)
   {
    k=NT.m_Ntable.indexOf(RT.m_rules[i].get(0));
    nu[k]=new String(" - аннулирующий");
   }
 }

// ********************************* ПОИСК ПРОИЗВОДЯЩИХ И ДОСТИЖИМЫХ ***************************
// Ищем  производящие символы, для этого состовляем список  нетерминалов, для конорых найдено
// хотя бы одно правило, правая часть которого состоит из терминальных символов.
// *********************************************************************************************

 int has=0; k=0;
 int presize; // Размер списка
 do
 {
 presize=N_1.size();
 i=0;j=0;
     do{
        has=0;
        k=1;
          do{                                         // Анализируем каждый элемент правой части i-ого правила
             if(RT.m_rules[i].get(k).toString().startsWith("<")==true)
              has=1;
              k++;
            }while(k<RT.m_rules[i].size());
              if((has==0)&&(N_1.contains(RT.m_rules[i].get(0))==false)&&RT.m_rules[i].get(0).toString().startsWith("<")==true)
              {
               N_1.add(RT.m_rules[i].get(0));        // Добавляем в список нетерминал
              }
        i++;
       }while(i<RT.m_size);
// Ищем правило, такое, что все нетерминалы, стоящие в его правой части уже занесены в список, и еслит такое есть,
// то добавляем в список нетерминал, стоящий в левой части правила
 i=0;j=0;int hasall=1;
      do{
        j=1;hasall=1;                                    // Полагаем что все содержит
        do{
          if(RT.m_rules[i].get(j).toString().startsWith("<")==true)
           if(N_1.contains(RT.m_rules[i].get(j))==false) // Если не содержит то меняем флаг
             hasall=0;
             j++;
          }while(j<RT.m_rules[i].size());
        if((hasall==1)&&(N_1.contains(RT.m_rules[i].get(0))==false))
              N_1.add(RT.m_rules[i].get(0));
           i++;
       }while(i<RT.m_size);
    if(N_1.size()==presize)break;  // Если размер списка не изменился за шаг, то все производящие символы найдены
 }while(true);

// Теперь будем искать все достижимые символы грамматики, для этого занесем в список начальный символ грмматики
 D_1.add(RT.m_rules[0].get(0));
// Если есть правило, левая часть которого находиться в списке, то включть все символы, находящиеся в правой части
 i=0;
 do{
 i=0;
 presize=D_1.size();
   do{
     if(D_1.contains(RT.m_rules[i].get(0))==true)
       for(j=1;j<RT.m_rules[i].size();j++)
         if(D_1.contains(RT.m_rules[i].get(j))==false)
          D_1.add(RT.m_rules[i].get(j));
    i++;
   }while(i<RT.m_size);
 if(D_1.size()==presize)break;
 }while(true);

// ПОЛУЧЕНИЕ НЕДОСТИЖИЫХ (ОНИ В СПИСКЕ D_2)
   for(i=0;i<NT.m_Ntable.size();i++)
       D_2.add(NT.m_Ntable.get(i));
   for(i=0;i<TT.m_Ttable.size();i++){
     if(TT.m_Ttable.get(i).toString().startsWith("\"-|\"")==false)
       D_2.add(TT.m_Ttable.get(i));}
   for(i=0;i<D_1.size();i++)
       D_2.remove(D_1.get(i));
   // ПОЛУЧЕНИЕ НЕПРОИЗВОДЩИХ (ОНИ В СПИСКЕ N_2)
   for(i=0;i<NT.m_Ntable.size();i++)
       N_2.add(NT.m_Ntable.get(i));
   for(i=0;i<N_1.size();i++)
       N_2.remove(N_1.get(i));

   if(N_2.size()!=0||D_2.size()!=0&&D_2.get(0).toString().startsWith("\"-|\"")==false)return 2;

//********************************************************************************************************************
// Анализ грамматики на свойство LL(1)
// Грамматика наывается LL(1) если мно-во выбор для правил с одинаковой левой частью не содржит одинаковых элементов
// Сначала необходимо определить мно-ва ПЕРВ и СЛЕД для каждого правила в грамматике
//********************************************************************************************************************

   LL=new LL1analysis(this);
   if(LL.Analyse(RT)==true) // Если грамматика относиться к классу LL(1), то возвращаем 4, иначе 3
    return 4;
   else
     return 3;
   }
}