[ 15. Выбор инструкций при
генерации кода
• Постановка задачи
• Деревянные языки
• Деревянные грамматики
• BURS и ее приложения
Лекция 15. Выбор инструкций при генерации кода
В этой лекции рассматриваются следующие вопросы:
• Постановка задачи выбора оптимальных инструкций
• Деревянные языки
• Деревянные грамматики
• BURS и ее приложения Выбор инструкций Задача:
•сопоставление конструкциям исходной программы последовательностей машинных инструкций (проекции конструкций) •выбор размещений для переменных и промежуточных результатов •выбор наилучших режимов адресации Способ:
•формализация представления исходной программы с помощью деревянных грамматик •описание машинной программы в терминах покрытий деревьев Выбор инструкций Выбор инструкций – это одна из стадий генерации машинного кода. В ее задачу входит сопоставление высокоуровневым конструкциям исходного языка последовательностей реализующих их машинных команд (проекция конструкций), выбор размещений для переменных и временных значений и выбор подходящих режимов адресации для доступа к данным.
Практически все системы команд предоставляют разнообразные режимы адресации.
Выбор способов представления операндов и конкретных инструкций для их обработки представляет нетривиальную проблему. К счастью, существует простой способ описания этого процесса, который при определенных допущениях дает оптимальный результат. Кроме того, описываемый подход дает возможность порождать генераторы кода по формальному описанию.
Для решения задачи построения генератора кода применяется теория деревянных языков и грамматик. Именно, входная программа разбивается на фрагменты (выражения), каждый из которых трактуется как предложение языка специального вида.
Вывод этого предложения в грамматике, определяющей такой язык, затем интерпретируется как последовательность машинных инструкций.
Деревянные языки a Скобочная запись дерева: a (b, c (d, e)) b c d e Алфавит:
A={l1,l2,…lk} Функция арности:
#: A{0,1,2,…} Множество всех деревьев в алфавите A:
T*A={}{a : aA, #(a)=0}{a (t1,…,t#(a)) : aA, #(a)>0, tiT*A, ti} Деревянный язык в алфавите A:
L T*A Деревянные языки Деревянные языки позволяют описать множества деревьев, обладающих определенными свойствами (везде далее будут иметься в виду деревья, содержащие конечное число вершин). Мы будем использовать скобочную запись дерева, которая может быть получена выписыванием пометок вершин при простом обходе дерева слева-направо и сверху-вниз. При этом поддеревья одной вершины отделяются от нее скобками, а между собой – запятыми.
Для определения понятия деревянного языка введем в расмотрение алфавит A, снабженный взаимно-однозначной функцией арности #, которая приписывает буквам алфавита неотрицательные целые числа.
Тогда можно определить множество всех деревьев в этом алфавите как совокупность всех деревьев, у которых каждая вершина • помечена символом a из алфавита A • имеет ровно #(a) поддеревьев • каждое ее поддерево в свою очередь является непустым деревом в алфавите A В множество всех деревьев в алфавите A мы искусственно включаем также пустое дерево, которое не содержит вершин.
Наконец, деревянным языком L в алфавите A мы назовем произвольное (возможно, пустое) подмножество множества всех деревьев в алфавите A.
Поскольку при функции арности, не превосходящей единицы, все деревья в данных определениях превращаются в линейные списки, деревянные языки можно рассматривать как обобщение обычных «линейных» языков.
Для дальнейших рассуждений введем следующие обозначения:
• через root(t) обозначим корень дерева t • через t(v) обозначим поддерево дерева t с корнем v (таким образом, t(root(t))=t) • через sons(v) обозначим множество сыновей вершины v • через son(v,i) обозачим i-го сына вершины v Для пары деревьев в одном и том же алфавите можно определить операцию подстановки. Для этого в одном из них выбирается лист, который затем заменяется на корень другого дерева. Если t2 подставляется вместо вершины v в дерево t1, то результат подстановки будем обозначать t1[vt2].
- деревянная грамматика в нормальной форме Одним из способов задания деревянных языков являются автоматные деревянные грамматики.
Деревянная грамматика в нормальной форме – это четверка, содержащая входной алфавит (снабженный функцией арности), алфавит нетерминалов, стартовый нетерминал и множество правил. В отличие от обычных контекстно-свободных грамматик, у которых в правой части правила стоит слово из объединенного алфавита терминалов и нетерминалов, в деревянной грамматике в правой части правила находится так называемый деревянный образец, который в общем случае является деревом, у которого нетерминалами могут быть помечены только (некоторые) листья. В приведенном выше определении требуется, чтобы деревянный образец имел высоту не более единицы и чтобы все его листья были помечены нетерминалами (именно поэтому данные грамматики называются грамматиками в нормальной форме).
Очевидно, что деревянные грамматики в данном виде есть обобщение обычных контекстно-свободных автоматных грамматик. Легко видеть, что возможен и контекстно-зависимый вариант – для этого достаточно разрешить присутствие деревянного образца в левой части правила. Заметим, наконец, что неавтоматный вариант контекстно-свободных грамматик не обобщается на деревянный случай – непонятно, как можно обобщить правило leaves(p) - множество листьев p, помеченных нетерминалами Для понимания того, как грамматики определяют язык, нам потребуется определить понятие выводимости образцов.
Как уже упоминалось выше, под образцом мы понимаем произвольное дерево, у которого некоторые листья помечены нетерминалами. В частности, тривиальное дерево, состоящее из одной вершины, является образцом (при этом единственная вершина может быть помечена как терминалом, так и нетерминалом).
Правила грамматики в нормальной форме содержат в правой части образцы специального вида, однако в выводе будут встречаться образцы произвольной формы.
Далее через leaves(p) мы будем обозначать множество листьев образца p, помеченных нетерминалами.
Пусть есть два образца p1 и p2, вершина vleaves(p1) и правило грамматики R=N:p’.
Будем говорить, что образец p2 выводится из образца p1 по правилу R, если v помечена нетерминалом N из левой части правила и p2 может быть получен подстановкой образца p’ из правой части правила в образец p1 вместо вершины v.
«