megaparsec

Monadic parser combinators

https://github.com/mrkkrp/megaparsec

Version on this page:4.4.0
LTS Haskell 22.41:9.5.0@rev:4
Stackage Nightly 2024-11-12:9.6.1
Latest on Hackage:9.6.1

See all snapshots megaparsec appears in

BSD-2-Clause licensed by Megaparsec contributors, Paolo Martini, Daan Leijen
Maintained by Mark Karpov
This version can be pinned in stack with:megaparsec-4.4.0@sha256:aa17fa6f41e825466e085f5fcaa3ce7c2558b330a324f3638533d1a7fcd1210d,6603

Module documentation for 4.4.0

Megaparsec

License FreeBSD Hackage Stackage Nightly Stackage LTS Build Status Coverage Status

This is an industrial-strength monadic parser combinator library. Megaparsec is a fork of Parsec library originally written by Daan Leijen.

Features

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.

Core features

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 WriterT, StateT, ReaderT and others are instances of MonadParsec, you can wrap ParsecT in these monads, achieving, for example, backtracking state.

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

The module Text.Megaparsec.Combinator (its functions are included in Text.Megaparsec) contains traditional, general combinators that work with any instance of Alternative and some even with instances of Applicative.

Role of Monad, Applicative, and 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:

  • failure allows to fail with arbitrary collection of messages.

  • label allows 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.

  • hidden hides any parser from error messages altogether, this is officially recommended way to hide things, prefer it to the label "" approach.

  • try enables backtracking in parsing.

  • lookAhead allows to parse something without consuming input.

  • notFollowedBy succeeds when its argument fails, it does not consume input.

  • withRecovery 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.

  • eof only succeeds at the end of input.

  • token is used to parse single token.

  • tokens makes it easy to parse several tokens in a row.

  • getParserState returns full parser state.

  • updateParserState applies given function on parser state.

This list of core functions is longer than in some other libraries. Our goal was easy 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:

  • String = [Char]

  • ByteString (strict and lazy)

  • Text (strict and lazy)

Character parsing

Megaparsec has decent support for Unicode-aware character parsing. Functions for character parsing live in Text.Megaparsec.Char (they all are included in Text.Megaparsec). The functions can be divided into several categories:

  • Simple parsers — parsers that parse certain character or several characters of the same kind. This includes newline, crlf, eol, tab, and space.

  • Parsers corresponding to categories of characters parse single character that belongs to certain category of characters, for example: controlChar, spaceChar, upperChar, lowerChar, printChar, 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 string parser is available as well as case-insensitive string'.

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.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.Lexer is intended to be imported qualified, 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.

Documentation

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.

Tutorials

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.

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 Text.Megaparsec.Char.

  • 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.

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 lookAhead for 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.

Related packages

The following packages are designed to be used with Megaparsec:

Authors

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.

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, 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.

License

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

Distributed under FreeBSD license.

Changes

