Abstract Syntax Trees

Exercises

1. Extend the expressions with a modulo operator % and an abs(_) function.
2. Write a better pretty printer that only outputs the minimal number of parentheses required
   to preserve the semantics of the expression.
3. Introduce a unary minus operator -x as syntactic sugar for the expression 0-x.
   This means that unary minus is defined in the grammar, but not in the syntax trees.
4. Implement a function that simplifies the constant parts of a tiny expression. Include
   algebraic rules on expressions involving identifiers, if you feel up to it.

Reading

• JDT documentation (see Eclipse Help)
• Dragon, Chapter 5.1-5.3 - note that the specifics of attribute-grammars notations will not be used in the course.
• Dragon, Chapter 5.4-5.5 - provides a deeper explanation of how actions are incorporated into the parse

Materials

ASTs and the JDT

Examples

src-antlr contains the antlr.astexample directory which includes the ASTOperator.g and ASTRewrite.g files that make use ANTLR's builtin support for tree construction and transformation. It also has, in antlr.example4, the grammar Example4.g which defines semantic actions to evaluate a given input expression.

src-jdt contains some fragments of code that illustrate how to use the JDT. The CollectXTest.java program is a unit test driver to exercise the CollectInt.java and ColelctName.java functionality.

A third interesting example is not loaded into SVN yet; it is accessible here. You should unzip this archive into your workspace and it will create the directory antlr.explicitast. This contains an example that explicitly constructs a non-ANTLR representation of a simple expression AST. It is instructive to study as you are getting started.

Use these as starting points to explore ANTLR's support for syntax directed translation and semantic actions. You should feel free to modify and experiment with them.