exception SYNTAX_ERROR;

datatype lexResult = PLUS | TIMES | INT | EOF | LPAREN | RPAREN; 
datatype nonTerminal = EXP | EXP1 | TERM | TERM1 | FACTOR ;

datatype token = NT of nonTerminal | T of lexResult;

val productions = 
  [[NT(TERM), NT(EXP1)], 
   [T(PLUS), NT(EXP)],
   [],
   [NT(FACTOR), NT(TERM1)],
   [T(TIMES), NT(TERM)],
   [],
   [T(INT)],
   [T(LPAREN), NT(EXP), T(RPAREN)]
  ]; 

fun parseTable EXP     INT       = 1
 |  parseTable EXP     LPAREN    = 1
 |  parseTable EXP1    PLUS      = 2
 |  parseTable EXP1    RPAREN    = 3
 |  parseTable EXP1    EOF       = 3
 |  parseTable TERM    INT       = 4
 |  parseTable TERM    LPAREN    = 4
 |  parseTable TERM1   PLUS      = 6
 |  parseTable TERM1   TIMES     = 5
 |  parseTable TERM1   RPAREN    = 6
 |  parseTable TERM1   EOF       = 6
 |  parseTable FACTOR  INT       = 7
 |  parseTable FACTOR  LPAREN    = 8
 |  parseTable _       _         = raise SYNTAX_ERROR;

   
fun pushAll [] stack = stack
 |  pushAll (x::xs) stack = pushAll xs (x::stack);


fun step ([]:token list) rest = rest
 |  step _ [] = raise SYNTAX_ERROR
 |  step (T(top)::RestStack) (this::moreInput) = 
      if (top=this) then 
          (print "advance()\n"; 
           step RestStack moreInput
          )
      else raise SYNTAX_ERROR
 |  step (NT(top)::RestStack) (this::moreInput) =
     let val index = parseTable top this in
       (print ("executing production no. "^Int.toString(index)^"\n");
        step (pushAll (List.rev (List.nth(productions, index-1)))
                      RestStack)
             (this::moreInput)
       )
      end;
        

fun parse () =  
   let val allTokens = [INT, PLUS, INT, EOF] in
     let val rest = (step [NT(EXP)] allTokens) in 
       if rest=[EOF] then print "accept\n"
         else raise SYNTAX_ERROR
     end
   end;