#include "lex.yy.c"

#define LINE 1
#define EXPR 2
#define ARGT 3
#define REST 4
#define BASE 5
#define XPNT 6
#define ACC 1000

#define EMPTYSTACK 1
#define INVALIDRULE 2
#define PARSEERROR 3

int ACTION[18][10] = {
   /* ID  STR  $ID  NUM    =    +    ^    (    )   \n */
   {   2,   0,   0,   0,   0,   0,   0,   0,   0,   0 } ,  /*  0 */
   {   0,   0,   0,   0,   0,   0,   0,   0,   0, ACC } ,  /*  1 */
   {   0,   0,   0,   0,   5,   0,   0,   0,   0,   0 } ,  /*  2 */
   {   0,   0,   0,   0,   0,   0,   0,   0,  -2,  -2 } ,  /*  3 */
   {   0,   0,   0,   0,   0,   0,   0,   0,   0,  -1 } ,  /*  4 */
   {   0,  11,  12,   0,   0,   0,   0,  10,   0,   0 } ,  /*  5 */
   {   0,   0,   0,   0,   0,   7,   0,   0,  -3,  -3 } ,  /*  6 */
   {   0,  11,  12,   0,   0,   0,   0,  10,   0,   0 } ,  /*  7 */
   {   0,   0,   0,   0,   0,   0,   0,   0,   9,   0 } ,  /*  8 */
   {   0,   0,   0,   0,   0, -10, -10,   0, -10, -10 } ,  /*  9 */
   {   0,  11,  12,   0,   0,   0,   0,  10,   0,   0 } ,  /* 10 */
   {   0,   0,   0,   0,   0,  -8,  -8,   0,  -8,  -8 } ,  /* 11 */
   {   0,   0,   0,   0,   0,  -9,  -9,   0,  -9,  -9 } ,  /* 12 */
   {   0,   0,   0,   0,   0,   0,   0,   0,  -4,  -4 } ,  /* 13 */
   {   0,   0,   0,   0,   0,  -5,   0,   0,  -5,  -5 } ,  /* 14 */
   {   0,   0,   0,   0,   0,  -6,  16,   0,  -6,  -6 } ,  /* 15 */
   {   0,   0,   0,  17,   0,   0,   0,   0,   0,   0 } ,  /* 16 */
   {   0,   0,   0,   0,   0,  -7,   0,   0,  -7,  -7 }    /* 17 */
};

int GOTO[18][7] = {
   /*  L'   L    E    A    R    B    X */
   {   0,   1,   0,   0,   0,   0,   0 } ,  /*  0 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /*  1 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /*  2 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /*  3 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /*  4 */
   {   0,   0,   4,   6,   0,  15,   0 } ,  /*  5 */
   {   0,   0,   0,   0,   3,   0,   0 } ,  /*  6 */
   {   0,   0,  13,   6,   0,  15,   0 } ,  /*  7 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /*  8 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /*  9 */
   {   0,   0,   8,   6,   0,  15,   0 } ,  /* 10 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /* 11 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /* 12 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /* 13 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /* 14 */
   {   0,   0,   0,   0,   0,   0,  14 } ,  /* 15 */
   {   0,   0,   0,   0,   0,   0,   0 } ,  /* 16 */
   {   0,   0,   0,   0,   0,   0,   0 }    /* 17 */
};

union _attr {
   int val;
   char *str;
};

typedef struct _node {
   int state;
   union _attr attr;
   struct _node *next;
} node;

typedef node *SLRstack;

typedef struct {
   char *name;
   char *value;
} stpair;
stpair ST[4096];
int nstentry = 0;

int token;
int stidx;

int STindex ( char *name )
{
   int i;

   for (i=0; i<nstentry; ++i) {
      if (!strcmp(name,ST[i].name)) return i;
   }
   return -1;
}

char *STload ( char *name )
{
   int i;

   i = STindex(name);
   if (i < 0) return strdup("");
   return strdup(ST[i].value);
}

void STstore ( char *name, char *value )
{
   stidx = STindex(name);
   if (stidx < 0) {
      stidx = nstentry;
      ++nstentry;
      ST[stidx].name = strdup(name);
   } else {
      free(ST[stidx].value);
   }
   ST[stidx].value = strdup(value);
}

SLRstack init ( )
{
   node *p;

   printf("    0");
   p = (node *)malloc(sizeof(node));
   p -> state = 0;
   p -> next = NULL;
   return p;
}

SLRstack push ( SLRstack S, int newstate, union _attr A )
{
   node *p;

   p = (node *)malloc(sizeof(node));
   p -> state = newstate;
   p -> attr = A;
   p -> next = S;
   printf(" -> %d", p -> state);
   return p;
}

