[Overview] [Previous] [Next]

Leftmost and Rightmost Derivations

Now consider the grammar

G = ({S, A, B, C}, {a, b, c}, S, P)
where
P = {Sgoes toABC, Agoes toaA, Agoes toempty string, Bgoes tobB, Bgoes toempty string, Cgoes tocC, Cgoes toempty string}.

With this grammar, there is a choice of variables to expand. Here is a sample derivation:

S directly derives ABC directly derives aABC directly derives aABcC directly derives aBcC directly derives abBcC directly derives abBc directly derives abbBc directly derives abbc

If we always expanded the leftmost variable first, we would have a leftmost derivation:

S directly derives ABC directly derives aABC directly derives aBC directly derives abBC directly derives abbBC directly derives abbC directly derives abbcC directly derives abbc

Conversely, if we always expanded the rightmost variable first, we would have a rightmost derivation:

S directly derives ABC directly derives ABcC directly derives ABc directly derives AbBc directly derives AbbBc directly derives Abbc directly derives aAbbc directly derives abbc

There are two things to notice here:

  1. Different derivations result in quite different sentential forms, but
  2. For a context-free grammar, it really doesn't make much difference in what order we expand the variables.
Copyright © 1996 by David Matuszek
Last modified Feb 26, 1996