CS 330 Lecture 11 – Abstract Syntax Trees
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/vendor_ruby/rubygems/dependency.rb:315:in `to_specs': Could not find 'coderay' (>= 0) among 94 total gem(s) (Gem::MissingSpecError) Checked in 'GEM_PATH=/var/www/.local/share/gem/ruby/3.2.0:/var/lib/gems/3.2.0:/usr/local/lib/ruby/gems/3.2.0:/usr/lib/ruby/gems/3.2.0:/usr/lib/x86_64-linux-gnu/ruby/gems/3.2.0:/usr/share/rubygems-integration/3.2.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/3.2.0:/home/johnch/.gems' , execute `gem env` for more information from /usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:327:in `to_spec' from /usr/lib/ruby/vendor_ruby/rubygems/core_ext/kernel_gem.rb:57:in `gem' from ./coderay:24:in `'
Block.java
/usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:315:in `to_specs': Could not find 'coderay' (>= 0) among 94 total gem(s) (Gem::MissingSpecError) Checked in 'GEM_PATH=/var/www/.local/share/gem/ruby/3.2.0:/var/lib/gems/3.2.0:/usr/local/lib/ruby/gems/3.2.0:/usr/lib/ruby/gems/3.2.0:/usr/lib/x86_64-linux-gnu/ruby/gems/3.2.0:/usr/share/rubygems-integration/3.2.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/3.2.0:/home/johnch/.gems' , execute `gem env` for more information from /usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:327:in `to_spec' from /usr/lib/ruby/vendor_ruby/rubygems/core_ext/kernel_gem.rb:57:in `gem' from ./coderay:24:in `'
Statement.java
/usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:315:in `to_specs': Could not find 'coderay' (>= 0) among 94 total gem(s) (Gem::MissingSpecError) Checked in 'GEM_PATH=/var/www/.local/share/gem/ruby/3.2.0:/var/lib/gems/3.2.0:/usr/local/lib/ruby/gems/3.2.0:/usr/lib/ruby/gems/3.2.0:/usr/lib/x86_64-linux-gnu/ruby/gems/3.2.0:/usr/share/rubygems-integration/3.2.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/3.2.0:/home/johnch/.gems' , execute `gem env` for more information from /usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:327:in `to_spec' from /usr/lib/ruby/vendor_ruby/rubygems/core_ext/kernel_gem.rb:57:in `gem' from ./coderay:24:in `'
PrintStatement.java
/usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:315:in `to_specs': Could not find 'coderay' (>= 0) among 94 total gem(s) (Gem::MissingSpecError) Checked in 'GEM_PATH=/var/www/.local/share/gem/ruby/3.2.0:/var/lib/gems/3.2.0:/usr/local/lib/ruby/gems/3.2.0:/usr/lib/ruby/gems/3.2.0:/usr/lib/x86_64-linux-gnu/ruby/gems/3.2.0:/usr/share/rubygems-integration/3.2.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/3.2.0:/home/johnch/.gems' , execute `gem env` for more information from /usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:327:in `to_spec' from /usr/lib/ruby/vendor_ruby/rubygems/core_ext/kernel_gem.rb:57:in `gem' from ./coderay:24:in `'
Expression.java
/usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:315:in `to_specs': Could not find 'coderay' (>= 0) among 94 total gem(s) (Gem::MissingSpecError) Checked in 'GEM_PATH=/var/www/.local/share/gem/ruby/3.2.0:/var/lib/gems/3.2.0:/usr/local/lib/ruby/gems/3.2.0:/usr/lib/ruby/gems/3.2.0:/usr/lib/x86_64-linux-gnu/ruby/gems/3.2.0:/usr/share/rubygems-integration/3.2.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/3.2.0:/home/johnch/.gems' , execute `gem env` for more information from /usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:327:in `to_spec' from /usr/lib/ruby/vendor_ruby/rubygems/core_ext/kernel_gem.rb:57:in `gem' from ./coderay:24:in `'
ExpressionInteger.java
/usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:315:in `to_specs': Could not find 'coderay' (>= 0) among 94 total gem(s) (Gem::MissingSpecError) Checked in 'GEM_PATH=/var/www/.local/share/gem/ruby/3.2.0:/var/lib/gems/3.2.0:/usr/local/lib/ruby/gems/3.2.0:/usr/lib/ruby/gems/3.2.0:/usr/lib/x86_64-linux-gnu/ruby/gems/3.2.0:/usr/share/rubygems-integration/3.2.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/3.2.0:/home/johnch/.gems' , execute `gem env` for more information from /usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:327:in `to_spec' from /usr/lib/ruby/vendor_ruby/rubygems/core_ext/kernel_gem.rb:57:in `gem' from ./coderay:24:in `'
repeat.logo
repeat 5
print 2
print 3
end