Java程序辅导

• Reading for Feb 10
– Finish Chapter 4 
• section 4.6 – Syntactic Analysis in Triangle  (pp 124 – 128)
• Materials on our website
– simpleAST
• illustrates AST construction and evaluation for miniArith
– AbstractSyntaxTrees.zip  
• miniJava.AbstractSyntaxTrees package needed to construct AST’s 
for miniJava in PA2
COMP 520  - Compilers
Lecture 8  (Tue Feb 8, 2022)
Abstract Syntax Trees
COMP 520:  Compilers  - Prins 08 - Abstract Syntax Trees
308 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
Topics
• From concrete syntax trees to abstract syntax trees
– AST “grammar”
– AST representation choices
– AST construction
• AST traversal
– generalize using Visitor
• miniJava AST classes (available on web)
– use these to construct the AST in PA2
– you will need to provide some implementation of sourcePosition
4• Concrete syntax is described by an (EBNF) CFG grammar 
– ex:  simple arithmetic expressions
S ::=  E $  
E ::=  E  Op T  |  T
T ::=  ( E )  | Num
• Concrete syntax tree for 
2 + (3 * 4) $
Concrete syntax tree
COMP 520:  Compilers  - Prins 08 - Abstract Syntax Trees
S ::=  E $
E ::=  T  ( Op T )*
T ::=  ( E ) | Num E
TOp  +
$
Num 2
Num 4Num 3
( E )
T
T Op * T
S
5Abstract syntax 
• Abstract syntax can be described by a simple CFG grammar
– ex:  simple arithmetic expressions
Expr ::=  Expr Op  Expr (BinExpr)
| Num (NumExpr)
• Abstract syntax tree for 2 + (3 * 4)
Expr
Expr ExprOp
+
Expr ExprOp
*
Num
2
Num
4
Num
3
COMP 520:  Compilers  - Prins 08 - Abstract Syntax Trees
6AST representation in Java (Strategy 1)
• AST classes define an (n-ary) tree with tagged nodes
• simple to define, more complex to construct and traverse
• minimal benefit from Java type checker
enum NodeType {UNARYEXPR, BINARYEXPR, NUM}
public abstract class AST {
public NodeType n;
}
public class Node extends AST {
public AST[] children;
public Node(NodeType n, AST[] children) { … }
}
public class Leaf extends AST {
public String spelling;
public Leaf(NodeType n, String spelling) { … }
}
COMP 520:  Compilers  - Prins 08 - Abstract Syntax Trees
7AST representation in Java (Strategy 2)
• AST classes closely follow structure of AST grammar
• more complex to define AST classes, but simpler to construct AST
• we gain considerable benefit from the Java type checker
• more rigorously supports AST traversal using a Visitor interface
• Rules
– create abstract class AST
– for each nonterminal in AST grammar
• construct an abstract subclass of AST
– for each choice within a rule
• construct a concrete subclass of the LHS nonterminal
• We will follow this strategy
COMP 520:  Compilers  - Prins 08 - Abstract Syntax Trees
8AST representation in Java (Strategy 2)
• Example
Expr ::= Expr Oper Expr (BinExpr)
| Num (NumExpr)
abstract public class AST {}
abstract public class Expr extends AST {}
public class BinExpr extends Expr {
public Terminal oper;
public Expr left, right;
public BinExpr(Expr left, Terminal oper, Expr right) { … }
}
public class NumExpr extends Expr {
public Terminal num;
public NumExpr(Terminal num) { … }
}
public class Terminal extends AST {
public String spelling;
public Terminal(String spelling) { … };
}
COMP 520:  Compilers  - Prins 08 - Abstract Syntax Trees
10
Building an AST during a concrete syntax parse
• concrete syntax for arithmetic 
expression grammar
E ::=  T  | E  op T
T ::=  ( E ) | num
• transformed and augmented
S ::=  E $
E ::=  T ( op T)*
T ::=  ( E ) | num
• abstract syntax
Expr ::=  Expr  Op Expr   (BinExpr)
| Num (NumExpr)
• how to build AST?
– modify parse procedures to return
pieces of AST
Expr parseS() { 
Expr e = parseE();
accept(Token.eot);
return e
}
Expr parseE() {
Expr e1 = parseT();
while (curToken.kind == Token.op) {
Terminal op = new Terminal(curToken);
acceptIt();
Expr e2 = parseT();
e1 = new BinExpr(e1,op,e2);
}
return e1; 
}
Expr parseT() {
case  (curToken.kind) { 
Token.LPAREN: 
acceptIt();
Expr e1 = parseE();
accept(Token.RPAREN);
return e1;
Token.num:
NumExpr e2 = new NumExpr(curToken);
acceptIt();
return e2;
}
}
COMP 520:  Compilers  - Prins 08 - Abstract Syntax Trees
11
mini-Triangle – Expression ASTs
Concrete 
Syntax
(EBNF)
Abstract
Syntax
(ASTs)
Tokens
COMP 520:  Compilers  - Prins 08 - Abstract Syntax Trees
12
mini-Triangle – Command ASTs
Concrete 
Syntax
ASTs
COMP 520:  Compilers  - Prins 08 - Abstract Syntax Trees
13
mini-Triangle – Declaration ASTs
Concrete 
Syntax
ASTs
COMP 520:  Compilers  - Prins 08 - Abstract Syntax Trees
14
The miniJava AST classes
08 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
AST
StatementExpressionReference Declaration
BaseRef QualRef NewExpr
ThisRef
IdRef
NewArrayExpr
NewObjectExpr
UnaryExpr
BinaryExpr
CallExpr
IxExpr
RefExpr
LiteralExpr
WhileStmt
IfStmt
BlockStmt
VarDeclStmt
AssignStmt
IxAssignStmt
CallStmt
ReturnStmt
ClassDecl
ParamDecl
VarDeclFieldDecl
MethodDecl
MemberDecl
Additional constructors for lists of class instances, with an iterator for traversal of the list: 
ClassDeclList, FieldDeclList, MethodDeclList, ParamDeclList, StatementList, ExprList
1508 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
1608 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
1708 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
Implementing a general AST traversal
• Strategy 1
– add methods to each AST class for each kind of traversal
• Example
– display methods for AST display
– eval methods for AST evaluation
– drawback
• Classes become very large when traversals get complex
– Contextual analysis
– Code generation
• Code for each kind of traversal  is scattered over many classes
1808 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
Implementing a general AST traversal
• Strategy 2
– use a visitor pattern
• A visitor Interface
– specifies a visitX method for each concrete class X in AST
• a visit method in each AST class
– public Object visit(Visitor v, Object arg)
– each separate traversal implements the Visitor interface
• sample Visitor instances
– AST display
– Identification
– Type checking
– Code generation
• Code for each type of visitor is collected in one class
– but a bit cumbersome to write out
1908 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
Simple set of AST classes 
abstract class AST {}
abstract class Expr extends AST {}
class BinExpr extends Expr {
public Token oper;
public Expr left;
public Expr right;
public BinExpr(Expr left, Token oper, Expr right) { . . . }
}
class NumExpr extends Expr {
public int val;
public NumExpr(int val) { . . . }
}
2008 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
The Visitor interface
• Visitor interface requires a visitX method for every (non-abstract) AST class X
• Each AST class is augmented with a single visit method
• All AST traversals use the same “visit” method in each node type
– the visit method “connects” a specific visitor v to this specific node
public interface Visitor {
visitBinaryExpr(BinaryExpr e);
visitNumExpr(NumExpr e);
}
class NumExpr extends Expr {
public int val;
public NumExpr(int v) { . . . }
public void visit(Visitor v) { v.visitNumExpr(this); }
}
2108 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
Inorder traversal of the AST
• The InorderWalk AST traversal implements the Visitor interface
public class InorderWalk implements Visitor {
public void visitBinExpr(BinExpr be) {
be.left.visit(this);
System.out.println(be.oper.spelling);
be.right.visit(this);
}
public void visitNumExpr(NumExpr ne) {
System.out.println(ne.val);
}
// print nodes of AST inorder
public void walk(AST a) {
a.visit(this);
}
}
2208 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
Adding arguments to the traversal (Book method)
• methods implemented by a Visitor have an Object arg and Object result
• AST class visit method has an Object arg and Object result
public interface Visitor {
Object visitBinExpr(BinExpr e, Object arg);
Object visitNumExr(NumExpr e, Object arg);
}
class NumExpr extends Expr {
public int val;
public NumExpr(int val) { . . . }
public Object visit(Visitor v, Object arg) {
return v.visitNumExpr(this, arg);
}
}
2308 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
Example use of the Visitor
• Individual traversals implement Visitor with custom logic for each node 
type 
• Good solution?
(+) appropriately OO
(+) compiler insures visitor defined for all node types 
(+) specific definitions gathered together in a single class
(-) Object parameters and results will require a lot of explicit casting
class Checker implements Visitor {
public Object visitAssignStmt(AssignStmt s, Object arg) {
Type t1 = (Type) s.ref.visit(this, arg);
Type t2 = (Type) s.exp.visit(this, arg);
return (t1.equals(t2)? t1 : Type.ERROR)
}
}
2408 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
Adding arguments to the traversal (parameterized types)
class NumExpr extends Expr {
public int val;
public NumExpr(int val) { . . . }
public  ResType
visit(Visitor v, ArgType arg) {
return v.visitNumExpr(this, arg);
}
}
public interface Visitor {
public ResultType visitBinExpr(BinExpr expr, ArgType arg);
public ResultType visitNumExpr(NumExpr expr, ArgType arg);
}
2508 - Abstract Syntax TreesCOMP 520:  Compilers  - Prins
Example use of the Visitor
• Individual traversals implement Visitor with custom logic for each node 
type 
• Good solution?
– Improves type checking in the visitors
– Improves readability 
class Checker implements Visitor {
...
public Type visitAssignStmt(AssignStmt s, Type arg) {
Type t1 = s.ref.visit(this, arg);
Type t2 = s.exp.visit(this, arg);
if (! t1.equals(t2)) 
typeError(“incompatible types in assignment”,s);
return Types.StmtType;
}