SLRstack pop ( SLRstack S )
{
   node *p;

   if (S == NULL) {
      fprintf(stderr, "*** Pop from an empty stack\n");
      exit(EMPTYSTACK);
   }
   p = S -> next;
   free(S);
   printf(" <- %d", p -> state);
   return p;
}

SLRstack shift ( SLRstack S , int newstate )
{
   union _attr A;

   printf(" [s%d]", newstate);
   if ( (token == ID) || (token == STR) ) A.str = strdup(yytext);
   else if (token == REF) A.str = STload(yytext + 1);
   else if (token == NUM) A.val = atoi(yytext);
   token = yylex();
   return push(S,newstate,A);
}

char *strplus ( char *s1, char *s2 )
{
   char *s;
   int l1, l2;

   l1 = strlen(s1); l2 = strlen(s2);
   s = (char *)malloc((l1 + l2 + 1) * sizeof(char));
   strcpy(s, s1);
   strcpy(s + l1, s2);
   return s;
}

char *strexp ( char *s, int r )
{
   char *t, *p;
   int l, i;

   l = strlen(s);
   p = t = (char *)malloc((l * r + 1) * sizeof(char));
   t[0] = '\0';
   for (i=0; i<r; ++i) p += sprintf(p,"%s",s);
   return t;
}

SLRstack reduce ( SLRstack S , int rule )
{
   union _attr A;
   int newstate;
   int head;

   printf(" [r%d]", rule);
   switch (rule) {
      case 1: /* L -> ID = E */
         STstore((S->next->next->attr).str,(S->attr).str);
         free((S -> attr).str);
         free((S -> next -> next -> attr).str);
         S = pop(S); S = pop(S); S = pop(S);
         head = LINE;
         break;
      case 2: /* E -> A R */
         A.str = strplus((S->next->attr).str,(S->attr).str);
         free((S->attr).str);
         free((S->next->attr).str);
         S = pop(S); S = pop(S);
         head = EXPR;
         break;
      case 3: /* R -> e */
         A.str = strdup("");
         head = REST;
         break;
      case 4: /* R -> + E */
         A.str = (S -> attr).str;
         S = pop(S); S = pop(S);
         head = REST;
         break;
      case 5: /* A -> B X */
         A.str = strexp((S->next->attr).str,(S->attr).val);
         free((S->next->attr).str);
         S = pop(S); S = pop(S);
         head = ARGT;
         break;
      case 6: /* X -> e */
         A.val = 1;
         head = XPNT;
         break;
      case 7: /* X -> ^ NUM */
         A.val = (S->attr).val;
         S = pop(S); S = pop(S);
         head = XPNT;
         break;
      case 8: /* B -> STR */
         A.str = (S->attr).str;
         S = pop(S);
         head = BASE;
         break;
      case 9: /* B -> $ID */
         A.str = (S->attr).str;
         S = pop(S);
         head = BASE;
         break;
      case 10: /* B -> ( E ) */
         A.str = (S->next->attr).str;
         S = pop(S); S = pop(S); S = pop(S);
         head = BASE;
         break;
      default: fprintf(stderr, "*** Invalid rule for reduction\n"); exit(INVALIDRULE);
   }
   newstate = GOTO[S->state][head];
   if (newstate == 0) {
      fprintf(stderr,"*** Error: Invalid GOTO\n");
      exit(PARSEERROR);
   }
   S = push(S,newstate,A);
   printf(" \n     ");
   return S;
}

void parse ( )
{
   SLRstack S;
   int state, action;

   printf("+++ Going to parse next statement\n");
   S = init();
   while (1) {
      if (S == NULL) {
         fprintf(stderr, "*** Top requested from empty stack\n");
         exit(EMPTYSTACK);
      }
      state = S -> state;
      action = ACTION[state][token - 1];
      if (action == ACC) { printf(" -> ACCEPT\n"); return; }
      if (action == 0) {
         fprintf(stderr, "*** Parse error\n");
         exit(PARSEERROR);
      }
      if (action > 0) S = shift(S,action);
      else S = reduce(S,-action);
   }
}

int main ( int argc, char *argv[] )
{
   if (argc > 1) yyin = (FILE *)fopen(argv[1], "r");
   while (1) {
      token = yylex();
      if (token == 0) break;
      if (token == EOL) continue;
      parse();
      printf("+++ Stored %s = %s\n\n", ST[stidx].name, ST[stidx].value);
      if (token != EOL) {
         fprintf(stderr, "*** Parse error: New line expected\n");
         exit(PARSEERROR);
      }
   }
   fclose(yyin);
   exit(0);
}