В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 29
Текст из файла (страница 29)
Òîãäà ñåìàíòèêà ïðàâèëà äëÿñïèñêà îáúÿâëåíèé ïðèíèìàåò âèäRULEDeclPart ::= ( Decl )SEMANTICSDisp<1>=0;1A: Disp<1>=Disp<1>+Size<1>;Size<0>=Disp<1>.Âñå îáúÿâëåíèÿ, êðîìå îáúÿâëåíèé ïåðåìåííûõ, èìåþòíóëåâîé ðàçìåð. Ðàçìåð îáúÿâëåíèÿ ïåðåìåííîé îïðåäåëÿåòñÿ ñëåäóþùèì ïðàâèëîì:RULEDecl ::= 'VAR' TypeDesSEMANTICSTablentry Entry;0: Entry=IncTab;Size<0>=((Table[VAL<2>]+1) / 2)*2;// Âûðàâíèâàíèå íà ãðàíèöó ñëîâàTable[Entry]=Disp<0>+Size<0>. êà÷åñòâå ïðèìåðà òðàíñëÿöèè îïðåäåëåíèÿ òèïà ðàññìîòðèì îáðàáîòêó îïèñàíèÿ çàïèñè:9.4. Òðàíñëÿöèÿ ïåðåìåííûõ211RULETypeDes ::= '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;};212Ãëàâà 9. Ãåíåðàöèÿ êîäàÇíà÷åíèå ðåãèñòðà NO îçíà÷àåò, ÷òî ñîîòâåòñòâóþùèéðåãèñòð â àäðåñàöèè íå èñïîëüçóåòñÿ.Äîñòóï ê ïåðåìåííûì îñóùåñòâëÿåòñÿ â çàâèñèìîñòè îòèõ óðîâíÿ: ãëîáàëüíûå ïåðåìåííûå àäðåñóþòñÿ ñ ïîìîùüþàáñîëþòíîé àäðåñàöèè; ïåðåìåííûå â ïðîöåäóðå òåêóùåãîóðîâíÿ àäðåñóþòñÿ ÷åðåç ðåãèñòð áàçû À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;else9.4.
Òðàíñëÿöèÿ ïåðåìåííûõ213{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);}if (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 ýòî òàáëèöà óðîâíåé ïðîöåäóð, ñîäåðæàùàÿ óêàçàòåëè íàïîñëåäîâàòåëüíî âëîæåííûå ïðîöåäóðû.Åñëè ñòåê îðãàíèçîâàí ñ ïîìîùüþ äèñïëåÿ, òî òðàíñëÿöèÿ äëÿ äîñòóïà ê ïåðåìåííûì ìîæåò áûòü îñóùåñòâëåíàñëåäóþùèì îáðàçîì:RULE214Ãëàâà 9. Ãåíåðàöèÿ êîäàVariable ::= 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 ýòî Ëèäåðíîìåð îïèñàíèÿ ïîëÿ):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=9.5. Òðàíñëÿöèÿ öåëûõ âûðàæåíèé215Address<0>.AddrDisp+Table[Val<2>];elseAddress<3>.IndexDisp=Address<0>.IndexDisp+Table[Val<2>];}.9.5.
Òðàíñëÿöèÿ öåëûõ âûðàæåíèéÒðàíñëÿöèÿ âûðàæåíèé ðàçëè÷íûõ òèïîâ óïðàâëÿåòñÿñèíòàêñè÷åñêè áëàãîäàðÿ íàëè÷èþ óêàçàòåëÿ òèïà ïåðåäêàæäîé îïåðàöèåé. Ìû ðàññìîòðèì íåêîòîðûå íàèáîëåå õàðàêòåðíûå ïðîáëåìû ãåíåðàöèè êîäà äëÿ âûðàæåíèé.Ñèñòåìà êîìàíä ÌÑ68020 îáëàäàåò äâóìÿ îñîáåííîñòÿìè, ñêàçûâàþùèìèñÿ íà ãåíåðàöèè êîäà äëÿ àðèôìåòè÷åñêèõ âûðàæåíèé (òî æå ìîæíî ñêàçàòü è î ãåíåðàöèè êîäàäëÿ âûðàæåíèé òèïà ¾ìíîæåñòâà¿):1) îäèí èç îïåðàíäîâ âûðàæåíèÿ (ïðàâûé) äîëæåí ïðèâûïîëíåíèè îïåðàöèè íàõîäèòüñÿ íà ðåãèñòðå, ïîýòîìó åñëè îáà îïåðàíäà íå íà ðåãèñòðàõ, òî ïåðåä âûïîëíåíèåìîïåðàöèè îäèí èç íèõ íàäî çàãðóçèòü íà ðåãèñòð;2) ñèñòåìà êîìàíä äîâîëüíî ¾ñèììåòðè÷íà¿, òî åñòü íåòñïåöèàëüíûõ òðåáîâàíèé ê ðåãèñòðàì ïðè âûïîëíåíèè îïåðàöèé (òàêèõ, íàïðèìåð, êàê ïàðû ðåãèñòðîâ èëè òðåáîâàíèÿ ÷¼òíîñòè è ò.ä.).Ïîýòîìó âûáîð êîìàíä ïðè ãåíåðàöèè àðèôìåòè÷åñêèõâûðàæåíèé îïðåäåëÿåòñÿ äîâîëüíî ïðîñòûìè òàáëèöàìèðåøåíèé.
Íàïðèìåð, äëÿ öåëî÷èñëåííîãî ñëîæåíèÿ òàêàÿòàáëèöà ïðèâåäåíà íà ðèñ. 9.4.Çäåñü èìååòñÿ â âèäó, ÷òî R îïåðàíä íà ðåãèñòðå, V ïåðåìåííàÿ èëè êîíñòàíòà. Òàêàÿ òàáëèöà ðåøåíèé äîëæíàòàêæå ó÷èòûâàòü êîììóòàòèâíîñòü îïåðàöèé.RULEIntExpr ::= 'PLUS' IntExpr IntExprSEMANTICSif (Address<2>.AddrMode!=D) &&(Address<3>.AddrMode!=D)216Ãëàâà 9. Ãåíåðàöèÿ êîäàËåâûéîïåðàíäA1RÏðàâûé îïåðàíä À2RVADD A1,A2 ADD A2, A1VADD A1, A2MOVE A1, RADD A2, RÐèñ. 9.4.{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.6.
Òðàíñëÿöèÿâûðàæåíèéàðèôìåòè÷åñêèõÎäíîé èç âàæíåéøèõ çàäà÷ ïðè ãåíåðàöèè êîäà ÿâëÿåòñÿ ðàñïðåäåëåíèå ðåãèñòðîâ. Ðàññìîòðèì õîðîøî èçâåñòíóþ òåõíèêó ðàñïðåäåëåíèÿ ðåãèñòðîâ ïðè òðàíñëÿöèè àðèôìåòè÷åñêèõ âûðàæåíèé, íàçûâàåìóþ àëãîðèòìîìÑåòè-Óëüìàíà. (Çàìå÷àíèå: â öåëÿõ áîëüøåé íàãëÿäíîñòè,â äàííîì ïàðàãðàôå ìû íåìíîãî îòñòóïàåì îò ñåìàíòèêèàðèôìåòè÷åñêèõ êîìàíä MC68020 è ïðåäïîëàãàåì, ÷òî êîìàíäàOp Arg1, Arg29.6.
Òðàíñëÿöèÿ àðèôìåòè÷åñêèõ âûðàæåíèé217âûïîëíÿåò äåéñòâèå Arg2:=Arg1 Op Arg2.)Ïóñòü ñèñòåìà êîìàíä ìàøèíû èìååò íåîãðàíè÷åííîå÷èñëî óíèâåðñàëüíûõ ðåãèñòðîâ, â êîòîðûõ âûïîëíÿþòñÿàðèôìåòè÷åñêèå êîìàíäû. Ðàññìîòðèì, êàê ìîæíî ñãåíåðèðîâàòü êîä, èñïîëüçóÿ äëÿ äàííîãî àðèôìåòè÷åñêîãî âûðàæåíèÿ ìèíèìàëüíîå ÷èñëî ðåãèñòðîâ.RS5RS5RS/55QRS/5Ðèñ. 9.5.Ïóñòü èìååòñÿ ñèíòàêñè÷åñêîå äåðåâî âûðàæåíèÿ.
Ïðåäïîëîæèì ñíà÷àëà, ÷òî ðàñïðåäåëåíèå ðåãèñòðîâ îñóùåñòâëÿåòñÿ ïî ïðîñòåéøåé ñõåìå ñâåðõó-âíèç ñëåâà-íàïðàâî,êàê èçîáðàæåíî íà ðèñ. 9.5. Òîãäà ê ìîìåíòó ãåíåðàöèè êîäà äëÿ ïîääåðåâà 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 ðåãèñòðîâ áóäåò èñïîëüçîâàíî äëÿ âû÷èñëå-218Ãëàâà 9.
Ãåíåðàöèÿ êîäàíèÿ R. Âñåãî áóäåò èñïîëüçîâàíî n + nr + 1 ðåãèñòðîâ.Âèäíî, ÷òî äëÿ äåðåâüåâ, ñîâïàäàþùèõ ñ òî÷íîñòüþ äîïîðÿäêà ïîòîìêîâ êàæäîé âåðøèíû, ìèíèìàëüíîå ÷èñëîðåãèñòðîâ ïðè ðàñïðåäåëåíèè èõ ñëåâà-íàïðàâî äîñòèãàåòñÿíà äåðåâå, ó êîòîðîãî â êàæäîé âåðøèíå ñëåâà ðàñïîëîæåíî áîëåå ¾ñëîæíîå¿ ïîääåðåâî, òðåáóþùåå áîëüøåãî ÷èñëàðåãèñòðîâ. Òàêèì îáðàçîì, åñëè äåðåâî òàêîâî, ÷òî â êàæäîé âíóòðåííåé âåðøèíå ïðàâîå ïîääåðåâî òðåáóåò ìåíüøåãî ÷èñëà ðåãèñòðîâ, ÷åì ëåâîå, òî, îáõîäÿ äåðåâî ñëåâàíàïðàâî, ìîæíî îïòèìàëüíî ðàñïðåäåëèòü ðåãèñòðû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
