Аноним

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

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


[[Файл:Derivation tree.png|750px]]
[[Файл:Derivation tree.png|750px]]
Строка 8: Строка 8:
(1) [[корень]] дерева <math>D</math> помечен символом <math>A</math>;
(1) [[корень]] дерева <math>D</math> помечен символом <math>A</math>;


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


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


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


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


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