Стр. 57 - Информационные структуры и их преобразование

Содержание 55
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Один из способов нахождения всех разборов входной цепочки состоит
в определении всех допускающих конфигураций, достижимых из С0.
Прослеживая левую ветвь, видим, что заключительная конфигурация
С6 не является допускающей. Чтобы определить, существует ли другая
допускающая конфигурация, необходимо сделать возврат по дереву, пока не
встретится конфигурация, для которой возможен еще не рассмотренный
выбор очередного такта. Так как в вершине С6 других выборов нет, то
необходимо выполнить возврат до вершины С1. Вершина С9 является
завершением альтернативной ветви для рассмотренной вершины, она
допускающая.
Если важен факт принадлежности цепочки данной грамматике, следует
вернуться к вершине С0 и перепробовать оставшиеся конфигурации. Если
исследуемая цепочка построена неверно, то придется рассмотреть все
конфигурации и выдать сообщение об ошибке.
Нисходящий разбор в терминах грамматик
Будем использовать входной указатель, который в начальный момент
времени указывает на самый левый символ рассматриваемой цепочки.
Процесс начнем с корня. Вершина, которую мы рассматриваем в данный
момент, – активная. Если активная вершина помечена некоторым
нетерминалом «А», нужно выбрать первую его альтернативу. (Пусть
A:=x1 …xk) К вершине А добавить к прямых потомков и сделать активной
вершину х1 (самую левую). Если активная вершина помечена терминалом,
нужно сравнить с ним текущий входной символ и сделать активной вершину
справа от нее, а также сдвинуть входной указатель на одну позицию вправо.
Если этот терминал не совпадает с текущим входным символом, нужно
вернуться к вершине, где было использовано предыдущее правило.
Если альтернатив больше нет, нужно вернуться к следующей
предыдущей вершине. Таким образом, предпринимается попытка сохранить
совместимость строящегося дерева с входной цепочкой.