CS 453 PA0 Part 3 -- AST Generation and Visitors

Introduction

There are three major parts to your PA3 assignment: AST construction involves modifying your .cup file so that each production results in an AST node connected to its children. Type checking and code generation involve applying a visitor that walks the AST.

To introduce you to AST construction and the visitor design pattern we will be modifying the PA0 interpreter so that it generates an AST, then uses a visitor in order to unparse the AST in postfix-notation.

We provide you with a complete scanner (in PA0.lex), a set of AST node classes, abstract visitor classes, and a DotVisitor, which will generate a .dot file of your AST. Dot is a file-format for representing directed graphs. Using DOT you can visualize your AST.

The PA0 Language

Recall the grammar from PA0: 
    program ::= stmts | ε
    stmts   ::= stmts stmt | stmt
    stmt    ::= PRINT exp SEMI
    exp     ::= exp TIMES exp | exp PLUS exp | exp MINUS exp | NUMBER
In Part3 we extend the grammar to also allow for parenthesized expressions: 
    exp     ::= LPAREN exp RPAREN

Node Types

We provide a number of node classes (in the ast/node directory) that your parser will instantiate and tie together. The nodes we provide are: Note that IStatement and IExp are interfaces for more specific types of nodes.

Completing PA0 Part 3

Download and extract PA0Part3Empty.tar. Remember, you can test this project by executing: 
    > make
    > java -classpath java-cup-11a-runtime.jar:. PA0 tests/add.in



Next, edit the .cup file so that it produces an AST.  You can visualize
what AST is produced for a program by executing the following commands:


    > make
    > java -classpath java-cup-11a-runtime.jar:. PA0 tests/add.in
    > dot -Tpng tests/add.in.ast.dot > tests/add.png
    > eog tests/add.png



Finally, edit UnparseVisitor so that it outputs a postfix
representation of your program.


Example Inputs, ASTs, and Outputs






 File
 Input
 Output




 add.in 
 
 
 
print 1+2;

  
 		  
 
 
print:  1  2  +

  
 
 [
 Show AST
 ]
  
 
 






 File
 Input
 Output




 stmts.in 
 
 
 
print 1+2;
print 3*4;
print 3-4;

  
 		  
 
 
print:  1  2  + 
print:  3  4  * 
print:  3  4  -

  
 
 [
 Show AST
 ]
  
 
 






 File
 Input
 Output




 noparens.in 
 
 
 
print 1 + 2 * 3;

  
 		  
 
 
print:  1  2  3  *  +

  
 
 [
 Show AST
 ]
  
 
 






 File
 Input
 Output




 parens.in 
 
 
 
print (1 + 2) * 3;

  
 		  
 
 
print:  1  2  +  3  *

  
 
 [
 Show AST
 ]