/*
 * LL(1) Skeleton Parser
 * -- fleshed out from Lecture 10, COMP 412
 *
 */

#include <stdio.h>
#include <libc.h>
#define INVALID -1

#include "LL1Table.h"

int tracing = 0;

int NextWord();  /* Scanner that reads integer token types from stdin */
void * malloc();

char buffer[1000];

/* 
 * A quick and dirty stack abstraction for use in the skeleton parser
 *
 */

int *Stack;
int StackSize = 1000;
int StackTop = -1;

int pop()
{
  StackTop--;
  if (StackTop < 0)
  {
    fprintf(stderr,"Stack underflow -- parser quits.\n");
    exit(-1);
  }
  else return Stack[StackTop];
} 

int push(int data)
{
  if (StackTop == -1)
  {
    Stack = (int *) malloc(StackSize * sizeof(int));
    StackTop = 0;
  }
  if (StackTop < StackSize)
  {
    Stack[StackTop++] = data;
  }
  if (StackTop == StackSize)
  { 
    int *NewStack;
    int NewSize, i;
    NewSize  = StackSize + StackSize / 2;
    NewStack = (int *) malloc(StackSize * sizeof(int));
    for (i=0;i<StackSize;i++)
      NewStack[i] = Stack[i];
    StackSize = NewSize;
    free(Stack);
    Stack = NewStack;
  }
}

int TopOfStack()
{
  int TopElement;

  TopElement = StackTop - 1;
  if (TopElement < 0)
    fprintf(stderr,"TOS underflows the stack.\n");

  return Stack[TopElement];
}


void trace(char *s)
{
  if (tracing)
    fprintf(stderr,"%s.\n",s);
}

void PrintProd(int p)
{
  int i, RHSLength;

  fprintf(stderr,"  %d. %s -> ",p,SymbolNames[LHS[p]]);
  RHSLength = RHS[p][0];

  for (i=1;i<=RHSLength;i++)
  {
    fprintf(stderr,"%s ",SymbolNames[RHS[p][i]]);
  }
  fprintf(stderr,"\n");
}

int Skeleton()
{
  int word, TOS, prod, i, entry;

  word = NextWord();
  push(ENDOFFILE);
  push(START);
  TOS = TopOfStack();

  sprintf(buffer,"Initialization: TOS = %s, word = %s.\n",
	  SymbolNames[TOS],SymbolNames[word]);
  trace(buffer);

  while(1)
  {
    if (TOS == ENDOFFILE && word == ENDOFFILE)
    {
      trace("Stack is empty and Word is ENDOFFILE");
      trace("Parse succeeds");
      return 1;
    }       
    else if (TOS >= NUM_NONTERMINALS)
    {
      if (TOS == word)
      {
        sprintf(buffer,"TOS '%s' matches current input word '%s'",
		SymbolNames[TOS],SymbolNames[word]);
        trace(buffer);
        entry = pop();
        sprintf(buffer,"  - popped '%s'",SymbolNames[entry]);
        trace(buffer);
        word = NextWord();
        sprintf(buffer,"  - advanced input and found '%s'",SymbolNames[word]);
        trace(buffer);
      }
      else /* a syntax error */
      {
        fprintf(stderr,"\nParser was looking for '%s' and found '%s'.\n",
                SymbolNames[TOS],SymbolNames[word]);
        fprintf(stderr,"Syntax error.\nParse terminates.\n\n");
        return -1;
      }
    }
    else 
    {
      prod = LL1Table[TOS][word-NUM_NONTERMINALS];
      sprintf(buffer,"Trying to expand %s with input word '%s'",
              SymbolNames[TOS],SymbolNames[word]);
      trace(buffer);

      if (0 <= prod && prod < NUM_PRODUCTIONS)
      {
	if (tracing) 
	  PrintProd(prod);
	
	/* remove LHS from stack */
        entry = pop();  
        sprintf(buffer,"  - popped '%s'",SymbolNames[entry]);
	trace(buffer);

        /* push RHS in right to left order */
        for (i=RHS[prod][0];i>0;i--)
	{
          entry = RHS[prod][i];
          if (entry < ENDOFFILE)
	  { 
            sprintf(buffer,"  - pushed '%s'",SymbolNames[entry]);
            trace(buffer);
            push(RHS[prod][i]);
	  }
        }
      }
      else 
      {
	fprintf(stderr,"Syntax error expanding '%s'.\n",SymbolNames[TOS]);
	return -1;
      }
    }
    TOS = TopOfStack();
  }
}


/* and a pseudo-scanner */

int NumWords  = -1;
int IndexIntoWords = 0;
int NumEndFiles = 0;

int NextWord()
{
  int val, i;

  if (NumWords < 0)
  {
    i = 0;
    while(Words[i] != ENDOFFILE)
      i++;

    NumWords = i+1;
  }

  val = Words[IndexIntoWords++];
  if (IndexIntoWords == NumWords)
  {
    IndexIntoWords --;
    NumEndFiles++;
  }

  if (NumEndFiles > 10)
  {
    fprintf(stderr,"NextWord invoked more than 1,000 times at end of file.\n");
    exit(-1);
  }
  return val;
}

/* 
 * The main routine 
 *
 */

int main(int argc, char *argv[])
{
  int i, j;
  int productions = 0;
  char *arg;
  
  /* parse the command-line arguments */
  for (i=1; i<argc; i++)
  {
    arg = argv[i];
    if (*arg == '-')
    {
      arg++;
      while(*arg != '\0')
      {
	switch(*arg)
	{
	case 't':
	  tracing++;
	  break;
        case 'p':
	  productions++;
	  break;

	default:
	  fprintf(stderr,"Bad command-line argument '%c'.\n",*arg);
          fprintf(stderr,"Valid options are:\n");
	  fprintf(stderr,"\tp - print production table\n");
	  fprintf(stderr,"\tt - trace parse\n");
          return -1;
	  break;
	}
	arg++;
      }
    }
  }


  if (productions)
  {
    fprintf(stderr,"Productions in the grammar:\n\n");
    for (i=0; i<NUM_PRODUCTIONS; i++)
    {
      PrintProd(i);
    }
    fprintf(stderr,"\n");
  }

  i = Skeleton();

  if (!tracing)
  {
    if (i >= 0)
      fprintf(stderr,"Parse was successful.\n");
    else
      fprintf(stderr,"\nParse failed.\n");
  }
}