Derivation tree

Материал из WikiGrapp
Версия от 15:42, 24 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Derivation tree''' --- дерево вывода. Let <math>G</math> be a CF-grammar and <math>x</math> be a sentence form in <math>G</math>. All equivalent der…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

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.