Изменения

==Синтаксически управляемая трансляция==

'''Синтаксически управляемое определение''' {{---}} обобщение (СУО) является контекстно-свободной грамматикиграмматикой с атрибутами и правилами. Атрибуты связаны с грамматическими символами, в которой каждый грамматический символ имеет связанное а правила — с ним множество атрибутовпродукциями.

'''Атрибут''' {{---}} дополнительное поле дополнительные данные, ассоциированные с данными у терминалов и нетерминаловграмматическими символами. (Более строгое определение требует ввести систему типов)Если $X$ представляет собой символ, а $a$ — один из его атрибутов, то значение а в некотором узле дерева разбора, помеченном $X$, записывается как $X.a$. Если узлы дерева разбора реализованы в виде записей или объектов, то атрибуты X могут быть реализованы как поля данных в записях, представляющих узлы $X$. Атрибуты могут быть любого вида: числами, типами, таблицами ссылок или строками.

На протяжении всей статьи будет Будем рассматривать в качестве примера грамматику для арифметических выраженийс операторами $+$ и $*$:

$ S \to E \\

Например, атрибутом терминала $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:#EEE"| Правило грамматикипродукции

В нашем примере видно, что $.val$ зависит только от детей, то есть это синтезируемый атрибут. Результат умножителя ($MUL.res$) зависит только от атрибутов атрибутов самого умножителя ($MUL.op_1$ и $MUL.op_2$), а значит тоже является синтезируемым(аналогично с сумматором ADD).

После такого разбора по таким правилам, в атрибуте $S.val$ корня дерева разбора будет лежать вычисленное значение выражения.Для изящности можно добавить еще одно Можно, например сразу напечатеть его, добавив правило $S \to E$ и действие(семантическое к нему правило) {print(ES.val)}. Тогда сразу после разбора выражения будет напечатан его результат.

Рассмотрим пример с ===Пример L-атрибутной грамматики.===Выпишем правила продукции и ассоциируем с ними действия(семантические правила) для грамматики объявления переменных:

!style="background-color:#EEE"| Правило грамматикиПродукции