Ambiguous Context-Free Grammar

languages

Definition

Ambiguous Context-Free Grammar

A context-free grammar is called ambiguous if it is not unambiguous.

Examples

If-then-else grammar

Consider the context-free grammar

$$G_1=(\{Anw\},\{if,then,else,expr,others\},P_1,Anw)$$

where $P_1$ contains the following production rules:

$$Anw\to \text{if}\text{expr}\text{then}Anw\mid \text{if}\text{expr}\text{then}Anw\text{else}Anw\mid \text{others}$$

The grammar is ambiguous, because the word

$$\text{if}\text{expr}\text{then}\text{if}\text{expr}\text{then}\text{others}\text{else}\text{others}$$

has two different leftmost derivations.