Alex Admiraal - Automated ANTLR Treewalker Generation

author:Alex Admiraal
title:Automated ANTLR Treewalker Generation
keywords:ANTLR, tree walker T.C. Ruys (1st supervisor) A. Rensink J.P. Katoen
graduation date:12 February 2010 (mark: 7/10)


ANTLR is a parser generator that allows the user to write flexible multi-pass language parsers. It can generate a parser that builds an abstract syntax tree from the parsed text, and it can generate tree walkers that can parse this tree. A typical ANTLR multi-pass language parser consists of one or more tree walkers, which can be used as checker, optimiser and/or code generator.

Ensuring a tree walker correctly matches the abstract syntax trees produced by the parser is a manual task. When a change in the parser specification affects the abstract syntax tree, all tree walkers need to be inspected and changed accordingly. Mistakes can lead to nontrivial errors and may therefore be hard to find and solve. This can be a significant problem, both for experienced and inexperienced users, both during development and maintenance of a language parser.

The root-cause of this problem lies in the redundancy between the ANTLR parser and tree walker specifications. Both specify the syntax of the abstract syntax tree; the parser specifies how it is to be created and the tree walker how it is to be parsed.

This thesis introduces ANTLRTGTG has been fully implemented and is demonstrated through a case-study that implements a compiler for the Triangle language.