7. ИСПОЛЬЗОВАНИЕ ГРАММАТИЧЕСКОГО АНАЛИЗА ДЛЯ КОМПИЛЯЦИИ

В этой книге речь идет в основном 0 грамматическом анализе предложений, а не о сопутствующей этому анализу последовательной компиляции. Последнему вопросу посвящен целый ряд статей [4, 6, 10, 20, 21, 28, 30, 31]. Можно дождаться завершения построения полного дерева грамматического анализа, а затем обрабатывать его. Другой возможный вариант состоит в том, чтобы выполнять действия компиляции непосредственно в процессе грамматического анализа. Краткое описание такого способа приводится ниже.

Рассмотрим некую грамматику с действиями в концах правил подстановки. В процессе разбора слева направо у нас формируется магазинный список. Рассматриваемые действия либо добавляют нечто к этому магазинному списку, либо извлекают из него некоторые элементы и помещают результат снова в магазинный список. Предположим сначала для простоты, что мы хотим преобразовывать выражения вида

в такую форму:

Будем использовать грамматику

Предполагается, что интерпретация ид добавляет имя идентификатора к магазинному списку. Действие р выполняется после первого идентификатора следующим образом:

Действие q выполняется, когда двум верхним элементам магазинного списка соответствуют S и ид:

Будем использовать эту грамматику в преобразованном виде:

Ниже перечисляются последовательные шаги:

А если бы мы захотели, чтобы из выражения

получалось

то мы воспользовались бы грамматикой

в которой ид и р действуют так же, как в предыдущем примере. Действие же r над двумя верхними элементами магазинного списка, соответствующими классам ид и S, выполняется следующим образом:

Теперь последовательность шагов имеет следующий вид:

В качестве более сложного примера рассмотрим грамматику

Мы можем ввести компилирующие действия

где

Например, это обеспечит трансляцию формулы

в фрагмент программы:

Преобразуем эту грамматику и получим новую грамматику:

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

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

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