Дерево разбора

Графическим способом отображения процесса разбора цепочек является дерево разбора (или дерево вывода).

Определение дерево разбора грамматики называется дерево, которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

- каждая вершина дерева обозначается символом грамматики ;

- корнем дерева является вершина, обозначенная начальным символом грамматики S;

- листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой строки e;

- если некоторый узел дерева обозначен символом , а связанные с ним узлы – символами , то в грамматике существует правило

Дерево разбора можно построить двумя способами: сверху вниз и снизу вверх.