В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 30
Текст из файла (страница 30)
Áåçïåðåñòðîéêè äåðåâà ýòî îçíà÷àåò, ÷òî åñëè â íåêîòîðîé âåðøèíå äåðåâà ñïðàâà ðàñïîëîæåíî áîëåå ñëîæíîå ïîääåðåâî,òî ñíà÷àëà ñãåíåðèðóåì êîä äëÿ íåãî, à çàòåì óæå äëÿ ëåâîãî ïîääåðåâà.Àëãîðèòì ðàáîòàåò ñëåäóþùèì îáðàçîì. Ñíà÷àëà îñóùåñòâëÿåòñÿ ðàçìåòêà ñèíòàêñè÷åñêîãî äåðåâà ïî ñëåäóþùèì ïðàâèëàì.Ïðàâèëà ðàçìåòêè:1) åñëè âåðøèíà ïðàâûé ëèñò èëè äåðåâî ñîñòîèò èçåäèíñòâåííîé âåðøèíû, ïîìå÷àåì ýòó âåðøèíó ÷èñëîì 1,åñëè âåðøèíà ëåâûé ëèñò, ïîìå÷àåì å¼ 0 (ðèñ.
9.6).RSRSZ[Ðèñ. 9.6.2) åñëè âåðøèíà èìååò ïðÿìûõ ïîòîìêîâ ñ ìåòêàìè l1 èl2 , òî â êà÷åñòâå ìåòêè ýòîé âåðøèíû âûáèðàåì íàèáîëüøååèç ÷èñåë l1 èëè l2 ëèáî ÷èñëî l1 + 1, åñëè l1 = l2 (ðèñ. 9.6.).9.6. Òðàíñëÿöèÿ àðèôìåòè÷åñêèõ âûðàæåíèéR l2¡op@R + 1 ¡l1@l2 R¢A¢ A¢¢AAà) l1 < l2R l1¡op@R ¡l1219R l1 + 1¡op@@@l2 R + 1 R + 1¡l1l2 R¢A¢A¢A¢ A¢ A¢ A¢¢AAá) l1 > l2â) l1 = l2Ðèñ. 9.7.Ýòà ðàçìåòêà ïîçâîëÿåò îïðåäåëèòü, êàêîå èç ïîääåðåâüåâ òðåáóåò áîëüøåãî êîëè÷åñòâà ðåãèñòðîâ äëÿ ñâîåãî âû÷èñëåíèÿ. Äàëåå îñóùåñòâëÿåòñÿ ðàñïðåäåëåíèå ðåãèñòðîâäëÿ ðåçóëüòàòîâ îïåðàöèé ïî ñëåäóþùèì ïðàâèëàì:1) Êîðíþ íàçíà÷àåòñÿ ïåðâûé ðåãèñòð.2) Åñëè ìåòêà ëåâîãî ïîòîìêà ìåíüøå ìåòêè ïðàâîãî, òîëåâîìó ïîòîìêó íàçíà÷àåòñÿ ðåãèñòð íà åäèíèöó áîëüøèé,÷åì ïðåäêó, à ïðàâîìó ñ òåì æå íîìåðîì (ñíà÷àëà âû÷èñëÿåòñÿ ïðàâîå ïîääåðåâî è åãî ðåçóëüòàò ïîìåùàåòñÿ âðåãèñòð R), òàê ÷òî ðåãèñòðû çàíèìàþòñÿ ïîñëåäîâàòåëüíî.
Åñëè æå ìåòêà ëåâîãî ïîòîìêà áîëüøå èëè ðàâíà ìåòêåïðàâîãî ïîòîìêà, òî íàîáîðîò, ïðàâîìó ïîòîìêó íàçíà÷àåòñÿ ðåãèñòð íà åäèíèöó áîëüøèé, ÷åì ïðåäêó, à ëåâîìó ñòåì æå íîìåðîì (ñíà÷àëà âû÷èñëÿåòñÿ ëåâîå ïîääåðåâî èåãî ðåçóëüòàò ïîìåùàåòñÿ â ðåãèñòð R ðèñ. 9.7).Ïîñëå ýòîãî ôîðìèðóåòñÿ êîä ïî ñëåäóþùèì ïðàâèëàì:1) åñëè âåðøèíà ïðàâûé ëèñò ñ ìåòêîé 1, òî åé ñîîòâåòñòâóåò êîäMOVE X, Rãäå R ðåãèñòð, íàçíà÷åííûé ýòîé âåðøèíå, à X àäðåñïåðåìåííîé, ñâÿçàííîé ñ âåðøèíîé (ðèñ. 9.8, á);2) åñëè âåðøèíà âíóòðåííÿÿ è å¼ ëåâûé ïîòîìîê ëèñòñ ìåòêîé 0, òî åé ñîîòâåòñòâóåò êîäÊîä ïðàâîãî ïîääåðåâàOp X, Rãäå R ðåãèñòð, íàçíà÷åííûé ýòîé âåðøèíå, X àäðåñ ïåðåìåííîé, ñâÿçàííîé ñ âåðøèíîé, à Op îïåðàöèÿ, ïðèìåí¼ííàÿ â âåðøèíå (ðèñ. 9.8, à);220Ãëàâà 9.
Ãåíåðàöèÿ êîäà5RSRS5;Z5;[Ðèñ. 9.8.3) åñëè íåïîñðåäñòâåííûå ïîòîìêè âåðøèíû íå ëèñòüÿè ìåòêà ïðàâîé âåðøèíû áîëüøå èëè ðàâíà ìåòêè ëåâîé, òîâåðøèíå ñîîòâåòñòâóåò êîäÊîä ïðàâîãî ïîääåðåâàÊîä ëåâîãî ïîääåðåâàOp R+1, Rãäå R ðåãèñòð, íàçíà÷åííûé âíóòðåííåé âåðøèíå, è îïåðàöèÿ Op, âîîáùå ãîâîðÿ, íå êîììóòàòèâíàÿ (ðèñ. 9.9, á);55RSRS555Z5[Ðèñ. 9.9.4) åñëè íåïîñðåäñòâåííûå ïîòîìêè âåðøèíû íå ëèñòüÿè ìåòêà ïðàâîé âåðøèíû ìåíüøå ìåòêè ëåâîé âåðøèíû, òîâåðøèíå ñîîòâåòñòâóåò êîäÊîä ëåâîãî ïîääåðåâà9.6. Òðàíñëÿöèÿ àðèôìåòè÷åñêèõ âûðàæåíèé221Êîä ïðàâîãî ïîääåðåâàOp R, R+1MOVE R+1, RÏîñëåäíÿÿ êîìàíäà ãåíåðèðóåòñÿ äëÿ òîãî, ÷òîáû ïîëó÷èòüðåçóëüòàò â íóæíîì ðåãèñòðå (â ñëó÷àå êîììóòàòèâíîé îïåðàöèè å¼ îïåðàíäû ìîæíî ïîìåíÿòü ìåñòàìè è èçáåæàòüäîïîëíèòåëüíîé ïåðåñûëêè ðèñ.
9.9, à).Ðàññìîòðèì àòðèáóòíóþ ñõåìó, ðåàëèçóþùóþ ýòè ïðàâèëà ãåíåðàöèè êîäà (äëÿ áîëüøåé íàãëÿäíîñòè âõîäíàÿãðàììàòèêà ñîîòâåòñòâóåò îáû÷íîé èíôèêñíîé çàïèñè, à íåËèäåð-ïðåäñòàâëåíèþ).  ýòîé ñõåìå ãåíåðàöèÿ êîäà ïðîèñõîäèò íå íåïîñðåäñòâåííî â ïðîöåññå îáõîäà äåðåâà, êàêðàíüøå, à èç-çà íåîáõîäèìîñòè ïåðåñòàâëÿòü ïîääåðåâüÿêîä ñòðîèòñÿ â âèäå òåêñòà ñ ïîìîùüþ îïåðàöèè êîíêàòåíàöèè. Ïðàêòè÷åñêè, êîíå÷íî, ýòî íåöåëåñîîáðàçíî: ðàçóìíåå óïðàâëÿòü îáõîäîì äåðåâà íåïîñðåäñòâåííî, îäíàêî äëÿïðîñòîòû ìû áóäåì ïîëüçîâàòüñÿ êîíêàòåíàöèåé.RULEExpr ::= IntExprSEMANTICSReg<1>=1; Code<0>=Code<1>; Left<1>=true.RULEIntExpr ::= IntExpr Op IntExprSEMANTICSLeft<1>=true; Left<3>=false;Label<0>=(Label<1>==Label<3>)? Label<1>+1: Max(Label<1>,Label<3>);Reg<1>=(Label<1> <= Label<3>)? Reg<0>+1: Reg<0>;Reg<3>=(Label<1> <= Label<3>)? Reg<0>: Reg<0>+1;Code<0>=(Label<1>==0)? Code<3> + Code<2>222Ãëàâà 9.
Ãåíåðàöèÿ êîäà+ Code<1> + "," + Reg<0>: (Label<1> < Label<3>)? Code<3> + Code<1> + Code<2> +(Reg<0>+1) + "," + Reg<0>: Code<1> + Code<3> + Code<2> +Reg<0> + "," + (Reg<0>+1)+ "MOVE" + (Reg<0>+1) + "," + Reg<0>.RULEIntExpr ::= IdentSEMANTICSLabel<0>=(Left<0>) ? 0 : 1;Code<0>=(!Left<0>)? "MOVE" + Reg<0> + "," + Val<1>: Val<1>.RULEIntExpr ::= '(' IntExpr ')'SEMANTICSLabel<0>=Label<2>;Reg<2>=Reg<0>;Code<0>=Code<2>.RULEOp ::= '+'SEMANTICSCode<0>="ADD".RULEOp ::= '-'SEMANTICSCode<0>="SUB".RULEOp ::= '*'SEMANTICSCode<0>="MUL".9.6.
Òðàíñëÿöèÿ àðèôìåòè÷åñêèõ âûðàæåíèé223RULEOp ::= '/'SEMANTICSCode<0>="DIV".([SUODEHO ,QW([SU UHJ ODEHO UHJ ODEHO UHJ 2S,QW([SU,QW([SU2S,GHQW$ODEHO ,QW([SU UHJODEHO ODEHO UHJ UHJ ,QW([SU,QW([SU,GHQW%,GHQW&2SODEHO ,QW([SU UHJ,QW([SU ODEHO UHJ 2SODEHO UHJ ,QW([SU,GHQW',QW([SU ODEHO UHJ ,GHQW(Ðèñ. 9.10.Àòðèáóòèðîâàííîå äåðåâî äëÿ âûðàæåíèÿ A*B+C*(D+E)ïðèâåäåíî íà ðèñ. 9.10. Ïðè ýòîì áóäåò ñãåíåðèðîâàí ñëåäóþùèé êîä:MOVEMULMOVEADDMULB,A,E,D,C,R1R1R2R2R2224Ãëàâà 9. Ãåíåðàöèÿ êîäàADD R1, R2MOVE R2, R1Ïðèâåä¼ííàÿ àòðèáóòíàÿ ñõåìà òðåáóåò äâóõ ïðîõîäîâïî äåðåâó âûðàæåíèÿ. Ðàññìîòðèì òåïåðü äðóãóþ àòðèáóòíóþ ñõåìó, â êîòîðîé äîñòàòî÷íî îäíîãî îáõîäà äëÿ ãåíåðàöèÿ ïðîãðàììû äëÿ âûðàæåíèé ñ îïòèìàëüíûì ðàñïðåäåëåíèåì ðåãèñòðîâ [9].Ïóñòü ìû ïðîèçâåëè ðàçìåòêó äåðåâà ðàçáîðà òàê æå,êàê è â ïðåäûäóùåì àëãîðèòìå.
Íàçíà÷åíèå ðåãèñòðîâ áóäåì ïðîèçâîäèòü ñëåäóþùèì îáðàçîì.Ëåâîìó ïîòîìêó âñåãäà íàçíà÷àåòñÿ ðåãèñòð, ðàâíûé åãîìåòêå, à ïðàâîìó åãî ìåòêå, åñëè îíà íå ðàâíà ìåòêå åãîëåâîãî áðàòà, è ìåòêå + 1, åñëè ìåòêè ðàâíû. Ïîñêîëüêóáîëåå ñëîæíîå ïîääåðåâî âñåãäà âû÷èñëÿåòñÿ ðàíüøå áîëåå ïðîñòîãî, åãî ðåãèñòð ðåçóëüòàòà èìååò áîëüøèé íîìåð,÷åì ëþáîé ðåãèñòð, èñïîëüçóåìûé ïðè âû÷èñëåíèè áîëååïðîñòîãî ïîääåðåâà, ÷òî ãàðàíòèðóåò ïðàâèëüíîñòü èñïîëüçîâàíèÿ ðåãèñòðîâ.Ïðèâåä¼ííûå ñîîáðàæåíèÿ ðåàëèçóþòñÿ ñëåäóþùåéàòðèáóòíîé ñõåìîé:RULEExpr ::= IntExprSEMANTICSCode<0>=Code<1>; Left<1>=true.RULEIntExpr ::= IntExpr Op IntExprSEMANTICSLeft<1>=true; Left<3>=false;Label<0>=(Label<1>==Label<3>)? Label<1>+1: Max(Label<1>,Label<3>);Code<0>=(Label<3> > Label<1>)? (Label<1>==0)? Code<3> + Code<2> + Code<1>+ "," + Label<3>9.6.
Òðàíñëÿöèÿ àðèôìåòè÷åñêèõ âûðàæåíèé: Code<3> + Code<1> + Code<2> +Label<1> + "," + Label<3>: (Label<3> < Label<1>)? Code<1> + Code<3> + Code<2> +Label<1> + "," + Label<3> +"MOVE" + Label<3> + "," + Label<1>: // ìåòêè ðàâíûCode<3> + "MOVE" + Label<3> +"," + Label<3>+1 + Code<1> +Code<2> + Label<1> + "," +Label<1>+1.RULEIntExpr ::= IdentSEMANTICSLabel<0>=(Left<0>) ? 0 : 1;Code<0>=(Left<0>) ? Val<1>: "MOVE" + Val<1> + "R1".RULEIntExpr ::= '(' IntExpr ')'SEMANTICSLabel<0>=Label<2>;Code<0>=Code<2>.RULEOp ::= '+'SEMANTICSCode<0>="ADD".RULEOp ::= '-'SEMANTICSCode<0>="SUB".RULEOp ::= '*'SEMANTICS225226Ãëàâà 9.
Ãåíåðàöèÿ êîäàCode<0>="MUL".RULEOp ::= '/'SEMANTICSCode<0>="DIV".Êîìàíäû ïåðåñûëêè òðåáóþòñÿ äëÿ ñîãëàñîâàíèÿ íîìåðîâ ðåãèñòðîâ, â êîòîðûõ îñóùåñòâëÿåòñÿ âûïîëíåíèå îïåðàöèè, ñ ðåãèñòðàìè, â êîòîðûõ äîëæåí áûòü âûäàí ðåçóëüòàò. Ýòî èìååò ñìûñë, êîãäà ýòè ðåãèñòðû ðàçíûå. Ïîëó÷èòüñÿ ýòî ìîæåò èç-çà òîãî, ÷òî ïî ïðèâåä¼ííîé ñõåìåðåçóëüòàò âûïîëíåíèÿ îïåðàöèè âñåãäà íàõîäèòñÿ â ðåãèñòðå ñ íîìåðîì ìåòêè, à ìåòêè ëåâîãî è ïðàâîãî ïîääåðåâüåâ ìîãóò ñîâïàäàòü.Äëÿ âûðàæåíèÿ A*B+C*(D+E) áóäåò ñãåíåðèðîâàí ñëåäóþùèé êîä:MOVE E, R1ADDMULMOVEMOVEMULADDD, R1C, R1R1, R2B, R1A, R1R1, R2 ïðèâåä¼ííûõ àòðèáóòíûõ ñõåìàõ ïðåäïîëàãàëîñü, ÷òîðåãèñòðîâ äîñòàòî÷íî äëÿ òðàíñëÿöèè ëþáîãî âûðàæåíèÿ.Åñëè ýòî íå òàê, ïðèõîäèòñÿ óñëîæíÿòü ñõåìó òðàíñëÿöèèè ïðè íåîáõîäèìîñòè ñáðàñûâàòü ñîäåðæèìîå ðåãèñòðîâ âïàìÿòü (èëè ìàãàçèí).9.7. Òðàíñëÿöèÿ ëîãè÷åñêèõ âûðàæåíèéËîãè÷åñêèå âûðàæåíèÿ, âêëþ÷àþùèå ëîãè÷åñêîå óìíîæåíèå, ëîãè÷åñêîå ñëîæåíèå è îòðèöàíèå, ìîæíî âû÷èñ-9.7.
Òðàíñëÿöèÿ ëîãè÷åñêèõ âûðàæåíèé227ëÿòü êàê íåïîñðåäñòâåííî, èñïîëüçóÿ òàáëèöû èñòèííîñòè,òàê è ñ ïîìîùüþ óñëîâíûõ âûðàæåíèé, îñíîâàííûõ íà ñëåäóþùèõ ïðîñòûõ ïðàâèëàõ:A AND B ýêâèâàëåíòíî if A then B else False,A OR Býêâèâàëåíòíî if A then True else B.Åñëè â êà÷åñòâå êîìïîíåíò âûðàæåíèé ìîãóò âõîäèòüôóíêöèè ñ ïîáî÷íûì ýôôåêòîì, òî, âîîáùå ãîâîðÿ, ðåçóëüòàò âû÷èñëåíèÿ ìîæåò çàâèñåòü îò ñïîñîáà âû÷èñëåíèÿ. Âíåêîòîðûõ ÿçûêàõ ïðîãðàììèðîâàíèÿ íå îãîâàðèâàåòñÿ, êàêèì ñïîñîáîì äîëæíû âû÷èñëÿòüñÿ ëîãè÷åñêèå âûðàæåíèÿ(íàïðèìåð, â Ïàñêàëå), â íåêîòîðûõ òðåáóåòñÿ, ÷òîáû âû÷èñëåíèÿ ïðîèçâîäèëèñü òåì èëè èíûì ñïîñîáîì (íàïðèìåð, â Ìîäóëå-2 òðåáóåòñÿ, ÷òîáû âûðàæåíèÿ âû÷èñëÿëèñüïî ïðèâåä¼ííûì ôîðìóëàì), â íåêîòîðûõ ÿçûêàõ åñòü âîçìîæíîñòü ÿâíî çàäàòü ñïîñîá âû÷èñëåíèÿ (Ñè, Àäà). Âû÷èñëåíèå ëîãè÷åñêèõ âûðàæåíèé íåïîñðåäñòâåííî ïî òàáëèöàì èñòèííîñòè àíàëîãè÷íî âû÷èñëåíèþ àðèôìåòè÷åñêèõâûðàæåíèé, ïîýòîìó ìû íå áóäåì èõ ðàññìàòðèâàòü îòäåëüíî.
Ðàññìîòðèì ïîäðîáíåå ñïîñîá âû÷èñëåíèÿ ñ ïîìîùüþïðèâåä¼ííûõ âûøå ôîðìóë (áóäåì íàçûâàòü åãî ¾âû÷èñëåíèåì ñ óñëîâíûìè ïåðåõîäàìè¿). Èíîãäà òàêîé ñïîñîáðàññìàòðèâàþò êàê îïòèìèçàöèþ âû÷èñëåíèÿ ëîãè÷åñêèõâûðàæåíèé.Ðàññìîòðèì ñëåäóþùóþ àòðèáóòíóþ ãðàììàòèêó ñîâõîäíûì ÿçûêîì ëîãè÷åñêèõ âûðàæåíèé:RULEExpr ::= BoolExprSEMANTICSFalseLab<1>=False; TrueLab<1>=True;Code<0>=Code<1>.RULEBoolExpr ::= BoolExpr 'AND' BoolExprSEMANTICSFalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.228Ãëàâà 9.
Ãåíåðàöèÿ êîäàRULEBoolExpr ::= BoolExpr 'OR' BoolExprSEMANTICSFalseLab<1>=NodeLab<3>; TrueLab<1>=TrueLab<0>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= FSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + FalseLab<0>.RULEBoolExpr ::= TSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + TrueLab<0>.Çäåñü ïðåäïîëàãàåòñÿ, ÷òî âñå âåðøèíû äåðåâà çàíóìåðîâàíû è íîìåð âåðøèíû äà¼ò àòðèáóò NodeLab. Ìåòêè âåðøèí ïåðåäàþòñÿ, êàê ýòî èçîáðàæåíî íà ðèñ. 9.11.7UXH/DE)DOVH/DE)DOVH/DE7UXH/DE$1')DOVH/DE7UXH/DE7UXH/DE)DOVH/DE1RGH/DE7UXH/DE)DOVH/DE25)DOVH/DE7UXH/DE1RGH/DEÐèñ.
9.11.Òàêèì îáðàçîì, êàæäîìó àòðèáóòèðîâàííîìó äåðåâó âýòîé àòðèáóòíîé ãðàììàòèêå ñîïîñòàâëÿåòñÿ êîä, ïîëó÷åííûé â ðåçóëüòàòå îáõîäà äåðåâà ñâåðõó-âíèç ñëåâà-íàïðàâîñëåäóþùèì îáðàçîì. Ïðè âõîäå â âåðøèíó BoolExpr ãåíåðèðóåòñÿ å¼ íîìåð, â âåðøèíå F ãåíåðèðóåòñÿ òåêñò GOTO9.7. Òðàíñëÿöèÿ ëîãè÷åñêèõ âûðàæåíèé229çíà÷åíèå àòðèáóòà FalseLab<0>, â âåðøèíå T GOTO çíà÷åíèå àòðèáóòà TrueLab<0>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
