Lets say I have given following grammar which generates arithmetic expressions in reverse polish notation:

$P={ E \rightarrow EE+ | EE* | a }$

I know this grammar is unambiguous.

What I do not understand is how I can prove this.

I already searched a lot to in google, etc. but everyone only says, that reverse polish notation are unambiguous, but not WHY.

Can you give me any hints?


1 Answer 1


To show that a grammar is unambiguous, it is enough to show that for any expression E, there is only one "last step" possible in any derivation of E. It is the case here : the last rule is given by the last symbol of the expression (either +, *, or a terminal a), and the parentheses will prevent any ambiguity. Of course you can not write "$abc+$" in your grammar, it has to be $(ab)c+$ or $a(bc)+$, but this is implicit when you define a grammar.

For instance, $a(bc+)*(bc)*+$ is not ambiguous : the last rule is given by the last symbol +, and so on... the expression it represents is $(a*(b+c))+(b*c)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.