497
правок
Изменения
Нет описания правки
Часто, осуществляя разбор, мы хотим извлечь какие-то данные или произвести какие-то действия, а не просто выяснить, разбирается ли текст в данной грамматике.
Вообще говоря, сначала можно получить [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Дерево_разбора|дерево разбора]], а потом уже, обходя его, выполнять эти действия.
В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда его просто слишком расточительно хранить в памяти целиком.
В связи с этим хочется какие-то действия производить уже на этапе разбора.
Например, мы хотим не только построить дерево разбора для арифметических выражений, а ещё и вычислить значение этого выражения. Возможно, даже не строя само дерево разбора.
Такой подход называется '''Синтаксически синтаксически управляемой трансляцией'''.
==Синтаксически управляемая трансляция==
{{Определение
|definition =
'''Атрибут''' ''(англ. attribute)'' {{---}} дополнительные данные, ассоциированные с грамматическими символами.Если $X$ представляет собой символ, а $a$ — один из его атрибутов, то значение $a$ в некотором узле дерева разбора, помеченном $X$, записывается как $X.a$. Если узлы дерева разбора реализованы в виде записей или объектов, то атрибуты $X$ могут быть реализованы как поля данных в записях, представляющих узлы $X$. Атрибуты могут быть любого вида: числами, типами, таблицами ссылок или строками.
}}
{{Определение
|definition =
Дерево разбора, в каждом узле которого атрибуты уже вычислены, называется '''аннотированным''' ''(англ. annotated)'', а процесс вычисления этих атрибутов {{- --}} '''аннотированием''' дерева разбора.
}}
{{Определение
|definition =
'''Транслирующий символ''' {{---}} нетерминал, который раскрывается в $\varepsilon$ и в момент раскрытия выполняет какое-то действие, которое связанное с ним связанодействие. Действия пишутся в фигурных скобках рядом с транслирующим символом.
}}
===Пример S-атрибутной грамматики===
<wikitex>
Выпишем синтаксически управляемое определение для грамматики арифметических выражений с операторами $+$ и $*$: (Здесь здесь $\{ADD {{...}} \}$ и $\{MUL {{...}} \}$ - транслирующие символы):
{| style="background-color:#CCC;margin:0.5px"
В нашем примере видно, что $val$ зависит только от детей в дереве разбора, то есть это синтезируемый атрибут. Результат умножителя ($MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемым(аналогично с сумматором $ADD$).
[[Файл:3mul5add4.png|500px|thumb|center|аннотированное Аннотированное дерево разбора для $'''3*5+4'''$]]
После такого разбора в $S.val$ будет лежать вычисленное значение выражения. Можно, например сразу напечатать его, добавив к нему правило $\{print(S.val)\}$.
===Пример L-атрибутной грамматики===
<wikitex>
Для наглядности рассмотрим грамматику объявления переменных: (в начале строки идет тип, затем через запятую имена переменных. Примеры строк, разбираемых в ней: '''int a''' или '''real x,y,z''' и подобные.): $D \to TL \\T \to int \mid real \\L \to L,id \mid id$
Выпишем продукции (с транслирующими символами) и ассоциируем с ними семантические правила:
|style="background-color:#FFF;padding:2px 30px"| $L_1.in=L.inh \\ ENTRY.key=id.text \\ ENTRY.value=L.inh$
|-
|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.text \\ ENTRY.value=L.inh$
|}
