В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 37
Текст из файла (страница 37)
При наложении образцана дерево выражения, во-первых, терминальный символ образца должен соответствовать терминальному символу дерева и, во-вторых, образцы должны«склеиваться» по типу нетерминального символа, т. е. тип корня образца202Глава 9. Генерация кодадолжен совпадать с типом вершины, в которую образец подставляется корнем.Допускается использование «цепных» образцов, т. е. образцов, корню которых не соответствует терминальный символ и которые имеют единственныйэлемент в правой части. Цепные правила служат для приведения вершинк одному типу. Например, в рассматриваемой системе команд одни и те жерегистры используются как для целей адресации, так и для вычислений.Если бы в системе команд для этих целей использовались разные группырегистров, то в грамматике команд могли бы использоваться разные нетерминалы, а для пересылки из адресного регистра в регистр данных могли быиспользоваться соответствующая команда и образец.Т а б л и ц а 9.29.10.
Генерация оптимального кода методами сопоставления образцов203Нетерминалы Reg на образцах могут быть помечены индексом (i или j ),что (неформально) соответствует номеру регистра и служит лишь для пояснения смысла использования регистров. Отметим, что при генерации кодарассматриваемым методом не осуществляется распределение регистров. Этоявляется отдельной задачей.Стоимость может определяться различными способами, например, числом обращений к памяти при выборке и исполнении команды.
Здесь мыне рассматриваем этого вопроса. На рис. 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;}Объем вычислений пропорционален объему дерева, умноженному на числонетерминалов и числу правил для каждого нетерминала, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
