В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 25
Текст из файла (страница 25)
Ïîýòîìó â äåðåâå ïîÿâëÿþòñÿ áîëåå äëèííûå è áîëååêîðîòêèå âåòâè, è ñðåäíåå âðåìÿ ïîèñêà óâåëè÷èâàåòñÿ.×òîáû óìåíüøèòü ñðåäíåå âðåìÿ ïîèñêà â äâîè÷íîìäåðåâå, ìîæíî â ïðîöåññå ïîñòðîåíèÿ äåðåâà ñëåäèòü çàòåì, ÷òîáû îíî âñ¼ âðåìÿ îñòàâàëîñü ñáàëàíñèðîâàííûì.À èìåííî, íàçîâ¼ì äåðåâî ñáàëàíñèðîâàííûì, åñëè íè äëÿêàêîé âåðøèíû âûñîòà âûõîäÿùåé èç íå¼ ïðàâîé âåòâè íåîòëè÷àåòñÿ îò âûñîòû ëåâîé áîëåå ÷åì íà 1. Äëÿ òîãî ÷òîáûäîñòè÷ü ñáàëàíñèðîâàííîñòè, â ïðîöåññå äîáàâëåíèÿ íîâûõ7.5. Òàáëèöû íà äåðåâüÿõ177$Q%Q'Q%Q&Q(QGh\Zy\_jrbgZ$Q'Q(QZ&Q[Ðèñ.
7.6.$Q&Q%Q(Q'Q)QGh\Zy\_jrbgZ(Q%Q'Q)Q$Q*Q&Q*QZ[Ðèñ. 7.7.âåðøèí äåðåâî ìîæíî ñëåãêà ïåðåñòðàèâàòü ñëåäóþùèì îáðàçîì [1].Îïðåäåëèì äëÿ êàæäîé âåðøèíû äåðåâà õàðàêòåðèñòèêó, ðàâíóþ ðàçíîñòè âûñîò âûõîäÿùèõ èç íå¼ ïðàâîé èëåâîé âåòâåé.  ñáàëàíñèðîâàííîì äåðåâå õàðàêòåðèñòèêàâåðøèíû ìîæåò áûòü ðàâíîé −1, 0 è 1, äëÿ ëèñòüåâ îíàðàâíà 0.Ïóñòü ìû îïðåäåëèëè ìåñòî íîâîé âåðøèíû â äåðåâå. żõàðàêòåðèñòèêà ðàâíà 0.
Íàçîâ¼ì ïóòü, âåäóùèé îò êîðíÿ ê178Ãëàâà 7. Îðãàíèçàöèÿ òàáëèö ñèìâîëîâ$Q&Q%Q'Q(Q(Q)Q$Q%Q'Q)Q *Q&Q*QGh\Zy\_jrbgZZ[Ðèñ. 7.8.$%($%(Gh\Zy\_jrbgZZ[Ðèñ. 7.9.íîâîé âåðøèíå, âûäåëåííûì. Ïðè äîáàâëåíèè íîâîé âåðøèíû ìîãóò èçìåíèòüñÿ õàðàêòåðèñòèêè òîëüêî òåõ âåðøèí,êîòîðûå ëåæàò íà âûäåëåííîì ïóòè. Ðàññìîòðèì çàêëþ÷èòåëüíûé îòðåçîê âûäåëåííîãî ïóòè, òàêîé, ÷òî äî äîáàâëåíèÿ âåðøèíû õàðàêòåðèñòèêè âñåõ âåðøèí íà í¼ì áûëèðàâíû 0. Åñëè âåðõíèì êîíöîì ýòîãî îòðåçêà ÿâëÿåòñÿ ñàìêîðåíü, òî äåðåâî ïåðåñòðàèâàòü íå íàäî, äîñòàòî÷íî ëèøüèçìåíèòü õàðàêòåðèñòèêè âåðøèí íà ýòîì ïóòè íà 1 èëè−1, â çàâèñèìîñòè îò òîãî, âëåâî èëè âïðàâî ïðèñòðîåíà7.6.
Ðåàëèçàöèÿ áëî÷íîé ñòðóêòóðû179íîâàÿ âåðøèíà.Ïóñòü âåðõíèé êîíåö çàêëþ÷èòåëüíîãî îòðåçêà íå êîðåíü. Ðàññìîòðèì âåðøèíó A ¾ðîäèòåëÿ¿ âåðõíåãî êîíöàçàêëþ÷èòåëüíîãî îòðåçêà. Ïåðåä äîáàâëåíèåì íîâîé âåðøèíû õàðàêòåðèñòèêà A áûëà ðàâíà ±1. Åñëè A èìåëà õàðàêòåðèñòèêó 1 (−1) è íîâàÿ âåðøèíà äîáàâëÿåòñÿ â ëåâóþ(ïðàâóþ) âåòâü, òî õàðàêòåðèñòèêà âåðøèíû A ñòàíîâèòñÿðàâíîé 0, à âûñîòà ïîääåðåâà ñ êîðíåì â A íå ìåíÿåòñÿ. Òàê÷òî è â ýòîì ñëó÷àå äåðåâî ïåðåñòðàèâàòü íå íàäî.Ïóñòü òåïåðü õàðàêòåðèñòèêà A äî ïåðåñòðàèâàíèÿ áûëà ðàâíà −1 è íîâàÿ âåðøèíà äîáàâëåíà ê ëåâîé âåòâè A(àíàëîãè÷íî äëÿ ñëó÷àÿ 1 è äîáàâëåíèÿ ê ïðàâîé âåòâè).Ðàññìîòðèì âåðøèíó B ëåâîãî ïîòîìêà A.
Âîçìîæíûñëåäóþùèå âàðèàíòû.Åñëè õàðàêòåðèñòèêà B ïîñëå äîáàâëåíèÿ íîâîé âåðøèíû â D ñòàëà ðàâíà −1, òî äåðåâî èìååò ñòðóêòóðó, èçîáðàæ¼ííóþ íà ðèñ. 7.6, à. Ïåðåñòðîèâ äåðåâî òàê, êàê ýòîèçîáðàæåíî íà ðèñ. 7.6, á, ìû äîáü¼ìñÿ ñáàëàíñèðîâàííîñòè (â ñêîáêàõ óêàçàíû õàðàêòåðèñòèêè âåðøèí, ãäå ýòî ñóùåñòâåííî, è ñîîòíîøåíèÿ âûñîò ïîñëå äîáàâëåíèÿ).Åñëè õàðàêòåðèñòèêà âåðøèíû B ïîñëå äîáàâëåíèÿ íîâîé âåðøèíû â E ñòàëà ðàâíà 1, òî íàäî îòäåëüíî ðàññìîòðåòü ñëó÷àè, êîãäà õàðàêòåðèñòèêà âåðøèíû E , ñëåäóþùåéçà B íà âûäåëåííîì ïóòè, ñòàëà ðàâíà −1, 1 è 0 (â ïîñëåäíåì ñëó÷àå âåðøèíà E íîâàÿ). Âèä äåðåâà äî è ïîñëåïåðåñòðîéêè äëÿ ýòèõ ñëó÷àåâ ïîêàçàí ñîîòâåòñòâåííî íàðèñ. 7.7, 7.8 è 7.9.7.6.
Ðåàëèçàöèÿ áëî÷íîé ñòðóêòóðûÑ òî÷êè çðåíèÿ ñòðóêòóðû ïðîãðàììû áëîêè (è/èëèïðîöåäóðû) îáðàçóþò äåðåâî. Êàæäîé âåðøèíå äåðåâà ýòîãî ïðåäñòàâëåíèÿ, ñîîòâåòñòâóþùåé áëîêó, ìîæíî ñîïîñòàâèòü ñâîþ òàáëèöó ñèìâîëîâ (è, âîçìîæíî, îäíó îáùóþ òàáëèöó èäåíòèôèêàòîðîâ). Ðàáîòó ñ òàáëèöàìè áëîêîâ ìîæíî îðãàíèçîâàòü â ìàãàçèííîì ðåæèìå: ïðè âõîäå â áëîêñîçäàâàòü òàáëèöó ñèìâîëîâ, ïðè âûõîäå óíè÷òîæàòü.180Ãëàâà 7. Îðãàíèçàöèÿ òàáëèö ñèìâîëîâÏðè ýòîì ñàìè òàáëèöû äîëæíû áûòü ñâÿçàíû â óïîðÿäî÷åííûé ñïèñîê, ÷òîáû ìîæíî áûëî ïðîñìàòðèâàòü èõ âïîðÿäêå âëîæåííîñòè.
Åñëè òàáëèöû îðãàíèçîâàíû ñ ïîìîùüþ ôóíêöèé ðàññòàíîâêè, ýòî îçíà÷àåò, ÷òî äëÿ êàæäîéòàáëèöû äîëæíà áûòü ñîçäàíà ñâîÿ òàáëèöà ðàññòàíîâêè.7.7. Ñðàâíåíèå ìåòîäîâ ðåàëèçàöèèòàáëèöÐàññìîòðèì ïðåèìóùåñòâà è íåäîñòàòêè ðàññìîòðåííûõìåòîäîâ ðåàëèçàöèè òàáëèö ñ òî÷êè çðåíèÿ òåõíèêè èñïîëüçîâàíèÿ ïàìÿòè.Èñïîëüçîâàíèå äèíàìè÷åñêîé ïàìÿòè, êàê ïðàâèëî, äîâîëüíî äîðîãàÿ îïåðàöèÿ, ïîñêîëüêó ìåõàíèçìû ïîääåðæàíèÿ ðàáîòû ñ äèíàìè÷åñêîé ïàìÿòüþ ìîãóò áûòü äîñòàòî÷íî ñëîæíû. Íåîáõîäèìî ïîääåðæèâàòü ñïèñêè ñâîáîäíîé èçàíÿòîé ïàìÿòè, âûáèðàòü íàèáîëåå ïîäõîäÿùèé êóñîê ïàìÿòè ïðè çàïðîñå, âêëþ÷àòü îñâîáîäèâøèéñÿ êóñîê â ñïèñîê ñâîáîäíîé ïàìÿòè è, âîçìîæíî, ñêëåèâàòü êóñêè ñâîáîäíîé ïàìÿòè â ñïèñêå.Ñ äðóãîé ñòîðîíû, èñïîëüçîâàíèå ìàññèâà òðåáóåò îòâåäåíèÿ çàðàíåå äîâîëüíî áîëüøîé ïàìÿòè, à ýòî îçíà÷àåò,÷òî çíà÷èòåëüíàÿ ïàìÿòü âîîáùå íå áóäåò èñïîëüçîâàòüñÿ.Êðîìå òîãî, ÷àñòî ïðèõîäèòñÿ çàïîëíÿòü íå âñå ýëåìåíòûìàññèâà (íàïðèìåð, â òàáëèöå èäåíòèôèêàòîðîâ èëè â òåõñëó÷àÿõ, êîãäà â ìàññèâå ôàêòè÷åñêè õðàíÿòñÿ çàïèñè ïåðåìåííîé äëèíû, íàïðèìåð, åñëè â òàáëèöå ñèìâîëîâ çàïèñèäëÿ ðàçëè÷íûõ îáúåêòîâ èìåþò ðàçëè÷íûé ñîñòàâ ïîëåé).Îáðàùåíèå ê ýëåìåíòàì ìàññèâà ìîæåò îçíà÷àòü èñïîëüçîâàíèå îïåðàöèè óìíîæåíèÿ ïðè âû÷èñëåíèè èíäåêñîâ, ÷òîìîæåò çàìåäëèòü èñïîëíåíèå.Íàèëó÷øèì, ïî-âèäèìîìó, ÿâëÿåòñÿ ìåõàíèçì äîñòóïàïî óêàçàòåëÿì è èñïîëüçîâàíèå ôàêòà ìàãàçèííîé îðãàíèçàöèè ïàìÿòè â êîìïèëÿòîðå.
Äëÿ ýòîãî ïðîöåäóðà âûäåëåíèÿ ïàìÿòè âûäà¼ò íåîáõîäèìûé êóñîê èç ïîäðÿä èäóùåéïàìÿòè, à ïðè âûõîäå èç ïðîöåäóðû âñÿ ïàìÿòü, ñâÿçàííàÿñ ýòîé ïðîöåäóðîé, îñâîáîæäàåòñÿ ïðîñòîé ïåðåñòàíîâêîé7.7. Ñðàâíåíèå ìåòîäîâ ðåàëèçàöèè òàáëèö181óêàçàòåëÿ ñâîáîäíîé ïàìÿòè â ñîñòîÿíèå ïåðåä íà÷àëîì îáðàáîòêè ïðîöåäóðû.  ÷èñòîì âèäå ýòî íå âñåãäà, îäíàêî,âîçìîæíî. Íàïðèìåð, ëîêàëüíûé ìîäóëü â Ìîäóëå-2 ìîæåò ýêñïîðòèðîâàòü íåêîòîðûå îáúåêòû íàðóæó. Ïðè ýòîìñõåìó ðåàëèçàöèè ïðèõîäèòñÿ ¾ïîäãîíÿòü¿ ïîä ìåõàíèçìðàñïðåäåëåíèÿ ïàìÿòè.  äàííîì ñëó÷àå, íàïðèìåð, íåîáõîäèìî ýêñïîðòèðîâàííûå îáúåêòû âûíåñòè â ñðåäó îõâàòûâàþùåãî áëîêà è ñâåðíóòü áëîê ëîêàëüíîãî ìîäóëÿ.Ãëàâà 8.Ïðîìåæóòî÷íîåïðåäñòàâëåíèåïðîãðàììû ïðîöåññå òðàíñëÿöèè êîìïèëÿòîð ÷àñòî èñïîëüçóþòïðîìåæóòî÷íîå ïðåäñòàâëåíèå (ÏÏ) èñõîäíîé ïðîãðàììû,ïðåäíàçíà÷åííîå ïðåæäå âñåãî äëÿ óäîáñòâà ãåíåðàöèè êîäà è/èëè ïðîâåäåíèÿ ðàçëè÷íûõ îïòèìèçàöèé.
Ñàìà ôîðìàÏÏ çàâèñèò îò öåëåé åãî èñïîëüçîâàíèÿ.Íàèáîëåå ÷àñòî èñïîëüçóåìûìè ôîðìàìè ÏÏ ÿâëÿåòñÿîðèåíòèðîâàííûé ãðàô (â ÷àñòíîñòè, àáñòðàêòíîå ñèíòàêñè÷åñêîå äåðåâî, â òîì ÷èñëå àòðèáóòèðîâàííîå), òð¼õàäðåñíûé êîä (â âèäå òðîåê èëè ÷åòâ¼ðîê), ïðåôèêñíàÿ è ïîñòôèêñíàÿ çàïèñü.8.1. Ïðåäñòàâëåíèå â âèäå îðèåíòèðîâàííîãî ãðàôàÏðîñòåéøåé ôîðìîé ïðîìåæóòî÷íîãî ïðåäñòàâëåíèÿÿâëÿåòñÿ ñèíòàêñè÷åñêîå äåðåâî ïðîãðàììû. Òó æå ñàìóþèíôîðìàöèþ î âõîäíîé ïðîãðàììå, íî â áîëåå êîìïàêòíîé8.2. Òð¼õàäðåñíûé êîä183ôîðìå äà¼ò îðèåíòèðîâàííûé àöèêëè÷åñêèé ãðàô (ÎÀÃ), âêîòîðîì â îäíó âåðøèíó îáúåäèíåíû âåðøèíû ñèíòàêñè÷åñêîãî äåðåâà, ïðåäñòàâëÿþùèå îáùèå ïîäâûðàæåíèÿ.
Ñèíòàêñè÷åñêîå äåðåâî è ÎÀà äëÿ îïåðàòîðà ïðèñâàèâàíèÿa := b ∗ −c + b ∗ −cïðèâåäåíû íà ðèñ. 8.1. DDE EFFEFZ[Ðèñ. 8.1.Íà ðèñ. 8.2 ïðèâåäåíû äâà ïðåäñòàâëåíèÿ â ïàìÿòè ñèíòàêñè÷åñêîãî äåðåâà íà ðèñ. 8.1, à. Êàæäàÿ âåðøèíà êîäèðóåòñÿ çàïèñüþ ñ ïîëåì äëÿ îïåðàöèè è ïîëÿìè äëÿ óêàçàòåëåé íà ïîòîìêîâ. Íà ðèñ. 8.2, á, âåðøèíû ðàçìåùåíûâ ìàññèâå çàïèñåé è èíäåêñ (èëè âõîä) âåðøèíû ñëóæèòóêàçàòåëåì íà íåå.8.2. Òð¼õàäðåñíûé êîäÒð¼õàäðåñíûé êîä ýòî ïîñëåäîâàòåëüíîñòü îïåðàòîðîâ âèäà x := y op z , ãäå x, y è z èìåíà, êîíñòàíòûèëè ñãåíåðèðîâàííûå êîìïèëÿòîðîì âðåìåííûå îáúåêòû.Çäåñü op äâóìåñòíàÿ îïåðàöèÿ, íàïðèìåð, îïåðàöèÿ ïëàâàþùåé èëè ôèêñèðîâàííîé àðèôìåòèêè, ëîãè÷åñêàÿ èëèïîáèòîâàÿ.
 ïðàâóþ ÷àñòü ìîæåò âõîäèòü òîëüêî îäèí çíàêîïåðàöèè.184Ãëàâà 8. Ïðîìåæóòî÷íîå ïðåäñòàâëåíèå ïðîãðàììû LG DLG ELG ELG FLGELGFLGELGFLGD LG FZ[Ðèñ. 8.2.Ñîñòàâíûå âûðàæåíèÿ äîëæíû áûòü ðàçáèòû íà ïîäâûðàæåíèÿ, ïðè ýòîì ìîãóò ïîÿâèòüñÿ âðåìåííûå èìåíà (ïåðåìåííûå). Ñìûñë òåðìèíà ¾òð¼õàäðåñíûé êîä¿ â òîì, ÷òîêàæäûé îïåðàòîð îáû÷íî èìååò òðè àäðåñà: äâà äëÿ îïåðàíäîâ è îäèí äëÿ ðåçóëüòàòà.
Òð¼õàäðåñíûé êîä ýòî ëèíåàðèçîâàííîå ïðåäñòàâëåíèå ñèíòàêñè÷åñêîãî äåðåâà èëèÎÀÃ, â êîòîðîì âðåìåííûå èìåíà ñîîòâåòñòâóþò âíóòðåííèì âåðøèíàì äåðåâà èëè ãðàôà. Íàïðèìåð, âûðàæåíèåx + y ∗ z ìîæåò áûòü ïðîòðàíñëèðîâàíî â ïîñëåäîâàòåëüíîñòü îïåðàòîðîât1 := y * zt2 := x + t1ãäå t1 è t2 èìåíà, ïîðîæä¼ííûå êîìïèëÿòîðîì. âèäå òð¼õàäðåñíîãî êîäà ïðåäñòàâëÿþòñÿ íå òîëüêîäâóìåñòíûå îïåðàöèè, âõîäÿùèå â âûðàæåíèÿ.  òàêîì æåâèäå ïðåäñòàâëÿþòñÿ îïåðàòîðû óïðàâëåíèÿ ïðîãðàììû èîäíîìåñòíûå îïåðàöèè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
