Определение 4.3.1. [10] Атрибутной формальной грамматикой (А-грамматикой) называется пара

Здесь G = <N, T, P, S> – безатрибутная КС-грамматика; А – атрибутная компонента,

где Х – множество атрибутов;

₁,_p­ – множество функций и предикатов, заданных на множестве Х со значениями во множестве R.

Каждому символу TN сопоставлено два непересекающихся множества:

· множество унаследованных атрибутов Х_у();

· множество синтезированных атрибутов Х_с().

При этом выполняются условия X() = X, X_y()X_c() =, X()=X_y()X_c().

Правила вычисления атрибутов определяется следующим образом [17]:

а) начальное значение каждого унаследованного атрибута для начального символа грамматики S (аксиомы) задается;

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

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

Атрибутная грамматика связывает атрибуты с вершинами синтаксического дерева вывода. Семантические правила вычисления значений атрибутов, соот­ветствующие правилу КС-грамматики, применяются для всех вхождений это­го правила в дерево вывода. Синтезированные атрибуты некоторой вершины хранят информацию, которая синтезируется из поддерева этой вершины и пе­редается вверх к корню дерева. Унаследованные атрибуты служат для хране­ния информации, которая передается сверху вниз, от корня дерева к его листьям. Фактически унаследованные атрибуты определяют контекст, в котором погру­жена вершина вместе со своим поддеревом. Контекстно-зависимые условия входного языка должны выражаться через ряд условий, входящих в семанти­ческие правила А-грамматики. Наконец, эти условия должны

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

Описание семантики языка с помощью атрибутных грамматик позволяет определить «смысл» исходной программы, как значения одного или несколь­ких специальных атрибутов корня синтаксического дерева этой программы. Поскольку главной задачей в процессе трансляции является получение объек­тной программы, то можно считать, что один из специальных атрибутов корня синтаксического дерева получает значение — последовательности операций абстрактной машины, т.е. объектную программу.

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

Правила вычисления значений атрибутов для нетерминальных и терминаль­ных вершин дерева вывода аналогичны правилам, указанным в определении 4.3.1. Для вычисления значений атрибутов символов действий вводится допол­нительное правило:

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

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

Для записи правил АТ-грамматики приняты следующие соглашения:

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

2) Семантические правила вычисления значений атрибутов записыва­ются под каждой продукцией в форме оператора присваивания, при этом вместо «=» используется знак «». В правой части от «» стоит либо выражение, либо имя процедуры (функции), с помощью которой и осу­ществляется вычисление значения атрибута. В левой части — имя пе­ременной (атрибута) или их список, которым присваивается значение, вычисленное в правой части правила.

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

Например, если нетерминал X имеет два синтезируемых и один наследуе­мый атрибуты, а нетерминалы Y и Z по одному наследуемому и одному синте­зируемому атрибуту, а терминал b — один атрибут, то правило

XbYZ {ПЕЧАТЬ},

где {ПЕЧАТЬ} — операционный символ, в АТ-грамматике будет иметь вид:

X_{p, q, r}b_sY_y,u Z_v,w {ПЕЧАТЬ}_m.

Если q, р — синтезируемые, а у, v, m, p — наследуемые атрибуты, то правила их вычисления могут быть заданы, например, в виде:

qSIN(n+w);

(r, w) S*n;

yp;

mp.

Определение 4.3.3.[17]. Атрибутная грамматика, в которой любое дерево вывода завершенное, называется корректной.

Среди грамматик, используемых для описания языков программирования, особое место занимают так называемые L-атрибутные грамматики. Этот класс грамматик допускает построение синтаксических анализаторов (атрибутных МП-автоматов), которые решают задачи о принадлежности той или иной це­почки терминальных символов, снабженных атрибутами, языку, порождаемо­му заданной атрибутной грамматикой.

Определение 4.3.4. [17] Атрибутная трансляционная грамматика называется L-атрибутной тогда и только тогда, когда выполняются следующие три условия

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

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

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

Свойства L-атрибутности (L в данном случае — это сокращение, Left — левый) накладывает дополнительные ограничения на правила вычисления унас­ледованных и синтезированных атрибутов. Суть ограничений состоит в том, что унаследованные атрибуты данного символа зависят от информации, кото­рая находится слева от него. Вводимые же ограничения вычисления значений синтезированных атрибутов (условия 2 и 3) исключают круговую зависимость атрибутов.

Таким образом, если дана продукция грамматики АВС, где А, В, СN, то атрибуты символов А, В, С должны вычисляться в следующем порядке:

1) унаследованные атрибуты А;      

2) унаследованные атрибуты В;

3) синтезированные атрибуты В;

4) унаследованные атрибуты С;

5) синтезированные атрибуты С;

6) синтезированные атрибуты А.

