Navigation

LEPL - A Parser Library for Python 3 (and 2.6)

>>> from lepl import *

>>> class Term(Node): pass
>>> class Factor(Node): pass
>>> class Expression(Node): pass

>>> expr   = Delayed()
>>> number = Digit()[1:,...]                          > 'number'
>>> spaces = Drop(Regexp(r'\s*'))

>>> with Separator(spaces):
>>>     term    = number | '(' & expr & ')'           > Term
>>>     muldiv  = Any('*/')                           > 'operator'
>>>     factor  = term & (muldiv & term)[:]           > Factor
>>>     addsub  = Any('+-')                           > 'operator'
>>>     expr   += factor & (addsub & factor)[:]       > Expression
>>>     line    = expr & Eos()

>>> parser = line.parse_string
>>> parser('1 + 2 * (3 + 4 - 5)')[0]

Expression
 +- Factor
 |   +- Term
 |   |   `- number '1'
 |   `- ' '
 +- operator '+'
 +- ' '
 `- Factor
     +- Term
     |   `- number '2'
     +- ' '
     +- operator '*'
     +- ' '
     `- Term
         +- '('
         +- Expression
         |   +- Factor
         |   |   +- Term
         |   |   |   `- number '3'
         |   |   `- ' '
         |   +- operator '+'
         |   +- ' '
         |   +- Factor
         |   |   +- Term
         |   |   |   `- number '4'
         |   |   `- ' '
         |   +- operator '-'
         |   +- ' '
         |   `- Factor
         |       `- Term
         |           `- number '5'
         `- ')'

Features

LEPL combines the simplicity and ease–of–use of a recursive descent parser with scalability (through memoisation) and advanced (but optional) features like lexing, AST generation, offside–rule, robustness to ambiguous and left–recursive grammars, etc. It is written and maintained by Andrew Cooke.

  • Parsers are Python code, defined in Python itself. No separate grammar is necessary.
  • Friendly syntax using Python’s operators allows grammars to be defined in a declarative style close to BNF.
  • Optional, integrated Lexer simplifies handling whitespace.
  • Built-in AST support with support for iteration, traversal and re–writing.
  • Generic, pure-Python approach supports parsing a wide variety of data including binary data (Python 3+ only).
  • Well documented and extensible, modular design.
  • Unlimited recursion depth. The underlying algorithm is recursive descent, which can exhaust the stack for complex grammars and large data sets. LEPL avoids this problem by using Python generators as coroutines.
  • The parser can itself be manipulated by Python code. This gives unlimited opportunities for future expansion and optimisation.
  • Support for ambiguous grammars. A parser can return more than one result (“complete backtracking”, “parse forests”).
  • Parsers can be made much more efficient with automatic memoisation (“packrat parsing”).
  • Memoisation can detect and control left recursive grammars. Together with LEPL’s support for ambiguity this means that “any” grammar can be supported.
  • Pluggable trace and resource management, including deepest match diagnostics and the ability to limit backtracking.
  • Support for the “offside rule” (significant indentation levels) when using the lexer.

Indices and tables

Table Of Contents

Next topic

A Tutorial for LEPL

This Page

Navigation

© Copyright 2009, Andrew Cooke. Created using Sphinx 0.6.2.