Derivation tree

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Let G be a CF-grammar and x be a sentence form in G.

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

Other names are Parse tree, Syntax tree.