Derivation trees

Derivations of strings in context-free languages have an associated tree representation called a derivation tree (or parse tree or syntax tree). The advantage of derivation trees is that they reveal the hierarchical structure of a derivation. The following diagram shows the tree for the string, “The cow annoys the student.” For those who diagrammed sentences in elementary school, this will have a somewhat familiar look.

The rewrite rules are also called production rules, or just productions for short. Consider the following simplistic grammar, which generates random sentences:

Get hands-on with 1400+ tech skills courses.