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

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

[[Помеченный граф|Помеченное]] [[упорядоченный граф|упорядоченное]] [[дерево]] <math>D</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> и всех ее потомков.

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