[Alphabetical Index | Tag Index]

Derivation

A sequence of production rule applications that rewrites the start symbol into the input string (i.e., by replacing a nonterminal symbol by its expansion at each step). This can be seen as a trace of a parser's actions or as a proof that the string belongs to the language.

Leftmost

A derivation where the leftmost nonterminal symbol is selected at every rewrite step.

Rightmost

A derivation where the rightmost nonterminal symbol is selected at every rewrite step.