5.1.3. Пример ат-грамматики

    Атрибутные транслирующие грамматики могут быть использованы для построения выводов, в которых построение цепочки совмещается с вычислением значений атрибутов. Чтобы различать атрибуты в правилах вывода, условимся записывать синтезируемые атрибуты с префиксом в виде знака процента (%), а наследуемые - с префиксом в виде наклонной черты (/). Например, если символ <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.

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

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

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

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

1. <S>                                                         -

2. <E>%a{ответ/b}                           b := a

3. <E>%e+<T>%f{ответ/b}              b := a; a := e+f;

4. <T>%h+<T>%f{ответ/b}              b := a; a := e+f; e := h ;

5. <P>%n+<T>%f{ответ/b}              b := a; a := e+f; e := h; h := n;

6. C/1+<T>%f{ответ/b}                    b := a; a := e+f; e := h; h := n; n := 1;

7. C/1+<T>%j*<P>%k{ответ/b}      b := a; a := 1+f; f := j*k;

8. C/1+<P>%n*<P>%k{ответ/b}     b := a; a := 1+f; f := j*k; j := n;

9. C/1+C/2*<P>%k{ответ/b}           b := a; a := 1+f; f := j*k; j := n; n := 2;

10. C/1+C/2*C/3{ответ/b}                 b := a; a := 1+f; f := 2*k; k := 3;

11. C/1+C/2*C/3{ответ/b}                 b := 7

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