Дерево вывода

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

Помеченное упорядоченное дерево [math]\displaystyle{ D }[/math] называется деревом вывода в контекстно-свободной грамматике [math]\displaystyle{ G(A)=(N,\Sigma,P,A) }[/math], если выполнены следующие условия:

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

(2) если [math]\displaystyle{ D_1,\ldots,D_k }[/math] --- поддеревья, корнями которых являются сыновья корня [math]\displaystyle{ D }[/math], помеченные символами [math]\displaystyle{ X_1, \ldots, X_k }[/math] соответственно, то [math]\displaystyle{ A\longrightarrow X_i\ldots X_k }[/math] --- правило из множества [math]\displaystyle{ P }[/math]. Каждое [math]\displaystyle{ D_i }[/math] должно либо быть деревом вывода в грамматике [math]\displaystyle{ G(X_i)=(N,\Sigma,P,X_i) }[/math], если [math]\displaystyle{ X_i }[/math] - нетерминал, либо состоять из единственной вершины, помеченной символом [math]\displaystyle{ X_i }[/math], если [math]\displaystyle{ X_i }[/math] --- терминал;

(3) если корень дерева имеет единственного сына, помеченного [math]\displaystyle{ e }[/math], то этот сын образует дерево, состоящее из единственной вершины, и [math]\displaystyle{ A\longrightarrow e }[/math] --- правило из множества [math]\displaystyle{ P }[/math].

Сечением дерева [math]\displaystyle{ D }[/math] называется такое множество [math]\displaystyle{ C }[/math] вершин дерева [math]\displaystyle{ D }[/math], что

(1) никакие две вершины из [math]\displaystyle{ C }[/math] не лежат на одном пути в [math]\displaystyle{ D }[/math],

(2) ни одну вершину дерева [math]\displaystyle{ D }[/math] нельзя добавить к [math]\displaystyle{ C }[/math], не нарушив свойства 1.

Крона сечения дерева [math]\displaystyle{ D }[/math] определяется как цепочка, которая получается конкатенацией меток вершин, образующих данное сечение, в их упорядочении слева направо, определяемом по следующему правилу. Рассматривается имеющееся упорядочение на множестве сыновей [math]\displaystyle{ p_1, }[/math] [math]\displaystyle{ \ldots, }[/math] [math]\displaystyle{ p_k }[/math] каждого отца [math]\displaystyle{ p }[/math] в дереве [math]\displaystyle{ D }[/math] и считается, что для любых [math]\displaystyle{ i\lt j }[/math] вершина [math]\displaystyle{ p_i }[/math] и все ее потомки расположены левее вершины [math]\displaystyle{ p_j }[/math] и всех ее потомков.

Кроной дерева [math]\displaystyle{ D }[/math] называется крона сечения, образованного из листьев дерева [math]\displaystyle{ D }[/math].

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

См. также Абстрактное синтаксическое представление.

Литература

[Ахо-Ульман],

[Касьянов/95],

[Касьянов-Поттосин],

[Евстигнеев-Касьянов/94]