Writing Parsers with PetitParser

After the announcement in the Moose mailing list and after various people have asked me to provide some introduction to PetitParser I decided to write short tutorial.

Originally I have written PetitParser as part of my work on the Helvetia system. PetitParser is a parsing framework different to many other popular parser generators. For example, it is not table based such as SmaCC or ANTLR. Instead it uses a unique combination of four alternative parser methodologies: scannerless parsers, parser combinators, parsing expression grammars and packrat parsers. As such PetitParser is more powerful in what it can parse and it arguably fits better the dynamic nature of Smalltalk. Let’s have a quick look at these four parser methodologies:

1. Scannerless Parsers combine what is usually done by two independent tools (scanner and parser) into one. This makes writing a grammar much simpler and avoids common problems when grammars are composed.
2. Parser Combinators are building blocks for parsers modeled as a graph of composable objects; they are modular and maintainable, and can be changed, recomposed, transformed and reflected upon.
3. Parsing Expression Grammars (PEGs) provide ordered choice. Unlike in parser combinators, the ordered choice of PEGs always follows the first matching alternative and ignores other alternatives. Valid input always results in exactly one parse-tree, the result of a parse is never ambiguous.
4. Packrat Parsers give linear parse time guarantees and avoid common problems with left-recursion in PEGs.

Loading PetitParser

Enough theory, let’s get started. PetitParser is developed in Pharo, but is also available on other Smalltalk platforms. A ready made image can be downloaded here. To load PetitParser into an existing image evaluate the following Gofer expression:

Gofer new
   renggli: 'petit'; 
   package: 'PetitParser';
   package: 'PetitTests';
   load.

There are other packages in the same repository that provide additional features, for example PetitSmalltalk is a Smalltalk grammar, PetitXml is an XML grammar, PetitJson is a JSON grammar, PetitAnalyzer provides functionality to analyze and transform grammars, and PetitGui is a Glamour IDE for writing complex grammars. We are not going to use any of these packages for now.

More information on how to get PetitParser can be found on the website of the project.

Writing a Simple Grammar

Writing grammars with PetitParser is simple as writing Smalltalk code. For example to write a grammar that can parse identifiers that start with a letter followed by zero or more letter or digits is defined as follows. In a workspace we evaluate:

identifier := #letter asParser , #word asParser star.

If you inspect the object identifier you’ll notice that it is an instance of a PPSequenceParser. This is because the #, operator created a sequence of a letter and a zero or more word character parser. If you dive further into the object you notice the following simple composition of different parser objects:

PPSequenceParser (this parser accepts a sequence of parsers)
    PPPredicateObjectParser (this parser accepts a single letter)
    PPRepeatingParser (this parser accepts zero or more instances of another parser)
       PPPredicateObjectParser (this parser accepts a single word character)

Parsing Some Input

To actually parse a string (or stream) we can use the method #parse::

identifier parse: 'yeah'.          " --> #($y #($e $a $h)) "
identifier parse: 'f12'.           " --> #($f #($1 $2)) "

While it seems odd to get these nested arrays with characters as a return value, this is the default decomposition of the input into a parse tree. We’ll see in a while how that can be customized.

If we try to parse something invalid we get an instance of PPFailure as an answer:

identifier parse: '123'.           " --> letter expected at 0 "

Instances of PPFailure are the only objects in the system that answer with true when you send the message #isPetitFailure. Alternatively you can also use #parse:onError: to throw an exception in case of an error:

identifier
   parse: '123'
   onError: [ :msg :pos | self error: msg ].

If you are only interested if a given string (or stream) matches or not you can use the following constructs:

identifier matches: 'foo'.         " --> true "
identifier matches: '123'.         " --> false "

Furthermore to find all matches in a given input string (or stream) you can use:

identifier matchesIn: 'foo 123 bar12'.

Similarly, to find all the matching ranges in the given input string (or stream) you can use:

identifier matchingRangesIn: 'foo 123 bar12'.

Different Kinds of Parsers

PetitParser provide a large set of ready-made parser that you can compose to consume and transform arbitrarily complex languages. The terminal parsers are the most simple ones. We’ve already seen a few of those:

The class side of PPPredicateObjectParser provides a lot of other factory methods that can be used to build more complex terminal parsers.

The next set of parsers are used to combine other parsers together:

So instead of using the #word predicated we could have written our identifier parser like this:

identifier := #letter asParser , (#letter asParser / #digit asParser) star.

To attach an action or transformation to a parser we can use the following methods:

To return a string of the parsed identifier, we can modify our parser like this:

