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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Derivation tree.png

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

(1) корень дерева D помечен символом A;

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

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

Сечением дерева D называется такое множество C вершин дерева D, что

(1) никакие две вершины из C не лежат на одном пути в D,

(2) ни одну вершину дерева D нельзя добавить к C, не нарушив свойства 1.

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

Кроной дерева D называется крона сечения, образованного из листьев дерева D.

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

См. также

Литература

  • Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
  • Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.