Изменения

'''Синтаксически управляемое определение''' {{''(англ. 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 \\

Стоит отметить, что не существует гарантии наличия даже одного порядка обхода дерева разбора, при котором вычислятся все атрибуты в узлах. Рассмотрим для примера следующие нетерминалы $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 $ Атрибуты делятся на '''наследуемые''' и '''синтезируемые'''.

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

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

!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$''']] После такого разбора в $S.val$ будет лежать вычисленное значение выражения. Можно, например сразу напечатать его, добавив к нему правило $\{print(S.val)\}$. ==Наследуемые атрибуты== {{Определение|definition ='''Атрибут''', значение которого зависит от значений атрибутов братьев узла или атрибутов родителя, называется '''наследуемым''' ''(англ. inherited attribute)''. }}

После разбора по таким правилам{{Определение|definition =Грамматика называется '''L-атрибутной''' ''(англ. L-attributed definition)'', в атрибуте $val$ корня дерева разбора будет лежать вычисленное значение выраженияесли значения наследуемых атрибутов зависят только от родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа).}}===Пример L-атрибутной грамматики===Для изящности можно добавить еще одно правило $S \to E$ и действиенаглядности рассмотрим грамматику объявления переменных (семантическое правило) {print(Eв начале строки идет тип, затем через запятую имена переменных.valПримеры строк, разбираемых в ней: '''int a''' или '''real x,y,z''' и подобные)}. Тогда сразу после разбора выражения будет напечатан его результат.:

Рассмотрим пример Выпишем продукции (с 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]] ==Пример работы с атрибутами в нисходящем разборе==Рассмотрим работы с атрибутами на примере 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>

При реализации методом рекурсивного спуска, каждому нетерминалу соответствует рекурсивная функция, которая ранее возвращала дерево разбора соответствующего узла. Теперь же функция, соответствующая некоторому нетерминалу Функции для $T$, будет принимать в качестве аргументов его наследуемые атрибуты, а возвращать его синтезируемые атрибутыи $T'$ строятся аналогично.

T()[[Файл: '''int''' T_12add3add7.val=T() consume(png|600px|center|thumb| Дерево разбора для '*') F.val=F() MUL.res = MUL(op1=T1.val, op2=F.val) ''$2\ +\ 3\ +\ 7$'return''' MUL.res]]

Заметим, что ==Атрибуты в рассматриваемой грамматике присутствует левая рекурсия, в связи с чем некоторые наши примеры имеют искусственный характер, хотя и являются наглядными. ANTLR==

Рассмотрим, что происходит с атрибутами при Общедоступный генератор разборщиков 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>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]