parsimonious 0.9.0

Goals

• Speed

• Frugal RAM use

• Minimalistic, understandable, idiomatic Python code

• Readable grammars

• Extensible grammars

• Complete test coverage

• Separation of concerns. Some Python parsing kits mix recognition with instructions about how to turn the resulting tree into some kind of other representation. This is limiting when you want to do several different things with a tree: for example, render wiki markup to HTML or to text.

• Good error reporting. I want the parser to work with me as I develop a grammar.

Install

To install Parsimonious, run:

$ pip install parsimonious

Example Usage

Here’s how to build a simple grammar:

>>> from parsimonious.grammar import Grammar
>>> grammar = Grammar(
...     """
...     bold_text  = bold_open text bold_close
...     text       = ~"[A-Z 0-9]*"i
...     bold_open  = "(("
...     bold_close = "))"
...     """)

You can have forward references and even right recursion; it’s all taken care of by the grammar compiler. The first rule is taken to be the default start symbol, but you can override that.

Next, let’s parse something and get an abstract syntax tree:

>>> print(grammar.parse('((bold stuff))'))
<Node called "bold_text" matching "((bold stuff))">
    <Node called "bold_open" matching "((">
    <RegexNode called "text" matching "bold stuff">
    <Node called "bold_close" matching "))">

You’d typically then use a nodes.NodeVisitor subclass (see below) to walk the tree and do something useful with it.

Another example would be to implement a parser for .ini-files. Consider the following:

grammar = Grammar(
    r"""
    expr        = (entry / emptyline)*
    entry       = section pair*

    section     = lpar word rpar ws
    pair        = key equal value ws?

    key         = word+
    value       = (word / quoted)+
    word        = ~r"[-\w]+"
    quoted      = ~'"[^\"]+"'
    equal       = ws? "=" ws?
    lpar        = "["
    rpar        = "]"
    ws          = ~"\s*"
    emptyline   = ws+
    """
)

We could now implement a subclass of NodeVisitor like so:

class IniVisitor(NodeVisitor):
    def visit_expr(self, node, visited_children):
        """ Returns the overall output. """
        output = {}
        for child in visited_children:
            output.update(child[0])
        return output

    def visit_entry(self, node, visited_children):
        """ Makes a dict of the section (as key) and the key/value pairs. """
        key, values = visited_children
        return {key: dict(values)}

    def visit_section(self, node, visited_children):
        """ Gets the section name. """
        _, section, *_ = visited_children
        return section.text

    def visit_pair(self, node, visited_children):
        """ Gets each key/value pair, returns a tuple. """
        key, _, value, *_ = node.children
        return key.text, value.text

    def generic_visit(self, node, visited_children):
        """ The generic visit method. """
        return visited_children or node

And call it like that:

from parsimonious.grammar import Grammar
from parsimonious.nodes import NodeVisitor

data = """[section]
somekey = somevalue
someotherkey=someothervalue

[anothersection]
key123 = "what the heck?"
key456="yet another one here"

"""

tree = grammar.parse(data)

iv = IniVisitor()
output = iv.visit(tree)
print(output)

This would yield

{'section': {'somekey': 'somevalue', 'someotherkey': 'someothervalue'}, 'anothersection': {'key123': '"what the heck?"', 'key456': '"yet another one here"'}}

Status

• Everything that exists works. Test coverage is good.

• I don’t plan on making any backward-incompatible changes to the rule syntax in the future, so you can write grammars with confidence.

• It may be slow and use a lot of RAM; I haven’t measured either yet. However, I have yet to begin optimizing in earnest.

• Error reporting is now in place. repr methods of expressions, grammars, and nodes are clear and helpful as well. The Grammar ones are even round-trippable!

• The grammar extensibility story is underdeveloped at the moment. You should be able to extend a grammar by simply concatenating more rules onto the existing ones; later rules of the same name should override previous ones. However, this is untested and may not be the final story.

• Sphinx docs are coming, but the docstrings are quite useful now.

• Note that there may be API changes until we get to 1.0, so be sure to pin to the version you’re using.

A Little About PEG Parsers

