» CS 330 Lecture 11 – Abstract Syntax Trees

CS 330 Lecture 11 – Abstract Syntax Trees

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

Agenda

what ?s
math problem
a Logo grammar
translating to an AST

TODO

Watch Aiken’s lectures 24 and 25 on abstract syntax trees and recursive descent parsing. On a 1/4 sheet, summarize your results from searching for reasons why many languages use semi-colons as statement terminators and parentheses around actual parameter lists.

Note

We’re about to write a Logo clone. To warm us up, here’s a math problem for you:

A turtle is sitting at (5, 10) with a 60-degree heading, meaning the angle between its line of sight and the positive x axis is 60 degrees. It moves forward 3 units. Where is it now?

Walking paths and calculating locations are exactly the kind of thing that we want to teach a machine to do for us. The programmer thinks at a high-level, focusing on navigation, while the computer does the number crunching. We’ll need a programming language to serve as a bridge.

As we saw last time, it’s rare that we can immediately execute code as it gets parsed. Instead, we often need to store it in some form for later execution. Today we’ll write a grammar for our Logo clone and look at converting it to an abstract syntax tree.

We’ll follow this algorithm:

Write your grammar.
Define the model of your program parts (usually the nonterminals) in your host language.
Walk the parse tree, translating your source’s structures to the host language.
Store (if compiling) or evaluate (if interpreting) the resulting abstract syntax tree.

Code

makefile

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

ANTLR_JAR = ${HOME}/bin/antlr-4.5.2-complete.jar

Interpreter.class: LogoLexer.java LogoParser.java Interpreter.java

LogoLexer.java LogoParser.java: Logo.g
  java -cp ${ANTLR_JAR} org.antlr.v4.Tool Logo.g

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

run:
  java -cp ${ANTLR_JAR}:. Interpreter

clean:
  rm -rf *.class LogoLexer.java LogoParser.java LogoBaseListener.java LogoListener.java *.tokens

Logo.g

grammar Logo;

// Nonterminals
program
  : block EOF
  ;

block
  : (statement NEWLINE)*
  ;

statement
  : REPEAT expression NEWLINE block END # Repeat
  | PRINT expression # Print
  ;

expression
  : INTEGER # Integer
  | IDENTIFIER # Identifier
  | expression (MULTIPLY|DIVIDE|MOD) expression # Multiplicative
  | expression (PLUS|MINUS) expression # Additive
  ;

// Terminals

IF: 'if';
ELSE: 'else';
TO: 'to';
MOVE: 'move';
ROTATE: 'turn';
REPEAT: 'repeat';
END: 'end';
PRINT: 'print';
LEFT_PARENTHESIS: '(';
RIGHT_PARENTHESIS: ')';
MULTIPLY: '*';
DIVIDE: '/';
MOD: '%';
PLUS: '+';
MINUS: '-';
ASSIGNMENT: '=';
IDENTIFIER: [a-z]+ [a-z_]*;
INTEGER: '-'? [0-9]+;

NEWLINE: '\n';
WHITESPACE: [ \t]+ -> 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 `'

Block.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 `'

Statement.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 `'

PrintStatement.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 `'

Expression.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 `'

ExpressionInteger.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 `'

repeat.logo

repeat 5
  print 2
  print 3
end