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