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

56 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Начало: первая активная вершина – корень дерева (S). Правила
занумерованы (альтернативы нетерминала). В соответствии с установленным
порядком выбираемая альтернатива в данном случае 1.Входной указатель
стоит на первом символе исследуемой цепочки. В рассматриваемом случае
активная вершина – терминал.
Осуществляется сравнение с символом во входной цепочке, который
помечен указателем. Имеет место совпадение. Передвинуть указатель вправо
на одну позицию. Активной становится вершина S (первая справа от
проанализированного нетерминала а).
Снова используется альтернатива 1. Активный символ - терминал (а)
совпадает с символом, который помечен указателем. Передвигаем указатель
вправо. Активная вершина S. У первых двух альтернатив первый терминал
не совпадает с символом, который помечен указателем. Испытывается 3-я
альтернатива. Передвинуть указатель. Активная вершина – вершина,
помеченная терминальным символом (b). Сравнить и передвинуть указатель.
Активная вершина – вершина справа от b. Используем альтернативу 3.
Вершины совпадают, входная цепочка прочитана. Однако в дереве остались
2 неиспользованных вершины. Последовательность используемых правил не
позволила констатировать факт принадлежности рассматриваемой цепочки к
данной грамматике.
Осуществить возврат по дереву до вершины, у которой имеется не
опробованная альтернатива.
Вернуть указатель к следующему символу входной цепочки и
использовать альтернативу 2, у которой активной вершиной является
терминал а. Сравнить первый символ с указателем. Передвинуть указатель и
активизировать справа от а.