Editing Context-free grammar (section)

== Derivations and syntax trees ==
<!-- This section is linked from [[LR parser]] -->

A ''derivation'' of a string for a grammar is a sequence of grammar rule applications that transform the start symbol into the string.
A derivation proves that the string belongs to the grammar's language.

A derivation is fully determined by giving, for each step:
* the rule applied in that step
* the occurrence of its left-hand side to which it is applied
For clarity, the intermediate string is usually given as well.

For instance, with the grammar:
# {{math|''S'' → ''S'' + ''S''}}
# {{math|''S'' → 1}}
# {{math|''S'' → a}}
the string
: {{math|1 + 1 + a}}
can be derived from the start symbol {{math|''S''}} with the following derivation:
: {{math|''S''}}
: {{math|→ ''S'' + ''S''}} (by rule 1. on {{math|''S''}})
: {{math|→ ''S'' + ''S'' + ''S''}} (by rule 1. on the second {{math|''S''}})
: {{math|→ 1 + ''S'' + ''S''}} (by rule 2. on the first {{math|''S''}})
: {{math|→ 1 + 1 + ''S''}} (by rule 2. on the second {{math|''S''}})
: {{math|→ 1 + 1 + a}} (by rule 3. on the third {{math|''S''}})

Often, a strategy is followed that deterministically chooses the next nonterminal to rewrite:
* in a ''leftmost derivation'', it is always the leftmost nonterminal;
* in a ''rightmost derivation'', it is always the rightmost nonterminal.

Given such a strategy, a derivation is completely determined by the sequence of rules applied. For instance, one leftmost derivation of the same string is
: {{math|''S''}}
: {{math|→ ''S'' + ''S''}} (by rule 1 on the leftmost {{math|''S''}})
: {{math|→ 1 + ''S''}} (by rule 2 on the leftmost {{math|''S''}})
: {{math|→ 1 + ''S'' + ''S''}} (by rule 1 on the leftmost {{math|''S''}})
: {{math|→ 1 + 1 + ''S''}} (by rule 2 on the leftmost {{math|''S''}})
: {{math|→ 1 + 1 + a}} (by rule 3 on the leftmost {{math|''S''}}),
which can be summarized as
: rule 1
: rule 2
: rule 1
: rule 2
: rule 3.

One rightmost derivation is:
: {{math|''S''}}
: {{math|→ ''S'' + ''S''}} (by rule 1 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + ''S'' + ''S''}} (by rule 1 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + ''S'' + a}} (by rule 3 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + 1 + a}} (by rule 2 on the rightmost {{math|''S''}})
: {{math|→ 1 + 1 + a}} (by rule 2 on the rightmost {{math|''S''}}),
which can be summarized as
: rule 1
: rule 1
: rule 3
: rule 2
: rule 2.

The distinction between leftmost derivation and rightmost derivation is important because in most [[parsing|parser]]s 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 parser]]s and [[LR parser]]s.

A derivation also imposes in some sense a hierarchical structure on the string that is derived. For example, if the string "{{math|1 + 1 + a}}" is derived according to the leftmost derivation outlined above, the structure of the string would be:
: {{math|{{mset|{{mset|1}}<sub>''S''</sub> + {{mset|{{mset|1}}<sub>''S''</sub> + {{mset|a}}<sub>''S''</sub>}}<sub>''S''</sub>}}<sub>''S''</sub>}}
where {{math|{{mset|...}}<sub>''S''</sub>}} denotes a substring recognized as belonging to {{math|''S''}}. This hierarchy can also be seen as a tree:

[[File:Simple Parse Tree 1.svg|x260px|Rightmost derivation of {{math|1 + 1 + a}}]]

This tree is called a ''[[parse tree]]'' or "concrete syntax tree" of the string, by contrast with the [[abstract syntax tree]]. In this case the presented leftmost and the rightmost derivations define the same parse tree; however, there is another rightmost derivation of the same string
: {{math|''S''}}
: {{math|→ ''S'' + ''S''}} (by rule 1 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + a}} (by rule 3 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + ''S'' + a}} (by rule 1 on the rightmost {{math|''S''}})
: {{math|→ ''S'' + 1 + a}} (by rule 2 on the rightmost {{math|''S''}})
: {{math|→ 1 + 1 + a}} (by rule 2 on the rightmost {{math|''S''}}),
which defines a string with a different structure
: {{math|{{mset|{{mset|{{mset|1}}<sub>''S''</sub> + {{mset|1}}<sub>''S''</sub>}}<sub>''S''</sub> + {{mset|a}}<sub>''S''</sub>}}<sub>''S''</sub>}}
and a different parse tree:

[[File:Simple Parse Tree 2.svg|x260px|Leftmost derivation of {{math|1 + 1 + a}}]]

Note however that both parse trees can be obtained by both leftmost and rightmost derivations.  For example, the last tree can be obtained with the leftmost derivation as follows:
: {{math|''S''}}
: {{math|→ ''S'' + ''S''}} (by rule 1 on the leftmost {{math|''S''}})
: {{math|→ ''S'' + ''S'' + ''S''}} (by rule 1 on the leftmost {{math|''S''}})
: {{math|→ 1 + ''S'' + ''S''}} (by rule 2 on the leftmost {{math|''S''}})
: {{math|→ 1 + 1 + ''S''}} (by rule 2 on the leftmost {{math|''S''}})
: {{math|→ 1 + 1 + a}} (by rule 3 on the leftmost {{math|''S''}}),

If a string in the language of the grammar has 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. Usually, ambiguity is a feature of the grammar, not the language, and an unambiguous grammar can be found that generates the same context-free language. However, there are certain languages that can only be generated by ambiguous grammars; such languages are called ''[[inherently ambiguous language]]s''.