CSCE 314 Lecture 15

« previous | Friday, September 30, 2011 | next »

Interpret ">>=" as "followed by"

-- definition: takes a parser and a function that returns another parser, and returns the composition of the two parsers
(>>=) :: Parser a -> (a -> Parser b) -> Parser b
parser >>= func = \input -> case parse parser input of
    []         -> []
    [(v, out)] -> parse (func v) out

ifStmt = keyword "if" >>= \_ ->
symbol '(' >>= \_ ->
expression >>= \e ->
symbol ')' >>= \_ ->
statement >>= \s ->
symbol ';' >>= \_ ->
return $ ASTIfStatement e s

-- can also be written as (>> takes parser, not function returning parser)
ifStmt = keyword "if" >>
symbol '(' >>
expression >>= \e ->
symbol ')' >>
statement >>= \s ->
symbol ';' >>
return $ ASTIfStatement e s

Current Parsenal

• Failure (fails every time)
• Return (returns what we give it)
• Item (takes the first item into the output)

Sat

Parser that accepts a character satisfying a predicate

sat :: (Char -> Bool) -> String -> [(Char, String)]
sat p = item >>= \v1 ->
    id p v1 then return v1 else failure

-- Examples
> parse (sat (=='a')) "abc"
[('a',"bc")]
> parse (sat (=='b')) "abc"
[]

-- Derived usage
digit :: Parser Char
digit = sat isDigit

String

string :: String -> Parser String
string [] = return []
string (x:xs) = char x >>= \c ->
                string xs >>= \cs ->
                return (c:cs)

> parse (string "if") "if (a<b) return;"
[("if"," (a<b) return;")]

Many

Suppose we want to parse zero or more occurrences of a certain type of character:

-- finds at least one occurrence of p
many1 :: Parser a -> Parser [a]
many1 p = p >> \v ->
          many p >>= \vs ->
          return (v:vs)

-- finds zero or more occurrences of p
many :: Parser a -> Parser [a]
many p = many1 p +++ return []

-- Examples
> parse (many digit) "123"
[("123","")]
> parse (many digit) "a123"
[("","a123")]

Semi-realistic Example

-- a letter followed by zero or more alphanumeric characters
identifier :: Parser String
identifier = letter >>= \x ->
             many alphanum >>= \xs ->
             return (x:xs)

> parse identifier "2len = 5"
[]
> parse identifier "len2 = 5"
[("len2"," = 5")]

nat :: Parser Int
nat = many1 digit >>= \xs ->
      return (read xs)

list = string "[" >>= \_ ->
       nat >>= \v ->
       many (string "," >>= \_ -> nat) >>= \vs ->
       string "]" >>= \_ ->
       return (v:vs)

-- Get rid of white space
space :: Parser ()
space = many (sat isSpace) >> return ()