Megaparsec tutorial

Published on February 23, 2019, last updated August 1, 2026

This is the Megaparsec tutorial, which was originally written as a chapter for the Intermediate Haskell book. Due to the lack of progress with the book, the other authors agreed to let me publish the text as a standalone tutorial so that people can benefit at least from this part of our work.

Japanese translation, Chinese translation.

• ParsecT and Parsec monads
• Character and binary streams
• Monadic and applicative syntax
• Forcing consumption of input with eof
• Working with alternatives
• Controlling backtracking with try
• Debugging parsers
• Labeling and hiding things
• Running a parser
• The MonadParsec type class
• Lexing
  • White space
  • Char and string literals
  • Numbers
• notFollowedBy and lookAhead
• Parsing expressions
• Indentation-sensitive parsing
  • nonIndented and indentBlock
  • Parsing a simple indented list
  • Nested indented list
  • Adding line folds
• Writing efficient parsers
• Parse errors
  • Parse error definitions
  • How to signal a parse error
  • Displaying parse errors
  • Catching parse errors in a running parser
  • Controlling location of parse errors
  • Reporting multiple parse errors
• Testing Megaparsec parsers
• Working with custom input streams

The toy parser combinators developed in the chapter “An Example: Writing Your Own Parser Combinators” are not suitable for real-world use, so let’s continue by taking a look at the libraries in the Haskell ecosystem that solve the same problem, and note the various trade-offs they make:

• parsec has been the “default” parsing library in Haskell for a long time. The library is said to be focused on the quality of its error messages. It does not, however, have good test coverage, and is currently in maintenance mode.

• attoparsec is a robust, fast parsing library with a focus on performance. It is the only library on this list that has full support for incremental parsing. Its downsides are the poor quality of its error messages, its inability to be used as a monad transformer, and the limited set of types that can be used as an input stream.

• trifecta features good error messages but is under-documented and hard to figure out. It can parse String and ByteString out-of-the-box, but not Text.

• megaparsec is a fork of parsec that has been actively developed in the last few years. The current version tries to find a nice balance between speed, flexibility, and quality of parse errors. As an unofficial successor of parsec, it stays conventional and immediately familiar for users who have used that library or who have read parsec tutorials.

It would be impractical to try to cover all these libraries, and so we will focus on megaparsec. More precisely, we are going to cover version 9, which by the time this book is published will probably have replaced the older versions almost everywhere.

ParsecT and Parsec monads

ParsecT is the main parser monad transformer and the central data type in megaparsec. ParsecT e s m a is parametrized like this:

• e is the type of the custom component of error messages. If we do not want anything custom (and for now we do not), we just use Void from the Data.Void module.

• s is the type of the input stream. megaparsec works out of the box with String, strict and lazy Text, and strict and lazy ByteStrings. It is also possible to work with custom input streams.

• m is the inner monad of the ParsecT monad transformer.

• a is the monadic value, the result of parsing.

Since most of the time m is nothing but Identity, the Parsec type synonym is quite useful:

type Parsec e s a = ParsecT e s Identity a

Parsec is simply the non-transformer version of ParsecT.

We can also draw an analogy between the monad transformers in megaparsec and the MTL monad transformers and classes. Indeed, there is also the MonadParsec type class, which is similar in its purpose to type classes such as MonadState and MonadReader. We will return to MonadParsec later and discuss it in more detail.

Speaking of type synonyms, the best way to start writing a parser with megaparsec is to define a custom type synonym for your parser. This is a good idea for two reasons:

• It will be easier to add top-level signatures like Parser Int, where Parser is your parsing monad. Without the signatures, things like e will often be ambiguous—it is the flip side of the polymorphic API of the library.

• Working with concrete types that have all type variables fixed helps GHC optimize a lot better. GHC cannot do much in terms of optimization if your parsers stay polymorphic. Although the megaparsec API is polymorphic, the end user is expected to stick to a concrete type of parsing monad, so inlining and the fact that most functions have their definitions dumped into so-called interface files will allow GHC to produce very efficient non-polymorphic code.

Let’s define a type synonym (typically called Parser) like this:

type Parser = Parsec Void Text
--                   ^    ^
--                   |    |
-- Custom error component Type of input stream

Until we start dealing with custom parsing errors, assume this type whenever you see Parser in the chapter.

Character and binary streams

It has been said that megaparsec can work with five types of input stream out of the box: String, strict and lazy Text, and strict and lazy ByteStrings. This is possible because the library makes these types instances of the Stream type class, which abstracts the functionality that every data type should support in order to be used as input to a megaparsec parser.

A simplified version of Stream could look like this:

class Stream s where
  type Token  s :: *
  type Tokens s :: *
  take1_ :: s -> Maybe (Token s, s) -- aka uncons
  tokensToChunk :: Proxy s -> [Token s] -> Tokens s

The real definition of Stream has more methods, but knowing about them is not necessary for using the library.

Note that the type class has two type functions associated with it:

• Token s for a stream s is the type of a single token. Common examples are Char and Word8, although it may be something else for custom streams.

• Tokens s for a stream s is the type of a “chunk” of the stream. The concept of chunk was introduced only for performance reasons. Indeed, it is often possible to have a more efficient representation of part of a stream that is isomorphic to a list of tokens [Token s]. For example, an input stream of type Text has Tokens s ~ Text: a chunk of Text is just Text. Although the type equality Tokens s ~ s often holds, Tokens s and s may differ for custom streams, and so we separate these types in megaparsec.

We can put all the default input streams into a single table like this:

It is important to get used to the Token and Tokens type functions, because they are ubiquitous in the types of the megaparsec API.

You may have noticed that if we group all the default input streams by token type, we get two groups:

• character streams, for which Token s ~ Char: String and strict/lazy Text,

• binary streams, for which Token s ~ Word8: strict and lazy ByteStrings.

It turns out that with megaparsec it is not necessary to code the same parsers for every type of input stream (this is the case, for example, with the attoparsec library), but we still must have different code for different token types:

• to get the common combinators for character streams, import the Text.Megaparsec.Char module;

• to get the same for binary streams, import Text.Megaparsec.Byte.

These modules contain two similar sets of helper parsers such as:

Let’s introduce a couple of primitives on which these modules are built, so that we understand the tools we are going to use.

The first primitive is called token, and, correspondingly, it allows us to parse a Token s:

token :: MonadParsec e s m
  => (Token s -> Maybe a)
    -- ^ Matching function for the token to parse
  -> Set (ErrorItem (Token s))
     -- ^ Expected items (in case of an error)
  -> m a

The first argument of token is the matching function for the token to parse. If the function returns something in a Just, that value becomes the result of parsing. Nothing indicates that the parser does not accept this token, and so the primitive fails.

The second argument is a Set (from the containers package) that contains all the expected ErrorItems to be displayed to the user in case of failure. We will explore the ErrorItem type in detail when we discuss parse errors.

To better understand how token works, let’s look at some definitions from the Text.Megaparsec module, which contains, among other things, some combinators that work with all types of input stream. satisfy is a fairly common combinator: we give it a predicate that returns True for the tokens we want to match, and it gives us a parser back:

satisfy :: MonadParsec e s m
  => (Token s -> Bool) -- ^ Predicate to apply
  -> m (Token s)
satisfy f = token testToken Set.empty
  where
    testToken x = if f x then Just x else Nothing

The job of testToken is to turn the f function, which returns Bool, into the function returning Maybe (Token s) that token expects. With satisfy, we do not know the exact sequence of tokens that we expect to match, so we pass Set.empty as the second argument.

satisfy should be understandable; let’s see how it works. To play with a parser, we need a helper function to run it. For testing in GHCi, megaparsec provides parseTest.

First, let’s start GHCi and import some modules:

λ> import Text.Megaparsec
λ> import Text.Megaparsec.Char
λ> import Data.Text (Text)
λ> import Data.Void

We add the Parser type synonym that we will use to resolve the ambiguity in the types of the parsers:

λ> type Parser = Parsec Void Text

We also need to enable the OverloadedStrings language extension so we can use string literals as Text values:

λ> :set -XOverloadedStrings

λ> parseTest (satisfy (== 'a') :: Parser Char) ""
1:1:
  |
1 | <empty line>
  | ^
unexpected end of input

λ> parseTest (satisfy (== 'a') :: Parser Char) "a"
'a'

λ> parseTest (satisfy (== 'a') :: Parser Char) "b"
1:1:
  |
1 | b
  | ^
unexpected 'b'

λ> parseTest (satisfy (> 'c') :: Parser Char) "a"
1:1:
  |
1 | a
  | ^
unexpected 'a'

λ> parseTest (satisfy (> 'c') :: Parser Char) "d"
'd'

The :: Parser Char annotation is necessary because satisfy by itself is polymorphic, so parseTest cannot know what to use in place of e and s in MonadParsec e s m (m is assumed to be Identity with these helpers). If we were working with a pre-existing parser that had a type signature, the explicit clarification of the parser type would be unnecessary.

