Is grammar that describes an equation in prefix (Polish) notation always unambiguous?

Question

I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \, 5 \, * \, 4 \, 3$ using the following grammar and rightmost derivation:

$$Expr \rightarrow + \, Expr \, Expr \, | \, * \, Expr \, Expr \, | \, 0 \, | \, \dots \, | \, 9 \,$$

While I have no trouble taking the derivation and creating its parse tree, the question also asks whether the grammar is ambiguous. In the scope of what I've been taught, my only tool for proving ambiguity has been to find a different parse tree for whatever leftmost or rightmost derivation I have, thus proving multiple valid parses and ambiguity. However, I have not been told how to prove unambiguity. I am fairly confident that the grammar described above is unambiguous based partially on intuition, and partially because it's designed for prefix notation. I tried to generate new trees for a given string to prove ambiguity, but since the operator is always leftmost, I could not find any string in which multiple parse trees could be created. If I am mistaken, please let me know.

My question is this: Is it possible for grammar that describes strings using prefix (Polish) notation such as the one above to ever be ambiguous? My intuition tells me that it will always be unambiguous, but I was wondering why this might be the case.

Answer 1

Your question is easy to answer. Take your grammar, and add the following rules: $$ \begin{align*} &S \to T \mid \mathit{Expr} \\ &T \to \mathit{Expr} \end{align*} $$

Your particular grammar, however, does seem unambiguous.

Here is how I would try to prove it. First, show the expressions are self-delimiting: no expression is a prefix of another one.

Now, when trying to parse an expression, you can determine which rule should be applied first by looking at the first symbol. In the interesting cases, you then have to partition the input into two expressions. The self-delimiting property should make this possible in a unique way.