Trying to understand parsers

I'm trying to use JavaCC to build a simple command line calculator that can handle a variety of expressions. While there are plenty of tutorials out there on how to write grammars, none that I've seen so far explain what happens afterwards.

What I understand right now is that after a string is passed into the parser, it's split into a tokens and turned into a parse tree. What happens next? Do I traverse through the pars开发者_C百科e tree doing a bunch of if-else string comparisons on the contents of each node and then perform the appropriate function?

I highly suggest you watch Scott Stanchfield's ANTLR 3.x tutorials. Even if you don't end up using ANTLR, which may be overkill for your project but I doubt it, you will learn a lot by watching him go through the thought process.

In general the process is...

1. Build a lexer to understand your tokens
2. Build a parser that can validate and understand and organize the input into an abstract syntax tree (AST) which should represent a simplified/easy-to-work-with version of your syntax
3. Run any calculation based on the AST

You need to actually compile or interpret it according to what you need..

For a calculator you just need to visit the tree recursively and evaluate the parsed tree while with a more complex language you would have to translate it to an intermediate language which is assembly-like but keeps abstraction from the underlying architecture.

Of course you could develop your own simple VM that is able to execute a set of instruction in which your language compiles but it would be overkill in your case.. just visit the parse tree. Something like:

enum Operation {
  PLUS, MINUS
}

interface TreeNode {
  float eval();
}

class TreeFloat implements TreeNode {
  float val;
  float eval() { return val; }
}

class TreeBinaryOp implements TreeNode {
  TreeNode first;
  TreeNode second;
  Operation op;

  float eval() {
    if (op == PLUS)
      return first.eval()+second.eval();
}

Then you just call the eval function on the root of the tree. A semantic checking could be needed (with the construction of a symbol table too if you plan to have variables or whatever).

Do I traverse through the parse tree doing a bunch of if-else string comparisons on the contents of each node and then perform the appropriate function?

No, there's no need to build a parse tree to implement a calculator. In the parts of the code where you would create a new node object, just do the calculations and return a number.

JavaCC allows you to choose any return type for a production, so just have your's return numbers.

Some parser generators (such as YACC) let you put actions within the grammar so when you apply a certain production you can also apply a defined action during that production.

E.g. in YACC:

E: NUM + NUM     {$$ = $1.value + $2.value};

would add the values of NUM and return the result to the E non-terminal.

Not sure what JavaCC lets you do.