Links

• Parsing CSS with Parsec is a very to-the-point tutorial and I recommend looking at it first – it's possible that after reading it you'll understand how to do parsing without any lengthy explanations. It's about Parsec, not Megaparsec, but the only difference is in combinator names (e.g. many1 should be some).

• Why Megaparsec was created and how it's better
• Switching from Parsec to Megaparsec
• An example of parsing a simple language
• How to do indentation-sensitive parsing

• official site
• list of tutorials

Imports

import Text.Megaparsec
import Text.Megaparsec.String    -- or Text / Text.Lazy / etc

Additionally, if you're going to use number parsers (e.g. integer):

import Text.Megaparsec.Lexer

A long, very basic example

(Only read it if you were left confused by Parsing CSS with Parsec.)

Parsers work like this:

• A parser consumes a piece of string and turns it into a value. Parser a returns a value of type a.

• If you combine parsers with >> or do, they get applied one-by-one (the 2nd parser would start consuming string from the place where the 1st parser stopped).

• If you combine parsers with <|>, they will be applied to the same pieces of string, but the 2nd parser would only be tried if the 1st parser fails.

Let's say you have something that is either a pair or a triplet of numbers, and has to be enclosed into double parens: ((1,2)) or ((1,2,3)). We'll represent it with Vec:

data Vec = V2 Integer Integer
         | V3 Integer Integer Integer
  deriving Show

Let's write a parser for Vec. First of all, notice that the parens are the same in both cases, and so we can write a special function for parsing something inside double parens:

doubleParens :: Parser a -> Parser a
doubleParens p = between (string "((") (string "))") p

between is a combinator available in Megaparsec. There are many such combinators – you can find the whole list in Text.Megaparsec.Combinator.

Next, parsers for V2 and V3:

v2 :: Parser Vec
v2 = doubleParens $ do
  a <- integer
  char ','
  b <- integer
  return (V2 a b)

v3 :: Parser Vec
v3 = doubleParens $ do
  a <- integer
  char ','
  b <- integer
  char ','
  c <- integer
  return (V3 a b c)

Once we have those 2 parsers, we can combine them:

vec :: Parser Vec
vec = try v2 <|> v3

try means that if v2 consumes some input and then fails, the next parser (i.e. v3) will be tried. By default Megaparsec only tries the next parser if the previous one fails without consuming any input, which gives you more control over how your parser behaves. (There are some parsing libraries that do automatic backtracking (i.e. when a parser fails, even at the last step, they always go back in time and try other parsers), but Megaparsec doesn't do it.)

To actually use the parser, we need parse:

parse
  :: Parser a
  -> String            	    -- Filepath (can be "")
  -> String                 -- String that is being parsed
  -> Either ParseError a	 

(The actual signature is more general because it can also work on Text and so on.)

> parse vec "" "((3,12))"
Right (V2 3 12)

What would happen if the input is bad?

> parse vec "" "1,2))"

Left line 1, column 1:
unexpected '1'
expecting "(("

> parse vec "" "((3,12,))"

Left line 1, column 7:
unexpected ','
expecting "))" or rest of integer

> parse vec "" "((1,a))"

Left line 1, column 5:
unexpected 'a'
expecting integer

By the way, there's a bit more repetition in our parsers that we could eliminate – specifically, parsing the first 2 numbers:

vec :: Parser Vec
vec = doubleParens $ do
  a <- integer
  char ','
  b <- integer
  choice [
    do char ','
       c <- integer
       return (V3 a b c),
    return (V2 a b) ]

Here we used choice, which is like <|> but for many parsers instead of just 2.

Links

• Parsing log files with Attoparsec

Imports

For parsing ByteString:

import Control.Applicative
import Data.Attoparsec.ByteString

For parsing Text:

import Control.Applicative
import Data.Attoparsec.Text

Helpers

This function modifies a parser to print some info about it (namely, what it has consumed, remaining input, and the value it has parsed):

import Debug.Trace
import Data.Attoparsec.Combinators

debug :: Show a => Parser a -> Parser a
debug p = do
  (consumed, a) <- match p
  remaining <- lookAhead takeText
  traceM ("result    : " ++ show a)
  traceM ("consumed  : " ++ show consumed)
  traceM ("remaining : " ++ show remaining)
  return a

Imports

import Control.Applicative
import Text.Trifecta

Gotchas

If you want to parse Text, either convert it to String or do something like this.

Imports

import Text.ParserCombinators.ReadP

Or if you have Control.Applicative imported, write it like this to avoid clashes:

import Control.Applicative
import Text.ParserCombinators.ReadP hiding (many, optional)

Usage

It might not be obvious how to run a parser, so:

-- Return all possible parses
parse :: ReadP a -> String -> [(a, String)]
parse = readP_to_S

-- Return all possible parses, and additionally require all input to be consumed
parseAll :: ReadP a -> String -> [a]
parseAll p = map fst . readP_to_S (p <* eof)

Gotchas

many is rather inefficient because it's nondeterministic and so all alternatives (0 elements consumed, 1 element consumed, 2 elements consumed, etc) have to be considered:

p = (,) <$> many (satisfy isLetter)
        <*> many (satisfy isUpper)

> map fst $ readP_to_S (p <* eof) "abcXYZ"
[("abc","XYZ"),
 ("abcX","YZ"),
 ("abcXY","Z"),
 ("abcXYZ","")]

If you know you wouldn't need this, use munch or munch1, it will be much faster. (Also note that in this example you'll get ("abcXYZ",""), not ("abc","XYZ"), if you use munch, but this is to be expected – just like with many in Parsec.)

