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

<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>