CHARMING PYTHON #B19: DParser for Python. -- Exploring Another Python Parser --

There are many Python parser libraries out there. I have written discussions of mx.TextTools, SimpleParse, SPARK, in this column; and of PLY in my book. Offhand, I know to exist PyGgy, Yapps, PLEX, PyLR, PyParsing, TPG, and I have vague recollections of reading announcements of a half dozen others. This is a category where users might be frustrated not by the dearth, but by the glut of high quality libraries.

What distinguishes DParser from all the others? Well, like PLY and Spark, DParser for Python utilizes function documentation strings to indicate its productions. This style lets you put action code right inside a production, for events that should occur when a particular grammar rule is fulfilled; the production-in-docstring style also lets you manipulate parse trees as parsing occurs. In contast to PLY or Spark, DParser itself is written in C, and so likely considerably faster than pure-Python parsers. DParser for Python is a fairly thin wrapper around an underlying C library--callbacks into Python take some extra time, but the basic parsing is a C speeds. For this article, however, I have not attempted any specific benchmarks, so exactly how fast or slow DParser is compared to other parsers is not something I can directly comment on.

In my own mind, I remain quite fond of SimpleParse's approach. SimpleParse is a wrapper to the fast mx.TextTools library (also written in C) that cleanly separates an EBNF grammar language from Python code. Usually using SimpleParse means generating a parse tree in one function call, then traversing this tree in separate code. For very large parsed documents, such a two step approach might be inefficient, but I find it easier to understand code written this way.

Still, enough of my readers have recommended Dparser for Python that it warrants a look, even given my preference for an isolated EBNF definition. By the way, as you will see in the examples, DParser uses no separate tokenization pass, just straight parsing. You can control whitespace recognization (that separates parse symbols) by defining the reserved d_whitespace() function; this amounts to being able to tokenize however you like.

Finding A Longest Production

As a first example of a DParser for Python program, I created a grammar that looks for several patterns that are subproductions of one aonther. This grammar handles a problem similar to the "dangling else" issue for many parsers. That is: how do you know when to stop looking for larger productions (e.g. is an "if" followed by an "else"?). My grammar looks at phrases that might contain words starting with "a", with "b" and with "c", in that order. All non-included words are just part of the "head" or "tail" of the phrase. A couple examples illustrate this, first the program itself:

Parser abc.py

#!/usr/bin/env python2.3
"Identify sequence of a-, b-, c- words"
#
#-- The grammar
def d_phrase(t, s):
    'phrase : words ( ABC | AB | A ) words'
    print "Head:", ''.join(s[0])
    print t[1][0]+":", ''.join(s[1])
    print "Tail:", ''.join(s[2])
def d_words(t):
    'words : word*'
def d_word(t):
    'word : "[a-z]+" '
def d_A(t):
    '''A : "a[a-z]*" '''
    return 'A'
def d_AB(t):
    '''AB : A "b[a-z]*" '''
    return 'AB'
def d_ABC(t):
    '''ABC : AB "c[a-z]*" '''
    return 'ABC'
#
#-- Parse STDIN
from dparser import Parser
from sys import argv, stdin
phrase, arg = stdin.read(), argv[-1]
Parser().parse(phrase,
               print_debug_info=(arg=='--debug'))

Simple to parse phrases

$ echo -n "alpha" | ./abc.py
Head:
A: alpha
Tail:
echo -n "xavier alpha beta charlie will" | ./abc.py
Head: xavier
ABC: alpha beta charlie
Tail: will
$ echo -n "mable delta xavier bruce" | ./abc.py
Traceback (most recent call last): [...]
dparser.SyntaxError:
syntax error, line:1
mable delta xavier bruce[syntax error]

So far, so good, apparently. My grammar finds an ABC when it is available, but settles for an A, or AB, when that is all there is to find.

But in truth, my grammar has a lot of problems in it when it encounters ambiguous grammars. In most cases, it appears that DParser will fall into an infinite loop when it cannot decide how to parse a phrase--probably the worst outcome; at least a traceback or reported error would tell you what went wrong. Sometimes (on my Mac OSX machine, at least), it produces a "Bus error" instead. I do not like either of those cases.

Addressing Ambiguity

Since all of the terminal productions have the same priority, the parser cannot decide how to parse something like:

Trying to parse an ambiguous phrase

