/*
               CSC 124: The Truth Lab First Stage

	  Progress Grades will be Given Second Week of Class

  In this multi-part assignment we will learn the basics of lexical 
  analysis and parsing, using the JFlex lexical analyzer but with
  (eventually) your own parser generator.

PART I: Do textbook exercises 2.1a-c, 2.4, and 2.5a.


  Ultimately, you need to write a program that takes as input a sentence of
  propositional logic, and output a truth table for the sentence.
  As examples:  (transcripts 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

    Enter proposition: ~(a ^ b) -> ~a v ~b
      a b  | value
      0 0  |  1
      0 1  |  1
      1 0  |  1
      1 1  |  1


The symbol | represents "or", & is "and", ! is "not" and -> is
"implies".  It is also valid to use the symbol "^" for "and", "v" for
"or" and "~" for "not". Use 0 or F for the constant false and 1 or T 
for true.  The above proposition can also be written as 
                 
             a v b -> b ^ c^~a

Propositional variables are NOT limited to single letters: a2 -> a2 is fine.
Of course, avb should not be confused with a v b: sometimes spaces are needed.

Syntactically, negation ! (~) binds tighter than all other
connectives (so you need to specify the precedence for it in the
correct way).  & binds tighter than than |, which in turn 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).

PART II: Use JFlex to write a lexical analyzer for this syntax.  All the
lexical analyzer produces are tokens.  It does not have to do anything else.
Issues such as precedence and associativity of the operators are left to the
parsing phase of the assignment.  You can put print statements in the action
part of each state transition to tracet the recognition of each token.

Your JFlex lexer should output instances of the following class (put in
separate file)

public class Gsym
{ 
    public final String sym;
    public String javatype = null;
    public boolean nonterminal = false;
    public String assoc = null;  // label of object associated with symbol.
    public Object value = null;
    // assoc and value never used together: assoc in rule, value on stack
    public Gsym(String x) {sym=x;}
    public Gsym(String x, Object v) {sym=x; value=v;}
    public Gsym(String x, String y, boolean t) 
     {sym=x; javatype=y; nonterminal=t;}

    public Gsym clone()
    { Gsym g = new Gsym(sym,javatype,nonterminal);
	g.assoc = assoc;  g.value = value;
	return g;
    }
}//Gsym

This is the generic "symbol" class used by MVOPG (my very own parser
generator).  Unlike Java Cup (yacc), I simplified things so that the lexer 
and the parser both use this "grammar symbol" class.  Not everything in this
class pertains to this assignment.  For example, when you see "->" you can
just return a new Gsym("->");  Consult my examples.  Write a main to test that
your lexer is indeed reading all the symbols.  The lexer class generated by
JFlex contains a public method yylex() to return symbols one at a time.


Part III: Abstract syntax.

Write an independent java program that represents abstract syntax trees for
propositional sentences.  Look at my examples (calculator, jBasic interpreter)
for examples.  Also read textbook section 1.3 and chapter 4 for ideas.
Note that at some point I will ask you to convert your tree classes to use
the Visitor design pattern, but that is not technically required for part III.

After you compile the abstract syntax classes, the lexer generated by JFlex
should also compile.

Here are some specific hints:

public interface Prop // interface for all propositions
{
    Boolean eval(Hashtable<String,Boolean> env); // evaluate proposition
    void vars(ArrayList<String> vs); // collects vars in vs list (init empty)
}

class propvar implements Prop // propositional variables
{
    String varname;
    public propvar(String s) {varname=s;}
    public Boolean eval(Hashtable<String,Boolean> env) 
    { return env.get(varname); }
    public void vars(ArrayList<String> vs) 
    { if (!vs.contains(varname)) vs.add(varname); }
}

Part IV: Generating a truth table.

Write a routine that generates a truth table with output as shown
above.  Since you don't have a parser yet, you can hand-code a couple
of small examples to test it (include ~(a & b) -> ~a | ~b (De Morgan
law).  Hint on generating the lines of the truth table: If there are n
distinct propositional variables in your proposition, then there
should be (int)Math.pow(2,n) lines in the truth table. Each line
corresponds to binar numer (000, 001, 010, etc.).  I believe there's
even a built-in "toBinaryString" function in java (find it yourself).

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.  Thus
the eval method in the hint code takes a "env", which is a Hashtable 
representing a truth assignment.

The truth table for -> is:

           a  b  |  a->b
           0  0  |   1
           0  1  |   1
           1  0  |   0
           1  1  |   1

***In order to receive a passing 1st progress grade, you must have
completed (not just attempted) each of parts 1-4 described above.

More parts later ...