Изменения

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

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

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

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

На протяжении всей статьи будет Будем рассматривать в качестве примера грамматику для арифметических выраженийс операторами $+$ и $*$:

$ S \to E \\ E \to E + T + E \mid T \\T \to T * F \times T \mid F \\

 Стоит отметить, что не существует гарантии наличия даже одного порядка обхода дерева разбора, при котором вычислятся все атрибуты в узлах. Рассмотрим для примера следующие нетерминалы $A$ и $B$: {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Продукция!style="background-color:#EEE"| Семантические правила|-|style="background-color:#FFF;padding:2px 30px"| $A \to B$|style="background-color:#FFF;padding:2px 30px"| $A.s = B.i \\ B.i = A.s+1$|}Данные правила циклические: невозможно вычислить ни $A.s$ в узле, ни $B.i$ в дочернем узле, не зная значение другого атрибута. Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов. ==Синтезируемые атрибуты=={{Определение|definition ='''Атрибут''', значение которого зависит от значений атрибутов детей данного узла или от других атрибутов этого узла, то атрибут называется '''синтезируемым''' ''(англ. synthesized attribute)''.}} {{Определение|definition =Грамматика называется '''S-атрибутной''' ''(англ. S-attributed definition)'', если с атрибутами выполняются только операции присваивания значений других атрибутов, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. То есть в грамматике используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх, от листьев к корню.}}===Пример S-атрибутной грамматики===Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$ (здесь $\{ADD {{...}} \}$ и $\{MUL {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующие символы]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.): {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Продукция!style="background-color:#EEE"| Семантические правила!style="background-color:#EEE"| Пояснения|-|style="background-color:#FFF;padding:2px 30px"| $S \to E$|style="background-color:#FFF;padding:2px 30px"| $S.val=E.val$|style="background-color:#FFF;padding:2px 30px"| |-|style="background-color:#FFF;padding:2px 30px"| $E_0 \to E_1 + T\ \{ADD\ res = op_1 + op_2\}$|style="background-color:#FFF;padding:2px 30px"| $ADD.op_1=E_1.val \\ ADD.op_2=T.val \\ E_0.val=ADD.res $|style="background-color:#FFF;padding:2px 30px"| В фигурных скобках {{---}} действия транслирующего символа ADD. $op_1$, $op_2$ и $res$ {{---}} атрибуты транслирующего символа. |-|style="background-color:#FFF;padding:2px 30px"| $E \to T$|style="background-color:#FFF;padding:2px 30px"| $E.val=T.val$|style="background-color:#FFF;padding:2px 30px"| |-|style="background-color:#FFF;padding:2px 30px"| $T_0 \to T_1 * F \ \{MUL\ res = op_1 \times op_2\}$|style="background-color:#FFF;padding:2px 30px"| $MUL.op_1=T.val \\ MUL.op_2=F.val \\ T_0.val=MUL.res$|style="background-color:#FFF;padding:2px 30px"| В фигурных скобках {{---}} действия транслирующего символа MUL. $op_1$, $op_2$ и $res$ {{---}} атрибуты транслирующего символа. |-|style="background-color:#FFF;padding:2px 30px"| $T \to F$|style="background-color:#FFF;padding:2px 30px"| $T.val=F.val$|style="background-color:#FFF;padding:2px 30px"| |-|style="background-color:#FFF;padding:2px 30px"| $F \to n$|style="background-color:#FFF;padding:2px 30px"| $F.val=n.val$|style="background-color:#FFF;padding:2px 30px"| |-|style="background-color:#FFF;padding:2px 30px"| $F \to (E)$|style="background-color:#FFF;padding:2px 30px"| $F.val=E.val$|style="background-color:#FFF;padding:2px 30px"| |} В нашем примере видно, что $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)'', если значения наследуемых атрибутов зависят только от родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа).}}===Пример 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:#CCC;margin:0.5px"!style="background-color:#EEE"| Продукция!style="background-color:#EEE"| Семантические правила|-|style="background-color:#FFF;padding:2px 30px"| $D \to TL$|style="background-color:#FFF;padding:2px 30px"| $L.inh = T.type$|-|style="background-color:#FFF;padding:2px 30px"| $T \to int$|style="background-color:#FFF;padding:2px 30px"| $T.type = integer$|-|style="background-color:#FFF;padding:2px 30px"| $T \to real$|style="background-color:#FFF;padding:2px 30px"| $T.type = real$|-|style="background-color:#FFF;padding:2px 30px"| $L_0 \to L_1,id\ \{ENTRY addtype(key, value)\}$|style="background-color:#FFF;padding:2px 30px"| $L_1.inh = L0.inh \\ ENTRY.key=id.text \\ ENTRY.value=L_0.inh$|-|style="background-color:#FFF;padding:2px 30px"| $L \to id\ \{ENTRY addtype(key, value)\}$|style="background-color:#FFF;padding:2px 30px"| $ENTRY.key=id.text \\ ENTRY.value=L.inh$|} Семантическое правило $L.inh = T.type$, связанное с продукцией $D \to TL$, определяет наследуемый атрибут $L.inh$ как тип объявления. Затем приведенные правила распространяют этот тип вниз по дереву разбора с использованием атрибута $L.inh$. Транслирующий символ $ENTRY$, связанный с продукциями для $L$, вызывает процедуру $addtype$ для добавления типа каждого идентификатора к его записи в таблице символов (по ключу, определяемому атрибутом $text$). [[Файл:Real_id1,_id2,_id3.png|600px|center|thumb|Аннотированное дерево разбора для '''$\mathbf{real}\ id1,\ id2,\ id3$'''|600px]] ==Пример работы с атрибутами в нисходящем разборе==Рассмотрим работы с атрибутами на примере LL(1)-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Устранение_левой_рекурсииПредиктивный_синтаксический_анализ | устранения левой рекурсииразборщика]] имеем следующеедля нее:

Например, атрибутом терминала $n$ будет число, которое он представляет: ($n.val = 123$). Атрибутами нетерминалов будут значения, вычисленные в поддереве.В процессе трансляции происходит присваивание атрибутов одних элементов грамматики другим элементам Рассмотрим для той же грамматикиарифметических выражений с операторами <tex>+, при этом присваивание может происходить более сложным способом\ *</tex>, чем простое копирование. В некоторых случаях могут быть нужны какие-то побочные эффекты, например вывод кода или взаимодействие с глобальным контекстом. Для этого нужны транслирующие символыскобками и выводом результата выражения пример на ANTLR.

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

Часто бывает неоптимально для каждого действия заводить транслирующий символ(добавляется лишний Стартовый нетерминал в грамматику)печатает результат: s : expr { System.out. Поэтому при простом присваиванииprintln(копировании$expr.val) атрибутов разрешают не выносить транслирующий символ и заменяют его списком действий, привязанным к правилу. ; };

Обычно, транслирующий символ может работать только со своими атрибутамиВ продукции для нетерминала <code>expr</code> определяется возвращаемое значение (<code>['''int''' val]</code>). Тогда перепишем правило $T \rightarrow T*F$ в виде:$T \rightarrow T*F\ \{MUL \ res = op_1*op_2\}Обращение к этому атрибуту имеет вид <code>$expr.value</code>. В фигурных скобках записаны семантические правила.

И ассоциируем с ним следующий список действийРазобранные нетерминалы возвращают результат, которые будут выполняться вычисленный в особом порядкеподдереве(<code>returns [int val]</code>) как свой синтезируемый атрибут, рассмотренном далее.процесс вычисления которого описан в фигурных скобках <code>{ $MUL.op_1 = T_1.val \\MUL.op_2 = F.val \\T_0$exprP.val = MUL; }</code>.res $

Атрибуты делятся на '''наследуемые''' и '''синтезируемые'''Наследуемые атрибуты передаются нетерминалу как параметр(<code>exprP[$term.{{Определение|definition ='''Атрибут''', значение которого зависит от значений атрибутов братьев узла или атрибутов родителя, называется '''наследуемым'''val]</code>). Если же значение атрибута зависит от значений детей узла или от других арибутов этого узла, то атрибут называется '''синтезируемым'''.}}

В нашем примере видно, что expr '''returns''' ['''int''' val] : term exprP[$term.val] { $ зависит только от детей, то есть синтезируемый атрибут. Результат умножителя (val = $MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемымexprP.val; } ;

exprP['''int''' i] '''returns''' ['''int''' val] : {{Определение$val = $i; } <font color="green"> // <tex>\varepsilon</tex>-правило</font> |definition '+' term expr = exprP[$i + $term.val] { $val =$expr.val; } ; Грамматика называется term '''returns'L-атрибутной'' ['''int''', если значения наследуемых атрибутов зависят только тот родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа)val] : fact termP[$fact.val] { $val = $termP.val; }}} ;

{{Определение|definition =Грамматика называется termP['''int''' i] '''returns''' '''S-атрибутной[int''', если с атрибутами выполняются только операции присваивания значений других атрибутов, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа.val] : { $val = $i; } | '*' fact expr = termP[$i * $fact.val] { $val = $expr.val; } ;

При реализаци методом рекурсивного спуска, каждому нетерминалу соответствует некая рекурсивная функция, которая ранее возвращала дерево разбора соответствующего узла fact '''returns''' ['''int''' val] : '(' expr ')' { $val = $expr. Теперь же функция, соответствующая некоторому нетерминалу val; } | NUM { $Aval = Integer.parseInt($, будет принимать в качестве аргументов его наследуемые атрибуты, а возвращать его синтезируемые атрибутыNUM.text); } ;