Изменения

Часто, осуществляя разбор, мы хотим извлечь какие-то данные или чтопроизвести какие-то сделатьдействия, а не просто выяснить, разбирается ли текст в данной грамматике.Вообще говоря, сначала можно получить [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора|дерево разборыразбора]], а потом уже, обойдя дерево разбораобходя его, по нему производить какие-то выполнять эти действия.В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда это дерево его просто слишком расточительно хранить в памятицеликом.В связи с этим хочется какие-то действия производить уже на этапе разбора. Такой подход называется '''Синтаксически управляемой трансляцией'''.

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

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

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

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

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

'''Транслирующий символ''' {{---}} нетерминал, который раскрывается в $\varepsilon$ и в момент раскрытия выполняет какое-то действие, которое связанное с ним связанодействие. Для простоты, будем писать действия Действия пишутся в фигурных скобках в том месте, где это нужнорядом с транслирующим символом.

T \to T \times * F \mid F \\

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

!style="background-color:#EEE"| продукцииПродукция

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

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

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

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

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

Выпишем синтексически синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$(здесь $\{ADD {{...}} \}$ и $\{MUL {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующие символы]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):

!style="background-color:#EEE"| продукцииПродукция

|style="background-color:#FFF;padding:2px 30px"| $val\ E E_0 \to E E_1 + T\ \{ADD\ res = op_1 + op_2\}$

|style="background-color:#FFF;padding:2px 30px"| $val\ T T_0 \to T \times T_1 * F \ \{MUL\ res = op_1 * \times op_2\}$

В нашем примере видно, что $.val$ зависит только от детейв дереве разбора, то есть это синтезируемый атрибут. Результат умножителя ($MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемым(аналогично с сумматором $ADD$).

[[Файл:3mul5add4.png|600px500px|thumb|center|аннотированное Аннотированное дерево разбора для '''$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 {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующий символ]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):

!style="background-color:#EEE"| ПродукцииПродукция

|style="background-color:#FFF;padding:2px 30px"| $L L_0 \to LL_1,id\ \{ENTRY addtype(key, value)\}$|style="background-color:#FFF;padding:2px 30px"| $L_1.ininh =LL0.inh \\ ENTRY.key=id.entry text \\ ENTRY.value=LL_0.inh$

|style="background-color:#FFF;padding:2px 30px"| $L.id \to id\ \{ENTRY addtype(key, value)\}$|style="background-color:#FFF;padding:2px 30px"| $ENTRY.key=id.entry text \\ ENTRY.value=L.inh$

Семантическое правило $L.inh = T.type$, связанное с продукцией $D \to TL$, определяет наследуемый атрибут $L.inh$ как тип объявления. Затем приведенные правила распространяют этот тип вниз по дереву разбора с использованием атрибута $L.inh$. Транслирующий символ $ENTRY$, связанный с продукциями для $L$, вызывает процедуру $addtype$ для добавления типа каждого идентификатора к его записи в таблице символов (по ключу, определяемому атрибутом $entrytext$). [[Файл:Real_id1,_id2,_id3.png|600px|center|thumb|Аннотированное дерево разбора для '''$\mathbf{real}\ id1,\ id2,\ id3$'''|600px]]</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)$ В данной реализации рекурсивные функции от нетерминалов получают на вход (если необходимо) наследуемые атрибуты узла и возвращают вершины дерева разбора, в атрибутах которых записан результат вычислений соответствующего подвыражения. Однако этот код легко изменить, чтобы он только вычислял значение выражения и не строил дерево разбора. Как мы видим, $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'$ строятся аналогично.

[[Файл:Real_id1,_id2,_id32add3add7.png|600px|center|thumb|аннотированное дерево Дерево разбора для '''real id1, id2, id3$2\ +\ 3\ +\ 7$'''|600px]]

==Атрибуты в ANTLR== Общедоступный генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение.

Общедоступный генератора разборщиков ANTLRРассмотрим для той же грамматики арифметических выражений с операторами <reftex>[http://www.antlr.org/ ANTLR {{---}} Parser generator]+,\ *</reftex> поддерживает синтаксически управляемое определение. Рассмотрим для примера грамматику арифметических выражений, скобками и выводом результата выражения пример на ANTLR.

Вне продукций граматики бывает нужно вставить в сгенерированный разборщик(пример для Java) package или import, а также некоторые поля и методы. Это делается с помощью grammar Expression; '''@header''' и '''@members''':{ package ru.ifmo.ctddev.wiki; }

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) { .где это нужно.Действия выполняются после предыдущего элемента грамматики и до следующего. } }

Естественным образом можно добавлять действия в продукции, где это нужноСтартовый нетерминал печатает результат: stats : e NEWLINE expr {System.out.println($eexpr.val);} | ID '=' e NEWLINE {memory.put($ID.text, $e.val);} | NEWLINE ;

Действия выполняются после предыдущего элемента грамматики и до следующегоВ продукции для нетерминала <code>expr</code> определяется возвращаемое значение (<code>['''int''' val]</code>). В данном примере действия добавлены на конце альтернативы, поэтому действие выполнится после того, как разборщик распознает все выражениеОбращение к этому атрибуту имеет вид <code>$expr. Когда разборщик встречает выражение, за которым идет символ новой строки, ему нужно напечатать результатvalue</code>. Когда он встречает присваивание - ему нужно записать имя и значение переменной в памятьВ фигурных скобках записаны семантические правила.

e returns Наследуемые атрибуты передаются нетерминалу как параметр(<code>exprP[int $term.val] : a=e op=('*'|'</'code>) 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]) для expr '''ereturns'''. Это именно тот атрибут, на который ссылается ['''$e.valint''' в примерах вышеval] : term exprP[$term.Во второй строке, присваивания '''a=e''' и '''b=e''' иллюстрируют семантические правила, а действие '''val] {$val = eval($aexprP.val, $op.type, $b.val);}''' {{---}} транслирующий символ из определений, которые мы рассматривали в начале статьи. ;

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

* [https://theantlrguy.atlassian.net/wiki/display/ANTLR4/Parser+Rules#ParserRules-RuleAttributeDefinitions| ANTLR Documentation {{--- }} Rule Attribute Definitions]