Homework 09: Symbolic Evaluation of Boolean Expressions in Java
Due: 10am Monday, April 4, 2011
Overview
Write a Java program boolSimp.dj
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:
...
The stub file BoolSimp.dj
also includes comments showing you exactly what code you have to write to complete writing your simplifier. Of course, you also need to write corresponding tests and add them to the file BoolSimpTest.java
.
The file Parser.java
is provided to enable you to test your solution on large inputs stored in files. Parser.java
includes two Parser
constructors Parser(File file)
and Parser(String form)
for building parsers to parse the boolean expression (in external text form) in the specified File
or String
, respectively. Since the library class File
is defined in the package java.io
, you need to insert either
Code Block |
---|
import java.io.*;
|
or more specifically
Code Block |
---|
import java.io.File;
|
at the head of a test file that uses the Parser
class on the contents of a file.
To construct a Parser
for the formula in a file {{}} <fileName>
you must invoke
Code Block |
---|
new Parser(new File("<fileName>")); |
...
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).
...
Here are the links for the files:
- boolsimp.ss\ is the reference Scheme program.
- BoolSimp.dj\ 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.dj\ is a stub program for an interpreter solution.
- InterpBoolSimpTest.java\ is a stub test file for an interpreter solution.
- InterpParser.java\ is a parser file for an interpreter solution.
...
The following files contain large formulas that can be reduced by your simplifier. Only the file files named bigData
x require a larger thread stack size than the JVM default on my laptop. I used the most platforms. NOTE: to handle the bigData
x files, you must set JVM argument -Xss64M for the Interactions JVM to get the bigData
files to runJVM using the DrJava Preferences command on the Edit menu. The JVM argument setting can be found on the last panel (called JVMs) in the Preferences categories tree.
- littleData1\ -> "T"
- littleData2\ -> "T"
- littleData3\ -> "(> h (> g (> f (> e (> d (> c (! b)))))))"
- littleData4\ -> "(> h (> g (> f (> e (| d (| c (| b a)))))))"
- bigData0\ -> "T"
- bigData1\ -> "(> j (> i (> h (> g (> f (> e (| d (| c (| b a)))))))))"