» CS 330 Lecture 9

CS 330 Lecture 9 – Grammars

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

Agenda

the source-to-execution pipeline
a boolean grammar
- terminals (the atoms)
- nonterminals (the molecules)
- productions
an interpreter

TODO

Setup ANTLR4 per Getting Started with ANTLR4. Define the aliases in you shell’s startup files (.zshrc or .bashrc, probably) so they stick around between sessions. Create a lexer and parser for the boolean grammar provided below. On a 1/4 sheet, draw the parse tree that you see when running the TestRig on the input !(true || false && true).
With the -gui command-line option, TestRig will try to open a window. This probably won’t automatically succeed when you are logged in remotely to one of the thingies. I highly suggest you figure out how to log in with X-forwarding on Windows or Mac. (Linux is pretty easy: ssh -X thing-04.cs.uwec.edu). You will definitely benefit from getting this working now for a couple of later assignments.

Failing the X-forwarding route, you can ask the TestRig to export a Postscript file:
```
echo "YOUR BOOLEAN EXPRESSION" | java -cp antlr-4.5.2-complete.jar:. org.antlr.v4.gui.TestRig Boo expression -ps parse_tree.ps
```
You’ll then need to download parse_tree.ps and view or convert it with a Postscript reader. There are many available online.

Note

We discuss today the pipeline that our source code goes through on its way to becoming an executable. Whether its compiled or interpreted directly, the first step is getting our tools to understand the source. We’ll have a look at how a grammar for a language can be used to automatically generate a lexer and a parser for our own custom languages.

Code

Boo.g

grammar Boo;

expression
  : LITERAL
  | LEFT_PARENTHESIS expression RIGHT_PARENTHESIS
  | IDENTIFIER
  | NOT expression
  | expression XOR expression
  | expression AND expression
  | expression OR expression
  ;

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