Project Part 4

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") 
    )

addop_expression -> mulop_expression { addop mulop_expression }

then we can add attributes and functions such as:

addop_expression -> mulop_expression { addop mulop_expression }
addop_expression.NodePtr = GetNode
addop_expression.Info = "+"
addop_expression.Left = mulop_expression₁.NodePtr
addop_expression.Right = mulop_expression₂.NodePtr

This might be printed out:

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

or, indenting,

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

This might be printed out:

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

or with indenting

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

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) ]
	                     

You will use the JJTree tool to build your ast's. Below is an excerpt from Theo's 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:

1) by default, all productions become a node of the same name.  the name can
be changed by putting "#name" after the production decalaration (but before
the colon)  "#void" will make sure that the node isn't created.

2) the file now needs to be called 'tea.jjt', not 'tea.jj'.  (JJTree is a
preprocessor to convert JJT->JJ)