Разбор без возвратов
Программа разбора в компиляторе ни в коем случае не должна прибе-
гать к возвратам. Мы должны иметь уверенность в том, что каждая пред-
полагаемая цель верна. Это нреобходимо потому, чтонам предстоит связать
семантику с синтаксисом, и по мере того, как мы будем прогнозировать и
находить цели, эти символы будут обрабатываться семантически. Вот неко-
торые примеры "обработки": 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. Заключение
В данном реферате рассматривались нисходящие распознаватели,
алгоритм нисходящего разбора и проблемы связанные с нисходящим
разбором. Одна из первых статей, рассматривающих фиксированный ал-
горитм нисходящего разбора, принадлежит Айронсу. Но его метод не
являлся нисходящим разбором в чистом виде, а являлся смешением нис-
ходящих и восходящих разборов. Алгоритм, приведенный в данном рефе-
рате, впервые был предложен в обзоре Флойда. Он же ввел и понятия
"отец - сын - брат". Способы избавления от возвратов описаны Унге-
ром.
5. Список литературы
1. Грисс. Конструирование компиляторов для цифровых вы-
числительных машин. М., Мир, 1975г.
2. Ахо А., Ульман Дж. Теория синтаксического анализа, пере-
вода и компиляции. М. Мир 1978г.
3. Ф.Льюис, Д.Розенкранц, Р.Стирнз. Теоретические основы
проектирования компиляторов. М., Мир, 1979г.
4. Фельдман Дж., Грис Д. Системы построения трансляторов.
Сб. Алгоритмы и алгоритмические языки, вып.5, ВЦ АН СССР, 1971г.
_