1632
правки
Изменения
м
<wikitex>
</wikitex>
<wikitex>
</wikitex>
<wikitex>
</wikitex>
<wikitex>
</wikitex>
<wikitex>
</wikitex>
<wikitex>Рассмотрим работы с атрибутами на примере $LL(1)$-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Предиктивный_синтаксический_анализ | разборщика]] для нее:
<font color="blue">res.val = E'.val</font>
</wikitex>[[Файл:2add3add7.png|600px|center|thumb| Дерево разбора для '''$2\ +\ 3\ +\ 7$''']]
В продукции для нетерминала <code>e</code> определяется возвращаемое значение (<code>[Integer value]</code>). Обращение к этому атрибуту имеет вид <code>$e.value</code>. В фигурных скобках записаны семантические правила.
rollbackEdits.php mass rollback
==Синтаксически управляемая трансляция==
{{Определение
|definition =
S \to E \\
E \to E + T \mid T \\
T \to T \times * F \mid F \\
F \to n \mid (E)
$
Данные правила циклические: невозможно вычислить ни $A.s$ в узле, ни $B.i$ в дочернем узле, не зная значение другого атрибута.
Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов.
==Синтезируемые атрибуты==
{{Определение
|definition =
Грамматика называется '''S-атрибутной''' ''(англ. S-attributed definition)'', если с атрибутами выполняются только операции присваивания значений других атрибутов, а внутри транслирующих символов происходят обращения только к атрибутам этого транслирующего символа. То есть в грамматике используются только синтезируемые атрибуты. Дерево разбора для такой грамматике всегда может быть аннотировано путем выполнения семантических правил снизу вверх, от листьев к корню.
}}
===Пример S-атрибутной грамматики===
Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$ (здесь $\{ADD {{...}} \}$ и $\{MUL {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующие символы]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):
|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"|
|-
|style="background-color:#FFF;padding:2px 30px"| $T_0 \to T_1 \times * 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$
После такого разбора в $S.val$ будет лежать вычисленное значение выражения. Можно, например сразу напечатать его, добавив к нему правило $\{print(S.val)\}$.
==Наследуемые атрибуты==
{{Определение
|definition =
Грамматика называется '''L-атрибутной''' ''(англ. L-attributed definition)'', если значения наследуемых атрибутов зависят только от родителей и братьев слева (то есть не зависят от значений атрибутов братьев справа).
}}
===Пример L-атрибутной грамматики===
Для наглядности рассмотрим грамматику объявления переменных
(в начале строки идет тип, затем через запятую имена переменных. Примеры строк, разбираемых в ней: '''int a''' или '''real x,y,z''' и подобные):
Выпишем продукции (с транслирующими символами) и ассоциируем с ними семантические правила
(здесь $\{ENTRY {{...}} \}$ {{- --}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующий символ]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):
{| style="background-color:#CCC;margin:0.5px"
|}
Семантическое правило $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]]
==Пример работы с атрибутами в нисходящем разборе==
$
$
В данной реализации рекурсивные функции от нетерминалов получают на вход(если необходимо) наследуемые атрибуты узла и возвращают вершины дерева разбора, в атрибутах которых записан результат вычислений соответствующего подвыражения. Однако этот код легко изменить, чтобы он только вычислял значение выражения и не строил дерево разбора. Как мы видим, $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'''
'''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'(temp)) "].val</font>
'''break'''
'''default''' :
<font color="red">error</font>("unexpected char")
'''return''' res
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''' :
res.addChild(Node("("))
res.addChild(E())
<font color="blue">rev.val = res.children["E"].val</font>
consume(')')
res.addChild(Node(")"))
Функции для $T$ и $T'$ строятся аналогично.
==Атрибуты в ANTLR==
Общедоступный генератора генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение.
Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+,\times*</tex>, скобками и выводом результата выражениая выражения пример на ANTLR.
grammar Expression;
Естественным образом можно добавлять действия в продукции, где это нужно. Действия выполняются после предыдущего элемента грамматики и до следующего.
Стартовый нетерминал печатает резульатрезультат: s : expr { System.out.println($eexpr.valueval);}; В продукции для нетерминала <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]
exprP['''int''' i] '''returns''' ['''int''' val]
: { $val = $i; }<font color="green"> // <tex>\varepsilon</tex>-правило</font> | '+' term e expr = exprP[$i + $term.val] { $val = $eexpr.val; }
;
term '''returns''' ['''int''' val]
: fact termP[$fact.val] { $val = $termpPtermP.val; }
;
termP['''int''' i] '''returns''' '''[int''' val]
: { $val = $i; } | '*' fact e expr = termP[$i * $fact.val] { $val = $eexpr.val; }
;
WS : [ \t \r \n]+ -> skip ;
NUM : [0-9]+ ;
== Примечания ==
