В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 34
Текст из файла (страница 34)
Ãåíåðàöèÿ îïòèìàëüíîãî êîäà12255MOVE #a,RaMOVE Rb,#x(Ra)Îñíîâíàÿ èäåÿ ïîäõîäà çàêëþ÷àåòñÿ â òîì, ÷òî êàæäàÿêîìàíäà ìàøèíû îïèñûâàåòñÿ â âèäå òàêîãî îáðàçöà. Ðàçëè÷íûå ïîêðûòèÿ äåðåâà ïðîìåæóòî÷íîãî ïðåäñòàâëåíèÿñîîòâåòñòâóþò ðàçëè÷íûì ïîñëåäîâàòåëüíîñòÿì ìàøèííûõêîìàíä.
Çàäà÷à âûáîðà êîìàíä ñîñòîèò â òîì, ÷òîáû âûáðàòü íàèëó÷øèé ñïîñîá ðåàëèçàöèè òîãî èëè èíîãî äåéñòâèÿ èëè ïîñëåäîâàòåëüíîñòè äåéñòâèé, òî åñòü âûáðàòü âíåêîòîðîì ñìûñëå îïòèìàëüíîå ïîêðûòèå.Äëÿ âûáîðà îïòèìàëüíîãî ïîêðûòèÿ áûëî ïðåäëîæåíîíåñêîëüêî èíòåðåñíûõ àëãîðèòìîâ, â ÷àñòíîñòè èñïîëüçóþùèõ äèíàìè÷åñêîå ïðîãðàììèðîâàíèå [14, 16]. Ìû çäåñüðàññìîòðèì àëãîðèòì [15], êîìáèíèðóþùèé âîçìîæíîñòèñèíòàêñè÷åñêîãî àíàëèçà è äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ.  îñíîâó ýòîãî àëãîðèòìà ïîëîæåí ñèíòàêñè÷åñêèéàíàëèç íåîäíîçíà÷íûõ ãðàììàòèê (ìîäèôèöèðîâàííûé àëãîðèòì Êîêà, ßíãåðà è Êàñàìè [18, 19]), ýôôåêòèâíûé âðåàëüíûõ ïðèëîæåíèÿõ. Ýòîò æå ìåòîä ìîæåò áûòü ïðèìåí¼í è òîãäà, êîãäà â êà÷åñòâå ïðîìåæóòî÷íîãî ïðåäñòàâëåíèÿ èñïîëüçóåòñÿ äåðåâî.9.10.2.
Ñèíòàêñè÷åñêèéãðàììàòèêàíàëèçäëÿT-Îáû÷íî êîä ãåíåðèðóåòñÿ èç íåêîòîðîãî ïðîìåæóòî÷íîãî ÿçûêà ñ äîâîëüíî æ¼ñòêîé ñòðóêòóðîé.  ÷àñòíîñòè, äëÿêàæäîé îïåðàöèè èçâåñòíà å¼ ðàçìåðíîñòü, òî åñòü ÷èñëîîïåðàíäîâ, áîëüøåå èëè ðàâíîå 0. Îïåðàöèè çàäàþòñÿ òåðìèíàëüíûìè ñèìâîëàìè, è íàîáîðîò áóäåì ñ÷èòàòü âñåòåðìèíàëüíûå ñèìâîëû çíàêàìè îïåðàöèé. Íàçîâ¼ì ãðàììàòèêè, óäîâëåòâîðÿþùèå ýòèì îãðàíè÷åíèÿì, T-ãðàììàòèêàìè.
Ïðàâàÿ ÷àñòü êàæäîé ïðîäóêöèè â Ò-ãðàììàòèêå åñòü ïðàâèëüíîå ïðåôèêñíîå âûðàæåíèå, êîòîðîå ìîæåòáûòü çàäàíî ñëåäóþùèì îïðåäåëåíèåì:256Ãëàâà 9. Ãåíåðàöèÿ êîäà(1) Îïåðàöèÿ ðàçìåðíîñòè 0 ÿâëÿåòñÿ ïðàâèëüíûì ïðåôèêñíûì âûðàæåíèåì;(2) Íåòåðìèíàë ÿâëÿåòñÿ ïðàâèëüíûì ïðåôèêñíûì âûðàæåíèåì;(3) Ïðåôèêñíîå âûðàæåíèå, íà÷èíàþùååñÿ ñî çíàêà îïåðàöèè ðàçìåðíîñòè n > 0, ÿâëÿåòñÿ ïðàâèëüíûì, åñëèïîñëå çíàêà îïåðàöèè ñëåäóåò n ïðàâèëüíûõ ïðåôèêñíûõ âûðàæåíèé;(4) Íè÷òî äðóãîå íå ÿâëÿåòñÿ ïðàâèëüíûì ïðåôèêñíûìâûðàæåíèåì.Îáðàçöû, ñîîòâåòñòâóþùèå ìàøèííûì êîìàíäàì, çàäàþòñÿ ïðàâèëàìè ãðàììàòèêè (âîîáùå ãîâîðÿ, íåîäíîçíà÷íîé).
Ãåíåðàòîð êîäà àíàëèçèðóåò âõîäíîå ïðåôèêñíîå âûðàæåíèå è ñòðîèò îäíîâðåìåííî âñå âîçìîæíûå äåðåâüÿðàçáîðà. Ïîñëå îêîí÷àíèÿ ðàçáîðà âûáèðàåòñÿ äåðåâî ñíàèìåíüøåé ñòîèìîñòüþ. Çàòåì ïî ýòîìó åäèíñòâåííîìóîïòèìàëüíîìó äåðåâó ãåíåðèðóåòñÿ êîä.Äëÿ T-ãðàììàòèê âñå öåïî÷êè, âûâîäèìûå èç ëþáîãîíåòåðìèíàëà A, ÿâëÿþòñÿ ïðåôèêñíûìè âûðàæåíèÿìè ñôèêñèðîâàííîé àðíîñòüþ îïåðàöèé. Äëèíû âñåõ âûðàæåíèé èç âõîäíîé öåïî÷êè a1 . . .
an ìîæíî ïðåäâàðèòåëüíîâû÷èñëèòü (ïîä äëèíîé âûðàæåíèÿ èìååòñÿ ââèäó äëèíàïîäñòðîêè, íà÷èíàþùåéñÿ ñ ñèìâîëà êîäà îïåðàöèè è çàêàí÷èâàþùåéñÿ ïîñëåäíèì ñèìâîëîì, âõîäÿùèì â âûðàæåíèå äëÿ ýòîé îïåðàöèè). Ïîýòîìó ìîæíî ïðîâåðèòü, ñîïîñòàâèìî ëè íåêîòîðîå ïðàâèëî ñ ïîäöåïî÷êîé ai . . . ak âõîäíîé öåïî÷êè a1 . . . an , ïðîõîäÿ ñëåâà-íàïðàâî ïî ai .
. . ak . ïðîöåññå ïðîõîäà ïî öåïî÷êå ïðåäâàðèòåëüíî âû÷èñëåííûå äëèíû ïðåôèêñíûõ âûðàæåíèé èñïîëüçóþòñÿ äëÿ òîãî,÷òîáû ïåðåéòè îò îäíîãî òåðìèíàëà ê ñëåäóþùåìó òåðìèíàëó, ïðîïóñêàÿ ïîäöåïî÷êè, ñîîòâåòñòâóþùèå íåòåðìèíàëàì ïðàâîé ÷àñòè ïðàâèëà.Öåïíûå ïðàâèëà íå çàâèñÿò îò îïåðàöèé, ñëåäîâàòåëüíî, èõ íåîáõîäèìî ïðîâåðÿòü îòäåëüíî.
Ïðèìåíåíèå îäíîãî öåïíîãî ïðàâèëà ìîæåò çàâèñåòü îò ïðèìåíåíèÿ äðóãîãîöåïíîãî ïðàâèëà. Ñëåäîâàòåëüíî, ïðèìåíåíèå öåïíûõ ïðàâèë íåîáõîäèìî ïðîâåðÿòü äî òåõ ïîð, ïîêà íåëüçÿ ïðèìå-9.10. Ãåíåðàöèÿ îïòèìàëüíîãî êîäà257íèòü íè îäíî èç öåïíûõ ïðàâèë. Ìû ïðåäïîëàãàåì, ÷òî âãðàììàòèêå íåò öèêëîâ â ïðèìåíåíèè öåïíûõ ïðàâèë. Ïîñòðîåíèå âñåõ âàðèàíòîâ àíàëèçà äëÿ T-ãðàììàòèêè äàíîíèæå â àëãîðèòìå 9.1. Òèï Titem â àëãîðèòìå 9.1 íèæåñëóæèò äëÿ îïèñàíèÿ ñèòóàöèé (òî åñòü ïðàâèë âûâîäà èïîçèöèè âíóòðè ïðàâèëà). Òèï Tterminal ýòî òèï òåðìèíàëüíîãî ñèìâîëà ãðàììàòèêè, òèï Tproduction òèï äëÿïðàâèëà âûâîäà.Àëãîðèòì 9.1Tterminal a[n];setofTproduction r[n];int l[n]; // l[i] - äëèíà a[i]-âûðàæåíèÿTitem h;// èñïîëüçóåòñÿ ïðè ïîèñêå ïðàâèë,// ñîïîñòàâèìûõ ñ òåêóùåé ïîäöåïî÷êîé// Ïðåäâàðèòåëüíûå âû÷èñëåíèÿÄëÿ êàæäîé ïîçèöèè i âû÷èñëèòü äëèíóa[i]-âûðàæåíèÿ l[i];// Ðàñïîçíàâàíèå âõîäíîé öåïî÷êèfor (int i=n-1;i>=0;i--){for (êàæäîãî ïðàâèëà A -> a[i] y èç P){j=i+1;if (l[i]>1)// Ïåðâûé òåðìèíàë a[i] óæå óñïåøíî// ñîïîñòàâëåí{h=[A->a[i].y];do// íàéòè a[i]y, ñîïîñòàâèìîå// ñ a[i]..a[i+l[i]-1]{Ïóñòü h==[A->u.Xv];if (X in T)if (X==a[j]) j=j+1; else break;else // X in Nif (èìååòñÿ X->w in r[j]) j=j+l[j];else break;h=[A->uX.v];258Ãëàâà 9.
Ãåíåðàöèÿ êîäà}//ïåðåéòè ê ñëåäóþùåìó ñèìâîëówhile (j!=i+l[i]);} // l[i]>1if (j==i+l[i]) r[i]=r[i] + { (A->a[i]y) }} // for ïî ïðàâèëàì A -> a[i] y// Ñîïîñòàâèòü öåïíûå ïðàâèëàwhile (ñóùåñòâóåò ïðàâèëî C->A èç P òàêîå, ÷òîèìååòñÿ íåêîòîðûé ýëåìåíò (A->w) â r[i]è íåò ýëåìåíòà (C->A) â r[i])r[i]=r[i] + { (C->A) };} // for ïî iÏðîâåðèòü, ïðèíàäëåæèò ëè (S->w) ìíîæåñòâó r[0];Ìíîæåñòâà r[i] èìåþò ðàçìåð O(|P |). Ìîæíî ïîêàçàòü,÷òî àëãîðèòì èìååò âðåìåííóþ è ¼ìêîñòíóþ ñëîæíîñòüO(n).Ðàññìîòðèì âíîâü ïðèìåð ðèñ. 9.24.  ïðåôèêñíîé çàïèñè ïðèâåä¼ííûé ôðàãìåíò ïðîãðàììû çàïèñûâàåòñÿ ñëåäóþùèì îáðàçîì:= + a x + @ + + b y @ + i z 5Íà ðèñ.
9.27 ïðèâåä¼í ðåçóëüòàò ðàáîòû àëãîðèòìà. Ïðàâèëà âû÷èñëåíèÿ ñòîèìîñòè ïðèâåäåíû â ñëåäóþùåì ðàçäåëå. Âñå âîçìîæíûå âûâîäû âõîäíîé öåïî÷êè (âêëþ÷àÿîïòèìàëüíûé) ìîæíî ïîñòðîèòü, èñïîëüçóÿ òàáëèöó l äëèíïðåôèêñíûõ âûðàæåíèé è òàáëèöó r ïðèìåíèìûõ ïðàâèë.Ïóñòü G ýòî T-ãðàììàòèêà. Äëÿ êàæäîé öåïî÷êè zèç L(G) ìîæíî ïîñòðîèòü àáñòðàêòíîå ñèíòàêñè÷åñêîå äåðåâî ñîîòâåòñòâóþùåãî âûðàæåíèÿ (ðèñ. 9.24). Ìû ìîæåìïåðåïèñàòü àëãîðèòì òàê, ÷òîáû îí ïðèíèìàë íà âõîäå àáñòðàêòíîå ñèíòàêñè÷åñêîå äåðåâî âûðàæåíèÿ, à íå öåïî÷êó.Ýòîò âàðèàíò àëãîðèòìà ïðèâåä¼í íèæå.  ýòîì àëãîðèòìåäåðåâî âûðàæåíèÿ îáõîäèòñÿ ñâåðõó âíèç è â í¼ì èùóòñÿ ïîääåðåâüÿ, ñîïîñòàâèìûå ñ ïðàâûìè ÷àñòÿìè ïðàâèëèç G.
Îáõîä äåðåâà îñóùåñòâëÿåòñÿ ïðîöåäóðîé PARSE. Ïîñëå îáõîäà ïîääåðåâà äàííîé âåðøèíû â íåé ïðèìåíÿåòñÿïðîöåäóðà MATCHED, êîòîðàÿ ïûòàåòñÿ íàéòè âñå îáðàçöû,9.10. Ãåíåðàöèÿ îïòèìàëüíîãî êîäàÎïåðàöèÿ=+ax+@++by@+iz5Äëèíà15311119831143111259Ïðàâèëà (ñòîèìîñòü)2(22)4(5)5(6)1(2)1(2)4(16) 5(17)7(11)5(13) 6(11)4(5)5(6)1(2)1(2)7(7)3(6)4(5)5(6)1(2)1(2)1(2)Ðèñ. 9.27.ñîïîñòàâèìûå ïîääåðåâó äàííîé âåðøèíû. Äëÿ ýòîãî êàæäîå ïðàâèëî-îáðàçåö ðàçáèâàåòñÿ íà êîìïîíåíòû â ñîîòâåòñòâèè ñ âñòðå÷àþùèìèñÿ â í¼ì îïåðàöèÿìè. Äåðåâî îáõîäèòñÿ ñïðàâà íàëåâî òîëüêî äëÿ òîãî, ÷òîáû èìåòü ñîîòâåòñòâèå ñ ïîðÿäêîì âû÷èñëåíèÿ â àëãîðèòìå 9.1.
Î÷åâèäíî,÷òî ìîæíî îáõîäèòü äåðåâî âûâîäà è ñëåâà íàïðàâî.Ñòðóêòóðà äàííûõ, ïðåäñòàâëÿþùàÿ âåðøèíó äåðåâà,èìååò ñëåäóþùóþ ôîðìó:struct Tnode {Tterminal op;Tnode * son[MaxArity];setofTproduction RULEs;}; êîììåíòàðèÿõ óêàçàíû ñîîòâåòñòâóþùèå ôðàãìåíòûàëãîðèòìà 9.1.260Ãëàâà 9. Ãåíåðàöèÿ êîäàÀëãîðèòì 9.2Tnode * root;bool MATCHED(Tnode * n, Titem h){ bool matching;ïóñòü h==Xv, v== v_1 v_2 ... v_m, m=Arity(X);if (X in T)// ñîïîñòàâëåíèå ïðàâèëàif (m==0) // if l[i]==1if (X==n->op) //if X==a[j]return(true);elsereturn(false);else // if l[i]>1if (X==n->op) //if X==a[j]{matching=true;for (i=1;i<=m;i++) //j=j+l[j]matching=matching && // while (j==i+l[i])MATCHED(n->son[i-1],v_i);return(matching); //h=[A->uX.v]}elsereturn(false);else // X in N ïîèñê ïîäâûâîäàif (â n^.RULEs èìååòñÿ ïðàâèëîñ ëåâîé ÷àñòüþ X)return(true);elsereturn(false);}void PARSE(Tnode * n){for (i=Arity(n->op);i>=1;i--)// for (i=n; i>=1;i--)PARSE(n->son[i-1]);n->RULEs=EMPTY;9.10.
Ãåíåðàöèÿ îïòèìàëüíîãî êîäà261for (êàæäîãî ïðàâèëà A->bu èç P òàêîãî,÷òî b==n->op)if (MATCHED(n,bu)) // if (j==i+l[i])n->RULEs=n->RULEs+{(A->bu)};// Ñîïîñòàâëåíèå öåïíûõ ïðàâèëwhile (ñóùåñòâóåò ïðàâèëî C->A èç P òàêîå, ÷òîíåêîòîðûé ýëåìåíò (A->w) â n->RULEsè íåò ýëåìåíòà(C->A) â n->RULEs)n->RULEs=n->RULEs+{(C->A)};}Îñíîâíàÿ ïðîãðàììà//Ïðåäâàðèòåëüíûå âû÷èñëåíèÿÏîñòðîèòü äåðåâî âûðàæåíèÿ äëÿ âõîäíîé öåïî÷êè z;root = óêàçàòåëü äåðåâà âûðàæåíèÿ;//Ðàñïîçíàòü âõîäíóþ öåïî÷êóPARSE(root);Ïðîâåðèòü, âõîäèò ëè âî ìíîæåñòâî root->RULEsïðàâèëî ñ ëåâîé ÷àñòüþ S;Âûõîäîì àëãîðèòìà ÿâëÿåòñÿ äåðåâî âûðàæåíèÿ äëÿ z ,âåðøèíàì êîòîðîãî ñîïîñòàâëåíû ïðèìåíèìûå ïðàâèëà. Ñïîìîùüþ òàêîãî äåðåâà ìîæíî ïîñòðîèòü âñå âûâîäû äëÿèñõîäíîãî ïðåôèêñíîãî âûðàæåíèÿ.9.10.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
