Parsing with parsec
A parser is a value
parsec builds a parser from small parsers with combinators, and a parser is a value like any other: it can be passed, returned and named. The type names the input, the state and the result:
parse :: Parsec String () a -> String -> String -> Either ParseError a
Parser a = Parsec String () a
many1 :: Parser a -> Parser [a]
digit :: Parser Char
parse takes the parser, a name for the source (shown in errors) and the input, and gives either an error with a position or the result. Nothing is consumed by naming a parser: it runs when parse is called, which is what makes a parser a pure value and a test of a parser a pure function.
A number and a grammar
Two parsers and one combinator are enough for a sum of numbers:
- many1 digit reads one or more digits and gives the string of them.
- read turns that string into an Int, which is the one unsafe step and is safe here because the characters are digits.
-
The grammar is written as a do block over the parser
monad, which is the same notation the IO lessons used: the difference is that
the effect is consumption of input.
An expression parser
module Main (main) whereimport Text.Parsecimport Text.Parsec.String (Parser)data Expr = Lit Int | Add Expr Exprderiving (Show)number :: Parser Exprnumber = dodigits <- many1 digitpure (Lit (read digits))expr :: Parser Exprexpr = doleft <- numberrest <- many (char '+' >> number)pure (foldl' Add left rest)main :: IO ()main = doprint (parse expr "" "1+2+3")print (parse expr "" "1+2+")ghc -Wall -O1 -o parse parse.hs
./parseRight (Add (Add (Lit 1) (Lit 2)) (Lit 3))
Left (line 1, column 5):
unexpected end of input
expecting digitThe good input gives the tree, left-associated because foldl' folds from the left, and the Show instance prints it. The bad input gives a Left with the position and two lines of expectation: after the last plus the parser was at the fifth column and wanted a digit. Nothing threw and nothing was printed to stderr; the error is a value.
The error and its position
The position is part of the error and not of the message the program builds, which is the reason to use a parser library instead of a hand-written loop:
- line 1, column 5 counts characters from one and lines from one, in the source name given to parse.
- unexpected end of input says what was found, and expecting digit says what was wanted; both come from the combinators.
- A try around a parser makes a failed alternative consume nothing, which is how backtracking is written when the grammar needs it.
The parser above stops at the first character it cannot use and returns what it parsed, which is why parse expr "" "1+2+x" gives a Right and leaves the eof at the end: parse (expr <* eof).
parsec, megaparsec and what is here
parsec is a boot library of GHC, so it is available offline and a Cabal file names it in build-depends like any other package. megaparsec is the modern descendant: better error messages, a different API, and a package that has to be downloaded. This container has parsec and not megaparsec, which is why the course uses the former and the capstone builds its parser with it.
The next part of the course leaves the single thread: forkIO, MVar, channels and STM, with the timings of the runtime on this machine.
Exercises
- Add multiplication with the precedence a reader expects and test it.
- Add parentheses with between and a recursive production.
- Put eof at the end and parse "1+2+x" again.
- Parse a list of decimal numbers separated by commas.
- Print the position of an error on the third line of a multi-line input.
- Explain why read digits cannot fail in this grammar.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is a parser in parsec?
Answer
A value of type Parser a that runs when parse is called
The parser is a pure value, which is why a test can call it directly.
-
What does
many1 digitparse?Answer
One or more digits
many1 requires at least one and allows more.
-
What does
parse expr "" "1+2+"return?Answer
A Left with the error and its column
The trailing plus has no number after it, so the parse fails with a position.
-
What does this program print?
module Main (main) where import Text.Parsec import Text.Parsec.String (Parser) number :: Parser Int number = do digits <- many1 digit pure (read digits) main :: IO () main = print (parse number "" "42")Answer
Right 42
The parser reads the digits and returns their value inside Right.
-
Which package is the modern descendant of parsec?
Answer
megaparsecMegaparsec is the newer library; this container has parsec as a boot library.
-
What does this program print?
module Main (main) where import Text.Parsec import Text.Parsec.String (Parser) letterA :: Parser Char letterA = char 'a' main :: IO () main = print (parse letterA "" "abc")Answer
Right 'a'
The parser consumes one character and returns it, so the result is Right with a Char.
-
What is in the error besides the message?
Answer
The line and column of the failure
The position is part of ParseError and is what makes the message useful.
-
What does this program print?
module Main (main) where import Text.Parsec import Text.Parsec.String (Parser) twice :: Parser String twice = do a <- string "ab" b <- string "ab" pure (a ++ b) main :: IO () main = print (parse twice "" "abab")Answer
Right "abab"
The two string parsers consume the two pairs and the results are concatenated.
-
What does adding
<* eofto a parser change?Answer
It rejects input left after the parsed part
The parser then has to consume everything, so trailing text is an error.
-
What does this program print?
module Main (main) where main :: IO () main = print (foldl (flip (:)) [] [1, 2, 3 :: Int])Answer
[3,2,1]
Each element is consed onto the front of the accumulator, which reverses the list.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev