Системы восходящего переписывания деревьев

Деревянные грамматики лежат в основе систем восходящего переписывания деревьев (Bottom-Up Rewriting Systems, BURS), которые на сегодняшний день являются одним из наиболее распространенных способов описания кодогенераторов. Точнее, BURS позволяет построить алгоритм выбора инструкций, который при определенных допущениях строит оптимальный код.

Деревянные грамматики представляются естественным выбором как механизм описания выбора команд, поскольку являются удобной формализацией сопоставления с образцом.

Для использования в качестве формализма описания выбора команд понятия теории деревянных грамматик интерпретируются следующим образом:

нетерминалы обозначают режимы адресации или классы размещения значений (регистр, непосредственный операнд и т.д.)
цепные правила обозначают преобразования типов или пересылки
язык, определяемый грамматикой - это формат внутреннего представления программы перед выбором команд
вывод дерева в данной грамматике - последовательность команд

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

Содержание раздела