В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 37
Текст из файла (страница 37)
Отметим, что при генерации кодарассматриваемым методом не осуществляется распределение регистров. Этоявляется отдельной задачей.Стоимость может определяться различными способами, например, числом обращений к памяти при выборке и исполнении команды. Здесь мыне рассматриваем этого вопроса. На рис. 9.24 приведен пример покрытияпромежуточного дерева рис. 9.23 образцами из табл. 9.2. В рамки заключены фрагменты дерева, сопоставленные образцу правила, номер которогоуказывается в левом верхнем углу рамки. В квадратных скобках указанырезультирующие вершины.Приведенное покрытие дает такую последовательность команд:11416742MOVEMOVEADDMOVEADDMOVEADDMOVE#a,Ra#b,Rb#y,Rb#i,Ri#z(Ri),Rb(Rb),Rb#5,RbRb,#x(Ra)Основная идея подхода заключается в том, что каждая команда машиныописывается в виде такого образца.
Различные покрытия дерева промежуточного представления соответствуют различным последовательностям машинных команд. Задача выбора команд состоит в том, чтобы выбрать наилучшийспособ реализации того или иного действия или последовательности действий, т. е. выбрать оптимальное (в некотором смысле) покрытие.Для выбора оптимального покрытия было предложено несколько интересных алгоритмов, в частности, использующих динамическое программирование [14, 18]. Мы здесь рассмотрим алгоритм, предложенный в [16].9.10.2.
Построение покрытия. В качестве промежуточного представления будем использовать абстрактное дерево программы. Абстрактное деревов качестве внутренних вершин содержит операции. В нашем случае при построении абстрактного дерева будем исходить из следующих предположений:1) каждая переменная программы адресуется суммой двух констант —адреса области памяти и смещения в этой области;2) для выборки значения по адресу используется операция @ — косвеннаяадресация;3) все массивы одномерные, причем размер элемента массива — одна адресуемая единица.204Глава 9.
Генерация кодаРис. 9.24Корень каждого образца помечен символом, который мы будем называтьнетерминальным (или нетерминалом). Смысл использования этого терминабудет объяснен ниже при использовании синтаксического анализа для построения покрытия. Некоторые листья образцов также могут быть помеченынетерминалами.
Содержательно можно считать, что нетерминал задает типрезультата, вычисляемого поддеревом. В нашем случае нетерминалов всегодва: Reg говорит о том, что результат должен размещаться в регистре, Stat —что результат не вырабатывается.9.10. Генерация оптимального кода методами сопоставления образцов205Задача построения покрытия заключается в таком наложении образцовна абстрактное дерево программы, что:1) всё дерево накрыто набором образцов;2) накрывающие образцы не пересекаются;3) во внутренних вершинах образцы «склеиваются» по нетерминалам, т. е.тип вершины-корня образца, примененного в вершине n абстрактногодерева, совпадает с типом вершины образца, для которого вершина nявляется листом.Для согласования типов вершин могут использоваться «цепные» образцы,т.
е. образцы типа Нетерминал → Нетерминал. Цепные образцы не зависятот операций, следовательно, их необходимо проверять отдельно. Применениеодного цепного образца может зависеть от применения другого цепного образца. Следовательно, применение цепных образцов необходимо проверять дотех пор, пока можно применить хотя бы один из цепных образцов. Мы предполагаем, что в грамматике нет циклов в применении цепных образцов.Построение всех вариантов покрытия дано ниже в алгоритме 9.1. В этомалгоритме дерево выражения обходится сверху-вниз, и в нем ищутся поддеревья, сопоставимые с образцами.
Обход дерева осуществляется процедуройPARSE. После обхода поддерева данной вершины в ней применяется процедура MATCHED, которая пытается найти все образцы, сопоставимые поддеревуданной вершины. С этой целью для каждого образца осуществляется рекурсивный обход поддерева. В результате обхода дерева снизу-вверх для каждойвершины n (как внутренней, так и листа) для каждого нетерминала находятсявсе покрытия поддерева с корнем n, помеченные этим нетерминалом (это множество может быть и пустым).
Точнее, для вершины n находится множествообразцов, применимых в этой вершине с учетом найденных образцов в вершинах дерева — потомках n, соответствующих листьям-нетерминалам образца,и цепных правил, примененных, в частности, к терминальным листьям образца (что соответствует листьям дерева программы). Для последующего отбораобразцов при поиске оптимального покрытия и генерации оптимального кодаиспользуется принцип динамического программирования: из всех возможныхспособов покрытия поддерева, соответствующих данному нетерминалу, выбирается тот, который дает минимальную суммарную стоимость. В данномслучае это возможно, поскольку стоимость полного покрытия определяетсякак сумма стоимостей его составляющих.Для реализации этого принципа каждой вершине ставится в соответствие множество HashMap nonTerm, хранящее для каждого нетерминаламинимальную стоимость покрытия поддерева для этой вершины, обеспечивающего соответствие нетерминала корню образца, и образец, дающий эту206Глава 9.
Генерация кодаминимальную стоимость (opt OptChoise). Список sons содержит потомковданной вершины, HashMap rules содержит множество проавил для каждогонетерминала. HashMap invert дает для каждого нетерминала множество левых частей для цепных правил с данной правой частью.Алгоритм 9.1class Tnode {Integer op;ArrayList sons;HashMap nonTerm;// Для каждого нетерминала OptChoice}class Pattern {Integer op;ArrayList sons; // Список Pattern}class Rule {int cost;Pattern pat;}class OptChoice {int cost;Rule rule;}HashMap invert; // Отображение нетерминала во множество// цепных правил с данной правой частьюHashSet NTerms; // НетерминалыHashMap rules; // Отображение нетерминала во множество правилHashSet operations;/** ******************************************************** */void Parse(Tnode n) {int i;Integer nextNT;OptChoice opt;Rule nextRule;Iterator NTiter = NTerms.iterator();while (NTiter.hasNext()) {// Для каждого нетерминалаnextNT = (Integer) NTiter.next();9.10.
Генерация оптимального кода методами сопоставления образцов207opt = (OptChoice) n.nonTerm.get(nextNT);opt.cost = maxCost;opt.rule = undef;HashSet currentRules = (HashSet) rules.get(nextNT);// Множество правил для нетерминалаIterator ruleIter = currentRules.iterator();while (ruleIter.hasNext()) {nextRule = (Rule) ruleIter.next();if (nextRule.pat.op == n.op) {int cost = Matched(n, nextRule);if (cost != maxCost)if (opt.cost > cost) {opt.cost = cost;opt.rule = nextRule;n.nonTerm.put(nextNT, opt);}}}boolean stop = false;while (!stop) {stop = true;NTiter = NTerms.iterator();while (NTiter.hasNext()) {nextNT = (Integer) NTiter.next();opt = (OptChoice) n.nonTerm.get(nextNT);if (opt.rule != undef) {HashSet inv = (HashSet) invert.get(nextNT);Iterator invIter = inv.iterator();while (invIter.hasNext()) {nextRule = (Rule) invIter.next();opt = (OptChoice) n.nonTerm.get(nextNT);if (nextRule.cost < opt.cost) {opt.cost = nextRule.cost;opt.rule = nextRule;n.nonTerm.put(nextNT, opt);}}}}}}}/** ******************************************************** */int Matched(Tnode n, Rule r) {208Глава 9.
Генерация кодаint m, i;if (operations.contains(r.pat.op))// r.pat.op может содержать операции и нетерминалыif (r.pat.op == n.op)if ((m = Arity(r.pat.op)) == 0)// нуль-местная операция, например, constreturn 0;else {// внутренняя вершинаint cost = 0, costSum = r.cost;for (i = 0; i < m; i++) {cost = Matched((Tnode) n.sons.get(i), (Rule) r.pat.sons.get(i));if (cost != maxCost)costSum += cost;else {costSum = maxCost;break;}}return costSum;}elsereturn maxCost;else// Нетерминалreturn ((OptChoice) n.nonTerm.get(r.pat.op)).cost;}Объем вычислений пропорционален объему дерева, умноженному на числонетерминалов и числу правил для каждого нетерминала, т.е.
имеет временнуюи емкостную сложности порядка O(n).Рассмотрим вновь пример рис. 9.23.В табл. 9.3 приведен результат работы алгоритма.9.10.3. Выбор дерева вывода наименьшей стоимости. Дерево наименьшей стоимости определяется как дерево, соответствующее минимальной стоимости покрытия. Дереву наименьшей стоимости соответствует наборкоманд, соответствующих образцам, реализующих это дерево. Выбор оптимального покрытия и соответствующих команд осуществляется в процессеобхода дерева: при движении сверху-вниз выбирается оптимальное покрытие, при движении снизу-вверх осуществляется генерация команд.
Обходдерева реализуется двумя взаимно рекурсивными функциями: функция CodeGen(Tnode n, NonTerm NT) осуществляет обход поддерева с вершиной nи (оптимальным) образцом, примененным в этой вершине для нетерминалаNT. Функция TreePass(Tnode n, Rule r) осуществляет обход поддерева с вершиной n согласно образцу r.9.10. Генерация оптимального кода методами сопоставления образцов209Т а б л и ц а 9.3Операция Длина Правила (стоимость)=152 (22)+34 (5)a11 (2)x11 (2)+114 (16) 5 (17)@97 (11)+85 (13) 6 (11)+34 (5)b11 (2)y11 (2)@47 (7)3 (6)+34 (5)5 (6)i11 (2)z11 (2)511 (2)5 (6)5 (6)void CodeGen(Tnode n, Integer NT) {Rule rule = ((OptChoice) n.nonTerm.get(NT)).rule;// Выбираем оптимальное правило для NTTreePass(n, rule);GenInstr(rule);}/** ******************************************************** */void TreePass(Tnode n, Rule r) {int m, i;if (operations.contains(r.pat.op))// Проверка: операция или нетерминалif ((m = Arity(r.pat.op)) != 0)for (i = 0; i < m; i++)TreePass((Tnode) n.sons.get(i), (Rule) r.pat.sons.get(i));elseCodeGen(n, r.pat.op);}210Глава 9.
Генерация кода9.10.4. Синтаксический анализ для T-грамматик. Обычно код генерируется из некоторого промежуточного языка с довольно жесткой структурой. В частности, для каждой операции известна ее размерность, т. е.число операндов, большее или равное 0. Операции задаются терминальнымисимволами, и наоборот — будем считать все терминальные символы знаками операций. Назовем грамматики, удовлетворяющие этим ограничениям,T-грамматиками. Правая часть каждой продукции в Т-грамматике естьправильное префиксное выражение, которое может быть задано следующимопределением.1) Операция размерности 0 является правильным префиксным выражением.2) Нетерминал является правильным префиксным выражением.3) Префиксное выражение, начинающееся со знака операции размерностиn > 0, является правильным, если после знака операции следует nправильных префиксных выражений.4) Ничто другое не является правильным префиксным выражением.Длины всех выражений из входной цепочки a1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