Этот порядок соответствует обходу синтаксического дерева сверху вниз и слева направо: «спускаясь» вниз от вершины, вычисляем унаследованные атрибуты, «поднимаясь» вверх к вершине, вычисляем синтезированные атрибуты.

Пример 4.3.1. [17]. Покажем, как можно применять АТ-грамматику при по­строении компилятора на примере трансляции оператора присваивания неко­торого гипотетического языка программирования.

Пусть синтаксис оператора присваивания задается с помощью следующей КС-грамматики G = <М, Т, Р, S>, где

N = {S, E, K, P, R, L},

T = {(, ), *, +, i, :=};

S = {S};

P = {Si:= E

EKR

R+ KR

KPL

L*PL

Pi

p(E)}

Данная грамматика порождает операторы присваивания, в правой части ко­торых стоит арифметическое выражение, в состав которого входят операции * и +. Символ i обозначает идентификатор и снабжается целочисленным индексом — указателем на соответствующий элемент таблицы идентификаторов. Так оператор присваивания вида

r:=(b + c)*d

в этом случае записывается следующим образом

i₁:=(i₂+i₃)*i₄

и ему соответствует дерево разбора на рис. 4.9.

Рис. 4.9. Синтаксическое дерево разбора цепочки i₁:= (i₂+i₃)*i₄

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

{СЛОЖИТЬ}_{2, 3, 200} {УМНОЖИТЬ}_{200, 4, 201} {ПРИСВОИТЬ}_{1, 201}

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

Таким образом, наша задача состоит в том, чтобы средствами АТ-грамматики описать процесс перевода оператора присваивания в последовательность действий абстрактной машины. Для этой цели сначала по исходной КС-грам­матике построим трансляционную грамматику цепочечного перевода. Прави­ла Т-грамматики примут вид:

Si:= E{ПРИСВОИТЬ}

EKR

R+K{СЛОЖИТЬ} R

KPL

P*P{УМНОЖИТЬ} L

Pi

P(E)

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

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

У нетерминала S атрибутов нет. Нетерминалы Е, К, Р имеют по одному синтезированному атрибуту, значением этого атрибута является указатель на элемент таблицы, содержащий результат вычисления подвыражения, по­рожденного соответствующим нетерминалом. Нетерминалы R и L имеют по два атрибута, первый из которых является унаследованным, а второй — синтезированным.

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

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

Атрибутная грамматика, снабженная комментариями об атрибутах симво­лов, имеет следующий вид:

Ex – СИНТЕЗИРУЕМЫЙ х

К_х – СИНТЕЗИРУЕМЫЙ х

P_х – СИНТЕЗИРУЕМЫЙ х

R_x,y – УНАСЛЕДОВАННЫЙ x, СИНТЕЗИРУЕМЫЙ y

L_x,y – УНАСЛЕДОВАННЫЙ х, СИНТЕЗИРУЕМЫЙ y

{СЛОЖИТЬ}x, y, z – УНАСЛЕДОВАННЫЕ х, у, z

{УМНОЖИТЬ}x, y, z – УНАСЛЕДОВАННЫЕ х, у, z

{ПРИСВОИТЬ}x, y – УНАСЛЕДОВАННЫЕ х, у

1) Si_a1:=E_b1 {ПРИСВОИТЬ}_{a2, b2}

              a2a1 b2b1

2) E_b2K_a1R_{a2, b1}

              a2a1 b2b1

3) R_{a1, b2}+K_b1{СЛОЖИТЬ}_{a2, b2, c1} R_{c2, d1}

              a2a1 c2c1

              b2b1 d2d1

              c1НОВТ

4)

              a2a1

5) K_b2P_a1L_{a2, b1}

              a2a1 b2b1

6) L_{a1, d2}*K_b1{УМНОЖИТЬ} _{a2, b2, c1} L_c2d1

              a2a1 c2c1

              b2b1 d2d1

              c1НОВТ

7)

              a2a1

8) P_a2i_a1

              a2a1

9) P_a2(E_a1)

              a2a1

Предположим, что процедура НОВТ при обращении к ней выдает последова­тельные адреса ячеек памяти, начиная с адреса 200. Тогда входная последователь­ность i₁ := (i₂ + i₃) * i₄ имеет атрибутное дерево вывода, показанное на рис. 4.10.

Рис. 4.10. Атрибутное дерево вывода входной последовательности i₁ := (i₂ + i₃) * i₄

Активная цепочка имеет вид:

i₁:=(i₂+i₃{СЛОЖИТЬ}_{2, 3, 200})*i₄{УМНОЖИТЬ}_{200, 4, 201}{ПРИСВОИТЬ}_{1, 201}

а операционная ее часть выглядит следующим образом:

{СЛОЖИТЬ}_{2, 3, 200} {УМНОЖИТЬ}_{200, 4, 201} {ПРИСВОИТЬ}_{1, 201}

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