Изменения

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

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

2511 байт добавлено, 11 февраль
Атрибуты в ANTLR
S \to E \\
E \to E + T \mid T \\
T \to T \times * F \mid F \\
F \to n \mid (E)
$
 
Все соображения, связанные с атрибутами, применимы как при нисходящем, так и при восходящем раброре, однако для нисходящего разборщика нужно будет сперва [[Устранение_левой_рекурсии| устранить левую рекурсию]]:
 
$
S \to E \\
E \to TE' \\
E' \to +TE' \mid \varepsilon \\
T \to FT' \\
T' \to * FT' \mid \varepsilon \\
F \to n \mid (E)
$
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| продукцииПродукция
!style="background-color:#EEE"| Семантические правила
|-
===Пример S-атрибутной грамматики===
<wikitex>
Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$ (здесь $\{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 E_0 \to E 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 T_0 \to T \times 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"|
|}
Выпишем продукции (с транслирующими символами) и ассоциируем с ними семантические правила
(здесь $\{ENTRY {{...}} \}$ {{- --}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующий символ]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.):
{| style="background-color:#CCC;margin:0.5px"
|style="background-color:#FFF;padding:2px 30px"| $T.type = real$
|-
|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.inh \\ ENTRY.key=id.text \\ ENTRY.value=LL_0.inh$
|-
|style="background-color:#FFF;padding:2px 30px"| $L \to id\ \{ENTRY addtype(key, value)\}$
|}
Семантическое правило $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]]
</wikitex>
==Пример работы с атрибутами в нисходящем разборе==
<wikitex>
Рассмотрим работы с атрибутами на примере $LL(1)$-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Предиктивный_синтаксический_анализ | разборщика]] для нее:
$
$
В данном примере не требуется дерево разбора в явном виде. В данной реализации рекурсивные функции от нетерминалов получают на вход(если необходимо) наследуемые атрибуты узла и возвращают синтезируемые (вершины дерева разбора, в атрибутах которых записан результат вычислений соответствующего подвыражения). Однако этот код легко изменить, чтобы он только вычислял значение выражения и не строил дерево разбора. Как мы видим, $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''' Node res = Node("E") '''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'"].val</font> '''break''' '''default''' : <font color="red">error</font>("unexpected char") '''return''' res
E() : '''int'''
T.val = T()
E'.val = E'(T.val)
'''return''' E'.val
E'(acc) : '''intNode''' Node res = Node("E'")
'''switch''' (curToken)
'''case''' '+' :
consume('+')
Tres.addChild(Node("+")) res = .addChild(T()) <font color="blue">temp = res.children["T"].val ADD.res = ADD(acc, temp) <font color="green">// ADD проведет вычисления из наследуемого атрибута add и атрибута ребенка "T.val)"</font> E'res.val = addChild(E'(ADD.res)) <font color="green">// результат вычислений будет передан правому ребенку как наследуемый атрибут</font> res.val = res.children["E'"].val</font> ''return'break'' E'.val '''case''' '\varepsilon$', ')': <font color="blue">res.val = acc</font> '''returnbreak''' acc '''default''' : <font color="red">error</font>("unexpected char") '''return''' res
F() : '''intNode''' Node res = Node("F")
'''switch''' (curToken)
'''case''' n :
consume(n)
Fres.addChild(Node(curToken)) <font color="blue">res.val = n.val</font> '''returnbreak''' F.val
'''case''' '(' :
consume('(')
Fres.addChild(Node("(")) res.addChild(E()) <font color="blue">rev.val = res.children["E()"].val</font>
consume(')')
'''return''' Fres.valaddChild(Node(")"))
'''default''' :
<font color="red">error</font>("unexpected char")
'''return''' res
Функции для $T$ и $T'$ строятся аналогично.
[[Файл:2add3add7.png|600px|center|thumb| Дерево разбора для '''$2\ +\ 3\ +\ 7$''']]
</wikitex>
==Атрибуты в ANTLR==
Общедоступный генератора генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение.  Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+,\ *</tex>, скобками и выводом результата выражения пример на ANTLR.  grammar Expression; '''@header''' { package ru.ifmo.ctddev.wiki; }  Естественным образом можно добавлять действия в продукции, где это нужно. Действия выполняются после предыдущего элемента грамматики и до следующего. Стартовый нетерминал печатает результат: s : expr { System.out.println($expr.val); };
Рассмотрим В продукции для примера грамматику арифметических выражений с оператором нетерминала <code>expr</code> определяется возвращаемое значение (<code>['''int''' val]</code>). Обращение к этому атрибуту имеет вид <code>$+$, $*$, и выводом результата выражениаяexpr.value</code>. В фигурных скобках записаны семантические правила.
Вне продукций грамматики бывает нужно вставить Разобранные нетерминалы возвращают результат, вычисленный в сгенерированный разборщикподдереве(для Java<code>returns [int val]</code>) packageкак свой синтезируемый атрибут, import, а также некоторые поля и методыпроцесс вычисления которого описан в фигурных скобках <code>{ $val = $exprP.val; }</code>. Это делается с помощью '''@header''' и '''@members''':
grammar Expr; '''@header''' { package tools; import java.util.*; } '''@parser::members''' { MapНаследуемые атрибуты передаются нетерминалу как параметр(<String, Integercode> memory = new HashMapexprP[$term.val]<String, Integer/code>(); int eval(int left, int op, int right) { ... } }
Естественным образом можно добавлять действия в продукции, где это нужно: expr '''stat:returns''' ['''eint''' NEWLINE {System.out.println($e.val);} ] | ID '=' '''e''' NEWLINE {memory.put(: term exprP[$IDterm.text, val] { $e.val); System.out.println($ID.text + "=" + $eexprP.val);} | NEWLINE ;
Действия выполняются после предыдущего элемента грамматики и до следующего 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; } ;
Правило для termP['''eint''' теперь выглядит следующим образомi] '''returns''' '''[int''' val] : { $val = $i; } | '*' fact expr = termP[$i * $fact.val] { $val = $expr.val; } ;
fact '''ereturns''' ['''returnsint''' [int val] : a=e op='('*expr ') b=e {$val = eval($a.val, $op.type, $b.val);} | a=e op=('+') b=e {$val = eval($a.val, $op.type, $bexpr.val);} | INT NUM {$val = $INTInteger.int;} | ID { String id = parseInt($IDNUM.text; $v = memory.containsKey(id) ? memory.get(id) : 0; } | '(' '''e''' ')' {$val = $e.val;} ;
В первой строке здесь определяется возвращаемое значение ('''[int val]''') Техническая деталь для нетерминала '''e'''. Это именно тот атрибутANTLR, на который ссылается '''$e.val''' в примерах выше.правила для лексического анализатора:Во второй строке, присваивания '''a=e''' и '''b=e''' иллюстрируют семантические правила, а действие '''{$val = eval($a.val, $op.type, $b.val) WS : [ \t \r \n]+ -> skip ;}''' {{ NUM : [0---}} транслирующий символ из определений, которые мы рассматривали в начале статьи.9]+ ;
== Примечания ==
Анонимный участник

Навигация