Просмотр кода страницы Derivation tree

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

Let <math>G</math> be a CF-grammar and <math>x</math> be a sentence form in <math>G</math>.

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

Other names are '''Parse tree''', '''Syntax tree'''.