Clone wiki

inf225public / glossary / Derivation

[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.

Updated