1.2. Ambiguous Grammars¶
1.2.1. Second Sample Grammar¶
In First Sample Grammar in the previous section, we developed a grammar for algebraic expressions that involved three non-terminals, namely \(<exp>, <term>\), and \(<var>\). Is it possible to develop a simpler grammar for the same language, for example, a grammar with fewer non-terminals? Here is one candidate grammar using only two non-terminals \(<exp>\) and \(<var>\).
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 parsing process. We could choose to first use the production with the \(+\) operator, as is done in the following slide show.
Or we could also start with the production having the \(*\) operator, in which case parsing proceeds as shown in the following slide show.
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 the usual operator precedence. However, in the parse tree produced in the second slide show, B would be added to A, which goes against the usual operator precedence.
1.2.2. Ambiguity in Grammars¶
A grammar that allows for two (or more) different parse trees to be built for the same expression is called an ambiguous grammar. Ambiguous grammars should always be avoided because the multiplicity of parse trees they allow prevents us from using parse trees to associate a unique meaning (or value, or semantics) to the expression that they represent.
The problem set for this section contains four review problems, the first three of which refer to the same grammar.
1.2.3. Ambiguous Grammar - Part 1¶
This first problem is about determining how many parse trees a given string has in a given grammar.
1.2.4. Ambiguous Grammar - Part 2¶
This problem is about determining how many parse trees another string has in the same grammar.
1.2.5. Ambiguous Grammar - Part 3¶
This problem is again about determining how many parse trees yet another string has in the same grammar.
1.2.6. Discovering Ambiguity¶
This problem provides practice discovering ambiguities in grammars as well as convincing yourself that a grammar is not ambiguous.
