В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 33
Текст из файла (страница 33)
Âî âðåìÿ êîìïèëÿöèè âî-246Ãëàâà 9. Ãåíåðàöèÿ êîäàîáùå ãîâîðÿ íå èçâåñòíî, óêàçûâàåò ëè pb íà ÷àñòü B â C .Íàïðèìåð, èç-çà òîãî, ÷òî pb ìîæåò áûòü ïðèñâîåí ïðîñòîóêàçàòåëü íà îáúåêò B . Òàê ÷òî âåëè÷èíà delta(B), óïîìÿíóòàÿ âûøå, ìîæåò áûòü ðàçëè÷íîé äëÿ ðàçíûõ îáúåêòîââ çàâèñèìîñòè îò ñòðóêòóðû êëàññîâ, ïîðîæäàåìûõ èç B èäîëæíà ãäå-òî õðàíèòñÿ âî âðåìÿ âûïîëíåíèÿ.Ñëåäîâàòåëüíî, delta(B ) äîëæíî ãäå-òî õðàíèòüñÿ èáûòü äîñòóïíî âî âðåìÿ èñïîëíåíèÿ.
Ïîñêîëüêó ýòî ñìåùåíèå íóæíî òîëüêî äëÿ âèðòóàëüíîãî âûçîâà ôóíêöèè,ëîãè÷íî õðàíèòü åãî â òàáëèöå âèðòóàëüíûõ ôóíêöèé.Óêàçàòåëü this, ïåðåäàâàåìûé âèðòóàëüíîé ôóíêöèè,ìîæåò áûòü âû÷èñëåí ïóò¼ì âû÷èòàíèÿ ñìåùåíèÿ îáúåêòà, äëÿ êîòîðîãî áûëà îïðåäåëåíà âèðòóàëüíàÿ ôóíêöèÿ,èç ñìåùåíèÿ îáúåêòà, äëÿ êîòîðîãî îíà âûçâàíà, à çàòåìâû÷èòàíèÿ ýòîé ðàçíîñòè èç óêàçàòåëÿ, èñïîëüçóåìîãî ïðèâûçîâå.
Çäåñü çíà÷åíèå delta(B ) áóäåò íåîáõîäèìî äëÿ ïîèñêà íà÷àëà îáúåêòà (â íàøåì ñëó÷àå C ), ñîäåðæàùåãî B ,ïî óêàçàòåëþ íà B . Ñãåíåðèðîâàííûé êîä âû÷òåò çíà÷åíèådelta(B ) èç çíà÷åíèÿ óêàçàòåëÿ, òàê ÷òî õðàíèòñÿ ñìåùåíèåñî çíàêîì ìèíóñ, -delta(B ). Îáúåêò êëàññà C áóäåò âûãëÿäåòü ñëåäóþùèì îáðàçîì:vtbl äëÿ A â Cvptrdelta(B )?- ÷àñòü Apbvptr÷àñòü B÷àñòü C- &C :: f 0vtbl äëÿ B â C?&C :: f -delta(B )&B :: g 0Ðèñ. 9.21.Òàáëèöà âèðòóàëüíûõ ôóíêöèé vtbl äëÿ B â C îòëè÷àåòñÿ îò vtbl äëÿ îòäåëüíî ðàçìåù¼ííîãî B . Êàæäàÿ êîìáèíàöèÿ áàçîâîãî è ïðîèçâîäíîãî êëàññîâ èìååò ñâîþ òàáëèöóvtbl.
 îáùåì ñëó÷àå îáúåêò ïðîèçâîäíîãî êëàññà òðåáóåòòàáëèöó vtbl äëÿ êàæäîãî áàçîâîãî êëàññà ïëþñ òàáëèöóäëÿ ïðîèçâîäíîãî êëàññà, íå ñ÷èòàÿ òîãî, ÷òî ïðîèçâîäíûé9.9. Òðàíñëÿöèÿ ñâîéñòâ ÿçûêîâ ïðîãðàììèðîâàíèÿ247êëàññ ìîæåò ðàçäåëÿòü òàáëèöó vtbl ñî ñâîèì ïåðâûì áàçîâûì êëàññîì. Òàêèì îáðàçîì, äëÿ îáúåêòà òèïà C â ýòîìïðèìåðå òðåáóåòñÿ äâå òàáëèöû vtbl (òàáëèöà äëÿ A â Cîáúåäèíåíà ñ òàáëèöåé äëÿ C îáúåêòà è åù¼ îäíà òàáëèöàíóæíà äëÿ B îáúåêòà â C ).9.9.5. Âèðòóàëüíûå áàçîâûå êëàññû ñ âèðòóàëüíûìè ôóíêöèÿìèÏðè íàëè÷èè âèðòóàëüíûõ áàçîâûõ êëàññîâ ïîñòðîåíèåòàáëèö äëÿ âûçîâîâ âèðòóàëüíûõ ôóíêöèé ñòàíîâèòñÿ áîëåå ñëîæíûì.
