3.2.5. Форма простого присваивания

Ограничения, накладываемые на L-атрибутную транслирующую грамматику, позволяют вычислять значения атрибутов в процессе нисходящего анализа входной цепочки. Нисходящий детерминированный анализатор для LL(1)-грамматик требует, чтобы L-атрибутная транслирующая грамматика, описывающая перевод, имела форму простого присваивания.

При определении транслирующей грамматики в 3.2.3 правила вычисления атрибутов записывались в виде операторов присваивания, левые части которых представля­ют собой атрибут или список атрибутов, а правые части - функ­цию, использующую в качестве аргументов значения некоторых атрибутов. Простейший случай функции из правой части операто­ра присваивания – тождественная или константная функция, на­пример a b или x, y 1 .

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

Если источники нескольких правил совпадают, то их приемники можно объединить в одну левую часть. Например, правила z, w a и x, y z можно записать в виде: x, y, z, w a , так как источнику второго правила z, согласно первому пра­вилу, присваивается значение а. Аналогично x y и a, b y можно записать как a, b, x y.

Определение. Множество копирующих правил назы­вается независимым, если источник каждого правила из этого множества не входит ни в одно из других правил множества.

Если два копирующих правила независимы, их нельзя объединять.

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

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

2) для каждого правила вывода грамматики соответствующее множество копирующих правил независимо.

Примером АТ-грамматики в форме простого присваивания явля­ется грамматика G₅^А.

Рассмотрим процедуру преобразования произвольной L-атри­бутной транслирующей грамматики в эквивалентную L-атрибутную грамматику в форме простого присваивания. Смысл используемого здесь поня­тия эквивалентности объясняется дальше.

1. Для каждой функции f(x₁, x₂, …, x_n), входящей в пра­вило вычисления атрибутов, связанное с некоторым правилом вы­вода грамматики, создать соответствующий ей операционный сим­вол { f }, который определяется следующим образом:

{ f } _{x1, x2, …, xn, p} унаследованные x₁, x₂, …, x_n

синтезированный p

p f(x₁, x₂, …, x_n)

2. Для каждого некопирующего правила z₁, z₂, …, z_m f(y₁, y₂, …, y_n),

связанного с некоторым правилом вывода грамматики, найти сим­волы a1, …, an, которые не содержатся в этом правиле вывода, и вставить в его правую часть символ { f } _{a1,a2, …, an, r}. Заменить некопирующее правило на следующие n + 1 копирующих правил:

ai y_i для каждого аргумента y_i;

z₁, z₂, …, z_m r .

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

а) операционный символ должен располагаться правее всех символов правой части правила вывода, атрибутами которых яв­ляются аргументы y₁, y₂, …, y_n;

б) операционный символ должен располагаться левее всех символов правой части правила вывода, атрибутами которых служат z₁, z₂, …, z_m;

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

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

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

Рассмотрим пример преобразования L-атрибутной транслирующей грамматики, порождающей префиксные арифметические выражения над константами, в форму простого присваивания. Атрибутные правила вывода этой грамматики приведены на рис. 3.11.

E _p cинтезированный p

{ОТВЕТ} _r унаследованный r

(1) S E_p { ОТВЕТ } _r

r p

2. E_p + E_q E_r

p q + r

2. E_p E_q E_r

p q r

(4) E_p c _r

p r

Рис. 3.11

Входными символами грамматики являются: лексема с, представляющая целочисленную константу, и знаки арифметических операций: + и . Входной символ с имеет один атрибут, значением которого является значение константы. Нетерминальный символ Е и операционный символ {ОТВЕТ} также имеют по одному атрибуту. Значением синтезированного атрибута символа Е является значе­ние подвыражения, порождаемого этим символом, а значением унаследованного атрибута символа (ОТВЕТ) – значение всего вы­ражения, порождаемого грамматикой.

Исходная грамматика содержит два некопирующих правила: p q + r и p q r, правые части которых представляют собой функции "сложение" и "умножение" соответственно. Для преобразования заданной грамматики в форму простого присваивания введем операционные символы {СЛОЖИТЬ}_{A, B, R} и {УМНОЖИТЬ} _{A, B, R}, каждый из которых имеет по два унаследованных атрибута A и B и один синтези­рованный атрибут R. Для операционного символа {СЛОЖИТЬ} _{A, B, R} атрибутное правило имеет вид: R A + B, а для операционного символа {УМНОЖИТЬ} _{A, B, R} – R A B.

Для того чтобы преобразованная грамматика также была L-атрибутной, символ {СЛОЖИТЬ} необходимо поместить правее всех символов правой части правила вывода (2), так как одним из аргументов сложения является атрибут самого правого симво­ла Е. Атрибут, получающий в качестве своего значения результат сложения, в определении места расположения символа (СЛОЖИТЬ) не участвует, так как он не приписан ни одному из символов правой части. Аналогичные рассуждения относительно операционного символа {УМНОЖИТЬ} определяют крайнюю правую позицию правой части правила (3), как единственно возможное место расположения этого символа. Полученная в результате преобразования L-атрибутная грамматика в форме простого присваивания приведена на рис. З.12.

E _p cинтезированный p

{ОТВЕТ} _r унаследованный r

{СЛОЖИТЬ} _{A, B, R} унаследованный а, b

r a + b cинтезированный r

{УМНОЖИТЬ} _{A, B, R} унаследованный а, b

r a b cинтезированный r

(1) S E_p { ОТВЕТ } _r

r p

(2) E_p + E_q E_r {СЛОЖИТЬ} _{A, B, R}

A q B r p R

(3) E_p E_q E_r {УМНОЖИТЬ} _{A, B, R}

A q B r p R

(4) E_p c _r

p r

Рис. 3.12

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

18