Пред.СтраницаСлед.Страница Раздел Содержание


5.5. Резюме.

    Атрибутные грамматики отличаются от транслирующих грамматик тем, что терминальные, нетерминальные и операционные символы могут иметь атрибуты, которые могут быть синтезируемыми или наследуемыми, и каждому правилу грамматики приписываются правила вычисления атрибутов.

    Построение выводов с помощью правил АТ-грамматик совмещается с вычислением значений атрибутов. Такие вычисления для синтезируемых атрибутов не всегда оказывается возможным выполнить при подстановке правой части правила, поэтому при выводе приходится сохранять те выражения, которые нельзя вычислить до момента определения значений, входящих в них величин.

    Построить преобразователь, реализующий перевод, определяемый АТ-грамматикой, оказывается возможным не для любой АТ-грамматики, а только такой, для которой выполняются требования L-атрибутных грамматик, и которая представлена в форме простого присваивания. Грамматика относится к классу L-атрибутных грамматик, если наследуемые атрибуты правых частей правил грамматики вычисляются по наследуемым атрибутам левой части или по атрибутам правой части, расположенным левее данного, и если синтезируемые атрибуты символов действия вычисляются по их наследуемым атрибутам.

    АТ-грамматика находится в форме простого присваивания, если каждое правило вычисления атрибутов представляет собой оператор присваивания с идентификатором или константой в правой части. АТ-грамматику можно преобразовать к форме простого присваивания путем замены функций, используемых в правых частях правил вычисления значений атрибутов, операционными символами, и включения этих символов в правила грамматики.
Нисходящий АП-преобразователь в процессе работы строит левый вывод входной цепочки в магазине, записывая в него атрибуты вместе с символами, образующими правила транслирующей грамматики. Если значения атрибутов при записи  в  магазин  не определены, то  вместо  их  значений записываются указатели на элементы магазина,  в которых  должны находиться эти значения или из которых нужно взять эти значения.
Чтобы указатели не зависели от положения вершины  магазина, необходимо использовать в качестве значения указателя смещение относительно рассматриваемого атрибута.
Запись значений атрибутов и установка указателей совмещается с  записью  в магазин правой части правила.  При этом все действия, связанные с построением  фрагмента  магазина,  соответствующего правой части правила грамматики, могут быть определены заранее  на  этапе  проектирования  преобразователя   и оформлены в виде инструкции, которая должна быть связана с командой преобразователя,  выполняющей запись правой части правила в магазин.
В каждом такте преобразователь читает символ, находящийся в вершине магазина,  и в зависимости от вида символа выполняет действия, предписываемые правилами работы и командами преобразователя.
Если задана LАТ- грамматика в форме простого  пприсваивания, то  построение преобразователя заключается в выделении из заданной грамматики соответствующей ей транслирующей грамматики, построении  команд  преобразователя для этой транслирующей грамматики, построении инструкций, описывающих выделение фрагментов магазина  для  правых  частей правил LАТ-грамматики,  и связывании инструкций с командами преобразователя. Для построения детерминированного нисходящего АТ-преобразователя необходимо, чтобы входная грамматика транслирующей грамматики, лежащей в основе заданной LАТ-грамматики, принадлежала  классу LL(1) -грамматик.
Восходящий АП-преобразователь выполняет перевод, задаваемый S-атрибутной грамматикой. Он выполняет переходы и действия, предписываемые таблицами перехода восходящего распознавателя. Таблицы распознавателя  строятся по входной грамматике, которая получается из заданной S-атрибутной грамматики.
Если входная грамматика принадлежит к классу LR(0) или SLR(1), то для заданной грамматики можно построить детерминированный АП-преобразователь. Такой преобразователь использует расширенные операции свертки и переноса, учитывающие необходимость работы с атрибутами.
 


Пред.Страница След.Страница Раздел Содержание