Реферат: Алгоритм нисходящего разбора. Нисходящие распознаватели

Подробно о синтаксических графах см. в книге Д.Гриса "Конструи-

рование компиляторов для цифровых вычислительных машин"

Разбор без возвратов

Программа разбора в компиляторе ни в коем случае не должна прибе-

гать к возвратам. Мы должны иметь уверенность в том, что каждая пред-

полагаемая цель верна. Это нреобходимо потому, чтонам предстоит связать

семантику с синтаксисом, и по мере того, как мы будем прогнозировать и

находить цели, эти символы будут обрабатываться семантически. Вот неко-

торые примеры "обработки": 1) при обработке описаний переменных иденти-

фикаторы помещаются в таблицу символов; 2) при обработке арифметических

выражений проверяют, совместимы ли типы операндов.

Если возврат произошел из-за того, что прогнозируемая цель неверна,

придется уничтожить результаты семантической обработки, сделанной во

время поисков этой цели. Сделать это не так -то просто, поэтому постара-

емся провести грамматический разбор без возвратов.

Для того, чтобы избавиться от возвратов, в компиляторах в качестве

контекста обычно используется следующий "незакрытый" символ исходной про-

граммы. Тогда на грамматику налагается следующее требование: если есть

альтернативы x|y|...|z, то множества символов, которыми могут начинаться

выводимые из x,y,..,z слова, должны быть попарно различны. То есть если

x => *Au и y => *Bv то A =/= B. если это требование выполнено, можно

довольно просто определить, какая из альтернатив x,y или z - наша цель.

Заметим, что факторизация оказывает здесь большую помощь. Если есть пра-

вило U ::= xy|xz, ео преобразование этого правила к виду U ::= x(y|z)

помогает сделать множесва первых символов для разных альтернатив непе-

ресекающимися.

4. Заключение

В данном реферате рассматривались нисходящие распознаватели,

алгоритм нисходящего разбора и проблемы связанные с нисходящим