I know that the grammar

<expr> = <expr> + <expr> | <num>
<num> = 0|1

is ambiguous because it cannot decide between (1+1)+1 or 1+(1+1). However, that would also mean that

<expr> = <expr> + <num> | <expr> * <num> | <num>
<num> = 0 | 1

would also be ambiguous because it couldn't tell if 1+1*1+1 is (1+1)*(1+1) or ((1+1)*1)+1. Or does it distinguish between these by terminating the interpretation as soon as it finds one match?

If it does terminate on a first match, then would 1+1*1+1 necessarily get interpreted as the first option since it is possible to interpret the "main operation" as being +?


You can't match 1+2*3+4 with expr * num because 3+4 isn't a num. The only possible match is expr + num, with 1+2*3 as the expr and 4 as the num. To make 1+2*3 an expr, you need to match it with expr * num, and then you can match 1+2 with expr + num. Finally, you can match 1 with num to make the innermost expr.

So the only possible parse is ((((1)+2)*3)+4) and the grammar is not ambiguous.

It is not the grammar we usually use for algebra because it produces an undesired parse, not because it is ambiguous.


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.