Изменения

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

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

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

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

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

S \to E \\

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

Стоит отметить, что не существует гарантии наличия даже одного порядка обхода дерева разбора, при котором вычислятся все атрибуты в узлах. Рассмотрим для примера следующие нетерминалы $S \to EE \to TE' \\E' \to +TE' \mid \varepsilon \\T \to FT' \\T' \to * FT' \mid \varepsilon \\F \to n \mid (E)A$и $B$:

{| style="background-color:#CCC;margin:0.5px" Например, атрибутом терминала $n$ будет число, которое он представляет!style="background-color: ($n.val #EEE"| Продукция!style= 123$). Атрибутами нетерминалов будут значения, вычисленные в поддереве."background-color:#EEE"| Семантические правила В процессе трансляции происходит присваивание атрибутов одних элементов грамматики другим элементам грамматики, при этом присваивание может происходить более сложным способом, чем простое копирование. В некоторых случаях могут быть нужны какие|-то побочные эффекты, например вывод кода или взаимодействие с глобальным контекстом. Для этого нужны транслирующие символы. Заменим правило |style="background-color:#FFF;padding:2px 30px"| $T A \rightarrow T*Fto B$ на следующее|style="background-color:#FFF;padding: 2px 30px"| $T \rightarrow T*F\{T_0A.vals =T_1.val*FB.vali \}$, где $\{T_0B.vali =T_1.val*FA.val\}s+1$ {{---|}} транслирующий символ. Аналогично к Данные правила циклические: невозможно вычислить ни $F \rightarrow n$ добавляется $\{F.val = nA.val\}s$. Часто бывает неоптимально для каждого действия заводить транслирующий символ(добавляется лишний нетерминал в грамматику). Поэтому при простом присваивании(копировании) атрибутов разрешают не выносить транслирующий символ и заменяют его списком действийузле, привязанным к правилу. Обычно, транслирующий символ может работать только со своими атрибутамини $B. Тогда перепишем правило $T \rightarrow T*F$ в виде: $T \rightarrow T*F\ \{MUL \ res = op_1*op_2\}i$ И ассоциируем с ним следующий список действий, которые будут выполняться в особом порядкедочернем узле, рассмотренном далеене зная значение другого атрибута. $ MUL.op_1 = T_1.val \\ MUL.op_2 = FДалее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов.val \\ T_0.val = MUL.res $ Атрибуты делятся на '''наследуемые''' и '''синтезируемые'''.</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$).

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

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

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

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

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

|style="background-color:#FFF;padding:2px 30px"| $L.in inh = T.type$

|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.in inh \\ ENTRY.key=id.entry text \\ ENTRY.value=LL_0.ininh$

|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.ininh$

Семантическое правило $L.in inh = T.type$, связанное с продукцией $D \to TL$, определяет наследуемый атрибут $L.ininh$ как тип объявления. Затем приведенные правила распространяют этот тип вниз по дереву разбора с использованием атрибута $L.ininh$. Транслирующий символ $ENTRY$, связанный с продукциями для $L$, вызывает процедуру $addtype$ для добавления типа каждого идентификатора к его записи в таблице символов (по ключу, определяемому атрибутом $entrytext$).

[[Файл:Real_id1,_id2,_id3.png|600px|center|thumb|Аннотированное дерево разбора для '''$\mathbf{real}\ id1,\ id2,\ id3$'''|600px]]<картинка/wikitex>

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

TE(): '''intNode''' T_1.valNode res =TNode("E") consume'''switch''' (curToken) '*''case''' n, '(' : res.addChild(T()) <font color="green">// подвешиваем левого сына</font> F <font color="blue">temp = res.children["T"].val</font> <font color=F"green">// атрибут левого сына</font> <font color="blue">Node rightSon = E'(temp) </font> <font color="green">// отдадим атрибут левого сына правому как наследуемый атрибут</font> MUL <font color="blue">res.res addChild(rightSon) </font> <font color= MUL(op1"green">// подвешиваем правого сына сына</font> <font color=T1"blue">res.val, op2=Fres.children["E'"].val</font> '''break''' '''default''' : <font color="red">error</font>("unexpected char") '''return''' MUL.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''' :x\ A \to A \alpha \Leftrightarrow x <font color=g"red">error</font>(A_1, \alpha"unexpected char") \\x '''return''' res Функции для $T$ и $T'$ строятся аналогично. [[Файл:2add3add7.png|600px|center|thumb| Дерево разбора для '''$2\ A +\to 3\beta +\Leftrightarrow x7$''']]</wikitex> ==Атрибуты в ANTLR==f( Общедоступный генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение.  Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+,\beta)$*</tex>, скобками и выводом результата выражения пример на ANTLR.

$x\ A \to \beta A' \\x\ A' \to \alpha A' \\x\ A \to \varepsilonСтартовый нетерминал печатает результат: 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; } ;

exprP['''int''' 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; } ;

хоть немного про ANTLR - атрибуты fact '''returns''' ['''int''' val] : '(' expr ')' { $val = $expr.val; } | NUM { $val = Integer.parseInt($NUM.text); } ;

== Примечания ==<references/wikitex>

* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Второе издание. 2008. Стр. ??? 383 {{---}} ???398.* [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]