{-
The basic parser library from the Grammars and Parsing course.
-}

module ParseBase
  ( Parser
  , run
  , failp, succeed       -- elementary parsers that don't consume input
  , symbol, token        -- elementary parsers
  , (<|>), (<*>), (<$>)  -- elementary parser combinators
  ) where


-- The type of parsers

type Parser s a = [s] -> [(a, [s])]

run :: Parser s a -> [s] -> a
run p input = case [ r | (r, []) <- p input ] of
  []    -> error "parse error"
  (r:_) -> r


-- Elementary parsers

failp :: Parser s a
failp xs = []

succeed :: a -> Parser s a
succeed r xs = [(r, xs)]

-- Note: not exported.
satisfy :: (s -> Bool) -> Parser s s
satisfy p [] = []
satisfy p (x:xs)
  | p x       = [(x, xs)]
  | otherwise = []

symbol :: Eq s => s -> Parser s s
symbol s = satisfy (== s)

token :: Eq s => [s] -> Parser s [s]
token k xs
  | k == take n xs = [(k, drop n xs)]
  | otherwise      = []
  where n = length k


-- Elementary parser combinators

infixl 7  <$>
infixl 6  <*>
infixr 4  <|>

(<|>) :: Parser s a -> Parser s a -> Parser s a
(p <|> q) xs = p xs ++ q xs

(<*>) :: Parser s (b -> a) -> Parser s b -> Parser s a
(p <*> q) xs = [ (f x, zs) | (f, ys) <- p xs, (x, zs) <- q ys ]

f <$> p = succeed f <*> p
--(<$>) :: (a -> b) -> Parser s a -> Parser s b
--(f <$> p) xs = [ (f y, ys) | (  y, ys) <- p xs ]