20. Атрибутные грамматики. Типы атрибутов. Правила вычисления атрибутов.

Атрибутные транслирующие грамматики.

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

Для задания семантики применяются различные приемы: W -грамматики, венский метаязык, аксиоматический и денотационный методы, а также атрибутные транслирующие грамматики (АТ-грамматики).

Рассматриваемые в настоящем разделе АТ-грамматики отличаются от транслирующих грамматик тем, что символам грамматики приписываются атрибуты, отражающие семантическую информацию, а правилам грамматики сопоставляются правила вычисления значений атрибутов. Чтобы пояснить назначение атрибутов, приведем несколько примеров. Если входной язык предусматривает использование констант C, то в качестве атрибута константы можно взять ее значение. Условимся записывать значение константы за ее обозначением с разделителем в виде косой черты, например, C/5. Если в Т-грамматике используются операционные символы {сложить}, то в качестве атрибутов таких символов можно взять значения операндов и результата. Обозначая атрибуты символами x, y, z, операционный символ с атрибутами запишем в виде {сложить}/x/y/z.

Определение АТ-грамматик В АТ-грамматиках используются атрибуты двух видов: наследуемые и синтезируемые. Значения наследуемых атрибутов определяются при выполнении очередного шага вывода по значениям атрибутов цепочки, содержащихся в левой части правила грамматики. Вычисление значений синтезируемых атрибутов может откладываться и определяться при выполнении последующих шагов вывода. В общем виде свойства АТ-грамматик могут быть сформулированы следующим образом.

Определение. Транслирующую грамматику называют атрибутной грамматикой или АТ-грамматикой если: 1. Символам грамматики приписаны один или несколько атрибутов и для каждого атрибута определено множество допустимых значений. 2. Атрибуты могут быть наследуемыми и синтезируемыми. 3. Для каждого правила грамматики должны быть заданы правила вычисления атрибутов в виде оператора присваивания с функцией в правой части, определяющей значение атрибута, расположенного слева. Такие функции для вычисления атрибутов могут зависеть от атрибутов правой или левой частей рассматриваемого правила. 4. Для наследуемых атрибутов начального символа должны быть заданы начальные значения. 5. Функции, вычисляющие значения синтезируемых атрибутов символов действия, должны зависеть от других атрибутов этого символа.

Пример АТ-грамматики Атрибутные транслирующие грамматики могут быть использованы для построения выводов, в которых построение цепочки совмещается с вычислением значений атрибутов. Чтобы различать атрибуты в правилах вывода, условимся записывать синтезируемые атрибуты с префиксом в виде знака процента (%), а наследуемые - с префиксом в виде наклонной черты (/). Например, если символ <X> имеет один синтезируемый атрибут a и два наследуемых атрибута b, c, а символы <Y> и <Z> имеют по одному наследуемому атрибуту d и e, то правило <X><Y><Z> может быть записано в виде:

<X>%a/b/c  <Y>/d<Z>/e.

Это правило вывода необходимо дополнить правилами вычисления значений атрибутов, которые в соответствии с приведенным определением могут иметь вид: a := b+d; d := 2*c; e := b. В дальнейшем правила вычисления атрибутов условимся записывать непосредственно за правилами вывода или на отдельной строчке, отделяя их от правил вывода двумя восклицательными знаками (!!). В качестве первого примера рассмотрим АТ-грамматику, описывающую трансляцию выражений, состоящих из констант C, в значение заданного выражения. Допустим, что у каждого нетерминала <E>, <T>, <P> имеется по одному атрибуту, принимающему целочисленные значения. Терминальный символ C также имеет один атрибут, определяющий значение константы и принимающий целочисленные значения. Операционный символ грамматики {ответ} имеет наследуемый атрибут с целочисленной областью значений. Начальным символом грамматики служит символ <S>.

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

Г _{5. 0} : <S> <E>%a{ответ/b}

!! b := a <E>%d <E>%e+<T>%f !! d := e+f <E>%g <T>%h !! g := h <T>%i <T>%j*<P>%k !! i := j*k <T>%m <P>%n !! m := n <P>%p (<E>%q) ! p := q <P>%r C/s !! r := s.

Демонстрация вычисления значений атрибутов с левым выводом

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

Выполнение совмещенного вывода в приведенной грамматике рассмотрим на примере цепочки C+C*C, содержащей константы со значениями 1, 2, 3.

При построении цепочек в строках 2, 3, 4, 5 правила вычисления атрибутов заносятся в список отложенных вычислений. Появление первой константы в выводимой цепочке приводит к выполнению трех правил в списке. Аналогично, сокращение списка отложенных вычислений происходит после получения цепочек в строках 9 и 10. Предполагается, что символ действия {ответ} в строке 11 передает полученное значение атрибута на выход.

21. L-атрибутные грамматики. Необходимость свойства L - атрибутности.

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 используется для проверки символов действия. Чтобы убедиться в его выполнении, нужно просмотреть список аргументов правил вычисления атрибутов и убедиться, что среди них нет синтезированных атрибутов.