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

При определении транслирующей грамматики в понятие входного символа не включалось представление о том, что он является лексемой и состоит из двух компонентов: типа и значения. На самом деле транслирующая грамматика способна описывать перевод только той части симво­ла, которая задает его тип. Рассмотрим, как можно расширить понятие грамматики цепочечного перевода, чтобы использовать при переводе оба компонента входного символа. Расширенная транслирующая грамматика получила название атри­бутной транслирующей грамматики (АТ-грамматики). АТ-грамматики были предложены Д. Кнутом [6] и в дальнейшем изучались ря­дом ученых. Материал данного подраздела в основном базируется на результатах, приведенных в [5], [7].

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

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

3.2.1. Синтезированные атрибуты

Рассмотрим получение АТ-грамматики из исходной транслирующей грамматики. Пусть задана транслирующая грамматика G₃^T (рис. 3.3), допускающая в качестве входа арифметические выражения, построен­ные из символов множества {с, +, , (, )}, где с – лексема, являющаяся целочисленной константой, и порождающая на выходе значение этого выражения. На рис. 3.4, а изображено дерево вывода для входной цепочки с₅ + с₂ с₈ (индексы обозначают значения лексем). Этой входной цепочке должна соответствовать выходная цепочка {ОТВЕТ}₂₁. Поскольку любое вхождение нетерминала Е, Т или Р в дерево вывода представляет собой некоторое подвыражение входного выражения, введем для каждого из символов Е, Т и Р по одному атрибуту, значением которого будет значение подвыражения, по­рождаемого этим нетерминалом. Входной символ с и операционный символ

S E {ОТВЕТ}

E E + T

E T

Т T P

T P

P ( E )

P c

Рис. 3.3

S

а б

Рис 3.4

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

Выберем для каждого атрибута каждого вхождения символа в правило вывода грамматики уникаль­ное имя и включим атрибуты в пра­вила вывода в виде подстрочных индексов соответствующих символов. Заметим, что одни и те же имена атрибутов можно использовать в нескольких правилах. Сопоставим каждому правилу вы­вода грамматики правило вычисления значения атрибута нетерминала из левой части правила, которому со­ответствует нетерминальная вершина дерева вывода. Рассмотрим, напри­мер, вершину Т дерева, изображенного на рис. 3.4, а. Правило вы­вода, примененное к этой вершине, имеет вид: Т Т Р. Оно определяет, что значение подвыражения, порожденного нетерми­налом из левой части правила, равно значению подвыражений, порожденных символами Р и Т из правой части правила, которые являются прямыми потомками вершины Т. Если р – атрибут симво­ла Т из левой части правила, а q и r – атрибуты символов Т и Р из правой части правила, то правило вычисления значения атрибута р будет иметь вид: p q r, где символ “” – знак операции присваивания. Таким образом, начиная с атрибу­тов входных символов и поднимаясь по дереву от кроны к корню, можно определить все значения атрибутов нетерминалов из левых частей правил вывода. Правила вычисления значений атрибутов для АТ-грамматики G₃^А, полученной по транслирующей граммати­ке G₃^T, приведены на рис. 3.5.

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

S E_q {ОТВЕТ}_r

r q

E_p E_q + T_r

p q + r

E_p T_q

p q

Е_p T_q P_r

p q r

T_p P_q

p q

P_p ( E_q )

p q

P_p c_q

p q

Рис. 3.5

Рассмотренные выше правила вычисления значений атрибутов не распространяются на атрибут операционного символа {ОТВЕТ}, который относится к классу унаследованных атрибутов.