В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 32
Текст из файла (страница 32)
Напомним,что в Лидер-представлении каждому описанию соответствует некоторый номер. В процессе работы генератора кодов поддерживается таблица Table,в которой по этому номеру (входу) содержится следующая информация:– для типа: его размер;– для переменной: смещение в области процедуры (или глобальной области);– для поля записи: смещение внутри записи;– для процедуры: размер локальных параметров;– для массива: размер массива, размер элемента, значение левой и правойграниц.Функция IncTab вырабатывает указатель (вход) на новый элемент таблицы, проверяя при этом наличие свободной памяти.Для вычисления адресов определим для каждого объявления два синтезируемых атрибута: DISP будет обозначать смещение внутри области процедуры(или единицы компиляции), а SIZE — размер.
Тогда семантика правила длясписка объявлений принимает видRULEDeclPart ::= ( Decl )SEMANTICSDisp<1>=0;1A: Disp<1>=Disp<1>+Size<1>;Size<0>=Disp<1>.Все объявления, кроме объявлений переменных, имеют нулевой размер.Размер объявления переменной определяется следующим правилом:RULEDecl ::= ’VAR’ TypeDesSEMANTICS9.4.
Трансляция переменных171Tablentry Entry;0: Entry=IncTab;Size<0>=((Table[VAL<2>]+1) / 2)*2;// Выравнивание на границу словаTable[Entry]=Disp<0>+Size<0>.В качестве примера трансляции определения типа рассмотрим обработкуописания записи:RULETypeDes ::= ’REC’ ( TypeDes ) ’END’SEMANTICSint Disp;Tablentry Temp;0: Entry<0>=IncTab;Disp=0;2A: {Temp=IncTab;Table[Temp]=Disp;Disp=Disp+Table[Entry<2>]+1) / 2)*2;// Выравнивание на границу слова}Table[Entry<0>]=Disp.9.4. Трансляция переменныхПеременные отражают всё многообразие механизмов доступа в языке.Переменная имеет синтезированный атрибут ADDRESS — это запись, описывающая адрес в команде МС68020.
Этот атрибут сопоставляется всемнетерминалам, представляющим значения. В системе команд МС68020 многоспособов адресации, и они отражены в структуре значения атрибута ADDRESS,имеющего следующий тип:enum Register{D0,D1,D2,D3,D4,D5,D6,D7,A0,A1,A2,A3,A4,A5,A6,SP,NO};enum AddrMode{D,A,Post,Pre,Indirect,IndPre,IndPost,IndirPC,IndPrePC,IndPostPC,InDisp,Index,IndexPC,Abs,Imm};struct AddrType{Register AddrReg,IndexReg;int IndexDisp,AddrDisp;short Scale;};Значение регистра NO означает, что соответствующий регистр в адресациине используется.172Глава 9.
Генерация кодаДоступ к переменным осуществляется в зависимости от их уровня: глобальные переменные адресуются с помощью абсолютной адресации; переменные в процедуре текущего уровня адресуются через регистр базы А6.Если магазин организован с помощью статической цепочки, то переменные предыдущего статического уровня адресуются через регистр статической цепочки А5; переменные остальных уровней адресуются «пробеганием»по статической цепочке с использованием вспомогательного регистра. Адреспеременной формируется при обработке структуры переменной слева направои передается сначала сверху вниз как наследуемый атрибут нетерминалаVarTail, а затем передается снизу-вверх как глобальный атрибут нетерминала Variable.
Таким образом, правило для обращения к переменной имеетвид (первое вхождение Number в правую часть — это уровень переменной,второе — ее Лидер-номер):RULEVariable ::= VarMode Number Number VarTailSEMANTICSint Temp;struct AddrType AddrTmp1, AddrTmp2;3: if (Val<2>==0) // Глобальная переменная{Address<4>.AddrMode=Abs;Address<4>.AddrDisp=0;}else // Локальная переменная{Address<4>.AddrMode=Index;if (Val<2>==Level<Block>) // Переменная// текущего уровняAddress<4>.AddrReg=A6;else if (Val<2>==Level<Block>-1)// Переменная предыдущего уровняAddress<4>.AddrReg=A5;else{Address<4>.Addreg=GetFree(RegSet<Block>);AddrTmp1.AddrMode=Indirect;AddrTmp1.AddrReg=A5;Emit2(MOVEA,AddrTmp1,Address<4>.AddrReg);AddrTmp1.AddrReg=Address<4>.AddrReg;AddrTmp2.AddrMode=A;AddrTmp2.AddrReg=Address<4>.AddrReg;for (Temp=Level<Block>-Val<2>;Temp>=2;Temp--)Emit2(MOVEA,AddrTmp1,AddrTmp2);}9.4.
Трансляция переменных173if (Val<2>==Level<Block>)Address<4>.AddrDisp=Table[Val<3>];elseAddress<4>.AddrDisp=Table[Val<3>]+Table[LevelTab[Val<2>]];}.Функция GetFree выбирает очередной свободный регистр (либо регистрданных, либо адресный регистр) и отмечает его как использованный в атрибуте RegSet нетерминала Block. Процедура Emit2 генерирует двухадреснуюкоманду. Первый параметр этой процедуры — код команды, второй и третийпараметры имеют тип AddrType и служат операндами команды. Смещениепеременной текущего уровня отсчитывается от базы (А6), а других уровней —от указателя статической цепочки, поэтому оно определяется как алгебраическая сумма размера локальных параметров и величины смещения переменной.Таблица LevelTab — это таблица уровней процедур, содержащая указателина последовательно вложенные процедуры.Если магазин организован с помощью дисплея, то трансляция для доступак переменным может быть осуществлена следующим образом:RULEVariable ::= VarMode Number Number VarTailSEMANTICSint Temp;3: if (Val<2>==0) // Глобальная переменная{Address<4>.AddrMode=Abs;Address<4>.AddrDisp=0;}else // Локальная переменная{Address<4>.AddrMode=Index;if (Val<2>=Level<Block>) // Переменная// текущего уровня{Address<4>.AddrReg=A6;Address<4>.AddrDisp=Table[Val<3>];}else{Address<4>.AddrMode=IndPost;Address<4>.AddrReg=NO;Address<4>.IndexReg=NO;Address<4>.AddrDisp=Display[Val<2>];Address<4>.IndexDisp=Table[Val<3>];}}.Рассмотрим трансляцию доступа к полям записи.
Она описывается следующим правилом (Number — это Лидер-номер описания поля):174Глава 9. Генерация кодаRULEVarTail ::= ’FIL’ Number VarTailSEMANTICSif (Address<0>.AddrMode==Abs){Address<3>.AddrMode=Abs;Address<3>.AddrDisp=Address<0>.AddrDisp+Table[Val<2>];}else{Address<3>=Address<0>;if (Address<0>.AddrMode==Index)Address<3>.AddrDisp=Address<0>.AddrDisp+Table[Val<2>];elseAddress<3>.IndexDisp=Address<0>.IndexDisp+Table[Val<2>];}.9.5.
Трансляция целых выраженийТрансляция выражений различных типов управляется синтаксически благодаря наличию указателя типа перед каждой операцией. Мы рассмотримнекоторые наиболее характерные проблемы генерации кода для выражений.Система команд МС68020 обладает двумя особенностями, сказывающимися на генерации кода для арифметических выражений (то же можно сказать и о генерации кода для выражений типа «множества»):1) один из операндов выражения (правый) должен при выполнении операции находиться на регистре, поэтому если оба операнда не на регистрах,то перед выполнением операции один из них надо загрузить на регистр;2) система команд довольно «симметрична», т.
е. нет специальных требований к регистрам при выполнении операций (таких, например, как парырегистров или требования четности и т. п.).Поэтому выбор команд при генерации арифметических выражений определяется довольно простыми таблицами решений. Например, для целочисленного сложения такая таблица приведена в табл. 9.1.Здесь имеется в виду, что R — операнд на регистре, V — переменная иликонстанта. Такая таблица решений должна также учитывать коммутативностьопераций.RULEIntExpr ::= ’PLUS’ IntExpr IntExprSEMANTICSif (Address<2>.AddrMode!=D) &&9.6.
Трансляция арифметических выражений175(Address<3>.AddrMode!=D){Address<0>.AddrMode=D;Address<0>.Addreg=GetFree(RegSet<Block>);Emit2(MOVE,Address<2>,Address<0>);Emit2(ADD,Address<2>,Address<0>);}elseif (Address<2>.AddrMode==D){Emit2(ADD,Address<3>,Address<2>);Address<0>:=Address<2>);}else {Emit2(ADD,Address<2>,Address<3>);Address<0>:=Address<3>);}.Т а б л и ц а 9.1Правый операнд А2ЛевыйоперандA1RRVADD A1,A2ADD A2, A1V ADD A1, A2 MOVE A1, RADD A2, R9.6.
Трансляция арифметических выраженийОдной из важнейших задач при генерации кода является распределениерегистров. Рассмотрим хорошо известную технику распределения регистровпри трансляции арифметических выражений, называемую алгоритмом Сети–Ульмана.Замечание. Для большей наглядности в данном разделе мы немногоотступаем от семантики арифметических команд MC68020 и предполагаем,что командаOp Arg1, Arg2выполняет действие Arg2:=Arg1 Op Arg2.Пусть система команд машины имеет неограниченное число универсальных регистров, в которых выполняются арифметические команды. Рассмотрим, как можно сгенерировать код, используя для данного арифметическоговыражения минимальное число регистров.Пусть имеется синтаксическое дерево выражения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
