Классы атрибутных грамматик и их реализация
В общем виде реализация вычислителей для атрибутных грамматик вызывает значительные трудности. Это связано с тем, что множество значений атрибутов,
связанных с данным деревом, приходится вычислять в соответствии с зависимостями атрибутов, которые образуют ориентированный ациклический граф. На практике стараются осуществлять процесс вычисления атрибутов, привязывая его к тому или иному способу обхода дерева. Рассматривают многовизитные, многопроходные и другие атрибутные вычислители. Это, как правило, ведет к ограничению допустимых зависимостей между атрибутами, поддерживаемых вычислителем.
Простейшими подклассами атрибутных грамматик, вычисления
всех атрибутов для которых может быть осуществлено одновременно с синтаксическим анализом, являются S-атрибутные и L-атрибутные грамматики.
Определение. Атрибутная грамматика называется S-атрибутной, если она содержит только синтезируемые атрибуты.
Нетрудно видеть, что для S-атрибутной грамматики на любом дереве разбора все атрибуты могут быть вычислены за один обход дерева снизу вверх. Таким образом, вычисление атрибутов можно делать параллельно
с восходящим синтаксическим анализом, например, LR(1)-анализом.
Пример5.8. Рассмотрим S-атрибутную грамматику для перевода арифметических выражений в ПОЛИЗ. Здесь атрибут v имеет строковый тип, - обозначает операцию конкатенации. Правила вывода и семантические правила определяются следующим образом
E1  | v(E1) = v(E2) v(T) ' + ' |
| E | v(E) = v(T) |
| T | v(T1) = v(T2) v(F) '*' |
| T | v(T) = v(F) |
| F | v(F) = v(id) |
| F | v(F) = v(E) |
Определение. Атрибутная грамматика называется L-атрибутной, если любой наследуемый атрибут
любого символа Xj
из правой части каждого правила X0
грамматики зависит только от
Заметим, что каждая S-атрибутная грамматика является L-атрибутной. Все атрибуты на любом дереве для L-атрибутной грамматики могут быть вычислены за один обход дерева сверху-вниз слева-направо.