Megaparsec 4.4.0

  • 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.

  • The count combinator now works with Applicative instances (previously it worked only with instances of Alternative). It’s now also faster.

  • tokens and parsers built upon it (such as string and 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 try with tokens-based parsers. This new feature does not affect performance in any way.

  • New primitive parser withRecovery added. 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.

  • eitherP combinator added.

  • Removed Enum instance of Message type. This was Parsec’s legacy that we should eliminate now. Message does not constitute enumeration, toEnum was never properly defined for it. The idea to use fromEnum to determine type of Message is also ugly, for this purpose new functions isUnexpected, isExpected, and isMessage are defined in Text.Megaparsec.Error.

  • Minor tweak in signature of MonadParsec type class. Collection of constraints changed from Alternative m, Monad m, Stream s t to 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 guard are defined for instances of MonadPlus, not Alternative.

Megaparsec 4.3.0

  • Canonicalized Applicative/Monad instances. Thanks to Herbert Valerio Riedel.

  • Custom messages in ParseError are printed each on its own line.

  • Now accumulated hints are not used with ParseError records that have only custom messages in them (created with Message constructor, as opposed to Unexpected or 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: indentLevel, nonIndented, and indentBlock.

Megaparsec 4.2.0

  • Made newPos constructor and other functions in Text.Megaparsec.Pos smarter. Now it’s impossible to create SourcePos with non-positive line number or column number. Unfortunately we cannot use Numeric.Natural because we need to support older versions of base.

  • ParseError is now a monoid. mergeError is used as mappend.

  • Added functions addErrorMessages and newErrorMessages to add several messages to existing error and to construct error with several attached messages respectively.

  • parseFromFile now lives in Text.Megaparsec.Prim. Previously we had 5 nearly identical definitions of the function, varying only in type-specific readFile function. Now the problem is solved by introduction of StorableStream type class. All supported stream types are instances of the class out of box and thus we have polymorphic version of parseFromFile.

  • ParseError is now instance of Exception (and Typeable).

  • Introduced runParser' and 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.

  • Introduced failure function that allows to fail with arbitrary collection of messages. unexpected is now defined in terms of failure. One consequence of this design decision is that failure is now method of MonadParsec, while unexpected is not.

  • Removed deprecated combinators from Text.Megaparsec.Combinator:

    • chainl
    • chainl1
    • chainr
    • chainr1

  • number parser in Text.Megaparsec.Lexer now can be used with signed combinator to parse either signed Integer or signed Double.

Megaparsec 4.1.1

  • Fixed bug in implementation of sepEndBy and sepEndBy1 and removed deprecation notes for these functions.

  • Added tests for sepEndBy and sepEndBy1.

Megaparsec 4.1.0

  • Relaxed dependency on base, so that minimal required version of base is now 4.6.0.0. This allows Megaparsec to compile with GHC 7.6.x.

  • Text.Megaparsec and Text.Megaparsec.Prim do not export data types Consumed and Reply anymore 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.

Megaparsec 4.0.0

General changes

  • Renamed many1 → some as well as other parsers that had many1 part in their names.

  • The following functions are now re-exported from Control.Applicative: (<|>), many, some, optional. See #9.

  • Introduced type class MonadParsec in 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 ParsecT.

  • Added new function parseMaybe for 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 notFollowedBy always succeeded with parsers that don’t consume input, see #6.

  • Flipped order of arguments in the primitive combinator label, see #21.

  • Renamed tokenPrim → token, removed old token, because tokenPrim is more general and original token is little used.

  • Made token parser more powerful, now its second argument can return Either [Message] a instead of Maybe a, so it can influence error message when parsing of token fails. See #29.

  • Added new primitive combinator hidden p which hides “expected” tokens in error message when parser p fails.

  • Tab width is not hard-coded anymore. It can be manipulated via getTabWidth and setTabWidth. Default tab-width is defaultTabWidth, which is 8.

Error messages

  • Introduced type class ShowToken and improved representation of characters and strings in error messages, see #12.

  • Greatly improved quality of error messages. Fixed entire Text.Megaparsec.Error module, 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 Utils.hs in old-tests for example.

  • Reduced number of Message constructors (now there are only Unexpected, Expected, and 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.Prim a lot clearer.

Built-in combinators

  • All built-in combinators in Text.Megaparsec.Combinator now work with any instance of Alternative (some of them even with Applicaitve).

  • Added more powerful count' parser. This parser can be told to parse from m to n occurrences of some thing. count is defined in terms of count'.

  • Removed optionMaybe parser, because optional from Control.Applicative does the same thing.

  • Added combinator someTill.

  • These combinators are considered deprecated and will be removed in future:

    • chainl
    • chainl1
    • chainr
    • chainr1
    • sepEndBy
    • sepEndBy1

Character parsing

  • Renamed some parsers:

    • alphaNum → alphaNumChar
    • digit → digitChar
    • endOfLine → eol
    • hexDigit → hexDigitChar
    • letter → letterChar
    • lower → lowerChar
    • octDigit → octDigitChar
    • space → spaceChar
    • spaces → space
    • upper → upperChar

  • Added new character parsers in Text.Megaparsec.Char:

    • asciiChar
    • charCategory
    • controlChar
    • latin1Char
    • markChar
    • numberChar
    • printChar
    • punctuationChar
    • separatorChar
    • symbolChar

  • Descriptions of old parsers have been updated to accent some Unicode-specific moments. For example, old description of letter stated that it parses letters from “a” to “z” and from “A” to “Z”. This is wrong, since it used Data.Char.isAlpha predicate internally and thus parsed many more characters (letters of non-Latin languages, for example).

  • Added combinators char', oneOf', noneOf', and string' which are case-insensitive variants of char, oneOf, noneOf, and string respectively.

Lexer

  • 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, integer and float now parse numbers without sign.

    • Removed natural parser, it’s equal to new integer now.

    • Renamed naturalOrFloat → number — this doesn’t parse sign too.

    • Added new combinator signed to parse all sorts of signed numbers.

  • Transformed Text.Parsec.Token into 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.

Other

  • Renamed the following functions:

    • permute → makePermParser
    • buildExpressionParser → makeExprParser

  • Added comprehensive QuickCheck test suite.

  • Added benchmarks.

Parsec 3.1.9

  • Many and various updates to documentation and package description (including the homepage links).

  • Add an Eq instance for ParseError.

  • Fixed a regression from 3.1.6: runP is again exported from module Text.Parsec.

Parsec 3.1.8

  • Fix a regression from 3.1.6 related to exports from the main module.

Parsec 3.1.7

  • 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 lookAhead.

Parsec 3.1.6

  • Export Text instances from Text.Parsec.

  • Make Text.Parsec exports more visible.

  • Re-arrange Text.Parsec exports.

  • Add functions crlf and endOfLine to Text.Parsec.Char for handling input streams that do not have normalized line terminators.

  • Fix off-by-one error in Token.charControl.

Parsec 3.1.4 & 3.1.5

  • Bump dependency on text.

Parsec 3.1.3

  • Fix a regression introduced in 3.1.2 related to positions reported by error messages.