Monadic parser combinators
|Version on this page:||5.0.1|
|LTS Haskell 20.23:||9.2.2|
|Stackage Nightly 2023-06-04:||9.3.1|
|Latest on Hackage:||9.3.1|
Module documentation for 5.0.1
- Comparison with other solutions
- Related packages
This is an industrial-strength monadic parser combinator library. Megaparsec is a fork of Parsec library originally written by Daan Leijen.
This 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.
The package is built around
MonadParsec, a MTL-style monad
transformer. All tools and features work with any instance of
MonadParsec. You can achieve various effects combining monad transformers,
i.e. building monad stack. Since most common monad transformers like
ReaderT and others are instances of
you can wrap
ParsecT in these monads, achieving, for example,
On the other hand
ParsecT is instance of many type classes as well. The
most useful ones are
(its functions are included in
Text.Megaparsec) contains traditional,
general combinators that work with any instance of
Alternative and some
even with instances of
Alternative should be obvious, so
let’s enumerate methods of
MonadParsec type class. The class represents
core, basic functions of Megaparsec parsing. The rest of library is built
via combination of these primitives:
failureallows to fail with arbitrary collection of messages.
labelallows to add a “label” to any parser, so when it fails the user will see the label in the error message where “expected” items are enumerated.
hiddenhides any parser from error messages altogether, this is officially recommended way to hide things, prefer it to the
tryenables backtracking in parsing.
lookAheadallows to parse something without consuming input.
notFollowedBysucceeds when its argument fails, it does not consume input.
withRecoveryallows to recover from parse errors “on-the-fly” and continue parsing. Once parsing is finished, several parse errors may be reported or ignored altogether.
eofonly succeeds at the end of input.
tokenis used to parse single token.
tokensmakes it easy to parse several tokens in a row.
getParserStatereturns full parser state.
updateParserStateapplies given function on parser state.
This list of core functions is longer than in some other libraries. Our goal was efficient and readable implementation of functionality provided by every such primitive, not minimal number of them. You can read the comprehensive description of every primitive function in Megaparsec documentation.
Megaparsec can currently work with the following types of input stream:
ByteString(strict and lazy)
Text(strict and lazy)
Megaparsec 5 introduces well-typed error messages and ability to use custom data types to adjust the library to your domain of interest. No need to keep your info as shapeless bunch of strings anymore.
The default error component (
Dec) has constructors corresponding to
function and indentation-related error messages. It is a decent option that
should work out-of-box for most parsing needs, while you are free to use
your own custom error component when necessary with little effort.
This new design allowed Megaparsec 5 to have much more helpful error messages for indentation-sensitive parsing instead of plain “incorrect indentation” phrase.
Alex and Happy support
Megaparsec works well with streams of tokens produced by tools like
Alex/Happy. Megaparsec 5 adds
updatePos method to
Stream type class that
gives you full control over textual positions that are used to report token
positions in error messages. You can update current position on per
character basis or extract it from token — all cases are covered.
Megaparsec has decent support for Unicode-aware character parsing. Functions
for character parsing live in
Text.Megaparsec.Char (they all are
Text.Megaparsec). The functions can be divided into several
Simple parsers — parsers that parse certain character or several characters of the same kind. This includes
Parsers corresponding to categories of characters parse single character that belongs to certain category of characters, for example:
digitChar, and others.
General parsers that allow you to parse a single character you specify or one of given characters, or any character except for given ones, or character satisfying given predicate. Case-insensitive versions of the parsers are available.
Parsers for sequences of characters parse strings. These are more efficient and provide better error messages than other approaches most programmers can come up with. Case-sensitive
stringparser is available as well as case-insensitive
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
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
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.
is a module that should help you write your lexer. If you have used
in the past, this module “fixes” its particularly inflexible
Text.Megaparsec.Lexer is intended to be imported qualified, it’s not
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,
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
Text.Megaparsec.Lexer module — no third party packages
Megaparsec is well-documented. All functions and data-types are thoroughly described. We pay attention to avoid outdated info or unclear phrases in our documentation. See the current version of Megaparsec documentation on Hackage for yourself.
You can visit site of the project which has several tutorials that should help you to start with your parsing tasks. The site also has instructions and tips for Parsec users who decide to switch.
Despite being quite flexible, Megaparsec is also faster than Parsec. The repository includes benchmarks that can be easily used to compare Megaparsec and Parsec. In most cases Megaparsec is faster, sometimes dramatically faster. If you happen to have some other benchmarks, I would appreciate if you add Megaparsec to them and let me know how it performs.
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 and 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:
Attoparsec is much faster but not that feature-rich. It should be used when you want to process large amounts of data where performance matters more than quality of error messages.
Megaparsec is good for parsing of source code or other human-readable texts. It has better error messages and it’s implemented as monad transformer.
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.
Megaparsec and Parsec
Since Megaparsec is a fork of Parsec, it’s necessary to list main differences between the two libraries:
Better error messages. We test our error messages using dense QuickCheck tests. Good error messages are just as important for us as correct return values of our parsers. Megaparsec will be especially useful if you write compiler or interpreter for some language.
Some quirks and “buggy features” (as well as plain bugs) of original Parsec are fixed. There is no undocumented surprising stuff in Megaparsec.
Better support for Unicode parsing in
Megaparsec has more powerful combinators and can parse languages where indentation matters.
Comprehensive QuickCheck test suite covering nearly 100% of our code.
We have benchmarks to detect performance regressions.
Better documentation, with 100% of functions covered, without typos and obsolete information, with working examples. Megaparsec’s documentation is well-structured and doesn’t contain things useless to end users.
Megaparsec’s code is clearer and doesn’t contain “magic” found in original Parsec.
Megaparsec has well-typed error messages and custom error messages.
Megaparsec can recover from parse errors “on the fly” and continue parsing.
Megaparsec is faster.
If you want to see a detailed change log,
CHANGELOG.md may be helpful.
To be honest Parsec’s development has seemingly stagnated. It has no test suite (only three per-bug tests), and all its releases beginning from version 3.1.2 (according or its change log) were about introducing and fixing regressions. Parsec is old and somewhat famous in Haskell community, so we understand there will be some kind of inertia, but we advise you use Megaparsec from now on because it solves many problems of original Parsec project. If you think you still have a reason to use original Parsec, open an issue.
Megaparsec and Parsers
There is Parsers package, which is great. You can use it with Megaparsec or Parsec, but consider the following:
It depends on both Attoparsec and Parsec, which means you always grab useless code installing it. This is ridiculous, by the way, because this package is supposed to be useful for parser builders, so they can write basic core functionality and get the rest “for free”. But with these useful functions you get two more parsers as dependencies.
It currently has a bug in definition of
lookAheadfor various monad transformers like
StateT, etc. which is visible when you create backtracking state via monad stack, not via built-in features.
We intended to use Parsers library in Megaparsec at some point, but aside from already mentioned flaws the library has different conventions for naming of things, different set of “core” functions, etc., different approach to lexer. So it didn’t happen, Megaparsec has minimal dependencies, it is feature-rich and self-contained.
The following packages are designed to be used with Megaparsec:
hspec-megaparsec— utilities for testing Megaparsec parsers with with Hspec.
The project was started and is currently maintained by Mark Karpov. You can
find complete list of contributors in
AUTHORS.md file in 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.
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, we are progressive folks).
If you want to write a tutorial to be hosted on Megaparsec’s site, open an issue or pull request here.
Copyright © 2015–2016 Megaparsec contributors Copyright © 2007 Paolo Martini Copyright © 1999–2000 Daan Leijen
Distributed under FreeBSD license.
Minor documentation improvements.
StorableStreamtype-class that was necessary for it. The reason for removal is that reading from file and then parsing its contents is trivial for every instance of
Streamand this function provides no way to use newer methods for running a parser, such as
runParser'. So, simply put, it adds little value and was included in 4.x versions for compatibility reasons.
Moved position-advancing function from arguments of
Streamtype class (named
updatePos). The new function allows to handle custom streams of tokens where every token contains information about its position in stream better (for example when stream of tokens is produced with happy/alex).
Support for include files (stack of positions instead of flat position) added. The new functions
popPositioncan be used to move “vertically” in the stack of positions.
setPositionstill work on top (“current file”) level, but user can get full stack via
getParserStateif necessary. Note that
ParseErrorand pretty-printing for it also support the new feature.
Added type function
Streamtype class. The function returns type of token corresponding to specific token stream.
ParsecT(and also type synonym
Parsec) are now parametrized over type of custom component in parse errors.
MonadParsectype class are:
e— type of custom component in parse errors,
s— type of input stream, and
m— type of underlying monad.
failureprimitive combinator was changed, now it accepts three arguments: set of unexpected items, set of expected items, and set of custom data.
tokenprimitive combinator was changed, now in case of failure a triple-tuple is returned with elements corresponding to arguments of
tokenprimitive can also be optionally given an argument of token type to use in error messages (as expected item) in case of end of input.
unexpectedcombinator now accepts argument of type
ErrorIteminstead of plain
General performance improvements and improvements in speed of some combinators,
Text.Megaparsec.Poswas completely rewritten. The new module uses
Posdata type with smart constructors to ensure that things like line and column number can be only positive.
SourcePoson the other hand does not require smart constructors anymore and its constructors are exported.
SourcePosare derived and pretty-printing is done with help of
Text.Megaparsec.Errorwas completely rewritten. A number of new types and type-classes are introduced:
ParseErrordoes not need smart constructors anymore and its constructor and field selectors are exported. It uses sets (from the
containerspackage) instead of sorted lists to enumerate unexpected and expected items. The new definition is also parametrized over token type and custom data type which can be passed around as part of parse error. Default “custom data” component is
Dec, which see. All in all, we have completely well-typed and extensible error messages now.
ParseErrorare derived and pretty-printing is done with help of
Text.Megaparsec.ShowTokenwas eliminated and type class
ShowTokenwas moved to
Text.Megaparsec.Error. The only method of that class in now named
showTokensand it works on streams of tokens, where single tokes are represented by
NonEmptylist with single element.
noneOf'now accept any instance of
Foldable, not only
Error messages about incorrect indentation levels were greatly improved. Now every such message contains information about desired ordering between “reference” indentation level and actual indentation level as well as values of these levels. The information is stored in
ParseErrorin well-typed form and can be pretty-printed when necessary. As part of this improvement, type of
incorrectIndentcombinator is introduced in
Text.Megaparsec.Lexermodule. It allows to fail with detailed information regarding incorrect indentation.
scientificparser that can parse arbitrary big numbers without error or memory overflow.
Double, but it’s defined in terms of
Scientifictype can reliably represent integer values as well as floating point values,
Either Integer Double(
Doublecan be extracted from
Scientificvalue anyway). This in turn makes
signedparser more natural and general, because we do not need ad-hoc
Signedtype class anymore.
skipBlockCommentNestedfunction that should help parse possibly nested block comments.
lineFoldfunction that helps parse line folds.
Now state returned on failure is the exact state of parser at the moment when it failed, which makes incremental parsing feature much better and opens possibilities for features like “on-the-fly” recovering from parse errors.
countcombinator now works with
Applicativeinstances (previously it worked only with instances of
Alternative). It’s now also faster.
tokensand parsers built upon it (such as
string') backtrack automatically on failure now, that is, when they fail, they never consume any input. This is done to make their consumption model match how error messages are reported (which becomes an important thing as user gets more control with primitives like
withRecovery). This means, in particular, that it’s no longer necessary to use
tokens-based parsers. This new feature does not affect performance in any way.
New primitive parser
withRecoveryadded. The parser allows to recover from parse errors “on-the-fly” and continue parsing. Once parsing is finished, several parse errors may be reported or ignored altogether.
Messagetype. This was Parsec’s legacy that we should eliminate now.
Messagedoes not constitute enumeration,
toEnumwas never properly defined for it. The idea to use
fromEnumto determine type of
Messageis also ugly, for this purpose new functions
isMessageare defined in
Minor tweak in signature of
MonadParsectype class. Collection of constraints changed from
Alternative m, Monad m, Stream s tto
Alternative m, MonadPlus m, Stream s t. This is done to make it easier to write more abstract code with older GHC where such primitives as
guardare defined for instances of
Monadinstances. Thanks to Herbert Valerio Riedel.
Custom messages in
ParseErrorare printed each on its own line.
Now accumulated hints are not used with
ParseErrorrecords that have only custom messages in them (created with
Messageconstructor, as opposed to
Expected). This strips “expected” line from custom error messages where it’s unlikely to be relevant anyway.
Added higher-level combinators for indentation-sensitive grammars:
newPosconstructor and other functions in
Text.Megaparsec.Possmarter. Now it’s impossible to create
SourcePoswith non-positive line number or column number. Unfortunately we cannot use
Numeric.Naturalbecause we need to support older versions of
ParseErroris now a monoid.
mergeErroris used as
newErrorMessagesto add several messages to existing error and to construct error with several attached messages respectively.
parseFromFilenow lives in
Text.Megaparsec.Prim. Previously we had 5 nearly identical definitions of the function, varying only in type-specific
readFilefunction. Now the problem is solved by introduction of
StorableStreamtype class. All supported stream types are instances of the class out of box and thus we have polymorphic version of
ParseErroris now instance of
runParserT'functions that take and return parser state. This makes it possible to partially parse input, resume parsing, specify non-standard initial textual position, etc.
failurefunction that allows to fail with arbitrary collection of messages.
unexpectedis now defined in terms of
failure. One consequence of this design decision is that
failureis now method of
Removed deprecated combinators from
Text.Megaparsec.Lexernow can be used with
signedcombinator to parse either signed
Fixed bug in implementation of
sepEndBy1and removed deprecation notes for these functions.
Added tests for
Relaxed dependency on
base, so that minimal required version of
baseis now 18.104.22.168. This allows Megaparsec to compile with GHC 7.6.x.
Text.Megaparsec.Primdo not export data types
Replyanymore because they are rather low-level implementation details that should not be visible to end-user.
Representation of file name and textual position in error messages was made conventional.
Fixed some typos is documentation and other materials.
someas well as other parsers that had
many1part in their names.
The following functions are now re-exported from
optional. See #9.
Introduced type class
MonadParsecin the style of MTL monad transformers. Eliminated built-in user state since it was not flexible enough and can be emulated via stack of monads. Now all tools in Megaparsec work with any instance of
MonadParsec, not only with
Added new function
parseMaybefor lightweight parsing where error messages (and thus file name) are not important and entire input should be parsed. For example it can be used when parsing of single number according to specification of its format is desired.
Fixed bug with
notFollowedByalways succeeded with parsers that don’t consume input, see #6.
Flipped order of arguments in the primitive combinator
label, see #21.
token, removed old
tokenPrimis more general and original
tokenis little used.
tokenparser more powerful, now its second argument can return
Either [Message] ainstead of
Maybe a, so it can influence error message when parsing of token fails. See #29.
Added new primitive combinator
hidden pwhich hides “expected” tokens in error message when parser
Tab width is not hard-coded anymore. It can be manipulated via
setTabWidth. Default tab-width is
defaultTabWidth, which is 8.
Introduced type class
ShowTokenand improved representation of characters and strings in error messages, see #12.
Greatly improved quality of error messages. Fixed entire
Text.Megaparsec.Errormodule, see #14 for more information. Made possible normal analysis of error messages without “render and re-parse” approach that previous maintainers had to practice to write even simplest tests, see module
Reduced number of
Messageconstructors (now there are only
Message). Empty “magic” message strings are ignored now, all the library now uses explicit error messages.
Introduced hint system that greatly improves quality of error messages and made code of
Text.Megaparsec.Prima lot clearer.
All built-in combinators in
Text.Megaparsec.Combinatornow work with any instance of
Alternative(some of them even with
Added more powerful
count'parser. This parser can be told to parse from
noccurrences of some thing.
countis defined in terms of
Control.Applicativedoes the same thing.
These combinators are considered deprecated and will be removed in future:
Renamed some parsers:
Added new character parsers in
Descriptions of old parsers have been updated to accent some Unicode-specific moments. For example, old description of
letterstated that it parses letters from “a” to “z” and from “A” to “Z”. This is wrong, since it used
Data.Char.isAlphapredicate internally and thus parsed many more characters (letters of non-Latin languages, for example).
string'which are case-insensitive variants of
Rewritten parsing of numbers, fixed #2 and #3 (in old Parsec project these are number 35 and 39 respectively), added per bug tests.
Since Haskell report doesn’t say anything about sign,
floatnow parse numbers without sign.
naturalparser, it’s equal to new
number— this doesn’t parse sign too.
Added new combinator
signedto parse all sorts of signed numbers.
Text.Megaparsec.Lexer. Little of Parsec’s code remains in the new lexer module. New module doesn’t impose any assumptions on user and should be vastly more useful and general. Hairy stuff from original Parsec didn’t get here, for example built-in Haskell functions are used to parse escape sequences and the like instead of trying to re-implement the whole thing.
Renamed the following functions:
Added comprehensive QuickCheck test suite.
Many and various updates to documentation and package description (including the homepage links).
Fixed a regression from 3.1.6:
runPis again exported from module
- Fix a regression from 3.1.6 related to exports from the main module.
Fix a regression from 3.1.6 related to the reported position of error messages. See bug #9 for details.
Reset the current error position on success of
Text.Parsecexports more visible.
Text.Parsec.Charfor handling input streams that do not have normalized line terminators.
Fix off-by-one error in
Parsec 3.1.4 & 3.1.5
- Bump dependency on
- Fix a regression introduced in 3.1.2 related to positions reported by error messages.