-- A recursive-descent parser for simple statement sequences

-- 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)

parse_S :: Parser  -- Parser for non-terminal S
parse_S (t:ts) =
  case t of
    Id -> let ts1 = terminal Eq ts
              ts2 = terminal Num ts1
          in ts2
    Print -> terminal Id ts
    Begin -> let ts1 = parse_S ts
                 ts2 = parse_L ts1
             in ts2

parse_L :: Parser
parse_L (t:ts) =
  case t of
    End  -> ts
    Semi -> let ts1 = parse_S ts
                ts2 = parse_L ts1
             in ts2

parse = parse_S (scanner "")