5.3. L - атрибутные транслирующие грамматики
5.3.1. L - атрибутные транслирующие грамматики
Задачей настоящего
раздела является не только знакомство с атрибутными описаниями переводов,
но и с нисходящими атрибутными
преобразователями. Они должны обрабатывать цепочки входных символов с атрибутами
и для каждой входной цепочки либо строить выходную цепочку в качестве ее
перевода,
либо отвергать ее, как не принадлежащую входному языку. Такие устройства
должны обеспечивать вычисление атрибутов в ходе нисходящего разбора. Возможность
такой обработки предоставляет не всякая АТ-грамматика,
а только грамматики, отвечающие определенным требованиям, которые выражаются
в виде ограничений как на характер зависимости атрибутов правил грамматики,
так и на вид правил вычисления атрибутов. Вначале рассмотрим подкласс атрибутных
транслирующих грамматик
с ограничениями на зависимости атрибутов, обеспечивающими их вычисление
при нисходящем разборе. Такие грамматики называются L
- атрибутными транслирующими грамматиками (LАТ-грамматиками).
Определение.
АТ-грамматика является L - атрибутной транслирующей грамматикой, если выполняются следующие три условия: 1) Каждый наследуемый атрибут символа правой части правила грамматики должен вычисляться с использованием либо наследуемых атрибутов символов левой части правила, либо с использованием произвольных атрибутов символов правой части правила, расположенных левее данного символа. 2) Каждый синтезируемый атрибут символа левой части правила грамматики должен вычисляться с использованием наследуемых атрибутов этого символа левой части правила или произвольных атрибутов символов правой части этого правила. 3) Каждый синтезируемый
атрибут символа действия должен вычисляться по наследуемым атрибутам этого
символа действия.
|
Чтобы убедиться
в том, что заданная АТ-грамматика обладает
свойствами LАТ-грамматики, нужно проверить
для каждого правила грамматики выполнение условий 1 и 2, а также для каждого
символа действия - выполнение условия 3. Такая проверка заключается в анализе
зависимостей атрибутов для каждого правила их вычисления.
В качестве иллюстрации
выполним анализ возможных зависимостей атрибутов, отвечающих описанным
условиям, для следующего правила:
Отметим также, что правила вычисления
не могут иметь, например, следующий вид:
Согласно условию правила 2 при вычислении атрибутов x1 и y1 могут быть использованы любые атрибуты кроме самих x1, y1.
Условие 3 используется для проверки символов действия. Чтобы убедиться в его выполнении, нужно просмотреть список аргументов правил вычисления атрибутов и убедиться, что среди них нет синтезированных атрибутов.