Homework 09: Symbolic Evaluation of Boolean Expressions in Java
Due: 10am FridayWednesday, March 2631, 2010
Overview
Write a Java program boolSimp.dj1
that reduces boolean expressions (represented in the input and output streams in Scheme-like notation) to simplified form. For the purposes of this assignment, boolean expressions are Scheme expressions constructed from:
...
- a Scheme program in the file
boolsimp.ss
equivalent to the Java program that you are required to write; - a Java "stub" file
boolSimp.dj1
that defines a composite hierarchy of "abstract syntax" tree classes rooted in the classForm
representing boolean expressions; - a Java library file
Parser.java
contain a classParser
with- a
read()
method that reads a boolean expression represented in "Scheme form" and returns the corresponsing JavaForm
abstract syntax tree and - a
reduce(
commented out)
simplify()
method that composes the visitors you must write inboolSimp.dj1
to simplify reduce whatever formula theParser
instance contains to simplified form.
- a
- a Java "stub" test file
boolSimpTest.java
that includes some rudimentary tests of the code in theboolSimp.dj1
stub file.
...
The Java abstract syntax classes include a separate composite hierarchy (called IfForm
for representing boolean expression as conditionals (the type ifExp
in boolsimp.ss
). This representation includes only three concrete variant classes, making it much easier to write the visitors that perform normalization, evaluation, and clean-up.
The visitor pattern is a straightforward but notationally involved alternative to the interpreter pattern.. You can mechanically translate interpreter pattern code to visitor pattern code. (Perhaps IDEs like Eclipse should support such transformations.) The interpreter solution to this assignment is easier to write than the visitor solution described in the preceding program description. If you are still learning Java mechanics, you are encouraged to write an interpreter solution first and translate it (if you can) to visitor form. A perfect interpreter solution will only be penalized 15% versus a perfect visitor solution. If you submit an interpreter solution, your program must conform to class signatures given in the interpreter pattern support code below (just as a visitor solution must conform to the class signatures given in the visitor pattern code below).
The interpreter version of the support code replaces the ConvertToIf
, Normalize
, HeadNormalize
, Evaluate
, and Print
visitors by methods named convertToIf
, normalize
, headNormalize
, eval
, and print
.
Support Code
Here are the links for the files:
- boolsimp.ss is the reference Scheme program.
- BoolSimp.dj1 is a stub program for a visitor solution.
- BoolSimpTest.java is a stub test file for a visitor solution.
- Parser.java is a parser file for a visitor solution.
- InterpBoolSimp.dj1 is a stub program for an interpreter solution.
- InterpBoolSimpTest.java is a stub test file for an interpreter solution.
- InterpParser.javaboolsimp.ss is a parser file for an interpreter solution.
InterpParser.java
is distinct from Parser.java
because the code for the reduce
method embedded in the parser is different in the two versions.
Sample Input Files
The following files contain large formulas that can be reduced by your simplifier. Only the file named bigData
require a larger thread stack size than the default on my laptop. I used the JVM argument -Xss64M for the Interactions JVM to get the bigData
files to run.
...