ANTLR is actually a parser generator which enables the end user to write flexible multi-pass language parsers. It could produce a parser which develops an abstract syntax tree from the parsed text, also it can generate tree walkers which may parse this tree. A common ANTLR multi-pass language parser contains a minimum of one tree walkers, that may be used as checker, optimiser and/or code generator. Making sure a tree walker accurately matches the abstract syntax trees made by the parser is a manual task. Whenever a change in the parser specs impacts the abstract syntax tree, all tree walkers must be examined and changed accordingly. Mistakes can result in nontrivial errors and might thus be difficult to find and fix. This could be a serious issue, both for knowledgeable and unskilled users, both during development and maintenance of a language parser. The root-cause of this challenge lies in the redundancy between the ANTLR parser and tree walker specifications…
Contents: Automated ANTLR tree walker generation
Introduction
1.1 ANTLR
1.1.1 Compilation phases
1.1.2 Abstract syntax trees
1.1.3 EBNF
1.1.4 Concrete Syntax Trees
1.2 Problem description
1.3 Overview of the thesis
2 Preliminaries and related work
2.1 Language parsing
2.1.1 Grammars
2.1.2 Abstract Syntax Trees
2.2 Tree representation
2.2.1 Classical notation
2.2.2 First-child, next-sibling notation
2.2.3 Linear notation
2.2.4 Properties of FCNS trees
2.3 Related work
3 Generating the tree grammar
3.1 Rationale
3.2 Tree pattern algebra
3.2.1 Tree patterns
3.2.2 Operations on tree patterns
3.2.3 Master and slave patterns
vCONTENTS
3.3 The context-free tree grammar
3.4 Building the AST
3.4.1 Rewriting production rules
3.4.2 Single carets
3.4.3 Normal-form
3.5 Modelling an annotated context-free grammar
3.5.1 Overview
3.5.2 Patterns that provide the root
3.5.3 Iterating through the rule
3.6 Constructing the context-free tree grammar
3.6.1 Overview
3.6.2 Start symbol
3.6.3 Pattern rules
4 Optimisation of the tree grammar
4.1 Macro expansion
4.2 Rule merging
4.2.1 Limitations to rule merging
4.3 Further optimisations
5 Implementation of ANTLRT G
5.1 Architectural overview
5.1.1 Integrated parser specification
5.1.2 Walker generator
5.2 Design
5.2.1 Algorithm
5.2.2 Grammar
5.3 Usage
5.3.1 Action annotations
5.3.2 Invocation
6 Case study: Triangle
6.1 Design of the Triangle compiler
6.1.1 Lexical analyser and parser
6.1.2 Checker
vi6.1.3 Generator
6.2 Generated C code
6.3 Evaluation
7 Conclusions
7.1 Summary
7.2 Evaluation of ANTLRT G
7.3 Future work
A ANTLRT G sources
A.1 FCNSTree class
A.2 TreePattern class
A.3 ANTLRT G grammar…
Source: University of Twente
Download URL 2: Visit Now