[Solved]: Unambiguity of Reverse Polish Notation

Problem Detail: 

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

$G=({E},{a,+,*},P,E)$
$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?

Asked By : xaedes

Answered By : Denis

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)$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3458