Homework 09: Symbolic Evaluation of Boolean Expressions in Java
Due: Wednesday 10am Friday, March 2526, 20092010
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:
- the symbols
T
andF
denoting the boolean valuestrue
andfalse
; - boolean variables (represented by symbols other than
T
,F
,!
,
&
,|
,>
, and?=)
that can be bound to either=true
orfalse
. - the unary function
!
meaningnot
. - the binary functions
&
,|
, and>
meanding
denotingand
,or
, andimplies
, respectively), and - the ternary function
?
meaningif
.
The shorter names T
, F
, !
, &
, |
, >
, and ?
are used instead of
true
, false
, not
, and
, or
, implies
, and ={{if=}) for notational brevity which matters in very large nputsinputs.
The course staff is providing:
- 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
expresssions; - 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 (commented out)
simplify()
method that composes the visitors you must write inboolSimp.dj1
to simplify whatever formula theParser
instance contains.
- a
- a Java "stub" test file
boolSimpTest.java
that includes some rudimentary tests of the code in theboolSimp.dj1
stub file.
...
If you omit the new File(...)
construction in the argument to Parser
and use "
<}} fileName
{{><fileName>"
instead,
you will create a Parser
for the String "<
fileName
>
{}
" <fileName>"
. which is interpreted
as a simple boolean variable.
The File
input format is important because it enables us to
conveniently teat apply your simplifier on to formulas that are thousands of symbols
long).
As a result, you only have to translate the Scheme code in
boolsimp.ss
into corresponding cleanly-written OO Java code by filling in the gaps in our Java
stub file boolSimp.dj1
. You are expected to
appropriately use the composite, interpreter, singleton, and visitor
patterns in the code that you write. Since the only stub files that
you have to modify are boolSimp.dj1
and boolSimpTest.java
, simply submit expanded
versions of these files
via OwlNet OwlSpace to submit your
assignment. Warning: we will run your program on large
inputs to determine if you wrote the code correctly. Try using the large test files provided on
the course wiki.
We have formatted the test files as a .java
file rather than a .dj1
because the Language Levels facility peforms no
useful augmentation of JUnit test classes and bypassing the language levels translator avoids some annoying bugs in the
implementation of that facility. Please remember to save you file boolSimpTest.java
as a .java
file not as a .dj1
file.
Correction: we now recommend using Advanced Level ( .dj2=) files instead of Full Java (
.java {{) files in mixed compilation with Intermediate Level files. You should be able to consistently use }} .dj2 {{ files instead of }} .java= files if you download the latest version of DrJava from www.cs.rice.edu/~javaplt/drjavarice. See the Addendum below.
The Scheme file boolsimp.ss
includes Scheme functions parse
and
unparse
to translate Scheme lists into abstract syntax trees and
vice-versa. Scheme provides a simple external syntax for lists (in
homage to is LISP heritage) but Java does not. Hence the java
Parser
class works on Java strings instead of lists. The Java visitor class
Print
in the BoolSimp.java
file performs unparsing of the abstract syntax
types Form
and IfForm
to type String.
The Scheme parsing functions rely on the following Scheme data definitions.
...
- a boolean constant
true
andfalse
; - a symbol
S
representing a boolean variable; (make-Not X)
whereX
is aboolExp
;(make-And X Y) where =X
andY
are =boolExp=sboolExps
;(make-Or X Y) where =X
andY
are =boolExp=sboolExps
;(make-Implies X Y) where ={{X
andY
are =boolExp=sboolExps
; or(make-If X Y Z)
whereX
,Y
, andZ
are =boolExp=sboolExps
.
Note: The or
operator must be written a as |
in Scheme instead of
|
because |
is a metasymbol with a special meaning in Scheme (akin
to ='=).
...