Slide 2.7: Derivations

Slide 2.6: Syntax diagrams
Slide 2.8: Parse trees
Home

Context-Free Grammars (Cont.)

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]