-- Parser for simple expressions.
-- A straightforward, hand-crafted, top-down predictive parser.
-- Developed for use in COMP2600
-- Clem Baker-Finch

module Parser (parseExp) where

import Scanner
import AbsSyn

-- Check that the next token is the one expected:
check :: Token -> [Token] -> [Token]

check tok []  = error "Unexpected end of input."
check tok (t:ts)
    | tok == t  = ts
    | otherwise = error (unscan tok ++ " expected.\n" ++ unscan t ++ " scanned.")
-- Parse an arithmetic expression.
-- Operator precedence is as usual, represented by the following grammar:

-- expr  ::= expr + term | expr - term | term
-- term ::= term * factor | factor
-- factor ::= num | ident | (expr)

-- Eliminate left recursion and left to factor give:

-- expr ::= term exprOpt
-- exprOpt ::= + term exprOpt | - term exprOpt | <empty>
-- term ::= factor termOpt
-- termOpt ::= * factor exprOpt | <empty>
-- factor ::= num | ident | (expr)

-- Director symbols:

-- first(expr) = first(term) = first(factor) = {NUM, LPAREN}

-- first(exprOpt) = {PLUS, MINUS}
-- follow(exprOpt) = {RPAREN, EOI}

-- first(term) = first(factor) = {NUM, LPAREN}

-- first(termOpt) = {TIMES}
-- follow(termOpt) = follow(exprOpt) U {PLUS, MINUS}

-- first(factor) = {NUM, LPAREN}

-- Parse an expr --
expr :: [Token] -> (Aexp, [Token])
expr = exprOpt . term

-- Parse an exprOpt --
exprOpt :: (Aexp, [Token]) -> (Aexp, [Token])
exprOpt (t1, PLUS:toks)  = exprOpt (t1 :+: t2, toks')
    where
    (t2, toks') = term toks		      
exprOpt (t1, MINUS:toks) = exprOpt (t1 :-: t2, toks')
    where
    (t2, toks') = term toks
exprOpt (t, toks)        = (t, toks)

-- Parse a term --
term ::  [Token] -> (Aexp, [Token])
term = termOpt . factor

-- Parse a termOpt --
termOpt :: (Aexp, [Token]) -> (Aexp, [Token])
termOpt (f1, TIMES:toks) = termOpt (f1 :*: f2, toks')
    where
    (f2, toks') = factor toks
termOpt (f, toks)        = (f, toks)

-- Parse a factor --
factor ::  [Token] -> (Aexp, [Token])
factor (NUM n:toks)  = (Num n, toks)
factor (LPAREN:toks) = (e,toks'')
    where
    (e, toks') = expr toks
    toks''     = check RPAREN toks'
factor (t:toks)      = error ("Unexpected symbol: " ++ unscan t)


-- Parse a whole expression (no remaining tokens) --
parseExp :: String -> Aexp
parseExp source = expTree
    where
    (expTree, []) = expr $ scan source