1.1. Example Grammar 2¶

Let's try to parse the expression \(A+B*C\) using this grammar. The grammar offers us a lot of options for how to start the parse. We could choose to first use the production with the \(+\) operator, as is done in the following slide-show.

Settings

Saving...
Server Error
Resubmit

Or we could also start with the production having the \(*\) operator, in which case the parse proceeds as shown in the following slide-show.

Settings

Saving...
Server Error
Resubmit

Note that both of the slide-shows above produce valid parse trees for this grammar. The problem, however, is that the two parse trees are different. In the first of the two parse trees, B would multiply C, which would correspond to usual operator precedence. However, in the parse tree produced by the second slide-show, B would be added to A, a result that is contrary to usual operator precedence. A grammar such as this, which allows two different parse trees for the same expression, is called an ambiguous grammar. Ambiguous grammars should always be avoided. Although they allow you to determine the syntactic correctness of an expression, the variety of parse trees they allow confounds our ability to use the parse trees for any type of reliable semantic action.

The review problem set for this module contains four review problems, the first three of which refer to the same grammar. The first problem is about determining how many parse trees a given string has in a given grammar.