Атрибутные транслирующие грамматики
<wikitex>Часто, осуществляя разбор, мы хотим извлечь какие-то данные или что-то сделать, а не просто выяснить, разбирается ли текст в данной грамматике. Вообще говоря, сначала можно получить дерево разборы, а потом уже, обойдя дерево разбора, по нему производить какие-то действия. В этом случае происходит дублирование функционала: промежуточное сохранение данных в виде дерева разбора не нужно, а иногда это дерево слишком расточительно хранить в памяти. В связи с этим хочется какие-то действия производить уже на этапе разбора. Такой подход называется Синтаксически управляемой трансляцией.
| Определение: |
| Синтаксически управляемое определение — обобщение контекстно-свободной грамматики, в которой каждый грамматический символ имеет связанное с ним множество атрибутов. |
| Определение: |
| Синтаксически управляемая трансляция — это трансляция, при которой в процессе разбора строки сразу выполняются какие-то действия, не используя промежуточное представление в виде дерева разбора. |
Синтаксически управляемая трансляция вводит две новые сущности: атрибут и транслирующий символ.
| Определение: |
| Атрибут — дополнительное поле с данными у терминалов и нетерминалов. (Более строгое определение требует ввести систему типов). |
| Определение: |
| Транслирующий символ — нетерминал, который раскрывается в $\varepsilon$ и в момент раскрытия выполняет какое-то действие, которое с ним связано. Для простоты действия пишутся в фигурных скобках в том месте, где это нужно. |
Для наглядности, на протяжении всей статьи будет рассматривать в качестве примера грамматику для арифметических выражений:
$
E \to T + E \mid T \\
T \to F \times T \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) $
Например, атрибутом терминала $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\}$.
</wikitex>
