Изменения

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

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

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

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

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

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

</wikitex>===Пример S-атрибутной грамматики.==<wikitex>=Выпишем синтексически синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$(здесь $\{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|аннотированное 500px|thumb|center|Аннотированное дерево разбора для '''$3*5+4|600px$''']]

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

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

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

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

</wikitex>===Пример L-атрибутной грамматики===Для наглядности рассмотрим грамматику объявления переменных (в начале строки идет тип, затем через запятую имена переменных. Примеры строк, разбираемых в ней: '''int a''' или '''real x,y,z''' и подобные): $D \to TL \\T \to int \mid real \\L \to L,id \mid id$ <wikitex>Выпишем продукции (с транслирующими символами) и ассоциируем с ними семантические правила для грамматики объявления переменных(здесь $\{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]] ==Пример работы с атрибутами в нисходящем разборе==Рассмотрим работы с атрибутами на примере 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'$ строятся аналогично. [[Файл:2add3add7.png|600px|center|thumb| Дерево разбора для '''$2\ +\ 3\ +\ 7$''']] ==Атрибуты в ANTLR== Общедоступный генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение.  Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+,\ *</tex>, скобками и выводом результата выражения пример на ANTLR.

[[Файл:Real_id1,_id2,_id3 grammar Expression; '''@header''' { package ru.ifmo.ctddev.png|аннотированное дерево разбора для 3*5+4|600px]]</wikitex>wiki; }

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

Общедоступный генератора разборщиков ANTLR<ref>[httpСтартовый нетерминал печатает результат://www s : expr { System.out.antlrprintln($expr.org/ ANTLR {{---}val); } Parser generator]</ref> поддерживает синтаксически управляемое определение. Рассмотрим для примера грамматику арифметических выражений.;

Вне продукций граматики бывает нужно вставить в сгенерированный разборщикВ продукции для нетерминала <code>expr</code> определяется возвращаемое значение (пример для Java) package или import, а также некоторые поля и методы. Это делается с помощью <code>['''@headerint''' и '''@members''':val]</code>). Обращение к этому атрибуту имеет вид <code>$expr.value</code>. В фигурных скобках записаны семантические правила.

grammar Expr; @header { package tools; import java.util.*; } @parser::members { MapРазобранные нетерминалы возвращают результат, вычисленный в поддереве(<String, Integercode> memory = new HashMapreturns [int val]<String, Integer/code>(); int eval(int leftкак свой синтезируемый атрибут, int op, int right) процесс вычисления которого описан в фигурных скобках <code>{ .$val = $exprP.val; }</code>. } }

Естественным образом можно добавлять действия в продукции, где это нужно: stat: e NEWLINE {System.out.printlnНаследуемые атрибуты передаются нетерминалу как параметр(<code>exprP[$eterm.val]</code>);} | ID '=' e NEWLINE {memory.put($ID.text, $e.val);} | NEWLINE ;

Действия выполняются после предыдущего элемента грамматики и до следующего expr '''returns''' ['''int''' val] : term exprP[$term. В данном примере действия добавлены на конце альтернативы, поэтому действие выполнится после того, как разборщик распознает все выражение. Когда разборщик встречает выражение, за которым идет символ новой строки, ему нужно напечатать результат. Когда он встречает присваивание - ему нужно записать имя и значение переменной в памятьval] { $val = $exprP.val; } ;

Правило для exprP['''eint''' теперь выглядит следующим образомi] '''returns''' ['''int''' val] : { $val = $i; } <font color="green"> // <tex>\varepsilon</tex>-правило</font> | '+' term expr = exprP[$i + $term.val] { $val = $expr.val; } ; term '''returns''' ['''int''' val] :fact termP[$fact.val] { $val = $termP.val; } ;

e returns termP['''int val''' i] : a=e op=('*'|'/returns''' '') b=e {$val = eval($a.val, $op.type, $b.val);} | a=e op=('+[int'|'-') b=e {$val = eval($a.val, $op.type, $b.val);} ] | INT : {$val = $INT.inti;} | ID { String id '*' fact expr = termP[$ID.text; i * $v = memoryfact.containsKey(id) ? memory.get(id) : 0; } | '(' e ')' val] {$val = $eexpr.val;} ;

В первой строке здесь определяется возвращаемое значение ([int val]) для fact '''ereturns'''. Это именно тот атрибут, на который ссылается ['''$e.valint''' в примерах выше.val]Во второй строке, присваивания : '('expr 'a=e''' и '''b=e''' иллюстрируют семантические правила, а действие '')' {$val = eval($aexpr.val, ; } | NUM { $opval = Integer.type, parseInt($bNUM.valtext);}''' {{---}} транслирующий символ из определений, которые мы рассматривали в начале статьи. ;

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

* [https://theantlrguy.atlassian.net/wiki/display/ANTLR4/Parser+Rules#ParserRules-RuleAttributeDefinitions| ANTLR Documentation {{--- }} Rule Attribute Definitions]* [http://www.amazon.com/The-Definitive-ANTLR-4-Reference/dp/1934356999| The Definitive ANTLR 4 Reference]