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 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.