teaching machines

CS 330 Lecture 10 – Basecalc Interpreter

February 16, 2015 by Chris Johnson. Filed under cs330, lectures, spring 2015.

Agenda

• what ?s
• whitespace
• expr productions
• parse trees
• a REPL
• an interpreter

TODO

• Read up on the origin of a programming language of your choosing, and share some interesting factoids on a 1/4 sheet.

Review

• Name one reason why early Fortran compilers were so good.
• Why is it harder to debug C code than, say, JavaScript or Python?
• Name some language rule that can be checked statically. Dynamically?

Process of Interpretation

1. Write your grammar in a *.g file.
2. Run antlr on *.g file to produce the Java source for your lexer and parser.
3. Compile all your Java code.
4. Test the parsing with grun GrammarName startingRule -(gui|tree) < input.txt.
5. Write a parse tree walk listener. Label productions as necessary to generate specific events.
6. In your callbacks, generate an abstract syntax tree or directly execute the interpreted code.

Code

Basecalc.g

grammar Basecalc;

line
  : expr 
  | expr CAST DIGITS
  ;

expr
  : LEFT_PARENTHESIS expr RIGHT_PARENTHESIS # Grouped
  | NOT expr # Negate
  | expr POWER expr # Power
  | expr MULTIPLICATIVE_OPERATOR expr # Multiply
  | expr ADDITIVE_OPERATOR expr # Add
  | expr SHIFT expr # Shift
  | expr AND expr # And
  | expr XOR expr # Xor
  | expr OR expr # Or
  | IDENTIFIER ASSIGNMENT expr # Assignment
  | DIGITS # Digits
  | DIGITS LESS DIGITS GREATER # DigitsWithBase
  | IDENTIFIER # Identifier
  ;

LEFT_PARENTHESIS: '(';
RIGHT_PARENTHESIS: ')';
POWER: '^^';
MULTIPLICATIVE_OPERATOR: [*/%];
ADDITIVE_OPERATOR: [-+];
NOT: '~';
SHIFT: '<<' | '>>';
AND: '&';
XOR: '^';
OR: '|';
ASSIGNMENT: ':=';
CAST: '->';
LESS: '<';
GREATER: '>';
IDENTIFIER: '$' [a-z]+ [a-z_]*;
DIGITS: [0-9a-zA-Z]+;

WHITESPACE: [ \n\r\t]+ -> skip;

Repl.java

import org.antlr.v4.runtime.ANTLRInputStream;
import org.antlr.v4.runtime.tree.ParseTreeWalker;
import org.antlr.v4.runtime.tree.ParseTree;
import org.antlr.v4.runtime.CommonTokenStream;
import java.util.Scanner;

public class Repl {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    System.out.print("> ");
    while (in.hasNextLine()) {
      String line = in.nextLine();

      ANTLRInputStream ais = new ANTLRInputStream(line);
      BasecalcLexer lexer = new BasecalcLexer(ais);
      CommonTokenStream tokens = new CommonTokenStream(lexer);
      BasecalcParser parser = new BasecalcParser(tokens);
      ParseTree tree = parser.line();

      System.out.println(parser.getNumberOfSyntaxErrors());

      ParseTreeWalker walker = new ParseTreeWalker();
      Interpreter interpreter = new Interpreter();
      walker.walk(interpreter, tree);
      
      System.out.print("> ");
    }
  }
}

Interpreter.java

public class Interpreter extends BasecalcBaseListener {
  @Override
  public void exitDigits(BasecalcParser.DigitsContext ctx) {
    String digitsAsString = ctx.DIGITS().getText(); 
    int digits = Integer.parseInt(digitsAsString);
    System.out.println(digits);
  }
}

Haiku