HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Unambiguity of Reverse Polish Notation

Submitted by: @import:stackexchange-cs··
0
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?

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

Context

StackExchange Computer Science Q#3458, answer score: 3

Revisions (0)

No revisions yet.