Изменения

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

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

361 байт добавлено, 08:12, 4 июня 2015
Нет описания правки
Такой подход называется '''Синтаксически управляемой трансляцией'''.
==Синтаксически управляемая трансляция==
{{Определение
|definition =
'''Синтаксически управляемое определение''' {{---}} обобщение (СУО) является контекстно-свободной грамматикиграмматикой с атрибутами и правилами. Атрибуты связаны с грамматическими символами, в которой каждый грамматический символ имеет связанное а правила — с ним множество атрибутовпродукциями.
}}
{{Определение
|definition =
'''Атрибут''' {{---}} дополнительное поле дополнительные данные, ассоциированные с данными у терминалов и нетерминаловграмматическими символами. (Более строгое определение требует ввести систему типов)Если $X$ представляет собой символ, а $a$ — один из его атрибутов, то значение а в некотором узле дерева разбора, помеченном $X$, записывается как $X.a$. Если узлы дерева разбора реализованы в виде записей или объектов, то атрибуты X могут быть реализованы как поля данных в записях, представляющих узлы $X$. Атрибуты могут быть любого вида: числами, типами, таблицами ссылок или строками.
}}
}}
На протяжении всей статьи будет Будем рассматривать в качестве примера грамматику для арифметических выраженийс операторами $+$ и $*$:
$ S \to E \\
E \to E + T \mid T \\
T \to T \times F \mid F \\
$
S \to E
E \to TE' \\
E' \to +TE' \mid \varepsilon \\
Например, атрибутом терминала $n$ будет число, которое он представляет: ($n.val = 123$). Атрибутами нетерминалов будут значения, вычисленные в поддереве. В процессе трансляции происходит присваивание атрибутов одних элементов грамматики другим элементам грамматики, при этом присваивание может происходить более сложным способом, чем простое копирование. В некоторых случаях могут быть нужны какие-то побочные эффекты, например вывод кода или взаимодействие с глобальным контекстом. Для этого нужны транслирующие символы.   Заменим правило $T \rightarrow T*F$ на следующее: $T \rightarrow T*F\{T_0.val=T_1.val*F.val\}$, где $\{T_0.val=T_1.val*F.val\}$ {{---}} транслирующий символ. Аналогично к $F \rightarrow n$ добавляется $\{F.val = n.val\}$.  Часто бывает неоптимально для каждого действия заводить транслирующий символ(добавляется лишний нетерминал в грамматику). Поэтому при простом присваивании(копировании) атрибутов разрешают не выносить транслирующий символ и заменяют его списком действий, привязанным к правилу.   Обычно, транслирующий символ может работать только со своими атрибутами. Тогда перепишем правило $T \rightarrow T*F$ в виде: $T \rightarrow T*F\ \{MUL \ res = op_1*op_2\}$  И ассоциируем с ним следующий список действий, которые будут выполняться в особом порядке, рассмотренном далее. $ MUL.op_1 = T_1.val \\ MUL.op_2 = F.val \\ T_0.val = MUL.res $
Атрибуты делятся на '''наследуемые''' и '''синтезируемые'''.
}}
Рассмотрим пример ===Пример S-атрибутной грамматики. === Выпишем все правила синтексическ управляемое определение для грамматики арифметических выражений, добавив транслирующие символы с операторами $+$ и ассоциировав с каждым правилом грамматики список семантических правил.$*$: 
{| style="background-color:#CCC;margin:0.5px"
!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"| $val\ E \to E + T\ \{ADD\ res = op_1 + op_2\}$
|}
В нашем примере видно, что $.val$ зависит только от детей, то есть это синтезируемый атрибут. Результат умножителя ($MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемым(аналогично с сумматором ADD).
<картинка>
После такого разбора по таким правилам, в атрибуте $S.val$ корня дерева разбора будет лежать вычисленное значение выражения.Для изящности можно добавить еще одно Можно, например сразу напечатеть его, добавив правило $S \to E$ и действие(семантическое к нему правило) {print(ES.val)}. Тогда сразу после разбора выражения будет напечатан его результат.
Хотя всегда можно переписать синтаксически управляемое определение таким образом, чтобы использовать только синтезируемые атрибуты, зачастую более удобно и естественно воспользоваться также и наследуемыми атрибутами.
}}
Рассмотрим пример с ===Пример L-атрибутной грамматики.===Выпишем правила продукции и ассоциируем с ними действия(семантические правила) для грамматики объявления переменных:
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Правило грамматикиПродукции
!style="background-color:#EEE"| Семантические правила
|-
496
правок

Навигация