Charming Python: Parsing with the SimpleParse module

A concise and readable EBNF-style wrapper

Many parsing tools have been written for Python. This column discusses a high-level parsing language built on top of Python. SimpleParse provides an EBNF-style syntax on top of mxTextTools that can greatly clarify the expression of grammars.

David Mertz, Analyzer, Gnosis Software, Inc.

David Mertz photo David Mertz would like to write, with Nietzsche, that these are the musings of an old philologist, but that untruth would unmask itself. But perhaps his (right here gratuitously plugged) forthcoming book, Text Processing in Python, will someday be mistaken for a cybernetic variant of philology. David may be reached at mertz@gnosis.cx; his life pored over at http://gnosis.cx/dW/. Suggestions and recommendations on this, past, or future columns are welcome.



01 January 2002

Also available in Japanese

Like most programmers, I have frequently needed to identify parts and structures that exist inside textual documents: log files, configuration files, delimited data, and more free-form (but still semi-structured) report formats. All of these documents have their own "little languages" for what can occur within them.

The way I have programmed these informal parsing tasks has always been somewhat of a hodgepodge of custom state-machines, regular expressions, and context-driven string tests. The pattern in these programs was always, roughly, "read a bit of text, figure out if we can make something of it, maybe read a bit more text afterwards, keep trying."

Parsers of the formal variety distill descriptions of the parts and structures in documents into concise, clear, and declarative rules for how to identify what makes up a document. The declarative aspect is particularly interesting here. All my old ad hoc parsers were imperative in flavor: read some characters, make some decisions, accumulate some variables, rinse, repeat. As this column's installments on functional programming have observed, the recipe style of program flow is comparatively error-prone and difficult to maintain.

Formal parsers almost always use variants on Extended Backus-Naur Form (EBNF) to describe the "grammars" of the languages they describe. Those tools we look at here do so, as does the popular compiler development tool YACC (and its variants). Basically, an EBNF grammar gives names to the parts you might find in a document; additionally, larger parts are frequently composed of smaller parts. The frequency and order in which small parts may occur in larger parts is specified by operators -- mostly the same symbols you see in regular expressions. In parser-talk, each named part in a grammar is called a "production."

Possibly without even knowing it, readers have already seen EBNF descriptions at work. For example, the familiar Python Language Reference defines what a floating point number looks like in Python:

EBNF-style description of floating point number
floatnumber:    pointfloat | exponentfloat
pointfloat:     [intpart] fraction | intpart "."
exponentfloat:  (nonzerodigit digit* | pointfloat) exponent
intpart:        nonzerodigit digit* | "0"
fraction:       "." digit+
exponent:       ("e"|"E") ["+"|"-"] digit+

Or you might have seen an XML DTD element defined in an EBNF style. For example, the <body> of a developerWorks tutorial looks like:

EBNF-style description in a developerWorks DTD
<!ELEMENT body  ((example-column | image-column)?, text-column) >

Spellings vary slightly, but the general notions of quantification, alternation, and sequencing exist in all EBNF-style language grammars.

Building tag lists with SimpleParse

SimpleParse is an interesting tool. To use this module, you need the underlying module mxTextTools, which implements a "tagging engine" in C. mxTextTools (see Resources later in this article) is powerful, but rather difficult to use. Once SimpleParse is layered on top of mxTextTools, the work becomes a lot easier.

Using SimpleParse is really quite simple, because it removes the need to think about most of the complexity of mxTextTools. The first thing to do is create an EBNF-style grammar that describes the language you want to handle. The second step is to call mxTextTools to create a tag list that describes all the successful productions when the grammar is applied to the document. Finally, you actually do something with the tag list returned by mxTextTools.

For this article, the "language" we will parse is the set of markup codes used by "smart ASCII" to indicate things like boldface, module names, and book titles. This is the very same language mxTextTools was earlier used to identify, and regular expressions and state-machines before that, in earlier installments. The language is far simpler than a full programming language would be, but complicated enough to be representative.

We probably need to back up for one moment here. What the heck is a "tag list" that mxTextTools gives us? Basically, this is a nested structure that simply gives the character offsets where every production was matched in the source text. mxTextTools traverses a source text quickly, but it does not do anything to the source text itself (at least not when using the SimpleParse grammars). Let's look at an abridged tag list:

