-- A recursive-descent parser for simple statement sequences

import Prelude hiding ((<*>))
    
-- The type of tokens delivered by the scanner:
data Token = Id | Eq | Num | Print | Begin | End | Semi
  deriving (Eq,Show)

scanner :: String -> [Token]
-- Example statement sequence
scanner _ = [Begin, Id, Eq, Num, Semi, Print, Id, End]

-- Type of parser functions:
type Parser = [Token] -> [Token]
-- input: list of tokens to parse
-- output: list of unconsumed tokens

-- A parser for terminal symbol:
terminal :: Token -> Parser
terminal tok (t:ts) =
  if tok == t
    then ts -- Token matches, return rest of token stream
    else error ("ERROR: wrong token \"" ++ show t ++ "\", expected: " ++ show tok)

-- A combinator for the sequence of two parsers:
(<*>) :: Parser -> Parser -> Parser
p1 <*> p2 = \ts -> p2 (p1 ts)

parse_S :: Parser  -- Parser for non-terminal S
parse_S (t:ts) =
  case t of
    Id    -> (terminal Eq <*> terminal Num) ts
    Print -> (terminal Id)                  ts
    Begin -> (parse_S <*> parse_L)          ts

parse_L :: Parser
parse_L (t:ts) =
  case t of
    End  -> ts
    Semi -> (parse_S <*> parse_L) ts

parse = parse_S (scanner "")