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

<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 $

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

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

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

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

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

Грамматика называется 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$ зависит только от детей, то есть синтезируемый атрибут. Результат умножителя ($MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемым(аналогично с сумматором ADD).

<картинка>

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