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

/*******************************
*  Gramatika je:
*  E -> E+T
*	|T
*  T -> T*F
*	|F
*  F => (E)
*	|num
*  Moramo se obavezno osloboditi leve rekurzije
*  pravila	skupovi izbora
*  E -> TE'	{ num , ( }
*  E'->	+TE'	{ + }
*	|eps	{ ) , EOI }
*  T -> FT'	{ ( , num }
*  T'-> *FT'	{ * }
*	|eps	{ + , ) , EOI }
*  F -> (E)	{ ( }
*	|num	{ num }
*  Uradicemo sintaksnu analizu odozgo nadole, simulaciom potisnog automata
*******************************/

/* Deklarisemo tokene koji nam se javljaju u gramatici */
#define NUM 1
#define PLUS 2
#define ZVEZDA 3
#define OZ 4			/* otvorena zagrada */
#define ZZ 5			/* zatvorena zagrada */
#define EOI 0			/* end of inpit */
/* Pored tokena na steku se mogu naci i nerminal, tako da i njih kodiramo brojevima */
#define E 6
#define EP 7
#define T 8
#define TP 9
#define F 10

/* uvodimo sledeci define, samo ako hocemo da nam program ispise izvodjenje */
#define ISPIS 1

/* Spoljasnja promenljiva koja ce predstvljati preduvidni token */
int lookahead;

/* Funkcija za obradu greske */
int
greska (char *poruka)
{
  fprintf (stderr, "%s\n", poruka);
  exit (EXIT_FAILURE);
  return -1;
}


/* Sami cemo isprogramirati leksicki alalizator,
 * a kasnije, u slozenijim primerima cemo koristiti
 * sistem lex
 */
int
yylex ()
{
  int ch = getchar ();
  switch (ch)
    {
    case '+':
      return PLUS;
    case '*':
      return ZVEZDA;
    case '(':
      return OZ;
    case ')':
      return ZZ;
    case '\n':
    case EOF:
      return EOI;
    }
  /* Ako je procitani karakter cifra, citamo sve naredne karaktere,
   * do pojave necega sto nije cifra, u cilju da procitano broj
   */
  if (isdigit (ch))
    {
      while (isdigit (ch = getchar ()))
	;
      /* Ono poslednje sto smo procitali, i sto nije cifra, vracamo na ulaz */
      ungetc (ch, stdin);
      return NUM;
    }
  /* Ako se na ulazu nije pojavilo nista od ovoga, onda prekidamo program,
   * i ispisujemo propratnu poruku
   */
  greska ("Leksicka greska: Nepoznat ulaz");
  return -1;
}

/* Makro za ucitavanje novog preduvidnog tokena u lookahead */
#define advance()   ( lookahead = yylex() )

/* Makro za proveravanje da li je preduvidni token jednak necemu */
#define match(x)    (lookahead == (x))

/* Maksimalna velicina steka potisnog automata,
 * stek cemo predstavljati pomocu statickog niza
 * i pokazivaca na prvo slobodno mesto u nizu */
#define MAX_STACK 256
#define STACK(type, array)	type array[MAX_STACK];\
 				int sp_##array = 0

/* Makroi koji barataju sa stekom */
#define empty(array)	(sp_##array<=0)
#define full(array)	(sp_##array>=MAX_STACK)
#define top(array)	(array[sp_##array - 1])
#define pop(array)	(empty(array)?greska("Stek je prazan"):(array[--sp_##array]))
#define push(array, x)	(full(array)?greska("Stek je pun"):(array[sp_##array++]=(x)))


