В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 27
Текст из файла (страница 27)
На первом проходе распределяем регистры. Если в некоторой вершине обнаруживается, что ее поддерево общее с уже вычисленным ранее, но значение регистра потеряно, то в такой вершине на втором проходе необходимо сгенерировать команду сброса регистра в рабочую память. Выигрыш в коде будет, если стоимостькоманды сброса регистра + доступ к памяти в повторном использовании этой памяти не превосходит стоимости заменяемого поддерева.
Поскольку стоимость команды MOVE известна, можно сравнить стоимостии принять оптимальное решение: пометить предыдущую вершину длясброса либо вычислять поддерево полностью.9.99.9.1Генерация оптимального кода методами синтаксического анализаСопоставление образцовТехника генерации кода, рассмотренная выше, основывалась на однозначном соответствии структуры промежуточного представления и описывающей это представление грамматики. Недостатком такого “жесткого” подхода является то, что как правило одну и ту же программу напромежуточном языке можно реализовать многими различными способами в системе команд машины. Эти разные реализации могут иметьразличную длину, время выполнения и другие характеристики.
Для генерации более качественного кода может быть применен подход, изложенный в настоящей главе.Этот подход основан на понятии “сопоставления образцов”: командам машины сопоставляются некоторые “образцы”, вхождения которых ищутся в промежуточном представлении программы, и делаетсяпопытка “покрыть” промежуточную программу такими образцами. Если это удается, то по образцам восстанавливается программа уже в кодах. Каждое такое покрытие соответствует некоторой программе, реализующей одно и то же промежуточное представление.На рис.
9.15 показано промежуточное дерево для оператора a = b[i] +5, где a, b, i – локальные переменные, хранимые со смещениями x, y, zсоответственно в областях данных с одноименными адресами.Элемент массива b занимает память в одну машинную единицу. 0местная операция const возвращает значение атрибута соответствующейвершины промежуточного дерева, указанного на рисунке в скобках после оператора. Одноместная операция @ означает косвенную адресациюи возвращает содержимое регистра или ячейки памяти, имеющей адрес, задаваемый аргументом операции.На рис.
9.16 показан пример сопоставления образцов машинным командам. Приведены два варианта задания образца: в виде дерева и вГЛАВА 9. ГЕНЕРАЦИЯ КОДА170FRQVWDFRQVW[#FRQVWFRQVWE#FRQVW\FRQVWLFRQVW]Рис. 9.15:виде правила контекстно-свободной грамматики. Для каждого образца указана машинная команда, реализующая этот образец, и стоимостьэтой команды.В каждом дереве-образце корень или лист может быть помечен терминальным и/или нетерминальным символом. Внутренние вершины помечены терминальными символами – знаками операций.
При наложении образца на дерево выражения, во-первых, терминальный символобразца должен соответствовать терминальному символу дерева, и, вовторых, образцы должны “склеиваться” по типу нетерминального символа, т.е. тип корня образца должен совпадать с типом вершины, в которую образец подставляется корнем.
Допускается использование “цепных” образцов, т.е. образцов, корню которых не соответствует терминальный символ, и имеющих единственный элемент в правой части. Цепные правила служат для приведения вершин к одному типу. Например,в рассматриваемой системе команд одни и те же регистры используются как для целей адресации, так и для вычислений. Если бы в системе команд для этих целей использовались разные группы регистров, тов грамматике команд могли бы использоваться разные нетерминалы,а для пересылки из адресного регистра в регистр данных могла бы использоваться соответствующая команда и образец.9.9. ГЕНЕРАЦИЯ ОПТИМАЛЬНОГО КОДА МЕТОДАМИ СИНТАКСИЧЕСКОГО АНАЛИЗА171H[jZa_p5HJFRQVWDhfZg^Zklhbfhklv5HJo FRQVW029(FRQVW56WDWo 5HJFRQVW5HJ029(5MFRQVW5L 5HJo #5HJFRQVW029(FRQVW5L5M 5HJo 5HJFRQVW$''FRQVW55HJo 5HJ5HJ$''5M5L6WDW5HJMIjZ\beh]jZffZlbdbFRQVW5HJL# 5HJM 5HJL5HJ5HJLFRQVW5HJFRQVW5HJL5HJM 5HJL5HJL#5HJM5HJo 5HJ# 5HJFRQVW $''FRQVW5M5LFRQVW# 5HJL 5HJM5HJo # 5HJ029(5M5LРис.
9.16:Нетерминалы Reg на образцах могут быть помечены индексом (i илиj), что (неформально) соответствует номеру регистра и служит лишь дляпояснения смысла использования регистров. Отметим, что при генерации кода рассматриваемым методом не осуществляется распределениерегистров. Это является отдельной задачей.Стоимость может определяться различными способами, например чис-ГЛАВА 9. ГЕНЕРАЦИЯ КОДА172лом обращений к памяти при выборке и исполнении команды. Здесьмы не рассматриваем этого вопроса. На рис. 9.17 приведен пример покрытия промежуточного дерева рис.
9.15 образцами рис. 9.16. В рамкизаключены фрагменты дерева, сопоставленные образцу правила, номеркоторого указывается в левом верхнем углу рамки. В квадратных скобках указаны результирующие вершины.Приведенное покрытие дает такую последовательность команд:MOVE b,RbADD #y,RbMOVE i,RiADD z(Ri),RbMOVE (Rb),RbADD #5,RbMOVE a,RaMOVE Rb,x(Ra)Основная идея подхода заключается в том, что каждая команда машины описывается в виде такого образца.
Различные покрытия дерева промежуточного представления соответствуют различным последовательностям машинных команд. Задача выбора команд состоит в том,чтобы выбрать наилучший способ реализации того или иного действияили последовательности действий, т. е. выбрать в некотором смысле оптимальное покрытие.Для выбора оптимального покрытия было предложено несколько интересных алгоритмов, в частности использующих динамическое программирование [11, 13]. Мы здесь рассмотрим алгоритм [12], комбинирующий возможности синтаксического анализа и динамического программирования. В основу этого алгоритма положен синтаксический анализнеоднозначных грамматик (модифицированный алгоритм Кока, Янгера и Касами [15, 16]), эффективный в реальных приложениях. Этот жеметод может быть применен и тогда, когда в качестве промежуточногопредставления используется дерево.9.9.2Синтаксический анализ для T-грамматикОбычно код генерируется из некоторого промежуточного языка с довольно жесткой структурой.
В частности, для каждой операции известна ее размерность, то есть число операндов, большее или равное 0. Операции задаются терминальными символами, и наоборот – будем считатьвсе терминальные символы знаками операций. Назовем грамматики,удовлетворяющие этим ограничениям, T-грамматиками. Правая частькаждой продукции в Т-грамматике есть правильное префиксное выражение, которое может быть задано следующим определением:(1) Операция размерности 0 является правильным префиксным выражением;9.9. ГЕНЕРАЦИЯ ОПТИМАЛЬНОГО КОДА МЕТОДАМИ СИНТАКСИЧЕСКОГО АНАЛИЗА173>6WDW @>5HJ5D@FRQVW[FRQVWD>5HJ5E@FRQVW>5HJ5E@#>5HJ5E@>5HJ5E@#>5HJ5E@FRQVWEFRQVW\>5HJ5L@FRQVW]FRQVWLРис.
9.17:(2) Нетерминал является правильным префиксным выражением;(3) Префиксное выражение, начинающееся со знака операции размерности n > 0, является правильным, если после знака операции сле-ГЛАВА 9. ГЕНЕРАЦИЯ КОДА174дует n правильных префиксных выражений;(4) Ничто другое не является правильным префиксным выражением.Образцы, соответствующие машинным командам, задаются правилами грамматики (вообще говоря, неоднозначной). Генератор кода анализирует входное префиксное выражение и строит одновременно все возможные деревья разбора. После окончания разбора выбирается дерево снаименьшей стоимостью.
Затем по этому единственному оптимальномудереву генерируется код.Для T-грамматик все цепочки, выводимые из любого нетерминалаA, являются префиксными выражениями с фиксированной арностьюопераций. Длины всех выражений из входной цепочки a1 ... an можнопредварительно вычислить (под длиной выражения имеется ввиду длина подстроки, начинающейся с символа кода операции и заканчивающейся последним символом, входящим в выражение для этой операции).
Поэтому можно проверить, сопоставимо ли некоторое правило сподцепочкой ai ... ak входной цепочки a1 ... an , проходя слева-направо поai ... ak . В процессе прохода по цепочке предварительно вычисленныедлины префиксных выражений используются для того, чтобы перейтиот одного терминала к следующему терминалу, пропуская подцепочки,соответствующие нетерминалам правой части правила.Цепные правила не зависят от операций, следовательно, их необходимо проверять отдельно.
Применение одного цепного правила можетзависеть от применения другого цепного правила. Следовательно, применение цепных правил необходимо проверять до тех пор, пока нельзяприменить ни одно из цепных правил. Мы предполагаем, что в грамматике нет циклов в применении цепных правил. Построение всех вариантов анализа для T-грамматики дано ниже в алгоритме 9.1. Тип Titemв алгоритме 9.1 ниже служит для описания ситуаций (т.е.
правил вывода и позиции внутри правила). Тип Tterminal – это тип терминальногосимвола грамматики, тип Tproduction – тип для правила вывода.Алгоритм 9.1Tterminal a[n];setofTproduction r[n];int l[n]; // l[i] - длина a[i]-выраженияTitem h; // используется при поиске правил,// сопоставимых с текущей подцепочкой// Предварительные вычисленияДля каждой позиции i вычислить длину a[i]-выражения l[i];// Распознавание входной цепочкиfor (int i=n-1;i>=0;i--){for (каждого правила A -> a[i] y из P){j=i+1;if (l[i]>1)9.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
