patternMinor
Unambiguity of Reverse Polish Notation
Viewed 0 times
unambiguitynotationpolishreverse
Problem
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?
$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?
Solution
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))+(bc)$
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))+(bc)$
Context
StackExchange Computer Science Q#3458, answer score: 3
Revisions (0)
No revisions yet.