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

<wikitex>Часто, осуществляя разбор, мы хотим извлечь какие-то данные или что-то сделать, а не просто выяснить, разбирается ли текст в данной грамматике. Вообще говоря, сначала можно получить дерево разборы, а потом уже, обойдя дерево разбора, по нему производить какие-то действия. В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда это дерево слишком расточительно хранить в памяти. В связи с этим хочется какие-то действия производить уже на этапе разбора. Такой подход называется Синтаксически управляемой трансляцией.

Определение:

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

Определение:

Синтаксически управляемая трансляция — это трансляция, при которой в процессе разбора строки сразу выполняются какие-то действия, не используя промежуточное представление в виде дерева разбора.

Синтаксически управляемая трансляция вводит две новые сущности: атрибут и транслирующий символ.

Определение:

Атрибут — дополнительное поле с данными у терминалов и нетерминалов. (Более строгое определение требует ввести систему типов).

Определение:

Транслирующий символ — нетерминал, который раскрывается в $\varepsilon$ и в момент раскрытия выполняет какое-то действие, которое с ним связано. Для простоты, будем писать действия в фигурных скобках в том месте, где это нужно.

На протяжении всей статьи будет рассматривать в качестве примера грамматику для арифметических выражений:

$ E \to T + E \mid T \\ T \to F \times T \mid F \\ F \to n \mid (E) $

После устранения левой рекурсии имеем следующее:

$ E \to TE' \\ E' \to +TE' \mid \varepsilon \\ T \to FT' \\ T' \to * FT' \mid \varepsilon \\ F \to n \mid (E) $

Например, атрибутом терминала $n$ будет число, которое он представляет: ($n.val = 123$). Атрибутами нетерминалов будут значения, вычисленные в поддереве. В процессе трансляции происходит присваивание атрибутов одних элементов грамматики другим элементам грамматики, при этом присваивание может происходить более сложным способом, чем простое копирование. В некоторых случаях могут быть нужны какие-то побочные эффекты, например вывод кода или взаимодействие с глобальным контекстом. Для этого нужны транслирующие символы.

Заменим правило $T \rightarrow T*F$ на следующее: $T \rightarrow T*F\{T_0.val=T_1.val*F.val\}$, где $\{T_0.val=T_1.val*F.val\}$ — транслирующий символ. Аналогично к $F \rightarrow n$ добавляется $\{F.val = n.val\}$.

Часто бывает неоптимально для каждого действия заводить транслирующий символ(добавляется лишний нетерминал в грамматику). Поэтому при простом присваивании(копировании) атрибутов разрешают не выносить транслирующий символ и заменяют его списком действий, привязанным к правилу.

Обычно, транслирующий символ может работать только со своими атрибутами. Тогда перепишем правило $T \rightarrow T*F$ в виде: $T \rightarrow T*F\ \{MUL \ res = op_1*op_2\}$

И ассоциируем с ним следующий список действий, которые будут выполняться в особом порядке, рассмотренном далее. $ MUL.op_1 = T_1.val \\ MUL.op_2 = F.val \\ T_0.val = MUL.res $

Атрибуты делятся на наследуемые и синтезируемые.

Определение:

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

В нашем примере видно, что $.val$ зависит только от детей, то есть синтезируемый атрибут. Результат умножителя ($MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемым.

Определение:

Грамматика называется L-атрибутной, если значения наследуемых атрибутов зависят только тот родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа).

Определение:

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

При реализаци методом рекурсивного спуска, каждому нетерминалу соответствует некая рекурсивная функция, которая ранее возвращала дерево разбора соответствующего узла. Теперь же функция, соответствующая некоторому нетерминалу $A$, будет принимать в качестве аргументов его наследуемые атрибуты, а возвращать его синтезируемые атрибуты.

</wikitex>