1632
правки
Изменения
м
<wikitex>Часто, осуществляя разбор, мы хотим извлечь какие-то данные или чтопроизвести какие-то сделатьдействия, а не просто выяснить, разбирается ли текст в данной грамматике.Вообще говоря, сначала можно получить [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора|дерево разборыразбора]], а потом уже, обойдя дерево разбораобходя его, по нему производить какие-то выполнять эти действия.В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда это дерево его просто слишком расточительно хранить в памятицеликом.В связи с этим хочется какие-то действия производить уже на этапе разбора. Например, мы хотим не только построить дерево разбора для арифметических выражений, а ещё и вычислить значение этого выражения. Возможно, даже не строя само дерево разбора. Такой подход называется '''Синтаксически синтаксически управляемой трансляцией'''.
На протяжении всей статьи будет Будем рассматривать в качестве примера грамматику для арифметических выраженийс операторами $+$ и $*$:
После [[Устранение_левой_рекурсии| устранения левой рекурсии]] имеем следующее:
Например, атрибутом терминала $n$ будет число, которое он представляет{| style="background-color:#CCC;margin: ($n0.val 5px"!style= 123$). Атрибутами нетерминалов будут значения, вычисленные в поддереве."background-color:#EEE"| ПродукцияВ процессе трансляции происходит присваивание атрибутов одних элементов грамматики другим элементам грамматики, при этом присваивание может происходить более сложным способом, чем простое копирование. В некоторых случаях могут быть нужны какие!style="background-то побочные эффекты, например вывод кода или взаимодействие с глобальным контекстом. Для этого нужны транслирующие символы.color:#EEE"| Семантические правила|- Заменим правило |style="background-color:#FFF;padding:2px 30px"| $T A \rightarrow T*Fto B$ на следующее|style="background-color:#FFF;padding: 2px 30px"| $T \rightarrow T*F\{T_0A.vals =T_1.val*FB.vali \}$, где $\{T_0B.vali =T_1A.val*F.val\}s+1$ {{---|}} транслирующий символ. Аналогично к Данные правила циклические: невозможно вычислить ни $F \rightarrow n$ добавляется $\{F.val = nA.val\}s$. Часто бывает неоптимально для каждого действия заводить транслирующий символ(добавляется лишний нетерминал в грамматику). Поэтому при простом присваивании(копировании) атрибутов разрешают не выносить транслирующий символ и заменяют его списком действийузле, привязанным к правилуни $B. Обычно, транслирующий символ может работать только со своими атрибутами. Тогда перепишем правило $T \rightarrow T*F$ в виде:$T \rightarrow T*F\ \{MUL \ res = op_1*op_2\}i$ И ассоциируем с ним следующий список действий, которые будут выполняться в особом порядкедочернем узле, рассмотренном далеене зная значение другого атрибута.$MUL.op_1 = T_1.val \\MUL.op_2 = F.val \\T_0.val = MUL.res $ Атрибуты делятся на '''наследуемые''' и '''синтезируемые'''Далее будет рассмотрено два класса синтаксически управляемых грамматик, для которых можно однозначно определить порядок вычисления атрибутов.
Рассмотрим пример S-атрибутной грамматики.
Выпишем все правила для грамматики арифметических выражений, добавив транслирующие символы и ассоциировав с каждым правилом грамматики список семантических правил.
После [[Файл:3mul5add4.png|500px|thumb|center|Аннотированное дерево разбора по таким правилам, в атрибуте для '''$val3*5+4$ корня дерева разбора будет лежать вычисленное значение выражения.Для изящности можно добавить еще одно правило $S \to E$ и действие(семантическое правило) {print(E.val)}. Тогда сразу после разбора выражения будет напечатан его результат.''']]
Хотя всегда можно переписать синтаксически управляемое определение таким образомПосле такого разбора в $S.val$ будет лежать вычисленное значение выражения. Можно, чтобы использовать только синтезируемые атрибутынапример сразу напечатать его, зачастую более удобно и естественно воспользоваться также и наследуемыми атрибутамидобавив к нему правило $\{print(S.val)\}$.
Рассмотрим пример Выпишем продукции (с L-атрибутной грамматики.Выпишем правила транслирующими символами) и ассоциируем с ними действия(семантические правила(здесь $\{ENTRY {{...}} \}$ {{---}} [[Атрибутные_транслирующие_грамматики#tr_char|транслирующий символ]]. Если в продукции несколько раз встречается одинаковый нетерминал, будем добавлять к нему индексы, считая от начала продукции.) для грамматики объявления переменных:
<картинка>[[Файл:Real_id1,_id2,_id3.png|600px|center|thumb|Аннотированное дерево разбора для '''$\mathbf{real}\ id1,\ id2,\ id3$'''|600px]]
==Аспекты $E \to TE' \\E' \to +TE' \mid \varepsilon \\T \to FT' \\T' \to * FT' \mid \varepsilon \\F \to n \mid (E)$ В данной реализациирекурсивные функции от нетерминалов получают на вход (если необходимо) наследуемые атрибуты узла и возвращают вершины дерева разбора, в атрибутах которых записан результат вычислений соответствующего подвыражения. Однако этот код легко изменить, чтобы он только вычислял значение выражения и не строил дерево разбора. Как мы видим, $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>
Рассмотрим некоторые аспекты реализации на более сложном примере.
При реализации методом рекурсивного спуска, каждому нетерминалу соответствует рекурсивная функция, которая ранее возвращала дерево разбора соответствующего узла. Теперь же функция, соответствующая некоторому нетерминалу $T$, будет принимать в качестве аргументов его наследуемые атрибуты, а возвращать его синтезируемые атрибуты.
TE'(acc): '''intNode''' T_1.valNode res =TNode("E'") '''switch''' (curToken) '''case''' '+' : consume('*+') F res.addChild(Node("+")) res.addChild(T()) <font color="blue">temp = res.children["T"].val ADD.res =FADD(acc, temp) <font color="green">// ADD проведет вычисления из наследуемого атрибута add и атрибута ребенка "T"</font> MUL res.addChild(E'(ADD.res )) <font color= MUL(op1"green">// результат вычислений будет передан правому ребенку как наследуемый атрибут</font> res.val =T1res.children["E'"].val</font> '''break''' '''case''' '$', op2')' : <font color=F"blue">res.val= acc</font> '''break''' '''default''' : <font color="red">error</font>("unexpected char") '''return''' MUL.res
Заметим, что в рассматриваемой грамматике присутствует левая рекурсия, в связи с чем некоторые наши примеры имеют искусственный характер, хотя и являются наглядными F() : '''Node''' Node res = Node("F") '''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="red">error</font>("unexpected char") '''return''' res
Рассмотрим, что происходит с атрибутами при [[Устранение_левой_рекурсии| устранения левой рекурсии]] из грамматикиФункции для $T$ и $T'$ строятся аналогично.Пусть есть правила:
<картинка> grammar Expression; '''@header''' { package ru.ifmo.ctddev.wiki; }
После устранения левой рекурсии:Естественным образом можно добавлять действия в продукции, где это нужно. Действия выполняются после предыдущего элемента грамматики и до следующего.
$x\ A \to \beta A' \\x\ A' \to \alpha A' \\x\ A \to \varepsilonСтартовый нетерминал печатает результат: s : expr { System.out.println($expr.val); };
Рассмотрим грамматику арифметических выражений, для наглядности оставив только числа, сложение и скобкиНаследуемые атрибуты передаются нетерминалу как параметр(<code>exprP[$term.val]</code>).
<картинки деревьев и псевдокод функций для грамматики до и после устранения левой рекурсии expr '''returns''' ['''int''' val] : term exprP[$term.>val] { $val = $exprP.val; } ;
хоть немного про ANTLR - атрибуты fact '''returns''' ['''int''' val] : '(' expr ')' { $val = $expr.val; } | NUM { $val = Integer.parseInt($NUM.text); } ;
rollbackEdits.php mass rollback
==Синтаксически управляемая трансляция==
{{Определение
|definition =
'''Синтаксически управляемое определение''' {{''(англ. syntax-directed definition)'' является [[Контекстно-свободные_грамматики,_вывод,_лево-}} обобщение _и_правосторонний_вывод,_дерево_разбора|контекстно-свободной грамматики]] грамматикой с атрибутами и правилами. Атрибуты связаны с грамматическими символами, в которой каждый грамматический символ имеет связанное а правила — с ним множество атрибутовпродукциями.
}}
{{Определение
|definition =
'''Синтаксически управляемая трансляция''' ''(англ. syntax-directed translation)'' {{---}} это трансляция, при которой в [[Предиктивный_синтаксический_анализ| процессе разбора ]] строки сразу выполняются какие-то действия, не используя промежуточное представление без использования промежуточного представления в виде дерева разбора.
}}
{{Определение
|definition =
'''Атрибут''' ''(англ. attribute)'' {{---}} дополнительное поле дополнительные данные, ассоциированные с данными у терминалов и нетерминаловграмматическими символами. Если $X$ представляет собой символ, а $a$ — один из его атрибутов, то значение $a$ в некотором узле дерева разбора, помеченном $X$, записывается как $X.a$. Если узлы дерева разбора реализованы в виде записей или объектов, то атрибуты $X$ могут быть реализованы как поля данных в записях, представляющих узлы $X$. (Более строгое определение требует ввести систему типов)Атрибуты могут быть любого вида: числами, типами, таблицами ссылок или строками.
}}
{{Определение
|definition =
Дерево разбора, имеющее вычисленные атрибуты в каждом узлекоторого атрибуты уже вычислены, называется '''аннотированным''' ''(англ. annotated)'', а процесс вычисления этих атрибутов {{--- }} '''аннотированием''' дерева разбора.
}}
{{Определение
|id = tr_char
|definition =
'''Транслирующий символ''' {{---}} нетерминал, который раскрывается в $\varepsilon$ и в момент раскрытия выполняет какое-то действие, которое связанное с ним связанодействие. Для простоты, будем писать действия Действия пишутся в фигурных скобках в том месте, где это нужнорядом с транслирующим символом.
}}
$ S \to E \\
E \to E + T \mid T \\
T \to T \times * F \mid F \\
F \to n \mid (E)
$
Стоит отметить, что не существует гарантии наличия даже одного порядка обхода дерева разбора, при котором вычислятся все атрибуты в узлах. Рассмотрим для примера следующие нетерминалы $E \to TE' \\E' \to +TE' \mid \varepsilon \\T \to FT' \\T' \to * FT' \mid \varepsilon \\F \to n \mid (E)A$и $B$:
==Синтезируемые атрибуты==
{{Определение
|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 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"| $val\ 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"|
|}
В нашем примере видно, что $.val$ зависит только от детейв дереве разбора, то есть это синтезируемый атрибут. Результат умножителя ($MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемым(аналогично с сумматором $ADD$). <картинка>
==Наследуемые атрибуты==
{{Определение
|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
$
{| 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.in inh = T.type$
|-
|style="background-color:#FFF;padding:2px 30px"| $T \to int$
|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.in inh \\ ENTRY.key=id.entry text \\ ENTRY.value=LL_0.ininh$
|-
|style="background-color:#FFF;padding:2px 30px"| $L.id \to id\ \{ENTRY addtype(key, value)\}$|style="background-color:#FFF;padding:2px 30px"| $ENTRY.key=id.entry text \\ ENTRY.value=L.ininh$
|}
Семантическое правило $L.in inh = T.type$, связанное с продукцией $D \to TL$, определяет наследуемый атрибут $L.ininh$ как тип объявления. Затем приведенные правила распространяют этот тип вниз по дереву разбора с использованием атрибута $L.ininh$. Транслирующий символ $ENTRY$, связанный с продукциями для $L$, вызывает процедуру $addtype$ для добавления типа каждого идентификатора к его записи в таблице символов (по ключу, определяемому атрибутом $entrytext$).
==Пример работы с атрибутами в нисходящем разборе==
Рассмотрим работы с атрибутами на примере LL(1)-грамматики арифметических выражений, которая уже была разобрана [[Построение FIRST и FOLLOW#Пример | ранее]] и расширим код [[Предиктивный_синтаксический_анализ | разборщика]] для нее:
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
[[Файл:2add3add7.png|600px|center|thumb| Дерево разбора для '''$x2\ A +\to A 3\alpha +\Leftrightarrow x7$''']] ==Атрибуты в ANTLR==g(A_1 Общедоступный генератор разборщиков ANTLR<ref>[http://www.antlr.org/ ANTLR {{---}} Parser generator]</ref> поддерживает синтаксически управляемое определение. Рассмотрим для той же грамматики арифметических выражений с операторами <tex>+, \alpha) \\x\ A \to \beta \Leftrightarrow x=f(\beta)$*</tex>, скобками и выводом результата выражения пример на ANTLR.
В продукции для нетерминала <картинкаcode>expr</code> определяется возвращаемое значение (<code>['''int''' val]</code>). Обращение к этому атрибуту имеет вид <code>$expr.value</code>. В фигурных скобках записаны семантические правила.
Разобранные нетерминалы возвращают результат, вычисленный в поддереве(<code>returns [int val]</code>) как свой синтезируемый атрибут, процесс вычисления которого описан в фигурных скобках <code>{ $val ===Более сложный пример===$exprP.val; }</code>.
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['''int''' i] '''returns''' '''[int''' val]
: { $val = $i; }
| '*' fact expr = termP[$i * $fact.val] { $val = $expr.val; }
;
Техническая деталь для ANTLR, правила для лексического анализатора:
WS : [ \t \r \n]+ -> skip ;
NUM : [0-9]+ ;
== Примечания ==<references/wikitex>
== Источники информации ==
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Первое издание. 2003. Стр. 279 {{---}} 305.
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс. Второе издание. 2008. Стр. ??? 383 {{---}} ???398.* [https://theantlrguy.atlassian.net/wiki/display/ANTLR4/Parser+Rules#ParserRules-RuleAttributeDefinitions| ANTLR Documentation {{- --}} Rule Attribute Definitions]* [http://www.amazon.com/The-Definitive-ANTLR-4-Reference/dp/1934356999| The Definitive ANTLR 4 Reference]
[[Категория: Методы трансляции]]
[[Категория: Нисходящий разбор]]