$ echo -n "alex bruce alice benny carl" | ./abc.py

Is this an AB followed by words? Is it words followed by ABC? For that matter, is it all words (made of of five word productions), and should raise a dparser.SyntaxError? I wind up with a "Bus error" or a frozen task rather than a parse. In the prior examples, the ambiguity happened to work out because of the eagerness of each production: once an ABC was found, the leading and trailing words fell into place.

It is quite confusing, actually, to understand exactly why the prior grammar works in those cases it does; more confusing, in a way, that understanding why it sometimes does not work.

Let us say that our desire in parsing a phrase is to find an ABC production whenever one exists, even if some other production (i.e. an AB) is satisfied first in left-to-right traversal. We can do that by elevating the priority of the ABC terminal production:

Revised d_ABC() production function for abc2.py

def d_ABC(t):
    'ABC : AB "c[a-z]*" $term 1'
    return 'ABC'

If a priority is not specified, a production is priority 0. Otherwise, any positive or negative integer may be used to rank productions. Now we can run:

Successfully finding late ABC

$ echo -n "alex bruce alice benny carl" | ./abc2.py
Head: alex bruce
ABC: alice benny carl
Tail:

Notice that alternatives within the (ABC|AB|A) alternation are all tried before the parser looks for the trailing words. So this succeeds without any priority specification:

No ambiguity issue between A and AB

$ echo -n "alex alice benny" | ./abc.py    Head: alex
AB: alice benny
Tail:

I found some difficult to explain anamolies in the behavior of DParser in the face of ambiguity. For example, adding, a trailing word that is definitely not an A convinces the parser to work--but only if run with debugging information!

Erratic behavior in face of ambiguity

$ echo -n "alex bruce alice benny carl dave" | ./abc.py
[...process freezes...]
$ echo -n "alex bruce alice benny carl dave" | ./abc.py --debug
[...debugging trace of speculative and final productions...]
Head: alex bruce
ABC: alice benny carl
Tail: dave

Either way, the priority specification in abc2.py resolves the parse in either case.

It is rather subtle and hard to understand exactly when ambiguities are resolved. Basically, productions are fulfilled as they are seen, left-to-right, and each one tries to grab as many words as it can, left-to-right. Backtracking happens only when something is unambiguously wrong in a lookahead. Roughly, anyway.

A Little On Debugging

One thing I like about DParser is its option to display debugging information. Seeing this does not necessarily make it obvious how to create a correct grammar, but at least it provides nice insight into the actions a parser takes when processing a particular phrase. For example:

#------- Showing a trace of speculative productions
$ echo -n "alex alice benny carl dave" | ./abc2.py --debug
               d_words ???:
                   d_A ???:     alex
                d_word ???:     alex
               d_words ???:
              d_phrase ???:     alex
               d_words ???:     alex
                   d_A ???:     alice
                d_word ???:     alice
               d_words ???:
               d_words ???:     alice
              d_phrase ???:     alex alice
              d_phrase ???:     alex alice
               d_words ???:     alex alice
                d_word ???:     benny
                  d_AB ???:     alice benny
               d_words ???:     benny
               d_words ???:     alice benny
               d_words ???:
              d_phrase ???:     alex alice benny
              d_phrase ???:     alex alice benny
              d_phrase ???:     alex alice benny
               d_words ???:     alex alice benny
                d_word    :     alex
               d_words    :     alex
                   d_A    :     alice
                  d_AB    :     alice benny
                 d_ABC ???:     alice benny carl
               d_words ???:
              d_phrase ???:     alex alice benny carl
                 d_ABC    :     alice benny carl
                d_word ???:     dave
               d_words ???:     dave
              d_phrase ???:     alex alice benny carl dave
                d_word    :     dave
               d_words    :     dave
              d_phrase    :     alex alice benny carl dave
Head: alex
ABC: alice benny carl
Tail: dave

The productions followed by question marks are speculative attempts; those without are final productions actually followed. Related to this, DParser gives you the capability to take actions differentially when a production is entered either speculatively or on a final parse. But default, the actions in a function body are only performed ona final parse. But you may specify either of two extra arguments to a production to handle speculative parses (there are also a number of other optional arguments not discussed in this article):

Actions during speculative parsing

def d_prod1(t, spec_only):
    'prod1 : this that+ other?'
    print "Speculative parse of prod1"
