// ANALIZATOR SKLADNIOWY Z PIERWSZENSTWEM
//
// Wczytuje ze standardowego wejscia ciag znakow oznaczajacy wyrazenie
// arytmetyczne.
// Drukuje na standardowe wyjscie drzewo rozbioru (lub komunikat
// bledu).

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define  dlug_wyr 50
#define  max_il_synow  3
#define  max_wys_stosu 100
#define  max_szer_druku  100
#define  max_wys_druku  40

typedef enum { FALSE = 0, TRUE = 1 }  Boolean;

typedef enum { wyr   = 0,
               v_wyr = 1,
               skl   = 2,
               pl    = 3,
               el    = 4,
               lnaw  = 5,
               pnaw  = 6,
               pusty = 7 }  Symbol;

typedef enum { nieokr   = 0,
               mniejsze = 1,
               rowne    = 2,
               wieksze  = 3 }  Pierw;
     
typedef enum { stan_pocz   = 0,
               stan_1      = 1,
               stan_2      = 2,
               stan_3      = 3,
               stan_V_1    = 4,
               stan_V_2    = 5,
               stan_W      = 6,
               stan_S_1    = 7,
               stan_S_2    = 8,
               stan_nieokr = 9 }  Stan;

struct dr { Boolean czyterm;
            union { Symbol lk;  // terminal, o ile  czyterm = TRUE
                    struct      // o ile  czyterm = FALSE
                      { Symbol ntm; // nieterminal
                        int il_syn;
                        struct dr* syn[max_il_synow];
                      } s;
                  } u;
          };
typedef struct dr  drzewo;

char leksyk[dlug_wyr];  int mce_leks;  Symbol leks;
 
//------------------------------------------------------
// POMOCNICZE:


void  blad (char komunikat[], char zn1, char zn2) {
  int i;
  for (i=1; i<mce_leks-1; i++)  printf (" ");
  printf ("^\n\n   !!! %s %c %c  !!!\n", komunikat, zn1, zn2);
  exit(1);
}


drzewo  drzewo_z_terminalu (Symbol t) {
    // z terminalu  t  robi drzewo zawierajace tylko  t
  drzewo drz;
  drz.czyterm = TRUE; drz.u.lk = t;
  return drz;
}


Symbol  symb_drzewa (drzewo drz) {
    // wybiera symbol stojacy w wierzcholku drzewa
  if (drz.czyterm)  return drz.u.lk;
  else  return drz.u.s.ntm;
}


char  znak_z_symb (Symbol sb) {
    // zamienia symbol  sb  na znak gotowy do druku
  switch (sb) {
    case wyr   : return 'W'; break;
    case v_wyr : return 'V'; break;
    case skl   : return 'S'; break;
    case pl    : return '+'; break;
    case el    : return 'L'; break;
    case lnaw  : return '('; break;
    case pnaw  : return ')'; break;
    case pusty : return '$'; break;
  }
}

//------------------------------------------------------
// OBSLUGA STOSU:


drzewo  stos [max_wys_stosu];
int  wys_stosu;


void  nowy_stos(void) {
  stos[0] = drzewo_z_terminalu (pusty);  wys_stosu = 1;
}


void  na_stos (drzewo drz) {
  if (wys_stosu == max_wys_stosu)
    blad ("Przekroczenie stosu", '\0', '\0');
  else {
    stos[wys_stosu] = drz;  wys_stosu++;
  }
}


drzewo  ze_stosu (void) {
  if (wys_stosu == 0)  blad ("Pusty stos", '\0', '\0');
  else {
    wys_stosu--;  return stos[wys_stosu];
  }
}


Symbol  szczyt_stosu (void) {
    // nie zmienia stanu stosu, tylko sprawdza,
    // jaki symbol jest na jego szczycie
  if (wys_stosu == 0)  return pusty;
  else  return symb_drzewa (stos[wys_stosu-1]);
}

//------------------------------------------------------
// ANALIZA LEKSYKALNA:


void  nast_leks (void) {
  if (mce_leks == strlen(leksyk))  leks = pusty;
  else {
    if (leksyk [mce_leks] == '+')  leks = pl;  else
    if (leksyk [mce_leks] == 'L')  leks = el;  else
    if (leksyk [mce_leks] == '(')  leks = lnaw;  else
    if (leksyk [mce_leks] == ')')  leks = pnaw;  else
    if (leksyk [mce_leks] == ' ')  leks = pusty;
    else  blad ("zly znak: ", leksyk [mce_leks], '\0');
    mce_leks++;
  }
}

//------------------------------------------------------
// REDUKCJA:


Pierw pierwszenstwo [8][8];
Stan  automat [5][8];


Symbol  nterm_ze_stanu (Stan st) {
    // ustala do jakiego nieterminalu redukuje sie podstawa zaleznie
    // od ostatecznego stanu automatu rozpoznajacego stos
  switch (st) {
      case stan_pocz:
      case stan_1:
      case stan_2:
      case stan_3:
      case stan_nieokr:  blad ("Cos zle na stosie", '\0', '\0'); break;
      case stan_V_1:
      case stan_V_2:  return v_wyr; break;
      case stan_W:  return wyr; break;
      case stan_S_1:
      case stan_S_2:  return skl; break;
  }
}


