Задача разбора цепочек КС-языков

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

Графическим способом отображения процесса разбора цепочек является дерево разбора (или дерево вывода).
Определение 3.4. Деревом разбора грамматики называется дерево, которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

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

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

Нисходящее дерево разбора

При построении дерева вывода сверху вниз построение начинается с начального символа грамматики, который помещается в корень дерева. Затем в грамматике выбирается необходимое правило, и на первом шаге вывода корневой символ раскрывается на несколько символов первого уровня. На втором шаге среди всех концевых вершин дерева выбирается крайняя (крайняя левая для левостороннего вывода, крайняя правая для правостороннего) вершина, обозначенная нетерминальным символом, для этой вершины выбирается нужное правило грамматики, и она раскрывается на несколько вершин следующего уровня. Построение дерева заканчивается, когда все концевые вершины обозначены терминальными символами, в противном случае надо вернуться ко второму шагу и продолжить построение.

Восходящее дерево разбора

Построение дерева вывода снизу вверх начинается с листьев дерева. В качестве листьев выбираются терминальные символы конечной цепочки вывода, которые на первом шаге построения образуют последний уровень (слой) дерева. Построение дерева идет по слоям. На втором шаге построения в грамматике выбирается правило, правая часть которого соответствует крайним символам в слое дерева (крайним правым символам при правостороннем выводе и крайним левым при левостороннем). Выбранные вершины слоя соединяются с новой вершиной, которая выбирается из левой части правила. Новая вершина попадает в слой дерева вместо выбранных вершин. Построение дерева закончено, если достигнута корневая вершина (обозначенная начальным символом), иначе следует вернуться ко второму шагу и повторить его над полученным слоем дерева.
Пример 3.2. Нисходящее дерево вывода строки a+b+a в грамматике G (пример 3.1) показано на рисунке 3.1.
Процесс построения восходящего дерева разбора показан на рисунке 3.2.

Рисунок 3.2 – Процесс построения восходящего дерева разбора