CSC448: Abstract Syntax Trees [2011/01/05]

CSC448: Further examples: Abstract Syntax Trees [22/22]

Abstract syntax trees (ASTs) are distinct from parse trees.

Pretty printer for Arithmetic.

Building the AST during parsing with CUP.

file:arithmetic.flex [source]

00001: import java_cup.runtime.SymbolFactory;
00002: 
00003: %%
00004: 
00005: %class ArithmeticLexer
00006: %public
00007: %{
00008:    private SymbolFactory sf;
00009:    public ArithmeticLexer (java.io.InputStream r, SymbolFactory sf)
00010:    {
00011:      this (r);
00012:      this.sf = sf;
00013:    }
00014: %}
00015: %eofval{
00016:   return sf.newSymbol ("EOF", sym.EOF);
00017: %eofval}
00018: 
00019: %unicode
00020: 
00021: %cup
00022: %cupdebug
00023: 
00024: %char
00025: %column
00026: %line
00027: 
00028: 
00029: ALPHA=[A-Za-z_]
00030: DIGIT=[0-9]
00031: NONNEWLINE_WHITE_SPACE_CHAR=[\ \t\b\012]
00032: NEWLINE=\r|\n|\r\n
00033: IDENT={ALPHA}({ALPHA}|{DIGIT}|_)*
00034: 
00035: %% 
00036: 
00037: <YYINITIAL> {
00038:   "(" { return sf.newSymbol ("LeftParen", sym.LPAREN); }
00039:   ")" { return sf.newSymbol ("RightParen", sym.RPAREN); }
00040:   ";" { return sf.newSymbol ("Semicolon", sym.SEMI); }
00041:   "=" { return sf.newSymbol ("Equals", sym.EQUALS); }
00042:   "+" { return sf.newSymbol ("Plus", sym.PLUS); }
00043:   "-" { return sf.newSymbol ("Minus", sym.MINUS); }
00044:   "*" { return sf.newSymbol ("Times", sym.TIMES); }
00045:   "/" { return sf.newSymbol ("Divide", sym.DIVIDE); }
00046: 
00047:   {NONNEWLINE_WHITE_SPACE_CHAR}+ { }
00048: 
00049:   {IDENT}
00050:     { return sf.newSymbol ("Identifier", sym.IDENTIFIER, yytext ()); }
00051: 
00052:   {DIGIT}+
00053:     {
00054:       int i = Integer.parseInt (yytext ());
00055:       return sf.newSymbol ("IntegerConstant", sym.INTEGER_CONSTANT, new Integer (i));
00056:     }
00057: }
00058: 
00059: {NEWLINE} { }
00060: 
00061: . {
00062:   System.out.println ("Illegal character: <" + yytext () + ">");
00063: }
00064: 
00065:

file:arithmetic.cup [source]

00001: import java_cup.runtime.*;
00002: 
00003: import java.util.ArrayList;
00004: import java.util.List;
00005: 
00006: 
00007: terminal           LPAREN, RPAREN;
00008: terminal           SEMI, EQUALS;
00009: terminal           PLUS, MINUS, TIMES, DIVIDE;
00010: 
00011: terminal String    IDENTIFIER; 
00012: terminal Integer   INTEGER_CONSTANT;
00013: 
00014: non terminal List<Decl>     decl_list;
00015: non terminal Decl           decl;
00016: non terminal Exp            expression;
00017: 
00018: precedence left PLUS, MINUS;
00019: precedence left TIMES, DIVIDE; 
00020: 
00021: 
00022: decl_list ::= decl_list:l decl:d
00023:               {: l.add (d); RESULT = l; :}
00024:               |
00025:               {: RESULT = new ArrayList<Decl> (); :}
00026:               ;
00027: 
00028: decl ::= IDENTIFIER:id EQUALS expression:e SEMI
00029:          {: RESULT = new Decl (id, e); :}
00030:          ;
00031: 
00032: expression ::= INTEGER_CONSTANT:i
00033:                {: RESULT = new ExpInt (i.intValue ()); :}
00034:                | IDENTIFIER:id 
00035:                {: RESULT = new ExpVar (id); :}
00036:                | expression:e1 PLUS expression:e2
00037:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.PLUS, e1, e2); :}
00038:                | expression:e1 MINUS expression:e2
00039:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.MINUS, e1, e2); :}
00040:                | expression:e1 TIMES expression:e2
00041:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.TIMES, e1, e2); :}
00042:                | expression:e1 DIVIDE expression:e2
00043:                {: RESULT = new ExpBinOp (ExpBinOp.BinOp.DIVIDE, e1, e2); :}
00044:                | LPAREN expression:e RPAREN
00045:                {: RESULT = e; :}
00046:                ;
00047: 
00048:

file:Main.java [source] [doc-public] [doc-private]

