Automated ANTLR tree walker generation

Admiraal, A.J. (2010) Automated ANTLR tree walker generation.

Abstract: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 ANTLRTG, an extension for ANTLR that allows the user to automatically generate a matching tree walker based on the specification of an ANTLR parser. An algorithm has been created, using a tree pattern algebra, that can determine a tree walker that is able to parse all possible tree walkers that can be generated by a given parser. ANTLRTG has been fully implemented and is demonstrated through a case-study that implements a compiler for the Triangle language
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science MSc (60300)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page