Parsers

• Type: monad

data Parser = P (String -> Tree)

-- return unused input
data Parser = P (String -> (Tree, String))

-- can be parsed in many ways
data Parser = P (String -> [(Tree, String)])

-- might not always produce a tree
data Parser = P (String -> [(a, String)])

Basic Parsers

-- always return empty list upon failure
failure :: Parser a
failure = P (\inp -> [])

-- return value without consuming input
return :: a -> Parser a
return v =  P (\inp -> [(v, inp)])

-- consume one character
item :: Parser Char
item = P (\inp ->
      case inp of
            ""      -> []
            (c:cs)  -> [(c, cs)]
)

-- if p fails, then use q
(+++) :: Parser a -> Parser a -> Parser a
p +++ q =  P (\inp -> 
let res = parse p inp in
      case res of
            [] -> parse q inp
            _ -> res
)

-- applies parser to a string
parse :: Parser a -> String -> [(a,String)]
parse (P p) inp  =  p inp

Sequencing

• Combine a sequence of parsers with do
• Layout rule
  • Each parser starts at the same column
• Values returned discarded if not named by using <-
• The last returned value = the returned value of the overall sequence of parsers
• If any parser fails, the overall sequence of parsers fail

p :: Parser (Char, Char)
p = do x <- item
       item
       y <- item
       return (x, y)

Derived Primitives

sat :: (Char -> Bool) -> Parser Char
sat p = do i <- item
           case p i in
               True -> return c
               False -> failure

char :: Char -> Parser Char
char c = sat (c ==)

-- apply the parser zero or more times
many :: Parser a -> Parser [a]
many p = many1 p +++ return []

-- apply the parser at least one time
many1 :: Parser a -> Parser [a]
many1 p = do x <- p
             xs <- many p
             return (x:xs)

Arithmetic Expressions

Rules

expr      -> term '+' expr | term
term      -> factor '*' term | factor
factor    -> digit | '(' expr ')'
digit     -> '0' | '1' | ... | '9'

pExpr :: Parser Expr
pExpr = do t <- pTerm
           token $ char '+'
           e <- pExpr
           return (Add t e)
        +++ pTerm

pTerm :: Parser Expr
pTerm = do f <- pFactor
           token $ char '*'
           t <- pTerm
           return (Mul f t)
        +++ pFactor

pFactor :: Parser Expr
pFactor = do token $ char '('
             e <- pExpr
             token $ char ')'
             return e
          +++ do i <- integer 
                 return (Val i)

interpret :: String -> Int
interpret xs = fst (head (parse pExpr xs))