We will use recursion techniques to build a "compiler" that translates a logical proposition into a format without conjunction operators and then "optimizes" (simplifies) the proposition by removing redundant negations (NOT) and True/False constants.
The input to the translator is a line of text that contains a proposition written with letters, True, False, parentheses, and the operators AND($^$), OR ($v$), and NOT ($~$). The proposition must be parenthesized, that is, $p ^ (True ^ ~r)$ must be entered, rather than $p ^ True ^ ~r$.
The first step is that
all occurrences of
$^$ are replaced by $~$ and $v$:
Next, the expression is "optimized" by removing extra uses of OR and NOT. Here are the steps that
can be taken on the previous example:
Here is an example of a session with the translator:
I have written a parser that converts a proposition (string) into a
nested-list parse tree. (In fact, you get two parsers: one I wrote by
hand, $handparseFYI.py$, and one that is automatically generated from
the grammar rules using the $PLY$ (Python-Lex-Yac) domain-specific language.
You'll be using the latter for your implementation, since it is a bit
less restrictive than the hand-written one.)
Your job is to write the functions that eliminate conjunctions (ANDs)
and optimize the resulting tree.
I have prepared an incomplete Python program, $translate.py$, and have indicated
where you install the missing functions.
The program can be downloaded at
http://www.cis.ksu.edu/~schmidt/301s14/Exercises/Translate.
Read the commentary embedded in the code before you add any of your own code.
The program is ready to be tested as is, and your job is to replace
the dummy functions in it by real functions.
Read the commentary embedded in the file before you add any of your own code.
This exercise will give you practice with grammars,
dynamic data structures, and recursive
function definitions.
If you have never used Python before, please read the web page,
Using Python for software development.
REALLY?????????????????
You can work solo or with a partner on this project. If you
work with a partner, you are required to
For each test case, copy the output that the program generates into a
txt file, $tests.txt$. Save the txt files with your completed program,
translate.py, in a folder. Zip the folder and
submit it to the CIS301 web page on K-State online.
You must submit both your completed program plus the output from
the test cases to receive credit for working the assignment.
Mr. Janovsky and I will copy your $translate.py$ into our own folders
that hold the parser and driver and run it. So, alter only
$translate.py$.
(Finally, please do not try to check your program with the CIS301 proof
checker, because the checker is unable to analyze programs that
manipulate strings and lists of strings. Sorry!)
> python run.py
Type proposition to translate: p ^ (True ^ ~r)
Parsed input: ['^', 'p', ['^', 'True', ['~', 'r']]]
which denotes (p ^ (True ^ ~r))
Translation:
ands removed: ['~', ['v', ['~', 'p'], ['~', ['~', ['v', ['~', 'True'], ['~', ['~', 'r']]]]]]]
~(~p v ~~(~True v ~~r))
double negation removed: ['~', ['v', ['~', 'p'], ['v', ['~', 'True'], ['~', ['~', 'r']]]]]
]]
~(~p v (~True v ~~r))
negation removed: ['~', ['v', ['~', 'p'], ['v', 'False', ['~', ['~', 'r']]]]]
~(~p v (False v ~~r))
or removed: ['~', ['v', ['~', 'p'], ['~', ['~', 'r']]]]
~(~p v ~~r)
double negation removed: ['~', ['v', ['~', 'p'], 'r']]
~(~p v r)
Output:
['~', ['v', ['~', 'p'], 'r']]
which denotes ~(~p v r)
The input syntax is defined by this
grammar rule:
What you implement
As always, file copying and sharing are not allowed (except within each
two-person team).
What to submit
I have included a file $testcases.txt$ of test cases you should
use to test your work. Do the tests in order, and you will have a
smooth job.