There are many Python parser libraries available. I have discussed mx.TextTools, SimpleParse, and SPARK in this column and covered PLY in my book (see Resources for links to these documents). Offhand, I know of PyGgy, Yapps, PLEX, PyLR, PyParsing, and 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 contrast to PLY or Spark, DParser itself is written in C, and is thus likely to be 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 at 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, despite 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 white space recognition (that separates parse symbols) by defining the reserved d_whitespace() function; this enables you 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 sub-productions of one another. This grammar handles a problem similar to the "dangling else" issue for many parsers. Specifically, how do you know when to stop looking for larger productions? (For example, 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 few examples illustrate this. First, the program itself:

#!/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'))

Let's run the parser against a few phrases to illustrate:

$ 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 when it encounters ambiguous phrases. 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.

Back to top

Addressing ambiguity

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

$ 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 five word productions), and should it 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 the cases that it does -- more confusing, in a way, than understanding why it sometimes does not work.

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

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:

$ 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:

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

I found some difficult-to-explain anomalies 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 ran with debugging information!

$ 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

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 only happens when something is unambiguously wrong in a lookahead. Roughly, anyway.

Back to top

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. By default, the actions in a function body are only performed on a 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.)

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.

Back to top

More on priorities

The earlier use of an assigned priority for the ABC production was a little bit of a hack, I confess. But in cases of straightforward ambiguity, fine tuning terminal priorities is a great tool. Let me give another grammar with a straightforward ambiguity:

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. For example:

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

Of course, you might get lucky with a particular phrase:

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

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

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):

$ 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

Back to top

Making a decision

Despite receiving recommendations from several readers, I am only lukewarm about DParser. It has quite a few powerful switches and options to productions that I have not discussed -- for example, specifying associativity. Overall, the DParser language is quite robust, and I strongly suspect that DParser for Python will run significantly faster than most pure-Python parsers.

However, I still cannot work up a great deal of 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 grammar with any parsing tool produces similar surprises, but I found DParser's somehow particularly surprising; SimpleParse, for example, surprised me less. Probably if I knew more about the ins-and-outs of the 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 still know less.

Resources

• Check out the DParser homepage on SourceForge.
  
  
• Documentation of the specifics of the Python binding are available. Many of the advanced features, however, are best documented in the DParser library documentation -- the Python wrapper is fairly thin.
  
  
• Several earlier Charming Python 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).
  
  
• Browse all of the Charming Python columns on developerWorks.
  
  
• David's Text Processing in Python (Addison Wesley, 2003) 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.
  
  
• Find more resources for Linux developers in the developerWorks Linux zone.
  
  
• Browse for books on these and other technical topics.
  
  
• Develop and test your Linux applications using the latest IBM tools and middleware with a developerWorks Subscription. You get IBM software from WebSphere, DB2, Lotus, Rational, and Tivoli, and a license to use the software for 12 months, all for less money than you might think.
  
  
• Download no-charge trial versions of selected developerWorks Subscription products that run on Linux, including WebSphere Studio Site Developer, WebSphere SDK for Web services, WebSphere Application Server, DB2 Universal Database Personal Developers Edition, Tivoli Access Manager, and Lotus Domino Server, from the Speed-start your Linux app section of developerWorks. For an even speedier start, help yourself to a product-by-product collection of how-to articles and tech support.
  
  

About the author

David Mertz has been writing the developerWorks columns Charming Python and XML Matters since 2000. Check out his book Text Processing in Python. For more on David, see his personal Web page.

Rate this article

Comments

Back to top

Table of contents

• Finding a longest production
• Addressing ambiguity
• A little on debugging
• More on priorities
• Making a decision
• Resources
• About the author
• Comments