Атрибутные транслирующие грамматики
Часто, осуществляя разбор, мы хотим извлечь какие-то данные или что-то сделать, а не просто выяснить, разбирается ли текст в данной грамматике. Вообще говоря, сначала можно получить дерево разборы, а потом уже, обойдя дерево разбора, по нему производить какие-то действия. В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда это дерево слишком расточительно хранить в памяти. В связи с этим хочется какие-то действия производить уже на этапе разбора. Такой подход называется Синтаксически управляемой трансляцией.
Содержание
Синтаксически управляемая трансляция
<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) $
Стоит отметить, что не существует гарантии наличия даже одного порядка обхода для вычисления всех атрибутов в узлах дерева разбора. Рассмотрим, например, нетерминалы $A$ и $B$:
| продукции | Семантические правила |
|---|---|
| $A \to B$ | $A.s = B.i \\ B.i = A.s+1$ |
Данные правила циклические; невозможно вычислить ни $A.s$ в узле,ни $B.i$ в дочернем узле, не зная значение другого атрибута. Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов. </wikitex>
Синтезируемые атрибуты
<wikitex>
| Определение: |
| Атрибут, значение которого зависит от значений атрибутов детей узла или от других атрибутов этого узла, то атрибут называется синтезируемым. |
| Определение: |
| Грамматика называется S-атрибутной, если с атрибутами выполняются только операции присваивания значений других атрибутов, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. То есть используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх, от листьев к корню. |
</wikitex>
Пример S-атрибутной грамматики.
<wikitex> Выпишем синтексически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$:
| продукции | Семантические правила |
|---|---|
| $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)\}$.
Хотя всегда можно переписать синтаксически управляемое определение таким образом, чтобы использовать только синтезируемые атрибуты, зачастую более удобно и естественно воспользоваться также и наследуемыми атрибутами. </wikitex>
Наследуемые атрибуты
<wikitex>
| Определение: |
| Атрибут, значение которого зависит от значений атрибутов братьев узла или атрибутов родителя, называется наследуемым. |
| Определение: |
| Грамматика называется L-атрибутной, если значения наследуемых атрибутов зависят только тот родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа). |
</wikitex>
Пример L-атрибутной грамматики
<wikitex> Выпишем продукции и ассоциируем с ними семантические правила для грамматики объявления переменных:
| Продукции | Семантические правила |
|---|---|
| $D \to TL$ | $L.inh = 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.inh \\ ENTRY.key=id.entry \\ ENTRY.value=L.inh$ |
| $L.id \to id\ \{ENTRY addtype(key, value)\}$ | $ENTRY.key=id.entry \\ ENTRY.value=L.inh$ |
Семантическое правило $L.inh = T.type$, связанное с продукцией $D \to TL$, определяет наследуемый атрибут $L.inh$ как тип объявления. Затем приведенные правила распространяют этот тип вниз по дереву разбора с использованием атрибута $L.inh$. Транслирующий символ ENTRY, связанный с продукциями для $L$, вызывает процедуру $addtype$ для добавления типа каждого идентификатора к его записи в таблице символов (по ключу, определяемому атрибутом $entry$).
<картинка> </wikitex>
Атрибуты в ANTLR
Общедоступный генератора разборщиков ANTLR[1] поддерживает синтаксически управляемое определение. Рассмотрим для примера грамматику арифметических выражений.
Вне продукций граматики бывает нужно вставить в сгенерированный разборщик(пример для Java) package или import, а также некоторые поля и методы. Это делается с помощью @header и @members:
grammar Expr;
@header { package tools; import java.util.*; }
@parser::members {
Map<String, Integer> memory = new HashMap<String, Integer>();
int eval(int left, int op, int right) {
...
}
}
Естественным образом можно добавлять действия в продукции, где это нужно:
stat: e NEWLINE {System.out.println($e.val);}
| ID '=' e NEWLINE {memory.put($ID.text, $e.val);}
| NEWLINE ;
Действия выполняются после предыдущего элемента грамматики и до следующего. В данном примере действия добавлены на конце альтернативы, поэтому действие выполнится после того, как разборщик распознает все выражение. Когда разборщик встречает выражение, за которым идет символ новой строки, ему нужно напечатать результат. Когда он встречает присваивание - ему нужно записать имя и значение переменной в память.
Правило для e теперь выглядит следующим образом:
e returns [int val]
: a=e op=('*'|'/') b=e {$val = eval($a.val, $op.type, $b.val);}
| a=e op=('+'|'-') b=e {$val = eval($a.val, $op.type, $b.val);}
| INT {$val = $INT.int;}
| ID {
String id = $ID.text;
$v = memory.containsKey(id) ? memory.get(id) : 0;
}
| '(' e ')' {$val = $e.val;} ;
В первой строке здесь определяется возвращаемое значение ([int val]) для e. Это именно тот атрибут, на который ссылается $e.val в примерах выше. Во второй строке, присваивания a=e и b=e иллюстрируют семантические правила, а действие {$val = eval($a.val, $op.type, $b.val);} — транслирующий символ из определений, которые мы рассматривали в начале статьи.
Примечания
Источники информации
- Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Первое издание. 2003. Стр. 279 — 305.
- Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Второе издание. 2008. Стр. 383 — 398.
- ANTLR Documentation - Rule Attribute Definitions