That seems to work all right. The problem with satisfy is that it does not say what is expected when it fails, because we cannot analyze the function that the caller of satisfy provides. There are other combinators that are less general but can generate more helpful error messages. For example, there is single (with type-constrained synonyms called char in Text.Megaparsec.Byte and Text.Megaparsec.Char), which matches a specific token value:

single :: MonadParsec e s m
  => Token s           -- ^ Token to match
  -> m (Token s)
single t = token testToken expected
  where
    testToken x = if x == t then Just x else Nothing
    expected    = Set.singleton (Tokens (t:|[]))

The Tokens data constructor has nothing in common with the type function Tokens that we discussed previously. In fact, Tokens is one of the constructors of ErrorItem, and it is used to specify a concrete sequence of tokens we expected to match.

λ> parseTest (char 'a' :: Parser Char) "b"
1:1:
  |
1 | b
  | ^
unexpected 'b'
expecting 'a'

λ> parseTest (char 'a' :: Parser Char) "a"
'a'

We can now define newline from the table above:

newline :: (MonadParsec e s m, Token s ~ Char) => m (Token s)
newline = single '\n'

The second primitive is called tokens, and it allows us to parse Tokens s; that is, it can be used to match a fixed chunk of input:

tokens :: MonadParsec e s m
  => (Tokens s -> Tokens s -> Bool)
    -- ^ Predicate to check equality of chunks
  -> Tokens s
    -- ^ Chunk of input to match against
  -> m (Tokens s)

There are also two parsers defined in terms of tokens:

-- from "Text.Megaparsec":
chunk :: MonadParsec e s m
  => Tokens s
  -> m (Tokens s)
chunk = tokens (==)

-- from "Text.Megaparsec.Char" and "Text.Megaparsec.Byte":
string' :: (MonadParsec e s m, Data.CaseInsensitive.FoldCase (Tokens s))
  => Tokens s
  -> m (Tokens s)
string' = tokens ((==) `on` Data.CaseInsensitive.mk)

Both match fixed chunks of input: chunk (which has type-constrained synonyms called string in Text.Megaparsec.Byte and Text.Megaparsec.Char) case-sensitively, and string' case-insensitively. For case-insensitive matching the case-insensitive package is used, hence the FoldCase constraint.

Let’s try to use the new combinators:

λ> parseTest (string "foo" :: Parser Text) "foo"
"foo"

λ> parseTest (string "foo" :: Parser Text) "bar"
1:1:
  |
1 | bar
  | ^
unexpected "bar"
expecting "foo"

