-- A recursive-descent parser for expressions which returns the value
-- of the expression.

parse_E :: [Token] -> ([Token], Int)
parse_E ts =
  let (ts1, tRes) = parse_T ts
  in case head ts of
       NUM _   -> parse_E' ts1 tRes
       LPAREN  -> parse_E' ts1 tRes
       _       -> parseError "E" ts

-- Second argument: semantic value of expression left oft E'
parse_E' :: [Token] -> Int -> ([Token], Int)
parse_E' ts lval = case head ts of
  PLUS    -> let (ts1, tRes) = parse_T (tail ts)
             in parse_E' ts1 (lval + tRes)
  RPAREN  -> (ts, lval)
  EOF     -> (ts, lval)
  _       -> parseError "E'" ts


parse_T :: [Token] -> ([Token], Int)
parse_T ts =
  let (ts1, fRes) = parse_F ts
  in case head ts of
       NUM _   -> parse_T' ts1 fRes
       LPAREN  -> parse_T' ts1 fRes
       _       -> parseError "T" ts

-- Second argument: semantic value of expression left oft T'
parse_T' :: [Token] -> Int -> ([Token], Int)
parse_T' ts lval = case head ts of
  PLUS    -> (ts, lval)
  MULT    -> let (ts1, fRes) = parse_F (tail ts)
             in parse_T' ts1 (lval * fRes)
  RPAREN  -> (ts, lval)
  EOF     -> (ts, lval)
  _       -> parseError "T'" ts


parse_F :: [Token] -> ([Token], Int)
parse_F (t:ts) =
  case t of
    NUM n  -> (ts, n)
    LPAREN -> let (ts1, eRes) = parse_E ts
              in (terminal RPAREN ts1, eRes)
    _      -> parseError "F" (t:ts)


parseError :: String -> [Token] -> a
parseError s ts =
   error ("Wrong token " ++ show (head ts) ++ " at beginning of " ++ s)


-- A parser for a terminal symbol just consumes a single token, if possible:
terminal :: Token -> ([Token] -> [Token])
terminal tok (t:ts) =
  if tok==t
    then ts
    else error $ "Wrong token \"" ++ show t ++ "\", expected: " ++ show tok

data Token = NUM Int | PLUS | MULT | LPAREN | RPAREN | EOF
  deriving (Eq,Show)

------------------------------------------------------------------------------
-- Examples:
main1 = snd (parse_E [NUM 3, PLUS, NUM 4, MULT, NUM 5, EOF]) -- 3 + 4 * 5
main2 = snd (parse_E [LPAREN, NUM 3, PLUS, NUM 4, RPAREN, MULT, NUM 5, EOF]) -- (3 + 4) * 5