A parse tree for a grammar G is a tree where
Every terminal string generated by a grammar has a corresponding parse tree; every valid parse tree represents a string generated by the grammar (called the yield of the parse tree).
Example: Given the following grammar, find a parse tree for the string 1 + 2 * 3:
The parse tree is:
E --> E --> N --> 1 + E --> E --> N --> 2 * E --> N --> 3
A grammar for which there are two different parse trees for the same terminal string is said to be ambiguous.
The grammar for balanced parentheses given earlier is an example of an ambiguous grammar:
P --> ( P ) | P P | epsilon
We can prove this grammar is ambiguous by demonstrating two parse trees for the same terminal string.
Here are two parse trees for the empty string:
P --> P --> epsilon P --> epsilon P --> epsilon
Here are two parse trees for ():
P --> P --> ( P --> epsilon ) P --> epsilon P --> P --> epsilon P --> ( P --> epsilon )
While in general it may be difficult to prove a grammar is ambiguous, the demonstration of two distinct parse trees for the same terminal string is sufficient proof that a grammar is ambiguous.
An unambiguous grammar for the same language (that is, the set of strings consisting of balanced parentheses) is:
P --> ( P ) P | epsilon
A parse tree is supposed to display the structure used by a grammar to generate an input string. This structure is not unique if the grammar is ambiguous. A problem arises if we attempt to impart meaning to an input string using a parse tree; if the parse tree is not unique, then the string has multiple meanings.
We typically use a grammar to define the syntax of a programming language. The structure of the parse tree produced by the grammar imparts some meaning on the strings of the language.
If the grammar is ambiguous, the compiler has no way to determine which of two meanings to use. Thus, the code produced by the compiler is not fully determined by the program input to the compiler.
Recall the grammar for expressions given earlier:
This grammar is ambiguous as shown by the two parse trees for the input string number + number * number:
E --> E --> number + E --> E --> number * E --> number E --> E --> E --> number + E --> number * E --> number
The first parse tree gives precedence to multiplication over addition; the second parse tree gives precedence to addition over multiplication. In most programming languages, only the former meaning is correct. As written, this grammar is ambiguous with respect to the precedence of the arithmetic operators.
Consider again the same grammar for expressions:
This grammar is ambiguous even if we only consider operators at the same precedence level, as in the input string number - number + number:
E --> E --> number - E --> E --> number + E --> number E --> E --> E --> number - E --> number + E --> number
The first parse tree (incorrectly) gives precedence to the addition operator; the second parse tree gives precedence to the subtraction operator. Since we normally group operators left to right within a precedence level, only the latter interpretation is correct.
Important note: computer arithmetic is not associative! Because of overflow, it may not be the case that (a+b)+c gives the same result as a+(b+c).
It is possible to write a grammar for arithmetic expressions that
If we attempt to build a parse tree for number - number + number, we see there is only one such tree:
E --> E --> E --> T --> F --> number - T --> F --> number + T --> numberThis parse tree correctly represents left associativity by using recursion on the left. If we rewrote the grammar to use recursion on the right, we would represent right associativity:
Our grammar also correctly represents precedence levels by introducing a new non-terminal symbol for each precedence level. According to our grammar, expressions consist of the sum or difference of terms (or a single terms), where a term consists of the product or division of factors (or a single factor), and a factor is a nested expression or a number.