Make a calculator's grammar that make a binary

问题:

I need to make a simple calculator (with infix operator) parser that handle the operators +,-,*,/ and float and variable. To make this I used javacc, and I have made this grammar with jjtree. It works but it doesn't ensure that the final tree will be a binary tree, which I need. I want something like 5*3+x-y to generate the following tree :

  *
 / \
5   +
   / \
  3   -
     / \
    x   y

What would be a proper grammar to do that, that would not be left-recursive ?

回答1:

Something like the following will give you the tree you asked for.

void sum():
{}
{
    term()
    [    plus() sum()
    |    minus() sum()
    |    times() sum()
    |    divide() sum()
    |    modulo() sum()
    ]
}


void term() :
{}
{
    "(" sum() ")" | Number() | Variable()
}

---Edit:---

To get a tree that reflects precedence and associativity, you can use definite nodes. See the JJTree documentation.

void sum() #void {} :
{
    term()
    (   plus() term() #BinOp(3)
    |   minus() term() #BinOp(3)
    )*
}

void term() #void {} :
{
    factor()
    (   times() factor() #BinOp(3)
    |   divide() factor() #BinOp(3)
    |   modulo() factor() #BinOp(3)
    )*
}

void factor() #void :
{}
{
    "(" sum() ")" | Number() | Variable()
}