λ> parseTest (string' "foo" :: Parser Text) "FOO"
"FOO"

λ> parseTest (string' "foo" :: Parser Text) "FoO"
"FoO"

λ> parseTest (string' "foo" :: Parser Text) "FoZ"
1:1:
  |
1 | FoZ
  | ^
unexpected "FoZ"
expecting "foo"

OK, we can match a single token and a chunk of input. The next step is to learn how to combine these building blocks to write more interesting parsers.

Monadic and applicative syntax

The simplest way to combine parsers is to execute them in succession. ParsecT and Parsec are monads, and monadic bind is exactly what we use for sequencing our parsers:

mySequence :: Parser (Char, Char, Char)
mySequence = do
  a <- char 'a'
  b <- char 'b'
  c <- char 'c'
  return (a, b, c)

We can run it to check that everything works as expected:

λ> parseTest mySequence "abc"
('a','b','c')

λ> parseTest mySequence "bcd"
1:1:
  |
1 | bcd
  | ^
unexpected 'b'
expecting 'a'

λ> parseTest mySequence "adc"
1:2:
  |
1 | adc
  |  ^
unexpected 'd'
expecting 'b'

An alternative syntax for sequential execution is possible if we remember that every monad is also an applicative functor, and so we can use applicative syntax:

mySequence :: Parser (Char, Char, Char)
mySequence =
  (,,) <$> char 'a'
       <*> char 'b'
       <*> char 'c'

The second version works just like the first. Which style to use is often a matter of taste. Monadic style is arguably more verbose and sometimes clearer, while applicative style is often more concise. That said, monadic style is of course more powerful, because monads are more powerful than applicative functors.

Forcing consumption of input with eof

Applicative is often powerful enough to allow us to do quite interesting things. Equipped with an associative operator that has an identity, we get a monoid on applicative functors, expressed in Haskell via the Alternative type class. The parser-combinators package provides quite a few abstract combinators built on the concepts of Applicative and Alternative. The Text.Megaparsec module re-exports them from Control.Applicative.Combinators.

One of the most common combinators is called many. It allows us to run a given parser zero or more times:

λ> parseTest (many (char 'a') :: Parser [Char]) "aaa"
"aaa"

λ> parseTest (many (char 'a') :: Parser [Char]) "aabbb"
"aa"

The second result may be a bit surprising. The parser consumed the as that matched, but stopped after that. Well, we did not say what we want to do after many (char 'a')!

Most of the time we actually want to force the parser to consume the entire input and report parse errors, instead of being shy and stopping silently. This is done by demanding that we reach the end of input. Happily, although the end of input is nothing but a concept, there is a primitive called eof :: MonadParsec e s m => m () that never consumes anything and only succeeds at the end of input. Let’s add it to our parser and try again:

λ> parseTest (many (char 'a') <* eof :: Parser [Char]) "aabbb"
1:3:
  |
1 | aabbb
  |   ^
unexpected 'b'
expecting 'a' or end of input

We did not say anything about bs in our parser, and they are certainly unexpected.

Working with alternatives

From now on we will be developing a real, useful parser that can parse URIs of the following form:

scheme:[//[user:password@]host[:port]][/]path[?query][#fragment]

We should remember that the things in square brackets [] are optional; they may or may not appear in a valid URI. [] may even be nested to express a possibility inside another possibility. We will handle all of this ¹.

Let’s start with scheme. We will accept only schemes that are known to us, namely data, file, ftp, http, https, irc, and mailto.

To match a fixed sequence of characters we use string. To express a choice, we use the (<|>) method from the Alternative type class. So we can write:

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE RecordWildCards   #-}

module Main (main) where

import Control.Applicative
import Control.Monad
import Data.Text (Text)
import Data.Void
import Text.Megaparsec hiding (State)
import Text.Megaparsec.Char
import qualified Data.Text as T
import qualified Text.Megaparsec.Char.Lexer as L

type Parser = Parsec Void Text

pScheme :: Parser Text
pScheme = string "data"
  <|> string "file"
  <|> string "ftp"
  <|> string "http"
  <|> string "https"
  <|> string "irc"
  <|> string "mailto"

Let’s try it:

λ> parseTest pScheme ""
1:1:
  |
1 | <empty line>
  | ^
unexpected end of input
expecting "data", "file", "ftp", "http", "https", "irc", or "mailto"

λ> parseTest pScheme "dat"
1:1:
  |
1 | dat
  | ^
unexpected "dat"
expecting "data", "file", "ftp", "http", "https", "irc", or "mailto"

λ> parseTest pScheme "file"
"file"

λ> parseTest pScheme "irc"
"irc"

Looks good, but the definition of pScheme is a bit repetitive. There is a way to write pScheme using the choice combinator:

pScheme :: Parser Text
pScheme = choice
  [ string "data"
  , string "file"
  , string "ftp"
  , string "http"
  , string "https"
  , string "irc"
  , string "mailto" ]

choice is just a synonym for asum—an operation that folds a list, putting (<|>) between its elements—so the two definitions of pScheme are actually the same, although the one that uses choice may look a bit nicer.

After the scheme, there should be a colon :. Recall that to require one thing to follow another, we use monadic bind or do notation:

data Uri = Uri
  { uriScheme :: Text
  } deriving (Eq, Show)

pUri :: Parser Uri
pUri = do
  r <- pScheme
  _ <- char ':'
  return (Uri r)

If we try to run pUri, we will see that it requires : to follow the scheme name now:

λ> parseTest pUri "irc"
1:4:
  |
1 | irc
  |    ^
unexpected end of input
expecting ':'

λ> parseTest pUri "irc:"
Uri {uriScheme = "irc"}

We are not done with parsing the scheme, though. A good Haskell programmer tries to define types in such a way that incorrect data cannot be represented. Not every Text value is a valid scheme. Let’s define a data type to represent schemes and make our pScheme parser return a value of that type:

data Scheme
  = SchemeData
  | SchemeFile
  | SchemeFtp
  | SchemeHttp
  | SchemeHttps
  | SchemeIrc
  | SchemeMailto
  deriving (Eq, Show)

pScheme :: Parser Scheme
pScheme = choice
  [ SchemeData   <$ string "data"
  , SchemeFile   <$ string "file"
  , SchemeFtp    <$ string "ftp"
  , SchemeHttp   <$ string "http"
  , SchemeHttps  <$ string "https"
  , SchemeIrc    <$ string "irc"
  , SchemeMailto <$ string "mailto" ]

data Uri = Uri
  { uriScheme :: Scheme
  } deriving (Eq, Show)

The (<$) operator just puts the value on its left-hand side into a functorial context, replacing whatever is there at the moment. a <$ f is the same as const a <$> f, but can be more efficient for some functors.

Let’s continue playing with our parser:

λ> parseTest pUri "https:"
1:5:
  |
1 | https:
  |     ^
unexpected 's'
expecting ':'

Hmm, https should be a valid scheme. Can you figure out what went wrong? The parser tries the alternatives one by one, and http matches, so it does not go further to try https. The solution is to put the SchemeHttps <$ string "https" line before the SchemeHttp <$ string "http" line. Remember: with alternatives, order matters!

Now pUri works correctly:

λ> parseTest pUri "http:"
Uri {uriScheme = SchemeHttp}

λ> parseTest pUri "https:"
Uri {uriScheme = SchemeHttps}

λ> parseTest pUri "mailto:"
Uri {uriScheme = SchemeMailto}

λ> parseTest pUri "foo:"
1:1:
  |
1 | foo:
  | ^
unexpected "foo:"
expecting "data", "file", "ftp", "http", "https", "irc", or "mailto"

Controlling backtracking with try

The next part to handle is [//[user:password@]host[:port]]—the authority. Here we have nested optional parts, so let us update the Uri type to reflect this:

data Uri = Uri
  { uriScheme    :: Scheme
  , uriAuthority :: Maybe Authority
  } deriving (Eq, Show)

data Authority = Authority
  { authUser :: Maybe (Text, Text) -- (user, password)
  , authHost :: Text
  , authPort :: Maybe Int
  } deriving (Eq, Show)

Now we need to discuss an important concept called backtracking. Backtracking is a way to travel back in time, “un-consuming” input in the process. This matters primarily with branching. Here is an example:

alternatives :: Parser (Char, Char)
alternatives = foo <|> bar
  where
    foo = (,) <$> char 'a' <*> char 'b'
    bar = (,) <$> char 'a' <*> char 'c'

Looks reasonable, let’s try it:

λ> parseTest alternatives "ab"
('a','b')

λ> parseTest alternatives "ac"
1:2:
  |
1 | ac
  |  ^
unexpected 'c'
expecting 'b'

What happens here is that the char 'a' part of foo (which is tried first) succeeded and consumed an a from the input stream. char 'b' then failed to match against 'c', and so we ended up with this error. An important detail here is that (<|>) did not even try bar, because foo had consumed some input!

This is done for performance reasons, and because it would make no sense to run bar, feeding it the leftovers of foo, anyway. bar wants to be run from the same point in the input stream as foo. megaparsec does not go back automatically, unlike, for example, attoparsec or the toy combinators from the previous chapter, so we must use a primitive called try to express our wish to backtrack explicitly. try p makes it so that if p fails after consuming input, try p fails as if no input had been consumed (in fact, it backtracks the entire parser state). This allows (<|>) to try its right-hand alternative:

alternatives :: Parser (Char, Char)
alternatives = try foo <|> bar
  where
    foo = (,) <$> char 'a' <*> char 'b'
    bar = (,) <$> char 'a' <*> char 'c'

λ> parseTest alternatives "ac"
('a','c')

All primitives that actually consume input (there are also primitives that alter the behavior of existing parsers, such as try itself) are “atomic” in terms of input consumption. This means that if they fail, they backtrack automatically, so there is no way they can consume some input and then fail halfway through. This is why pScheme, with its list of alternatives, works: string is defined on top of tokens, and tokens is a primitive. We either match the entire string with string, or we fail without consuming any input at all.

Back to parsing URIs: (<|>) can be used to build a handy combinator called optional:

optional :: Alternative f => f a -> f (Maybe a)
optional p = (Just <$> p) <|> pure Nothing

If p in optional p matches, we get its result in a Just; otherwise Nothing is returned. Just what we want! There is no need to define optional—Text.Megaparsec re-exports this combinator for us. We can now use it in pUri:

pUri :: Parser Uri
pUri = do
  uriScheme <- pScheme
  void (char ':')
  uriAuthority <- optional . try $ do            -- (1)
    void (string "//")
    authUser <- optional . try $ do              -- (2)
      user <- T.pack <$> some alphaNumChar       -- (3)
      void (char ':')
      password <- T.pack <$> some alphaNumChar
      void (char '@')
      return (user, password)
    authHost <- T.pack <$> some (alphaNumChar <|> char '.')
    authPort <- optional (char ':' *> L.decimal) -- (4)
    return Authority {..}                        -- (5)
  return Uri {..}                                -- (6)

I took the liberty of accepting any alphanumeric sequence of characters as username and password, and made similarly arbitrary simplifications in the format of the host.

Some important points here:

• In (1) and (2) we need to wrap the argument of optional with try, because it is a composite parser, not a primitive.

• (3) some is just like many, but demands that its argument parser match at least once: some p = (:) <$> p <*> many p.

• (4) Do not use try unless necessary! Here, if char ':' succeeds (and, being built on top of token, it does not itself need a try), we know for sure that a port must follow it, so we just demand a decimal number with L.decimal. After matching :, we are committed and do not need a way to go back.

• In (5) and (6) we assemble the Authority and Uri values using the RecordWildCards language extension.

• void :: Functor f => f a -> f () is used to explicitly discard the result of parsing; without it we would get warnings about unused values from GHC.

Play with pUri in GHCi and see for yourself that it works:

λ> parseTest (pUri <* eof) "https://mark:secret@example.com"
Uri
  { uriScheme = SchemeHttps
  , uriAuthority = Just (Authority
    { authUser = Just ("mark","secret")
    , authHost = "example.com"
    , authPort = Nothing } ) }

λ> parseTest (pUri <* eof) "https://mark:secret@example.com:123"
Uri
  { uriScheme = SchemeHttps
  , uriAuthority = Just (Authority
    { authUser = Just ("mark","secret")
    , authHost = "example.com"
    , authPort = Just 123 } ) }

λ> parseTest (pUri <* eof) "https://example.com:123"
Uri
  { uriScheme = SchemeHttps
  , uriAuthority = Just (Authority
    { authUser = Nothing
    , authHost = "example.com"
    , authPort = Just 123 } ) }

λ> parseTest (pUri <* eof) "https://mark@example.com:123"
1:13:
  |
1 | https://mark@example.com:123
  |             ^
unexpected '@'
expecting '.', ':', alphanumeric character, or end of input

Debugging parsers

However, you may find that there is a problem:

λ> parseTest (pUri <* eof) "https://mark:@example.com"
1:7:
  |
1 | https://mark:@example.com
  |       ^
unexpected '/'
expecting end of input

The parse error could be better! What to do? The easiest way to figure out what is going on is to use the built-in dbg helper from the Text.Megaparsec.Debug module:

dbg :: (VisualStream s, ShowToken (Token s), ShowErrorComponent e, Show a)
  => String            -- ^ Debugging label
  -> ParsecT e s m a   -- ^ Parser to debug
  -> ParsecT e s m a   -- ^ Parser that prints debugging messages

The VisualStream type class is defined for input streams that can be printed on the screen in readable form. We will not dwell on it here.

Let’s use it in pUri:

pUri :: Parser Uri
pUri = do
  uriScheme <- dbg "scheme" pScheme
  void (char ':')
  uriAuthority <- dbg "auth" . optional . try $ do
    void (string "//")
    authUser <- dbg "user" . optional . try $ do
      user <- T.pack <$> some alphaNumChar
      void (char ':')
      password <- T.pack <$> some alphaNumChar
      void (char '@')
      return (user, password)
    authHost <- T.pack <$> dbg "host" (some (alphaNumChar <|> char '.'))
    authPort <- dbg "port" $ optional (char ':' *> L.decimal)
    return Authority {..}
  return Uri {..}

Then let’s try running pUri on that unfortunate input again:

λ> parseTest (pUri <* eof) "https://mark:@example.com"
scheme> IN: "https://mark:@example.com"
scheme> MATCH (COK): "https"
scheme> VALUE: SchemeHttps

user> IN: "mark:@example.com"
user> MATCH (EOK): <EMPTY>
user> VALUE: Nothing

host> IN: "mark:@example.com"
host> MATCH (COK): "mark"
host> VALUE: "mark"

port> IN: ":@example.com"
port> MATCH (CERR): ':'
port> ERROR:
port> 1:14:
port> unexpected '@'
port> expecting integer

auth> IN: "//mark:@example.com"
auth> MATCH (EOK): <EMPTY>
auth> VALUE: Nothing

1:7:
  |
1 | https://mark:@example.com
  |       ^
unexpected '/'
expecting end of input

We can now see exactly what is going on inside megaparsec:

• scheme matches successfully.

• user fails: although there is a username, mark, there is no password after the colon : (we demand that the password not be empty here). We fail and, thanks to try, backtrack.

• host starts from the same point as user and now tries to interpret the input as a hostname. We can see that it succeeds and returns mark as the hostname.

• There may be a port number after the host, so port gets its chance now. It sees :, but there is no integer after it, so port fails as well.

• The whole auth parser thus fails (port is inside auth, and it has failed).

• The auth parser returns Nothing because it could not parse anything. Now eof demands that we have reached the end of input, but that is not the case, so we get the final error message.

What to do? This is an example of a situation where wrapping large portions of code in try may make parse errors worse. Let us take another look at the syntax we want to parse:

scheme:[//[user:password@]host[:port]][/]path[?query][#fragment]

What are we looking for? Something that would allow us to commit to a certain branch of parsing—just like with the port, where seeing the colon : tells us that a port number must follow. If you look carefully, you will see that the double slash // is the sign that our URI has an authority part. Since we match // with an “atomic” parser (string), matching on it backtracks automatically, and once we have matched //, we can safely demand the authority part. Let us remove the first try from pUri:

pUri :: Parser Uri
pUri = do
  uriScheme <- pScheme
  void (char ':')
  uriAuthority <- optional $ do -- removed 'try' on this line
    void (string "//")
    authUser <- optional . try $ do
      user <- T.pack <$> some alphaNumChar
      void (char ':')
      password <- T.pack <$> some alphaNumChar
      void (char '@')
      return (user, password)
    authHost <- T.pack <$> some (alphaNumChar <|> char '.')
    authPort <- optional (char ':' *> L.decimal)
    return Authority {..}
  return Uri {..}

Now we get a nicer parse error:

λ> parseTest (pUri <* eof) "https://mark:@example.com"
1:14:
  |
1 | https://mark:@example.com
  |              ^
unexpected '@'
expecting integer

It is still a bit misleading, but, well, that is a tricky example I have picked—lots of optionals.

Labeling and hiding things

Sometimes the list of expected items can get rather long. Remember what we get when we try to use an unrecognized scheme?

λ> parseTest (pUri <* eof) "foo://example.com"
1:1:
  |
1 | foo://example.com
  | ^
unexpected "foo://"
expecting "data", "file", "ftp", "http", "https", "irc", or "mailto"

megaparsec provides a way to override expected items with something custom, typically called a label. This is done with the help of the label primitive (which has a synonym in the form of the (<?>) operator):

pUri :: Parser Uri
pUri = do
  uriScheme <- pScheme <?> "valid scheme"
  -- the rest stays the same

λ> parseTest (pUri <* eof) "foo://example.com"
1:1:
  |
1 | foo://example.com
  | ^
unexpected "foo://"
expecting valid scheme

We can go on and add more labels to make error messages more human-readable:

pUri :: Parser Uri
pUri = do
  uriScheme <- pScheme <?> "valid scheme"
  void (char ':')
  uriAuthority <- optional $ do
    void (string "//")
    authUser <- optional . try $ do
      user <- T.pack <$> some alphaNumChar <?> "username"
      void (char ':')
      password <- T.pack <$> some alphaNumChar <?> "password"
      void (char '@')
      return (user, password)
    authHost <- T.pack <$> some (alphaNumChar <|> char '.') <?> "hostname"
    authPort <- optional (char ':' *> label "port number" L.decimal)
    return Authority {..}
  return Uri {..}

For example:

λ> parseTest (pUri <* eof) "https://mark:@example.com"
1:14:
  |
1 | https://mark:@example.com
  |              ^
unexpected '@'
expecting port number

Another primitive is called hidden. If label renames things, hidden just removes them altogether. Compare:

λ> parseTest (many (char 'a') >> many (char 'b') >> eof :: Parser ()) "d"
1:1:
  |
1 | d
  | ^
unexpected 'd'
expecting 'a', 'b', or end of input

λ> parseTest (many (char 'a') >> hidden (many (char 'b')) >> eof :: Parser ()) "d"
1:1:
  |
1 | d
  | ^
unexpected 'd'
expecting 'a' or end of input

hidden is useful when it is desirable to make error messages less noisy. For example, when parsing a programming language it is a good idea to drop “expecting white space” messages, because there can usually be white space after each token anyway.

EXERCISE: Now that all the necessary tools have been explained, finishing the pUri parser is left as an exercise for the reader.

Running a parser

We explored in detail how to construct parsers, but we haven’t looked at the functions that allow us to run them, except for parseTest.

Traditionally, the “default” function for running a parser from your program has been parse. But parse is actually a synonym for runParser:

runParser
  :: Parsec e s a -- ^ Parser to run
  -> String     -- ^ Name of source file
  -> s          -- ^ Input for parser
  -> Either (ParseErrorBundle s e) a

The second argument is just a file name that will be included in the generated parse errors; megaparsec is not going to read anything from that file, because the actual input comes as the third argument of the function.

runParser allows us to run the Parsec monad which, as we already know, is the non-transformer version of ParsecT:

type Parsec e s = ParsecT e s Identity

runParser has three siblings: runParser', runParserT, and runParserT'. The versions with the T suffix run the ParsecT monad transformer, and the “prime” versions take and return the parser state. Let’s put all the functions into a table:

A custom initial state may be necessary if you want, for example, to set the tab width to some non-standard value (the default is 8). As an example, here is the type signature of runParser':

runParser'
  :: Parsec e s a -- ^ Parser to run
  -> State s    -- ^ Initial state
  -> (State s, Either (ParseErrorBundle s e) a)

Modifying State manually is advanced usage of the library, and we are not going to describe it here.

If you are wondering what ParseErrorBundle is, we’ll discuss it in one of the following sections.

The MonadParsec type class

All the tools in megaparsec work with any instance of the MonadParsec type class. The type class abstracts the primitive combinators—the elementary building blocks of all megaparsec parsers, the combinators that cannot be expressed in terms of other combinators.

Having the primitive combinators in a type class allows ParsecT, the principal concrete monad transformer of megaparsec, to be wrapped in the familiar transformers of the MTL family, achieving different interactions between the layers of a monadic stack. To better understand the motivation, recall that the order of the layers in a monadic stack matters. If we combine ReaderT and State like this:

type MyStack a = ReaderT MyContext (State MyState) a

the outer layer, ReaderT, cannot inspect the internal structure of the underlying m layer. The Monad instance for ReaderT describes the binding strategy:

newtype ReaderT r m a = ReaderT { runReaderT :: r -> m a }

instance Monad m => Monad (ReaderT r m) where
  m >>= k = ReaderT $ \r -> do
    a <- runReaderT m r
    runReaderT (k a) r

In fact, the only thing we know about m is that it is an instance of Monad, and so the state of m can only be passed to k via monadic bind. That is what we typically want from (>>=) of ReaderT anyway.

The (<|>) method of the Alternative type class works differently—it “splits” the state, and the two branches of parsing no longer interact, so we get backtracking state in the sense that if the first branch is discarded, changes to its state are discarded as well and cannot influence the second branch (we “backtrack” the state when the first branch fails).

To illustrate, let us see the definition of Alternative for ReaderT:

instance Alternative m => Alternative (ReaderT r m) where
  empty = liftReaderT empty
  ReaderT m <|> ReaderT n = ReaderT $ \r -> m r <|> n r

This is all very nice, because ReaderT is a “stateless” monad transformer and it is easy to delegate the actual work to the inner monad (the Alternative instance of m comes in handy here) without needing to combine the monadic state associated with ReaderT itself (it has none).

Now let’s take a look at State. Since State s a is just a type synonym for StateT s Identity a, we should look at the Alternative instance for StateT s m itself:

instance (Functor m, Alternative m) => Alternative (StateT s m) where
  empty = StateT $ \_ -> empty
  StateT m <|> StateT n = StateT $ \s -> m s <|> n s

Here we can see the splitting of the state s, just like we saw the sharing of the reader context r. There is a difference, though, because the expressions m s and n s produce stateful results: together with the monadic value, they return the new state in a tuple. Here we either go with m s or with n s, naturally achieving backtracking.

What about ParsecT? Let us now consider putting State inside ParsecT like this:

type MyStack a = ParsecT Void Text (State MyState) a

ParsecT is more complex than ReaderT and its implementation of (<|>) has to do more:

• managing the state of the parser itself;
• merging parse errors (when appropriate), should they happen.

The implementation of (<|>) in ParsecT‘s instance of Alternative thus cannot delegate its work to the Alternative instance of the underlying monad State MyState, and so no splitting of MyState happens—we have no backtracking.

Let us demonstrate this with an example:

{-# LANGUAGE OverloadedStrings #-}

module Main (main) where

import Control.Applicative
import Control.Monad.State.Strict
import Data.Text (Text)
import Data.Void
import Text.Megaparsec hiding (State)

type Parser = ParsecT Void Text (State String)

parser0 :: Parser String
parser0 = a <|> b
  where
    a = "foo" <$ put "branch A"
    b = get   <* put "branch B"

parser1 :: Parser String
parser1 = a <|> b
  where
    a = "foo" <$ put "branch A" <* empty
    b = get   <* put "branch B"

main :: IO ()
main = do
  let run p          = runState (runParserT p "" "") "initial"
      (Right a0, s0) = run parser0
      (Right a1, s1) = run parser1

  putStrLn  "Parser 0"
  putStrLn ("Result:      " ++ show a0)
  putStrLn ("Final state: " ++ show s0)

  putStrLn  "Parser 1"
  putStrLn ("Result:      " ++ show a1)
  putStrLn ("Final state: " ++ show s1)

Here is the result of running the program:

Parser 0
Result:      "foo"
Final state: "branch A"
Parser 1
Result:      "branch A"
Final state: "branch B"

With parser0 we can see that the branch b is not tried. With parser1, however, it is clear that the final result—the value returned by get—comes from the branch a, even though it fails because of empty and it is the branch b that succeeds (empty in the context of parsing means “fail instantly and without any information about what has happened”). No backtracking happens.

What to do if we want backtracking custom state in our parser? We can achieve that by wrapping ParsecT inside StateT:

type MyStack a = StateT MyState (ParsecT Void Text Identity) a

Now if we use (<|>) in MyStack, the instance used is that of StateT:

StateT m <|> StateT n = StateT $ \s -> m s <|> n s

This gives us backtracking state and then delegates the rest of the work to the Alternative instance of its inner monad, ParsecT. This behavior is exactly what we want:

{-# LANGUAGE OverloadedStrings #-}

module Main (main) where

import Control.Applicative
import Control.Monad.Identity
import Control.Monad.State.Strict
import Data.Text (Text)
import Data.Void
import Text.Megaparsec hiding (State)

type Parser = StateT String (ParsecT Void Text Identity)

parser :: Parser String
parser = a <|> b
  where
    a = "foo" <$ put "branch A" <* empty
    b = get   <* put "branch B"

main :: IO ()
main = do
  let p            = runStateT parser "initial"
      Right (a, s) = runParser p "" ""
  putStrLn ("Result:      " ++ show a)
  putStrLn ("Final state: " ++ show s)

The program prints:

Result:      "initial"
Final state: "branch B"

To make this approach feasible, StateT should support the whole set of primitive parsers, so that we can work with it just like with ParsecT. In other words, it should be an instance of MonadParsec, just as it is an instance not only of MonadState but also, for example, of MonadWriter when its inner monad is an instance of MonadWriter (in MTL):

instance MonadWriter w m => MonadWriter w (StateT s m) where …

Indeed, we can lift primitives from the inner instance of MonadParsec into StateT:

instance MonadParsec e s m => MonadParsec e s (StateT st m) where …

megaparsec defines instances of MonadParsec for all the MTL monad transformers, so that the user is free to insert the transformers inside ParsecT or wrap ParsecT in those transformers, achieving different kinds of interaction between the layers of a monadic stack.

Lexing

Lexing is the process of transforming the input stream into a stream of tokens—integers, keywords, symbols, etc.—which are easier to parse than the raw input directly, or are expected as input to parsers created with parser generators. Lexing can be performed in a separate pass with an external tool such as alex, but megaparsec also provides functions that should simplify writing a lexer seamlessly, as part of your parser.

There are two lexer modules: Text.Megaparsec.Char.Lexer for character streams and Text.Megaparsec.Byte.Lexer for byte streams. We will be using Text.Megaparsec.Char.Lexer because we work with strict Text as the input stream, but most functions are mirrored in Text.Megaparsec.Byte.Lexer as well, should you wish to work with ByteStrings.

White space

The first topic we need to cover is dealing with white space. It is helpful to consume white space in a consistent manner, either before every token or after every token. Megaparsec’s lexer modules follow the strategy “assume no white space before a token and consume all white space after a token”.

To consume white space we need a special parser that we will refer to as a space consumer. The Text.Megaparsec.Char.Lexer module provides a helper for building a general space consumer:

space :: MonadParsec e s m
  => m () -- ^ A parser for space characters which does not accept empty
          -- input (e.g. 'space1')
  -> m () -- ^ A parser for a line comment (e.g. 'skipLineComment')
  -> m () -- ^ A parser for a block comment (e.g. 'skipBlockComment')
  -> m ()

The documentation for the space function is quite comprehensive on its own, but let us complement it with an example:

{-# LANGUAGE OverloadedStrings #-}

module Main (main) where

import Data.Text (Text)
import Data.Void
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as L -- (1)

type Parser = Parsec Void Text

sc :: Parser ()
sc = L.space
  space1                         -- (2)
  (L.skipLineComment "//")       -- (3)
  (L.skipBlockComment "/*" "*/") -- (4)

Some notes:

• Text.Megaparsec.Char.Lexer is intended to be imported qualified, because it contains names that collide with names from, for example, Text.Megaparsec.Char—space, for one.

• The first argument of L.space should be a parser that is used to pick up white space. An important detail is that it should not accept empty input, because then L.space would go into an infinite loop. space1 is a parser from Text.Megaparsec.Char that meets the requirements perfectly.

• The second argument of L.space defines how to skip line comments, that is, comments that start with a given sequence of tokens and end at the end of the line. The skipLineComment helper allows us to easily craft an auxiliary parser for line comments.

• The third argument of L.space in turn defines how to pick up block comments: everything between a starting and an ending sequence of tokens. The skipBlockComment helper allows us to deal with non-nested block comments. If supporting nested block comments is desirable, skipBlockCommentNested should be used instead.

Operationally, L.space tries all three parsers in turn, as many times as it can, until none of them can be applied anymore, meaning that we have consumed all the white space there is. Knowing this, it should make sense that if your grammar does not include block or line comments, you can just pass empty as the second and/or third argument of L.space. empty, being the identity of (<|>), will just cause L.space to try the parser for the next white space component—exactly what is desired.

With the space consumer sc in hand, we can then define various white space-related helpers:

lexeme :: Parser a -> Parser a
lexeme = L.lexeme sc

symbol :: Text -> Parser Text
symbol = L.symbol sc

• lexeme is a wrapper for lexemes that picks up all trailing white space using the supplied space consumer.

• symbol is a parser that matches given text using string internally and then similarly picks up all trailing white space.

We will see how it all works together in a moment, but first we need to introduce a couple more helpers from Text.Megaparsec.Char.Lexer.

Char and string literals

Parsing character and string literals can be tricky because of various escaping rules. To make life easier, megaparsec provides the charLiteral parser:

charLiteral :: (MonadParsec e s m, Token s ~ Char) => m Char

The job of charLiteral is to parse a single character that may be escaped according to the syntax for character literals described in the Haskell report. Note that it does not parse the quotes around the literal, though, for two reasons:

• so that the user can control how character literals are quoted,
• so that charLiteral can be used to parse string literals as well.

Here are some example parsers built on top of charLiteral:

charLiteral :: Parser Char
charLiteral = between (char '\'') (char '\'') L.charLiteral

stringLiteral :: Parser String
stringLiteral = char '\"' *> manyTill L.charLiteral (char '\"')

• To turn L.charLiteral into a parser for char literals, we only need to add the enclosing quotes. Here we follow Haskell syntax and use single quotes. The between combinator is defined simply as between open close p = open *> p <* close.

• stringLiteral uses L.charLiteral to parse the individual characters inside a string literal enclosed in double quotes.

The second function is also interesting because of its use of the manyTill combinator:

manyTill :: Alternative m => m a -> m end -> m [a]
manyTill p end = go
  where
    go = ([] <$ end) <|> ((:) <$> p <*> go)

manyTill tries to apply the end parser on every iteration, and if it fails, it then runs the p parser and accumulates the results of p in a list.

There is also someTill for when you want to demand that at least one item be present.

Numbers

Finally, a very common need is parsing numbers. For integral numbers, there are three helpers that can parse values in decimal, octal, and hexadecimal representation:

decimal, octal, hexadecimal
  :: (MonadParsec e s m, Token s ~ Char, Num a) => m a

Using them is easy:

integer :: Parser Integer
integer = lexeme L.decimal

λ> parseTest (integer <* eof) "123  "
123

λ> parseTest (integer <* eof) "12a  "
1:3:
  |
1 | 12a
  |   ^
unexpected 'a'
expecting end of input or the rest of integer

scientific accepts integer and fractional grammars, while float accepts only fractional grammars. scientific returns the Scientific type from the scientific package, while float is polymorphic in its result type and can return any instance of RealFloat:

scientific :: (MonadParsec e s m, Token s ~ Char)              => m Scientific
float      :: (MonadParsec e s m, Token s ~ Char, RealFloat a) => m a

For example:

float :: Parser Double
float = lexeme L.float

λ> parseTest (float <* eof) "123"
1:4:
  |
1 | 123
  |    ^
unexpected end of input
expecting '.', 'E', 'e', or digit

λ> parseTest (float <* eof) "123.45"
123.45

λ> parseTest (float <* eof) "123d"
1:4:
  |
1 | 123d
  |    ^
unexpected 'd'
expecting '.', 'E', 'e', or digit

Note that none of these parsers parse signed numbers. To make a parser for signed numbers, we need to wrap an existing parser with the signed combinator:

signedInteger :: Parser Integer
signedInteger = L.signed sc integer

signedFloat :: Parser Double
signedFloat = L.signed sc float

The first argument of signed—the space consumer—controls how white space is consumed between the sign and the actual numeral. If you do not want to allow space there, just pass return () instead.

notFollowedBy and lookAhead

There are two more primitives (in addition to try) that can look ahead in the input stream without actually advancing the parsing position in it.

The first one is called notFollowedBy:

notFollowedBy :: MonadParsec e s m => m a -> m ()

It succeeds only when its argument parser fails, and it never consumes any input or modifies the parser state.

As an example of when you may want to use notFollowedBy, consider parsing keywords:

pKeyword :: Text -> Parser Text
pKeyword keyword = lexeme (string keyword)

This parser has a problem: what if the keyword we are matching against is just a prefix of an identifier? In that case it is definitely not a keyword. We must therefore eliminate that case by using notFollowedBy:

pKeyword :: Text -> Parser Text
pKeyword keyword = lexeme (string keyword <* notFollowedBy alphaNumChar)

Another primitive is lookAhead:

lookAhead :: MonadParsec e s m => m a -> m a

If the argument p of lookAhead succeeds, the whole construct lookAhead p also succeeds but the input stream (and the entire parser state) stays untouched, i.e. nothing is consumed.

One example of where this may be useful is performing a check on an already-parsed value and then either failing or continuing successfully. The idiom can be expressed in code like this:

withPredicate1
  :: (a -> Bool)       -- ^ The check to perform on parsed input
  -> String            -- ^ Message to print when the check fails
  -> Parser a          -- ^ Parser to run
  -> Parser a          -- ^ Resulting parser that performs the check
withPredicate1 f msg p = do
  r <- lookAhead p
  if f r
    then p
    else fail msg

This demonstrates a use of lookAhead, but we should also note that when the check is successful we perform the parsing twice, which is not good. Here is an alternative solution using the getOffset function:

withPredicate2
  :: (a -> Bool)       -- ^ The check to perform on parsed input
  -> String            -- ^ Message to print when the check fails
  -> Parser a          -- ^ Parser to run
  -> Parser a          -- ^ Resulting parser that performs the check
withPredicate2 f msg p = do
  o <- getOffset
  r <- p
  if f r
    then return r
    else do
      setOffset o
      fail msg

This way we just set the offset in the input stream to what it was before running p, and then fail. There is now a mismatch between what remains unconsumed and the offset position, but it does not matter in this case, because we end parsing immediately by calling fail. It may matter in other cases. We will see how to do better in situations like this later in this chapter.

Parsing expressions

By “expression” we mean a structure formed from terms and operators applied to those terms. Operators can be prefix, infix, or postfix, left- or right-associative, and of different precedence. An example of such a construct would be the arithmetic expressions familiar from school:

a * (b + 2)

Here we can see two kinds of terms: variables (a and b) and integers (2). There are also two operators: * and +.

Writing an expression parser may take a while to get right. To help with that, the parser-combinators package comes with the Control.Monad.Combinators.Expr module, which exports only two things: the Operator data type and the makeExprParser helper. Both are well documented, so in this section we will not repeat the documentation; instead, we are going to write a simple but fully functional expression parser.

Let’s start by defining a data type that represents an expression as an AST:

data Expr
  = Var String
  | Int Int
  | Negation Expr
  | Sum      Expr Expr
  | Subtr    Expr Expr
  | Product  Expr Expr
  | Division Expr Expr
  deriving (Eq, Ord, Show)

To use makeExprParser we need to provide it with a term parser and an operator table:

makeExprParser :: MonadParsec e s m
  => m a               -- ^ Term parser
  -> [[Operator m a]]  -- ^ Operator table, see 'Operator'
  -> m a               -- ^ Resulting expression parser

Let’s start with the term parser. It is helpful to think of a term as a box that is to be treated as an indivisible whole by the expression-parsing algorithm when it works with things like associativity and precedence. In our case there are three things that fall into this category: variables, integers, and entire expressions in parentheses. Using the definitions from previous chapters, we can define the term parser as:

pVariable :: Parser Expr
pVariable = Var <$> lexeme
  ((:) <$> letterChar <*> many alphaNumChar <?> "variable")

pInteger :: Parser Expr
pInteger = Int <$> lexeme L.decimal

parens :: Parser a -> Parser a
parens = between (symbol "(") (symbol ")")

pTerm :: Parser Expr
pTerm = choice
  [ parens pExpr
  , pVariable
  , pInteger
  ]

pExpr :: Parser Expr
pExpr = makeExprParser pTerm operatorTable

operatorTable :: [[Operator Parser Expr]]
operatorTable = undefined -- TODO

The definitions of pVariable, pInteger, and parens should be clear by now. We are also quite lucky here in that we do not need any trys in pTerm, because the grammars do not overlap:

• if we see an opening parenthesis (, we know that an expression in parentheses is to follow, so we commit to that branch;

• if we see a letter, we know that it is the start of an identifier;

• if we see a digit, we know that it is the start of an integer.

Finally, to finish pExpr we need to define the operatorTable. We can see from the type that it is a nested list. Every inner list is a list of operators we want to support; they all have equal precedence. The outer list is ordered by descending precedence, so the higher we place a group of operators in it, the tighter they bind:

data Operator m a -- N.B.
  = InfixN  (m (a -> a -> a)) -- ^ Non-associative infix
  | InfixL  (m (a -> a -> a)) -- ^ Left-associative infix
  | InfixR  (m (a -> a -> a)) -- ^ Right-associative infix
  | Prefix  (m (a -> a))      -- ^ Prefix
  | Postfix (m (a -> a))      -- ^ Postfix

operatorTable :: [[Operator Parser Expr]]
operatorTable =
  [ [ prefix "-" Negation
    , prefix "+" id
    ]
  , [ binary "*" Product
    , binary "/" Division
    ]
  , [ binary "+" Sum
    , binary "-" Subtr
    ]
  ]

binary :: Text -> (Expr -> Expr -> Expr) -> Operator Parser Expr
binary  name f = InfixL  (f <$ symbol name)

prefix, postfix :: Text -> (Expr -> Expr) -> Operator Parser Expr
prefix  name f = Prefix  (f <$ symbol name)
postfix name f = Postfix (f <$ symbol name)

Note how we place Parser (Expr -> Expr -> Expr) inside InfixL in binary, and similarly Parser (Expr -> Expr) in prefix and postfix. That is, we run symbol name and return a function to apply to the terms in order to get the final result of type Expr.

We can now try our parser—it is ready!

λ> parseTest (pExpr <* eof) "a * (b + 2)"
Product (Var "a") (Sum (Var "b") (Int 2))

λ> parseTest (pExpr <* eof) "a * b + 2"
Sum (Product (Var "a") (Var "b")) (Int 2)

λ> parseTest (pExpr <* eof) "a * b / 2"
Division (Product (Var "a") (Var "b")) (Int 2)

λ> parseTest (pExpr <* eof) "a * (b $ 2)"
1:8:
  |
1 | a * (b $ 2)
  |        ^
unexpected '$'
expecting ')' or operator

The documentation for the Control.Monad.Combinators.Expr module contains some hints that are useful in certain less standard situations, so it is a good idea to read it as well.

Indentation-sensitive parsing

The Text.Megaparsec.Char.Lexer module contains tools that should be helpful when parsing indentation-sensitive grammars. We are going to review the available combinators first, and then put them to use by writing an indentation-sensitive parser.

nonIndented and indentBlock

Let’s start with the simplest thing—nonIndented:

nonIndented :: (TraversableStream s, MonadParsec e s m)
  => m ()              -- ^ How to consume indentation (white space)
  -> m a               -- ^ Inner parser
  -> m a

It allows us to make sure that its inner parser consumes input that is not indented. It is part of the model behind high-level parsing of indentation-sensitive input. We state that there are top-level items that are not indented and that all indented tokens are directly or indirectly children of those top-level definitions. In megaparsec, we do not need any additional state to express this. Since indentation is always relative, our idea is to explicitly tie together the parsers for reference tokens and indented tokens, thus defining an indentation-sensitive grammar via a pure combination of parsers.

So, how do we define a parser for an indented block? Let’s take a look at the signature of indentBlock:

indentBlock :: (TraversableStream s, MonadParsec e s m, Token s ~ Char)
  => m ()              -- ^ How to consume indentation (white space)
  -> m (IndentOpt m a b) -- ^ How to parse “reference” token
  -> m a

First, we specify how to consume indentation. An important thing to note here is that this space-consuming parser must consume newlines as well, while tokens (the reference token and the indented tokens) should not normally consume newlines after them.

As you can see, the second argument allows us to parse the reference token and return a data structure that tells indentBlock what to do next. There are several options:

data IndentOpt m a b
  = IndentNone a
    -- ^ Parse no indented tokens, just return the value
  | IndentMany (Maybe Pos) ([b] -> m a) (m b)
    -- ^ Parse many indented tokens (possibly zero), use given indentation
    -- level (if 'Nothing', use level of the first indented token); the
    -- second argument tells how to get the final result, and the third
    -- argument describes how to parse an indented token
  | IndentSome (Maybe Pos) ([b] -> m a) (m b)
    -- ^ Just like 'IndentMany', but requires at least one indented token to
    -- be present

We can change our mind and parse no indented tokens, we can parse many (that is, possibly zero) indented tokens, or we can require at least one such token. We can either allow indentBlock to detect the indentation level of the first indented token and use that, or specify the indentation level manually.

Parsing a simple indented list

Let’s parse a simple indented list of some items. We begin with the import section:

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TupleSections     #-}

module Main (main) where

import Control.Applicative hiding (some)
import Control.Monad (void)
import Data.Text (Text)
import Data.Void
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as L

type Parser = Parsec Void Text

We will need two kinds of space consumer: one that consumes newlines, scn, and one that does not, sc (here it actually only parses spaces and tabs):

lineComment :: Parser ()
lineComment = L.skipLineComment "#"

scn :: Parser ()
scn = L.space space1 lineComment empty

sc :: Parser ()
sc = L.space (void $ some (char ' ' <|> char '\t')) lineComment empty

lexeme :: Parser a -> Parser a
lexeme = L.lexeme sc

Just for fun, we allow line comments that start with #.

pItemList is a top-level form that is itself a combination of a reference token (the list header) and indented tokens (the list items), so:

pItemList :: Parser (String, [String]) -- header and list items
pItemList = L.nonIndented scn (L.indentBlock scn p)
  where
    p = do
      header <- pItem
      return (L.IndentMany Nothing (return . (header, )) pItem)

For our purposes, an item is a sequence of alphanumeric characters and dashes:

pItem :: Parser String
pItem = lexeme (some (alphaNumChar <|> char '-')) <?> "list item"

Let’s load the code into GHCi and try it with the help of the built-in parseTest:

λ> parseTest (pItemList <* eof) ""
1:1:
  |
1 | <empty line>
  | ^
unexpected end of input
expecting list item

λ> parseTest (pItemList <* eof) "something"
("something",[])

λ> parseTest (pItemList <* eof) "  something"
1:3:
  |
1 |   something
  |   ^
incorrect indentation (got 3, should be equal to 1)

λ> parseTest (pItemList <* eof) "something\none\ntwo\nthree"
2:1:
  |
2 | one
  | ^
unexpected 'o'
expecting end of input

Remember that we are using the IndentMany option, so empty lists are OK; on the other hand, the built-in combinator space has hidden the phrase “expecting more space” from error messages, so this error message is perfectly reasonable.

Let’s continue:

λ> parseTest (pItemList <* eof) "something\n  one\n    two\n  three"
3:5:
  |
3 |     two
  |     ^
incorrect indentation (got 5, should be equal to 3)

λ> parseTest (pItemList <* eof) "something\n  one\n  two\n three"
4:2:
  |
4 |  three
  |  ^
incorrect indentation (got 2, should be equal to 3)

λ> parseTest (pItemList <* eof) "something\n  one\n  two\n  three"
("something",["one","two","three"])

Let’s replace IndentMany with IndentSome and Nothing with Just (mkPos 5) (indentation levels are counted from 1, so this will require 4 spaces before the indented items):

pItemList :: Parser (String, [String])
pItemList = L.nonIndented scn (L.indentBlock scn p)
  where
    p = do
      header <- pItem
      return (L.IndentSome (Just (mkPos 5)) (return . (header, )) pItem)

Now:

λ> parseTest (pItemList <* eof) "something\n"
2:1:
  |
2 | <empty line>
  | ^
incorrect indentation (got 1, should be greater than 1)

λ> parseTest (pItemList <* eof) "something\n  one"
2:3:
  |
2 |   one
  |   ^
incorrect indentation (got 3, should be equal to 5)

λ> parseTest (pItemList <* eof) "something\n    one"
("something",["one"])

The first message may be a bit surprising, but megaparsec knows that there must be at least one item in the list, so it checks the indentation level; it is 1, which is incorrect, so it reports it.

Nested indented list

Let’s allow list items to have subitems. For this we will need a new parser, pComplexItem:

pComplexItem :: Parser (String, [String])
pComplexItem = L.indentBlock scn p
  where
    p = do
      header <- pItem
      return (L.IndentMany Nothing (return . (header, )) pItem)

pItemList :: Parser (String, [(String, [String])])
pItemList = L.nonIndented scn (L.indentBlock scn p)
  where
    p = do
      header <- pItem
      return (L.IndentSome Nothing (return . (header, )) pComplexItem)

If we feed something like this:

first-chapter
  paragraph-one
      note-A # an important note here!
      note-B
  paragraph-two
    note-1
    note-2
  paragraph-three

into our parser, we will get:

Right
  ( "first-chapter"
  , [ ("paragraph-one",   ["note-A","note-B"])
    , ("paragraph-two",   ["note-1","note-2"])
    , ("paragraph-three", [])
    ]
  )

This demonstrates how this approach scales to nested indented constructs without requiring additional state.

Adding line folds

A line fold consists of several elements that can be put on one line or on several lines as long as the indentation level of the subsequent items is greater than the indentation level of the first item.

Let’s make use of another helper called lineFold:

pComplexItem :: Parser (String, [String])
pComplexItem = L.indentBlock scn p
  where
    p = do
      header <- pItem
      return (L.IndentMany Nothing (return . (header, )) pLineFold)

pLineFold :: Parser String
pLineFold = L.lineFold scn $ \sc' ->
  let ps = some (alphaNumChar <|> char '-') `sepBy1` try sc'
  in unwords <$> ps <* scn -- (1)

lineFold works like this: we give it a space consumer that accepts newlines, scn, and it gives back a special space consumer, sc', that we can use in the callback to consume space between the elements of the line fold.

Why use try sc' and scn on line (1)? The situation is the following:

• The components of a line fold can only be more indented than its start.
• sc' consumes white space, including newlines, in such a way that after consuming white space the column number is greater than the initial column.
• To stop, sc' should encounter the opposite situation; that is, the column number after consumption should be less than or equal to the initial column. At that point it fails without consuming input (thanks to try), and scn is used to pick up the white space before the new thing that will start at that column.
• The sc' we used previously already probed the white space with a space consumer that consumes newlines. So it is only logical to consume newlines when picking up trailing white space too. This is why scn, and not sc, is used on line (1).

EXERCISE: Playing with the final version of our parser is left as an exercise for the reader. You can create “items” that consist of multiple words, and as long as they are line-folded they will be parsed and concatenated with a single space between them.

Writing efficient parsers

Let’s discuss what to try in order to improve the performance of a megaparsec parser. It should be noted right away that one should always verify any improvement through profiling and benchmarking. That is the only way to know whether we are doing the right thing when tuning performance.

Some common pieces of advice:

• If your parser uses a monad stack instead of the plain Parsec monad (recall that it is the ParsecT monad transformer over Identity, which is quite lightweight), make sure you use at least version 0.5 of the transformers library and at least version 7.0 of megaparsec. Both libraries have critical performance improvements in these versions, so you can get better performance for free.

• The Parsec monad will always be faster than ParsecT-based monad transformers. Avoid using StateT, WriterT, and other monad transformers unless absolutely necessary. The more you add to the monadic stack, the slower your parser will be.

• Backtracking is an expensive operation. Avoid building long chains of alternatives where every alternative can go deep into the input before failing.

• Do not keep your parsers polymorphic unless you really have a reason to do so. It is best to fix the types of parsers by specifying concrete types, such as type Parser = Parsec Void Text, for every top-level definition. This way GHC will be able to optimize better.

• Inline generously (when it makes sense, of course). You may not believe your eyes when you see how much of a difference inlining can make, especially for short functions. This is particularly true for parsers that are defined in one module and used in another, because the INLINE and INLINEABLE pragmas make GHC dump function definitions into interface files, and this facilitates specializing.

• Use the fast primitives such as takeWhileP, takeWhile1P, and takeP whenever you can. This blog post explains why they are so fast.

• Avoid oneOf and noneOf, preferring satisfy and anySingleBut whenever possible.

While most of the points above do not require additional comment, I think it would be beneficial to get into the habit of using the newer fast primitives: takeWhileP, takeWhile1P, and takeP. The first two are especially common, as they allow us to replace many- and some-based constructs, making them faster and changing the type of the returned data to a chunk of the input stream, i.e. the Tokens s type we discussed previously.

For example, recall that when we parsed URIs, we had this code for parsing the username in the authority component:

  user <- T.pack <$> some alphaNumChar

We can replace it with takeWhile1P:

  user <- takeWhile1P (Just "alpha num character") isAlphaNum
  --                  ^                            ^
  --                  |                            |
  -- label for tokens we match against         predicate

When we parse ByteStrings and Text, this will be a lot faster than the original approach. Also note that T.pack is no longer necessary, as we get Text directly from takeWhile1P.

These equations may be helpful for understanding the meaning of the Maybe String argument of takeWhileP and takeWhile1P:

takeWhileP  (Just "foo") f = many (satisfy f <?> "foo")
takeWhileP  Nothing      f = many (satisfy f)
takeWhile1P (Just "foo") f = some (satisfy f <?> "foo")
takeWhile1P Nothing      f = some (satisfy f)

Parse errors

Now that we have explored how to use most of the features of megaparsec, it is time to learn more about parse errors: how they are defined, how to signal them, and how to process them inside a running parser.

Parse error definitions

The ParseError type is defined like this:

data ParseError s e
  = TrivialError Int (Maybe (ErrorItem (Token s))) (Set (ErrorItem (Token s)))
    -- ^ Trivial errors, generated by Megaparsec's machinery. The data
    -- constructor includes the offset of error, unexpected token (if any),
    -- and expected tokens.
  | FancyError Int (Set (ErrorFancy e))
    -- ^ Fancy, custom errors.

In English: a ParseError is either a TrivialError, with at most one unexpected item and a (possibly empty) collection of expected items, or a FancyError.

ParseError s e is parametrized over two type variables:

• s is the type of the input stream.
• e is the type of the custom component of the parse error.

ErrorItem is defined as:

data ErrorItem t
  = Tokens (NonEmpty t)      -- ^ Non-empty stream of tokens
  | Label (NonEmpty Char)    -- ^ Label (cannot be empty)
  | EndOfInput               -- ^ End of input

NonEmpty is a type for non-empty lists; it comes from Data.List.NonEmpty. And here is ErrorFancy:

data ErrorFancy e
  = ErrorFail String
    -- ^ 'fail' has been used in parser monad
  | ErrorIndentation Ordering Pos Pos
    -- ^ Incorrect indentation error: desired ordering between reference
    -- level and actual level, reference indentation level, actual
    -- indentation level
  | ErrorCustom e
    -- ^ Custom error data, can be conveniently disabled by indexing
    -- 'ErrorFancy' by 'Void'

ErrorFancy includes data constructors for two common cases that megaparsec supports out of the box:

• Use of the fail function, which causes the parser to fail, reporting an arbitrary String.

• Indentation-related issues, which we saw in a previous section. Since we provide tools for working with indentation-sensitive grammars out of the box, we need a way to store well-typed information about problems with indentation.

Finally, ErrorCustom is a sort of “extension slot” that allows us to embed arbitrary data into the ErrorFancy type. When we do not need any custom data in our parse errors, we parametrize ErrorFancy by Void. Since Void is not inhabited by non-bottom values, ErrorCustom becomes “cancelled out” or, if we follow the analogy between algebraic data types and numbers, “multiplied by zero”.

In older versions of the library, ParseErrors were returned directly by functions like parse, but version 7 delays the calculation of the line and column for each error, as well as the fetching of the relevant input line for display in case of an error. This is done to make parsing faster, because all this information is usually useful only when a parser fails. Another problem with older versions of the library is that displaying several parse errors at once required re-traversing the input each time to fetch the right line.

The problem is solved with the ParseErrorBundle data type:

-- | A non-empty collection of 'ParseError's equipped with 'PosState' that
-- allows to pretty-print the errors efficiently and correctly.

data ParseErrorBundle s e = ParseErrorBundle
  { bundleErrors :: NonEmpty (ParseError s e)
    -- ^ A collection of 'ParseError's that is sorted by parse error offsets
  , bundlePosState :: PosState s
    -- ^ State that is used for line\/column calculation
  }

All parser-running functions return a ParseErrorBundle with a correctly set bundlePosState and a collection of ParseErrors inside.

How to signal a parse error

Let’s discuss different ways to signal a parse error. The simplest function for that is fail:

λ> parseTest (fail "I'm failing, help me!" :: Parser ()) ""
1:1:
  |
1 | <empty line>
  | ^
I'm failing, help me!

For many people who are familiar with simpler parsing libraries such as parsec, this is often enough. However, displaying a parse error to the user is not everything; we may need to analyze and/or manipulate it. This is where Strings are not very convenient.

Trivial parse errors are usually generated by megaparsec, but we can signal any such error ourselves using the failure combinator:

failure :: MonadParsec e s m
  => Maybe (ErrorItem (Token s)) -- ^ Unexpected item (if any)
  -> Set (ErrorItem (Token s)) -- ^ Expected items
  -> m a

unfortunateParser :: Parser ()
unfortunateParser = failure (Just EndOfInput) (Set.fromList es)
  where
    es = [Tokens (NE.fromList "a"), Tokens (NE.fromList "b")]

λ> parseTest unfortunateParser ""
1:1:
  |
1 | <empty line>
  | ^
unexpected end of input
expecting 'a' or 'b'

Unlike the fail-based approach, trivial parse errors are easy to pattern-match on, inspect, and modify.

For fancy errors we correspondingly have the fancyFailure combinator:

fancyFailure :: MonadParsec e s m
  => Set (ErrorFancy e) -- ^ Fancy error components
  -> m a

With fancyFailure, it is often desirable to define a helper like the one we have in the lexer modules instead of calling fancyFailure directly:

incorrectIndent :: MonadParsec e s m
  => Ordering  -- ^ Desired ordering between reference level and actual level
  -> Pos               -- ^ Reference indentation level
  -> Pos               -- ^ Actual indentation level
  -> m a
incorrectIndent ord ref actual = fancyFailure . Set.singleton $
  ErrorIndentation ord ref actual

As an example of adding a custom parse error component to your parser, let’s go through defining a special parse error that says that a given Text value is not a keyword.

First, we need to define the data type, with constructors representing the scenarios we want to support:

data Custom = NotKeyword Text
  deriving (Eq, Show, Ord)

And tell megaparsec how to display it in parse errors:

instance ShowErrorComponent Custom where
  showErrorComponent (NotKeyword txt) = T.unpack txt ++ " is not a keyword"

Next we update our Parser type synonym:

type Parser = Parsec Custom Text

After that we can define the notKeyword helper:

notKeyword :: Text -> Parser a
notKeyword = customFailure . NotKeyword

Where customFailure is a useful helper that comes from the Text.Megaparsec module:

customFailure :: MonadParsec e s m => e -> m a
customFailure = fancyFailure . E.singleton . ErrorCustom

Finally, let us try it:

λ> parseTest (notKeyword "foo" :: Parser ()) ""
1:1:
  |
1 | <empty line>
  | ^
foo is not a keyword

Displaying parse errors

Displaying of ParseErrorBundles is done with the errorBundlePretty function:

-- | Pretty-print a 'ParseErrorBundle'. All 'ParseError's in the bundle will
-- be pretty-printed in order together with the corresponding offending
-- lines by doing a single efficient pass over the input stream. The
-- rendered 'String' always ends with a newline.

errorBundlePretty
  :: ( VisualStream s
     , TraversableStream s
     , ShowErrorComponent e
     )
  => ParseErrorBundle s e -- ^ Parse error bundle to display
  -> String               -- ^ Textual rendition of the bundle

In 99% of cases this is the only function you will need.

Catching parse errors in a running parser

Another useful feature of megaparsec is that it is possible to “catch” a parse error, alter it in some way, and then re-throw it, just like with exceptions. This is enabled by the observing primitive:

-- | @'observing' p@ allows to “observe” failure of the @p@ parser, should
-- it happen, without actually ending parsing, but instead getting the
-- 'ParseError' in 'Left'. On success parsed value is returned in 'Right'
-- as usual. Note that this primitive just allows you to observe parse
-- errors as they happen, it does not backtrack or change how the @p@
-- parser works in any way.

observing :: MonadParsec e s m
  => m a             -- ^ The parser to run
  -> m (Either (ParseError (Token s) e) a)

Here is a complete program demonstrating typical usage of observing:

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TypeApplications  #-}

module Main (main) where

import Control.Applicative hiding (some)
import Data.List (intercalate)
import Data.Set (Set)
import Data.Text (Text)
import Data.Void
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Data.Set as Set

data Custom
  = TrivialWithLocation
    [String] -- position stack
    (Maybe (ErrorItem Char))
    (Set (ErrorItem Char))
  | FancyWithLocation
    [String] -- position stack
    (ErrorFancy Void) -- Void, because we do not want to allow to nest Customs
  deriving (Eq, Ord, Show)

instance ShowErrorComponent Custom where
  showErrorComponent (TrivialWithLocation stack us es) =
    parseErrorTextPretty (TrivialError @Text @Void undefined us es)
      ++ showPosStack stack
  showErrorComponent (FancyWithLocation stack cs) =
    parseErrorTextPretty (FancyError @Text @Void undefined (Set.singleton cs))
      ++ showPosStack stack

showPosStack :: [String] -> String
showPosStack = intercalate ", " . fmap ("in " ++)

type Parser = Parsec Custom Text

inside :: String -> Parser a -> Parser a
inside location p = do
  r <- observing p
  case r of
    Left (TrivialError _ us es) ->
      fancyFailure . Set.singleton . ErrorCustom $
        TrivialWithLocation [location] us es
    Left (FancyError _ xs) -> do
      let f (ErrorFail msg) = ErrorCustom $
            FancyWithLocation [location] (ErrorFail msg)
          f (ErrorIndentation ord rlvl alvl) = ErrorCustom $
            FancyWithLocation [location] (ErrorIndentation ord rlvl alvl)
          f (ErrorCustom (TrivialWithLocation ps us es)) = ErrorCustom $
            TrivialWithLocation (location:ps) us es
          f (ErrorCustom (FancyWithLocation ps cs)) = ErrorCustom $
            FancyWithLocation (location:ps) cs
      fancyFailure (Set.map f xs)
    Right x -> return x

myParser :: Parser String
myParser = some (char 'a') *> some (char 'b')

main :: IO ()
main = do
  parseTest (inside "foo" myParser) "aaacc"
  parseTest (inside "foo" $ inside "bar" myParser) "aaacc"