Изменения

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

 Стоит отметить, что не существует гарантии наличия даже одного порядка обхода дерева разбора, при котором вычислятся все атрибуты в узлах. Рассмотрим для примера следующие нетерминалы $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#Пример | ранее]] и расширим код [[Устранение_левой_рекурсииПредиктивный_синтаксический_анализ | устранения левой рекурсииразборщика]] имеем следующеедля нее:

Часто бывает неоптимально для каждого действия заводить транслирующий символ 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

Обычно, транслирующий символ может работать только со своими атрибутами. Тогда перепишем правило $T \rightarrow T* F$ в виде() :'''Node'''$T \rightarrow T* Node res = Node("F\ \{MUL \ ") '''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= op_1*op_2\}$"red">error</font>("unexpected char") '''return''' res

И ассоциируем с ним следующий список действий, которые будут выполняться в особом порядке, рассмотренном далее.Функции для $T$ и $T'$MUL.op_1 = T_1.val \\MULстроятся аналогично.op_2 = F.val \\T_0.val = MUL.res $

Атрибуты делятся на '''наследуемые''' и '''синтезируемые'''[[Файл:2add3add7.{{Определениеpng|definition =600px|center|thumb| Дерево разбора для '''Атрибут$2\ +\ 3\ +\ 7$''', значение которого зависит от значений атрибутов братьев узла или атрибутов родителя, называется '''наследуемым'''. Если же значение атрибута зависит от значений детей узла или от других арибутов этого узла, то атрибут называется '''синтезируемым'''.}}]]

Общедоступный генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{Определение|definition =Грамматика называется '''L-атрибутной''', если значения наследуемых атрибутов зависят только тот родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа).--}}Parser generator]</ref> поддерживает синтаксически управляемое определение.

{{Определение|definition =Грамматика называется '''S-атрибутной''', если Рассмотрим для той же грамматики арифметических выражений с атрибутами выполняются только операции присваивания значений других атрибутовоператорами <tex>+, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. То есть используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх\ *</tex>, от листьев к корнюскобками и выводом результата выражения пример на ANTLR.}}

Хотя всегда можно переписать синтаксически управляемое определение таким образом, чтобы использовать только синтезируемые атрибуты, зачастую более удобно и естественно воспользоваться также и наследуемыми атрибутами grammar Expression; '''@header''' { package ru.ifmo.ctddev.wiki; }

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

TВ продукции для нетерминала <code>expr</code> определяется возвращаемое значение (): <code>['''int''' T_1.val=T(]</code>) consume('*') F.val=F() MULОбращение к этому атрибуту имеет вид <code>$expr.res = MUL(op1=T1value</code>.val, op2=F.val) '''return''' MULВ фигурных скобках записаны семантические правила.res

ЗаметимРазобранные нетерминалы возвращают результат, что вычисленный в рассматриваемой грамматике присутствует левая рекурсияподдереве(<code>returns [int val]</code>) как свой синтезируемый атрибут, процесс вычисления которого описан в связи с чем некоторые наши примеры имеют искусственный характер, хотя и являются нагляднымифигурных скобках <code>{ $val = $exprP. Левую рекурсию устраним позжеval; }</code>.Распишем все правила, добавив транслирующие символы и ассоциировав с каждым правилом список присваиваний(присваивания помечены троеточием и отступом):

Наследуемые атрибуты передаются нетерминалу как параметр(<code>exprP[$ val\ E \to E + T\ \{ADD\ res = op_1 + op_2\} \\{{...}}\ \ \ ADD.op_1=E_1.val \\{{...}}\ \ \ ADD.op_2=T.val \\{{...}}\ \ \ E_0.val=ADD.res \\E \to T \\{{...}}\ \ \ E.val=T.val \\val\ T \to T \times F \ \{MUL\ res = op_1 + op_2\} \\{{...}}\ \ \ MUL.op_1=T.val \\{{...}}\ \ \ MUL.op_2=Fterm.val \\{{...}}\ \ \ T_0.val=MUL.res \\T \to F \\{{...}}\ \ \ T.val=F.val \\F \to n \\{{...}}\ \ \ F.val=n.val \\ F \to (E]</code>) \\{{...}}\ \ \ F.val=E.val \\$

Рассмотрим, что происходит с атрибутами при expr '''returns''' ['''int''' val] : term exprP[Устранение_левой_рекурсии| устранения левой рекурсии$term.val]] из грамматики { $val = $exprP.val; }Пусть есть правила: ;

exprP['''int''' i] '''returns''' ['''int''' val] : { $val = $x\ A \to A \alpha \Leftrightarrow xi; } <font color=g(A_1, \alpha) \"green"> // <tex>\varepsilon</tex>-правило</font>x\ A \to \beta \Leftrightarrow x | '+' term expr = exprP[$i + $term.val] { $val =f(\beta)$expr.val; } ; term '''returns''' ['''int''' val] : fact termP[$fact.val] { $val = $termP.val; } ;

После устранения левой рекурсии fact '''returns''' ['''int''' val] :'(' expr ')' { $val = $expr.val; } | NUM { $val = Integer.parseInt($NUM.text); } ;

$Техническая деталь для ANTLR, правила для лексического анализатора:x WS : [ \ A t \to r \beta A' \\x\ A' \to \alpha A' \\x\ A \to \varepsilonn]+ -> skip ;$ NUM : [0-9]+ ;