ITEC 460 - Chapter 6 Notes - Tree Implementation and Visitors

Tree implementation

• What kinds of expressions can we have???


• abstract class ASTExpression{ }


• Implementing classes:
• class ASTIntegerLiteral extends ASTExpression{...}
• class ASTOperatorExpression extends ASTExpression{...}


• Constants: ASTOperatorExpression.PLUS etc

Creating Expressions

• Example page 125:

            ASTExpression tree1;
            tree1 = new
                ASTOperatorExpression
                (
                    new ASTIntegerLiteral(3),    // Left
                    new ASTOperatorExpression    // Right
                    (
                        new ASTIntegerLiteral(4),
                        new ASTIntegerLiteral(5),
                        ASTOperatorExpression.MULTIPLY
                    ),
                    ASTOperatorExpression.PLUS   // Operator
                );
            

• Example 2: 3*8 + 4/2


• Class Implementation: Figures 6.12 and 6.13

Using the Getters

            int value;
            value = (
                        (ASTIntegerLiteral)
                            (
                                (ASTOperatorExpression)
                                    (
                                        (ASTOperatorExpression) tree1
                                    ).left()
                            ).right()
                    ).value();
            

Constrast Notations

// Java notation 2:
                (ASTIntegerLiteral) ( (ASTOperatorExpression) ( (ASTOperatorExpression) tree1).left()).right()).value();

-- Ada notation 1:
                        ASTIntegerLiteral(
                            ASTOperatorExpression( 
                                ASTOperatorExpression(tree1
                                ).left
                            ).right
                        ).value;

-- Ada notation 2:
                        ASTIntegerLiteral
                        (
                            ASTOperatorExpression
                            ( 
                                ASTOperatorExpression(tree1).left
                            ).right
                        ).value;

-- Ada notation 3:
                        ASTIntegerLiteral(ASTOperatorExpression(ASTOperatorExpression(tree1).left).right).value;
            

Traversing the Tree: Vistors

• Visitor Pattern
• Each visit method has a parameter whose type matches that node
• Each visit method calls accept on the fields of the node
• Each accept calls the corresponding visit
• Why doesn't visit simply call visit?


• Abstract means of traversing and/or evaluating the tree


• Each type of node contains a hook allowing a Visitor to visit


• Create Vistor objects to accomplish various tasks


• Vistors can accomplish various tasks without modifying underlying tree representation


• Example: Traverse tree for type checking
• Example: Traverse tree for for code generation


• First, Simple Example: Evaluate expression tree

Evaluating an Expression Tree, without a Visitor

            int calculateValue(ASTExpression exp)
            {
                if (exp instanceof(ASTIntegerLiteral))
                    return ((ASTIntegerLiteral) exp).value();
                else if (exp instanceof ASTOperatorExpression)
                    return calculateOperator((ASTOperatorExpression) exp);
                else 
                    ; // Handle other possible expression types
            }
            

• Someone once said: Any if statement in a procedure is a candidate for polymorphism


• Visitor replaces the if and the casting

Using the Vistor Pattern

• Each node that is to be visited must implement
• public Object accept(ASTVisitor v)

Using the Vistor Pattern in Class ASTExpression

• Class ASTExpression becomes (it was empty):

            abstract class ASTExpression
            {
                public abstract Object accept(ASTVisitor v);
            }
            

Examples Implementing accept

• Class ASTIntegerLiteral must implement accept:

            class ASTIntegerLiteral
            {
                ...

                public Object accept(ASTVisitor v)
                {
                    return v.visitIntegerLiteral(this);
                }
            }

            class ASTOperatorExpression
            {
                ...

                public Object accept(ASTVisitor v)
                {
                    return v.visitOperatorExpression(this);
                }
            }
            

• See the complete definitions pages 128 and 130

Defining the Visitors

• The visitors specify what happens when accept(Visitor v) calls v


• A visitor for ASTIntegerLiteral nodes

            public Object visitIntegerLiteral(ASTIntegerLiteral literal)
            {
                return new Integer(literal.value());
            }
            

• Contrast the formal and actual parameters for the visitIntegerLiteral(...)


• A visitor for ASTExpression nodes - See page 129


• Complete implementation: pages 130 and 131

A Tree Printer Visitor

• Pages 132-134

Implementing with JavaCC - JavaCC Actions

• The parser can define a (static) main program


• Rules can have actions that are executed when the rule is matched
• Example (parens.jj): page 135 with input (())


• Rules can return value
• Example (parens2).jj: page 136 with input ((()))


• Action executed after rule is matched

JavaCC Actions and Return Values - A Calculator

• Define rules for return the value of each expression seen


• Example (calc.jj) pages 139 and 140


• The implied grammar is expressed in EBNF
• Example: Expr → Term ( (+|-) Term )*


• No rules go to empty strings

JavaCC Actions and Parameters - Another Calculator

• Now define the grammar with rules that go to empty strings


• Example (calc2.jj) pages 142 and 143


• Example:

                Expr → Term ExprPrime 

                ExprPrime → <PLUS> Term ExprPrime 
                          | <MINUS> Term ExprPrime
                          | 
                

• Problem: ExprPrime needs the result of the preceding Term


• Solution: Pass parameters to rules!
• Example (calc3.jj) pages 144 and 145

JavaCC Actions for Building an AST

• Finally ...


• Use EBNF expression grammar (based on calc.jj)


• Add actions to create and return tree nodes


• Example (expression.jj) pages 148 and 149

Project

• See Constructors, etc pages 150 - 154
• See provided code files (from Galles web site):
• AST*.java


• ASTVisitor.java [prettified]


• TestParser.java (Fig 6.38, called abstractSyntaxTest.java in book) [prettified]


• ASTPrintTree.java (called ASTPrint.java in book) [prettified]

Topic

Topic

Topic