Дерево левых выводов

Материал из WikiGrapp
Перейти к:навигация, поиск

Дерево левых выводов (Left-derivation tree) — дерево, определяемое для контекстно-свободной грамматики следующим образом: корню дерева поставлена в соответствие цепочка, состоящая из единственного начального символа; если цепочка \alpha сопоставлена с некоторой вершиной p дерева, то для каждой цепочки \beta, получаемой левой подстановкой из \alpha, заводится вершина дерева и объявляется преемником вершины p.

Литература

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