-- A recursive-descent parser for a simple statement language
--
-- This version uses a simple sequencing combinator for parsers
-- to improve its readability

infixr 4 <*>

-- the type of tokens delivered by the scanner:
data Token = Id | Eq | Num | Print | Begin | End | Semi
   deriving (Eq,Show)

scanner :: String -> [Token]
scanner _ = [Begin, Id, Eq, Num, Semi, Print, Id, End] -- example scan


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

-- sequence combinator for parsers:
-- input: two parsers p1 and p2
-- output: a parser that recognizes the concatenation of p1 and p2
(<*>)    :: Parser -> Parser -> Parser
p1 <*> p2 = \ts -> p2 (p1 ts)


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

parse_S :: Parser
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


main1 = parse_S [Begin, Id, Eq, Num, Semi, Print, Id, End]
main2 = parse_S [Begin, Id, Eq, Num, Semi, Print, Num, End]