3.3.1. Общая характеристика и проблемы нисходящего анализа

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

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

В общем случае, в ходе нисходящего анализа, возникают следующие про­блемы:

1) Первая проблема возникает, когда цель определяется с использования правила с левой рекурсией.

Если А — цель и первое же правило для А имеет вид , то в соответ­ствии с данным методом будет установлена подцель А. В свою очередь, вспо­могательная подцель А потребуется для введенной подцели А и т.д.

Таким образом, леворекурсивные правила при нисходящем разборе надо исключать из грамматики.

2) Вторая проблема – недетерминированность вывода. Предположим, что при нисходящем анализе необходимо заменить самый левый нетерминал, определяемый правилом вида

Как узнать, какой цепочкой i*, i = 1,…, l необходимо заменить нетерминал А?

Общего метода нет. Есть рекомендации:

· упорядочить правила так, чтобы наиболее вероятные альтернати­вы испытывались первыми. Обычно первой испытывают самую длин­ную альтернативу. Однако если входная строка содержит ошибку, все равно придется перебрать все альтернативы;

· заглядывание вперед на 1-2 символа. Это позволяет более точно выбрать альтернативу. Делается это с помощью определения функ­ции

Fk(A) = {t* | At* и |t*| = k или At* и |t*| < k}.

· используя Fk(n), можно для всех AiN построить {Fk(A)}. Тогда сравнивая префикс оставшейся части входной цепочки с элементами множества (Fk(A)}, можно более быстро, во-первых, и более точно, во-вторых, выйти на приемлемую альтернативу;

· учет использованных в данных обстоятельствах альтернатив. Если альтернативы имеют общие префиксы и их неприемлемость фикси­руется в пределах этих префиксов, то можно пропускать целую груп­пу альтернатив с соответствующими префиксами;

· ограничить количество возвратов по глубине.

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