1632
правки
Изменения
м
<wikitex>Часто, осуществляя разбор, мы хотим извлечь какие-то данные или что-то сделать, а не просто выяснить, разбирается ли текст в данной грамматике.
Вообще говоря, сначала можно получить дерево разборы, а потом уже, обойдя дерево разбора, по нему производить какие-то действия.
В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда это дерево слишком расточительно хранить в памяти.
В связи с этим хочется какие-то действия производить уже на этапе разбора.
Такой подход называется '''Синтаксически управляемой трансляцией'''.
После Выпишем продукции (с транслирующими символами) и ассоциируем с ними семантические правила(здесь $\{ENTRY {{...}} \}$ {{---}} [[Устранение_левой_рекурсииАтрибутные_транслирующие_грамматики#tr_char| устранения левой рекурсиитранслирующий символ]] имеем следующее. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.): {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Продукция!style="background-color:#EEE"| Семантические правила|-|style="background-color:#FFF;padding:2px 30px"| $D \to TL$|style="background-color:#FFF;padding:2px 30px"| $L.inh = T.type$|-|style="background-color:#FFF;padding:2px 30px"| $T \to int$|style="background-color:#FFF;padding:2px 30px"| $T.type = integer$|-|style="background-color:#FFF;padding:2px 30px"| $T \to real$|style="background-color:#FFF;padding:2px 30px"| $T.type = real$|-|style="background-color:#FFF;padding:2px 30px"| $L_0 \to L_1,id\ \{ENTRY addtype(key, value)\}$|style="background-color:#FFF;padding:2px 30px"| $L_1.inh = L0.inh \\ ENTRY.key=id.text \\ ENTRY.value=L_0.inh$|-|style="background-color:#FFF;padding:2px 30px"| $L \to id\ \{ENTRY addtype(key, value)\}$|style="background-color:#FFF;padding:2px 30px"| $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.png|600px|center|thumb|Аннотированное дерево разбора для '''$\mathbf{real}\ id1,\ id2,\ id3$'''|600px]] ==Пример работы с атрибутами в нисходящем разборе==Рассмотрим работы с атрибутами на примере LL(1)-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Предиктивный_синтаксический_анализ | разборщика]] для нее:
Например, атрибутом терминала exprP['''int''' i] '''returns''' ['''int''' val] : { $nval = $ будет число, которое он представляет: (i; } <font color="green"> // <tex>\varepsilon</tex>-правило</font> | '+' term expr = exprP[$i + $nterm.val] { $val = 123$). Атрибутами нетерминалов будут значения, вычисленные в поддеревеexpr.val; } ; term '''returns''' ['''int''' val]В процессе трансляции происходит присваивание атрибутов одних элементов грамматики другим элементам грамматики, при этом присваивание может происходить более сложным способом, чем простое копирование : fact termP[$fact. В некоторых случаях могут быть нужны какие-то побочные эффекты, например вывод кода или взаимодействие с глобальным контекстом. Для этого нужны транслирующие символыval] { $val = $termP.val; } ;
Заменим правило $T \rightarrow T*F$ на следующее fact '''returns''' ['''int''' val] : '(' expr ')' { $T \rightarrow T*F\{T_0.val=T_1.val*F.val\}$, где $\{T_0.val=T_1.val*Fexpr.val\; }$ { | NUM {---}} транслирующий символ. Аналогично к $F \rightarrow n$ добавляется $\{F.val = nInteger.val\}parseInt($NUM.text); } ;
</wikitex>[[Категория: Методы трансляции]][[Категория: Нисходящий разбор]]
rollbackEdits.php mass rollback
Часто, осуществляя разбор, мы хотим извлечь какие-то данные или произвести какие-то действия, а не просто выяснить, разбирается ли текст в данной грамматике.
Вообще говоря, сначала можно получить [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора|дерево разбора]], а потом уже, обходя его, выполнять эти действия.
В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда его просто слишком расточительно хранить в памяти целиком.
В связи с этим хочется какие-то действия производить уже на этапе разбора.
Например, мы хотим не только построить дерево разбора для арифметических выражений, а ещё и вычислить значение этого выражения. Возможно, даже не строя само дерево разбора.
Такой подход называется '''синтаксически управляемой трансляцией'''.
==Синтаксически управляемая трансляция==
{{Определение
|definition =
'''Синтаксически управляемое определение''' {{''(англ. syntax-directed definition)'' является [[Контекстно-свободные_грамматики,_вывод,_лево-}} обобщение _и_правосторонний_вывод,_дерево_разбора|контекстно-свободной грамматики]] грамматикой с атрибутами и правилами. Атрибуты связаны с грамматическими символами, в которой каждый грамматический символ имеет связанное а правила — с ним множество атрибутовпродукциями.
}}
{{Определение
|definition =
'''Синтаксически управляемая трансляция''' ''(англ. syntax-directed translation)'' {{---}} это трансляция, при которой в [[Предиктивный_синтаксический_анализ| процессе разбора ]] строки сразу выполняются какие-то действия, не используя промежуточное представление без использования промежуточного представления в виде дерева разбора.
}}
{{Определение
|definition =
'''Атрибут''' ''(англ. attribute)'' {{---}} дополнительное поле дополнительные данные, ассоциированные с данными у терминалов грамматическими символами. Если $X$ представляет собой символ, а $a$ — один из его атрибутов, то значение $a$ в некотором узле дерева разбора, помеченном $X$, записывается как $X.a$. Если узлы дерева разбора реализованы в виде записей или объектов, то атрибуты $X$ могут быть реализованы как поля данных в записях, представляющих узлы $X$. Атрибуты могут быть любого вида: числами, типами, таблицами ссылок или строками.}} {{Определение|definition =Дерево разбора, в каждом узле которого атрибуты уже вычислены, называется '''аннотированным''' ''(англ. annotated)'', а процесс вычисления этих атрибутов {{---}} '''аннотированием''' дерева разбора.}} {{Определение|id = tr_char|definition ='''Транслирующий символ''' {{---}} нетерминал, который раскрывается в $\varepsilon$ и в момент раскрытия выполняет связанное с ним действие. Действия пишутся в фигурных скобках рядом с транслирующим символом.}} Будем рассматривать в качестве примера грамматику для арифметических выражений с операторами $+$ и $*$: $S \to E \\ E \to E + T \mid T \\T \to T * F \mid F \\F \to n \mid (E) $ Стоит отметить, что не существует гарантии наличия даже одного порядка обхода дерева разбора, при котором вычислятся все атрибуты в узлах. Рассмотрим для примера следующие нетерминалы $A$ и нетерминалов$B$: {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Продукция!style="background-color:#EEE"| Семантические правила|-|style="background-color:#FFF;padding:2px 30px"| $A \to B$|style="background-color:#FFF;padding:2px 30px"| $A.s = B.i \\ B.i = A.s+1$|}Данные правила циклические: невозможно вычислить ни $A.s$ в узле, ни $B.i$ в дочернем узле, не зная значение другого атрибута. Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов. ==Синтезируемые атрибуты=={{Определение|definition ='''Атрибут''', значение которого зависит от значений атрибутов детей данного узла или от других атрибутов этого узла, то атрибут называется '''синтезируемым''' ''(Более строгое определение требует ввести систему типовангл. synthesized attribute)''.
}}
{{Определение
|definition =
Грамматика называется '''Транслирующий символS-атрибутной''''' {{(англ. S---}} нетерминалattributed definition)'', который раскрывается в $\varepsilon$ и в момент раскрытия выполняет какое-то действиеесли с атрибутами выполняются только операции присваивания значений других атрибутов, которое с ним связаноа внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. Для простоты действия пишутся То есть в фигурных скобках в том местеграмматике используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх, где это нужноот листьев к корню.
}}
===Пример S-атрибутной грамматики===
Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$ (здесь $\{ADD {{...}} \}$ и $\{MUL {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующие символы]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Продукция
!style="background-color:#EEE"| Семантические правила
!style="background-color:#EEE"| Пояснения
|-
|style="background-color:#FFF;padding:2px 30px"| $S \to E$
|style="background-color:#FFF;padding:2px 30px"| $S.val=E.val$
|style="background-color:#FFF;padding:2px 30px"|
|-
|style="background-color:#FFF;padding:2px 30px"| $E_0 \to E_1 + T\ \{ADD\ res = op_1 + op_2\}$
|style="background-color:#FFF;padding:2px 30px"| $ADD.op_1=E_1.val \\ ADD.op_2=T.val \\ E_0.val=ADD.res $
|style="background-color:#FFF;padding:2px 30px"| В фигурных скобках {{---}} действия транслирующего символа ADD. $op_1$, $op_2$ и $res$ {{---}} атрибуты транслирующего символа.
|-
|style="background-color:#FFF;padding:2px 30px"| $E \to T$
|style="background-color:#FFF;padding:2px 30px"| $E.val=T.val$
|style="background-color:#FFF;padding:2px 30px"|
|-
|style="background-color:#FFF;padding:2px 30px"| $T_0 \to T_1 * F \ \{MUL\ res = op_1 \times op_2\}$
|style="background-color:#FFF;padding:2px 30px"| $MUL.op_1=T.val \\ MUL.op_2=F.val \\ T_0.val=MUL.res$
|style="background-color:#FFF;padding:2px 30px"| В фигурных скобках {{---}} действия транслирующего символа MUL. $op_1$, $op_2$ и $res$ {{---}} атрибуты транслирующего символа.
|-
|style="background-color:#FFF;padding:2px 30px"| $T \to F$
|style="background-color:#FFF;padding:2px 30px"| $T.val=F.val$
|style="background-color:#FFF;padding:2px 30px"|
|-
|style="background-color:#FFF;padding:2px 30px"| $F \to n$
|style="background-color:#FFF;padding:2px 30px"| $F.val=n.val$
|style="background-color:#FFF;padding:2px 30px"|
|-
|style="background-color:#FFF;padding:2px 30px"| $F \to (E)$
|style="background-color:#FFF;padding:2px 30px"| $F.val=E.val$
|style="background-color:#FFF;padding:2px 30px"|
|}
В нашем примере видно, что $val$ зависит только от детей в дереве разбора, то есть это синтезируемый атрибут. Результат умножителя ($MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемым(аналогично с сумматором $ADD$). [[Файл:3mul5add4.png|500px|thumb|center|Аннотированное дерево разбора для '''$3*5+4$''']] После такого разбора в $S.val$ будет лежать вычисленное значение выражения. Можно, например сразу напечатать его, добавив к нему правило $\{print(S.val)\}$. ==Наследуемые атрибуты== {{Определение|definition ='''Атрибут''', значение которого зависит от значений атрибутов братьев узла или атрибутов родителя, называется '''наследуемым''' ''(англ. inherited attribute)''. }} {{Определение|definition =Грамматика называется '''L-атрибутной''' ''(англ. L-attributed definition)'', если значения наследуемых атрибутов зависят только от родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа).}}===Пример L-атрибутной грамматики===Для наглядностирассмотрим грамматику объявления переменных (в начале строки идет тип, затем через запятую имена переменных. Примеры строк, на протяжении всей статьи будет рассматривать разбираемых в качестве примера грамматику для арифметических выраженийней: '''int a''' или '''real x,y,z''' и подобные): $ E D \to T + E \mid T TL \\T \to F \times T int \mid F real \\F L \to n L,id \mid (E)id
$
$
$
В данной реализации рекурсивные функции от нетерминалов получают на вход (если необходимо) наследуемые атрибуты узла и возвращают вершины дерева разбора, в атрибутах которых записан результат вычислений соответствующего подвыражения. Однако этот код легко изменить, чтобы он только вычислял значение выражения и не строил дерево разбора. Как мы видим, $val$ {{---}} синтезируемый атрибут, $acc$ {{---}} наследуемый атрибут, $ADD$ {{---}} транслирующий символ. Синим подсвечены строки, отвечающие за работу с атрибутами.
Здесь <tex>\mathtt{Node}</tex> {{---}} структура следующего вида:
'''struct''' Node
children : '''map<String, Node>'''
name : '''string'''
val : '''int''' <font color="green">// атрибут нетерминала</font>
'''function''' addChild('''Node''') <font color="green">// функция, подвешивающая поддерево к данному узлу</font>
E() : '''Node'''
Node res = Node("E")
'''switch''' (curToken)
'''case''' n, '(' :
res.addChild(T()) <font color="green">// подвешиваем левого сына</font>
<font color="blue">temp = res.children["T"].val</font> <font color="green">// атрибут левого сына</font>
<font color="blue">Node rightSon = E'(temp) </font> <font color="green">// отдадим атрибут левого сына правому как наследуемый атрибут</font>
<font color="blue">res.addChild(rightSon) </font> <font color="green">// подвешиваем правого сына сына</font>
<font color="blue">res.val = res.children["E'"].val</font>
'''break'''
'''default''' :
<font color="red">error</font>("unexpected char")
'''return''' res
E'(acc) : '''Node'''
Node res = Node("E'")
'''switch''' (curToken)
'''case''' '+' :
consume('+')
res.addChild(Node("+"))
res.addChild(T())
<font color="blue">temp = res.children["T"].val
ADD.res = ADD(acc, temp) <font color="green">// ADD проведет вычисления из наследуемого атрибута add и атрибута ребенка "T"</font>
res.addChild(E'(ADD.res)) <font color="green">// результат вычислений будет передан правому ребенку как наследуемый атрибут</font>
res.val = res.children["E'"].val</font>
'''break'''
'''case''' '$', ')' :
<font color="blue">res.val = acc</font>
'''break'''
'''default''' :
<font color="red">error</font>("unexpected char")
'''return''' res
F() : '''Node'''
Node res = Node("F")
'''switch''' (curToken)
'''case''' n :
consume(n)
res.addChild(Node(curToken))
<font color="blue">res.val = n.val</font>
'''break'''
'''case''' '(' :
consume('(')
res.addChild(Node("("))
res.addChild(E())
<font color="blue">rev.val = res.children["E"].val</font>
consume(')')
res.addChild(Node(")"))
'''default''' :
<font color="red">error</font>("unexpected char")
'''return''' res
Функции для $T$ и $T'$ строятся аналогично.
[[Файл:2add3add7.png|600px|center|thumb| Дерево разбора для '''$2\ +\ 3\ +\ 7$''']]
==Атрибуты в ANTLR==
Общедоступный генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение.
Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+,\ *</tex>, скобками и выводом результата выражения пример на ANTLR.
grammar Expression;
'''@header''' { package ru.ifmo.ctddev.wiki; }
Естественным образом можно добавлять действия в продукции, где это нужно. Действия выполняются после предыдущего элемента грамматики и до следующего.
Стартовый нетерминал печатает результат:
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>exprP[$term.val]</code>).
expr '''returns''' ['''int''' val]
: term exprP[$term.val] { $val = $exprP.val; }
;
termP['''int''' i] '''returns''' '''[int''' val]
: { $val = $i; }
| '*' fact expr = termP[$i * $fact.val] { $val = $expr.val; }
;
Техническая деталь для ANTLR, правила для лексического анализатора:
WS : [ \t \r \n]+ -> skip ;
NUM : [0-9]+ ;
== Примечания ==
<references/>
== Источники информации ==
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Первое издание. 2003. Стр. 279 {{---}} 305.
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Второе издание. 2008. Стр. 383 {{---}} 398.
* [https://theantlrguy.atlassian.net/wiki/display/ANTLR4/Parser+Rules#ParserRules ANTLR Documentation {{---}} Rule Attribute Definitions]
* [http://www.amazon.com/The-Definitive-ANTLR-4-Reference/dp/1934356999| The Definitive ANTLR 4 Reference]
