В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 35
Текст из файла (страница 35)
Âûáîð äåðåâà âûâîäà íàèìåíüøåéñòîèìîñòèT-ãðàììàòèêè, îïèñûâàþùèå ñèñòåìû êîìàíä, îáû÷íîÿâëÿþòñÿ íåîäíîçíà÷íûìè. ×òîáû ñãåíåðèðîâàòü êîä äëÿíåêîòîðîé âõîäíîé öåïî÷êè, íåîáõîäèìî âûáðàòü îäíî èçâîçìîæíûõ äåðåâüåâ âûâîäà. Ýòî äåðåâî äîëæíî ïðåäñòàâëÿòü æåëàåìîå êà÷åñòâî êîäà, íàïðèìåð ðàçìåð êîäà è/èëèâðåìÿ âûïîëíåíèÿ.Äëÿ âûáîðà äåðåâà èç ìíîæåñòâà âñåõ ïîñòðîåííûõ äåðåâüåâ âûâîäà ìîæíî èñïîëüçîâàòü àòðèáóòû ñòîèìîñòè,àòðèáóòíûå ôîðìóëû, âû÷èñëÿþùèå èõ çíà÷åíèÿ, è êðèòå-262Ãëàâà 9. Ãåíåðàöèÿ êîäàðèè ñòîèìîñòè, êîòîðûå îñòàâëÿþò äëÿ êàæäîãî íåòåðìèíàëà åäèíñòâåííîå ïðèìåíèìîå ïðàâèëî.
Àòðèáóòû ñòîèìîñòèñîïîñòàâëÿþòñÿ âñåì íåòåðìèíàëàì, àòðèáóòíûå ôîðìóëû âñåì ïðàâèëàì T-ãðàììàòèêè.Ïðåäïîëîæèì, ÷òî äëÿ âåðøèíû n îáíàðóæåíî ïðèìåíèìîå ïðàâèëîp : A → z0 X1 z1 . . . Xk zk ,ãäå zi ∈ T ∗ äëÿ 0 6 i 6 k è Xj ∈ N äëÿ 1 6 j 6 k . Âåðøèíà n èìååò ïîòîìêîâ n1 , . . . , nk , êîòîðûå ñîîòâåòñòâóþòíåòåðìèíàëàì X1 , .
. . , Xk . Çíà÷åíèÿ àòðèáóòîâ ñòîèìîñòèâû÷èñëÿþòñÿ îáõîäÿ äåðåâî ñíèçó ââåðõ. Âíà÷àëå àòðèáóòû ñòîèìîñòè èíèöèàëèçèðóþòñÿ íåîïðåäåë¼ííûì çíà÷åíèåì UndefinedValue. Ïðåäïîëîæèì, ÷òî çíà÷åíèÿ àòðèáóòîâñòîèìîñòè äëÿ âñåõ ïîòîìêîâ n1 , . . . , nk âåðøèíû n âû÷èñëåíû. Åñëè ïðàâèëó p ñîïîñòàâëåíà ôîðìóëàa(A) = f (b(Xi ), c(Xj ), . . .) äëÿ 1 6 i, j 6 k,òî ïðîèçâîäèòñÿ âû÷èñëåíèå çíà÷åíèÿ àòðèáóòà a íåòåðìèíàëà A â âåðøèíå n. Äëÿ âñåõ ïðèìåí¼ííûõ ïðàâèëèùåòñÿ òàêîå, êîòîðîå äà¼ò ìèíèìàëüíîå çíà÷åíèå ñòîèìîñòè. Îòñóòñòâèå ïðèìåí¼ííûõ ïðàâèë îáîçíà÷àåòñÿ ÷åðåçUndefined, çíà÷åíèå êîòîðîãî ïîëàãàåòñÿ áîëüøèì ëþáîãîîïðåäåë¼ííîãî çíà÷åíèÿ.Äîáàâèì â àëãîðèòì 9.2 ðåàëèçàöèþ àòðèáóòîâ ñòîèìîñòè, ôîðìóë èõ âû÷èñëåíèÿ è êðèòåðèåâ îòáîðà.
Èç àëãîðèòìà ìîæíî èñêëþ÷èòü ïîèñê ïîäâûâîäîâ, ñîîòâåòñòâóþùèõ ïðàâèëàì, äëÿ êîòîðûõ çíà÷åíèå àòðèáóòà ñòîèìîñòèíå îïðåäåëåíî. Ñòðóêòóðà äàííûõ, ïðåäñòàâëÿþùàÿ âåðøèíó äåðåâà, ïðèíèìàåò ñëåäóþùèé âèä:struct Tnode {Tterminal op;Tnode * son[MaxArity];struct * { unsigned CostAttr;Tproduction Production;} nonterm [Tnonterminal];OperatorAttributes ...9.10. Ãåíåðàöèÿ îïòèìàëüíîãî êîäà263Òåëî ïðîöåäóðû PARSE ïðèíèìàåò âèävoid PARSE(Tnode *n){for (i=Arity(n->op);i>=1;i--)PARSE(n->son[i]);for (êàæäîãî A èç N){n->nonterm[A].CostAttr=UndefinedValue;n->nonterm[A].production=Undefined;}for (êàæäîãî ïðàâèëà A->bu èç Pòàêîãî, ÷òî b==n->op)if (MATCHED(n,bu)){Âû÷èñëèòüÀòðèáóòûÑòîèìîñòèÄëÿ(A,n,(A->bu));ÏðîâåðèòüÊðèòåðèéÄëÿ(A,n->nonterm[A].CostAttr);if ((A->bu) ëó÷øå,÷åì ðàíåå îáðàáîòàííîå ïðàâèëî äëÿ A){Ìîäèôèöèðîâàòü(n->nonterm[A].CostAttr);n->nonterm[A].production=(A->bu); }}// Ñîïîñòàâèòü öåïíûå ïðàâèëàwhile (ñóùåñòâóåò ïðàâèëî C->A èç P, êîòîðîåëó÷øå, ÷åì ðàíåå îáðàáîòàííîå ïðàâèëî äëÿ A){Âû÷èñëèòüÀòðèáóòûÑòîèìîñòèÄëÿ(C,n,(C->A));ÏðîâåðèòüÊðèòåðèéÄëÿ(C,n->nonterm[C].CostAttr);if ((C->A) ëó÷øå){Ìîäèôèöèðîâàòü(n->nonterm[C].CostAttr);n->nonterm[C].production=(C->A); }}}Ïðîöåäóðà Âû÷èñëèòüÀòðèáóòûÑòîèìîñòèÄëÿ (A, n,(A → bu)) âû÷èñëÿåò ñòîèìîñòü ïðèìåíåíèÿ ïðàâèëà â äàííîé âåðøèíå äëÿ äàííîãî íåòåðìèíàëà.Ïðîöåäóðà ÏðîâåðèòüÊðèòåðèéÄëÿ(C, n → nonterm[C].CostAttr) îïðåäåëÿåò íàèëó÷øåå ïðàâèëî.Ïðîöåäóðà Ìîäèôèöèðîâàòü(n → nonterm[C].CostAttr)ïîçâîëÿåò õðàíèòü ýòî íàèëó÷øåå çíà÷åíèå â âàðèàíòå.Äåðåâî íàèìåíüøåé ñòîèìîñòè îïðåäåëÿåòñÿ êàê äåðåâî, ñîîòâåòñòâóþùåå ìèíèìàëüíîé ñòîèìîñòè êîðíÿ.
Êî-264Ãëàâà 9. Ãåíåðàöèÿ êîäàãäà âûáðàíî äåðåâî âûâîäà íàèìåíüøåé ñòîèìîñòè, âû÷èñëÿþòñÿ çíà÷åíèÿ àòðèáóòîâ, ñîïîñòàâëåííûõ âåðøèíàì äåðåâà âûâîäà, è ãåíåðèðóþòñÿ ñîîòâåòñòâóþùèå ìàøèííûåêîìàíäû. Âû÷èñëåíèå çíà÷åíèé àòðèáóòîâ, ãåíåðàöèÿ êîäà îñóùåñòâëÿþòñÿ â ïðîöåññå îáõîäà âûáðàííîãî äåðåâàâûâîäà ñâåðõó âíèç, ñëåâà íàïðàâî. Îáõîä âûáðàííîãî äåðåâà âûâîäà âûïîëíÿåòñÿ ïðîöåäóðîé âû÷èñëèòåëÿ àòðèáóòîâ, íà âõîä êîòîðîé ïîñòóïàþò êîðåíü äåðåâà âûðàæåíèÿ è àêñèîìà ãðàììàòèêè.
Ïðîöåäóðà èñïîëüçóåò ïðàâèëîA → z0 X1 z1 . . . Xk zk , ñâÿçàííîå ñ óêàçàííîé âåðøèíîé n,è çàäàííûé íåòåðìèíàë A, ÷òîáû îïðåäåëèòü ñîîòâåòñòâóþùèå èì âåðøèíû n1 , . . . , nk è íåòåðìèíàëû X1 , . . . , Xk .Çàòåì âû÷èñëèòåëü ðåêóðñèâíî îáõîäèò êàæäóþ âåðøèíóni , èìåÿ íà âõîäå íåòåðìèíàë Xi .9.10.4. Àòðèáóòíàÿ ñõåìà äëÿ àëãîðèòìàñîïîñòàâëåíèÿ îáðàçöîâÀëãîðèòìû 9.1 è 9.2 ÿâëÿþòñÿ ¾óíèâåðñàëüíûìè¿ â òîìñìûñëå, ÷òî êîíêðåòíûå ãðàììàòèêè âûðàæåíèé è îáðàçöîâ ÿâëÿþòñÿ, ïî-ñóùåñòâó, ïàðàìåòðàìè ýòèõ àëãîðèòìîâ. òî æå âðåìÿ, äëÿ êàæäîé êîíêðåòíîé ãðàììàòèêè ìîæíî íàïèñàòü ñâîé àëãîðèòì ïîèñêà îáðàçöîâ. Íàïðèìåð, âñëó÷àå íàøåé ãðàììàòèêè âûðàæåíèé è ïðèâåä¼ííûõ íàðèñ.
9.25 îáðàçöîâ àëãîðèòì 9.2 ìîæåò áûòü ïðåäñòàâëåíàòðèáóòíîé ãðàììàòèêîé, ïðèâåä¼ííîé íèæå.Íàñëåäóåìûé àòðèáóò Match ñîäåðæèò óïîðÿäî÷åííûéñïèñîê (âåêòîð) îáðàçöîâ äëÿ ñîïîñòàâëåíèÿ â ïîääåðåâåäàííîé âåðøèíû. Êàæäûé èç îáðàçöîâ èìååò âèä ëèáî <opoplist> (op îïåðàöèÿ â äàííîé âåðøèíå, à oplist ñïèñîê å¼ îïåðàíäîâ), ëèáî ïðåäñòàâëÿåò ñîáîé íåòåðìèíàëN .  ïåðâîì ñëó÷àå oplist ¾ðàñïðåäåëÿåòñÿ¿ ïî ïîòîìêàìâåðøèíû äëÿ äàëüíåéøåãî ñîïîñòàâëåíèÿ. Âî âòîðîì ñëó÷àå ñîïîñòàâëåíèå ñ÷èòàåòñÿ óñïåøíûì, åñëè åñòü ïðàâèëîN → op {P ati }, ãäå w ñîñòîèò èç îáðàçöîâ, óñïåøíî ñîïîñòàâëåííûõ ïîòîìêàì äàííîé âåðøèíû.
 ýòîì ñëó÷àåïî ïîòîìêàì â êà÷åñòâå îáðàçöîâ ðàñïðåäåëÿþòñÿ ýëåìåíòû ïðàâîé ÷àñòè ïðàâèëà. Ýòè äâà ìíîæåñòâà îáðàçöîâ ìî-9.10. Ãåíåðàöèÿ îïòèìàëüíîãî êîäà265ãóò ïåðåñåêàòüñÿ. Ñèíòåçèðóåìûé àòðèáóò Pattern âåêòîð ëîãè÷åñêèõ çíà÷åíèé, äà¼ò ðåçóëüòàò ñîïîñòàâëåíèÿ ïîâåêòîðó-îáðàçöó Match.Òàêèì îáðàçîì, ïðè ñîïîñòàâëåíèè îáðàçöîâ ìîãóòâñòðåòèòüñÿ äâà ñëó÷àÿ:1. Âåêòîð îáðàçöîâ ñîäåðæèò îáðàçåö <op {P ati }>, ãäåop îïåðàöèÿ, ïðèìåí¼ííàÿ â äàííîé âåðøèíå.
Òîãäàðàñïðåäåëÿåì îáðàçöû P ati ïî ïîòîìêàì è ñîïîñòàâëåíèå ïî äàííîìó îáðàçöó ñ÷èòàåì óñïåøíûì (èñòèííûì), åñëè óñïåøíû ñîïîñòàâëåíèÿ ýëåìåíòîâ ýòîãîîáðàçöà ïî âñåì ïîòîìêàì.2. Îáðàçöîì ÿâëÿåòñÿ íåòåðìèíàë N . Òîãäà ðàññìàòðèâàåì âñå ïðàâèëà âèäà N → op {P ati }. Âíîâü ðàñïðåäåëÿåì îáðàçöû P ati ïî ïîòîìêàì è ñîïîñòàâëåíèåñ÷èòàåì óñïåøíûì (èñòèííûì), åñëè óñïåøíû ñîïîñòàâëåíèÿ ïî âñåì ïîòîìêàì.  îáùåì ñëó÷àå óñïåøíûì ìîæåò áûòü ñîïîñòàâëåíèå ïî íåñêîëüêèì îáðàçöàì.Îòìåòèì, ÷òî â îáùåì ñëó÷àå â ïîòîìêè îäíîâðåìåííîïåðåäà¼òñÿ íåñêîëüêî îáðàçöîâ äëÿ ñîïîñòàâëåíèÿ. ïðèâåä¼ííîé íèæå àòðèáóòíîé ñõåìå íå ðàññìàòðèâàþòñÿ ïðàâèëà âûáîðà ïîêðûòèÿ íàèìåíüøåé ñòîèìîñòè(ñì.
ïðåäûäóùèé ðàçäåë). Âûáîð îïòèìàëüíîãî ïîêðûòèÿìîæåò áûòü ñäåëàí åù¼ îäíèì ïðîõîäîì ïî äåðåâó, àíàëîãè÷íî òîìó, êàê ýòî áûëî ñäåëàíî âûøå. Íàïðèìåð, â ïðàâèëå ñ '+' èìååòñÿ íåñêîëüêî îáðàçöîâ äëÿ Reg , íî ðåàëüíîãîâûáîðà îäíîãî èç íèõ íå îñóùåñòâëÿåòñÿ. Êðîìå òîãî, íåóòî÷íåíû íåêîòîðûå äåòàëè ðåàëèçàöèè.  ÷àñòíîñòè, êîíêðåòíûé ñïîñîá ôîðìèðîâàíèÿ âåêòîðîâ Match è Pattern. òåêñòå óïîòðåáëÿåòñÿ òåðìèí ¾äîáàâèòü¿, ÷òî îçíà÷àåòäîáàâëåíèå ê âåêòîðó îáðàçöîâ î÷åðåäíîãî ýëåìåíòà.
Âåêòîðû îáðàçöîâ çàïèñàíû â óãëîâûõ ñêîáêàõ.RULEStat ::= '=' Reg RegSEMANTICS266Ãëàâà 9. Ãåíåðàöèÿ êîäàMatch<2>=<'+' Reg Const>;Match<3>=<Reg>;Pattern<0>[1]=Pattern<2>[1]&Pattern<3>[1].Ýòîìó ïðàâèëó ñîîòâåòñòâóåò îäèí îáðàçåö 2. Ïîýòîìó âêà÷åñòâå îáðàçöîâ ïîòîìêîâ ÷åðåç èõ àòðèáóòû Match ïåðåäàþòñÿ, ñîîòâåòñòâåííî,<'+' Reg Const> è <Reg>.RULEReg ::= '+' Reg RegSEMANTICSif (Match<0> ñîäåðæèò Reg â ïîçèöèè i){Match<2>=<Reg,Reg,Reg>;Match<3>=<Const,Reg,<'@' '+' Reg Const>>;}if (Match<0> ñîäåðæèò îáðàçåö <'+' Reg Const>â ïîçèöèè j){äîáàâèòü Reg ê Match<2> â íåêîòîðîé ïîçèöèè k;äîáàâèòü Const ê Match<3> â íåêîòîðîé ïîçèöèè k;}if (Match<0> ñîäåðæèò îáðàçåö <'+' Reg Const>â ïîçèöèè j)Pattern<0>[j]=Pattern<2>[k]&Pattern<3>[k];if (Match[0] ñîäåðæèò Reg â i-é ïîçèöèè)Pattern<0>[i]=(Pattern<2>[1]&Pattern<3>[1])|(Pattern<2>[2]&Pattern<3>[2])|(Pattern<2>[3]&Pattern<3>[3]).Îáðàçöû, ñîîòâåòñòâóþùèå ýòîìó ïðàâèëó, ñëåäóþùèå:(4) Reg → '+' Reg Const,(5) Reg → '+' Reg Reg ,(6) Reg → '+' Reg '@' '+' Reg Const.Àòðèáóòàì Match âòîðîãî è òðåòüåãî ñèìâîëîâ â êà÷åñòâåîáðàçöîâ ïðè ñîïîñòàâëåíèè ìîãóò áûòü ïåðåäàíû âåêòîðû<Reg, Reg, Reg> è <Const, Reg, <'@' '+' Reg Const>>,ñîîòâåòñòâåííî.
Èç àíàëèçà äðóãèõ ïðàâèë ìîæíî çàêëþ÷èòü, ÷òî ïðè ñîïîñòàâëåíèè îáðàçöîâ ïðåäêîâ ëåâîé ÷àñòè9.10. Ãåíåðàöèÿ îïòèìàëüíîãî êîäà267äàííîãî ïðàâèëà àòðèáóòó Match ñèìâîëà ëåâîé ÷àñòè ìîæåò áûòü ïåðåäàí îáðàçåö <'+' Reg Const> (èç îáðàçöîâ 2,3, 6) èëè îáðàçåö Reg.6WDW0 5HJ!3 W! 5HJ&RQVW0 5HJ&RQVW!! W!5HJ 30 &RQVW! W!5HJ 30 5HJ!3 W!5HJ0 5HJ5HJ5HJ!5HJ3 WWW!#0 5HJ&RQVW!5HJ5HJ!3 IW!&RQVW0 &RQVW5HJ #5HJ&RQVW!!3 WWI!5HJ&RQVW0 5HJ5HJ5HJ5HJ!3 WWWW!5HJ0 5HJ5HJ5HJ!3 WWW!5HJ&RQVW0 &RQVW5HJ5HJ #5HJ&RQVW!!3 WWI!&RQVW#0 5HJ5HJ5HJ5HJ5HJ5HJ!3 WWWWW!&RQVW5HJ0 &RQVW5HJ #5HJ&RQVW!&RQVW!3 IWWI!5HJ0 5HJ&RQVW!5HJ 5HJ&RQVW!!3 WWW!5HJ0 &RQVW5HJ #5HJ&RQVW!&RQVW&RQVW!3 WWIWW!&RQVWÐèñ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