Other combinators are non-deterministic too, which can sometimes lead to unexpected issues.

Links

• Implementation notes
• Examples

Imports and pragmas

{-# LANGUAGE RecursiveDo #-}

import Control.Applicative
import Text.Earley
-- If you want to construct a parser for a language with operators
import Text.Earley.Mixfix

Usage

The type for parsers is Prod:

data Prod
       r    -- A phantom variable, like “s” in “ST s a”
       e    -- Type for names of parsers
       t    -- Type for characters (e.g. Char or Word8 or some Token)
       a    -- Result of the parser

e is usually going to be String even if you're parsing e.g. Text. t will be Char for String and Text, and SomeToken if you have previously lexed/tokenized your input. It's usual to define a type synonym like this:

type Parser r a = Prod r String Char a

Writing parsers with Earley is similar to Parsec, with 2 major differences:

• You can't use do and monadic parsing – for instance, it's impossible to write a parser that would parse a prime number, while with Parsec it's easy.

• You're given much less combinators by default and so you have to write many things (between, etc) by yourself.

If a parser depends on itself, it will loop. To avoid that, you have to define recursive parsers in the context of Grammar:

data Term = Number Integer | Add Term Term
  deriving Show

grammar :: Grammar r (Parser r Term)
grammar = mdo
  let number = Number <$> integer
  add <- rule $
    Add <$> term <*> (word "+" *> number)
  term <- rule $
    number <|> add
  return term

(word is the same as string in Parsec.)

As you can see, you can define parsers that depend on each other, but all such parsers have to be marked with rule.

To run a Grammar, use fullParses:

> let (parses, rep) = fullParses (parser grammar) "1+2+3"

> parses
[Add (Add (Number 1) (Number 2))
     (Number 3)]

> rep
Report {position = 5, expected = [], unconsumed = ""})

You can also use allParses to get partial parses as well, or report to see how much of the input the parser can consume without actually getting all parses.

Note that our grammar is left-recursive, but Earley was still able to parse it. The model of parsing you might have if you know Parsec is inapplicable to Earley.

Also note that there can be several parses. For instance, if we changed the definition of add to

  add <- rule $
    Add <$> term <*> (word "+" *> term)

we'd get the following parses:

> fst $ fullParses (parser grammar) "1+2+3"
[ Add (Add (Number 1) (Number 2))
      (Number 3)
, Add (Number 1)
      (Add (Number 2) (Number 3))]

Mixfix parsing

See Text.Earley.Mixfix and this example.

(TODO: write a better example here.)

add something!

add something!

add something!