CODEWITHSUNDEEP
parsinggrammarbnfebnfassociativity
fredoverflow
fredoverflow

Reputation: 263128

BNF grammar for left-associative operators

I have the following EBNF grammar for simple arithmetic expressions with left-associative operators:

expression:
    term {+ term}
    
term:
    factor {* factor}
    
factor:
    number
    ( expression )

How can I convert this into a BNF grammar without changing the operator associativity? The following BNF grammar does not work for me, because now the operators have become right-associative:

expression:
    term
    term + expression
    
term:
    factor
    factor * term
    
factor:
    number
    ( expression )

Wikipedia says:

Several solutions are:

  1. rewrite the grammar to be left recursive, or
  2. rewrite the grammar with more nonterminals to force the correct precedence/associativity, or
  3. if using YACC or Bison, there are operator declarations, %left, %right and %nonassoc, which tell the parser generator which associativity to force.

But it does not say how to rewrite the grammar, and I don't use any parsing tools like YACC or Bison, just simple recursive descent. Is what I'm asking for even possible?

Upvotes: 7

Views: 5251

Answers (2)

Branco Medeiros
Branco Medeiros

Reputation: 759

What Puppy suggests can also be expressed by the following grammar:

expression: term opt_add
opt_add: '+' term opt_add
       | /* empty */

term:  factor opt_mul
opt_mul: '*' factor opt_mul
       | /* emtpty */

factor: number
      | '(' expression ')

Upvotes: 1

Puppy
Puppy

Reputation: 146930

expression
    : term 
    | expression + term;

Just that simple. You will, of course, need an LR parser of some description to recognize a left-recursive grammar. Or, if recursive descent, recognizing such grammars is possible, but not as simple as right-associative ones. You must roll a small recursive ascent parser to match such.

Expression ParseExpr() {
    Expression term = ParseTerm();
    while(next_token_is_plus()) {
        consume_token();
        Term next = ParseTerm();
        term = PlusExpression(term, next);
    }
    return term;
}

This pseudocode should recognize a left-recursive grammar in that style.

Upvotes: 10

Related Questions