В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 32
Текст из файла (страница 32)
Âûäåëåíèå îáùèõ ïîäâûðàæåíèé237åñëè ïîääåðåâüÿ äëÿ íèõ ñîâïàäàþò, òî åñòü èìåþò îäèíàêîâóþ ñòðóêòóðó è, ñîîòâåòñòâåííî, îäèíàêîâûå îïåðàöèè âîâíóòðåííèõ âåðøèíàõ è îäèíàêîâûå îïåðàíäû â ëèñòüÿõ.Âûäåëåíèå îáùèõ ïîäâûðàæåíèé ïîçâîëÿåò ãåíåðèðîâàòüäëÿ íèõ êîä îäèí ðàç, õîòÿ ìîæåò ïðèâåñòè è ê íåêîòîðûìòðóäíîñòÿì, î ÷¼ì âêðàòöå áóäåò ñêàçàíî íèæå.Âûäåëåíèå îáùèõ ïîäâûðàæåíèé ïðîâîäèòñÿ íà ëèíåéíîì ó÷àñòêå è îñíîâûâàåòñÿ íà äâóõ ïîëîæåíèÿõ.1. Ïîñêîëüêó íà ëèíåéíîì ó÷àñòêå ïåðåìåííîé ìîæåòáûòü íåñêîëüêî ïðèñâàèâàíèé, òî ïðè âûäåëåíèè îáùèõïîäâûðàæåíèé íåîáõîäèìî ðàçëè÷àòü âõîæäåíèÿ ïåðåìåííûõ äî è ïîñëå ïðèñâàèâàíèÿ.
Äëÿ ýòîãî êàæäàÿ ïåðåìåííàÿ ñíàáæàåòñÿ ñ÷¼ò÷èêîì. Âíà÷àëå ñ÷¼ò÷èêè âñåõ ïåðåìåííûõ óñòàíàâëèâàþòñÿ ðàâíûìè 0. Ïðè êàæäîì ïðèñâàèâàíèè ïåðåìåííîé å¼ ñ÷¼ò÷èê óâåëè÷èâàåòñÿ íà 1.2. Âûäåëåíèå îáùèõ ïîäâûðàæåíèé îñóùåñòâëÿåòñÿ ïðèîáõîäå äåðåâà âûðàæåíèÿ ñíèçó ââåðõ ñëåâà íàïðàâî. Ïðèäîñòèæåíèè î÷åðåäíîé âåðøèíû (ïóñòü îïåðàöèÿ, ïðèìåí¼ííàÿ â ýòîé âåðøèíå, åñòü áèíàðíàÿ op; â ñëó÷àå óíàðíîéîïåðàöèè ðàññóæäåíèÿ òå æå) ïðîñìàòðèâàåì îáùèå ïîäâûðàæåíèÿ, ñâÿçàííûå ñ op.
Åñëè èìååòñÿ âûðàæåíèå, ñâÿçàííîå ñ op è òàêîå, ÷òî åãî ëåâûé îïåðàíä åñòü îáùåå ïîäâûðàæåíèå ñ ëåâûì îïåðàíäîì íîâîãî âûðàæåíèÿ, à ïðàâûé îïåðàíä - îáùåå ïîäâûðàæåíèå ñ ïðàâûì îïåðàíäîìíîâîãî âûðàæåíèÿ, òî îáúÿâëÿåì íîâîå âûðàæåíèå îáùèìñ íàéäåííûì è â íîâîì âûðàæåíèè çàïîìèíàåì óêàçàòåëüíà íàéäåííîå îáùåå âûðàæåíèå. Áàçèñîì ïîñòðîåíèÿ ñëóæèò ïåðåìåííàÿ: åñëè îïåðàíäàìè îáîèõ âûðàæåíèé ÿâëÿþòñÿ îäèíàêîâûå ïåðåìåííûå ñ îäèíàêîâûìè ñ÷¼ò÷èêàìè,òî îíè ÿâëÿþòñÿ îáùèìè ïîäâûðàæåíèÿìè.
Åñëè âûðàæåíèå íå âûäåëåíî êàê îáùåå, îíî çàíîñèòñÿ â ñïèñîê îïåðàöèé, ñâÿçàííûõ ñ op.Ðàññìîòðèì òåïåðü ðåàëèçàöèþ àëãîðèòìà âûäåëåíèÿîáùèõ ïîäâûðàæåíèé. Ïîääåðæèâàþòñÿ ñëåäóþùèå ãëîáàëüíûå ïåðåìåííûå:Table òàáëèöà ïåðåìåííûõ; äëÿ êàæäîé ïåðåìåííîéõðàíèòñÿ å¼ ñ÷¼ò÷èê (Count) è óêàçàòåëü íà âåðøèíó äåðåâàâûðàæåíèé, â êîòîðîé ïåðåìåííàÿ âñòðåòèëàñü â ïîñëåäíèé238Ãëàâà 9. Ãåíåðàöèÿ êîäàðàç â ïðàâîé ÷àñòè (Last);OpTable òàáëèöà ñïèñêîâ (òèïà LisType) îáùèõ ïîäâûðàæåíèé, ñâÿçàííûõ ñ êàæäîé îïåðàöèåé.
Êàæäûé ýëåìåíò ñïèñêà õðàíèò óêàçàòåëü íà âåðøèíó äåðåâà (ïîëåAddr) è ïðîäîëæåíèå ñïèñêà (ïîëå List).Ñ êàæäîé âåðøèíîé äåðåâà âûðàæåíèÿ ñâÿçàíà çàïèñüòèïà NodeType, ñî ñëåäóþùèìè ïîëÿìè:Left ëåâûé ïîòîìîê âåðøèíû,Right ïðàâûé ïîòîìîê âåðøèíû,Comm óêàçàòåëü íà ïðåäûäóùåå îáùåå ïîäâûðàæåíèå,Flag ïðèçíàê, ÿâëÿåòñÿ ëè ïîääåðåâî îáùèì ïîäâûðàæåíèåì,Varbl ïðèçíàê, ÿâëÿåòñÿ ëè âåðøèíà ïåðåìåííîé,VarCount ñ÷¼ò÷èê ïåðåìåííîé.Âûäåëåíèå îáùèõ ïîäâûðàæåíèé è ïîñòðîåíèå äåðåâà îñóùåñòâëÿþòñÿ ïðèâåä¼ííûìè íèæå ïðàâèëàìè.
ÀòðèáóòEntry íåòåðìèíàëà Variable äà¼ò óêàçàòåëü íà ïåðåìåííóþ â òàáëèöå Table. Àòðèáóò Val ñèìâîëà Op äà¼ò êîäîïåðàöèè. Àòðèáóò Node ñèìâîëîâ IntExpr è Assignmentäà¼ò óêàçàòåëü íà çàïèñü òèïà NodeType ñîîòâåòñòâóþùåãîíåòåðìèíàëà.RULEAssignment ::= Variable IntExprSEMANTICSTable[Entry<1>].Count=Table[Entry<1>].Count+1.// Óâåëè÷èòü ñ÷¼ò÷èê ïðèñâàèâàíèé ïåðåìåííîéRULEIntExpr ::= VariableSEMANTICSif ((Table[Entry<1>].Last!=NULL)// Ïåðåìåííàÿ óæå áûëà èñïîëüçîâàíà&& (Table[Entry<1>].Last->VarCount== Table[Entry<1>].Count ))// Ñ òåõ ïîð ïåðåìåííîé íå áûëî ïðèñâàèâàíèÿ{Node<0>->Flag=true;// Ïåðåìåííàÿ - îáùåå ïîäâûðàæåíèå9.8.
Âûäåëåíèå îáùèõ ïîäâûðàæåíèé239Node<0>->Comm= Table[Entry<1>].Last;// Óêàçàòåëü íà îáùåå ïîäâûðàæåíèå}else Node<0>->Flag=false;Table[Entry<1>].Last=Node<0>;// Óêàçàòåëü íà ïîñëåäíåå èñïîëüçîâàíèå ïåðåìåííîéNode<0>->VarCount= Table[Entry<1>].Count;// Íîìåð èñïîëüçîâàíèÿ ïåðåìåííîéNode<0>->Varbl=true.// Âûðàæåíèå - ïåðåìåííàÿRULEIntExpr ::= Op IntExpr IntExprSEMANTICSLisType * L; //Òèï ñïèñêîâ îïåðàöèèif ((Node<2>->Flag) && (Node<3>->Flag))// È ñïðàâà, è ñëåâà - îáùèå ïîäâûðàæåíèÿ{L=OpTable[Val<1>];// Íà÷àëî ñïèñêà îáùèõ ïîäâûðàæåíèé äëÿ îïåðàöèèwhile (L!=NULL)if ((Node<2>==L->Left)&& (Node<3>==L->Right))// Ëåâîå è ïðàâîå ïîääåðåâüÿ ñîâïàäàþòbreak;else L=L->List;// Ñëåäóþùèé ýëåìåíò ñïèñêà}else L=NULL; //Íå îáùåå ïîäâûðàæåíèåNode<0>->Varbl=false; // Íå ïåðåìåííàÿNode<0>->Comm=L;// Óêàçàòåëü íà ïðåäûäóùåå îáùåå ïîäâûðàæåíèå// èëè NULLif (L!=NULL){Node<0>->Flag=true; //Îáùåå ïîäâûðàæåíèåNode<0>->Left=Node<2>;240Ãëàâà 9.
Ãåíåðàöèÿ êîäà// Óêàçàòåëü íà ëåâîå ïîääåðåâîNode<0>->Right=Node<3>;// Óêàçàòåëü íà ïðàâîå ïîääåðåâî}else {Node<0>->Flag=false;// Äàííîå âûðàæåíèå íå ìîæåò ðàññìàòðèâàòüñÿ// êàê îáùåå. Åñëè îáùåãî ïîäâûðàæåíèÿ ñ// äàííûì íå áûëî, âêëþ÷èòü äàííîå â ñïèñîê// äëÿ îïåðàöèèL=alloc(sizeof(struct LisType));L->Addr=Node<0>;L->List=OpTable[Val<1>];OpTable[Val<1>]=L;}.Ðàññìîòðèì òåïåðü íåêîòîðûå ïðîñòûå ïðàâèëà ðàñïðåäåëåíèÿ ðåãèñòðîâ ïðè íàëè÷èè îáùèõ ïîäâûðàæåíèé. Åñëè ÷èñëî ðåãèñòðîâ îãðàíè÷åíî, ìîæíî âûáðàòü îäèí èçñëåäóþùèõ äâóõ âàðèàíòîâ.1.
Ïðè îáíàðóæåíèè îáùåãî ïîäâûðàæåíèÿ ñ ïîäâûðàæåíèåì â óæå ïðîñìîòðåííîé ÷àñòè äåðåâà (è, çíà÷èò, ñóæå ðàñïðåäåë¼ííûìè ðåãèñòðàìè) ïðîâåðÿåì, ðàñïîëîæåíî ëè åãî çíà÷åíèå íà ðåãèñòðå. Åñëè äà, è åñëè ðåãèñòðïîñëå ýòîãî íå ìåíÿëñÿ, çàìåíÿåì âû÷èñëåíèå ïîääåðåâà íàçíà÷åíèå â ðåãèñòðå. Åñëè ðåãèñòð ìåíÿëñÿ, òî âû÷èñëÿåìïîäâûðàæåíèå çàíîâî.2. Ââîäèì åù¼ îäèí ïðîõîä. Íà ïåðâîì ïðîõîäå ðàñïðåäåëÿåì ðåãèñòðû. Åñëè â íåêîòîðîé âåðøèíå îáíàðóæèâàåòñÿ, ÷òî å¼ ïîääåðåâî îáùåå ñ óæå âû÷èñëåííûì ðàíåå, íîçíà÷åíèå ðåãèñòðà ïîòåðÿíî, òî â òàêîé âåðøèíå íà âòîðîì ïðîõîäå íåîáõîäèìî ñãåíåðèðîâàòü êîìàíäó ñáðîñà ðåãèñòðà â ðàáî÷óþ ïàìÿòü.
Âûèãðûø â êîäå áóäåò, åñëè ñòîèìîñòü êîìàíäû ñáðîñà ðåãèñòðà + äîñòóï ê ïàìÿòè â ïîâòîðíîì èñïîëüçîâàíèè ýòîé ïàìÿòè íå ïðåâîñõîäèò ñòîèìîñòè çàìåíÿåìîãî ïîääåðåâà. Ïîñêîëüêó ñòîèìîñòü êîìàíäû MOVE èçâåñòíà, ìîæíî ñðàâíèòü ñòîèìîñòè è ïðèíÿòüîïòèìàëüíîå ðåøåíèå: ïîìåòèòü ïðåäûäóùóþ âåðøèíó äëÿñáðîñà ëèáî âû÷èñëÿòü ïîääåðåâî ïîëíîñòüþ.9.9. Òðàíñëÿöèÿ ñâîéñòâ ÿçûêîâ ïðîãðàììèðîâàíèÿ2419.9. Òðàíñëÿöèÿ îáúåêòíî-îðèåíòèðîâàííûõ ñâîéñòâ ÿçûêîâ ïðîãðàììèðîâàíèÿ ýòîì ðàçäåëå áóäóò ðàññìîòðåíû ìåõàíèçìû òðàíñëÿöèè áàçîâûõ êîíñòðóêöèé îáúåêòíî-îðèåíòèðîâàííûõ ÿçûêîâ ïðîãðàììèðîâàíèÿ, à èìåííî íàñëåäîâàíèÿ è âèðòóàëüíûõ ôóíêöèé íà ïðèìåðå ÿçûêà Ñ++.9.9.1.
Âèðòóàëüíûå áàçîâûå êëàññûÊ îïèñàòåëþ áàçîâîãî êëàññà ìîæíî äîáàâèòü êëþ÷åâîåñëîâî virtual.  ýòîì ñëó÷àå åäèíñòâåííûé ïîäîáúåêò âèðòóàëüíîãî áàçîâîãî êëàññà ðàçäåëÿåòñÿ êàæäûì áàçîâûìêëàññîì, â êîòîðîì òîò, èñõîäíûé, áàçîâûé êëàññ îïðåäåë¼í êàê âèðòóàëüíûé.Ïóñòü ìû èìååì ñëåäóþùóþ èåðàðõèþ íàñëåäîâàíèÿ:classclassclassclassL {. . . }A : public virtual L {. . .
}B : public virtual L {. . . }C : public A, public B {. . . }Ýòî ìîæíî èçîáðàçèòü ñëåäóþùåé äèàãðàììîé êëàññîâ:- L ¾AB66CÐèñ. 9.15. Äèàãðàììà êëàññîâ.Êàæäûé îáúåêò A èëè îáúåêò B áóäåò ñîäåðæàòü L, íîâ îáúåêòå C áóäåò ñóùåñòâîâàòü ëèøü îäèí îáúåêò êëàññàL. ßñíî, ÷òî ïðåäñòàâëåíèå îáúåêòà âèðòóàëüíîãî áàçîâîãî242Ãëàâà 9. Ãåíåðàöèÿ êîäàêëàññà L íå ìîæåò áûòü â îäíîé è òîé æå ïîçèöèè îòíîñèòåëüíî è A, è B äëÿ âñåõ îáúåêòîâ. Ñëåäîâàòåëüíî, âî âñåõîáúåêòàõ êëàññîâ, êîòîðûå âêëþ÷àþò êëàññ L êàê âèðòóàëüíûé áàçîâûé êëàññ, äîëæåí õðàíèòüñÿ óêàçàòåëü íà L.Ðåàëèçàöèÿ A, B è C îáúåêòîâ ìîãëà áû âûãëÿäåòü ñëåäóþùèì îáðàçîì:A∗ aptr = new A;aptrB ∗ aptr = new B ;bptrC ∗ aptr = new C ;cptr---×àñòü A×àñòü L×àñòü B×àñòü L×àñòü×àñòü×àñòü×àñòüABCLÐèñ. 9.16. Ðåàëèçàöèÿ A, B è C îáúåêòîâ.9.9.2.
Ìíîæåñòâåííîå íàñëåäîâàíèåÈìåÿ äâà êëàññàclass A {. . . af (int);}class B {. . . bf (int); }ìîæíî îáúÿâèòü òðåòèé êëàññ ñ ýòèìè äâóìÿ â êà÷åñòâåáàçîâûõ:class C : public A, public B {. . . }Îáúåêò êëàññà C ìîæåò áûòü ðàçìåù¼í êàê íåïðåðûâíûé îáúåêò âèäà:×àñòü A×àñòü B×àñòü CÐèñ. 9.17.9.9.
Òðàíñëÿöèÿ ñâîéñòâ ÿçûêîâ ïðîãðàììèðîâàíèÿ243Êàê è â ñëó÷àå ñ åäèíè÷íûì íàñëåäîâàíèåì, çäåñü íå ãàðàíòèðóåòñÿ ïîðÿäîê âûäåëåíèÿ ïàìÿòè äëÿ áàçîâûõ êëàññîâ, ïîýòîìó îáúåêò êëàññà C ìîæåò âûãëÿäåòü è òàê:×àñòü B×àñòü C×àñòü AÐèñ. 9.18.Äîñòóï ê ÷ëåíó êëàññà A, B èëè C ðåàëèçóåòñÿ â òî÷íîñòè òàê æå, êàê è äëÿ åäèíè÷íîãî íàñëåäîâàíèÿ: êîìïèëÿòîð çíàåò ïîëîæåíèå â îáúåêòå êàæäîãî ÷ëåíà è ïîðîæäàåòñîîòâåòñòâóþùèé êîä.Åñëè îáúåêò ðàçìåù¼í â ïàìÿòè â ñîîòâåòñòâèè ñ ïåðâîé äèàãðàììîé: ñíà÷àëà ÷àñòü A îáúåêòà, à çàòåì ÷àñòèB è C , òî âûçîâ ôóíêöèè - ÷ëåíà êëàññà A èëè C áóäåòòàêèì æå, êàê âûçîâ ôóíêöèè-÷ëåíà ïðè åäèíè÷íîì íàñëåäîâàíèè.
Âûçîâ ôóíêöèè-÷ëåíà êëàññà B äëÿ îáúåêòà, çàäàííîãî óêàçàòåëåì íà C , ðåàëèçóåòñÿ íåñêîëüêî ñëîæíåå.ÐàññìîòðèìC ∗ pc = new C ;pc → bf(2);Ôóíêöèÿ B :: bf() åñòåñòâåííî ïðåäïîëàãàåò, ÷òî å¼ ïàðàìåòð this ÿâëÿåòñÿ óêàçàòåëåì íà B . ×òîáû ïîëó÷èòü óêàçàòåëü íà ÷àñòü B îáúåêòà C , ñëåäóåò äîáàâèòü ê óêàçàòåëþpc ñìåùåíèå B îòíîñèòåëüíî C - êîíñòàíòó âðåìåíè êîìïèëÿöèè, êîòîðóþ ìû áóäåì íàçûâàòü delta(B ). Ñîîòíîøåíèåóêàçàòåëÿ pc è óêàçàòåëÿ this, ïåðåäàâàåìîãî â B ::bf, ïîêàçàíî íèæå.pc-this äëÿ B ::bf-×àñòü A×àñòü B×àñòü CÐèñ. 9.19.?Delta(B )244Ãëàâà 9.
Ãåíåðàöèÿ êîäà9.9.3. Åäèíè÷íîå íàñëåäîâàíèå è âèðòóàëüíûå ôóíêöèèÅñëè êëàññ base ñîäåðæèò âèðòóàëüíóþ ôóíêöèþ vf , àêëàññ derived, ïîðîæä¼ííûé ïî êëàññó base, òàêæå ñîäåðæèò ôóíêöèþ vf òîãî æå òèïà, òî îáðàùåíèå ê vf äëÿîáúåêòà êëàññà derived âûçûâàåò derived :: vf äàæå ïðèäîñòóïå ÷åðåç óêàçàòåëü èëè ññûëêó íà base.  òàêîì ñëó÷àå ãîâîðÿò, ÷òî ôóíêöèÿ ïðîèçâîäíîãî êëàññà ïîäìåíÿåò(override) ôóíêöèþ áàçîâîãî êëàññà. Åñëè, îäíàêî, òèïûýòèõ ôóíêöèé ðàçëè÷íû, òî ôóíêöèè ñ÷èòàþòñÿ ðàçëè÷íûìè è ìåõàíèçì âèðòóàëüíîñòè íå âêëþ÷àåòñÿ.Âèðòóàëüíûå ôóíêöèè ìîæíî ðåàëèçîâàòü ïðè ïîìîùèòàáëèöû óêàçàòåëåé íà âèðòóàëüíûå ôóíêöèè vtbl.  ñëó÷àå åäèíè÷íîãî íàñëåäîâàíèÿ òàáëèöà âèðòóàëüíûõ ôóíêöèé êëàññà áóäåò ñîäåðæàòü ññûëêè íà ñîîòâåòñòâóþùèåôóíêöèè, à êàæäûé îáúåêò äàííîãî êëàññà áóäåò ñîäåðæàòü óêàçàòåëü íà òàáëèöó vtbl.class A {public:int a;virtual void f (int);virtual void g (int);virtual void h(int);};class B : public A {public:int b;void g (int);};class C : public B {public:int c;void h(int);};Îáúåêò êëàññà C áóäåò âûãëÿäåòü ïðèìåðíî òàê:9.9.
Òðàíñëÿöèÿ ñâîéñòâ ÿçûêîâ ïðîãðàììèðîâàíèÿ-int a;vptrint bint c245&A :: f&B :: g&C :: hÐèñ. 9.20.9.9.4. Ìíîæåñòâåííîå íàñëåäîâàíèå è âèðòóàëüíûå ôóíêöèèÏðè ìíîæåñòâåííîì íàñëåäîâàíèè âèðòóàëüíûå ôóíêöèè ðåàëèçóþòñÿ íåñêîëüêî ñëîæíåå. Ðàññìîòðèì ñëåäóþùèå îáúÿâëåíèÿ:class A {public:virtual void f (int);};class B : {public:virtual void f (int);virtual void g (int);};class C : public A, public B {public:void f ();};Ïîñêîëüêó êëàññ A ïîðîæä¼í ïî êëàññàì A è B , êàæäûéèç ñëåäóþùèõ âûçîâîâ áóäåò îáðàùàòüñÿ ê C :: f () (ñ÷èòàÿ,÷òî êàæäûé èç òð¼õ óêàçàòåëåé ñìîòðèò íà îáúåêò êëàññàC ):pa → f ()pb → f ()pc → f ()Ðàññìîòðèì, äëÿ ïðèìåðà, âûçîâ pb → f (). Ïðè âõîäåâ C :: f óêàçàòåëü this äîëæåí óêàçûâàòü íà íà÷àëî îáúåêòà C , à íå íà ÷àñòü B â í¼ì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
