3. Атрибутные транслирующие грамматики

В основе методов перевода, описываемых в данном учебном пособии, лежат концепции транслирующей грамматики и атрибутной транслирующей грамматики.

3.1. Транслирующие грамматики

Транслирующая грамматика – это КС-грамматика, множество терминалов которой разбито на множество входных и множество операционных символов.

Определение. Транслирующей грамматикой называется пятерка объектов G^T = < T_i , T_a, N, S, R >, где T_i – словарь входных символов, T_a – словарь операционных символов, N – нетерминальный словарь, S N –начальный символ транслирующей грамматики, R – конечное множество правил вывода вида A . Здесь A N, (T_i U T_a U N)^*.

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

Транслирующая грамматика G₀^T, описывающая перевод инфиксных арифметических выражений в ПОЛИЗ, приведена на рис. 3.1, а.

1. E E + T {+} (1) E E + T

2. E T (2) E T

3. T T P {} (3) T T P

4. T P (4) T P

5. P (E) (5) P (E)

6. P i { i ) (6) P i

а б

Рис. 3.1

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

Например, входной грамматикой G₀ для транслирующей грамматики G₀^T является КС-грамматика для инфиксных арифметических выражений, приведенная на рис.3.1, б.

Рассмотрим левый вывод цепочки i + i i во входной грамматике G₀.

E E + T T + T P + T i + T i + T P i + P P i + i P i + i i

Применив эту же последовательность правил к соответ­ствующим нетерминалам транслирующей грамматики G₀^T, получим следующий левый вывод:

E E + T {+} T + T {+} P + T {+} i { i } + T {+} i { i } + T P {} {+} i { i } + P P {} {+} i { i } + i { i } P {} {+} i { i } + i { i } i { i } {} {+}

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

Например, последовательность i + i i является входной частью активной цепочки i { i } + i { i } i { i } { } { + }, a последовательность

{ i } { i } { i }{ } { + } – ее операционной частью.

Определение. Множество всех пар, первыми элемен­тами которых являются входные части активной цепочки, а вторыми элементами –операционные части активной цепочки, называется синтаксически управляемым переводом (G^T), определяемым транслирующей грамматикой G^Т.

В восходящих методах обработки языков широко применяются постфиксные транслирующие грамматики.

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

Примером постфиксной транслирующей грамматики является грамматика G^T₀.

Для получения транслирующей грамматики входной язык описы­вается входной КС-грамматикой. Затем в правила вывода этой грамматики вставляются операционные символы для описания семантических действий, связанных с соответствующими правилами.

Рассмотрим получение транслирующей грамматики G₀^T по входной грамматике G₀. В ПОЛИЗ операнды располагаются в той же последовательнос­ти, что и в инфиксной записи, а знаки операций следуют непо­средственно после своих операндов в том порядке, в котором они выполняются. Для того чтобы идентификатор i выдавался сразу после его прочтения, правило (6) преобразуется к виду P i { i }. Чтобы знак операции сложения выдавался непосредственно после своих операндов, правило (1) заменяется на Е E + T {+}. Это правило интерпретирует­ся следующим образом: обработка арифметического выражения Е состоит из обработки первого операнда (Е), чтения символа “+”, обработки второго операнда (Т) и выдачи символа “+”. Аналогичные рассуждения позволяют следующим образом преобразовать правило (3):

Т T P {}.

Один и тот же перевод можно определить разными транслирующими грамматиками. Например, две транслирующие грамматики G₁^T и G₂^T, определяющие перевод в ПОЛИЗ инфиксных бесскобочных ариф­метических выражений, выполняемых в порядке написания опера­ций, приведены соответственно на рис. 3.2, а и 3.2, б.

(1) E E + T {+} (1) E i { i } R

(2) E T P {} (2) R + i { i } {+} R

3. E T (3) R i { i } { } R

4. Т i (4) R

а б

Рис. 3.2

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

Примером грамматики цепочечного перевода является грамма­тика G₀^T, приведенная на рис. 3.1, а.

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