void  redukcja (void) {
  Stan st = stan_pocz;
  drzewo drz;  int i;
  drz.czyterm = FALSE;
  drz.u.s.il_syn = 0;
  do {
    for (i=drz.u.s.il_syn; i>0; i--)
      drz.u.s.syn[i] = drz.u.s.syn[i-1];
      (drz.u.s.il_syn)++;
      drz.u.s.syn[0] = (drzewo*)malloc(sizeof(drzewo));
      *(drz.u.s.syn[0]) = ze_stosu();
      st = automat [st][symb_drzewa(*(drz.u.s.syn[0]))];
  } while (
    pierwszenstwo[szczyt_stosu()][symb_drzewa(*(drz.u.s.syn[0]))] == rowne
  );
  drz.u.s.ntm = nterm_ze_stanu (st);
  na_stos (drz);
}

//------------------------------------------------------
// INICJALIZACJE:


void  init_pierw (void) {
  Symbol  sb1, sb2;
  for (sb1=wyr; sb1<=pusty; sb1++)
    for (sb2=wyr; sb2<=pusty; sb2++)
      pierwszenstwo [sb1][sb2] = nieokr;
  for (sb1=wyr; sb1<=pusty; sb1++)  pierwszenstwo [sb1][pusty] = wieksze;
  for (sb2=wyr; sb2<=pnaw; sb2++)  pierwszenstwo [pusty][sb2] = mniejsze;
  pierwszenstwo [wyr][pnaw] = rowne;
  pierwszenstwo [skl][pl] = wieksze;
  pierwszenstwo [skl][pnaw] = wieksze;
  pierwszenstwo [pl][skl] = rowne;
  pierwszenstwo [pl][el] = mniejsze;
  pierwszenstwo [pl][lnaw] = mniejsze;
  pierwszenstwo [el][pl] = wieksze;
  pierwszenstwo [el][pnaw] = wieksze;
  pierwszenstwo [lnaw][wyr] = rowne;
  pierwszenstwo [lnaw][skl] = mniejsze;
  pierwszenstwo [lnaw][el] = mniejsze;
  pierwszenstwo [lnaw][lnaw] = mniejsze;
  pierwszenstwo [lnaw][v_wyr] = mniejsze;
  pierwszenstwo [pnaw][pl] = wieksze;
  pierwszenstwo [pnaw][pnaw] = wieksze;
  pierwszenstwo [v_wyr][pl] = rowne;
  pierwszenstwo [v_wyr][pnaw] = wieksze;
}


void  init_aut (void) {
  Stan st; Symbol sb;
  for (st=stan_pocz; st<=stan_V_1; st++)
    for (sb=wyr; sb<=pusty; sb++)
      automat [st][sb] = stan_nieokr;
  automat [stan_pocz][v_wyr] = stan_W;
  automat [stan_pocz][skl] = stan_V_1;
  automat [stan_pocz][el] = stan_S_1;
  automat [stan_pocz][pnaw] = stan_1;
  automat [stan_1][wyr] = stan_2;
  automat [stan_2][lnaw] = stan_S_2;
  automat [stan_3][v_wyr] = stan_V_2;
  automat [stan_V_1][pl] = stan_3;
}


void  init_leks (void) {
  scanf ("%s", leksyk);  mce_leks = 0;
}


void  inicjalizacje (void) {
  init_pierw();  init_aut();  nowy_stos();  init_leks();  nast_leks();
}

//------------------------------------------------------
// DRUKOWANIE DRZEWA:


char  druk [max_szer_druku][max_wys_druku];


void  dr_drz (drzewo drz, int* szer, int* wys) {
  int  szer_syna[max_il_synow], wys_syna[max_il_synow];
  int  max_wys, i,j;
  if (drz.czyterm) {
    *szer=*szer+3; *wys=1;
    druk[*szer-1][*wys-1] = znak_z_symb (drz.u.lk);
  }  else {   // Drzewo nieterminalowe:
    max_wys = 0;
    for (i=0; i<drz.u.s.il_syn; i++) {
      dr_drz (*drz.u.s.syn[i], szer, &wys_syna[i]);
      szer_syna[i] = *szer;
      if (max_wys < wys_syna[i])  max_wys = wys_syna[i];
    }
    druk[*szer-1][max_wys+1] = znak_z_symb (drz.u.s.ntm);
    if (drz.u.s.il_syn > 0) {
      for (i=0; i<drz.u.s.il_syn; i++)
        for (j=wys_syna[i]; j<max_wys+1; j++)
          druk[szer_syna[i]-1][j] = '|';
      for (i=szer_syna[0]; i<*szer-1; i++)  druk[i][max_wys+1] = '-';
      for (i=0; i<drz.u.s.il_syn-1; i++)
        druk[szer_syna[i]-1][max_wys+1] = ',';
    }
    *wys = max_wys+2;
  }
}


void  drukuj_drzewo (drzewo drz) {
  int szer,wys,i,j;
  for (i=0; i<max_szer_druku; i++)
    for (j=0; j<max_wys_druku; j++)
      druk[i][j] = ' ';
  szer=0;
  dr_drz (drz, &szer, &wys);
  for (j=wys-1; j>=0; j--) {
    for (i=0; i<szer; i++)  printf("%c",druk[i][j]);
    printf("\n");
  }
  printf("\n");
}

//------------------------------------------------------


int main(void) {
  drzewo drz;
  inicjalizacje ();
  do {
    switch (pierwszenstwo [szczyt_stosu()][leks]) {
      case nieokr:
        blad ("Te symbole nie moga wystepowac obok siebie: ",
              znak_z_symb (szczyt_stosu()), znak_z_symb (leks));
        break;
      case mniejsze:
      case rowne:
        drz = drzewo_z_terminalu (leks); na_stos (drz); nast_leks();
        break;
      case wieksze: redukcja(); break;
    }
  } while (wys_stosu != 2 || szczyt_stosu() != wyr || leks != pusty);
  drz = ze_stosu (); drukuj_drzewo (drz);

  return 0;
}

//------------------------------------------------------