Атрибутные транслирующие грамматики — различия между версиями

Версия 09:55, 5 июня 2015

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

Например, мы хотим не только построить дерево разбора для арифметических выражений, а ещё и вычислить значение этого выражения. Возможно, даже не строя само дерево разбора.

Такой подход называется Синтаксически управляемой трансляцией.

Содержание

1 Синтаксически управляемая трансляция
2 Синтезируемые атрибуты
- 2.1 Пример S-атрибутной грамматики
3 Наследуемые атрибуты
- 3.1 Пример L-атрибутной грамматики
4 Пример работы с атрибутами в нисходящем разборе
5 Атрибуты в ANTLR
6 Примечания
7 Источники информации

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

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

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

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

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

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

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

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

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

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

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

Транслирующий символ — нетерминал, который раскрывается в $\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>

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

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

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

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

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

</wikitex>

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

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

(Здесь $\{ADD Шаблон:... \}$ и $\{MUL Шаблон:... \}$ - транслирующие символы)

Продукция	Семантические правила
$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$).

аннотированное дерево разбора для 3*5+4

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

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

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

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

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

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

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

</wikitex>

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

<wikitex> Для наглядности рассмотрим грамматику объявления переменных: в начале строки идет тип, затем через запятую имена переменных. Примеры строк, разбираемых в ней: int a или real x,y,z и подобные. Выпишем продукции (с транслирующими символами) и ассоциируем с ними семантические правила:

Продукция	Семантические правила
$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.text \\ ENTRY.value=L.inh$
$L.id \to id\ \{ENTRY addtype(key, value)\}$	$ENTRY.key=id.text \\ ENTRY.value=L.inh$

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

аннотированное дерево разбора для real id1, id2, id3

</wikitex>

Пример работы с атрибутами в нисходящем разборе

<wikitex> Рассмотрим работы с атрибутами на примере $LL(1)$-грамматики арифметических выражений, которая уже была разобрана ранее и расширим код разборщика для нее:

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

E() : int
    T.val = T()
    E'.val = E'(T.val)
    return E'.val

E'(acc) : int
    switch (curToken) 
        case '+' :
            consume('+')
            T.res = T()
            ADD.res = ADD(acc, T.val)
            E'.val = E'(ADD.res)
            return E'.val
            break
        case '\varepsylon':
            return acc
        default 
            error("unexpected char")

F() : int
    switch (curToken)
        case n :
            consume(n)
            F.val = n.val
            return F.val
        case '(' :
            consume('(')
            F.val = E()
            consume(')')
            return F.val
        default :
            error("unexpected char")

Функции для $T$ и $T'$ строятся аналогично.

</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); System.out.println($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);} — транслирующий символ из определений, которые мы рассматривали в начале статьи.

Примечания

↑ ANTLR — Parser generator

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

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

[1] ANTLR — Parser generator

[1]

@@ Строка 168: / Строка 168: @@
 </wikitex>
+==Пример работы с атрибутами в нисходящем разборе==
+<wikitex>
+Рассмотрим работы с атрибутами на примере $LL(1)$-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Предиктивный_синтаксический_анализ | разборщика]] для нее:
+$
+E \to TE' \\
+E' \to +TE' \mid \varepsilon \\
+T \to FT' \\
+T' \to * FT' \mid \varepsilon \\
+F \to n \mid (E)
+$
+ E() : '''int'''
+     T.val = T()
+     E'.val = E'(T.val)
+     '''return''' E'.val
+ E'(acc) : '''int'''
+     '''switch''' (curToken)
+         '''case''' '+' :
+             consume('+')
+             T.res = T()
+             ADD.res = ADD(acc, T.val)
+             E'.val = E'(ADD.res)
+             '''return''' E'.val
+             '''break'''
+         '''case''' '\varepsylon':
+             '''return''' acc
+         '''default'''
+             <font color="red">error</font>("unexpected char")
+ F() : '''int'''
+     '''switch''' (curToken)
+         '''case''' n :
+             consume(n)
+             F.val = n.val
+             '''return''' F.val
+         '''case''' '(' :
+             consume('(')
+             F.val = E()
+             consume(')')
+             '''return''' F.val
+         '''default''' :
+             <font color="red">error</font>("unexpected char")
+Функции для $T$ и $T'$ строятся аналогично.
+</wikitex>
 ==Атрибуты в ANTLR==

Атрибутные транслирующие грамматики — различия между версиями

Версия 09:55, 5 июня 2015

Содержание

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

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

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

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

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

Пример работы с атрибутами в нисходящем разборе

Атрибуты в ANTLR

Примечания

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты