Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 313

Derivation Trees of Context-Free Grammars

Consider a context-free (Type 2) grammarG. Any derivation of a wordwinL(G)can be represented
graphically by means of an ordered, rooted treeT, called aderivation treeorparse tree. We illustrate such a
derivation tree below.
LetGbe the context-free grammar with the following productions:

S→aAB, A→Bba, B→bB, B→c

The wordw=acbabccan be derived fromSas follows:

S⇒aAB⇒a(Bba)B⇒acbaB⇒acba(bB)⇒acbabc

One can draw a derivation treeTof the wordwas indicated by Fig. 12-6. Specifically, we begin withSas the

root and then add branches to the tree according to the production used in the derivation ofw. This yields the

completed treeTwhich is shown in Fig. 12-6(e). The sequence of leaves from left to right inTis the derived

wordw. Also, any non-leaf inTis a variable, sayA, and the immediate successors (children) ofAform a word

αwhereA→αis the production ofGused in the derivation ofw.

Fig. 12-6

Backus-Naur Form

There is another notation, called the Backus-Naur form, which is sometimes used for describing the produc-
tions of a context-free (Type 2) grammar. Specifically:

(i) “::=” is used instead of “→.”

(ii) Every nonterminal is enclosed in brackets〈〉.

(iii) All productions with the same nonterminal left-hand side are combined into one statement with all the

right-hand sides listed on the right of ::=separated by vertical bars.

For instance, the productionsA→aB,A→b,A→BCare combined into the one statement:

〈A〉:: =a〈B〉|b|〈B〉〈C〉