Пред.СтраницаСлед.СтраницаРаздел Содержание
5.3. L - атрибутные транслирующие грамматики
5.3.1. L - атрибутные транслирующие грамматики
Задачей
настоящего раздела является не только знакомство с атрибутными описаниями переводов, но и с нисходящими атрибутными преобразователями.
Они должны обрабатывать цепочки входных символов с атрибутами и для каждой
входной цепочки либо строить выходную цепочку в качестве ее перевода, либо отвергать ее, как не
принадлежащую входному языку. Такие устройства должны обеспечивать вычисление
атрибутов в ходе нисходящего разбора. Возможность такой обработки предоставляет
не всякая АТ-грамматика, а только
грамматики, отвечающие определенным требованиям, которые выражаются в виде
ограничений как на характер зависимости атрибутов правил грамматики, так и на
вид правил вычисления атрибутов. Вначале рассмотрим подкласс атрибутных транслирующих грамматик с ограничениями на
зависимости атрибутов, обеспечивающими их вычисление при нисходящем разборе.
Такие грамматики называются L - атрибутными
транслирующими грамматиками (LАТ-грамматиками).
Определение. АТ-грамматика является L - атрибутной транслирующей грамматикой, если выполняются следующие три условия: 1) Каждый наследуемый атрибут символа правой части правила грамматики должен вычисляться с использованием либо наследуемых атрибутов символов левой части правила, либо с использованием произвольных атрибутов символов правой части правила, расположенных левее данного символа. 2) Каждый синтезируемый атрибут символа левой части правила грамматики должен вычисляться с использованием наследуемых атрибутов этого символа левой части правила или произвольных атрибутов символов правой части этого правила. 3)
Каждый синтезируемый атрибут символа действия должен вычисляться по
наследуемым атрибутам этого символа действия. |
Значение
условия 1 состоит в том, что оно обеспечивает зависимость наследуемых атрибутов
от величин, находящихся только слева от них в правиле грамматики (символ L в
обозначении LАТ-грамматики - это
сокращение от Left - левый). Это условие позволяет обрабатывать атрибуты
сверху вниз, потому что каждый символ обрабатывается до того, как прочитаны
символы справа от него. Условия 2 и 3 обеспечивают исключение круговых
зависимостей атрибутов. Все три условия, взятые вместе, приводят к следующему
порядку вычисления атрибутов для правила вида
<A> ® <B><C>:
1)
наследуемые атрибуты <A>,
2) наследуемые атрибуты <B>,
3) синтезируемые атрибуты <B>,
4) наследуемые атрибуты <C>,
5) синтезируемые атрибуты <C>,
6) синтезируемые атрибуты <A>.
Чтобы
убедиться в том, что заданная АТ-грамматика
обладает свойствами LАТ-грамматики,
нужно проверить для каждого правила грамматики выполнение условий 1 и 2, а
также для каждого символа действия - выполнение условия 3. Такая проверка
заключается в анализе зависимостей атрибутов для каждого правила их вычисления.
В качестве
иллюстрации выполним анализ возможных зависимостей атрибутов, отвечающих
описанным условиям, для следующего правила:
<A>/a1%x1%y1
® <B>/b1<C>%x2<D>%y2/a2/b2<E>/a3
Анализ зависимостей этого правила должен заключаться в
проверке того, что правила вычисления атрибутов b1,
a2, b2, a3 должны удовлетворять условию 1, а правила
вычисления атрибутов x1, y1 - условию 2. Согласно условию 1 правило
вычисления атрибута b1 может использовать
для вычисления только атрибут a1, поэтому такие правила могут, например, иметь
вид:
b1 =
f(a1) или b1 = 112 или (b1,b2) = a1.
Последнее из приведенных выражений обозначает множественное присваивание, когда двум величинам одновременно присваивается одно и то же значение.
Отметим также, что правила
вычисления не могут иметь, например, следующий вид:
b1 = x1 или b1 = g(y2,b1).
Условие 1 для рассматриваемого правила позволяет использовать для вычисления атрибутов a2 и b2 в качестве аргументов величины a1, b1, x2, а при вычислении a3 аргументами могут быть a1, b1, x2, y2, a2, b2.
Согласно условию правила 2 при вычислении атрибутов x1 и y1 могут быть использованы любые атрибуты кроме самих x1, y1.
Условие 3 используется для проверки символов действия. Чтобы убедиться в его выполнении, нужно просмотреть список аргументов правил вычисления атрибутов и убедиться, что среди них нет синтезированных атрибутов.