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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Пример работы с атрибутами в нисходящем разборе)
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 9 участников)
Строка 10: Строка 10:
  
 
==Синтаксически управляемая трансляция==
 
==Синтаксически управляемая трансляция==
<wikitex>
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 60: Строка 59:
 
Данные правила циклические: невозможно вычислить ни $A.s$ в узле, ни $B.i$ в дочернем узле, не зная значение другого атрибута.  
 
Данные правила циклические: невозможно вычислить ни $A.s$ в узле, ни $B.i$ в дочернем узле, не зная значение другого атрибута.  
 
Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов.
 
Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов.
</wikitex>
 
  
 
==Синтезируемые атрибуты==
 
==Синтезируемые атрибуты==
<wikitex>
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 73: Строка 70:
 
Грамматика называется '''S-атрибутной''' ''(англ. S-attributed definition)'', если с атрибутами выполняются только операции присваивания значений других атрибутов, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. То есть в грамматике используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх, от листьев к корню.
 
Грамматика называется '''S-атрибутной''' ''(англ. S-attributed definition)'', если с атрибутами выполняются только операции присваивания значений других атрибутов, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. То есть в грамматике используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх, от листьев к корню.
 
}}
 
}}
</wikitex>
 
 
===Пример S-атрибутной грамматики===
 
===Пример S-атрибутной грамматики===
<wikitex>
 
 
Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$ (здесь $\{ADD {{...}} \}$ и $\{MUL {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующие символы]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):
 
Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$ (здесь $\{ADD {{...}} \}$ и $\{MUL {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующие символы]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):
  
Строка 117: Строка 112:
  
 
После такого разбора в $S.val$ будет лежать вычисленное значение выражения. Можно, например сразу напечатать его, добавив к нему правило $\{print(S.val)\}$.
 
После такого разбора в $S.val$ будет лежать вычисленное значение выражения. Можно, например сразу напечатать его, добавив к нему правило $\{print(S.val)\}$.
 
</wikitex>
 
  
 
==Наследуемые атрибуты==
 
==Наследуемые атрибуты==
  
<wikitex>
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 132: Строка 124:
 
Грамматика называется '''L-атрибутной''' ''(англ. L-attributed definition)'', если значения наследуемых атрибутов зависят только от родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа).
 
Грамматика называется '''L-атрибутной''' ''(англ. L-attributed definition)'', если значения наследуемых атрибутов зависят только от родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа).
 
}}
 
}}
</wikitex>
 
 
===Пример L-атрибутной грамматики===
 
===Пример L-атрибутной грамматики===
<wikitex>
 
 
Для наглядности рассмотрим грамматику объявления переменных  
 
Для наглядности рассмотрим грамматику объявления переменных  
 
(в начале строки идет тип, затем через запятую имена переменных. Примеры строк, разбираемых в ней: '''int a''' или '''real x,y,z''' и подобные):
 
(в начале строки идет тип, затем через запятую имена переменных. Примеры строк, разбираемых в ней: '''int a''' или '''real x,y,z''' и подобные):
Строка 171: Строка 161:
  
 
[[Файл:Real_id1,_id2,_id3.png|600px|center|thumb|Аннотированное дерево разбора для '''$\mathbf{real}\ id1,\ id2,\ id3$'''|600px]]
 
[[Файл:Real_id1,_id2,_id3.png|600px|center|thumb|Аннотированное дерево разбора для '''$\mathbf{real}\ id1,\ id2,\ id3$'''|600px]]
</wikitex>
 
  
 
==Пример работы с атрибутами в нисходящем разборе==
 
==Пример работы с атрибутами в нисходящем разборе==
<wikitex>
 
 
Рассмотрим работы с атрибутами на примере LL(1)-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Предиктивный_синтаксический_анализ | разборщика]] для нее:
 
Рассмотрим работы с атрибутами на примере LL(1)-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Предиктивный_синтаксический_анализ | разборщика]] для нее:
  
Строка 190: Строка 178:
 
  '''struct''' Node
 
  '''struct''' Node
 
     children : '''map<String, Node>'''
 
     children : '''map<String, Node>'''
     name: '''string'''
+
     name : '''string'''
 
     val : '''int'''                  <font color="green">// атрибут нетерминала</font>
 
     val : '''int'''                  <font color="green">// атрибут нетерминала</font>
 
     '''function''' addChild('''Node''')    <font color="green">// функция, подвешивающая поддерево к данному узлу</font>
 
     '''function''' addChild('''Node''')    <font color="green">// функция, подвешивающая поддерево к данному узлу</font>
Строка 251: Строка 239:
  
 
[[Файл:2add3add7.png|600px|center|thumb| Дерево разбора для '''$2\ +\ 3\ +\ 7$''']]
 
[[Файл:2add3add7.png|600px|center|thumb| Дерево разбора для '''$2\ +\ 3\ +\ 7$''']]
</wikitex>
 
  
 
==Атрибуты в ANTLR==
 
==Атрибуты в ANTLR==
  
Общедоступный генератора разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение.  
+
Общедоступный генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение.  
  
Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+ *</tex>, скобками и выводом результата выражениая пример на ANTLR.
+
Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+,\ *</tex>, скобками и выводом результата выражения пример на ANTLR.
  
 
  grammar Expression;
 
  grammar Expression;
Строка 264: Строка 251:
 
Естественным образом можно добавлять действия в продукции, где это нужно. Действия выполняются после предыдущего элемента грамматики и до следующего.
 
Естественным образом можно добавлять действия в продукции, где это нужно. Действия выполняются после предыдущего элемента грамматики и до следующего.
  
Стартовый нетерминал печатает резульат:
+
Стартовый нетерминал печатает результат:
  s : expr { System.out.println($e.value);};
