Derivations
A grammar derives strings by beginning with the start symbol and repeatedly replacing a nonterminal by the body of a production for that nonterminal.
The terminal strings that can be derived from the start symbol form the language of the grammar.
Reconsider the grammar of simple arithmetic expressions:
<exp> ::= <exp> <op> <exp> | ( <exp> ) | number
<op> ::= + | – | *
the following list shows two popular derivations, where the symbol ⇒ denotes the relation encompassing one step of a derivation and the square brackets enclose the production used in that step:
- A leftmost derivation is a derivation in which the leftmost nonterminal is replaced at each step in the derivation.
An example of a leftmost derivation is given as follows:
(1) <exp> ⇒ <exp> <op> <exp> [<exp> ⇒ <exp> <op> <exp>]
(2) ⇒ ( <exp> ) <op> <exp> [<exp> ⇒ ( <exp> )]
(3) ⇒ ( <exp> <op> <exp> ) <op> <exp> [<exp> ⇒ <exp> <op> <exp>]
(4) ⇒ ( number <op> <exp> ) <op> <exp> [<exp> ⇒ number]
(5) ⇒ ( number – <exp> ) <op> <exp> [<op> ⇒ –]
(6) ⇒ ( number – number ) <op> <exp> [<exp> ⇒ number]
(7) ⇒ ( number – number ) * <exp> [<op> ⇒ *]
(8) ⇒ ( number – number ) * number [<exp> ⇒ number]
- A rightmost derivation is a derivation in which the rightmost nonterminal is replaced at each step in the derivation.
An example of a rightmost derivation is given as follows:
(1) <exp> ⇒ <exp> <op> <exp> [<exp> ⇒ <exp> <op> <exp>]
(2) ⇒ <exp> <op> number [<exp> ⇒ number]
(3) ⇒ <exp> * number [<op> ⇒ *]
(4) ⇒ ( <exp> ) * number [<exp> ⇒ ( <exp> )]
(5) ⇒ ( <exp> <op> <exp> ) * number [<exp> ⇒ <exp> <op> <exp>]
(6) ⇒ ( <exp> <op> number ) * number [<exp> ⇒ number]
(7) ⇒ ( <exp> – number ) * number [<op> ⇒ –]
(8) ⇒ ( number – number ) – number [<exp> ⇒ number]