////////////////////////////////////////////////////////////////////////////////
//
//  Simple Left to right Rightmost derivation syntax analyzer
//  Marcelo Johann - PUCRS - Uruguaiana 2002
//
////////////////////////////////////////////////////////////////////////////////

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

// Here we must define terminal and non terminal symbols, limited to 256.
// Terminals first, and FIRST_NON indicates the first non terminal char.
// MAX_TOKEN can be used to reduce table size, but limited to 256 (see below).


#define TER_ID		0
#define TER_OR		1
#define TER_AND		2
#define TER_ABRE	3
#define TER_FECHA	4
#define TER_FIM		5
#define FIRST_NON	6
#define NON_E		6
#define NON_T		7
#define NON_F		8

#define MAX_TOKEN	9
#define MAX_STATE	12
#define MAX_PRODUCTION	6

/// Standard Actions for the parser

#define ACTION_PUSH	1024
#define ACTION_REDUCE	2048
#define ACTION_ACCEPT	4096

// These are general defines for all parsers

#define FALSE		0
#define	TRUE		1
#define TERMINAL(a)	( a < FIRST_NON ? 1 : 0 )
#define MAX_STACK	40

// This is the Parser Table, again for all parsers
// Each entry of Action contains one action: push, reduce, accept or error (empty).
// Each entry of Transition contains the number of the action for terminals or the
// next state (transition part of the table) for non terminals.

int Action[MAX_STATE][FIRST_NON] = {
  {ACTION_PUSH,0,0,ACTION_PUSH,0,0},
  {0,ACTION_PUSH,0,0,0,ACTION_ACCEPT},
  {0,ACTION_REDUCE,ACTION_PUSH,0,ACTION_REDUCE,ACTION_REDUCE},
  {0,ACTION_REDUCE,ACTION_REDUCE,0,ACTION_REDUCE,ACTION_REDUCE},
  {ACTION_PUSH,0,0,ACTION_PUSH,0,0},
  {0,ACTION_REDUCE,ACTION_REDUCE,0,ACTION_REDUCE,ACTION_REDUCE},
  {ACTION_PUSH,0,0,ACTION_PUSH,0,0},
  {ACTION_PUSH,0,0,ACTION_PUSH,0,0},
  {0,ACTION_PUSH,0,0,ACTION_PUSH,0},
  {0,ACTION_REDUCE,ACTION_PUSH,0,ACTION_REDUCE,ACTION_REDUCE},
  {0,ACTION_REDUCE,ACTION_REDUCE,0,ACTION_REDUCE,ACTION_REDUCE},
  {0,ACTION_REDUCE,ACTION_REDUCE,0,ACTION_REDUCE,ACTION_REDUCE}
  };

int Transition[MAX_STATE][MAX_TOKEN] = {
  {5,0,0,4,0,0,		1,2,3},
  {0,6,0,0,0,0,		0,0,0},
  {0,2,7,0,2,2,		0,0,0},
  {0,4,4,0,4,4,		0,0,0},
  {5,0,0,4,0,0,		8,2,3},
  {0,6,6,0,6,6,		0,0,0},
  {5,0,0,4,0,0,		0,9,3},
  {5,0,0,4,0,0,		0,0,10},
  {0,6,0,0,11,0,	0,0,0},
  {0,1,7,0,1,1,		0,0,0},
  {0,3,3,0,3,3,		0,0,0},
  {0,5,5,0,5,5,		0,0,0}
  };

int Production[MAX_PRODUCTION+1][2] = {
  {0,0},
  {NON_E,3},
  {NON_E,1},
  {NON_T,3},
  {NON_T,1},
  {NON_F,3},
  {NON_F,1}
  };

void printSymbol(int s)
  {
  switch(s)
    {
    case TER_ID		: printf("id "); break;
    case TER_OR		: printf("v "); break;
    case TER_AND	: printf("& "); break;
    case TER_ABRE	: printf("( "); break;
    case TER_FECHA	: printf(") "); break;
    case TER_FIM	: printf("$ "); break;
    case NON_F		: printf("F "); break;
    case NON_T		: printf("T "); break;
    case NON_E		: printf("E "); break;
    default		: printf("Unknown "); break;
    }
  }

// This is the stack in which the parser operates
// Is is tested for overflow/underflow but generates no error
// The *user* should test it before pushing/popping.

int Stack[MAX_STACK];
int StackTopPos = 0;
#define StackEmpty()	(StackTopPos? FALSE : TRUE)
#define StackFull()	(StackTopPos==MAX_STACK)
#define StackTop()	(StackTopPos? Stack[StackTopPos-1] : 0)
#define StackPop()	(StackTopPos? StackTopPos-- : FALSE )
#define StackPush(a)	(StackTopPos<MAX_STACK? Stack[StackTopPos++] = (a) : FALSE) 


// This is our input, already in!!!!

int Entrada[256] = { 
  TER_ID,TER_OR,
  TER_ABRE,TER_ID,TER_AND,TER_ID,TER_FECHA,
  TER_AND,TER_ID,TER_FIM
  };
int atual = 0;
int next_token()   
  {
  printf("Lendo token da entrada: ");
  printSymbol(Entrada[atual]);
  printf("\n");
  return Entrada[atual++];
  }

void printRule(int num)
  {
  switch(num)
    {
  case 1: printf("E->EvT\n"); break;
  case 2: printf("E->T\n"); break;
  case 3: printf("T->T&F\n"); break;
  case 4: printf("T->F\n"); break;
  case 5: printf("F->(E)\n"); break;
  case 6: printf("F->id\n"); break;
    }
  }

void printStack()
  {
  int i = 0;
  int len = 0;

  printf("STACK: ");
  for (i=0; i < StackTopPos; i+=2)
    {
    printSymbol(Stack[i]);
    printf("%d ",Stack[i+1]);
    }        
  printf("\n");        
  }

// MAIN: need to say more?

int main(int argc, char **argv)
  {
  int Em = 0;
  int ai = 0;
  int i = 0;
  int r = 0;
  int Emr = 0;
  int A = 0;
  int prod = 0;

  StackPush(NON_E);	// Start symbol just to make the stack even
  StackPush(0);		// starting state
  ai = next_token();	// first token

  while(1) 
    {
    printStack();
    Em = StackTop();
    getchar();
    if ( Action[Em][ai] == ACTION_ACCEPT )
      {
      printf("Success!\n");
      break;
      }
    else
    if ( Action[Em][ai] == 0 )
      {
      printf("Error on state %d with symbol ",Em);
      printSymbol(ai);
      printf("!\n");
      break;
      }
    else
    if ( Action[Em][ai] == ACTION_PUSH )
      {
      printf("Empilha \n");
      StackPush(ai);
      StackPush(Transition[Em][ai]);
      ai = next_token();  
      }
    else
    if ( Action[Em][ai] == ACTION_REDUCE )
      {
      // Find production and print it
      prod = Transition[Em][ai];
      printf("Reduz com regra: ");
      printRule(prod);
      // Pop 2r symbols from stack
      r = Production[prod][1];
      for (i = 0; i < 2*r; ++i)
	StackPop();
      // Push the lçeft hand side and new state
      A = Production[prod][0];
      Emr = StackTop();
      StackPush(A);
      StackPush(Transition[Emr][A]);
      }
    else
      {
      printf("Unknown action in the table!\n");
      exit(0);
      }
    }
  }