megaparsec: Monadic parser combinators

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

Warnings:

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


[Skip to Readme]

Properties

Versions 4.0.0, 4.1.0, 4.1.1, 4.2.0, 4.3.0, 4.4.0, 5.0.0, 5.0.1, 5.1.0, 5.1.1, 5.1.2, 5.2.0, 5.3.0, 5.3.1, 6.0.0, 6.0.1, 6.0.2, 6.1.0, 6.1.1, 6.2.0, 6.3.0, 6.4.0, 6.4.1, 6.5.0, 6.5.0, 7.0.0, 7.0.1, 7.0.2, 7.0.3, 7.0.4, 7.0.5, 8.0.0, 9.0.0, 9.0.1, 9.1.0, 9.2.0, 9.2.1, 9.2.2, 9.3.0, 9.3.1, 9.4.0, 9.4.1, 9.5.0, 9.6.0, 9.6.1
Change log CHANGELOG.md
Dependencies base (>=4.7 && <5.0), bytestring (>=0.2 && <0.11), case-insensitive (>=1.2 && <1.3), containers (>=0.5 && <0.6), deepseq (>=1.3 && <1.5), fail (>=4.9 && <4.10), mtl (>=2.0 && <3.0), parser-combinators (>=0.4 && <1.0), scientific (>=0.3.1 && <0.4), semigroups (>=0.18 && <0.19), text (>=0.2 && <1.3), transformers (>=0.4 && <0.6), void (>=0.7 && <0.8) [details]
License BSD-2-Clause
Author Megaparsec contributors, Paolo Martini <paolo@nemail.it>, Daan Leijen <daan@microsoft.com>
Maintainer Mark Karpov <markkarpov92@gmail.com>
Category Parsing
Home page https://github.com/mrkkrp/megaparsec
Bug tracker https://github.com/mrkkrp/megaparsec/issues
Source repo head: git clone https://github.com/mrkkrp/megaparsec.git
Uploaded by mrkkrp at 2018-03-27T16:22:29Z

Modules

[Index]

Flags

Manual Flags

NameDescriptionDefault
dev

Turn on development settings.

Disabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Readme for megaparsec-6.5.0

[back to package description]

Megaparsec

License FreeBSD Hackage Stackage Nightly Stackage LTS Build Status

This is an industrial-strength monadic parser combinator library. Megaparsec is a feature-rich package that strikes 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. All tools and features work with all instances of MonadParsec. You 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, you can 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 available in Parsec plus features some combinators that are missing in other parsing libraries:

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

So now that we have matched the main “performance boosters” of Attoparsec, Megaparsec 6 is not significantly slower than Attoparsec if you write your parser carefully (see also the section about performance).

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

It's also simple to make it work with custom token streams, and Megaparsec users have done so many times.

Error messages

Megaparsec 5 introduced well-typed error messages and the ability to use custom data types to adjust the library to specific domain of interest. No need to use a shapeless bunch of strings.

The design of parse errors has been revised in version 6 significantly, but custom errors are still easy (probably even easier now).

Alex support

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

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.

Permutation parsing

For those who are interested in parsing of permutation phrases, there is Text.Megaparsec.Perm. You have to import the module explicitly, it's not included in the Text.Megaparsec module.

Expression parsing

Megaparsec has a solution for parsing of expressions. Take a look at Text.Megaparsec.Expr. You have to import the module explicitly, it's not included in the Text.Megaparsec.

Given a table of operators that describes their fixity and precedence, you can construct a parser that will parse any expression involving the operators. See documentation for comprehensive description of how it works.

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 you quickly solve simple tasks and doesn't get in your way when you want to implement something less standard.

Since Megaparsec 5, all tools for indentation-sensitive parsing are available in Text.Megaparsec.Char.Lexer module—no third party packages required.

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 Megaparsec tutorials here. They should provide sufficient guidance to help you to start with your parsing tasks. The site also has instructions and tips for Parsec users who decide to migrate to Megaparsec.

Performance

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

Test case Execution time Allocated Max residency
CSV (Attoparsec) 57.14 μs 397,912 10,560
CSV (Megaparsec) 76.27 μs 557,272 9,120
Log (Attoparsec) 244.2 μs 1,181,120 11,144
Log (Megaparsec) 315.2 μs 1,485,776 11,392
JSON (Attoparsec) 14.39 μs 132,496 9,048
JSON (Megaparsec) 26.70 μs 233,336 9,424

The benchmarks were created to guide development of Megaparsec 6 and can be found here.

If you think your Megaparsec parser is not efficient enough, take a look at these instructions.

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 the 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 size of input data is usually not huge, just go with Megaparsec, otherwise Attoparsec may be a better choice.

Since version 6, Megaparsec features the same fast primitives that Attoparsec has, so in many cases the difference in speed is not that big. Megaparsec now aims to be “one size fits all” ultimate solution to parsing, so it can be used even to parse low-level binary formats.

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. It's probably good, but also under-documented, and has unfixed bugs and flaws. Other reasons one may question choice of Trifecta is his/her parsing library:

Idris has recently 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 to safely (it your code compiles, then it probably works) parse context-free grammars (CFG). Megaparsec is a lower-level library compared to Earley, but there are still enough reasons to choose it over Earley:

IOW, Megaparsec is less safe but also more powerful.

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

The following are some prominent projects that use Megaparsec:

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

Authors

The project was started and is currently maintained by Mark Karpov. You can find the complete list of contributors in the AUTHORS.md file in the official repository of the project. Thanks to all the people who propose features and ideas, although they are not in AUTHORS.md, without them Megaparsec would not be that good.

Contribution

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

Pull requests are also welcome (and yes, they will get attention and will be merged quickly if they are good).

License

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

Distributed under FreeBSD license.