PEG parsers don’t draw a distinction between lexing and parsing; everything is done at once. As a result, there is no lookahead limit, as there is with, for instance, Yacc. And, due to both of these properties, PEG grammars are easier to write: they’re basically just a more practical dialect of EBNF. With caching, they take O(grammar size * text length) memory (though I plan to do better), but they run in O(text length) time.

Writing Grammars

Grammars are defined by a series of rules. The syntax should be familiar to anyone who uses regexes or reads programming language manuals. An example will serve best:

my_grammar = Grammar(r"""
    styled_text = bold_text / italic_text
    bold_text   = "((" text "))"
    italic_text = "''" text "''"
    text        = ~"[A-Z 0-9]*"i
    """)

You can wrap a rule across multiple lines if you like; the syntax is very forgiving.

Optimizing Grammars

Processing Parse Trees

A parse tree has a node for each expression matched, even if it matched a zero-length string, like "thing"? might.

The NodeVisitor class provides an inversion-of-control framework for walking a tree and returning a new construct (tree, string, or whatever) based on it. For now, have a look at its docstrings for more detail. There’s also a good example in grammar.RuleVisitor. Notice how we take advantage of nodes’ iterability by using tuple unpacks in the formal parameter lists:

def visit_or_term(self, or_term, (slash, _, term)):
    ...

For reference, here is the production the above unpacks:

or_term = "/" _ term

When something goes wrong in your visitor, you get a nice error like this:

[normal traceback here...]
VisitationException: 'Node' object has no attribute 'foo'

Parse tree:
<Node called "rules" matching "number = ~"[0-9]+"">  <-- *** We were here. ***
    <Node matching "number = ~"[0-9]+"">
        <Node called "rule" matching "number = ~"[0-9]+"">
            <Node matching "">
            <Node called "label" matching "number">
            <Node matching " ">
                <Node called "_" matching " ">
            <Node matching "=">
            <Node matching " ">
                <Node called "_" matching " ">
            <Node called "rhs" matching "~"[0-9]+"">
                <Node called "term" matching "~"[0-9]+"">
                    <Node called "atom" matching "~"[0-9]+"">
                        <Node called "regex" matching "~"[0-9]+"">
                            <Node matching "~">
                            <Node called "literal" matching ""[0-9]+"">
                            <Node matching "">
            <Node matching "">
            <Node called "eol" matching "
            ">
    <Node matching "">

The parse tree is tacked onto the exception, and the node whose visitor method raised the error is pointed out.

Future Directions

Version History

0.9.0

• Add support for Python 3.7, 3.8, 3.9, 3.10 (righthandabacus, Lonnen)

• Drop support for Python 2.x, 3.3, 3.4 (righthandabacus, Lonnen)

• Remove six and go all in on Python 3 idioms (Lonnen)

• Replace re with regex for improved handling of unicode characters in regexes (Oderjunkie)

• Dropped nose for unittest (swayson)

• Grammar.__repr__() now correctly escapes backslashes (ingolemo)

• Custom rules can now be class methods in addition to functions (James Addison)

• Make the ascii flag available in the regex syntax (Roman Inflianskas)

0.8.1

• Switch to a function-style print in the benchmark tests so we work cleanly as a dependency on Python 3. (Edward Betts)

0.8.0

• Make Grammar iteration ordered, making the __repr__ more like the original input. (Lucas Wiman)

• Improve text representation and error messages for anonymous subexpressions. (Lucas Wiman)

• Expose BadGrammar and VisitationError as top-level imports.

• No longer crash when you try to compare a Node to an instance of a different class. (Esben Sonne)

• Pin six at 1.9.0 to ensure we have python_2_unicode_compatible. (Sam Raker)

• Drop Python 2.6 support.

0.7.0

• Add experimental token-based parsing, via TokenGrammar class, for those operating on pre-lexed streams of tokens. This can, for example, help parse indentation-sensitive languages that use the “off-side rule”, like Python. (Erik Rose)

• Common codebase for Python 2 and 3: no more 2to3 translation step (Mattias Urlichs, Lucas Wiman)

