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

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

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

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

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

<wikitex>

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

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

Стоит отметить, что не существует гарантии наличия даже одного порядка обхода дерева разбора, при котором вычислятся все атрибуты в узлах. Рассмотрим для примера следующие нетерминалы $A$ и $B$:

Продукция	Семантические правила
$A \to B$	$A.s = B.i \\ B.i = A.s+1$

Данные правила циклические: невозможно вычислить ни $A.s$ в узле, ни $B.i$ в дочернем узле, не зная значение другого атрибута. Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов. </wikitex>

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

<wikitex>

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

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

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

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

</wikitex>

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

<wikitex> Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$ (здесь $\{ADD Шаблон:... \}$ и $\{MUL Шаблон:... \}$ — транслирующие символы. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):

Продукция	Семантические правила	Пояснения
$S \to E$	$S.val=E.val$
$E_0 \to E_1 + T\ \{ADD\ res = op_1 + op_2\}$	$ADD.op_1=E_1.val \\ ADD.op_2=T.val \\ E_0.val=ADD.res $	В фигурных скобках - действия транслирующего символа ADD. $op_1$, $op_2$ и $res$ - атрибуты транслирующего символа.
$E \to T$	$E.val=T.val$
$T_0 \to T_1 \times F \ \{MUL\ res = op_1 \times op_2\}$	$MUL.op_1=T.val \\ MUL.op_2=F.val \\ T_0.val=MUL.res$	В фигурных скобках - действия транслирующего символа MUL. $op_1$, $op_2$ и $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>

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

<wikitex>

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

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

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

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

</wikitex>

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

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

$ D \to TL \\ T \to int \mid real \\ L \to L,id \mid id $

Выпишем продукции (с транслирующими символами) и ассоциируем с ними семантические правила (здесь $\{ENTRY Шаблон:... \}$ - транслирующий символ. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):

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

В данном примере не требуется дерево разбора в явном виде. В данной реализации рекурсивные функции от нетерминалов получают на вход(если необходимо) наследуемые атрибуты узла и возвращают синтезируемые (результат вычислений соответствующего подвыражения). Как мы видим, $val$ - синтезируемый атрибут, $acc$ - наследуемый атрибут, $ADD$ - транслирующий символ.

E() : Node
    Node res = Node("E")
    switch (curToken)
        case n, '('  :
            res.addChild(T())
            temp = res.children[T].val
            res.addChild(E'(temp)) 
            break
        default :
            error("unexpected char")
    res.val = E'.val
    return res

E'(acc) : Node
    Node res = Node("E'")
    switch (curToken) 
        case '+' :
            consume('+')
            res.addChild(Node("+"))
            res.addChild(T())
            temp = res.children[T].val
            ADD.res = ADD(acc, temp)
            res.addChild(E'(ADD.res))
            res.val = res.children[E'].val
            break
        case '$', ')' :
            res.val = acc;
            break
        default :
            error("unexpected char")
     return res

F() : Node
    Node res = Node("F")
    switch (curToken)
        case n :
            consume(n)
            res.addChild(Node(curToken)) 
            res.val = n.val
            break
        case '(' :
            consume('(')
            res.addChild(Node("("))
            res.addChild(E())
            rev.val = res.children[E].val
            consume(')')
            res.addChild(Node(")"))
        default :
            error("unexpected char")
    return res

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

</wikitex>

Атрибуты в ANTLR

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

Рассмотрим для примера грамматику арифметических выражений с операторами [math]+-\times \div[/math], и выводом результата выражениая.

Вне продукций грамматики бывает нужно вставить в сгенерированный разборщик(для Java) package, import, а также некоторые поля и методы. Это делается с помощью @header и @members:

grammar Expr;
@header { package ru.ifmo.ctddev.wiki; import java.util.*; } 
@parser::members { 
    Map<String, Integer> memory = new HashMap<String, Integer>();
    int eval(int left, int op, int right) { 
        //...
    }
}

Стартовый нетерминал печатает резульат:

s : e { System.out.println($e.value);};

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

e returns [Integer value]:
    t {$value = $t.value;}
    (
        '+'   t {$value += $t.value;}
        | '-' t {$value -= $t.value;}
    )*;

t returns [Integer value]:
    f {$value = $f.value;}
    ( '*' f {$value *= $f.value;} )*;

f returns [Integer value]:
    '-' f {$value = $f.value;}
    | NUM {$value = Integer.parseInt($NUM.text);}
    | '(' e ')' {$value = $e.value;}
    ;

Техническая деталь для ANTLR, правила для лексического анализатора:

WS : [ \t \r \n]+ -> skip ;
NUM : [0-9]+ ;

В продукции для нетерминала e определяется возвращаемое значение ([Integer value]). Обращение к этому атрибуту имеет вид $e.value. В фигурных скобках записаны семантические правила.

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

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