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: