Project Part 4

Abstract Syntax Trees

10 Points

Abstract Syntax Trees are a "pared down" parse tree. Each node is an element of the language. The non-leaf nodes represent operators while the leaf nodes represent operands.

Example 1 Abstract Syntax Tree for a + b where a is opnd1 and b is opnd2.

In parenthesized form, this could be written: 

 
     (plus ("a" "b") ) or (+ (a b ) )
 
 or indenting, 

 
     (plus 
          ("a" "b") 
     )
The production that relates to such a node is

If we create a data structure for the nodes of the abstract syntax tree:

then we can add attributes and functions such as:

Example 2 Abstract Syntax Tree for If (a < b) m = 2;

This might be printed out:

(IF ("<" ("a" "b") := ("m" 2") ) )

or, indenting, 

 (IF 
    (
      "<" ("a" "b") 
       := ("m" 2")  
    ) 
 )
Example 3 Abstract Syntax Tree for WHILE (a < b) m = 2 ;

This might be printed out:

(WHILE ("<" ("a" "b") ) := ("m" 2") ) )

or with indenting 

 (WHILE (
    "<"  ("a" "b")  
    ":=" ("m" 2") 
        ) 
 )
(Other indentings possible here)

Consider the following program: 

 void input_a() {
      a = b3;
      xyz = a + b + c - p / q;
      a = xyz * ( p + q );
      p = a - xyz - p;
 }
 
 
 Its ast might be printed out: 

 
     Unit [
        Line(1)
         (void (input_a)
        Line (2)
           (:=
             (a, b3) )  
        Line (3)
           (:=
 	    (xyz, +
 		   (a +
 		      (b -
 		          (c /
                               (p q))))))
 	Line (4)
              (:=
                (a *
                   (xyz +  
                        (p q))))
         Line (5)
              (:=
                (p -
                   (a -
                      (xyz p))))
         Line (6)
            EndVoid) ]
The output need not look exactly like that above, but you should print out line numbers and somehow show the ast structure.

You will use the JJTree tool to build your ast's. Below is an excerpt from the solution: 

 
 options {
   IGNORE_CASE = false;
   OPTIMIZE_TOKEN_MANAGER = true;
   MULTI = false;
   STATIC = false;
 }
 
 PARSER_BEGIN(tea)
 
 import java.io.*;
 
 public class tea {
 
   public static void main(String[] args) throws ParseException,
 						FileNotFoundException
   {
    if ( args.length < 1 ) {
       System.out.println("Please pass in the filename for a parameter.");
       System.exit(1);
    }
 
    tea parser = new tea( new FileInputStream(args[0]) );
 
    SimpleNode root = parser.program();
    root.dump("");
 
    System.out.println("Parse completed.");
   }
 }
 
 PARSER_END(tea)
 
 SKIP: /* Whitespace */
 {
   "\t"
 | "\n"
 | "\r"
 | " "
 }
 
 TOKEN: /* Most Things */
 {
   <IF: "if">
 | <ELSE: "else">
 | <TYPE: "void">
 | <VARIABLE_TYPE: "int">
 | <LPAREN: "(">
 | <RPAREN: ")">
 | <LBRACE: "{">
 | <RBRACE: "}">
 | <COMMA: ",">
 | <SEMICOLON: ";">
 | <WHILE: "while">
 | <DO: "do">
 | <FOR: "for">
 }
 
 TOKEN: /* Expression Tokens */
 {
   <ADDOP: "+" | "-">
 | <MULOP: "*" | "/" | "%">
 | <ASSIGNOP: "=">
 | <NOT: "!">
 | <AND: "&&">
 | <OR: "||">
 | <RELOP: "!=" | "==">
 | <LTGT: ">" | "<" | ">=" | "<=">
 }
 
 TOKEN: /* Generic Name & Number */
 {
   <NUMBER: (["0"-"9"])+>
 | <NAME: ["a"-"z","A"-"Z"] (["a"-"z","A"-"Z","0"-"9","_"])*>
 }
 
 SimpleNode program() :
 {}
 {
   method_declaration() <EOF> { return jjtThis; }
 }
 
 void method_declaration() :
 {
 	Token tok1, tok2;
 } {
   (tok1=<TYPE>|tok1=<VARIABLE_TYPE>) tok2=<NAME> <LPAREN> <RPAREN>
 	    <LBRACE> statement_block() <RBRACE>
 	    {
 		jjtThis.ovalue = tok1.image;
 		jjtThis.value = tok2.image;
 	    }
 }
 
 void statement_block() #void :
 {}
 {
   ( statement() )*
 }
 
 void statement() #void :
 {}
 {
   simplestatement() <SEMICOLON>
 | compoundstatement()
 | <LBRACE> statement_block() <RBRACE>
 }
 
 void simplestatement() #void :
 {}
 {
   declarativestatement() | assignmentstatement()
 }
 
 void declarativestatement() :
 {
 	Token tok1;
 } {
   tok1=<VARIABLE_TYPE> assignmentstatement() (<COMMA> assignmentstatement())*
   {
 	jjtThis.value = tok1.image;
   }
 }
 
 void assignmentstatement() :
 {
 	Token temp;
 } {
   temp=<NAME> [<ASSIGNOP> expression()]
   {
 	jjtThis.value = temp.image;
   }
 }
Important notes: