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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Дерево редукций''' (''Reduction tree'') - дерево, определяемое для заданных цепочки ...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Дерево редукций''' (''Reduction tree'') -
'''Дерево редукций''' (''[[Reduction tree]]'') — [[дерево]], определяемое для заданных [[цепочка|цепочки]] <math>\alpha</math> и ''[[контекстно-свободная грамматика|контекстно-свободной грамматики]]'' следующим образом: [[корень|корню]] дерева соответствует цепочка <math>\alpha</math>; если с некоторой [[вершина|вершиной]] <math>p</math> сопоставлена цепочка <math>\beta</math>, то для каждой возможной редукции <math>\beta</math> заводится новая вершина
дерево, определяемое для заданных цепочки <math>\alpha</math> и ''контекстно-свободной грамматики'' следующим образом: корню
[[преемник вершины]] <math>p</math>, которой и ставится в соответствие цепочка, получаемая в результате этой редукции.
дерева соответствует цепочка <math>\alpha</math>; если с некоторой
вершиной <math>p</math> сопоставлена цепочка <math>\beta</math>, то для каждой
возможной редукции <math>\beta</math> заводится новая вершина ---
преемник вершины <math>p</math>, которой и ставится в соответствие
цепочка, получаемая в результате этой редукции.
==Литература==
==Литература==
[Касьянов-Поттосин],
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


[Евстигнеев-Касьянов/94]
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.

Текущая версия от 18:42, 3 февраля 2011

Дерево редукций (Reduction tree) — дерево, определяемое для заданных цепочки [math]\displaystyle{ \alpha }[/math] и контекстно-свободной грамматики следующим образом: корню дерева соответствует цепочка [math]\displaystyle{ \alpha }[/math]; если с некоторой вершиной [math]\displaystyle{ p }[/math] сопоставлена цепочка [math]\displaystyle{ \beta }[/math], то для каждой возможной редукции [math]\displaystyle{ \beta }[/math] заводится новая вершина — преемник вершины [math]\displaystyle{ p }[/math], которой и ставится в соответствие цепочка, получаемая в результате этой редукции.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.