В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 31
Текст из файла (страница 31)
Íàïðèìåð, äëÿ âûðàæåíèÿF OR ( F AND T AND T ) OR Tïîëó÷èì àòðèáóòèðîâàííîåðèñ. 9.12, è êîääåðåâî,èçîáðàæ¼ííîåíà([SU7UXH/DE 7UXH%RRO([SU )DOVH/DE )DOVH1RGH/DE 257UXH/DE 7UXH)DOVH/DE %RRO([SU1RGH/DE )7UXH/DE 7UXH%RRO([SU )DOVH/DE )DOVH1RGH/DE 25%RRO([SU7UXH/DE 7UXH)DOVH/DE 1RGH/DE 7UXH/DE 7UXH%RRO([SU )DOVH/DE 7UXH/DE )DOVH/DE 1RGH/DE $1'71RGH/DE 7UXH/DE 7UXH$1'7UXH/DE %RRO([SU )DOVH/DE 1RGH/DE 7Ðèñ. 9.12.1:7:GOTO2:8:4:9: GOTO5:10:GOTO6:GOTO3:GOTOTrue: ...False: ...1RGH/DE %RRO([SU )DOVH/DE %RRO([SU)7UXH/DE 7UXH%RRO([SU )DOVH/DE )DOVH236TrueTrue1RGH/DE 7UXH/DE 7UXH%RRO([SU )DOVH/DE 1RGH/DE 7230Ãëàâà 9. Ãåíåðàöèÿ êîäàÝòó ëèíåàðèçîâàííóþ çàïèñü ìîæíî òðàêòîâàòü êàêïðîãðàììó âû÷èñëåíèÿ ëîãè÷åñêîãî çíà÷åíèÿ: êàæäàÿñòðîêà ìîæåò áûòü ïîìå÷åíà íîìåðîì âåðøèíû è ñîäåðæàòü ëèáî ïåðåõîä íà äðóãóþ ñòðîêó, ëèáî ïåðåõîä íà Trueèëè False, ÷òî ñîîòâåòñòâóåò çíà÷åíèþ âûðàæåíèÿ trueèëè false.
Áóäåì ãîâîðèòü, ÷òî ïîëó÷åííàÿ ïðîãðàììà âû÷èñëÿåò (èëè èíòåðïðåòèðóåò) çíà÷åíèå âûðàæåíèÿ, åñëèâ ðåçóëüòàòå å¼ âûïîëíåíèÿ (îò ïåðâîé ñòðîêè) ìû ïðèä¼ìê ñòðîêå, ñîäåðæàùåé GOTO True èëè GOTO False.Óòâåðæäåíèå 9.1.  ðåçóëüòàòå èíòåðïðåòàöèèïîääåðåâà ñ íåêîòîðûìè çíà÷åíèÿìè àòðèáóòîâFalseLab è TrueLab â åãî êîðíå âûïîëíÿåòñÿ êîìàíäàGOTO TrueLab, åñëè çíà÷åíèå âûðàæåíèÿ èñòèííî,è êîìàíäà GOTO FalseLab, åñëè çíà÷åíèå âûðàæåíèÿëîæíî.Äîêàçàòåëüñòâî.
Ïðèìåíèì èíäóêöèþ ïî âûñîòå äåðåâà. Äëÿ äåðåâüåâ âûñîòû 1, ñîîòâåòñòâóþùèõ ïðàâèëàìBoolExpr ::= F è BoolExpr ::= T,ñïðàâåäëèâîñòü óòâåðæäåíèÿ ñëåäóåò èç ñîîòâåòñòâóþùèõàòðèáóòíûõ ïðàâèë. Ïóñòü äåðåâî èìååò âûñîòó n > 1. Çàâèñèìîñòü àòðèáóòîâ äëÿ äèçúþíêöèè è êîíúþíêöèè ïðèâåäåíà íà ðèñ. 9.13.Åñëè äëÿ êîíúþíêöèè çíà÷åíèå ëåâîãî ïîääåðåâà ëîæíî è ïî èíäóêöèè âû÷èñëåíèå ëåâîãî ïîääåðåâà çàâåðøàåòñÿ êîìàíäîé GOTO FalseLab<1>, òî ïîëó÷àåì, ÷òî âû÷èñëåíèå âñåãî äåðåâà çàâåðøàåòñÿ êîìàíäîé ïåðåõîäàGOTO FalseLab<0> (= FalseLab<1>). Åñëè æå çíà÷åíèå ëåâîãî ïîääåðåâà èñòèííî, òî åãî âû÷èñëåíèå çàâåðøàåòñÿ êîìàíäîé ïåðåõîäà GOTO TrueLab<1> (= NodeLab<3>).Åñëè çíà÷åíèå ïðàâîãî ïîääåðåâà ëîæíî, òî âû÷èñëåíèåâñåãî äåðåâà çàâåðøàåòñÿ êîìàíäîé GOTO FalseLab<0> (=FalseLab<3>).
Åñëè æå îíî èñòèííî, âû÷èñëåíèå âñåãî äåðåâà çàâåðøàåòñÿ êîìàíäîé ïåðåõîäà GOTO TrueLab<0> (=TrueLab<3>). Àíàëîãè÷íî äëÿ äèçúþíêöèè.Óòâåðæäåíèå 9.2. Äëÿ ëþáîãî ëîãè÷åñêîãî âûðàæåíèÿ,ñîñòîÿùåãî èç êîíñòàíò, ïðîãðàììà, ïîëó÷åííàÿ â ðå-9.7. Òðàíñëÿöèÿ ëîãè÷åñêèõ âûðàæåíèé231)DOVH/DE !7UXH/DE !)DOVH/DE ! )DOVH/DE !$1'7UXH/DE ! 1RGH/DE !)DOVH/DE ! )DOVH/DE !7UXH/DE ! 7UXH/DE !)DOVH/DE !7UXH/DE !)DOVH/DE ! 1RGH/DE !257UXH/DE ! 7UXH/DE !)DOVH/DE ! )DOVH/DE !7UXH/DE ! 7UXH/DE !Ðèñ. 9.13.çóëüòàòå îáõîäà äåðåâà ýòîãî âûðàæåíèÿ, çàâåðøàåòñÿ ñî çíà÷åíèåì ëîãè÷åñêîãî âûðàæåíèÿ â îáû÷íîéèíòåðïðåòàöèè, òî åñòü îñóùåñòâëÿåòñÿ ïåðåõîä íàTrue äëÿ çíà÷åíèÿ, ðàâíîãî true, è ïåðåõîä íà ìåòêóFalse äëÿ çíà÷åíèÿ f alse.Äîêàçàòåëüñòâî.
Ýòî óòâåðæäåíèå ÿâëÿåòñÿ ÷àñòíûìñëó÷àåì ïðåäûäóùåãî. Åãî ñïðàâåäëèâîñòü ñëåäóåò èç òîãî,÷òî ìåòêè êîðíÿ äåðåâà ðàâíû ñîîòâåòñòâåííî TrueLab =True è FalseLab = False.Äîáàâèì òåïåðü íîâîå ïðàâèëî â ïðåäûäóùóþ ãðàììàòèêó:RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" + "if (" + Val<1> +"==T) GOTO" + TrueLab<0> + "else GOTO" +FalseLab<0>.232Ãëàâà 9. Ãåíåðàöèÿ êîäàÒîãäà, íàïðèìåð, äëÿ âûðàæåíèÿ A OR (B AND C ANDD) OR E ïîëó÷èì ñëåäóþùóþ ïðîãðàììó:1:7:if (A==T) GOTO True else GOTO 22:8:4:9: if (B==T) GOTO 5 else GOTO 35:10:if (C==T) GOTO 6 else GOTO 36:if (D==T) GOTO True else GOTO 33:if (E==T) GOTO True else GOTO FalseTrue: ...False: ...Ïðè êàæäîì êîíêðåòíîì íàáîðå äàííûõ ýòà ïðîãðàììà ïðåâðàùàåòñÿ â ïðîãðàììó âû÷èñëåíèÿ ëîãè÷åñêîãîçíà÷åíèÿ.Óòâåðæäåíèå 9.3.  êàæäîé ñòðîêå ïðîãðàììû, ñôîðìèðîâàííîé ïðåäûäóùåé àòðèáóòíîé ñõåìîé, îäíà èçìåòîê âíóòðè óñëîâíîãî îïåðàòîðà ñîâïàäàåò ñ ìåòêîé ñëåäóþùåé ñòðîêè.Äîêàçàòåëüñòâî.
Äåéñòâèòåëüíî, ïî ïðàâèëàì íàñëåäîâàíèÿ àòðèáóòîâ TrueLab è FalseLab, â ïðàâèëàõ äëÿ äèçúþíêöèè è êîíúþíêöèè ëèáî àòðèáóò FalseLab, ëèáî àòðèáóò TrueLab ïðèíèìàåò çíà÷åíèå ìåòêè ñëåäóþùåãî ïîääåðåâà. Êðîìå òîãî, êàê çíà÷åíèå FalseLab, òàê è çíà÷åíèåTrueLab, ïåðåäàþòñÿ â ïðàâîå ïîääåðåâî îò ïðåäêà. Òàêèìîáðàçîì, ñàìûé ïðàâûé ïîòîìîê âñåãäà èìååò îäíó èç ìåòîê TrueLab èëè FalseLab, ðàâíóþ ìåòêå ïðàâîãî áðàòà ñîîòâåòñòâóþùåãî ïîääåðåâà. Ó÷èòûâàÿ ïîðÿäîê ãåíåðàöèèêîìàíä, ïîëó÷àåì ñïðàâåäëèâîñòü óòâåðæäåíèÿ.Äîïîëíèì òåïåðü àòðèáóòíóþ ãðàììàòèêó ñëåäóþùèìîáðàçîì:RULEExpr ::= BoolExprSEMANTICSFalseLab<1>=False; TrueLab<1>=True;Sign<1>=false;9.7.
Òðàíñëÿöèÿ ëîãè÷åñêèõ âûðàæåíèéCode<0>=Code<1>.RULEBoolExpr ::= BoolExpr 'AND' BoolExprSEMANTICSFalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Sign<1>=false; Sign<3>=Sign<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= BoolExpr 'OR' BoolExprSEMANTICSFalseLab<1>=NodeLab<3>; TrueLab<1>=TrueLab<0>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Sign<1>=true; Sign<3>=Sign<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= 'NOT' BoolExprSEMANTICSFalseLab<2>=TrueLab<0>; TrueLab<2>=FalseLab<0>;Sign<2>=! Sign<0>;Code<0>=Code<2>.RULEBoolExpr ::= FSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + FalseLab<0>.RULEBoolExpr ::= TSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + TrueLab<0>.RULEBoolExpr ::= IdentSEMANTICS233234Ãëàâà 9.
Ãåíåðàöèÿ êîäàCode<0>=NodeLab<0> + ":" + "if (" + Val<1> +"==T) GOTO" + TrueLab<0> + "else GOTO" +FalseLab<0>.Ïðàâèëà íàñëåäîâàíèÿ àòðèáóòà Sign ïðèâåäåíû íàðèñ. 9.14.6LJQ6LJQ$1'6LJQ IDOVH6LJQ !127256LJQ6LJQ WUXH6LJQ6LJQ ! QRW6LJQ !Ðèñ. 9.14.Ïðîãðàììó æåëàòåëüíî ñôîðìèðîâàòü òàêèì îáðàçîì,÷òîáû else-ìåòêà áûëà êàê ðàç ìåòêîé ñëåäóþùåé âåðøèíû.
Êàê ýòî ìîæíî ñäåëàòü, ñëåäóåò èç ñëåäóþùåãî óòâåðæäåíèÿ.Óòâåðæäåíèå 9.4.  êàæäîé òåðìèíàëüíîé âåðøèíå,ìåòêà áëèæàéøåãî ïðàâîãî äëÿ íå¼ ïîääåðåâà ðàâíàçíà÷åíèþ àòðèáóòà FalseLab ýòîé âåðøèíû, òîãäàè òîëüêî òîãäà, êîãäà çíà÷åíèå àòðèáóòà Sign ýòîéâåðøèíû ðàâíî true, è íàîáîðîò, ìåòêà áëèæàéøåãîïðàâîãî äëÿ íå¼ ïîääåðåâà ðàâíà çíà÷åíèþ àòðèáóòàTrueLab ýòîé âåðøèíû, òîãäà è òîëüêî òîãäà, êîãäàçíà÷åíèå àòðèáóòà Sign ðàâíî f alse.Äîêàçàòåëüñòâî.
Äåéñòâèòåëüíî, åñëè áëèæàéøåé îáùåé âåðøèíîé ÿâëÿåòñÿ AND, òî â ëåâîãî ïîòîìêà ïåðåäà¼òñÿ NodeLab ïðàâîãî ïîòîìêà â êà÷åñòâå TrueLab è îäíîâðåìåííî Sign ïðàâîãî ïîòîìêà ðàâåí true. Åñëè æå áëèæàéøåé îáùåé âåðøèíîé ÿâëÿåòñÿ OR, òî â ëåâîãî ïîòîìêàïåðåäà¼òñÿ NodeLab ïðàâîãî ïîòîìêà â êà÷åñòâå FalseLab9.7. Òðàíñëÿöèÿ ëîãè÷åñêèõ âûðàæåíèé235è îäíîâðåìåííî Sign ïðàâîãî ïîòîìêà ðàâåí f alse. Âî âñåæå ïðàâûå ïîòîìêè çíà÷åíèÿ TrueLab, FalseLab è Sign ïåðåäàþòñÿ èç ïðåäêà (çà èñêëþ÷åíèåì ïðàâèëà äëÿ NOT, âêîòîðîì TrueLab è FalseLab ìåíÿþòñÿ ìåñòàìè, íî îäíîâðåìåííî íà ïðîòèâîïîëîæíûé ìåíÿåòñÿ è Sign).Ýòè äâà óòâåðæäåíèÿ (3 è 4) ïîçâîëÿþò çàìåíèòü ïîñëåäíåå ïðàâèëî àòðèáóòíîé ãðàììàòèêè ñëåäóþùèì îáðàçîì:RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" +(Sign<0>? "if (" + Val<1> + "==T) GOTO" + TrueLab<0>: "if (" + Val<1> + "==F) GOTO" + FalseLab<0>). ñâîþ î÷åðåäü, ïðè ãåíåðàöèè ìàøèííûõ êîìàíä ýòîïðàâèëî ìîæíî çàìåíèòü íà ñëåäóþùåå:RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" + "TST" + Val<1> +(Sign<0>? "BNE" + TrueLab<0>: "BEQ" + FalseLab<0>).Òàêèì îáðàçîì, äëÿ âûðàæåíèÿ A OR (B AND C ANDD) OR E ïîëó÷èì ñëåäóþùèé êîä íà êîìàíäàõ ïåðåõîäà:1:7:TSTBNE2:8:4:9: TSTBEQ5:10:TSTBEQ6:TSTATrueB3C3D236Ãëàâà 9.
Ãåíåðàöèÿ êîäàBNE TrueTST EBEQ FalseTrue: ...False: ...3:Åñëè ýëåìåíòîì ëîãè÷åñêîãî âûðàæåíèÿ ÿâëÿåòñÿ ñðàâíåíèå, òî ãåíåðèðóåòñÿ êîìàíäà, ñîîòâåòñòâóþùàÿ çíàêóñðàâíåíèÿ (BEQ äëÿ =, BNE äëÿ <>, BGE äëÿ >= è ò.ä.), åñëè àòðèáóò Sign ñîîòâåòñòâóþùåé âåðøèíû èìååò çíà÷åíèåtrue, è îòðèöàíèå (BNE äëÿ =, BEQ äëÿ <>, BLT äëÿ >= è ò.ä.),åñëè àòðèáóò Sign èìååò çíà÷åíèå f alse.9.8. Âûäåëåíèå îáùèõ ïîäâûðàæåíèéÂûäåëåíèå îáùèõ ïîäâûðàæåíèé îòíîñèòñÿ ê îáëàñòèîïòèìèçàöèè ïðîãðàìì.  îáùåì ñëó÷àå òðóäíî (èëè äàæå íåâîçìîæíî) ïðîâåñòè ãðàíèöó ìåæäó îïòèìèçàöèåé è¾êà÷åñòâåííîé òðàíñëÿöèåé¿.
Îïòèìèçàöèÿ ýòî è åñòüêà÷åñòâåííàÿ òðàíñëÿöèÿ. Îáû÷íî òåðìèí ¾îïòèìèçàöèÿ¿óïîòðåáëÿþò, êîãäà äëÿ ïîâûøåíèÿ êà÷åñòâà ïðîãðàììûèñïîëüçóþò å¼ ãëóáîêèå ïðåîáðàçîâàíèÿ òàêèå, íàïðèìåð,êàê ïåðåâîä â ãðàôîâóþ ôîðìó äëÿ èçó÷åíèÿ íåòðèâèàëüíûõ ñâîéñòâ ïðîãðàììû. ýòîì ñìûñëå âûäåëåíèå îáùèõ ïîäâûðàæåíèé îäíà èç ïðîñòåéøèõ îïòèìèçàöèé. Äëÿ å¼ îñóùåñòâëåíèÿòðåáóåòñÿ íåêîòîðîå ïðåîáðàçîâàíèå ïðîãðàììû, à èìåííî ïîñòðîåíèå îðèåíòèðîâàííîãî àöèêëè÷åñêîãî ãðàôà, îêîòîðîì ãîâîðèëîñü â ãëàâå, ïîñâÿù¼ííîé ïðîìåæóòî÷íûìïðåäñòàâëåíèÿì.Ëèíåéíûé ó÷àñòîê ýòî ïîñëåäîâàòåëüíîñòü îïåðàòîðîâ, â êîòîðóþ óïðàâëåíèå âõîäèò â íà÷àëå è âûõîäèò âêîíöå áåç îñòàíîâêè è ïåðåõîäà èçíóòðè.Ðàññìîòðèì äåðåâî ëèíåéíîãî ó÷àñòêà, â êîòîðîì âåðøèíàìè ñëóæàò îïåðàöèè, à ïîòîìêàìè îïåðàíäû. Áóäåìãîâîðèòü, ÷òî äâå âåðøèíû îáðàçóþò îáùåå ïîäâûðàæåíèå,9.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
