5.9 An example tree

     < < "S", 0, 7 >, [
         < < "A", 0, 2 >, [
             < < "T", 0, 1 >, [ ] >,
             < < "U", 1, 2 >, [ ] >
         ] >,
         < < "B", 2, 2 >, [ ] >,
         < < "C", 2, 3 >, [
             < < "V", 2, 3 >, [ ] >
         ] >,
         < < "D", 3, 5 >, [
             < < "W", 3, 4 >, [ ] >,
             < < "X", 4, 5 >, [ ] >
         ] >,
         < < "E", 5, 7 >, [
             < < "Y", 5, 6 >, [ ] >,
             < < "Z", 6, 7 >, [ ] >
         ] >
      ] >

In the tree above, we use symbol names (for example, "S") as symbol IDs. Since we have not used the same symbol twice, we will be able to refer to a node by its symbol name. In practical parse trees, symbols usually occur many times.

Node S has 5 children. Node A has 2 children. Node B has no children and is a nulled node. Nodes T, U, V, W, X, Y, and Z are terminal nodes. Nodes S, A, C, D, and E are BNF rule nodes. The tree implies a grammar with at least the following rules:

    S ::= A B C D E
    A ::= T U
    B ::=
    C ::= V
    D ::= W X
    E ::= Y Z

The tree derives the sentence

      T U V W X Y X

and can do so in several ways. One is these is its rightmost derviation:

    S -> A B C D E
      -> A B C D Y Z
      -> A B C W X Y Z
      -> A B V W X Y Z
      -> A V W X Y Z
      -> T U V W X Y Z

This is called the rightmost derviation because, at each derivation step, the symbol that is expanded is the rightmost symbol possible. There is also a leftmost derivation:

    S -> A B C D E
      -> T U B C D E
      -> T U C D E
      -> T U V D E
      -> T U V W X E
      -> T U V W X Y Z