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

5.4.4. Порядок построения АП

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

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

1) Удалим из правил заданной LАТ-грамматики все атрибуты и правила их вычисления. В результате получим транслирующую грамматику.
2) Для полученной транслирующей грамматики построим преобразователь.  Учитывая, что такой преобразователь в дальнейшем должен быть использован для работы с атрибутами, внесем следующие изменения в правила его построения:
     а) чтобы первая команда преобразователя могла установить начальные значения последующих атрибутов начального символа грамматики, в качестве начальной примем конфигурацию следующего вида:

     (s0 , <заданная цепочка>, h 0 ),
     б) откажемся от совмещения команд для правил вида <А> --> b a ,
где b является терминалом, имеющим атрибут, и  a  - некоторая цепочка из терминальных и нетерминальных символов, используя вместо команды
     f(s0, b,<A>) = (s0, aR)
две команды
     f * 0(s0, b, <A>) = (s0, aRb)
     f(s0, b, b) = (s0, $),
поскольку при выполнении  одной  команды  терминальный  символ и, следовательно, его атрибут не записываются в магазин, что  делает невозможным формирование  указателя для правила вычисления атрибута, в котором используется атрибут терминала b.
3) Для каждого правила заданной LАТ- грамматики построим инструкцию, описывающую построение фрагмента стека при записи правой части правила в стек.
4) Пронумеруем инструкции и введем обозначение инструкции в виде символа  #  с последующим номером инструкции. Во всех командах построенного преобразователя, выполняющих запись цепочек в стек, заменим цепочки обозначениями соответствующих инструкций, выполняющих запись атрибутной цепочки в стек. В результате получаем функцию преходов в виде:
     f(s0, <входной символ>,<символ в вершине магазина>) = (s0, <номер выполняемой инструкции>).


Подразумевается, что построенный таким образом АТ-преобразователь должен работать в соответствии с правилами 1-6 и выполнять действия, предписываемые инструкциями.


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