Editing Ambiguous grammar (section)

== Examples ==

=== Trivial language ===
The simplest example is the following ambiguous grammar (with start symbol A) for the trivial language that consists of only the empty string:
: A → A | ε
... meaning that the nonterminal A can be derived to either itself again, or to the empty string. Thus the empty string has leftmost derivations of length 1, 2, 3, and indeed of any length, depending on how many times the rule A → A is used.

This language also has an unambiguous grammar, consisting of a single [[Production rule (formal languages)|production rule]]:
: A → ε
... meaning that the unique production can produce only the empty string, which is the unique string in the language.

In the same way, any grammar for a non-empty language can be made ambiguous by adding duplicates.

=== Unary string ===
The [[regular language]] of unary strings of a given character, say <code>'a'</code> (the regular expression <code>a*</code>), has the unambiguous grammar:
: A → aA | ε
... but also has the ambiguous grammar:
: A → aA | Aa | ε
These correspond to producing a [[right-associative]] tree (for the unambiguous grammar) or allowing both left- and right- association. This is elaborated below.

=== Addition and subtraction ===
The [[context free grammar]]
: A → A + A | A − A | a
is ambiguous since there are two leftmost derivations for the string a + a + a:

{| border="0"
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; || A || → A + A
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| A || → A + A
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + A
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| || → A + A + A (First A is replaced by A+A. Replacement of the second A would yield a similar derivation.)
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + A + A
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| || → a + A + A
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + a + A
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| || → a + a + A
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + a + a
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| || → a + a + a
|}

As another example, the grammar is ambiguous since there are two [[parse tree]]s for the string a + a &minus; a:
: [[Image:Leftmostderivations jaredwf.svg|Leftmostderivations jaredwf.svg|400px|class=skin-invert]]

The language that it generates, however, is not inherently ambiguous; the following is a non-ambiguous grammar generating the same language:
: A → A + a | A − a | a

=== Dangling else ===
{{main|Dangling else}}
A common example of ambiguity in computer programming languages is the [[dangling else]] problem. In many languages, the <code>else</code> in an [[Conditional (computer programming)#If–then(–else)|If–then(–else)]] statement is optional, which results in nested conditionals having multiple ways of being recognized in terms of the context-free grammar.

Concretely, in many languages one may write conditionals in two valid forms: the if-then form, and the if-then-else form – in effect, making the else clause optional.

In a grammar containing the rules{{efn|The following example uses [[Pascal (programming language)|Pascal]] syntax.}}

 Statement → '''if''' Condition '''then''' Statement |
             '''if''' Condition '''then''' Statement '''else''' Statement |
             ...
 Condition → ...

some ambiguous phrase structures can appear. The expression
 '''if''' a '''then''' '''if''' b '''then''' s '''else''' s2
can be parsed as either
 '''if''' a '''then''' '''begin''' '''if''' b '''then''' s '''end''' '''else''' s2
or as
 '''if''' a '''then''' '''begin''' '''if''' b '''then''' s '''else''' s2 '''end'''
depending on whether the <code>else</code> is associated with the first <code>if</code> or second <code>if</code>.

This is resolved in various ways in different languages. Sometimes the grammar is modified so that it is unambiguous, such as by requiring an <code>endif</code> statement or making <code>else</code> mandatory. In other cases the grammar is left ambiguous, but the ambiguity is resolved by making the overall phrase grammar context-sensitive, such as by associating an <code>else</code> with the nearest <code>if</code>. In this latter case the grammar is unambiguous, but the context-free grammar is ambiguous.{{clarify|reason=There is no such thing as an 'overall phrase grammar'. The 'nearest-if' rule can possibly be implemented by using a slightly modified, but still context-free grammar.|date=January 2017}}

=== An unambiguous grammar with multiple derivations ===
The existence of multiple derivations of the same string does not suffice to indicate that the grammar is ambiguous; only multiple ''leftmost'' derivations (or, equivalently, multiple parse trees) indicate ambiguity.

For example, the simple grammar
 S → A + A
 A → 0 | 1
is an unambiguous grammar for the language { 0+0, 0+1, 1+0, 1+1 }. While each of these four strings has only one leftmost derivation, it has two different derivations, for example
 S [[Context-free grammar#Rule application|⇒]] A + A ⇒ 0 + A ⇒ 0 + 0
and
 S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0
Only the former derivation is a leftmost one.