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

Перейти к навигации Перейти к поиску

Дерево вывода (посмотреть исходный код)

Версия от 17:10, 3 февраля 2011

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


Помеченное упорядоченное дерево <math>D</math>
[[Файл:Derivation tree.png|750px]]
называется ''деревом вывода''  в
контекстно-свободной грамматике <math>G(A)=(N,\Sigma,P,A)</math>, если
выполнены следующие условия:


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


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


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


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


(1) никакие две вершины из <math>C</math> не лежат на одном пути в <math>D</math>,
(1) никакие две вершины из <math>C</math> не лежат на одном [[путь|пути]] в <math>D</math>,


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


''Крона сечения'' дерева <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>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>.


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


См. также ''Абстрактное синтаксическое представление.''
==См. также==
* ''[[(Абстрактное) синтаксическое представление|Абстрактное синтаксическое представление]].''
==Литература==
==Литература==
[Ахо-Ульман],  
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
 
[Касьянов/95],  
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
 
[Касьянов-Поттосин],  


[Евстигнеев-Касьянов/94]
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
Источник — http://pco.iis.nsk.su/grapp/index.php/Служебная:Сравнение_версий/2638...6079

Навигация