identifier := (#letter asParser , (#letter asParser / #digit asParser) star) flatten.

These are the basic elements to build parsers. There are a few more well documented and tested factory methods in the operations protocol of PPParser. If you want browse that protocol.

Writing a More Complicated Grammar

Now we are able to write a more complicated grammar for evaluating simple arithmetic expressions. Within a workspace we start with the grammar for a number (actually an integer):

number :=  #digit asParser plus token trim ==> [ :token | token value asNumber ].

Then we define the productions for addition and multiplication in order of precedence. Note that we instantiate the productions as PPUnresolvedParser upfront, because they recursively refer to each other. The method #def: resolves this recursion using the reflective facilities of the host language:

term := PPUnresolvedParser new.
prod := PPUnresolvedParser new.
prim := PPUnresolvedParser new.
 
term def: (prod , $+ asParser trim , term ==> [ :nodes | nodes first + nodes last ])
   / prod.
prod def: (prim , $* asParser trim , prod ==> [ :nodes | nodes first * nodes last ])
   / prim.
prim def: ($( asParser trim , term , $) asParser trim ==> [ :nodes | nodes second ])
   / number.

To make sure that our parser consumes all input we wrap it with the end parser into the start production:

start := term end.

That’s it, now we can test our parser and evaluator:

start parse: '1 + 2 * 3'.       " --> 7 "
start parse: '(1 + 2) * 3'.     " --> 9 "

As an exercise we could extend the parser to also accept negative numbers and floating point numbers, not only integers. Furthermore it would be useful to add support subtraction and division as well. All these features can be added with a few lines of PetitParser code.

Disk Filesystem

A while ago Colin Putney announced the Filesystem framework, a nice and extensible replacement for the ugly FileDirectory class in Pharo. While all core classes are well commented, there is a quick start missing that explains how end users are supposed to adopt the framework. This blog post should fill that gap.

First we need to load the package:

 Gofer new
     wiresong: 'mc';
     package: 'Filesystem';
     load.

The framework supports different kinds of filesystems that can be used interchangeably and that can transparently work with each other. The most obvious one is the filesystem on your hard disk. We are going to work with that one for now:

 working := FSDiskFilesystem current working.

Put the above code into a workspace and evaluate it. It assigns a reference of the current working directory to the variable working. References are the central object of the framework and provide the primary mechanism of working with files and directories. All code below works on FSReference instances.

Navigating the Filesystem

Now lets do some more interesting things. To list all children of your working directory evaluate the following expression:

 working children.

To iterate over all children recursively evaluate:

 working allChildren.

To get a reference to a specific file or directory within your working directory use the slash operator:

 cache := working / 'package-cache'.

Navigating back to the parent is easy:

 cache parent.

You can check for various properties of the cache directory by evaluating the following expressions:

 cache exists.             "--> true"
 cache isFile.             "--> false"
 cache isDirectory.        "--> true"
 cache basename.           "--> 'package-cache'"

To get additional information about the filesystem entry evaluate:

 cache entry creation.     "--> 2010-02-14T10:34:31+00:00"
 cache entry modification. "--> 2010-02-14T10:34:31+00:00"
 cache entry size.         "--> 0 (directories have size 0)"

The framework also supports locations, late-bound references that point to a file or directory. When asking to perform a concrete operation, a location behaves the same way as a reference. Currently the following locations are supported:

 FSLocator desktop.
 FSLocator home.
 FSLocator image.
 FSLocator vmBinary.
 FSLocator vmDirectory.

If you save a location with your image and move the image to a different machine or operating system, a location will dynamically adapt and always point to the place you would expect.

Opening Read- and Write-Streams

To open a file-stream on a file ask the reference for a read- or write-stream:

 stream := (working / 'foo.txt') writeStream.
 stream nextPutAll: 'Hello World'.
 stream close.

 stream := (working / 'foo.txt') readStream.
 stream contents.
 stream close.

Please note that #writeStream overrides any existing file and #readStream throws an exception if the file does not exist. There are also short forms available:

 working / 'foo.txt' writeStreamDo: [ :stream | stream nextPutAll: 'Hello World' ].

 working / 'foo.txt' readStreamDo: [ :stream | stream contents ].

Have a look at the streams protocol of FSReference for other convenience methods.

Renaming, Copying and Deleting Files and Directories

You can also copy and rename files by evaluating:

 (working / 'foo.txt') copyTo: (working / 'bar.txt').

To create a directory evaluate:

 backup := working / 'cache-backup'.
 backup createDirectory.

And then to copy the contents of the complete package-cache to that directory simply evaluate:

 cache copyAllTo: backup.

Note, that the target directory would be automatically created, if it was not there before.

To delete a single file evaluate:

 (working / 'bar.txt') delete.

To delete a complete directory tree use the following expression. Be careful with that one though.

 backup deleteAll.

That’s the basic API of the Filesystem library. If there is interest we can have a look at other features and other filesystem types in a next iteration.