00001: import java.io.FileInputStream;
00002: import java.util.List;
00003: import java.util.Map;
00004: 
00005: import java_cup.runtime.*;
00006: 
00007: 
00008: public class Main
00009: {
00010:   public static void main (String[] args) 
00011:     throws Exception
00012:   {
00013:     SymbolFactory sf = new ComplexSymbolFactory ();
00014:     ArithmeticLexer lexer;
00015:     if (args.length == 0) {
00016:       lexer = new ArithmeticLexer (System.in, sf);
00017:     } else {
00018:       lexer = new ArithmeticLexer (new java.io.FileInputStream (args[0]), sf);
00019:     }
00020:     ArithmeticParser parser = new ArithmeticParser (lexer, sf);
00021: 
00022:     Symbol symbol = parser.parse ();
00023: 
00024:     List<Decl> decls = (List<Decl>) symbol.value;
00025:     for (Decl decl : decls) {
00026:       System.out.println (decl);
00027:     }
00028: 
00029:     System.out.println ();
00030: 
00031:     Interpreter interpreter = new Interpreter ();
00032:     Map<String, Integer> bindings = interpreter.evaluateDecls (decls);
00033:     for (String var : bindings.keySet ()) {
00034:       System.out.println (var + " = " + bindings.get (var));
00035:     }
00036:   }
00037: }
00038: 
00039:

file:Decl.java [source] [doc-public] [doc-private]

00001: public class Decl
00002: {
00003:   public final String var;
00004:   public final Exp exp;
00005: 
00006: 
00007:   public Decl (String var, Exp exp)
00008:   {
00009:     this.var = var;
00010:     this.exp = exp;
00011:   }
00012: 
00013: 
00014:   public String toString ()
00015:   {
00016:     return var + " = " + exp + ";";
00017:   }
00018: }
00019:

file:Exp.java [source] [doc-public] [doc-private]
00001: public abstract class Exp
00002: {
00003: }
00004: 

file:ExpBinOp.java [source] [doc-public] [doc-private]

00001: public class ExpBinOp extends Exp
00002: {
00003:   public enum BinOp { 
00004:     PLUS ("+"),
00005:     MINUS ("-"),
00006:     TIMES ("*"),
00007:     DIVIDE ("/"),
00008:     ;
00009: 
00010:     final String string;
00011: 
00012:     BinOp (String string) 
00013:     {
00014:       this.string = string;
00015:     }
00016: 
00017:     public String toString ()
00018:     {
00019:       return string;
00020:     }
00021:   };
00022: 
00023: 
00024:   public final BinOp op;
00025:   public final Exp left;
00026:   public final Exp right;
00027: 
00028: 
00029:   ExpBinOp (BinOp op, Exp left, Exp right)
00030:   {
00031:     this.op = op;
00032:     this.left = left;
00033:     this.right = right;
00034:   }
00035: 
00036: 
00037:   public String toString ()
00038:   {
00039:     return "(" + left + " " + op + " " + right + ")";
00040:   }
00041: }
00042:

file:ExpInt.java [source] [doc-public] [doc-private]

00001: public class ExpInt extends Exp
00002: {
00003:   public final int value;
00004: 
00005: 
00006:   public ExpInt (int value)
00007:   {
00008:     this.value = value;
00009:   }
00010: 
00011: 
00012:   public String toString ()
00013:   {
00014:     return Integer.toString (value);
00015:   }
00016: }
00017:

file:ExpVar.java [source] [doc-public] [doc-private]

00001: public class ExpVar extends Exp
00002: {
00003:   public final String var;
00004: 
00005: 
00006:   public ExpVar (String var)
00007:   {
00008:     this.var = var;
00009:   }
00010: 
00011: 
00012:   public String toString ()
00013:   {
00014:     return var;
00015:   }
00016: }
00017:

file:Interpreter.java [source] [doc-public] [doc-private]

00001: import java.util.List;
00002: import java.util.HashMap;
00003: import java.util.Map;
00004: 
00005: 
00006: public class Interpreter
00007: {
00008:   public Map<String, Integer> evaluateDecls (List<Decl> decls)
00009:   {
00010:     Map<String, Integer> bindings = new HashMap<String, Integer> ();
00011:     
00012:     for (Decl decl : decls) {
00013:       int value = evaluateExp (bindings, decl.exp);
00014:       bindings.put (decl.var, new Integer (value));
00015:     }
00016:     
00017:     return bindings;
00018:   }
00019: 
00020: 
00021:   int evaluateExp (Map<String, Integer> bindings, Exp exp) 
00022:   {
00023:     if (exp instanceof ExpInt) {
00024:       ExpInt expI = (ExpInt) exp;
00025:       return expI.value;
00026: 
00027:     } else if (exp instanceof ExpVar) {
00028:       ExpVar expV = (ExpVar) exp;
00029:       Integer value = bindings.get (expV.var);
00030:       if (value == null) {
00031:         throw new RuntimeException ("Variable " + expV.var + " not defined");
00032:       } else {
00033:         return value.intValue ();
00034:       }
00035: 
00036:     } else if (exp instanceof ExpBinOp) {
00037:       ExpBinOp expB = (ExpBinOp) exp;
00038:       int left = evaluateExp (bindings, expB.left);
00039:       int right = evaluateExp (bindings, expB.right);
00040:       if (expB.op.equals (ExpBinOp.BinOp.PLUS)) {
00041:         return left+right;
00042:       } else if (expB.op.equals (ExpBinOp.BinOp.MINUS)) {
00043:         return left-right;
00044:       } else if (expB.op.equals (ExpBinOp.BinOp.TIMES)) {
00045:         return left*right;
00046:       } else if (expB.op.equals (ExpBinOp.BinOp.DIVIDE)) {
00047:         return left/right;
00048:       } else {
00049:         throw new RuntimeException ("Missing case for BinOp " + expB.op);
00050:       }
00051: 
00052:     } else {
00053:       throw new RuntimeException ("Missing case for Exp " + exp);
00054:     }
00055:   }
00056: }
00057: