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

Дерево левых выводов (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.