SimpleParse A Parser Generator for mxTextTools v2.0.0

SimpleParse is a BSD-licensed Python package providing a simple parser generator for use with the mxTextTools text-tagging engine. SimpleParse allows you to generate tagging tables for use with the text-tagging engine directly from your EBNF grammar.

Unlike most parser generators, SimpleParse generates single-pass parsers (there is no distinct tokenization stage), an approach taken from the predecessor project (mcf.pars) which attempted to create "autonomously parsing regex objects". The resulting parsers are not as generalized as those created by, for instance, the Earley algorithm, but they do tend to be useful for the parsing of computer file formats and the like (as distinct from natural language and similar "hard" parsing problems).

In addition to the parser generator, the SimpleParse project includes a sub-project to create a modified version of the mxTextTools engine which reorganizes the code to allow for certain common EBNF constructs.

For those interested in working on the project, I'm actively interested in welcoming and supporting both new developers and new users. Feel free to contact me.

Documentation

Scanning with SimpleParse -- describes the process of creating a Parser object with your EBNF grammar, and using that parser to scan input texts
SimpleParse Grammars -- reference to the various features of the default SimpleParse EBNF grammar variant
Processing Result Trees -- brief description of the results of the tagging/scanning process and the features available for processing (and altering) those results
Common Problems -- description of a number of common bugs, errors, pitfalls and anti-patterns when using the engine.
IBM DeveloperWorks Article by Dr. David Mertz -- discusses (and teaches the use of) SimpleParse 1.0, contrasting the EBNF-based parser with tools such as regexen for text-processing tasks. Watch also for Dr. Mertz' upcoming book Text Processing with Python
mxTextTools documentation -- documents the underlying mxTextTools engine. Hopefully most users of SimpleParse who aren't actually creating custom/prebuilt parsing elements shouldn't need this link.
PyDoc references -- automatically generated documentation on the various elements within the package. Of particular interest are the library of reusable structures (simpleparse.common) and the Parser class, which is the primary interface for the parsing system.

Acquisition and Installation

You will need a copy of Python with distutils support (Python versions 2.0 and above include this). If you want to build the non-recursive TextTools engine, you'll also need a C compiler compatible with your Python build and understood by distutils.

To install the base SimpleParse engine, download the latest version in your preferred format. If you are using the Win32 installer, simply run the executable. If you are using one of the source distributions, unpack the distribution into a temporary directory (maintaining the directory structure) then run:

setup.py install

in the top directory created by the expansion process.

You will want the mxBase 2.1.0 distribution to run SimpleParse. This package should be available in all the standard formats, follow the same instructions as for the SimpleParse package to install. If you want to use the non-recursive implementation, you will need to get the source archive. It is possible to use mxBase 2.0.3 with SimpleParse, but not to use it for building the non-recursive TextTools engine. Note: without the non-recursive rewrite of 2.1.0, the test suite will not pass all tests. A single test (which is tested with a number of different versions of the simpleparse grammar) will fail. I'm not sure why it fails with the recursive version, but it does argue for using the non-recursive rewrite.

To build the non-recursive TextTools engine, you'll need to get the source distribution for the non-recursive implementation from the SimpleParse file repository. This archive is intended to be expanded over the mxBase source archive from the top-level directory (it was created with the 2.1.0 beta1 distribution specifically), replacing one file and adding four others.

cd egenix-mx-base-2.1.0
gunzip non-recursive-1.0.0b1.tar.gz
tar -xvf non-recursive-1.0.0b1.tar

(Or use WinZip on Windows). When you have completed that, run:

setup.py build --force install

in the top directory of the eGenix-mx-base source tree. It is hoped that eventually the non-recursive rewrite will be folded into the eGenix-mx-base distribution so this extra step won't be necessary.

Features

New in 2.0:

