3.2.3. Определение атрибутной транслирующей грамматики

Определение. Атрибутная транслирующая граммати­ка - это транслирующая грамматика, обладающая следующими до­полнительными свойствами:

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

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

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

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

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

4. Правила вычисления значений синтезированных атрибутов определяются следующим образом:

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

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

Будем записывать атрибуты в виде индексов соответствующих символов АТ-грамматики, при этом для каждого атрибута будем указывать, к какому классу этот атрибут относится. Например:

Х_a,b синтезированный а унаследованный b

Правила вычисления атрибутов будем записывать в виде опе­раторов присваивания, левая часть которых – атрибут или спи­сок атрибутов, а правая часть – функция.

Рассмотрим AT-грамматику G₅^А, описывающую перевод оператора присваивания некоторого языка программирования в цепочку тетрад с кодами операций: СЛОЖИТЬ, УМНОЖИТЬ, ПРИСВОИТЬ. Левой частью оператора присваивания является идентификатор, а правой частью – бесскобочное арифметическое выражение, выполняемое слева направо в порядке написания операций.

Входными символами грамматики являются символы множества { i, +, , = }, где i – лексема, представляющая идентификатор. Каждый идентификатор имеет один атрибут, значением которого является указатель на соответствующий элемент таблицы идентификаторов.

Операционные символы {СЛОЖИТЬ}, {УМНОЖИТЬ}, {ПРИСВОИТЬ} соответствуют кодам операций тетрад, получаемых на выходе. Символы {СЛОЖИТЬ} и {УМНОЖИТЬ} имеют по три унаследованных атрибута, значениями которых яв­ляются указатели на элементы таблицы, в которой хранятся значения левого операнда, правого операнда и результата соответственно. Операционный символ {ПРИСВОИТЬ} имеет два унаследо­ванных атрибута. Значение первого атрибута – указатель на элемент таблицы идентификаторов, соответствующий идентифика­тору из левой части оператора присваивания, а значением второго атрибута является указатель на элемент таблицы, в кото­ром хранится значение выражения из правой части оператора присваивания.

Словарь нетерминальных символов состоит из символов S, Е и R. Начальный символ S не имеет атрибутов, символ Е имеет один синтезированный атрибут, значением которого является указатель на элемент таблицы, содержащий значение выражения, порождаемого Е, а символ R имеет два атрибута: унаследованный (первый) и синтезированный. Значением унаследованного атрибута является указатель на элемент таблицы, соответствующий промежуточному результату, предшествующему R. Этот промежуточный результат является также левым операндом первой операции, порождаемой нетерминальным символом R, если такая операция имеет место. Значение синтезированного атрибута символа R – указатель на элемент таблицы, соответствующий значению подвыражения, которое получается после присоединения цепочки, порожденной символом R, к цепочке, представляющей левый опе­ранд.

Правила вывода АТ-грамматики G₅^А с соответствующими правилами вычисления атрибутов приведены на рис. 3.9. В атрибутных правилах, связанных с правилами вывода (3) и (4), используется процедура-функция без параметров GETNEW, которая вы­дает значение указателя на свободную позицию таблицы, в которой будут запоминаться промежуточные результаты. Строго го­воря, эта процедура не является функцией, так как при разных обращениях к ней получаются разные результаты. Таким образом, пользуясь процедурой GETNEW, мы несколько отступаем от опре­деления АТ-грамматики. Вместо того чтобы использовать процедуру GETNEW, можно ввести дополнительные атрибуты для запоминания адресов занятых позиций таблицы. Однако при использовании процедуры GETNEW атрибутные правила получаются более простыми, и такой подход можно порекомендовать при практическом конструировании компиляторов.

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

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

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

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

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

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

5. Повторять шаг 4 до тех пор, пока значения всех атрибутов символов, входящих в дерево вывода, не будут вычислены, или шаг 4 не может быть выполнен.