PetitParser SPL case study


PetitParser is a top-down parsing framework that combines scannerless parsing, parser combinators, parsing expression grammars and packrat parsers. We present here the steps involved in using PP2 (PetitParser2) to implement an interpreter for SPL, a simple structured programming language designed to be used as an exercise in a Compiler Construction course.


NB: There is also an PetitParser SPL case study slideshow.

What is SPL?

This case study explores how to use PetitParser todevelop an interpreter for a simple structured programming language. Start by by having a quick look at SPL.

What is PetitParser?

If you haven't already done so, read the Parsing with PetitParser2 tutorial.

Scannerless parsing with PetitParser

Since PetitParser is a scannerless parser framework, there is no lexical analysis phase. Instead, the same kinds of parser rules are used to detect tokens. We illustrate this by defining simple parsers for the tokens of SPL. See Parsing SPL tokens.

Debugging grammar rules

We continue by developing the grammar rules step-by-step. See Debugging SPL grammar rules.

Extracting a parser class

We continue to script the grammar rules until we have a more-or-less complete script. Actually, at any point we can decide to extract a parser class from the script, and then continue developing with the new class. See Extracting a class from a PetitParser script.

Testing with examples

So far we have been testing our scripted parser with code snippets, but of course we would like proper regression tests. In GT these will be example methods. To see how to do this, go to Testing a PetitParser class.

Adding parser actions to build the SPL AST

Our SPLGrammar PP2CompositeNode subclass: #SPLGrammar instanceVariableNames: 'keyword identifier boolean integer float number string varDecl primary unary factor term comparison equality logicAnd logicOr assignment expression exprStmt printStmt ifStmt whileStmt block statement declaration program parenthesizedExpression negatedUnary assignmentExpression comment ignorable' classVariableNames: '' package: 'GToolkit-Demo-SPL-PetitParser' parser only recognizes SPL code, but does not do anything useful with it, but return a collection of recognized tokens. We now want to build an AST that can be interpreted. This is decsribed in Using PetitParser to build an AST.

Implementing an SPL interpreter

In the last step we build an SPL interpreter. Instead of implementing this as a visitor that visitors the AST nodes, we directly use the AST as part of the state of a running SPL program using a small-step operation semantics. The details are described in Implementing an SPL interpreter.

SPL Facade

We have now seen all the steps involved in parsing SPL, building an AST and interpreting it. Finally we introduce an SPL Object subclass: #SPL instanceVariableNames: '' classVariableNames: '' package: 'GToolkit-Demo-SPL-SPL' Facade class containing a few convenience methods and examples. See SPL Facade