New, refactored and simplified API. Most of the time you only need to deal with a single class for all your interactions with the parser system (simpleparse.parser.Parser), and one module if you decide to use the provided post-processing mechanism (simpleparse.dispatchprocessor).
"Expanded Productions" -- allow you to define productions whose children are reported as if the enclosing production did not exist (allows you to use productions for organisational as well as reporting purposes)
Exposure of callout mechanism in mxTextTools
Exposure of "LookAhead" mechanism in mxTextTools (allows you to spell "is followed by", "is not followed by", or "matches x but doesn't match y" in SimpleParse EBNF grammars). Specified with the prefix ?, as in ?-"this" which matches iff "this" is not the next item, but on matching doesn't move the read-head forward (more precisely, it causes the engine to continue processing at the previous position).
"Error on fail" error-reporting facility, allows you to raise Parser Syntax Errors when particular productions (or element tokens) fail to match. Allow for fairly flexible error reporting. To specify, just add a '!' character after the element token that must match, or include it as a stand-alone token in a sequential group to specify that all subsequent items must succeed. You can specify an error message format by using a string literal after the ! character.
Library of common constructs (simpleparse.common package) which are easily included in your grammars
Hexidecimal escapes for string and character ranges
Rewritten generators -- the generator interface has been seperated from the parser interfaces, this makes it possible to write grammars directly using generator objects if desired, and allows defining the EBNF grammar using the same tools as generate derived parsers
An XML-Parser (including DTD parsing) based on the XML specification's EBNF (this is not a production parser, merely an example for parsing a complex file format, and is not yet Unicode capable)
Example VRML97 and LISP parsers
Compatability API for SimpleParse 1.0 applications
With the non-recursive mxTextTools, can process (albeit inefficiently) recursion-as-repetition grammars
Non-recursive rewrite of mxTextTools now ~95% of the speed of the recursive version

General

Simple-to-use interface, define an EBNF and start parsing
Fast for small files -- this is primarily a feature of the underlying TextTools engine, rather than a particular feature of the parser generator.
Allows pre-built and external parsing functions, which allows you to define Python methods to handle tricky parsing tasks

"Class" of Parsers Generated

Our (current) parsers are top-down, in that they work from the top of the parsing graph (the root production). They are not, however, tokenising parsers, so there is no appropriate LL(x) designation as far as I can see, and there is an arbitrary lookahead mechanism that could theoretically parse the entire rest of the file just to see if a particular character matches). I would hazard a guess that they are theoretically closest to a deterministic recursive-descent parser.

There are no backtracking facilities, so any ambiguity is handled by choosing the first successful match of a grammar (not the longest, as in most top-down parsers, mostly because without tokenisation, it would be expensive to do checks for each possible match's length). As a result of this, the parsers are entirely deterministic.

The time/memory characteristics are such that, in general, the time to parse an input text varies with the amount of text to parse. There are two major factors, the time to do the actual parsing (which, for simple deterministic grammars should be close to linear with the length of the text, though a pathalogical grammar might have radically different operating characteristics) and the time to build the results tree (which depends on the memory architecture of the machine, the currently free memory, and the phase of the moon). As a rule, SimpleParse parsers will be faster (for suitably limited grammars) than anything you can code directly in Python. They will not generally outperform grammar-specific parsers written in C.

Missing Features

SimpleParse does not current use an Earley or similar highly generalised parser, instead, it uses a simple deterministic parsing algorithm which, though fast for certain classes of problems, is incapable of dealing with ambiguity, backtracking or cross-references
The library of common patterns is extremely sparse
No case-insensitive matching commands available
Unicode support
There is no analysis or (significant) reduction done on the grammar. Having now read most of Parsing Techniques - A Practical Guide, I can see how some fairly significant changes will be required to support such operations (and thereby the more common parsing techniques).

Possible Future Directions

Alternative parsing back-ends -- the new objectgenerator module is fairly well isolated from the rest of the system, and encompasses most of the dependencies on the mxTextTools engine. Adding an optional Earley or similar back-end should be possible with minimal upset to the project. A backend using re objects is another possibility (my precursor mcf.pars engine was written to use regexen for parsing, and was an acceptable (though not stellar) performer).
Alternative EBNF grammars -- SimpleParse's EBNF, though fairly readily understood, is not by any means the only EBNF variant, providing support for a number of EBNF variants would ease the job of porting grammars to the system.
More common/library code -- common data formats, HTML and/or SGML parsers

mxTextTools Rewrite Enhancements

Case-insensitive matching commands?
Backtracking support?

Alternate C Back-end?

Given the amount of effort poured into the mxTextTools engine, this may seem silly, but it would be nice to implement a more advanced parsing algorithm directly in C, without going through the assembly-like interface of mxTextTools. Given that Marc-André isn't interested in adopting the non-recursive codebase, there's not much point retaining compatability with mxTextTools, so moving to a more parser-friendly engine might be the best approach.

Copyright, License & Disclaimer

Permission to use, copy, modify, and distribute this software and its documentation for any purpose and without fee or royalty is hereby granted, provided that the above copyright notice appear in all copies and that both the copyright notice and this permission notice appear in supporting documentation or portions thereof, including modifications, that you make.

THE AUTHOR MIKE C. FLETCHER DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE!

A
Open Source project