Стратегия разбора

Стратегия разбора
В процессе синтаксического анализа лексическая свертка программы обычно просматривается слева направо (и мы ограничимся рассмотрением только таких алгоритмов). Если программа допустима, то этот процесс завершается построением одного из ее деревьев разбора. Узнавая на каждом следующем шаге все большее число символов из лексической свертки транслируемой программы (и таким образом узнавая все большее число висячих вершин ее дерева разбора), мы попытаемся построить дерево разбора (которое согласуются с уже имеющейся информацией о программе), как бы заполняя его внутренними вершинами в некотором порядке. В принципе, мы можем выбрать произвольный порядок заполнения дерева. Однако этот порядок может в большой степени влиять на эффективность разбора, как в смысле трудоемкости, так и в смысле работы с ошибками (по отношению к той или иной конкретной грамматике). Он также тесно связан со всем процессом трансляции.
В большинство существующих методов разбора порядок заполне¬ния дерева сводится к одному из двух основных вариантов (или стра¬тегий):
• Стратегия нисходящего анализа. При заполнении сверху вниз все предшественники каждой заполняемой в дереве внутренней вершины к этому моменту уже заполнены. Таким образом, заполняя дерево при нисхо¬дящем анализе, мы как бы движемся от его корня к висячим верши¬нам
• Восходящий анализ. Заполнение снизу вверх (стратегия так на¬зываемого) характеризуется тем, что все преем¬ники каждой заполняемой в дереве вершины уже принадлежат по¬строенной части дерева. При восходящем анализе мы строим дерево от висячих вершин к корню.
В каждой из перечисленных стратегий можно реализовать ал¬горитм анализа для произвольного КС-языка.
Процесс нисходящего разбора
Процесс разбора (сверху-вниз) с точки зрения построения дерева разбора можно проиллюстрировать следующим образом.
• Фрагменты недостроенного дерева соответствуют сентенциальным формам вывода.
• Вначале дерево состоит только из одной вершины, соответствующей аксиоме S.
• В этот момент по первому символу входного потока предсказывающий анализатор должен определить правило S->X1 X2 …, которое должно быть применено к S.
• Затем необходимо определить правило, которое должно быть применено к X1, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y->a ….
• Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.
Рассмотрим метод рекурсивного спуска, как один из методов рекурсивного спуска.