Precedence of operators in BNF grammar

Question

I'm doing a homework assignment where I am give some BNF grammar:

<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> + <term>
      | <term>
<term> -> <term> * <factor>
      | <factor>
<factor> -> ( <expr> )
      | <id>

and the question is:

"Rewrite this grammar so that the + operator is right associative and takes precedence over the * operator."

A classmate suggested we simply switch the + and * operators and then + will have precedence and gain right association, however I don't think this is correct since the question is recursive.

My question is, does the + operator gain precedence and right association by simply switching it with the * operator? My two thoughts are to remove the recursion and do what my classmate suggests, or put the + operator in a condition where is must be surrounded by ( and ) to work.

Maybe I'm over thinking this?

swapping + and * in the grammar will clearly swap the precedence, but making them right-associative is a seperate step — Mooing Duck
@MooningDuck Let me just take a picture of that so I can say I told you so to my friend... Ok done. So now referring to right-association would I simply be able to make the addition operator recursively in parenthesis and cut out the multiplication at that point? I believe that would be consider right association. Ex. A = B * (C + (C + (C + C))) — Ryan Tibbetts
Associativity is (it seems to me) related to the kind of recursion. As you can see in your example, both expr and term are left-recursive and have left-associativity. Maybe changing the type of recursion used in the production you are interested changes it's associativity also. — Branco Medeiros

Mooing Duck Mooing Duck · Accepted Answer · 2015-02-18T20:15:00

Swapping + and * in the grammar will clearly swap the precedence, but making them right-associative is a separate step, so that's easy.

However, for Right-vs-Left associativity, I'm having trouble understanding your suggestions, but both of them seem wrong.

If we take the sample input A = A + B + C, then your grammar parses it like this:

assign: <id> = <expr>
    id: A
    expr: <expr> + <term>
        expr: <expr> + <term>
            expr: <expr> + <term>
                expr: <term>
                term: <factor>
                    factor: <id>
                         id: A
            term: <factor>
                factor: <id>
                    id: B
        term: <factor>
            factor: <id>
                id: C

Or, if you prefer the same thing in a parenthetical format:

(A) = ((((A))+(B))+(C))

Notice that the innermost and thus first evaluated + is the one farthest to the left. Thus, your grammar has Left associativity. You need to change expr and term so that the first one evaluated is the one farthest to the right for the grammar to have right associativity. Parenthesis provide a way to "overrule" of whatever the associativity the grammar has, but otherwise aren't really related to the associativity.

Precedence of operators in BNF grammar

1 Answers