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

/**
  * Класс описывает магазинный распознователь(преобразователь).
  * Содержит классы описывающие автомат, функции переходов и шаги работы распознователя(перобразователя),
  * а так же методы для распознавания цепочек подаваемых на вход распознователя(преобразователя).
  *
**/

public class Recognizer{
    private int dim=2000;
/**
  * Класс описывает автомат (т.е. распознователь(преобразователь)).
**/

 public class Automat{

/**
  *  Входная лента, на которую записана цепочка языка, созданного пользователем.
**/
    public String[] m_lenta=new String[dim];
/**
  *  Магазин автомата.
**/
    public Stack m_stack=new Stack();
/**
  *  Шаг работы автомата.
**/
    public int m_step;
/**
  *  Счетчик входной ленты, на которую записана цепочка языка.
**/
    int m_cnt;
/**
  *  Метод инициализирует автомат.
  *  @param цепочка языка,
  *  @param начальный символ грамматики.
**/
    public void Init(String lenta,String sp){
    int i=0,t=0,j=0,p=0;
    do{
       if(lenta.charAt(i)=='"'){
       t=i;j=0;
        do{
         j++;i++;
          }
        while(lenta.charAt(i)!='"');
        if(p==dim)break;
        m_lenta[p]=new String(lenta.substring(t,t+j+1));
        p++;
      }else if(lenta.charAt(i)!=' ')
        {
        if(p==dim)break;
        m_lenta[p]=new String(lenta.substring(i,i+1));
        p++;
        }
      i++;                                    // Считаем элементы цепочки
     }while(i<lenta.length());
    if(p==dim){AddError(0,13);}else
    {A.m_lenta[p]=new String("\"-|\"");p++;}

    m_cnt=p;
    m_stack.push("\"[]\"");                   // Заносим маркер дна магазина
    m_stack.push(sp);                         // Заносим в стек аксиому грамматики, или начальный символ
    m_step=0;
    }
  }
/**
  * Класс левую часть функции перехода распознователя(преобразователя).
**/
  class FTable{
/**
  * Символ входной цепочки (точнее терминальный символ грамматики, описывающей вх. цепочку.
**/
    String L;
/**
  * Символ выходной цепочки, которая будет записана на выходную ленту перобразователя.
**/
    String OL;
/**
  * Символ в вершине магазина распознователя (проебразователя).
**/
    String S;
/**
  * Символьное представление функции перехода (левая и правая части).
**/
    String R;
/**
  * Указатель на таблицу действий.
**/
    int a;
  }

  class FAction{
    public
    String   toSTACK;                         // Цепочка которую необходимо занести в стек
    String[] m_list = new String[dim];         // Цепочка которую необходимо занести в стек
    int type;                                 // Тип действия
    int cnt;
  }

  class FLog{
    public
    Stack STACK;
    String Chain;
    String Function;
    String Outchain;
    ArrayList Errors = new ArrayList();
    int steps;
  }

  class FError{
    public int str;
    public int pos;
    public int col;
  }

                                             // Интересно сделать это число переменным, зависящим от числа правил грамматики
  public FTable[]  FT = new FTable[dim];     // Скажем более 2000 ф-ций перехода быть вероятно не может
  public FAction[] FA = new FAction[dim];
  public FLog[]    FL = new FLog[dim];
  public FError[]  FE = new FError[dim];