Tag list produced from SimpleParse grammar
(1,
 [('plain',
   0,
   15,
   [('word', 0, 4, [('alphanums', 0, 4, [])]),
    ('whitespace', 4, 5, []),
    ('word', 5, 10, [('alphanums', 5, 10, [])]),
    ('whitespace', 10, 11, []),
    ('word', 11, 14, [('alphanums', 11, 14, [])]),
    ('whitespace', 14, 15, [])]),
  ('markup',
   15,
   27,
 ...
 289)

The elipses in the middle represent a bunch more matches. But the part we see says the following. The root production ("para") succeeds and ends at offset 289 (the length of the source text). The child production "plain" matches offsets 0 through 15. This "plain" child is itself composed of smaller productions. After the "plain" production, the "markup" production matches offsets 15 through 27. The details are left out, but this first "markup" is made of components, and additional productions succeed later in the source.


An EBNF-style grammar for "smart ASCII"

We have glanced at the tag list that SimpleParse + mxTextTools can give us. But we really need to look at the grammar that was used to generate this tag list. The grammar is where the real work happens. EBNF grammars are almost self-explanatory to read (although designing one does require a bit of thought and testing):

typographify.def
para           := (plain / markup)+
plain          := (word / whitespace / punctuation)+
whitespace     := [ \t\r\n]+
alphanums      := [a-zA-Z0-9]+
word           := alphanums, (wordpunct, alphanums)*, contraction?
wordpunct      := [-_]
contraction    := "'", ('am'/'clock'/'d'/'ll'/'m'/'re'/'s'/'t'/'ve')
markup         := emph / strong / module / code / title
emph           := '-', plain, '-'
strong         := '*', plain, '*'
module         := '[', plain, ']'
code           := "'", plain, "'"
title          := '_', plain, '_'
punctuation    := (safepunct / mdash)
mdash          := '--'
safepunct      := [!@#$%^&()+=|\{}:;<>,.?/"]

This grammar is almost exactly the way you would describe the "smart ASCII" language verbally, which is a nice sort of clarity. A paragraph consist of some plain text and some marked-up text. Plain text consists of some collection of words, whitespace, and punctuation. Marked-up text might be emphasized, or strongly emphasized, or module names, etc. Strongly emphasized text is surrounded by asterisks. And so on. A couple of features like just what a "word" really is, or just what a contraction can end with, take a bit of thought, but the syntax of EBNF doesn't get in the way.

In contrast, the same sort of rules can be described even more tersely using regular expressions. This is what the first version of the "smart ASCII" markup program did. But this terseness is much harder to write, and harder still to tweak later. The following code expresses largely (but not precisely) the same set of rules:

Python regexs for smart ASCII markup
# [module] names
re_mods =   r"""([\(\s'/">]|^)\[(.*?)\]([<\s\.\),:;'"?!/-])"""
# *strongly emphasize* words re_strong = r"""([\(\s'/"]|^)\*(.*?)\*([\s\.\),:;'"?!/-])"""
# -emphasize- words re_emph = r"""([\(\s'/"]|^)-(.*?)-([\s\.\),:;'"?!/])"""
# _Book Title_ citations re_title = r"""([\(\s'/"]|^)_(.*?)_([\s\.\),:;'"?!/-])"""
# 'Function()' names re_funcs = r"""([\(\s/"]|^)'(.*?)'([\s\.\),:;"?!/-])"""

If you discover or invent some slightly new variant of the language, it is a lot easier to play with the EBNF grammar than with those regular expressions. Moreover, using mxTextTools will generally be even faster in performing the manipulations of the patterns.


Generating and using a tag list

For our sample program, we put the actual grammar in a separate file. For most purposes, this is a good organization to use. Changing the grammar is usually a different sort of task than changing the application logic; and the files reflect this. But the whole of what we do with the grammar is pass it as a string to a SimpleParse function, so in principle we could include it in the main application (or even dynamically generate it in some way).

Let's look at our entire (compact) tagging application:

typographify.py
import os from sys 
import stdin, stdout, stderr from simpleparse 
import generator from mx.TextTools 
import TextTools

input = stdin.read()
decl = open(
'typographify.def').read() from typo_html 
import codes
parser = generator.buildParser(decl).parserbyname('para')
taglist = TextTools.tag(input, parser)
for tag, beg, end, parts in taglist[1]:
    if tag == 'plain':
        stdout.write(input[beg:end])
    elif tag == 'markup':
        markup = parts[0]
        mtag, mbeg, mend = markup[:3]
        start, stop = codes.get(mtag, ('<!-- unknown -->','<!-- / -->'))
        stdout.write(start + input[mbeg+1:mend-1] + stop)
stderr.write('parsed %s chars of %s\n' %  (taglist[-1], len(input)))

Here is what it does. First read in the grammar, and create an mxTextTools parser from the grammar. Next we apply the tag-table/parser to the input source to create a tag list. Finally, we loop through the tag list, and emit some new marked-up text. The loop could, of course, do anything else desired with each production encountered.

For the particular grammar used for smart ASCII, everything in the source text is expected to fall into either a "plain" production or a "markup" production. Therefore, it suffices to loop across a single level in the tag list (except when we look exactly one level lower for the specific markup production, such as "title"). But a more free-form grammar -- such as occurs for most programming languages -- could easily recursively descend into the tag list, and look for production names at every level. For example, if the grammar were to allow nested markup codes, this recursive style would probably be used. You might enjoy the exercise of figuring out how to adjust the grammar (hint: remember that productions are allowed to be mutually recursive).

The particular markup codes that go to the output live in yet another file, for organizational not essential reasons. A little trick of using a dictionary as a switch statement is used here (although the otherwise case remains too narrow in the example). The idea is just that we might in the future want to create multiple "output format" files for, say, HTML, DocBook, LaTeX, or others. The particular markup file used for the example looks like:

typo_html.py
codes = \
{ 'emph'    : ('<em>', '</em>'),
  'strong'  : ('<strong>', '</strong>'),
  'module'  : ('<em><code>', '</code></em>'),
  'code'    : ('<code>', '</code>'),
  'title'   : ('<cite>', '</cite>'),
}

Extending this to other output formats is straightforward.


Conclusion

SimpleParse provides a concise and very readable EBNF-style wrapper to the underlying power and speed of the cryptic mxTextTools C module. Moreover, EBNF grammars are already familiar to many programmers, even if only in passing. I cannot prove anything about what is easier to understand -- intuitions differ -- but I can comment quantitatively on source length. The mxTypographify module that was manually developed earlier is the following size:

wc mxTypographify.py
199     776    7041 mxTypographify.py

Of these 199 lines, a fair number are comments. And 18 of those lines are an included regular expression version of the markup function that is included for timing comparisons. But what the program does is essentially identical to what typographify.py -- listed above -- does. In contrast, our SimpleParse program, including its support files comes to:

wc typo*.def typo*.py
19      79     645 typographify.def
20      79     721 typographify.py
 6      25     205 typo_html.py
45     183    1571 total

In other words, about one fourth as many lines. This version has fewer comments, but that is mostly because the EBNF grammar is fairly self-documenting. I would not want to emphasize LOC too strongly -- obviously, you can play games with minimizing or maximizing code length. But in a general way, one of the few real empirical results of work studies on programmers is that kLOC/programmer-month is fairly close to constant across languages and libraries. Of course, the regular expression version is, in turn, one third as long as the SimpleParse version -- but I think the density of its expression makes it fragile to maintain and harder to write. I think, on balance, SimpleParse wins of the approaches considered.

Resources

Comments

developerWorks: Sign in

Required fields are indicated with an asterisk (*).


Need an IBM ID?
Forgot your IBM ID?


Forgot your password?
Change your password

By clicking Submit, you agree to the developerWorks terms of use.

 


The first time you sign into developerWorks, a profile is created for you. Select information in your profile (name, country/region, and company) is displayed to the public and will accompany any content you post. You may update your IBM account at any time.

All information submitted is secure.

Choose your display name



The first time you sign in to developerWorks, a profile is created for you, so you need to choose a display name. Your display name accompanies the content you post on developerWorks.

Please choose a display name between 3-31 characters. Your display name must be unique in the developerWorks community and should not be your email address for privacy reasons.

Required fields are indicated with an asterisk (*).

(Must be between 3 – 31 characters.)

By clicking Submit, you agree to the developerWorks terms of use.

 


All information submitted is secure.

Dig deeper into Linux on developerWorks


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=Linux, Open source
ArticleID=11188
ArticleTitle=Charming Python: Parsing with the SimpleParse module
publish-date=01012002