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?


migrated from cstheory.stackexchange.com Sep 7 '12 at 5:27

This question came from our site for theoretical computer scientists and researchers in related fields.


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, privacy policy and cookie policy

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