Пред.СтраницаСлед.Страница Раздел Содержание
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 и выполнять действия, предписываемые
инструкциями.