Разбор рекурсивным спуском

Разбор рекурсивным спуском
Рассмотрим сначала разбор сверху в низ. Исходными данными для такого разбора является входная сентенциальная форма и дерево разбора, содержащее только корень, т.е. выделенный нетерминал. Задача разбора – ,используя правила грамматики построить полное дерево, соответствующее сентенциальной форме. Самый простой, но не самый оптимальный подход, состоит в создании рекурсивной программы, которая каждый раз выполняет подстановку для самого левого нетерминала дерева с использованием первого правила подстановки для этого нетерминала. Дойдя до терминалов, выполняется сравнение полученной части сентенциальной формы дерева с исходной. Если они совпадают, то часть дерева вывода принимается. Если нет, то выполняется рекурсивный шаг назад, и пытаемся подставить второе правило для нетерминала, а если больше правил нет, то выполняется еще шаг назад. Если в результате таких выводов будет построено дерево, соответствующее исходной сентенциальной форме, то исходная цепочка считается правильной и синтаксический анализ завершенным. Если дерево построить не удалось, то исходная цепочка отвергается.
Разумеется, такая процедура будет работать только для правой грамматики, т.к. левая зациклится.

Алгоритм

1. Создается корень дерева и заполняется выделенным символом грамматики
2. Вызывается процедура рекурсивного спуска, и ей передается дерево
3. Если процедура рекурсивного спуска вернула 1, то разбор успешен и дерев разбора заполнено, иначе ошибка.
Процедура рекурсивного спуска
1. Найти самый левый нетерминал.
2. Если он не найден, то п.10
3. Для i=1, до NP выполнить 4
4. Если левая часть правила i грамматики содержит текущий нетерминал, то перейти к п. 5, иначе п. 8
5. Достроить текущий нетерминал, согласно правилам
6. Если в результате подстановки 1 или несколько корней левых поддеревьев текущего узла содержат терминалы, то сравнить их с очередными символами исходной цепочки
7. Если они совпали, то эту часть цепочки считаем разобранной и возвращаем 1, иначе п.8
8. Перейти к следующей итерации цикла
9. Вернуть 0.
10. Если дерево соответствует цепочке, то вернуть 1, иначе 0.
Основным недостатком такой процедуры, является большое количество возвратов, т.е. ошибочных выводов. Теперь рассмотрим способы их исключения.
Ограниченные грамматики
Однако такой разбор не будет столь эффективным, чтобы быть применимым на практике, и будет содержать большое количество проб и ошибок. Основная проблема предсказывающего разбора – определение правила вывода, которое нужно применить к нетерминалу.
Впрочем, мож¬но определить ограниченные классы грамматик, которые поддаются более эффективному анализу в той или иной из указанных стратегий. Естественно, эти ограниченные классы грамматик являются менее гибкими как с точки зрения получаемых языков, так и по способам порождения предложений.

• LL(k) – грамматики, для которых левый нисходящий анализатор может определить какое правило использовать для вывода, если позволить ему принимать во внимание k-следующих входных символов, считая от текущей позиции просмотра.
• LR(k)-грамматики, для которых правый нисходящий анализатор работает детерминированно, если позволить ему принимать во внимание k входных символов, расположенных справа от текущей входной позиции.
• Грамматики предшествования, для которых правый анализатор может находить основу правовыводимой цепочки, учитывая только некоторые отношения между парами ее смежных символов.