Parse Trees

A parse tree for a grammar G is a tree where

the root is the start symbol for G
the interior nodes are the nonterminals of G
the leaf nodes are the terminal symbols of G.
the children of a node T (from left to right) correspond to the symbols on the right hand side of some production for T in G.

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:

<E> --> <D>
<E> --> ( <E> )
<E> --> <E> + <E>
<E> --> <E> - <E>
<E> --> <E> * <E>
<E> --> <E> / <E>
<D> --> 0 | 1 | 2 | ... 9

The parse tree is:

      E --> E --> N --> 1
  	  +
  	  E --> E --> N --> 2
  		*
  		E --> N --> 3

Ambiguous Grammars

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

The Problem of Ambiguous Grammars

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.

Ambiguous Precedence

Recall the grammar for expressions given earlier:

<E> --> number
<E> --> ( <E> )
<E> --> <E> + <E>
<E> --> <E> - <E>
<E> --> <E> * <E>
<E> --> <E> / <E>

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.

Ambiguous Associativity

Consider again the same grammar for expressions:

<E> --> number
<E> --> ( <E> )
<E> --> <E> + <E>
<E> --> <E> - <E>
<E> --> <E> * <E>
<E> --> <E> / <E>

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

An Unambiguous Grammar for Expressions

It is possible to write a grammar for arithmetic expressions that

is unambiguous
enforces the precedence of * and / over + and -
enforces left associativity

Here is one such grammar:

<E> --> <E> + <T> | <E> - <T> | <T>
<T> --> <T> * <F> | <T> / <F> | <F>
<F> --> ( <E> ) | number

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 --> number

This 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:

<E> --> <T> + <E> | <T> - <E> | <T>
<T> --> <F> * <T> | <F> / <T> | <F>
<F> --> ( <E> ) | number

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.