Context-Free Grammars #

Derivations #

Beginning with the start symbol, each production rule rewrites a nonterminal by its right hand side. For example

(1)

The replacement of a single by is written as

and is read as " derives ".The symbol means deriving in one step.

We can take a single and repeatedly apply productions in any order to get a sequence of replacements. For example

When a sequence of derivation steps rewrites to , we denote it as , meaning deriving in zero or more steps. Likewise, the symbol means deriving in one or more steps.

To understand how parsers work, we shall consider derivations in which the nonterminal to be replaced at each step is chosen as follows:

1. leftmost derivations: the leftmost nonterminal in each sentential is always chosen. We use the symbol to denote a leftmost derivation
2. rightmost derivations: the rightmost nonterminal in each sentential is always chosen. We use the symbol to denote a rightmost derivation

For example, (notice the leftmost nonterminal is always replaced before others)

Ambiguity #

An ambiguous grammar is one that produces more than one leftmost derivation or more than one rightmost derivation for the same sentence. For example, the arithmetic expression grammar (1) permits two distinct leftmost derivations for the sentence

However, we would normally evaluate an expression like as , rather than as .