• Drop Python 3.1 and 3.2 support.

• Fix a bug in Grammar.__repr__ which fails to work on Python 3 since the string_escape codec is gone in Python 3. (Lucas Wiman)

• Don’t lose parentheses when printing representations of expressions. (Michael Kelly)

• Make Grammar an immutable mapping (until we add automatic recompilation). (Michael Kelly)

0.6.2

• Make grammar compilation 100x faster. Thanks to dmoisset for the initial patch.

0.6.1

• Fix bug which made the default rule of a grammar invalid when it contained a forward reference.

0.6

• Add support for “custom rules” in Grammars. These provide a hook for simple custom parsing hooks spelled as Python lambdas. For heavy-duty needs, you can put in Compound Expressions with LazyReferences as subexpressions, and the Grammar will hook them up for optimal efficiency–no calling __getitem__ on Grammar at parse time.

• Allow grammars without a default rule (in cases where there are no string rules), which leads to also allowing empty grammars. Perhaps someone building up grammars dynamically will find that useful.

• Add @rule decorator, allowing grammars to be constructed out of notations on NodeVisitor methods. This saves looking back and forth between the visitor and the grammar when there is only one visitor per grammar.

• Add parse() and match() convenience methods to NodeVisitor. This makes the common case of parsing a string and applying exactly one visitor to the AST shorter and simpler.

• Improve exception message when you forget to declare a visitor method.

• Add unwrapped_exceptions attribute to NodeVisitor, letting you name certain exceptions which propagate out of visitors without being wrapped by VisitationError exceptions.

• Expose much more of the library in __init__, making your imports shorter.

• Drastically simplify reference resolution machinery. (Vladimir Keleshev)

0.5

• Add alpha-quality error reporting. Now, rather than returning None, parse() and match() raise ParseError if they don’t succeed. This makes more sense, since you’d rarely attempt to parse something and not care if it succeeds. It was too easy before to forget to check for a None result. ParseError gives you a human-readable unicode representation as well as some attributes that let you construct your own custom presentation.

• Grammar construction now raises ParseError rather than BadGrammar if it can’t parse your rules.

• parse() now takes an optional pos argument, like match().

• Make the _str__() method of UndefinedLabel return the right type.

• Support splitting rules across multiple lines, interleaving comments, putting multiple rules on one line (but don’t do that) and all sorts of other horrific behavior.

• Tolerate whitespace after opening parens.

• Add support for single-quoted literals.

0.4

• Support Python 3.

• Fix import * for parsimonious.expressions.

• Rewrite grammar compiler so right-recursive rules can be compiled and parsing no longer fails in some cases with forward rule references.

0.3

• Support comments, the ! (“not”) operator, and parentheses in grammar definition syntax.

• Change the & operator to a prefix operator to conform to the original PEG syntax. The version in Parsing Techniques was infix, and that’s what I used as a reference. However, the unary version is more convenient, as it lets you spell AB & A as simply A &B.

• Take the print statements out of the benchmark tests.

• Give Node an evaluate-able __repr__.

0.2

• Support matching of prefixes and other not-to-the-end slices of strings by making match() public and able to initialize a new cache. Add match() callthrough method to Grammar.

• Report a BadGrammar exception (rather than crashing) when there are mistakes in a grammar definition.

• Simplify grammar compilation internals: get rid of superfluous visitor methods and factor up repetitive ones. Simplify rule grammar as well.

• Add NodeVisitor.lift_child convenience method.

• Rename VisitationException to VisitationError for consistency with the standard Python exception hierarchy.

• Rework repr and str values for grammars and expressions. Now they both look like rule syntax. Grammars are even round-trippable! This fixes a unicode encoding error when printing nodes that had parsed unicode text.

• Add tox for testing. Stop advertising Python 2.5 support, which never worked (and won’t unless somebody cares a lot, since it makes Python 3 support harder).

• Settle (hopefully) on the term “rule” to mean “the string representation of a production”. Get rid of the vague, mysterious “DSL”.

0.1

• A rough but useable preview release

Thanks to Wiki Loves Monuments Panama for showing their support with a generous gift.