teaching machines

CS 330 Lecture 10 – Translating to an AST

February 13, 2012 by Chris Johnson. Filed under cs330, lectures, spring 2012.

Agenda

• adding functions to Flop
• storing parse results in an AST
• quiz

Code

Flop.g

grammar Flop;

@header {
import java.util.HashMap;
}

@members {
  HashMap<String, Integer> memory;
  HashMap<String, Expression> functions;

  public abstract class Expression {
    public abstract int evaluate();
  }

  public class Literal extends Expression {
    private int value;

    public Literal(int value) {
      this.value = value;
    }

    public int evaluate() {
      return value;
    }
  }

  public class Variable extends Expression {
    private String name;

    public Variable(String name) {
      this.name = name;
    }

    public int evaluate() {
      return memory.get(name);
    }
  }

  public class Call extends Expression {
    private String name;

    public Call(String name) {
      this.name = name;
    }

    public int evaluate() {
      return functions.get(name).evaluate();
    }
  }

  public class Add extends Expression {
    private Expression left;
    private Expression right;

    public Add(Expression left, Expression right) {
      this.left = left;
      this.right = right;
    }

    public int evaluate() {
      return left.evaluate() + right.evaluate();
    }
  }

  public class Multiply extends Expression {
    private Expression left;
    private Expression right;

    public Multiply(Expression left, Expression right) {
      this.left = left;
      this.right = right;
    }

    public int evaluate() {
      return left.evaluate() * right.evaluate();
    }
  }

  public void setMemory(HashMap<String, Expression> functions,
                        HashMap<String, Integer> memory) {
    this.functions = functions;
    this.memory = memory;
  }
}

stat
  : ID EQUALS expr {memory.put($ID.text, $expr.root.evaluate());}
  | ID LEFTPAREN RIGHTPAREN EQUALS expr {functions.put($ID.text, $expr.root);}
  | expr {System.out.println($expr.root.evaluate());}
  ;

expr returns [Expression root]
  : e1=precedence10
    {$root = $e1.root;}
    (PLUS e2=precedence10 {$root = new Add($root, $e2.root);})*
  ;

precedence10 returns [Expression root]
  : e1=precedence20
    {$root = $e1.root;}
    (TIMES e2=precedence20 {$root = new Multiply($root, $e2.root);})*
  ;

precedence20 returns [Expression root]
  : NUMBER {$root = new Literal(Integer.parseInt($NUMBER.text));}
  | ID {$root = new Variable($ID.text);}
  | ID LEFTPAREN RIGHTPAREN {$root = new Call($ID.text);}
  | LEFTPAREN expr RIGHTPAREN {$root = $expr.root;}
  ;

LEFTPAREN
  : '('
  ;

RIGHTPAREN
  : ')'
  ;

ID
  : '$' ('A'..'Z'|'a'..'z') ('A'..'Z'|'a'..'z'|'0'..'9')*
  ;

EQUALS
  : '='
  ;

PLUS
  : '+'
  ;

TIMES
  : '*'
  ;

NUMBER
  : '-'? '0'..'9'+
  ;

WHITESPACE
  : (' '|'\t'|'\r'|'\n')+ {skip();}
  ;

FlopInterpreter.java

import java.io.IOException;
import org.antlr.runtime.*;
import java.util.Scanner;
import java.util.HashMap;

public class FlopInterpreter {
  public static void main(String[] args) throws IOException, RecognitionException {

    Scanner lineReader = new Scanner(System.in);
    HashMap<String, Integer> memory = new HashMap<String, Integer>();
    HashMap<String, FlopParser.Expression> functions = new HashMap<String, FlopParser.Expression>();

    System.out.print("> ");
    while (lineReader.hasNextLine()) {
      ANTLRStringStream in = new ANTLRStringStream(lineReader.nextLine());
      FlopLexer lexer = new FlopLexer(in);
      CommonTokenStream tokens = new CommonTokenStream(lexer);
      FlopParser parser = new FlopParser(tokens);
      parser.setMemory(functions, memory);
      parser.stat();
      System.out.print("> ");
    }
  }
}

Haiku