/* CSC 124: The Truth Lab READ THIS TWICE!!!! In this assignment we will put what we've learned so far this semester into a self-contained project. we are going to use JLex and Java_Cup to write a program that takes as input a sentence of propositional logic, and output a truth table for the sentence: For example: (transcript of my working program:) Enter proposition: (a|b)->(b&c&!a) a b c | value 0 0 0 | 1 0 0 1 | 1 0 1 0 | 0 0 1 1 | 1 1 0 0 | 0 1 0 1 | 0 1 1 0 | 0 1 1 1 | 0 The symbol | represents "or", & is "and", ! is "not" and -> is "implies". It is also valid to use the symbol "^" for "and" and "~" for "not". One can also use 0 and 1 for the constants false and true respectively. The unary ! binds tighter than all other connectives (so you need to specify the precedence for it in the correct way). & and | binds tighter than ->. & and | associates to the left but -> associates to the right. For example, a->!b|c is the same as a->((!b)|c). These rules should allow you to use an ambiguous grammar in Java_Cup with precedence declarations. Unlike the online calculator example, we can't just perform the calculation as we parse, because we don't know what values the variables will be bound to. We need to generate an abstract syntax tree structure that represents the expression. Then, after the parsing stage, we need to enumerate all possible assignments for the variables - that is, all possible combinations of 0's and 1's for the variables of the sentence. Then we can evaluate the abstract syntax tree for each "truth assignment" and determine the results. The classes following these comments consititute the abstract syntax representation. All expression classes implement the "exp" abstract interface (abstract superclass). conste : constant expressions (0 or 1) vare : variable expression (a, b, or any identifier) ande : and expression (E1 & E2) note : negative expression (!E) ore : or expression (E1 | E2) -- you must complete this impe : implication expression (E1 -> E2). -- you must complete this Each expression class must implement a method "eval" that evaluates the expression (recursively) given a truth assignment (that is, an assignment of 0's or 1's to each propositional variable). The truth assignment is implemented using a Java API Hashtable. For example, given: Hashtable H = new Hashtable(2); // creates a hash table with up to 2 entries (if there are 2 variables). To assign true to the variable "a", we say: H.put("a",true); To get the truth value of a variable stored in the table, we use the expression H.get("a"). The String "a" is called a "key" to the hashtable, and the Boolean value is called the "value" of the key. Regular arrays can only use non-negative integers for the key, whereas hashtables can use keys of any type. The type parameters therefore determines what kind of table should be created. You can only use reference types for type parameters, that's why it's "Boolean" instead of "boolean". But new Java 1.5 allows automatic conversion from the two types, so using them is not so bad (anymore). The interface for exp and the classes for conste, vare, ande and note have been written. You need to complete the classes for ore and impe. ore is a no-brainer, but there's no Java built-in boolean operator for implication, so you'll have to be a bit more clever here. The definition of -> is: a b | a->b 0 0 | 1 0 1 | 1 1 0 | 0 1 1 | 1 After you have completed the definition of each class, given any exp E, E.eval(H) will return the truth value of the expression relative to the truth assignment (hashtable) H. */ import java.util.*; // Abstract syntax for propositional logic interface exp { Boolean eval(Hashtable env); } class conste implements exp // constants true and false { boolean val; public conste(boolean v) {val=v;} public Boolean eval(Hashtable env) { return val; } } class vare implements exp // propositional variable { String v; public vare(String s) {v=s;} public Boolean eval(Hashtable env) { return env.get(v); } // lookup truth assignment in hash table. } // super class for all binary operator expressions class opsuper { exp left, right; // left and right subexpressions. public opsuper(exp l, exp r) {left=l; right=r;} } class ande extends opsuper implements exp { public ande(exp l, exp r) { super(l,r); } public Boolean eval(Hashtable env) { return left.eval(env) && right.eval(env); } } // ande class nege implements exp { exp sub; // sub-expression public nege(exp s) {sub=s;} public Boolean eval(Hashtable env) { return !sub.eval(env); } } class ore // COMPLETE THIS CLASS { } // ore class impe // COMPLETE THIS CLASS { } // impe /* ************************************************** For the next step of the assignment, you need to write a Java_Cup grammar file to create a parser for reading in propositional sentences from System.in. Sketch the grammar on paper and follow the online calculator example on the web page. I've also provided you with a lexical analyzer, in truth.lex, on the homepage. However, to use it, you must make sure that the names of your terminal symbols are consistently declared in your .cup file (i.e, AND, OR, IMP, NOT, ID, etc ...) The semantic value associated with the start symbol of your grammar should naturally be an exp object. The semantic actions (enclosed in {: :}) for each production should construct the exp tree bottom-up. There is one other thing that your parser should do: In order to build the truth table, we need to know how many distinct variables there are in an expression. For example, in (a|b)->(b&c&!a) there are three distinct variables: a, b, c. We need a data structure to record this. I suggest you use the following (declared in your .java file, not your .cup file): */ // For java_cup integration: class Vars { public static ArrayList S = new ArrayList(31); } /* This class effectively introduces a global variable, Vars.S, into your program. The variable can be changed by other parts of the program. The Java API structure ArrayList represents a vector of Strings. Vars.S.add("a"); will add a new string to the ArrayList Vars.S.get(2) will return the 3rd string in the ArrayList Vars.S.size() returns the size of the arraylist. Vars.S.contains("b") determines if "b" is a member of the ArrayList In the class Vars the ArrayList S is initialized to a maximum capacity of 31 entries. Why 31? See below. Whenever your parser sees an ID:s (identifier), it should check if the string s is inside Vars.S. If it is not already there, add it. That way, after everything is parsed the globally-accessible Vars.S structure will contain a list of the unique identifiers. Got it? If not, come see me outside of the class (I'm expecting you). At this point, you're ready to write the "main" program. I've given you the following skeleton: all it does is to call parse(), which returns an exp object. */ public class truthlab { public static void main(String[] args) throws Exception { parser Prs = new parser(); System.out.print("Enter proposition: "); exp E = (exp) Prs.parse().value; int n = Vars.S.size(); // number of propositional variables Hashtable Env = new Hashtable(n); System.out.println("and the truth table is ..."); // YOU HAVE TO COMPLETE THIS ... } // main } /* The main program should generate all possible truth table assignments (represented inside in a Hashtable) and call eval on the exp tree E. So how do you generate all possible truth assignments? Observe that for n variables, there are 2^n or (int)Math.pow(2,n) possible truth assignments, representing in binary the numbers 0 to (int)Math.pow(2,n)-1. So all you have to do is to enumerate these numbers and for each number, extract each bit from right to left. If we use two's complement integers, we can use this technique to represent up to 31 different propositional variables, which is certainly enough. Additional hints: Given positive int k, k%2==1 tests if the least-significant (rightmost) bit of k is 1. k = k/2; will shift the bits of k to the right, discarding the least-significant bit. You have to figure out the rest. ----------------------------------------------------------------- TO SUMMARIZE: For this assignment I have provided you with the following: 1. the lexical analyser truth.lex 2. the abstract syntax classes except ore and impe. 3. the algorithm and data structure for capturing the list of all distinct variables in a sentence. 4. The algorithm for generating all possible truth assignments. I have also provided you with examples of .cup specifications, most notably the one for the online calculator. YOU HAVE TO DO THE FOLLOWING: *** make sure you create a unique directory and are using jdk 1.5 *** 0. Finish the ore and impe classes (this should be warmup). 1. Write a .cup parser specification, being careful to use the the same names for terminal tokens as they are used in truth.lex. The parser's semantic actions should contruct an exp tree and record the distinct variables in the structure Vars.S 2. Finish writing main. 3. java_cup the .cup file, THEN JLex the .lex file. Then compile all .java files together. Test and demonstrate it to me. 4. Erase my comments to make it look like you wrote it all by yourself. 5. (currently optional) Make all necessary modifications to add a new operator for exclusive-or. Use "*" as the symbol. The output of your program should be well-formated and be similar to mine. Read these guidelines carefully once again before proceeding to the programming phase. */