  public Automat A = new Automat();

  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)=='#')                   // Если начинаем читать многосимвольный
      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;
 }

 int err=0;

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

  public int GenerateAll(ArrayList s,boolean Convert){

    FL[1000]=new FLog();
    String r,str="";
    int i=0;                                   // счетчик строк
    int j=0;                                   // счетчик символов в строке
    int f=0;                                   // счетчик функций переходов
    int e=0;                                   // счетчик ошибок
    int k=0;                                   // счетчик элементов
    int t,w;
    int se=0;int type=0;

   if(s.size()==0){AddError(0,-1);return -1;}
   do{
      r=Clear(s.get(i).toString());
      j=0;se=0;type=0;
       do{
          if(r.length()==0)break;                               // Если строка пуста, то переходим к следующей
          if((r.charAt(j)=='(')){j++;FT[f]=new FTable();FA[f]=new FAction();FA[f].type=type;
          if(r.length()==j){AddError(i,0);break;}
          if(r.charAt(j)!='S'){AddError(i,0);break;}j++;
          if(r.length()==j){AddError(i,1);break;}
          if(r.charAt(j)!=','){AddError(i,1);break;}j++;
          if(r.length()==j){AddError(i,2);break;}
          // Содержимое ленты может быть много или односимольный терминал
          if(r.charAt(j)=='"'){t=j;w=0;// Формируем многосимвольный терминал
                               do{j++;w++;if(r.length()==j){se=1;AddError(i,8);break;}}while(r.charAt(j)!='"'); //
                                  if(se==1)break;FT[f].L=new String(r.substring(t,t+w+1));
                              }else if(r.charAt(j)!='>'&&r.charAt(j)!='<'&&r.charAt(j)!=')'&&r.charAt(j)!='(')
                              {FT[f].L=new String(r.substring(j,j+1));}else{se=1;AddError(i,11);break;}j++;
                              if(r.length()==j){AddError(i,1);break;}
                              if(r.charAt(j)!=','){AddError(i,1);break;}j++;if(r.length()==j){AddError(i,3);break;}
                              // Содержимым вершины стека может быть много- или односимольный терминал или нетерминал или символ
         if(r.charAt(j)=='<'){t=j;w=0;// Формируем нетерминал
                              do{j++;w++; if(r.length()==j){se=1;AddError(i,9);break;}}while(r.charAt(j)!='>');
                              if(se==1)break;FT[f].S=new String(r.substring(t,t+w+1));}else
         if(r.charAt(j)=='#'){t=j;w=0;// Формируем многосимвольный терминал
                              do{j++;w++; if(r.length()==j){se=1;AddError(i,10);break;}}while(r.charAt(j)!='#');
                              if(se==1)break;FT[f].S=new String(r.substring(t,t+w+1));}else
         if(r.charAt(j)=='"'){t=j;w=0;// Формируем многосимвольный терминал
                              do{j++;w++;if(r.length()==j){se=1;AddError(i,8);break;}}while(r.charAt(j)!='"');
                              if(se==1)break;FT[f].S=new String(r.substring(t,t+w+1));}else
                              if(r.charAt(j)!='>'&&r.charAt(j)!='<'&&r.charAt(j)!=')'&&r.charAt(j)!='(')
                              {// Формируем односимвольный терминал
                              FT[f].S=new String(r.substring(j,j+1));}else{se=1;AddError(i,11);break;} j++;
                              if(r.length()==j){AddError(i,4);break;}
                              if(r.charAt(j)!=')'){AddError(i,4);break;}j++;
                              if(r.length()==j){AddError(i,5);break;}
                              if(r.charAt(j)!='='){AddError(i,5);break;}j++;
                              if(r.length()==j){AddError(i,6);break;}
                              if(r.charAt(j)!='('){AddError(i,6);break;}j++;
                              if(r.length()==j){AddError(i,0);break;}
                              if(r.charAt(j)!='S'){AddError(i,0);break;}j++;
                              if(r.length()==j){AddError(i,1);break;}
                              if(r.charAt(j)!=','){AddError(i,1);break;}j++;
                              if(r.length()==j){AddError(i,3);break;}k=0;
                   do{// формируем цепочку которую будем заносить в текст
        if(r.charAt(j)=='<'){t=j;w=0;           // Формируем нетерминал
                             do{j++;w++;if(r.length()==j){se=1;AddError(i,9);break;}}while(r.charAt(j)!='>');
                             if(se==1)break;FA[f].m_list[k]=new String(r.substring(t,t+w+1));k++;}else
        if(r.charAt(j)=='#'){t=j;w=0;       // Формируем многосимвольный терминал
                             do{j++;w++;if(r.length()==j){se=1;AddError(i,10);break;}}while(r.charAt(j)!='#');
                             if(se==1)break;FA[f].m_list[k]=new String(r.substring(t,t+w+1));k++;}else
        if(r.charAt(j)=='"'){t=j;w=0;                     // Формируем многосимвольный терминал
                             do{j++;w++;if(r.length()==j){se=1;AddError(i,8);break;}}while(r.charAt(j)!='"');
                             if(se==1)break;FA[f].m_list[k]=new String(r.substring(t,t+w+1));k++;}else
        if(r.charAt(j)!=','){if(r.charAt(j)!='>'&&r.charAt(j)!='<'&&r.charAt(j)!=')'&&r.charAt(j)!='(')
                             FA[f].m_list[k]=new String(r.substring(j,j+1));else {se=1;AddError(i,11);break;}
                             k++;}else {se=1;AddError(i,1);break;}
                             j++;if(r.length()==j){se=1;AddError(i,1);break;}
                    }while(r.charAt(j)!=',');if(se==1)break;j++;if(r.length()==j){AddError(i,0);break;}
                      // Теперь ищем терминал выходной ленты
        if(r.charAt(j)=='#'){t=j;w=0;// Формируем многосимвольный терминал
                             do{j++;w++;if(r.length()==j){se=1;AddError(i,10);break;}}while(r.charAt(j)!='#');
                             if(se==1)break;FT[f].OL=new String(r.substring(t,t+w+1));}else
        if(r.charAt(j)=='"'){t=j;w=0;// Формируем многосимвольный терминал
                             do{j++;w++;if(r.length()==j){se=1;AddError(i,8);break;}}while(r.charAt(j)!='"');
                             if(se==1)break;FT[f].OL=new String(r.substring(t,t+w+1));}else
        if(r.charAt(j)=='$')FT[f].OL=new String(r.substring(j,j+1));
                            else{se=1;AddError(i,7);break;}j++;
                            if(j==r.length()){se=1;AddError(i,7);break;}if(se==1)break;
                            if(r.charAt(j)!=')'){se=1;AddError(i,4);break;}if(se==1)break;j++;
                            FT[f].a=f;FA[f].cnt=k;String q="";
                            for(int v=0;v<k;v++)q+=FA[f].m_list[v];
                            str=new String("(S,"+FT[f].L+","+FT[f].S+")=(S,"+q+","+FT[f].OL+")");
                            if(FA[f].type==1)FT[f].R=new String("*"+str);else FT[f].R=new String(str);
                            f++;if(f==dim){AddError(i,12);return -1;}
                            break;
                        }else if(r.charAt(j)=='*'){type=1;j++;}else {AddError(i,6);break;}
         }while(j<r.length());
      i++;
   }while(i<s.size());


  if(err>0)return -1;else
    return f;     // Возвраается ноль если ошибок не было и -1 если были. Да ! Забыл, мясо здесь заканчивается ...:))
  }

  public int ExpressAnanlyze(ArrayList Functions,String Chain,boolean Convert,String SP)
  {
    int st=0;                                            // Счетчик шагов работы автомата
    int use=0;                                           // Use=1 если функция перехода найдена, иначе Use=0
    int cp=0;                                            // Указатель на цепочку
    int i=0;                                             // Указатель на функцию перехода в таблице
    String log;                                          // Строка для вывода протокола в файл

    int f=GenerateAll(Functions,Convert);                // Строим таблицы с функциями переходов

    A.Init(Chain,SP);                                    // инициализируем автомат, занесем цепочку на ленту и нач. символ
                                                         // в магазин
    FL[0]=new FLog();
    FL[0].Outchain="";
    FL[0].steps=0;
    if(f<=0){return 1;}                                  // Ф-ций перхода нет или ошибка !
    do{
     i=0;use=0;
     do{                                                 // Просматриваем таблицы и ищем подходящую функцию перехода
        if(((A.m_lenta[cp].compareTo(FT[i].L)==0))&&(A.m_stack.lastElement().toString().compareTo(FT[i].S)==0)
         ||((A.m_stack.lastElement().toString().compareTo(FT[i].OL)==0)&&(FT[i].L.indexOf("$")>=0)))
          {
            st++;                                        // Считаем щаги работы автомата
            FL[st]=new FLog();
            FL[st].Chain="";
            FL[st].Outchain="";
            FL[st].STACK=new Stack();
            for(int k=A.m_stack.size()-1;k>=0;k--)
              FL[st].STACK.push(A.m_stack.get(k));
             for(int k=cp;k<A.m_cnt;k++){
                 if(k==cp)FL[st].Chain+=("=->   "+A.m_lenta[k]+"   <-=\n      ");
                 else FL[st].Chain+=(A.m_lenta[k]);}
            FL[st].Function=FT[i].R;

             if((A.m_stack.lastElement().toString().compareTo(FT[i].OL)==0)&&(FT[i].L.compareTo("$")==0)) // *(S,$,#T#)=(S,$,#T#)
             {
               A.m_stack.pop();
               FL[st].Outchain.replace('#',' ')  ;
               FL[st-1].Outchain.replace('#',' ');
               FT[i].OL.replace('#',' ');
               FL[st].Outchain+=FL[st-1].Outchain.replace('#',' ')+FT[i].OL;
             }
              else
             if((FT[i].OL.compareTo("$")==0)&&(FA[i].m_list[0].compareTo("$")==0))  // Анализ ф-ции вида  [*]... = (S,$,$)
             {
             A.m_stack.pop();
             if(FA[i].type==0)cp++;
             FL[st].Outchain+=FL[st-1].Outchain.replace('#',' '); // Пишем цепочку на выходную ленту
             }
             else{
             FL[st].Outchain.replace('#',' ');
             FL[st-1].Outchain.replace('#',' ');
             FT[i].OL.replace('#',' ');
             if(FT[i].OL.compareTo("$")!=0)               // Анализ ф-ции вида ... = (S,T/N,#T#)
             FL[st].Outchain+=FL[st-1].Outchain.replace('#',' ')+FT[i].OL; // Пишем цепочку на выходную ленту
             else FL[st].Outchain+=FL[st-1].Outchain.replace('#',' ');
             if(FT[i].L.compareTo(FT[i].S)==0)            // Анализ ф-ции  вида (S,T,T)=(S,$)
             {
             FL[st].Outchain.replace('#',' ')  ; //?
             A.m_stack.pop();
             cp++;
             }else
             if(FA[i].m_list[0].charAt(0)=='$'){          // Анализ ф-ции вида [*](S,<>,<>)=(S,$)
             if(FA[i].type==0)cp++;                       // Сдвиг ленты
             A.m_stack.pop();                             // Вытолкнуть
             }
             else
             {
             FL[st].Outchain.replace('#',' ')  ; //?
             if(FA[i].type==0)cp++;                       // Сдвиг ленты
             A.m_stack.pop();                             // Удаляем из вершины стека
             for(int j=0;j<FA[i].cnt;j++)
              {
              A.m_stack.push(FA[i].m_list[j]);            // Помещаем цепочку в стек
              }
             }
             }
             use=1;                                       // Устанавливаем флаг
             if(A.m_stack.isEmpty()==true)                // Анализ на успех распознования
              {
              FL[0].steps=st;
              return 3;
              }
            }
        i++;
    }while(i<f);
     if(use==0){                                          // Найдена ли была функция перехода
       st++;
       FL[st]=new FLog();
       FL[st].Chain="";
       FL[st].Outchain="";
       FL[0].steps=st;
       FL[st].STACK=new Stack();
       for(int k=A.m_stack.size()-1;k>=0;k--)
                FL[st].STACK.push(A.m_stack.get(k));
       for(int k=cp;k<A.m_cnt;k++){
                 if(k==cp)FL[st].Chain+=("=->   "+A.m_lenta[k]+"   <-=\n      ");
                 else FL[st].Chain+=(A.m_lenta[k]);}
          return 2;
          }
   }while(true);

 }
};


