Определение и свойства АТ-грамматики

АТ-грамматика — это транслирующая грамматика, дополнен­ная следующим образом.

1. Каждый терминал, нетерминал и операционный символ имеет конечное множество атрибутов, и каждый атрибут имеет множество (возможно, бесконечное) допустимых значений.

2. Все атрибуты нетерминалов и операционных символов де­лятся на наследуемые и синтезируемые.

3. Наследуемые атрибуты вычисляются следующим образом:

а) значение наследуемого атрибута из правой части правила
грамматики вычисляется как функция некоторых других атрибутов
символов, входящих в правую или левую часть данного правила;

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

4. Синтезируемые атрибуты вычисляются так:

а) значение синтезируемого атрибута нетерминала из левой
части правила грамматики вычисляется как функция некоторых
других атрибутов символов из левой или правой части данного
правила;

б) значение синтезируемого атрибута операционного симво­ла вычисляется как функция некоторых других атрибутов этого
символа.

5. Значения атрибутов терминалов считаются заданными, они
не относятся ни к наследуемым, ни к синтезируемым.

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

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

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

2. Присвоить значения атрибутам терминалов, входящих в
дерево разбора.

3. Присвоить начальные значения наследуемым атрибутам
аксиомы грамматики на дереве разбора.

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

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

Показано, что можно найти подклассы АТ - грамматик, которым соответствуют детерминированные МП - машины. Сформулирован ряд важных теорем, отдельные из которых дадим здесь без доказательства.

Теорема 1.Любая трансляция, определяемая L-AT-грамматикой, может быть выполнена недетерминированной атрибутной МП - машиной.

АТ - грамматика называется L-AT-грамматикой, если вы­полняются следующие условия (ограничения на АТ - грамматику).

1. Значение наследуемого атрибута символа из правой части правила может зависеть только от наследуемых атрибутов левой части правила и от любых атрибутов символов, стоящих в пра­вой части правила левее рассматриваемого символа.

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

3. Значение синтезируемого атрибута операционного символа зависит только от наследуемых атрибутов этого символа. Условие 1 делает наследуемые атрибуты некоторого узла дерева разбора зависящими (прямо или косвенно) от атрибутов терминалов, расположенных на дереве левее данного узла. Отсюда и наименование грамматики (Left - левая). Условия 2 и 3 делают грамматику корректной.

Теорема 4.Любую трансляцию, определяемую L-AT-грамматикой, у которой входная грамматика является LL(k)-грамматикой, можно выполнить на атрибутной детерминированной МП-I машине с концевым маркером.

Отметим, что здесь, как и в случае с МП-распознавателем, LL(k)-грамматика обеспечивает применение нисходящей страте­гии анализа.

Теорема 6.Всякая трансляция, определяемая некоторой S-атрибутной польской транслирующей грамматикой (S-АПТ-грамматикой) с входной LR(к)-грамматикой, может быть выполнена детерминированной атрибутной МП - машиной с концевым мар­кером.

В данном случае МП - машина работает с использованием вос­ходящей стратегии анализа. АТ - грамматика называется польской, если все операционные символы встречаются только в качестве последних символов правых частей правил грамматики. Нако­нец, L-AT-грамматика называется S-атрибутной, если все атри­буты нетерминалов — синтезируемые.