Пред.Страница След.Страница Раздел Содержание
7.4. Определение атрибутов и построение АТ-грамматики
Напомним, что для построения нисходящего АТ‑преобразователя, необходимо использовать левостороннюю атрибутную грамматику простого присваивания. Построение грамматики будем выполнять, полагая, что все операции присваивания и чтения значений атрибутов должны выполняться символами действия.
Условимся также, что для обозначения атрибутов в такой грамматике будем использовать идентификаторы, состоящие из строчных букв и целых чисел с предшествующей точкой. Например, <Терм>.c1 или {MAS}.x10.y10. При таком способе обозначения синтезируемые и наследуемые атрибуты записываются одинаково, поэтому для указания вида атрибутов введем описание вида, которое должно предшествовать правилам грамматики. Описание должно состоять из указателя вида (синтезируемые или наследуемые) и списка атрибутов. Например,
Наследуемые q1,q2,q3;
Построение атрибутной грамматики начнем с определения атрибутов символов действия, а затем определим атрибуты нетерминальных символов.
Символу
действия {STP}, выполняющему
формирование кода типа переменных описания, придадим один атрибут, который должен
возвращать код типа.
{6}.a1;
Символу
действия {MVR}, выполняющему
извлечение атрибута токена и построение записи в таблице TVR,
придадим один синтезируемый атрибут, значением которого должен быть код типа
переменной.
{5}.b1;
Символу действия {CVR}, выполняющему проверку вхождения переменной в таблицу TVR, назначим также один атрибут:
{CVR}.c1;
Символы действия, создающие атомы для двуместных операций, должны получать указатели на значения двух операндов и возвращать указатель на строку результата в таблице VariableTable. Следовательно, символы действия {MAN} и {MOR} должны иметь по три атрибута:
{3}.x1.x2.x3 и {2}.x4.x5.x6.
Символ действия {MNT} соответствует операции, имеющей только один операнд. Кроме того, он должен возвращать указатель на строку результата в таблице VariableTable. Следовательно, он должен иметь только два атрибута:
{4}.у1.у2.
Операция присваивания предполагает сохранение результата, полученного в правой части оператора, поэтому символу действия {MAS} придадим два атрибута, представляющих собой указатели таблицы VariableTable на переменную левой части оператора, и результат вычисления правой части:
{1}.z1.z2.
Для определения атрибутов нетерминальных символов нужно четко представлять их назначение и использование в процессе построения вывода. При этом необходимо помнить, что при замене нетерминального символа левой части правила грамматики в процессе вывода, правой частью правила для вычисления значений атрибутов должны быть использованы атрибуты заменяемого символа. В качестве иллюстрации способа определения атрибутов рассмотрим несколько примеров.
Так, построение атома для оператора присваивания, должно выполняться с помощью следующих правил транслирующей грамматики:
<Оператор> ::=
"Идентификатор"{CVR} <Про_оператор>
<Про_оператор>
::= "=" <Выражение> {MAS}";"
Собственно построение атома оператора присваивания выполняется с помощью символа действия {MAS}, которому припишем два атрибута - z1 и z2. Значением первого атрибута – z1 должен быть указатель на переменную, расположенную в левой части оператора присваивания, а второй атрибут - z2 должен сохранять указатель на значение правой части оператора. Однако указатель на переменную левой части оператора определяется в первом правиле символом действии {CVR}.Чтоб передать это значение
символу {MAS}, припишем символу {CVR} атрибут c1, а для передачи значения этого атрибута следующему правилу придадим нетерминальному символу <Про_оператор> атрибут j1, значение которого должно определяться правилом присваивания j1 = c1. Таким образом, после подстановки в первое правило вместо термина <Про_оператор> атрибут z1 может получить значение, хранящееся в c1, с помощью присваивания z1 = j2.Значение правой части оператора присваивания формируется в результате построения вывода символа <Выражение>, поэтому придадим этому символу атрибут k1, значение которого присвоим
атрибуту z2. В результате получаем правила атрибутной грамматики в следующем виде:
<Оператор> ::=
Идентификатор"{CVR}.c1 <Про_оператор> j1
/ j1 = c1;
<Про_оператор>.j2 ::= "="
<Выражение>.k1 {MAS}.z1.z2";"
/ z1 = j2, z2 = k1;
Рассуждая аналогичным образом, приходим к выводу, что нетерминальные символы <Терм>, <Фактор> и <Факт> так же должны иметь по одному синтезированному атрибуту:
<Терм>.l1, <Фактор>.p1, <Факт>.s1;
Нетерминальные символы <Про_выражение> и <Про_терм> должны, во-первых, принимать значения атрибутов, сформированных на последующих шагах вывода и, во-вторых, предавать эти значения атрибутам предыдущих шагов, поэтому присоединим к каждому символу по два синтезируемых атрибута.
<Про_выражение>.m1.n1 , <Про_терм>.q1.r1;
В результате получаем правила атрибутной грамматики в виде:
<Про_выражение>.m2.n2 ::= "|" <Терм>l2{MOR}.x1.x2.x3
<Про_выражение>.m3.n3 / m2=m3, x1=l2, x2=n2, n3=x3;
< Про_терм >.q2.r2 ::= "&" <Фактор>.p2{2}.x4.x5.x6
< Про_терм 13>.q3.r3 / q2=q3, x4=p2, x5=r2, r3=x6;
В
нашей грамматике содержатся два заключительных правила вида:
<Про_выражение>.m4.n4 ::= $ / m4=n4;
< Про_терм >.q4.r4 ::= $ / q4=r4;
Учитывая,
что присваивание значений атрибутам должны выполнять символы действия,
перепишем заключительные правила, используя символ {PAT} , следующим образом:
<Про_выражение>.m4.n4 ::=
{8} / m4=n4;
< Про_терм >.q4.r4 ::= {8} / q4=r4;
Построенная
атрибутная грамматика, использующая ссылки на таблицы нетерминальных символов и
символов действия, имеет вид:
Hаследуемые:j1, j2, f1, f2, g1, g2, g3, g4;
1. <1> ::= {<2> <3>}
2. <2> ::= "bool"{6}.a1 <4>.f1 / f1=a1
3. <3> ::= <6><7>
4. <4>.f2 ::=":""Идентификатор"{5}.b1<5>.g1
/ b1=f2, g1=f2
5. <5>.g2 ::=",""Идентификатор"{5}.b2<5>.g3
/ b2=g2, g3=g2
6. <5>.g4 ::= ";"
7. <6> ::= "Идентификатор"{7}.c1<8>.j1 / j1=c1
8. <7> ::= <6><7>
9. <7> ::= $
10.
<8>.j2 ::=
"="<9>.k1{1}.d1.d2";" / d1=j2, d2=k1
11.
<9>.k2 ::= <10>.l1<11>.m1.n1 / k2=m1, n1=l1
12.
<10>.l3 ::= <12>.p1<13>.q1.r1 / l3=q1, r1=p1
13.
<11>.m2.n2 ::= "|" <10>l2{3}.x1.x2.x3<11>.m3.n3
/ m2=m3, x1=l2, x2=n2, n3=x3
14.
<11>.m4.n4 ::= {8} / m4=n4
15.
<12>.p3
::= "~"<14>.s1{4}.y1.y2 / y1=s1, p3=y2
16.
<12>.p2
::= <14>.s2 / p2=s2
17.
<13>.q2.r2
::= "&" <12>.p2{2}.x4.x5.x6<13>.q3.r3
/ q2=q3, x4=p2, x5=r2,
r3=x6
18.
<13>.q4.r4
::= {8} / q4=r4
19.
<14>.s3::="Идентификатор"{7}.c2 / s3=c2
20.
<14>.s4::=
"("<9>.k3")" /
s4=k3
21.
<14>.s5::=
"false"{9}.t1 / s5=t1
22.
<14>.s6::=
"true"{9}.t2 / s6=t2
Пред.Страница След.Страница Раздел Содержание