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