Current version: 0.3.5, 2011-01-13

Look at the new version 0.9 on its way to the release.

Description

Parser combinators are just higher-order functions that take parsers as their arguments and return them as result values. Parser combinators are:

• First-class values
• Extremely composable
• Tend to make the code quite compact
• Resemble the readable notation of xBNF grammars

Parsers made with funcparserlib are pure-Python LL(*) parsers. It means that it's very easy to write them without thinking about look-aheads and all that hardcore parsing stuff. But the recursive descent parsing is a rather slow method compared to LL(k) or LR(k) algorithms.

So the primary domain for funcparserlib is parsing little languages or external DSLs (domain specific languages).

The library itself is very small. Its source code is only 0.5 KLOC, with lots of comments included. It features the longest parsed prefix error reporting, as well as a tiny lexer generator for token position tracking.

Documentation

• The funcparserlib Tutorial is a good starting point
• Nested Brackets Mini-HOWTO is a shorter intro
• Parsing Stages Illustrated (with pictures!) for a general view
• Examples in ./examples directory
• GraphViz DOT parser
• JSON parser
• The source code is quite straightforward and well-documented
• Changelog
• FAQ

Performance and Code Size

Despite being an LL(*) parser, funcparserlib has a reasonable performance. For example, a JSON parser written using funcparserlib is 3 times faster than a parser using the popular pyparsing library and only 5 times slower than the specialized JSON library simplejson that uses ad hoc parsing. Here are some stats¹:

funcparserlib and pyparsing both have the smallest user code size (that is a common feature of parsing libraries compared to ad hoc parsers). The library code of funcparserlib is 7 times smaller (and much more cleaner) than pyparsing. The json-ply uses a LALR parser ply (similar to Yacc) and performs like funcparserlib. cjson is a C library, hence the incredible performance :)

Download

The current release can be downloaded from the PyPI.

Show Me the Code

This is an excerpt from a JSON parser (RFC 4627). This full example as well as others can be found in ./examples directory.

def parse(seq):
    'Sequence(Token) -> object'
    ...
    n = lambda s: a(Token('Name', s)) >> tokval
    def make_array(n):
        if n is None:
            return []
        else:
            return [n[0]] + n[1]
    ...
    null = n('null') >> const(None)
    true = n('true') >> const(True)
    false = n('false') >> const(False)
    number = toktype('Number') >> make_number
    string = toktype('String') >> make_string
    value = forward_decl()
    member = string + op_(':') + value >> tuple
    object = (
        op_('{') +
        maybe(member + many(op_(',') + member)) +
        op_('}')
        >> make_object)
    array = (
        op_('[') +
        maybe(value + many(op_(',') + value)) +
        op_(']')
        >> make_array)
    value.define(
          null
        | true
        | false
        | object
        | array
        | number
        | string)
    json_text = object | array
    json_file = json_text + skip(finished)

    return json_file.parse(seq)

Project Stats

Similar Projects

• LEPL. A recursive descent parsing library that uses two-way generators for backtracking. Its source code is rather large: 17 KLOC
• pyparsing. A recursive descent parsing library. Probably the most popular Python parsing library. Nevertheless its source code is quite dirty (though 4 KLOC only)
• Monadic Parsing in Python. A series of blog entries on monadic parsing
• Pysec (aka Parsec in Python). A blog entry on monadic parsing, with nice syntax for Python

¹ Testing hardware: Pentium III, 1 GHz, 512 MB. JSON files were taken from a real project, in a normalized encoding, i. e. they contained no extra separators. The version 0.3.2 of the library was used.