Home

Awesome

Megaparsec

License FreeBSD Hackage Stackage Nightly Stackage LTS CI

This is an industrial-strength monadic parser combinator library. Megaparsec is a feature-rich package that tries to find a nice balance between speed, flexibility, and quality of parse errors.

Features

The project provides flexible solutions to satisfy common parsing needs. The section describes them shortly. If you're looking for comprehensive documentation, see the section about documentation.

Core features

The package is built around MonadParsec, an MTL-style monad transformer. Most features work with all instances of MonadParsec. One can achieve various effects combining monad transformers, i.e. building a monadic stack. Since the common monad transformers like WriterT, StateT, ReaderT and others are instances of the MonadParsec type class, one can also wrap ParsecT in these monads, achieving, for example, backtracking state.

On the other hand ParsecT is an instance of many type classes as well. The most useful ones are Monad, Applicative, Alternative, and MonadParsec.

Megaparsec includes all functionality that is typically available in Parsec-like libraries and also features some special combinators:

In addition to that, Megaparsec features high-performance combinators similar to those found in Attoparsec:

Megaparsec is about as fast as Attoparsec if you write your parser carefully (see also the section about performance).

The library can currently work with the following types of input stream out-of-the-box:

It's also possible to make it work with custom token streams by making them an instance of the Stream type class.

Error messages

External lexers

Megaparsec works well with streams of tokens produced by tools like Alex. The design of the Stream type class has been changed significantly in the recent versions, but user can still work with custom streams of tokens.

Character and binary parsing

Megaparsec has decent support for Unicode-aware character parsing. Functions for character parsing live in the Text.Megaparsec.Char module. Similarly, there is Text.Megaparsec.Byte module for parsing streams of bytes.

Lexer

Text.Megaparsec.Char.Lexer is a module that should help you write your lexer. If you have used Parsec in the past, this module “fixes” its particularly inflexible Text.Parsec.Token.

Text.Megaparsec.Char.Lexer is intended to be imported using a qualified import, it's not included in Text.Megaparsec. The module doesn't impose how you should write your parser, but certain approaches may be more elegant than others. An especially important theme is parsing of white space, comments, and indentation.

The design of the module allows one quickly solve simple tasks and doesn't get in the way when the need to implement something less standard arises.

Text.Megaparsec.Byte.Lexer is also available for users who wish to parse binary data.

Documentation

Megaparsec is well-documented. See the current version of Megaparsec documentation on Hackage.

Tutorials

You can find the most complete Megaparsec tutorial here. It should provide sufficient guidance to help you start with your parsing tasks.

Performance

Despite being flexible, Megaparsec is also fast. Here is how Megaparsec compares to Attoparsec (the fastest widely used parsing library in the Haskell ecosystem):

Test caseExecution timeAllocatedMax residency
CSV (Attoparsec)76.50 μs397,78410,544
CSV (Megaparsec)64.69 μs352,4089,104
Log (Attoparsec)302.8 μs1,150,03210,912
Log (Megaparsec)337.8 μs1,246,49610,912
JSON (Attoparsec)18.20 μs128,3689,032
JSON (Megaparsec)25.45 μs203,8249,176

You can run the benchmarks yourself by executing:

$ nix-build -A benches.parsers-bench
$ cd result/bench
$ ./bench-memory
$ ./bench-speed

More information about benchmarking and development can be found here.

Comparison with other solutions

There are quite a few libraries that can be used for parsing in Haskell, let's compare Megaparsec with some of them.

Megaparsec vs Attoparsec

Attoparsec is another prominent Haskell library for parsing. Although both libraries deal with parsing, it's usually easy to decide which you will need in particular project:

So, if you work with something human-readable where the size of input data is moderate, it makes sense to go with Megaparsec, otherwise Attoparsec may be a better choice.

Megaparsec vs Parsec

Since Megaparsec is a fork of Parsec, we are bound to list the main differences between the two libraries:

If you want to see a detailed change log, CHANGELOG.md may be helpful. Also see this original announcement for another comparison.

Megaparsec vs Trifecta

Trifecta is another Haskell library featuring good error messages. These are the common reasons why Trifecta may be problematic to use:

Idris has switched from Trifecta to Megaparsec which allowed it to have better error messages and fewer dependencies.

Megaparsec vs Earley

Earley is a newer library that allows us to safely parse context-free grammars (CFG). Megaparsec is a lower-level library compared to Earley, but there are still enough reasons to choose it:

In other words, Megaparsec is less safe but also more powerful.

Related packages

The following packages are designed to be used with Megaparsec (open a PR if you want to add something to the list):

Prominent projects that use Megaparsec

Some prominent projects that use Megaparsec:

Links to announcements and blog posts

Here are some blog posts mainly announcing new features of the project and describing what sort of things are now possible:

Contribution

Issues (bugs, feature requests or otherwise feedback) may be reported in the GitHub issue tracker for this project.

Pull requests are also welcome. If you would like to contribute to the project, you may find this document helpful.

License

Copyright © 2015–present Megaparsec contributors
Copyright © 2007 Paolo Martini
Copyright © 1999–2000 Daan Leijen

Distributed under FreeBSD license.