Operator precedence with LR(0) parser

Question

A typical BNF defining arithmetic operations:

E :- E + T
  |  T
T :- T * F
  |  F
F :- ( E )
  | number

Is there any way to re-write this grammar so it could be implemented with an LR(0) parser, while still retaining the precedence and left-associativity of the operators? I'm thinking it should be possible by introducing some sort of disambiguation non-terminals, but I can't figure out how to do it.

Thanks!

Answer 1

A language can only have an LR(0) grammar if it's prefix-free, meaning that no string in the language is a prefix of another. In this case, the language you're describing isn't prefix-free. For example, the string number + number is a prefix of number + number + number.

A common workaround to address this would be to "endmark" your language by requiring all strings generated to end in a special "done" character. For example, you could require that all strings generated end in a semicolon. If you do that, you can build an LR(0) parser for the language with this grammar:

S → E;

E → E + T | T

T → T * F | F

F → number | (E)