home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)

S0
Interpreting S
(finalized in class)

The language S0

  Expr   ::= Num | Paren | BinOp | Ifnz
  Paren  ::= | Expr |     (note: these “|”s are literal -- not BNF “or”s)
  BinOp  ::= ? Op Expr Expr
  Ifnz   ::= ( Expr ) !0  Expr : Expr 
  Op     ::= ad | su | mu

where Num is any numeric literal (as written in either Java or Racket, your choice ¹). For the provided parsers to work, whitespace is required between all terminals with the exception of punctuation.

Semantics:

A Paren is a parenthesized expression (used for grouping only);
A Binop is a binary operator expression, in prefix; ad means addition; su means subtraction; mu means multiplication.
A Ifnz evaluates its first expression; if it is non-zero then the result is the second expression (evaluated), else the result is the third expression (evaluated).

Discussion

Give five example programs (Exprs) written in S0.
Give their parse trees.
How should we represent these trees, internally? (In Racket, and equivalently in Java).

Where we're headed

For interpreting this language, we will implement three methods:
- parse, which turns source-code into an internal representation,
- toString which turns internal representation back into source-code,
- eval, which actually interprets the program, returning a value (a number for S0-S2, and a number-or-function in S3).
I recommend implementing and testing the methods in this order. Some test-cases will be provided. There might be other helper functions to implement as well.

S0 Implementations

S0.rkt, with helper files scanner.rkt (and, scanner-demo.rkt); test cases expr-test-S0.rkt, and student-extras.rkt.
Note:Download the racket files, and then choose Open… from DrRacket. Do not copy/paste into an empty DrRacket window, since that window is probably using a student-language, and some of the files below use full racket.
Java S0-java/ (browse the directory), or see the .jar.
Note the composite pattern to implement union-types, in Java: The classes Expr and its four variants Num/BinOp/Ifnz/Paren are organized in the same way AncTree and its two variants Child/Unknown were.

¹This is so we can just use our language's built-in number-parsing functions, without getting bogged down in tokening input. So racket implementations will allow exactly those strings recognized by number?, (including +nan.0, -inf.0, and 2+3i).

Similarly, if using Java, the semantics of S0's arithmetic will be similar to IEEE floating point arithmetic (rather than perfectly-correct arithmetic).

Don't confuse S0's class Num (which extends Expr) with the existing java.lang.Number, which doesn't extend Expr.

↩