def d_prod2(t, spec):
    'prod2: spam* eggs toast'
    if spec:
        print "Speculative parse of prod2"
    else:
        print "Final parse of prod2"

Of course, all the information displayed by my speculative productions is also displayed (in slightly different form) by using the print_debug_info argument to dparser.Parser.parse(). But you could also decide to take other actions--trigger external events, for example.

Term-for-term ambiguous grammar, ibm.py

def d_phrase(t, s):
    'phrase : word ( vowel | caps | threeletter ) word'
    print "Head:", ''.join(s[0])
    print t[1][0]+":", ''.join(s[1])
    print "Tail:", ''.join(s[2])
def d_word(t): 'word : "[A-Za-z]+" '
def d_vowel(t):
    'vowel : "[AEIOUaeiou][A-Za-z]*"'
    return 'VOWEL'
def d_caps(t):
    'caps : "[A-Z]+"'
    return 'CAPS'
def d_threeletter(t):
    'threeletter : "[A-Za-z][A-Za-z][A-Za-z]"'
    return '3LETT'
#-- Parse STDIN
from dparser import Parser
from sys import stdin
Parser().parse(stdin.read())

The productions for vowel, caps and threeletter are not necessarily distinct, they can all grab an overlapping set of words, e.g.:

When DParser detects ambiguity gracefully

$ echo -n "Read IBM developerWorks" | ./ibm.py
Traceback (most recent call last): [...]
dparser.AmbiguityException:  [...]

Fortuitous avoindance of parse ambiguity

$ echo -n "Read GNOSIS website" | ./ibm.py
Head: Read
CAPS: GNOSIS
Tail: website

Rather than hope for good luck, let us explicitly indicate a priority between productions:

Resolving ambiguous term, ibm2.py

def d_vowel(t):
    'vowel : "[AEIOUaeiou][A-Za-z]*" $term 3'
    return 'VOWEL'
def d_caps(t):
    'caps : "[A-Z]+" $term 2'
    return 'CAPS'
def d_threeletter(t):
    'threeletter : "[A-Za-z][A-Za-z][A-Za-z]" $term 1'
    return '3LETT'

Now every phrase would like to identify middle word types in a specific order (only of ones possible, of course):

Disambiguated parse results

$ echo -n "Read IBM developerWorks" | ./ibm2.py
Head: Read
VOWEL: IBM
Tail: developerWorks
$ echo -n "Read XYZ journal" | ./ibm2.py
Head: Read
CAPS: XYZ
Tail: journal

Making A Decision

Despite its recommendation by several readers, I am only lukewarm about DParser. It has quite a few powerful switches and options to productions that I have not gone into--for example, specifying associativity; overall the DParser language is quite robust. And I strongly suspect DParser for Python will run significantly faster than most pure-Python parsers.

However, I still cannot work up a complete enthusiasm for the function docstring style of parsers; obviously, many excellent Python programmers disagree with me on this. But I also found some of the parse results a little bit mystifying: Why succeed in debug mode, but not standard mode? Exactly when does ambiguity come up? Developing a grammer with any parsing tool produces similar surprises, but I somehow found DParser's particularly surprising; SimpleParse, for example, surprised me less. Probably if I knew more about the ins-and-outs of underlying parsing algorithms it would make more sense; in my relative ignorance, I am probably a lot like 95%+ of my readers though. There are people who know more about parsing than I do; but in truth, most programmers know still less.

Resources

Several earlier installments have looked at other parsers for Python. Spark and PLY are similar to DParser in using docstrings of functions to describe productions. mx.TextTools is a lower-level state machine, and SimpleParse makes use of a non-Python EBNF syntax to describe grammars (and translates it to fast mx.TextTools operations, behind the scenes).

My book, Text Processing in Python discusses both SimpleParse and mx.TextTools (borrowing from my corresponding developerWorks articles), but adds a discussion of PLY. You can read the book online, or buy it at fine bookstores:

About The Author

David Mertz thinks that artificial languages are perfectly natural, but natural languages seem a bit artificial. David may be reached at [email protected]; his life pored over athttp://gnosis.cx/publish/. Check out David's book Text Processing in Python (http://gnosis.cx/TPiP/).

Charming Python #b19: Dparser For Python.

Exploring Another Python Parser

Why Look At Dparser, Too?