int
main ()
{
  /* Stek potisnog automata */
  STACK (int, parse_stack);

  /* Ucitavamo prvi token */
  advance ();

  /* Na stek stavljamo aksiomu gramatike, tj. startni simbol */
  push (parse_stack, E);

  /* Sve dok je stek automata neprazan */
  while (!empty (parse_stack))
    {
      /* gledamo sta je na vrhu steka */
      switch (top (parse_stack))
	{
	  /* ako je na vrhu steka E */
	case E:
	  /* Proveravamo da li je preduvidni token jedan NUM ili ( */
	  if (match (NUM) || match (OZ))
	    {
	      /* ako jeste preduzimamo svodjenje E -> T E'
	       * tj. sa steka skidamo E, a postavljamo T i E',
	       * ali u ubrnutom poretku. Zasto?
	       */
	      pop (parse_stack);
	      push (parse_stack, EP);
	      push (parse_stack, T);
	      /* Ako nam treba najlevlje izvodjenje, ispisujemo ga */
#ifdef ISPIS
	      printf ("E->TE'\n");
#endif
	    }
	  /* u suprotom ispisujemo gresku */
	  else
	    greska ("Sintaksna greska: Na ulazu ocekujemo NUM ili (");
	  break;
	  /* ako je na vrhu steka E' */
	case EP:
	  if (match (PLUS))
	    {
	      /* sa steka skidamo E'
	       * a na stek postavljamo +TE' u obrnutom poretku
	       */
	      pop (parse_stack);
	      push (parse_stack, EP);
	      push (parse_stack, T);
	      push (parse_stack, PLUS);
#ifdef ISPIS
	      printf ("E'->+TE'\n");
#endif
	    }
	  else if (match (ZZ) || match (EOI))
	    {
	      /* primenjujemo svodjenje E'->eps
	       * dakle samo sa steka skidamo E'
	       */
	      pop (parse_stack);
#ifdef ISPIS
	      printf ("E'->eps\n");
#endif
	    }
	  else
	    greska
	      ("Sintaksna greska: Na ulazu je ocekivamo + ili ) ili kraj ulaza");
	  break;
	case T:
	  if (match (NUM) || match (OZ))
	    {
	      pop (parse_stack);
	      push (parse_stack, TP);
	      push (parse_stack, F);
#ifdef ISPIS
	      printf ("T->FT'\n");
#endif
	    }
	  else
	    greska ("Sintaksna greska: Na ulazu ocekujemo NUM ili (");
	  break;
	case TP:
	  if (match (ZVEZDA))
	    {
	      pop (parse_stack);
	      push (parse_stack, TP);
	      push (parse_stack, F);
	      push (parse_stack, ZVEZDA);
#ifdef ISPIS
	      printf ("T'->*FT'\n");
#endif
	    }
	  else if (match (PLUS) || match (ZZ) || match (EOI))
	    {
	      pop (parse_stack);
#ifdef ISPIS
	      printf ("T'->eps\n");
#endif
	    }
	  else
	    greska
	      ("Sintaksna greska: Ocekivano je na ulazu *, +, ) ili kraj ulaza");
	  break;
	case F:
	  if (match (OZ))
	    {
	      pop (parse_stack);
	      push (parse_stack, ZZ);
	      push (parse_stack, E);
	      push (parse_stack, OZ);
#ifdef ISPIS
	      printf ("F->(E)\n");
#endif
	    }
	  else if (match (NUM))
	    {
	      pop (parse_stack);
	      push (parse_stack, NUM);
#ifdef ISPIS
	      printf ("F->num\n");
#endif
	    }
	  else
	    greska ("Sintaksna greska: Ocekivano je na ulazu ( ili num");
	  break;
	default:
	  /* ako se na vrhu steka nadje nesto sto nije neterminal,
	   * to onda mora da bude terminal(token)
	   * koji mora da se poklapa sa onim sto je preduvidni token
	   */
	  if (match (top (parse_stack)))
	    {
	      /* Skidamo token sa steka, i ucitavamo sledeci token */
	      pop (parse_stack);
	      advance ();
	    }
	  /* ako nam se ne poklapaju vrh steka i preduvidni token, ispisujemo gresku */
	  else
	    {
	      switch (top (parse_stack))
		{
		case NUM:
		  greska ("Sintaksna greska: Ocekivano je na ulazu NUM\n");
		case PLUS:
		  greska ("Sintaksna greska: Ocekivano je na ulazu +");
		case ZVEZDA:
		  greska ("Sintaksna greska: Ocekivano je na ulazu *");
		case OZ:
		  greska ("Sintaksna greska: Ocekivano je na ulazu (");
		case ZZ:
		  greska ("Sintaksna greska: Ocekivano je na ulazu )");
		case EOI:
		  greska ("Sintaksna greska: Ocekivano je kraj ulaza");
		}
	    }
	  break;
	}
    }

  if (!match (EOI))
    greska ("Sintaksna greska: Visak simbola na ulazu");

  return 0;
}