# Does BNF terminate on a first match?

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 +?

## 1 Answer

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.