I. Abstract Syntax Trees (ASTs) in JastAdd A. importance of ASTs ------------------------------------------ IMPORTANCE OF ASTS ASTs are: the key interface between parser and rest of compiler (or static analysis) ------------------------------------------ B. overview in JastAdd ------------------------------------------ ABSTRACT SYNTAX TREES IN JASTADD ASTs are described in .ast files (e.g., WHILE.ast) JastAdd tool converts to java classes (e.g., AST/IfS.java, AST/BExpr.java) At runtime, each AST is a Java object. (constructed by the parser) ------------------------------------------ C. WHILE.ast file ------------------------------------------ // WHILE.ast file Program ::= S; abstract Op ::= ; Op_b : Op; Op_r : Op; Op_a : Op; abstract Expr; abstract AExpr: Expr; VarRefExpr: AExpr ::= ; NumLitExpr: AExpr ::= ; ABinaryExpr: AExpr ::= Left:AExpr Op:Op_a Right:AExpr; abstract BExpr: Expr; BoolLitExpr:BExpr ::= ; NotExpr: BExpr ::= BExpr; LogicExpr: BExpr ::= Left:BExpr Op:Op_b Right:BExpr; RelExpr: BExpr ::= Left:AExpr Op:Op_r Right:AExpr; // statements abstract S; CompoundS: S ::= SList:S* ; AssignS:S ::= AExpr; SkipS:S ::= ; IfS:S ::= LabeledBExpr S1:S S2:S ; WhileS:S ::= LabeledBExpr S; LabeledBExpr: BExpr ::= BExpr; abstract Label; NumLabel:Label ::= ; abstract Block; StmtBlock: Block ::= S; TestBlock: Block ::= LabeledBExpr; ------------------------------------------ What's the syntax? What does "abstract" mean? 1. picture of runtime AST ------------------------------------------ PARSED AST EXAMPLE Parsing the program if x < 5 then y := 2 else skip gives the AST: [Program | S: * ] | v [IfS | LabeledBExpr: * | S1: * | S2: *] / | \ v v v [LabeledBExpr | [AssignS | [SkipS | LabelAST: * LabelAST: * LabelAST: * ] BExpr: * ]| Var: * \ / | AExpr: * ] \ v v [NumLabel | LabelAST: *] [NumLabel | [NumLabel | Num: * ] / Num: * ] | v | v [String | "1"] v [String | "3"] [String | "2"] [RelExpr | Left: *-----\ | Op_r: *-----|----->[Op_r | Contents: * ] | Right: * ] | | / v v [String | "<" ] [VarRefExpr | Contents * ] | v [String | "x" ] [NumLitExpr | Contents: * ] | v [String | "5"] ------------------------------------------ II. Attributes A. What are attributes? ------------------------------------------ ATTRIBUTES defn: an *attribute* is Two kinds of attributes: Synthesized: (passed up) AST's value computed from attributes of subtrees Inherited: (passed down) AST's value given to it from its parent in the AST ------------------------------------------ B. Examples of Synthesized Attributes ------------------------------------------ SYNTHESIZED ATTRIBUTE EXAMPLE aspect Unparse { syn String Program.unparse(); syn String S.unparse(); syn String Expr.unparse(); syn String Op.unparse(); syn String Label.unparse(); eq Program.unparse() = getS().unparse(); eq CompoundS.unparse() { StringBuffer s = new StringBuffer(); s.append("{\n"); int len = getNumSList(); for (int i = 0; i < len; i++) { s.append(getSList(i).unparse()); if (i < len-1) { s.append(";\n"); } } s.append("\n}"); return s.toString(); } eq VarRefExpr.unparse() { return getContents();} eq NumLitExpr.unparse() { return getContents();} eq BoolLitExpr.unparse() { return getContents();} eq ABinaryExpr.unparse() { return "(" + getLeft().unparse() + " " + getOp().getContents() + " " + getRight().unparse() + ")";} // ... similarly, see Unparse.jrag } ------------------------------------------ C. inherited attribute example Suppose we want to have indentation for prettyprinting? ------------------------------------------ import utility.PPUtility; aspect PrettyPrint { inh int S.nestingLevel(); eq Program.getS().nestingLevel() = 0; eq CompoundS.getSList(int index).nestingLevel() = nestingLevel()+1; eq IfS.getS1().nestingLevel() = nestingLevel(); eq IfS.getS2().nestingLevel() = nestingLevel(); eq WhileS.getS().nestingLevel() = nestingLevel(); eq StmtBlock.getS().nestingLevel() = 0; // just for sake of form // ... syn String Program.prettyPrint(); syn String S.prettyPrint(); syn String Expr.prettyPrint(); syn String Op.prettyPrint(); syn String Label.prettyPrint(); // ... eqs use nestingLevel()... } ------------------------------------------ Why does nestingLevel need to be inherited? III. Data Flow Graphs (2.1) A. use of (data) flow graphs ------------------------------------------ USE OF (DATA) FLOW GRAPHS DFGs are used to: summarize control flow in a program, direct information in a dataflow analysis ------------------------------------------ B. overview in JastAdd ------------------------------------------ DFGs IN JASTADD Not a built-in feature of JastAdd I implemented in: a Java class: FlowGraph a DFG.jrag file ------------------------------------------ C. DFG.jarg file ------------------------------------------ import java.util.*; import utility.SetRepUtility; import utility.FlowGraph; aspect DFG { syn Label S.init(); // ... syn Set