0

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 ?

Maeln
  • 370
  • 1
  • 21

1 Answers1

0

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()
}
Theodore Norvell
  • 15,366
  • 6
  • 31
  • 45
  • But would it preserve operator precedence, has I'm parsing equation in infix notation ? – Maeln Nov 11 '14 at 12:28
  • No, it doesn't respect operator precedence. Nor does it get the associativity right. This is deliberate. If you look at the example tree in the original post, you will see that it also doesn't respect operator precedence and it doesn't get the associativity of + and - right. See edit. – Theodore Norvell Nov 11 '14 at 13:25
  • Oops, my bad, I've quickly done the example, it should respect operator precedence, my bad. I'm trying [this](http://stackoverflow.com/a/7867104/1149206), it's not has formal has using a grammar but it works pretty well for what I'm trying to achieve. Anyway thanks for your answer ! – Maeln Nov 11 '14 at 13:39
  • Well see the edit, JJTree was designed to let you build the tree you want. – Theodore Norvell Nov 11 '14 at 13:43