5.4 Derivations

A step of a derivation, or derivation step, is a change made to a symbol string by applying one of the rules from the grammar. The rule must be one of those with a LHS that occurs in the symbol string. The result of the derivation step is another symbol string, one in which an occurrence of the LHS symbol from the rule is replaced by the RHS of the rule. For example, if A, B, C, D, and X are symbols, and

    X ::= B C

is a rule, then

    A X D -> A B C D

is a derivation step,

• with “A X D” as its beginning,
• “A B C D” as its end or result, and
• X ::= B C as its rule.

A derivation is a sequence of derivation steps. The length of a derivation is its length in steps.

• A string X derives a string Y iff there is a derivation of zero or more steps which begins with the string X and ends in the string Y. In the example above (see derivation-example), we say that the symbol string “A X D” derives the symbol string “A B C D” in one step.
• We say that a first symbol string directly derives a second symbol string iff there is a derivation of length 1 from the first symbol string to the second symbol string. In the example above (see derivation-example), we say that the symbol string “A X D” directly derives the symbol string “A B C D”.
• Every symbol string is said to derive itself in a derivation of length 0. A zero length derivation is a trivial derivation.
• A derivation which is not trivial (that is, a derivation which has one or more steps) is a non-trivial derivation.
• If a derivation is not trivial or direct, that is, if it has more than one step, then it is an indirect derivation.

Pedantically, a symbol X and a string that consists of only that symbol are two different things. But we often say “the symbol X”, or “X”, as shorthand for “the string of length 1 whose only symbol is X”. For example, if the string containing only the symbol X derives a string Y, we will usually say simply that “X derives Y”.

Wherever symbol or string X derives Y, we may also say X produces Y. Derivations are often described as symbol matches. Wherever symbol or string X derives Y, we may also say that Y matches X or that X matches Y. It is particularly common to say that X matches Y when Y is a sentence.

The parse of an input by a grammar is successful iff, according to the grammar, the start symbol produces the input sentence. The set of all input sentences that a grammar will successfully parse is the language of the grammar.