Аноним

Дерево вывода: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Дерево вывода''' (''[[Derivation tree, parse tree, syntax]]'') - способ представления множества ''выводов'' одной и той же ''[[цепочка|цепочки]]'' в ''[[контекстно-свободная грамматика|контекстно-свободной грамматике]]'', различающихся лишь порядком применения правил.
'''Дерево вывода''' (''[[Derivation tree, parse tree, syntax]]'') - способ представления множества ''выводов'' одной и той же ''[[цепочка|цепочки]]'' в ''[[контекстно-свободная грамматика|контекстно-свободной грамматике]]'', различающихся лишь порядком применения правил.


[[Файл:Derivation tree.png|500px]]
[[Файл:Derivation tree.png|750px]]


[[Помеченный граф|Помеченное]] [[упорядоченный граф|упорядоченное]] [[дерево]] <math>D</math>
[[Помеченный граф|Помеченное]] [[упорядоченный граф|упорядоченное]] [[дерево]] <math>D</math>
Строка 23: Строка 23:
''[[Крона сечения]]'' дерева <math>D</math> определяется как [[цепочка]], которая получается конкатенацией меток вершин, образующих данное сечение, в их упорядочении слева направо, определяемом по следующему правилу. Рассматривается имеющееся упорядочение на множестве сыновей <math>p_1,</math> <math> \ldots,</math> <math>p_k</math> каждого [[отец вершины ордерева|отца]] <math>p</math> в дереве <math>D</math> и считается, что для любых <math>i<j</math> вершина <math>p_i</math> и все ее [[потомок вершины|потомки]] расположены левее вершины <math>p_j</math> и всех ее потомков.
''[[Крона сечения]]'' дерева <math>D</math> определяется как [[цепочка]], которая получается конкатенацией меток вершин, образующих данное сечение, в их упорядочении слева направо, определяемом по следующему правилу. Рассматривается имеющееся упорядочение на множестве сыновей <math>p_1,</math> <math> \ldots,</math> <math>p_k</math> каждого [[отец вершины ордерева|отца]] <math>p</math> в дереве <math>D</math> и считается, что для любых <math>i<j</math> вершина <math>p_i</math> и все ее [[потомок вершины|потомки]] расположены левее вершины <math>p_j</math> и всех ее потомков.


''[[Кроной дерева]]'' <math>D</math> называется крона сечения, образованного из [[лист|листьев]] дерева <math>D</math>.
''[[Крона дерева|Кроной дерева]]'' <math>D</math> называется крона сечения, образованного из [[лист|листьев]] дерева <math>D</math>.


Другие названия --- ''[[Дерево разбора]], [[Синтаксическое дерево]].''
Другие названия --- ''[[Дерево разбора]], [[Синтаксическое дерево]].''