В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 33
Текст из файла (страница 33)
Предположим сначала, что распределение регистров осуществляется по простейшей схеме176Глава 9. Генерация кодаРис. 9.4сверху-вниз слева-направо, как изображено на рис. 9.4. Тогда к моментугенерации кода для поддерева LR занято n регистров. Пусть поддерево Lтребует nl регистров, а поддерево R — nr регистров. Если nl = nr , то привычислении L будет использовано nl регистров и под результат будет занят(n + 1)-й регистр. Еще nr (= nl ) регистров будет использовано при вычислении R.
Таким образом, общее число использованных регистров будет равноn + nl + 1.Если nl > nr , то при вычислении L будет использовано nl регистров. Привычислении R будет использовано nr < nl регистров, и всего будет использовано не более чем n + nl регистров. Если nl < nr , то после вычисления L подрезультат будет занят один регистр (предположим, (n + 1)-й), а nr регистровбудет использовано для вычисления R. Всего будет использовано n + nr + 1регистров.Видно, что для деревьев, совпадающих с точностью до порядка потомков каждой вершины, минимальное число регистров при распределении ихслева-направо достигается на дереве, у которого в каждой вершине слева расположено более «сложное» поддерево, требующее большего числа регистров.Таким образом, если в каждой внутренней вершине дерева правое поддеревотребует меньшего числа регистров, чем левое, то, обходя дерево слева направо, можно оптимально распределить регистры.
Без перестроения дереваэто означает, что если в некоторой вершине дерева справа расположено болеесложное поддерево, то сначала сгенерируем код для него, а затем уже длялевого поддерева.Алгоритм работает следующим образом. Сначала осуществляется разметка синтаксического дерева. Разметка позволяет определить для каждогоподдерева, сколько регистров потребуется для его вычисления. Разметкаосуществляется по следующим правилам.9.6.
Трансляция арифметических выражений177Правила разметки:1. Если вершина — правый лист или дерево состоит из единственнойвершины, то помечаем эту вершину числом 1 (рис. 9.5, б); если вершина —левый лист, то помечаем ее нулем (рис. 9.5, а).Рис. 9.52. Если вершина имеет прямых потомков с метками l1 и l2 , то в качествеметки этой вершины выбираем наибольшее из чисел l1 , l2 либо число l1 + 1,если l1 = l2 (рис. 9.6).Рис. 9.6Далее осуществляется распределение регистров для результатов операций. Распределение регистров основывается на следующих рассуждениях.Пусть корню поддерева назначен регистр с номером n. Индуктивное утверждение заключается в том, что к моменту вычисления поддерева все регистрыс номерами 1, . .
. , n заняты под промежуточные результаты уже вычисленныхподдеревьев, и, возможно, при вычислении данного поддерева используютсярегистры с номерами, бо́льшими n. После завершения вычислений в данномподдереве значение хранится в регистре с номером n. Назначение регистровосуществляется по следующим правилам:1) Корню назначается первый регистр.2) Если метка левого потомка меньше или равна метке правого, то левомупотомку назначается регистр на единицу больший, чем предку, а правому —с тем же номером (сначала вычисляется правое поддерево и его результатпомещается в регистр R — рис.
9.6, а, в), так что регистры занимаются последовательно. Если же метка левого потомка больше метки правого потомка,то наоборот, правому потомку назначается регистр на единицу больший, чем178Глава 9. Генерация кодапредку, а левому — с тем же номером (сначала вычисляется левое поддеревои его результат помещается в регистр R — рис. 9.6, б).После этого формируется код по следующим правилам.1. Если вершина — правый лист с меткой 1, то ей соответствует кодMOVE X, Rгде R — регистр, назначенный этой вершине, а X — адрес переменной,связанной с вершиной (рис. 9.7, б).Рис. 9.72. Если вершина внутренняя и ее левый потомок — лист с меткой 0, то ейсоответствует кодКод правого поддереваOp X, Rгде R — регистр, назначенный этой вершине, X — адрес переменной,связанной с вершиной, а Op — операция, примененная в вершине (рис.
9.7, а).3. Если непосредственные потомки вершины — не листья и метка правойвершины больше или равна метке левой, то вершине соответствует кодКод правого поддереваКод левого поддереваOp R+1, Rгде R — регистр, назначенный внутренней вершине, а операция Op, вообщеговоря, — не коммутативная (рис. 9.8, б);Рис. 9.84. Если непосредственные потомки вершины — не листья и метка правойвершины меньше метки левой вершины, то вершине соответствует кодКод левого поддереваКод правого поддереваOp R, R+1MOVE R+1, R9.6. Трансляция арифметических выражений179Последняя команда генерируется для того, чтобы получить результат в нужном регистре (в случае коммутативной операции ее операнды можно поменятьместами и избежать дополнительной пересылки — рис.
9.8, а).Рассмотрим атрибутную схему, реализующую эти правила генерации кода(для большей наглядности входная грамматика соответствует обычной инфиксной записи, а не Лидер-представлению). В этой схеме генерация кодане происходит непосредственно в процессе обхода дерева, как раньше, а из-занеобходимости переставлять поддеревья код строится в виде текста с помощью операции конкатенации. Практически, конечно, это нецелесообразно:разумнее управлять обходом дерева непосредственно, однако для простотымы будем пользоваться конкатенацией.RULEExpr ::= IntExprSEMANTICSReg<1>=1; Code<0>=Code<1>; Left<1>=true.RULEIntExpr ::= IntExpr Op IntExprSEMANTICSLeft<1>=true; Left<3>=false;Label<0>=(Label<1>==Label<3>)? Label<1>+1: Max(Label<1>,Label<3>);Reg<1>=(Label<1> <= Label<3>)? Reg<0>+1: Reg<0>;Reg<3>=(Label<1> <= Label<3>)? Reg<0>: Reg<0>+1;Code<0>=(Label<1>==0)? Code<3> + Code<2>+ Code<1> + "," + Reg<0>: (Label<1> < Label<3>)? Code<3> + Code<1> + Code<2> +(Reg<0>+1) + "," + Reg<0>: Code<1> + Code<3> + Code<2> +Reg<0> + "," + (Reg<0>+1)+ "MOVE" + (Reg<0>+1) + "," + Reg<0>.RULEIntExpr ::= IdentSEMANTICSLabel<0>=(Left<0>) ? 0 : 1;Code<0>=(!Left<0>)? "MOVE" + Reg<0> + "," + Val<1>180Глава 9.
Генерация кода: Val<1>.RULEIntExpr ::= ’(’ IntExpr ’)’SEMANTICSLabel<0>=Label<2>;Reg<2>=Reg<0>;Code<0>=Code<2>.RULEOp ::= ’+’SEMANTICSCode<0>="ADD".RULEOp ::= ’-’SEMANTICSCode<0>="SUB".RULEOp ::= ’*’SEMANTICSCode<0>="MUL".RULEOp ::= ’/’SEMANTICSCode<0>="DIV".Атрибутированное дерево для выражения A*B+C*(D+E)на рис. 9.9.
При этом будет сгенерирован следующий код:MOVEMULMOVEADDMULADDMOVEприведеноB, R1A, R1E, R2D, R2C, R2R1, R2R2, R1Приведенная атрибутная схема требует двух проходов по дереву выражения. Рассмотрим теперь другую атрибутную схему, в которой генерацияпрограммы для выражений с оптимальным распределением регистров требуетлишь одного обхода [9].Пусть мы произвели разметку дерева разбора так же, как и в предыдущем алгоритме. В качестве регистра результата вычисления поддерева будемназначать регистр с номером, равным метке вершины.9.6. Трансляция арифметических выражений181Рис. 9.9Левому потомку всегда назначается регистр, равный его метке, а правому— его метке, если она не равна метке его левого брата, и метке, увеличеннойна единицу, если метки равны.
Поскольку более сложное поддерево всегдавычисляется раньше более простого, его регистр результата имеет большийномер, чем любой регистр, используемый при вычислении более простогоподдерева, что гарантирует правильность использования регистров.Приведенные соображения реализуются следующей атрибутной схемой:RULEExpr ::= IntExprSEMANTICSCode<0>=Code<1>; Left<1>=true.RULEIntExpr ::= IntExpr Op IntExprSEMANTICSLeft<1>=true; Left<3>=false;Label<0>=(Label<1>==Label<3>)? Label<1>+1: Max(Label<1>,Label<3>);Code<0>=(Label<3> > Label<1>)? (Label<1>==0)? Code<3> + Code<2> + Code<1>182Глава 9.
Генерация кода+ ",R" + Label<3>: Code<3> + Code<1> + Code<2> + "R"+Label<1> + ",R" + Label<3>: (Label<3> < Label<1>)? Code<1> + Code<3> + Code<2> + "R"+Label<1> + "," + Label<3> +"MOVE" + Label<3> + ",R" + Label<1>: // метки равныCode<3> + "MOVE R" + Label<3> +",R" + (Label<3>+1) + Code<1> +Code<2> + "R" + Label<1> + ",R" +(Label<1>+1).RULEIntExpr ::= IdentSEMANTICSLabel<0>=(Left<0>) ? 0 : 1;Code<0>=(Left<0>) ? Val<1>: "MOVE" + Val<1> + "R1".RULEIntExpr ::= ’(’ IntExpr ’)’SEMANTICSLabel<0>=Label<2>;Code<0>=Code<2>.RULEOp ::= ’+’SEMANTICSCode<0>="ADD".RULEOp ::= ’-’SEMANTICSCode<0>="SUB".RULEOp ::= ’*’SEMANTICSCode<0>="MUL".RULEOp ::= ’/’SEMANTICSCode<0>="DIV".9.7.
Трансляция логических выражений183Команды пересылки требуются для согласования номеров регистров, в которых выполняется операция, с регистрами, в которых должен быть выданрезультат. Это имеет смысл, когда эти регистры разные. Получиться этоможет из-за того, что по приведенной схеме результат выполнения операциивсегда находится в регистре с номером метки, а метки левого и правогоподдеревьев могут совпадать.Для выражения A*B+C*(D+E) будет сгенерирован следующий код:MOVE E, R1ADDMULMOVEMOVEMULADDD, R1C, R1R1, R2B, R1A, R1R1, R2В приведенных атрибутных схемах предполагалось, что регистров достаточно для трансляции любого выражения.
Если это не так, то приходитсяусложнять схему трансляции и при необходимости сбрасывать содержимоерегистров в память (или магазин).Реализация этой атрибутной схемы приведена в программном приложениив пакете ToyLang.9.7. Трансляция логических выраженийЛогические выражения, включающие логическое умножение, логическоесложение и отрицание, можно вычислять как непосредственно, используятаблицы истинности, так и с помощью условных выражений, основанных наследующих простых правилах:A AND BA OR Bэквивалентноэквивалентноif A then B else False,if A then True else B.Если в выражение могут входить функции с побочным эффектом, то,вообще говоря, результат вычисления зависит от способа вычисления. В некоторых языках программирования не оговаривается, каким способом должнывычисляться логические выражения (например, в Паскале); в некоторых требуется, чтобы вычисления производились конкретным способом (например,в Модуле-2 требуется, чтобы выражения вычислялись по приведенным формулам); в некоторых языках есть возможность явно задать способ вычисления(Си, Ада).
Вычисление логических выражений непосредственно по таблицамистинности аналогично вычислению арифметических выражений, поэтому мыне будем их рассматривать отдельно. Рассмотрим подробнее способ вычисления с помощью приведенных выше формул (будем называть его вычислением184Глава 9. Генерация кодас условными переходами). Иногда такой способ рассматривают как оптимизацию вычисления логических выражений.Рассмотрим следующую атрибутную грамматику со входным языком логических выражений:RULEExpr ::= BoolExprSEMANTICSFalseLab<1>=False; TrueLab<1>=True;Code<0>=Code<1>.RULEBoolExpr ::= BoolExpr ’AND’ BoolExprSEMANTICSFalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= BoolExpr ’OR’ BoolExprSEMANTICSFalseLab<1>=NodeLab<3>; TrueLab<1>=TrueLab<0>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= FSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + FalseLab<0>.RULEBoolExpr ::= TSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + TrueLab<0>.Здесь предполагается, что все вершины дерева занумерованы и номер вершины дает атрибут NodeLab.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