+
  s : expr { System.out.println($expr.val); };
 +
 
 +
В продукции для нетерминала <code>expr</code> определяется возвращаемое значение (<code>['''int''' val]</code>). Обращение к этому атрибуту имеет вид <code>$expr.value</code>. В фигурных скобках записаны семантические правила.
  
 
Разобранные нетерминалы возвращают результат, вычисленный в поддереве(<code>returns [int val]</code>) как свой синтезируемый атрибут, процесс вычисления которого описан в фигурных скобках <code>{ $val = $exprP.val; }</code>.
 
Разобранные нетерминалы возвращают результат, вычисленный в поддереве(<code>returns [int val]</code>) как свой синтезируемый атрибут, процесс вычисления которого описан в фигурных скобках <code>{ $val = $exprP.val; }</code>.
Строка 276: Строка 265:
  
 
  exprP['''int''' i] '''returns''' ['''int''' val]
 
  exprP['''int''' i] '''returns''' ['''int''' val]
     :                                           { $val = $i; } <font color="green"> // <tex>\varepsilon</tex>-правило</font>
+
     :                                             { $val = $i; } <font color="green"> // <tex>\varepsilon</tex>-правило</font>
     | '+' term e = exprP[$i + $term.val]        { $val = $e.val; }
+
     | '+' term expr = exprP[$i + $term.val]        { $val = $expr.val; }
 
     ;
 
     ;
 
 
 
  term '''returns''' ['''int''' val]
 
  term '''returns''' ['''int''' val]
     : fact termP[$fact.val]    { $val = $termpP.val; }
+
     : fact termP[$fact.val]    { $val = $termP.val; }
 
     ;
 
     ;
  
 
  termP['''int''' i] '''returns''' '''[int''' val]
 
  termP['''int''' i] '''returns''' '''[int''' val]
     :                                           { $val = $i; }
+
     :                                             { $val = $i; }
     | '*' fact e = termP[$i * $fact.val]        { $val = $e.val; }
+
     | '*' fact expr = termP[$i * $fact.val]        { $val = $expr.val; }
 
     ;
 
     ;
  
Строка 297: Строка 286:
 
  WS : [ \t \r \n]+ -> skip ;
 
  WS : [ \t \r \n]+ -> skip ;
 
  NUM : [0-9]+ ;
 
  NUM : [0-9]+ ;
 
 
В продукции для нетерминала <code>e</code> определяется возвращаемое значение (<code>[Integer value]</code>). Обращение к этому атрибуту имеет вид <code>$e.value</code>. В фигурных скобках записаны семантические правила.
 
  
 
== Примечания ==
 
== Примечания ==

Текущая версия на 19:15, 4 сентября 2022

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

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

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

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

Определение:
Синтаксически управляемое определение (англ. 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 * 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$ в дочернем узле, не зная значение другого атрибута. Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов.

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

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


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

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

Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$ (здесь $\{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 * 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)\}$.

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

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


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

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

Для наглядности рассмотрим грамматику объявления переменных (в начале строки идет тип, затем через запятую имена переменных. Примеры строк, разбираемых в ней: 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_0 \to L_1,id\ \{ENTRY addtype(key, value)\}$ $L_1.inh = L0.inh \\ ENTRY.key=id.text \\ ENTRY.value=L_0.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$).

Аннотированное дерево разбора для $\mathbf{real}\ id1,\ id2,\ id3$

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

Рассмотрим работы с атрибутами на примере 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$ — транслирующий символ. Синим подсвечены строки, отвечающие за работу с атрибутами.

Здесь [math]\mathtt{Node}[/math] — структура следующего вида:

struct Node
    children : map<String, Node>
    name : string
    val : int                  // атрибут нетерминала
    function addChild(Node)    // функция, подвешивающая поддерево к данному узлу


E() : Node
    Node res = Node("E")
    switch (curToken)
        case n, '('  :
            res.addChild(T())            // подвешиваем левого сына
            temp = res.children["T"].val // атрибут левого сына
            Node rightSon = E'(temp)     // отдадим атрибут левого сына правому как наследуемый атрибут
            res.addChild(rightSon)       // подвешиваем правого сына сына
            res.val = res.children["E'"].val
            break
        default :
            error("unexpected char")
    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)  // ADD проведет вычисления из наследуемого атрибута add и атрибута ребенка "T"
            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'$ строятся аналогично.

Дерево разбора для $2\ +\ 3\ +\ 7$

Атрибуты в ANTLR

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

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

grammar Expression;
@header { package ru.ifmo.ctddev.wiki; } 

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

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

s : expr { System.out.println($expr.val); };

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

Разобранные нетерминалы возвращают результат, вычисленный в поддереве(returns [int val]) как свой синтезируемый атрибут, процесс вычисления которого описан в фигурных скобках { $val = $exprP.val; }.

Наследуемые атрибуты передаются нетерминалу как параметр(exprP[$term.val]).

expr returns [int val]
    : term exprP[$term.val]     { $val = $exprP.val; }
    ;
exprP[int i] returns [int val]
    :                                              { $val = $i; }  // [math]\varepsilon[/math]-правило
    | '+' term expr = exprP[$i + $term.val]        { $val = $expr.val; }
    ;
term returns [int val]
    : fact termP[$fact.val]     { $val = $termP.val; }
    ;
termP[int i] returns [int val]
    :                                              { $val = $i; }
    | '*' fact expr = termP[$i * $fact.val]        { $val = $expr.val; }
    ;
fact returns [int val]
    : '(' expr ')'                  { $val = $expr.val; }
    | NUM                           { $val = Integer.parseInt($NUM.text); }
    ;

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

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

Примечания

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

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