#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
*  Ovde smo prepravili prethodni zadatak da pored toga sto
*  preverava da li neki ulaz odgovara aritmetickom izrazu
*  program i racuna vrednos tog izraza
*  Svakom pravilu se dodaje odgovarajuca akcija,
*  i na taj nacin dobijemo shemu prevodjenja
*  pravila	skupovi izbora		akcije
*  E -> TE'	{ num , ( }		{E.v = T.v + E'.v}
*  E'->	+TE'	{ + }			{E'1.v = T.v + E'2.v}
*	|eps	{ ) , EOI }		{E'.v = 0}
*  T -> FT'	{ ( , num }		{T.v = F.v * T'.v}
*  T'-> *FT'	{ * }			{T'1.v = F.v * T'2.v}
*	|eps	{ + , ) , EOI }		{T'.v = 1}
*  F -> (E)	{ ( }			{F.v = E.v}
*	|num	{ num }			{F.v = num.v}
*  Svim simbolima u stablu smo dodali atribute, tj. vrednosti
*  Primetiti da smo ovde koristili desnu asovijativnost
*  zbog desno rekurzivnih pravila, sto nam nije problem,
*  jer imamo samo sabiranje i mnozenje.
*  Da smo imali i oduzimanje ili deljenje, morali bi da obezbedimo
*  levu asocijativnost iako imamo desno rekurzivna pravila
*  To bi uradili tako sto bi svaki neterminal imao dva atributa
*******************************/

/* 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 */

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

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

/* Za svaki neterminal deklarisemo po jednu funkciju
 * Prvo navodimo deklaracije, pa zatim definicije.
 * Nase funkcije ce sada vracati int, koji predstavlja vrednost
 * tj. atribut neterminala
 */

int E ();
int EP ();
int T ();
int TP ();
int F ();


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


/* Sami cemo isprogramirati leksicki alalizator,
 * a kasnije, u slozenijim primerima cemo koristiti
 * sistem lex
 * Moramo izmeniti i leksicki alalizator, tako da on kada naidje
 * na neki broj, vrati token NUM, ali mu postavi atribut
 * na njegovu vrednost koju cemo cuvati u promenljivoj yylval
 */
int yylval;

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))
    {
      yylval = ch - '0';
      while (isdigit (ch = getchar ()))
	yylval = yylval * 10 + ch - '0';
      /* 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;
}

/* definicija funkcije koja odgovara neterminalu E */
int
E ()
{
  /* Ako nam se na ulazu nadje terminal num ili ( , primenjujemo pravilo E->TE' */
  if (lookahead == NUM || lookahead == OZ)
    {
#ifdef ISPIS
      printf ("E->TE'\n");
#endif
      return T () + EP ();
    }
  /* Ako nam se na ulazu naslo nesto drugo, prijavljujemo gresku i neuspesno zavrsavamo prigram */
  else
    greska ("Sintaksna greska: Ocekivano je na ulazu num ili )");
  return -1;
}

/* definicija funkcije koja odgovara neterminalu EP */
int
EP ()
{
  /* Ako nam sa na ulazu pojavi PLUS, primenjujemo pravilo E'->+TE' */
  if (lookahead == PLUS)
    {
#ifdef ISPIS
      printf ("E'->+TE'\n");
#endif
      lookahead = yylex ();
      return T () + EP ();
    }
  /* Ako nam se na ulazu pojavi EOI, ili ) , primenjujemo pravilo E'->eps */
  else if (lookahead == EOI || lookahead == ZZ)
    {
#ifdef ISPIS
      printf ("E'->eps\n");
#endif
      return 0;
    }
  /* U slucaju bilo cega drugog, prekidamo program, uz odgovarajucu poruku */
  else
    greska ("Sintaksna greska: Ocekivano je na ulazu +, ) ili kraj ulaza");
  return -1;
}

/* definicija funkcije koja odgovara neterminalu T */
int
T ()
{
  /* Ako nam sa na ulazu pojavi ( ili num primenjujemo pravilo T->FT' */
  if (lookahead == OZ || lookahead == NUM)
    {
#ifdef ISPIS
      printf ("T->FT'\n");
#endif
      return F () * TP ();
    }
  else
    greska ("Sintaksna greska: Ocekivano je na ulazu ( ili num");
  return -1;
}

/* Definicija funkcije koja odgovara neterminalu T' */
int
TP ()
{
  /* Ako nam se na ulazu nasla ZVEZDA, primenjujemo pravilo T'->*FT' */
  if (lookahead == ZVEZDA)
    {
#ifdef ISPIS
      printf ("T'->*FT'\n");
#endif
      lookahead = yylex ();
      return F () * TP ();
    }
  /* Ako nam se na ulazu nadje +, ) ili kraj ulaza, primenjujemo pravilo T'->eps */
  else if (lookahead == PLUS || lookahead == ZZ || lookahead == EOI)
    {
#ifdef ISPIS
      printf ("T'->eps\n");
#endif
      return 1;
    }
  else
    greska
      ("Sintaksna greska: Ocekivano je na ulazu *, +, ), ili kraj ulaza");
  return -1;
}

/* Definicija funkcije koja odgovara neterminalu F */
int
F ()
{
  /* Ako ne na ulazu pojavila (, primenjujemo pravilo F->(E) */
  if (lookahead == OZ)
    {
      int temp;
#ifdef ISPIS
      printf ("F->(E)\n");
#endif
      lookahead = yylex ();
      temp = E ();
      /* proveravamo da li je sledeci karakter ), jer to mora da bude ako nije doslo do greske */
      if (lookahead == ZZ)
	lookahead = yylex ();
      else
	greska ("Ocekivana na ulazu zatvorena zagrada");
      return temp;
    }
  else if (lookahead == NUM)
    {
#ifdef ISPIS
      printf ("F->num\n");
#endif
      lookahead = yylex ();
      return yylval;
    }
  else
    greska ("Sintaksna greska: Ocekvano na ulazu ( ili num");
  return -1;
}


/* U main funkciji ucitavamo prvi karakter, i pozivamo funkciju koja ce nam
 * naci izvodjenje sa startni simbol S */
int
main ()
{
  int result;
  lookahead = yylex ();
  result = E ();
  if (lookahead != EOI)
    greska ("Sintaksna greska: Visak tokena na ulazu");
  printf ("Vrednost izraza je %d\n", result);
  return 0;
}