Derivation tree

Derivation tree --- дерево вывода.

Let [math]\displaystyle{ G }[/math] be a CF-grammar and [math]\displaystyle{ x }[/math] be a sentence form in [math]\displaystyle{ G }[/math].

All equivalent derivations of [math]\displaystyle{ x }[/math] can be represented by its derivation tree that is an ordered rooted tree labeled by elements from [math]\displaystyle{ V\bigcup \{e\} }[/math], such that the following properties hold. The root of the tree has a label [math]\displaystyle{ S }[/math], labels of all leaves enumerated according to their ordering forms [math]\displaystyle{ x }[/math] and for any internal node [math]\displaystyle{ q }[/math] of the tree with a list of all sons [math]\displaystyle{ q_1, q_2, \ldots, q_r, }[/math] [math]\displaystyle{ r\geq 0, }[/math] enumerated according to their ordering, there is such a production [math]\displaystyle{ A\rightarrow a_1 a_2 \ldots a_r }[/math] of the grammar that either [math]\displaystyle{ a_1 a_2 \ldots a_r \not = e }[/math] and the nodes [math]\displaystyle{ q, q_1, q_2, }[/math] [math]\displaystyle{ \ldots, q_r }[/math] have labels [math]\displaystyle{ A, a_1, a_2, \ldots, a_r }[/math], respectively, or [math]\displaystyle{ a_1 a_2 \ldots a_r = e }[/math], [math]\displaystyle{ r=1 }[/math], [math]\displaystyle{ q }[/math] has a label [math]\displaystyle{ A }[/math] and [math]\displaystyle{ q_1 }[/math] has the empty string [math]\displaystyle{ e }[/math] as a label.

Other names are Parse tree, Syntax tree.