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

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

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

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

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

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

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

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

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

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

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

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

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

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

$ E \to E + T \mid T \\ T \to T \times F \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-атрибутной, если с атрибутами выполняются только операции присваивания значений других атрибутов, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. То есть используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх, от листьев к корню.

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

Правило грамматики	Семантические правила
$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$ корня дерева разбора будет лежать вычисленное значение выражения. Для изящности можно добавить еще одно правило $S \to E$ и действие(семантическое правило) {print(E.val)}. Тогда сразу после разбора выражения будет напечатан его результат.

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

Рассмотрим пример с 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