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