Ðàññìîòðèì ñëåäóþùèå îáúÿâëåíèÿ:class W {public:virtual void f ();virtual void g ();virtual void h();virtual void k ();};class M W : public virtual W {public:void g ();};class BW : public virtual W {public:void f ();};class BM W : public BW , public M W , public virtual W {public:void h();};Îòíîøåíèå íàñëåäîâàíèÿ äëÿ ýòîãî ïðèìåðà ìîæåòáûòü èçîáðàæåíî â âèäå àöèêëè÷åñêîãî ãðàôà òàêèì îáðàçîì:248Ãëàâà 9.
Ãåíåðàöèÿ êîäà- W {f, g, h, k} ¾6BW {f }M W {g}66BM W {h}Ðèñ. 9.22.Ôóíêöèè-÷ëåíû êëàññà BM W ìîãóò èñïîëüçîâàòüñÿ,íàïðèìåð, òàê:void g(BM W ∗ pbmw){pbmw → f (); // âûçûâàåò BW :: f ()pbmw → g(); // âûçûâàåò M W :: g()pbmw → h(); // âûçûâàåò BM W :: h()}Ðàññìîòðèì òåïåðü ñëåäóþùèé âûçîâ âèðòóàëüíîéôóíêöèè f ():void h(BM W ∗ pbmw){M W ∗ pmw = pbmw;pmw → f (); // âûçûâàåò BW :: f (), ïîòîìó, ÷òî// pbmw óêàçûâàåò íà BM W , äëÿ êîòîðîãî f áåð¼òñÿèç BW !}Âèðòóàëüíûé âûçîâ ôóíêöèè ïî îäíîìó ïóòè â ñòðóêòóðå íàñëåäîâàíèÿ ìîæåò ïðèâåñòè ê îáðàùåíèþ ê ôóíêöèè,ïåðåîïðåäåë¼ííîé íà äðóãîì ïóòè.Ñòðóêòóðà îáúåêòîâ êëàññà BM W è åãî òàáëèö âèðòóàëüíûõ ôóíêöèé vtbl ìîãóò âûãëÿäåòü ñëåäóþùèì îáðàçîì:9.9.
Òðàíñëÿöèÿ ñâîéñòâ ÿçûêîâ ïðîãðàììèðîâàíèÿ-vptr÷àñòüvptr÷àñòü÷àñòüvptr÷àñòüBWMWBM WW249vtbl äëÿ BW â BM W&BW ::f0&M W ::g0 + delta(M W )&BM W ::h 0 + delta(BM W )&W ::k0 + delta(W )vtbl äëÿ M W â BM W&BW ::f0 − delta(M W )&M W ::g0&BM W ::h delta(BM W )−delta(M W )&W ::kdelta(W ) − delta(M W )vtbläëÿW â BM W&BW ::f0 − delta(W )&M W ::gdelta(M W ) − delta(W )&BM W ::h delta(BM W ) − delta(W )&W ::k0-Ðèñ. 9.23.Âèðòóàëüíîé ôóíêöèè äîëæåí áûòü ïåðåäàí óêàçàòåëüthis íà îáúåêò êëàññà, â êîòîðîì ýòà ôóíêöèÿ îïèñàíà. Ïîýòîìó ñëåäóåò õðàíèòü ñìåùåíèå äëÿ êàæäîãî óêàçàòåëÿôóíêöèè èç vtbl. Êîãäà îáúåêò ðàçìåù¼í â ïàìÿòè òàê, êàêýòî èçîáðàæåíî âûøå, ñìåùåíèå, õðàíèìîå ñ óêàçàòåëåìâèðòóàëüíîé ôóíêöèè, èñ÷èñëÿåòñÿ âû÷èòàíèåì ñìåùåíèÿêëàññà, äëÿ êîòîðîãî ýòà òàáëèöà vtbl ñîçäàíà, èç ñìåùåíèÿêëàññà, ïîñòàâëÿþùåãî ýòó ôóíêöèþ. Ðàññìîòðèì ïðèìåð:void callvirt(w∗ pw){ pw → f ();}main (){ callvirt(new BM W );} ôóíêöèè main âûçîâ callvirt ñ óêàçàòåëåì íà BM Wòðåáóåò ïðèâåäåíèÿ ê óêàçàòåëþ íà W , ïîñêîëüêó ôóíêöèÿ callvirt îæèäàåò ïàðàìåòð òèïà W ∗ .
Òàê êàê ôóíêöèÿcallvirt âûçûâàåò f () (÷åðåç óêàçàòåëü íà BM W , ïðåîáðà-250Ãëàâà 9. Ãåíåðàöèÿ êîäàçîâàííûé ê óêàçàòåëþ íà W ), áóäåò èñïîëüçîâàíà òàáëèöàvtbl êëàññà W (â BM W ), ãäå óêàçàíî, ÷òî ýêçåìïëÿðîì âèðòóàëüíîé ôóíêöèè f (), êîòîðóþ íóæíî âûçâàòü, ÿâëÿåòñÿBW :: f (). ×òîáû ïåðåäàòü ôóíêöèè BW :: f () óêàçàòåëüthis íà BW , óêàçàòåëü pw äîëæåí áûòü âíîâü ïðèâåä¼íê óêàçàòåëþ íà BM W (âû÷èòàíèåì ñìåùåíèÿ äëÿ W ), àçàòåì ê óêàçàòåëþ íà BW (äîáàâëåíèåì ñìåùåíèÿ BW âîáúåêòå BM W ). Çíà÷åíèå ñìåùåíèÿ BW â îáúåêòå BM Wìèíóñ ñìåùåíèå W â îáúåêòå BM W è åñòü ñìåùåíèå, õðàíèìîå â ñòðîêå òàáëèöû vtbl äëÿ w â BM W äëÿ ôóíêöèèBW :: f ().9.10. Ãåíåðàöèÿ îïòèìàëüíîãî êîäà ìåòîäàìè ñèíòàêñè÷åñêîãîàíàëèçà9.10.1.
Ñîïîñòàâëåíèå îáðàçöîâÒåõíèêà ãåíåðàöèè êîäà, ðàññìîòðåííàÿ âûøå, îñíîâûâàëàñü íà îäíîçíà÷íîì ñîîòâåòñòâèè ñòðóêòóðû ïðîìåæóòî÷íîãî ïðåäñòàâëåíèÿ è îïèñûâàþùåé ýòî ïðåäñòàâëåíèåãðàììàòèêè. Íåäîñòàòêîì òàêîãî ¾æ¼ñòêîãî¿ ïîäõîäà ÿâëÿåòñÿ òî, ÷òî êàê ïðàâèëî îäíó è òó æå ïðîãðàììó íà ïðîìåæóòî÷íîì ÿçûêå ìîæíî ðåàëèçîâàòü ìíîãèìè ðàçëè÷íûìèñïîñîáàìè â ñèñòåìå êîìàíä ìàøèíû. Ýòè ðàçíûå ðåàëèçàöèè ìîãóò èìåòü ðàçëè÷íóþ äëèíó, âðåìÿ âûïîëíåíèÿ èäðóãèå õàðàêòåðèñòèêè.
Äëÿ ãåíåðàöèè áîëåå êà÷åñòâåííîãî êîäà ìîæåò áûòü ïðèìåí¼í ïîäõîä, èçëîæåííûé â íàñòîÿùåé ãëàâå.Ýòîò ïîäõîä îñíîâàí íà ïîíÿòèè ¾ñîïîñòàâëåíèÿ îáðàçöîâ¿: êîìàíäàì ìàøèíû ñîïîñòàâëÿþòñÿ íåêîòîðûå ¾îáðàçöû¿, âõîæäåíèÿ êîòîðûõ èùóòñÿ â ïðîìåæóòî÷íîìïðåäñòàâëåíèè ïðîãðàììû, è äåëàåòñÿ ïîïûòêà ¾ïîêðûòü¿ïðîìåæóòî÷íóþ ïðîãðàììó òàêèìè îáðàçöàìè. Åñëè ýòîóäà¼òñÿ, òî ïî îáðàçöàì âîññòàíàâëèâàåòñÿ ïðîãðàììà óæåâ êîäàõ.
Êàæäîå òàêîå ïîêðûòèå ñîîòâåòñòâóåò íåêîòî-9.10. Ãåíåðàöèÿ îïòèìàëüíîãî êîäà251ðîé ïðîãðàììå, ðåàëèçóþùåé îäíî è òî æå ïðîìåæóòî÷íîåïðåäñòàâëåíèå.FRQVWDFRQVW[#FRQVWFRQVWE#FRQVW\FRQVWLFRQVW]Ðèñ. 9.24.Íà ðèñ. 9.24 ïîêàçàíî ïðîìåæóòî÷íîå äåðåâî äëÿ îïåðàòîðà a = b[i] + 5, ãäå a, b, i ëîêàëüíûå ïåðåìåííûå,õðàíèìûå ñî ñìåùåíèÿìè x, y , z ñîîòâåòñòâåííî â îáëàñòÿõäàííûõ ñ îäíîèì¼ííûìè àäðåñàìè.Ýëåìåíò ìàññèâà b çàíèìàåò ïàìÿòü â îäíó ìàøèííóþåäèíèöó. 0-ìåñòíàÿ îïåðàöèÿ const âîçâðàùàåò çíà÷åíèåàòðèáóòà ñîîòâåòñòâóþùåé âåðøèíû ïðîìåæóòî÷íîãî äåðåâà, óêàçàííîãî íà ðèñóíêå â ñêîáêàõ ïîñëå îïåðàòîðà.Îäíîìåñòíàÿ îïåðàöèÿ @ îçíà÷àåò êîñâåííóþ àäðåñàöèþ èâîçâðàùàåò ñîäåðæèìîå ðåãèñòðà èëè ÿ÷åéêè ïàìÿòè, èìåþùåé àäðåñ, çàäàâàåìûé àðãóìåíòîì îïåðàöèè.Íà ðèñ.
9.25 ïîêàçàí ïðèìåð ñîïîñòàâëåíèÿ îáðàçöîâìàøèííûì êîìàíäàì. Ïðèâåäåíû äâà âàðèàíòà çàäàíèÿîáðàçöà: â âèäå äåðåâà è â âèäå ïðàâèëà êîíòåêñòíî-252Ãëàâà 9. Ãåíåðàöèÿ êîäàH[jZa_p5HJIjZ\beh]jZffZlbdb5HJoFRQVWFRQVWDhfZg^Zklhbfhklv029(FRQVW5 6WDW5HJM 6WDWo 5HJFRQVW5HJ029(5MFRQVW5LFRQVW5HJL#5HJM5HJL5HJ5HJL5HJo#5HJFRQVW029(FRQVW5L5M5HJo5HJFRQVW$''FRQVW55HJo5HJ5HJ$''5M5LFRQVW5HJFRQVW5HJL5HJM 5HJL5HJL#5HJo5HJ#5HJFRQVW $''FRQVW5M5L 5HJM FRQVW#5HJL5HJo#5HJ029(5M5L5HJMÐèñ.
9.25.ñâîáîäíîé ãðàììàòèêè. Äëÿ êàæäîãî îáðàçöà óêàçàíà ìàøèííàÿ êîìàíäà, ðåàëèçóþùàÿ ýòîò îáðàçåö, è ñòîèìîñòüýòîé êîìàíäû. êàæäîì äåðåâå-îáðàçöå êîðåíü èëè ëèñò ìîæåò áûòüïîìå÷åí òåðìèíàëüíûì è/èëè íåòåðìèíàëüíûì ñèìâîëîì.Âíóòðåííèå âåðøèíû ïîìå÷åíû òåðìèíàëüíûìè ñèìâîëà-9.10. Ãåíåðàöèÿ îïòèìàëüíîãî êîäà253ìè çíàêàìè îïåðàöèé. Ïðè íàëîæåíèè îáðàçöà íà äåðåâî âûðàæåíèÿ, âî-ïåðâûõ, òåðìèíàëüíûé ñèìâîë îáðàçöàäîëæåí ñîîòâåòñòâîâàòü òåðìèíàëüíîìó ñèìâîëó äåðåâà, è,âî-âòîðûõ, îáðàçöû äîëæíû ¾ñêëåèâàòüñÿ¿ ïî òèïó íåòåðìèíàëüíîãî ñèìâîëà, òî åñòü òèï êîðíÿ îáðàçöà äîëæåí ñîâïàäàòü ñ òèïîì âåðøèíû, â êîòîðóþ îáðàçåö ïîäñòàâëÿåòñÿêîðíåì. Äîïóñêàåòñÿ èñïîëüçîâàíèå ¾öåïíûõ¿ îáðàçöîâ, òîåñòü îáðàçöîâ, êîðíþ êîòîðûõ íå ñîîòâåòñòâóåò òåðìèíàëüíûé ñèìâîë, è èìåþùèõ åäèíñòâåííûé ýëåìåíò â ïðàâîé÷àñòè.
Öåïíûå ïðàâèëà ñëóæàò äëÿ ïðèâåäåíèÿ âåðøèí êîäíîìó òèïó. Íàïðèìåð, â ðàññìàòðèâàåìîé ñèñòåìå êîìàíäîäíè è òå æå ðåãèñòðû èñïîëüçóþòñÿ êàê äëÿ öåëåé àäðåñàöèè, òàê è äëÿ âû÷èñëåíèé. Åñëè áû â ñèñòåìå êîìàíääëÿ ýòèõ öåëåé èñïîëüçîâàëèñü ðàçíûå ãðóïïû ðåãèñòðîâ,òî â ãðàììàòèêå êîìàíä ìîãëè áû èñïîëüçîâàòüñÿ ðàçíûåíåòåðìèíàëû, à äëÿ ïåðåñûëêè èç àäðåñíîãî ðåãèñòðà â ðåãèñòð äàííûõ ìîãëà áû èñïîëüçîâàòüñÿ ñîîòâåòñòâóþùàÿêîìàíäà è îáðàçåö.Íåòåðìèíàëû Reg íà îáðàçöàõ ìîãóò áûòü ïîìå÷åíû èíäåêñîì (i èëè j ), ÷òî (íåôîðìàëüíî) ñîîòâåòñòâóåò íîìåðóðåãèñòðà è ñëóæèò ëèøü äëÿ ïîÿñíåíèÿ ñìûñëà èñïîëüçîâàíèÿ ðåãèñòðîâ. Îòìåòèì, ÷òî ïðè ãåíåðàöèè êîäà ðàññìàòðèâàåìûì ìåòîäîì íå îñóùåñòâëÿåòñÿ ðàñïðåäåëåíèåðåãèñòðîâ.
Ýòî ÿâëÿåòñÿ îòäåëüíîé çàäà÷åé.Ñòîèìîñòü ìîæåò îïðåäåëÿòüñÿ ðàçëè÷íûìè ñïîñîáàìè, íàïðèìåð ÷èñëîì îáðàùåíèé ê ïàìÿòè ïðè âûáîðêåè èñïîëíåíèè êîìàíäû. Çäåñü ìû íå ðàññìàòðèâàåì ýòîãî âîïðîñà. Íà ðèñ. 9.26 ïðèâåä¼í ïðèìåð ïîêðûòèÿ ïðîìåæóòî÷íîãî äåðåâà ðèñ. 9.24 îáðàçöàìè ðèñ. 9.25.  ðàìêè çàêëþ÷åíû ôðàãìåíòû äåðåâà, ñîïîñòàâëåííûå îáðàçöó ïðàâèëà, íîìåð êîòîðîãî óêàçûâàåòñÿ â ëåâîì âåðõíåìóãëó ðàìêè.  êâàäðàòíûõ ñêîáêàõ óêàçàíû ðåçóëüòèðóþùèå âåðøèíû.Ïðèâåä¼ííîå ïîêðûòèå äà¼ò òàêóþ ïîñëåäîâàòåëüíîñòüêîìàíä:14MOVE #b,RbADD #y,Rb254Ãëàâà 9. Ãåíåðàöèÿ êîäà>6WDW@>5HJ5D@FRQVW[FRQVWD>5HJ5E@>5HJ5E@#>5HJ5E@#>5HJ5E@>5HJ5E@FRQVW\>5HJ5L@FRQVWEFRQVWLÐèñ. 9.26.1674FRQVWMOVEADDMOVEADD#i,Ri#z(Ri),Rb(Rb),Rb#5,RbFRQVW]9.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
