1
$\begingroup$

mexp ::= (< mexp >) | < mexp >< mathlowop >< mexp > | < mulexp > | < float > | < var >

mulexp ::= < mexp >< mathhighop >< mexp >

mathlowop ::= + | -

mathhighop ::= / | *

That's the BNF I've come up with for parsing simple mathematical expressions where the operands can only be floats or variables. I've looked at a number of resources in books and on the web and for the same type of problem, they usually have a slightly longer, more complex bnf. Is my BNF incorrect in some way? Or is it correct but there is a significant advantage in doing it another way?

$\endgroup$
  • 2
    $\begingroup$ It would help if you could give a particular grammar whose differences you don't get. As it is, it's impossible to give you a good answer; one can imagine many features a grammar might have. (Also, see here for a related question.) $\endgroup$ – Raphael Apr 13 '14 at 15:50
  • 1
    $\begingroup$ Here Unambiguous grammar for exponentiation operation explain a similar grammar, also explained how can you correctly convert it into unambiguous/ambiguous form. $\endgroup$ – Grijesh Chauhan Apr 13 '14 at 17:55
  • $\begingroup$ What have you done to try to validate your grammar? Can you frame a more general question that is more likely to be useful to others? The purpose of this site is to build up an archive of high-quality questions and answers that will likely be useful to others. Right now, this question is very specific and unlikely to be helpful to others. We are not a place to outsource debugging or testing tasks. And, questions where a possible answer is "yes, it's correct" tend not to be a good fit for our format. $\endgroup$ – D.W. Apr 15 '14 at 18:26
7
$\begingroup$

Your grammar will generate mathematical expressions, but you haven't captured the notion of operator precedence. For instance, there are two different ways your grammar can generate the expression $a+a*a$, one having the interpretation we'd write as $a+[a*a]$ and the other having $[a+a]*a$. Using the jargon, we'd say your grammar is ambiguous.

A grammar that avoids this problem is

< expression > ::= < term > + < expression > | < term > - < expression > | < term >

< term > ::= < factor > * < term > | < factor > / < term > | < factor >

< factor > ::= (< expression >) | < float > | < var >

See if you can generate $a+a*a$ in two different ways using your grammar and then try the same thing with this grammar. That should give you an idea of what's going on here.

$\endgroup$
  • 1
    $\begingroup$ Do note that this grammar does not handle the unary minus $\endgroup$ – Alex Oct 9 '18 at 23:48
  • $\begingroup$ How could it be done to handle it too? would this work? < term > ::= < factor > * < term > | < factor > / < term > | - < factor > | < factor > $\endgroup$ – Falk Aug 22 '19 at 11:22
1
$\begingroup$

If you are looking for a grammar, then yours is correct. If you are going to implement a parser, you might want to tweak your grammar a bit. It depends on the tools you are going to use.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.