Изменения

Перейти к: навигация, поиск

Атрибутные транслирующие грамматики

90 байт добавлено, 14:26, 6 июня 2015
Нет описания правки
S \to E \\
E \to E + T \mid T \\
T \to T \times * F \mid F \\
F \to n \mid (E)
$
|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$
|}
Семантическое правило $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 : '''stringint''' <font color="green">// атрибут нетерминала</font> '''function''' addChild('''Node''') <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")
<font color="blue">res.val = E'.val</font>
'''return''' res
'''break'''
'''case''' '$', ')' :
<font color="blue">res.val = acc;</font>
'''break'''
'''default''' :
Общедоступный генератора разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение.
Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+\times*</tex>, скобками и выводом результата выражениая пример на ANTLR.
grammar Expression;
Разобранные нетерминалы возвращают результат, вычисленный в поддереве(<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; } // <tex>\varepsilon</tex>-правило
| '+' term e = exprP[$i + $term.val] { $val = $e.val; }
;
496
правок

Навигация