The Truth Lab, 2/16/99


Writing a compiler is an exercise in "meta-programming" where the syntax and structures of one language is used to reason about and manipulate syntax and strutures of another language. This lab asks you to build a truth table generator similar to the one shown in class. Here the "object" language to be manipulated is the language of proposional calculus. It well illustrates the need for a abstract syntax tree, and the distinction between the semantic and the syntactic phases of a compiler (and of meta-programming in general). Much code has already been provided for you, and are available from the following locations:
  1. http://shakti.trincoll.edu/~cliang/c371/truth.lex
  2. http://shakti.trincoll.edu/~cliang/c371/truth.cup
  3. http://shakti.trincoll.edu/~cliang/c371/truthtable.java

You may use/not use, or modify these files anyway you want. For the main "truthtable" file, you need to complete the definition of the the abstract syntax tree classes, define a procedure that traverses the tree and collects all the propositional letters in the tree, then write a procedure (presumably in main) that generates truth assignments and evaluates the tree, printing out the truth table in the process.

To generate the truth table, the Integer.toBinaryString(int x) function returns a string of 1's and 0's that corresponds to the binary representation of x. However, leading "0"'s must be added so the length of the string matches the number of propositional letters - this is already done for you by your super-nice professor in the constructor of the "assignment" class of "truthtable.java". If there are n different letters in the propositional sentence, then its truth table will contain (int) Math.pow(2,n) lines.