Context-free grammar: Encyclopedia II - Context-free grammar - Derivations and syntax trees

Context-free grammar - Derivations and syntax trees

There are basically two ways to describe how in a certain grammar a string can be derived from the start symbol. The simplest way is to list the consecutive strings of symbols, beginning with the start symbol and ending with the string, and the rules that have been applied. If we introduce a strategy such as "always replace the left-most nonterminal first" then for context-free grammars the list of applied grammar rules is by itself sufficient. This is called the leftmost derivation of a string. For example, if we take the following grammar:

and the string "1 + 1 + 1" then the left derivation of this string is the list [ (1), (1), (2), (2), (2) ]. Analogously the rightmost derivation is defined as the list that we get if we always replace the rightmost nonterminal first. In this case this would be the list [ (1), (2), (1), (2), (2)].

The distinction between leftmost derivation and rightmost derivation is important because in most parsers the transformation of the input is defined by giving a piece of code for every grammar rule that is executed whenever the rule is applied. Therefore it is important to know whether the parser determines a leftmost or a rightmost derivation because this determines the order in which the pieces of code will be executed. See for an example LL parsers and LR parsers.

A derivation also imposes in some sense a hierarchical structure on the string that is derived. For example the structure of the string "1 + 1 + 1" would, according to the leftmost derivation, be:

where { ... }_S indicates a substring recognized as belonging to S. This hierarchy can also be seen as a tree:

           S
          /|\
         / | \
        /  |  \
       S  '+'  S
      /|\      |
     / | \     |
    S '+' S   '1'
    |     |
   '1'   '1'

This tree is called a concrete syntax tree (see also abstract syntax tree) of the string. In this case the presented leftmost and the rightmost derivation define the same syntax tree, however there is another (leftmost) derivation of the same string possible

and this defines the following syntax tree:

           S 
          /|\
         / | \
        /  |  \
       S  '+'  S
       |      /|\
       |     / | \
      '1'   S '+' S
            |     |
           '1'   '1'

If for certain strings in the language of the grammar there is more than one parsing tree then the grammar is said to be an ambiguous grammar. Such grammars are usually hard to parse because the parser cannot always decide which grammar rule it has to apply.

Adapted from the Wikipedia article "Derivations and syntax trees", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki