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

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

Синтаксически управляемая трансляция

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

Синтаксически управляемое определение (СУО) является контекстно-свободной грамматикой с атрибутами и правилами. Атрибуты связаны с грамматическими символами, а правила — с продукциями.

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

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

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

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

Атрибут — дополнительные данные, ассоциированные с грамматическими символами.Если $X$ представляет собой символ, а $a$ — один из его атрибутов, то значение а в некотором узле дерева разбора, помеченном $X$, записывается как $X.a$. Если узлы дерева разбора реализованы в виде записей или объектов, то атрибуты X могут быть реализованы как поля данных в записях, представляющих узлы $X$. Атрибуты могут быть любого вида: числами, типами, таблицами ссылок или строками.

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

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

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

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

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

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

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

$ S \to 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 
$

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

Синтезируемые атрибуты

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

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

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

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

Пример S-атрибутной грамматики.

Выпишем синтексическ управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$:

продукции	Семантические правила
$S \to E$	$S.val=E.val$
$val\ E \to E + T\ \{ADD\ res = op_1 + op_2\}$	$ADD.op_1=E_1.val \\ ADD.op_2=T.val \\ E_0.val=ADD.res $
$E \to T$	$E.val=T.val$
$val\ T \to T \times F \ \{MUL\ res = op_1 + op_2\}$	$MUL.op_1=T.val \\ MUL.op_2=F.val \\ T_0.val=MUL.res$
$T \to F$	$T.val=F.val$
$F \to n$	$F.val=n.val$
$F \to (E)$	$F.val=E.val$

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

<картинка>

После такого разбора, в $S.val$ будет лежать вычисленное значение выражения. Можно, например сразу напечатеть его, добавив правило к нему правило {print(S.val)}.

Хотя всегда можно переписать синтаксически управляемое определение таким образом, чтобы использовать только синтезируемые атрибуты, зачастую более удобно и естественно воспользоваться также и наследуемыми атрибутами.

Наследуемые атрибуты

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

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

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

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

Пример L-атрибутной грамматики

Выпишем продукции и ассоциируем с ними семантические правила для грамматики объявления переменных:

Продукции	Семантические правила
$D \to TL$	$L.in = T.type$
$T \to int$	$T.type = integer$
$T \to real$	$T.type = real$
$L \to L,id\ \{ENTRY addtype(key, value)\}$	$L_1.in=L.in \\ ENTRY.key=id.entry \\ ENTRY.value=L.in$
$L.id \to id\ \{ENTRY addtype(key, value)\}$	$ENTRY.key=id.entry \\ ENTRY.value=L.in$

Семантическое правило $L.in = T.type$, связанное с продукцией $D \to TL$, определяет наследуемый атрибут $L.in$ как тип объявления. Затем приведенные правила распространяют этот тип вниз по дереву разбора с использованием атрибута $L.in$. Транслирующий символ ENTRY, связанный с продукциями для $L$, вызывает процедуру $addtype$ для добавления типа каждого идентификатора к его записи в таблице символов (по ключу, определяемому атрибутом $entry$).

<картинка>

Аспекты реализации

Рассмотрим некоторые аспекты реализации на более сложном примере.

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

T(): int
    T_1.val=T()
    consume('*')
    F.val=F()
    MUL.res = MUL(op1=T1.val, op2=F.val)
    return MUL.res

Заметим, что в рассматриваемой грамматике присутствует левая рекурсия, в связи с чем некоторые наши примеры имеют искусственный характер, хотя и являются наглядными.

Рассмотрим, что происходит с атрибутами при устранения левой рекурсии из грамматики. Пусть есть правила:

$ x\ A \to A \alpha \Leftrightarrow x=g(A_1, \alpha) \\ x\ A \to \beta \Leftrightarrow x=f(\beta) $

<картинка>

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

$ x\ A \to \beta A' \\ x\ A' \to \alpha A' \\ x\ A \to \varepsilon $

<картинка>

Более сложный пример

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

<картинки деревьев и псевдокод функций для грамматики до и после устранения левой рекурсии.>

<также пример генерации ассемблерного кода для стековой и регистровой машины.>

хоть немного про ANTLR - атрибуты.

</wikitex>

Источники информации

• Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Первое издание. 2003. Стр. 279 — 305.
• Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Второе издание. 2008. Стр. ??? — ???.
• ANTLR Documentation - Rule Attribute Definitions