Изменения

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

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

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

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

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

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

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

Например, атрибутом терминала $n$ будет число, которое он представляет: ($n.val = 123$). Атрибутами нетерминалов будут значения, вычисленные в поддереве. В процессе трансляции происходит присваивание атрибутов одних элементов грамматики другим элементам грамматики, при этом присваивание может происходить более сложным способом, чем простое копирование. В некоторых случаях могут быть нужны какие-то побочные эффекты, например вывод кода или взаимодействие с глобальным контекстом. Для этого нужны транслирующие символы. Заменим правило $T \rightarrow T*F$ на следующее: $T \rightarrow T*F\{T_0.val=T_1.val*F.val\}$, где $\{T_0.val=T_1.val*F.val\}$ {{---}} транслирующий символ. Аналогично к $F \rightarrow n$ добавляется $\{F.val = n.val\}$. Часто бывает неоптимально для каждого действия заводить транслирующий символ(добавляется лишний нетерминал в грамматику). Поэтому при простом присваивании(копировании) атрибутов разрешают не выносить транслирующий символ и заменяют его списком действий, привязанным к правилу. Обычно, транслирующий символ может работать только со своими атрибутами. Тогда перепишем правило $T \rightarrow T*F$ в виде: $T \rightarrow T*F\ \{MUL \ res = op_1*op_2\}$ И ассоциируем с ним следующий список действий, которые будут выполняться в особом порядке, рассмотренном далее. $ 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> ==Пример работы с атрибутами в нисходящем разборе==<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

При реализации методом рекурсивного спуска, каждому нетерминалу соответствует рекурсивная функция, которая ранее возвращала дерево разбора соответствующего узла F() : '''Node''' Node res = Node("F") '''switch''' (curToken) '''case''' n : consume(n) res. Теперь же функция, соответствующая некоторому нетерминалу $T$, будет принимать в качестве аргументов его наследуемые атрибуты, а возвращать его синтезируемые атрибуты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(): '''int''' T_1.val=$ и $T() consume('*') F.val=F() MUL.res = MUL(op1=T1.val, op2=F.val) '''return''' MUL$ строятся аналогично.res

Заметим, что в рассматриваемой грамматике присутствует левая рекурсия, в связи с чем некоторые наши примеры имеют искусственный характер, хотя и являются наглядными[[Файл:2add3add7. png|600px|center|thumb| Дерево разбора для '''$2\ +\ 3\ +\ 7$''']]</wikitex>

$Общедоступный генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение. x\ A \to A \alpha Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+,\Leftrightarrow x=g(A_1*</tex>, \alpha) \\x\ A \to \beta \Leftrightarrow x=f(\beta)$скобками и выводом результата выражения пример на 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]