Here are some components of my online calculator program. These fragments of code are provided as guidelines for how to write your truth table programs. // class that represents grammar symbol, used by both lexer and parser: public class Gsym { public final String sym; // e.g., "=", "+", "while" public String javatype = null; // e.g., String, int, etc public boolean nonterminal = false; public String assoc = null; // label of object associated with symbol. public Object value = null; // for example, value of a number symbol // 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 ////////////////////////////////////////////////////////////////////////////// /* The following is the JFlex file I used for the lexical analyzer: The declaration %class calclexer means that jflex will produce a file calclexer.java with a public class calclexer. The declaration %type Gsym means that the main parsing function calclexer.yylex() will return objects of type Gsym. is the initial state, what follows is a regular expression. We always stay at state unless there is a command to begin another state. In the action part (enclosed by { }) of each rule, yytext() refers to the text (as String) that the pattern matched. */ // online calculator lexical analyzer - create Gsym objects %% %class calclexer %unicode %type Gsym %eofval{ {return new Gsym("EOF"); } %eofval} LineTerminator = \r|\n|\r\n WhiteSpace = {LineTerminator} | [ \t\f] DecIntegerLiteral = 0 | [1-9][0-9]* SimpleToken = "+" | "*" | "-" | "/" | "==" | "(" | ")" | "=" | "let" | "in" Identifier = [:jletter:] [:jletterdigit:]* %% {WhiteSpace} { /* do nothing */ } {SimpleToken} { return new Gsym(yytext()); } {Identifier} { return new Gsym("var",new String(yytext())); } {DecIntegerLiteral} { return new Gsym("num",new Integer(yytext()));} [^] { throw new Error("Illegal character <"+ yytext()+">"); } ////////////////////////////////////////////////////////////////////////////// /* The following is the code for the abstract syntax */ public interface Expr // abstract type of all expressions { int eval(); } class intexp implements Expr // integer literal { int val; public intexp(Integer x) { val = (int)x; } public int eval() {return val;} } class binop // code shared by all binary operators { Expr e1, e2; public binop(Expr a, Expr b) {e1=a; e2=b;} } class sumexp extends binop implements Expr { public sumexp(Expr a, Expr b) {super(a,b);} public int eval() { return e1.eval() + e2.eval(); } } class multexp extends binop implements Expr { public multexp(Expr a, Expr b) {super(a,b);} public int eval() { return e1.eval() * e2.eval(); } } class subexp extends binop implements Expr { public subexp(Expr a, Expr b) {super(a,b);} public int eval() { return e1.eval() - e2.eval(); } } class eqexp extends binop implements Expr { public eqexp(Expr a, Expr b) {super(a,b);} public int eval() { if (e1.eval()==e2.eval()) return 1; else return 0;} } class negexp implements Expr // unary minus { Expr e; public negexp(Expr x) {e=x;} public int eval() {return -1 * e.eval();} } ////////////////////////////////////////////////////////////////////////////// /* The following is the grammar I used with MVOPG (my very own parser generator) for the online calculator. I picked the format of the grammar so that it's easy to parse. Spaces are important (don't write B-->B), production rules occupy single lines, and the semantic action enclosed in { }'s must be at the very end of each rule. This makes it relatively easy to hand-code a "metaparser" for a grammar file such as this. For YVOPG, you may use my syntax, or design a different syntax for your grammars. But you must implement your metaparser from scratch. */ # Grammar for online calculator # The syntax nonterminal E Expr means that the semantic attribute associated # with the non-terminal symbol E is the java type Expr. nonterminal E Expr terminal ( ) + * - == typedterminal num Integer topsym E # top level grammar symbol # precedence and associativity declarations. # These rules must appear before the production rules. left * 500 left + 400 left - 400 left == 300 left ) 50 left ( 900 left num 980 # Grammar production rules, order breaks reduce-reduce conflicts # spaces must separate grammar elements, including spaces in { ... }. E --> num:x { return new intexp(x); } E --> E:e1 + E:e2 { return new sumexp(e1,e2); } E --> E:e1 * E:e2 { return new multexp(e1,e2); } E --> E:e1 - E:e2 { return new subexp(e1,e2); } E --> E:e1 == E:e2 { return new eqexp(e1,e2); } E --> - E:e { return new negexp(e); } E --> ( E:e ) { return e; } # ends file, whatever follows EOF is ignored and can be used for more comments. EOF ////////////////////////////////////////////////////////////////////////////// /* The following is the java class I used to represent a grammar rule. In other words the metaparser transforms production rules in the grammar into objects of this class: */ class Grule // grammar rule such as E -> E:a + E:b { Gsym lhs; // left-hand side non-terminal ArrayList rhs = new ArrayList(); // right-hand side of rule String action = "return null;\n}"; // default action closes delegate String operator = null; // used for operator precedence Ruleaction act; // delegate to be generated differently for each grammar } // "delegate" interface that represents production rule interface Ruleaction { Object compval(); // compute value for nonterminal to be pushed } ////////////////////////////////////////////////////////////////////////////// /* After the metaparser parses the grammar file, it then generated the following Java program: */ public class calcparser extends absparser { public void setactions() { int ri = 0; Grule candidate = null; candidate = Rules.get(ri++); candidate.act = new Ruleaction() { public Object compval() { int si = Stack.size()-1; Gsym stackele=null; stackele = Stack.remove(si--); Integer x = (Integer) stackele.value; return new intexp(x); } }; candidate = Rules.get(ri++); candidate.act = new Ruleaction() { public Object compval() { int si = Stack.size()-1; Gsym stackele=null; stackele = Stack.remove(si--); Expr e2 = (Expr) stackele.value; stackele = Stack.remove(si--); stackele = Stack.remove(si--); Expr e1 = (Expr) stackele.value; return new sumexp(e1,e2); } }; candidate = Rules.get(ri++); candidate.act = new Ruleaction() { public Object compval() { int si = Stack.size()-1; Gsym stackele=null; stackele = Stack.remove(si--); Expr e2 = (Expr) stackele.value; stackele = Stack.remove(si--); stackele = Stack.remove(si--); Expr e1 = (Expr) stackele.value; return new multexp(e1,e2); } }; /* ... similar clauses skipped ... */ } // setactions } // parser class /* The generated code instantiates the delegate act of each rule with the appropriate code to create the corresponding abstract syntax structure. The code generated is very minimal, but there must be some code generated for each different grammar. The parts of code that all parsers have in common are placed in the code for the abstract class absparser that this class (calcparser) extends. The type parameter Expr must match the type of object returned by the semantic action associated with the "topsym" symbol (the initial non-terminal of the grammar). This arrangement allowed me to code up a parser generator easily, but it's not the most effective or efficient. In fact, each time that the calculator program runs, the meta-parser must re-read the grammar file so it can form the appropriate representation of each rule (as well as operator precedence and associativity.) */ ////////////////////////////////////////////////////////////////////////////// /* This is the front end of the calculator program: */ import java.io.*; import java.util.*; public class calculator { public static void main(String[] argv) throws Exception { ArrayList S = new ArrayList(); // list of tokens /* // hand-coded example (3+4)*2 S.add(new Gsym("(")); S.add(new Gsym("num",new Integer(3))); S.add(new Gsym("+")); S.add(new Gsym("num",new Integer(4))); S.add(new Gsym(")")); S.add(new Gsym("*")); S.add(new Gsym("num",2)); S.add(new Gsym("EOF")); */ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.print("Enter expression: "); String instring = br.readLine(); calclexer lexer = new calclexer(new StringReader(instring)); Gsym token = lexer.yylex(); while (token !=null) { S.add(token); if (token.sym.equals("EOF")) token = null; else token = lexer.yylex(); }// scan all tokens into arraylist all at once. calcparser parser = new calcparser(S); if (argv.length>0 && argv[0].equals("renew")) metaparser.genparser("calc"); if (argv.length>0 && argv[0].equals("trace")) parser.trace=true; Expr etree = parser.parse(); System.out.println("Value == "+etree.eval()); } }