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

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

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

[[Помеченный граф|Помеченное]] [[упорядоченный граф|упорядоченное]] [[дерево]] <math>D</math>

называется ''деревом вывода''  в контекстно-свободной грамматике <math>G(A)=(N,\Sigma,P,A)</math>, если выполнены следующие условия:

(1) [[корень]] дерева <math>D</math> помечен символом <math>A</math>;

 

(3) если корень дерева имеет единственного сына, помеченного <math>e</math>, то этот сын образует дерево, состоящее из единственной вершины, и <math>A\longrightarrow e</math> --- правило из

''[[Сечение|Сечением]]'' дерева <math>D</math> называется такое множество <math>C</math> вершин дерева <math>D</math>, что

(1) никакие две вершины из <math>C</math> не лежат на одном [[путь|пути]] в <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> и всех ее потомков.

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

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

==См. также==

''[[Абстрактное синтаксическое представление]].''