» CS 330 Lecture 10 – Interpreting a Parse Tree

CS 330 Lecture 10 – Interpreting a Parse Tree

February 15, 2016 by Chris Johnson. Filed under cs330, lectures, spring 2016.

Agenda

what ?s
retcon: matching numeric ranges with regex
evaluate this
tree walking
eager vs. lazy
toward Logo

Note

We left off last time being able to lex and parse boolean expressions. Today we evaluate them by walking the parse tree. First off, let’s try doing this manually. Evaluate this tree:

We’ll automate this evaluation by creating our own tree walker in ANTLR and registering callbacks for the various expressions we might encounter.

Code

Boo.g

grammar Boo;

expression
  : LITERAL # Literal
  | LEFT_PARENTHESIS expression RIGHT_PARENTHESIS # Parenthesized
  | IDENTIFIER # Identifier
  | NOT expression # Not
  | expression XOR expression # Xor
  | expression AND expression # And
  | expression OR expression # Or
  ;

fragment TRUE: 'true';
fragment FALSE: 'false';
LITERAL: TRUE | FALSE;

LEFT_PARENTHESIS: '(';
RIGHT_PARENTHESIS: ')';

AND: '&&';
OR: '||';
NOT: '!';
XOR: '^';

IDENTIFIER: [a-zA-Z]+;

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

Interpreter.java

/usr/lib/ruby/2.7.0/rubygems/dependency.rb:311:in `to_specs': Could not find 'coderay' (>= 0) among 56 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/.gem/ruby/2.7.0:/var/lib/gems/2.7.0:/usr/lib/ruby/gems/2.7.0:/usr/share/rubygems-integration/2.7.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/2.7.0:/home/johnch/.gems', execute `gem env` for more information
	from /usr/lib/ruby/2.7.0/rubygems/dependency.rb:323:in `to_spec'
	from /usr/lib/ruby/2.7.0/rubygems/core_ext/kernel_gem.rb:62:in `gem'
	from ./coderay:24:in `'

makefile

Note to copy and pasters: makefile rules need to be indented with real tabs, not spaces.

ANTLR_JAR = antlr-4.5.2-complete.jar

Interpreter.class: BooLexer.java BooParser.java Interpreter.java

BooLexer.java BooParser.java: Boo.g
  java -cp ${ANTLR_JAR} org.antlr.v4.Tool Boo.g

%.class: %.java
  javac -cp ${ANTLR_JAR}:. $<

clean:
  rm -rf *.class BooLexer.java BooParser.java BooBaseListener.java BooListener.java *.tokens