В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 43
Текст из файла (страница 43)
Âû÷èñëåíèå àòðèáóòîâ ÷èñòîé kâèçèòíîé àòðèáóòíîé ãðàììàòèêèprocedure âèçèò_â_ïîääåðåâî (n, i);{n êîðåíü ïîääåðåâà;i íîìåð âèçèòà â ýòî ïîääåðåâî}{Ïðåäïîëàãàåòñÿ, ÷òî â âåðøèíå nïðèìåíåíî ïðàâèëî âûâîäà p}begin âû÷èñëèòü íåêîòîðûå íàñëåäóåìûå àòðèáóòû Xn;{ýòè àòðèáóòû îïðåäåëÿþòñÿ <nj1 , A> äëÿ íà÷àëà i-ãîâèçèòà â ñîîòâåòñòâóþùåé âû÷èñëèòåëüíîéïîñëåäîâàòåëüíîñòè}âèçèò_â_ïîääåðåâî (n, i);{Xnij ñèìâîë ïðàâîé ÷àñòè ïðàâèëà p}...âèçèò_â_ïîääåðåâî (njl, ijl);âû÷èñëèòü íåêîòîðûå ñèíòåçèðóåìûå àòðèáóòû Xnend;begin for j := 1 to k do âèçèò_â_ïîääåðåâî(r, j){r êîðåíü äåðåâà}end end. çàâèñèìîñòè îò òîãî, êàêèå îãðàíè÷åíèÿ áóäóò íàêëàäûâàòüñÿ íà ïîðÿäîê ïîñåùåíèÿ âåðøèí è âûáîð àòðèáóòîâ, âû÷èñëÿåìûõ íà òîì èëè èíîì âèçèòå, áóäóò ïîëó÷àòüñÿ òå èëè èíûå êëàññû àòðèáóòíûõ ãðàììàòèê.B.7. Íåçàöèêëåííûå àòðèáóòíûå ãðàììàòèêè315B.7.
Àáñîëþòíîíåçàöèêëåííûåàòðèáóòíûå ãðàììàòèêèÎáîçíà÷èì IOx îðèåíòèðîâàííûé ãðàô, âåðøèíàìè êîòîðîãî ÿâëÿþòñÿ àòðèáóòû ñèìâîëà X è èç âåðøèíû b èä¼òäóãà â âåðøèíó a òîãäà è òîëüêî òîãäà, êîãäà â àòðèáóòíîéãðàììàòèêå AG ñóùåñòâóåò òàêîå ïîääåðåâî ñ êîðíåì X ,÷òî â ãðàôå çàâèñèìîñòåé ýòîãî ïîääåðåâà ñóùåñòâóåò ïóòüèç b â a. ×åðåç Dp∗ îáîçíà÷èì ãðàô Dp [IOX1 , ..., IOXnp ].Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ àáñîëþòíî íåçàöèêëåííîé (AN C), åñëè íè îäèí èç ãðàôîâ D íå ñîäåðæèòîðèåíòèðîâàííûõ öèêëîâ [6].Àáñîëþòíî íåçàöèêëåííûå àòðèáóòíûå ãðàììàòèêè îáðàçóþò ñîáñòâåííûé ïîäêëàññ íåçàöèêëåííûõ àòðèáóòíûõãðàììàòèê.Ïðèìåð B.1. Íåçàöèêëåííàÿ àòðèáóòíàÿ ãðàììàòèêà,íå ÿâëÿþùàÿñÿ àáñîëþòíî íåçàöèêëåííîé (ðèñ.
B.1.).SAabxybSAabxy¢A¢ A¢AbbÐèñ. B.1.IO : a b x yD : abxyÝòà ãðàììàòèêà ïîðîæäàåò âñåãî äâà ñëîâà b è bb. Êàæäîå èç äâóõ äåðåâüåâ ïîðîæäàåò íåçàöèêëåííûå ãðàôûçàâèñèìîñòåé, îäíàêî ãðàììàòèêà íå ÿâëÿåòñÿ àáñîëþòíîíåçàöèêëåííîé. Ïðîèñõîäèò ýòî îò òîãî, ÷òî çàâèñèìîñòè,ðåàëèçóåìûå â ðàçíûõ äåðåâüÿõ, ¾íàêëàäûâàþòñÿ¿ íà îäèíãðàô IO.Äëÿ ïîñòðîåíèÿ ãðàôîâ IO èìååòñÿ ïðîñòîé ïîëèíîìèàëüíûé àëãîðèòì:Àëãîðèòì B.3. Ïîñòðîåíèå ãðàôîâ IO àòðèáóòíîéãðàììàòèêè AG.316Ïðèëîæåíèå B.
Àòðèáóòíûå ãðàììàòèêèbegin Ïîëîæèòü IOx := {A(X)}äëÿ êàæäîãî X ∈ N ; {ãðàô áåç äóã}while èìååòñÿ ïðàâèëî p ñ ëåâîé ÷àñòüþ X òàêîå, ÷òî âDp∗ åñòü ïóòü èç i â s, i ∈ I(X),s ∈ S(X), íî â IOx íåò äóãè èç i â sdo äîáàâèòü ýòó äóãó â IOxend end.Ïîñêîëüêó ýòîò àëãîðèòì ïîëèíîìèàëåí è çàäà÷à îïðåäåëåíèÿ íàëè÷èÿ îðèåíòèðîâàííûõ öèêëîâ â ãðàôå òàêæåïîëèíîìèàëüíà, ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà:Òåîðåìà B.9. Çàäà÷à îïðåäåëåíèÿ, ÿâëÿåòñÿ ëè äàííàÿ àòðèáóòíàÿ ãðàììàòèêà àáñîëþòíî íåçàöèêëåííîé, ïîëèíîìèàëüíà ïî äëèíå àòðèáóòíîé ãðàììàòèêè.Àáñîëþòíî íåçàöèêëåííûå àòðèáóòíûå ãðàììàòèêè èíòåðåñíû òåì, ÷òî äëÿ íèõ èìååòñÿ ïîëèíîìèàëüíûé àëãîðèòì ïëàíèðîâàíèÿ âèçèòîâ.Îáîçíà÷èì ÷åðåç A(p) ìíîæåñòâî àòðèáóòîâ ñèìâîëîâñèíòàêñè÷åñêîãî ïðàâèëà p.
Ðàññìîòðèì àòðèáóòèðîâàííîåäåðåâî t â AG è íåêîòîðóþ åãî âíóòðåííþþ âåðøèíó n,â êîòîðîé ïðèìåíåíî ïðàâèëî âûâîäà p.  êàæäûé ìîìåíò âðåìåíè â ïðîöåññå âû÷èñëåíèÿ àòðèáóòîâ äåðåâà têàêèì-ëèáî àëãîðèòìîì âû÷èñëåíèÿ êàêèå-òî àòðèáóòû èçA(p) âû÷èñëåíû, à êàêèå-òî íåò. Íàçîâ¼ì ñîñòîÿíèåì ïðàâèëà, ïðèìåí¼ííîãî â äåðåâå âûâîäà, ìíîæåñòâî âû÷èñëåííûõ àòðèáóòîâ ñèìâîëîâ, âõîäÿùèõ â ýòî ïðàâèëî. Íà÷àëüíûì ñîñòîÿíèåì äëÿ êàæäîãî ïðàâèëà ÿâëÿåòñÿ ìíîæåñòâî{a<k> | Xk ∈ T }.Ïëàí ýòî ïîñëåäîâàòåëüíîñòü èíñòðóêöèé âèäàf pa<k> èëè V ISIT (k, I), ãäå I ⊂ I(Xk ), åñëè k íîìåð ñèìâîëà ïðàâîé ÷àñòè ïðàâèëà p.
I íàçûâàåòñÿ âõîäíûì ìíîæåñòâîì. Ïëàí âñåãäà çàâåðøàåòñÿ èíñòðóêöèåéS(A), A ⊂ A(p) ïåðåâåñòè ïðàâèëî p â ñîñòîÿíèå A. Èíñòðóêöèÿ f pa<k> âû÷èñëÿåò àòðèáóò a<k>, V ISIT (k, I)îñóùåñòâëÿåò âèçèò â ïîääåðåâî k -ãî ñèìâîëà ïðàâîé ÷à-B.7. Íåçàöèêëåííûå àòðèáóòíûå ãðàììàòèêè317ñòè ñî çíà÷åíèÿìè íàñëåäóåìûõ àòðèáóòîâ I ýòîãî ñèìâîëà,èíñòðóêöèÿ S èçìåíÿåò ñîñòîÿíèå ïðàâèëà.Îáîçíà÷èì Dpa<k> ìíîæåñòâî àðãóìåíòîâ ñåìàíòè÷åñêîãî ïðàâèëà f pa<k>. Áóäåì ãîâîðèòü, ÷òî ñåìàíòè÷åñêîå ïðàâèëî f ãîòîâî ê âû÷èñëåíèþ â ñîñòîÿíèè A ïðàâèëàp, åñëè a<k> ∈/ A, íî Dpa<k> ⊂ A.Åñëè p : X0 → X1 ...
Xnp è ïðàâèëî p íàõîäèòñÿ â ñîñòîÿíèè A, òî ðåçóëüòàòîì k -ãî ïîääåðåâà, k ∈ [1, np ], áóäåìíàçûâàòü ìíîæåñòâî {a<k> | a<k> ∈/ A, a ∈ S(Xk ) è äëÿêàæäîãî i<j>, äëÿ êîòîðîãî åñòü äóãà èç i<j> â a<k> âIOXk , i<j> ∈ A} (ïðåäïîëàãàåòñÿ, ÷òî ó êàæäîãî íåòåðìèíàëà åñòü õîòÿ áû îäèí ñèíòåçèðóåìûé àòðèáóò).Ïëàíèðîâàíèå îñóùåñòâëÿåòñÿ íèæåñëåäóþùèì àëãîðèòìîì. Ðåçóëüòàò ðàáîòû àëãîðèòìà çàíîñèòñÿ â äâóìåðíûé ìàññèâ EVAL, îäíèì âõîäîì â êîòîðûé ñëóæèò ñîñòîÿíèå ïðàâèëà, äðóãèì âõîäíîå ìíîæåñòâî. Ñòðîêà ýòîñòðîêà èíñòðóêöèé Stv âåêòîð ñîñòîÿíèé ïðàâèë; îí ïåðåäà¼òñÿ êàê àðãóìåíò ïðîöåäóðå P LAN , çàòåì äóáëèðóåòñÿ âíóòðè ïðîöåäóðû P LAN è îáðàùåíèå ê P LAN ìåíÿåòçíà÷åíèå ñâîåãî àðãóìåíòà â òî÷êå âûçîâà (÷òî îáîçíà÷åíî çíàêîì var ïåðåä ïàðàìåòðîì Stv ïðîöåäóðû P LAN ).Åñëè äëÿ íåêîòîðîãî ýëåìåíòà òàáëèöû EVAL â ïðîöåäóðåP LAN íà÷àòî ïîñòðîåíèå ïëàíà, òî ýòîò ýëåìåíò ìåòèòñÿçíà÷êîì @, ÷òîáû èçáåæàòü áåñêîíå÷íîé ðåêóðñèè.
Áóäåìãîâîðèòü, ÷òî ôóíêöèÿ f ãîòîâà ê âû÷èñëåíèþ, åñëè âñå å¼àðãóìåíòû îïðåäåëåíû, íî àòðèáóò, êîòîðûé îíà âû÷èñëÿåò, íå îïðåäåë¼í.Àëãîðèòì B.4. Ïîñòðîåíèå ïëàíîâ äëÿ êàæäîãî âîçìîæíîãî ñîñòîÿíèÿ êàæäîãî ïðàâèëà.var EVAL : array[ñîñòîÿíèå, âõîäíîå ìíîæåñòâî] of ñòðîêà;St : array [1 .. P ] of ñîñòîÿíèå;{P ÷èñëî ñèíòàêñè÷åñêèõ ïðàâèë}procedure P LAN ( p; I; var Stv);{p íîìåð ñèíòàêñè÷åñêîãî ïðàâèëà, I âõîäíîåìíîæåñòâî; Stv âåêòîð ñîñòîÿíèÿ ïðàâèë}var S : ñòðîêà {ñòðîÿùèéñÿ ïëàí};LStv : array [1 .. p] of ñîñòîÿíèå;318Ïðèëîæåíèå B. Àòðèáóòíûå ãðàììàòèêè{ëîêàëüíûé âåêòîð ñîñòîÿíèÿ ïðàâèë}A : set of àòðèáóò;{ñîñòîÿíèå ïðàâèëà p}stop: boolean;beginif (EVAL [Stv[p], I] ïóñò)thenA := I ∪ Stv[p]; s := ïóñòî ; LStv := Stv;stop := f alse; EVAL [Stv[p], I] :=0 @0 ;repeatif (∃ f pa<k> ãîòîâàÿ ê âû÷èñëåíèþ)thens := s || f pa<k>; A := A + a<k>elseif (∃ ïîääåðåâî k , ðåçóëüòàò Y êîòîðîãî íå ïóñò)thens := s || V ISIT (k, I(Xk ) ∩ A); A := AU Y ;for pi : Xk → u doP LAN (pi , I(Xk ) ∩ A, LStv){â ýòîé òî÷êå ìåíÿåòñÿ çíà÷åíèå LStv[pi ]}endelse stop := trueend enduntil stop;EVAL [Stv[p], I] := s || st(A); Stv := A{Stv[p] ìåíÿåòñÿ â òî÷êå âûçîâà}end end;{òåëî ïðîãðàììû} begin for I := 1 to p doSt[i] := ìíîæåñòâî àòðèáóòîâ òåðìèíàëîâ ïðàâèëà i;P LAN ({}, {}, St)end end.Âû÷èñëåíèå àòðèáóòîâ íà äåðåâå t çàêëþ÷àåòñÿ â âûïîëíåíèè ïîñòðîåííûõ ïëàíîâ â ñîîòâåòñòâèè ñ èçìåíåíèÿìèñîñòîÿíèé ïðàâèë è îñóùåñòâëÿåòñÿ ñëåäóþùåé ïðîãðàììîé:begin êàæäîå ïðàâèëî äåðåâà t ïåðåâåñòèâ íà÷àëüíîå ñîñòîÿíèå,îïðåäåëÿåìîå ìíîæåñòâîì àòðèáóòîâ òåðìèíàëîâ;V ISIT (êîðåíü, {})end.B.8.
Ïðîñòûå ìíîãîâèçèòíûå àòðèáóòíûå ãðàììàòèêè 319B.8. Ïðîñòûå ìíîãîâèçèòíûå àòðèáóòíûå ãðàììàòèêèÀòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ïðîñòîé k âèçèòíîé, åñëè äëÿ êàæäîãî íåòåðìèíàëà X ∈ V ñóùåñòâóåò ðàçáèåíèå A1 (X), ... , Am (X) ìíîæåñòâà àòðèáóòîâA(X), ãäå m ∈ [1, k] è m ìîæåò çàâèñåòü îò X , òî åñòüm = m(X), òàêîå, ÷òî äëÿ ëþáîãî äåðåâà âûâîäà t ñëîâàèç G ñóùåñòâóåò âû÷èñëèòåëüíàÿ ïîñëåäîâàòåëüíîñòü, ïðèêîòîðîé äëÿ ëþáîãî âõîæäåíèÿ X â t âñå àòðèáóòû Aj (X)âû÷èñëÿþòñÿ ïðè âûïîëíåíèè j -ãî âèçèòà â ïîääåðåâî cêîðíåì X äëÿ âñåõ j ∈ [1, m(X)] [7].Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ïðîñòîé ìíîãîâèçèòíîé (SM V ), åñëè îíà ÿâëÿåòñÿ ïðîñòîé k -âèçèòíîé äëÿêàêîãî-íèáóäü k .Ñóùåñòâóþò àáñîëþòíî íåçàöèêëåííûå àòðèáóòíûåãðàììàòèêè, íå ÿâëÿþùèåñÿ ïðîñòûìè ìíîãîâèçèòíûìè.Ïðèìåð B.2.
Çäåñü àòðèáóòû a è b ñèìâîëà A ëåâîãî ïîääåðåâà âû÷èñëÿþòñÿ íà ïåðâîì âèçèòå, à x è y íà âòîðîì. Äëÿ ñèìâîëà A ïðàâîãî ïîääåðåâà íàîáîðîò àòðèáóòû x è y âû÷èñëÿþòñÿ íà ïåðâîì âèçèòå, a è b íàâòîðîì (ðèñ. B.2).S¡@¡¡abxyBabxyA@@C abxyAabxyÐèñ. B.2.Òåîðåìà B.10. Âñÿêàÿ ïðîñòàÿ k -âèçèòíàÿ ãðàììàòèêà ÿâëÿåòñÿ àáñîëþòíî íåçàöèêëåííîé [7].Òåîðåìà B.11.
Çàäà÷à îïðåäåëåíèÿ òîãî, ÿâëÿåòñÿ ëèïðîèçâîëüíàÿ àòðèáóòíàÿ ãðàììàòèêà ïðîñòîé ìíîãîâèçèòíîé, N P -ïîëíà [7]. Ìàëî òîãî, N P -ïîëíà äà-320Ïðèëîæåíèå B. Àòðèáóòíûå ãðàììàòèêèæå çàäà÷à îïðåäåëåíèÿ ïðîñòîé 2-âèçèòíîñòè [7]. Åñëè äëÿ êàæäîãî ñèìâîëà äàíî ðàçáèåíèå åãî àòðèáóòîâïî âèçèòàì, òî àëãîðèòì âû÷èñëåíèÿ àòðèáóòîâ äåðåâà ïðèíèìàåò ñëåäóþùèé âèä:Àëãîðèòì B.5. Âû÷èñëåíèå àòðèáóòîâ â ïðîñòîé ìíîãîâèçèòíîé ãðàììàòèêå.procedure âèçèò_â_ïîääåðåâî(n, i);begin âû÷èñëèòü íàñëåäóåìûå àòðèáóòû I(Xn);âèçèò_â_ïîääåðåâî (nj1, ij1);...âèçèò_â_ïîääåðåâî (njm, ijm);âû÷èñëèòü ñèíòåçèðóåìûå àòðèáóòû S(Xn)end;beginf orj := 1tok(Xr)doâèçèò_â_ïîääåðåâî (r, j){r êîðåíü}end.B.9.
ÎäíîâèçèòíûåãðàììàòèêèàòðèáóòíûåÈíòåðåñíûé ÷àñòíûé ñëó÷àé ïðîñòûõ ìíîãîâèçèòíûõ ãðàììàòèê ïðåäñòàâëÿþò îäíîâèçèòíûå ãðàììàòèêè(IV)[8].Ãðàôîì BG áðàòüåâ ïðàâèëà p áóäåì íàçûâàòü ãðàô,âåðøèíàìè êîòîðîãî ÿâëÿþòñÿ ñèìâîëû ïðàâîé ÷àñòè ïðàâèëà p : X0 → X1 ... Xnp è èç Xi â Xj èä¼ò äóãà òîãäà èòîëüêî òîãäà, êîãäà êàêèå-ëèáî ýëåìåíòû I(Xj ) çàâèñÿò îòêàêèõ-ëèáî ýëåìåíòîâ S(Xi ), i, j ∈ [1, n].Òåîðåìà B.12. Àòðèáóòíàÿ ãðàììàòèêà ÿâëÿåòñÿ îäíîâèçèòíîé òîãäà è òîëüêî òîãäà, êîãäà íè îäèí èçãðàôîâ áðàòüåâ BGp íå ñîäåðæèò îðèåíòèðîâàííûõöèêëîâ [9].B.10.
Ìíîãîïðîõîäíûå ãðàììàòèêè321Èç ýòîé òåîðåìû íåïîñðåäñòâåííî ñëåäóåòÒåîðåìà B.13. Çàäà÷à îïðåäåëåíèÿ òîãî, ÿâëÿåòñÿ ëèïðîèçâîëüíàÿ àòðèáóòíàÿ ãðàììàòèêà îäíîâèçèòíîé,ïîëèíîìèàëüíà.Çàäà÷à ïëàíèðîâàíèÿ âèçèòîâ äëÿ îäíîâèçèòíûõ ãðàììàòèê ñâîäèòñÿ ê íàõîæäåíèþ êàêîãî-íèáóäü ëèíåéíîãîïîðÿäêà áðàòüåâ êàæäîãî ïðàâèëà, óäîâëåòâîðÿþùåãî ÷àñòè÷íîìó ïîðÿäêó, îïðåäåëÿåìîìó ãðàôîì áðàòüåâ BGp.Àëãîðèòì âû÷èñëåíèÿ àòðèáóòîâ äëÿ îäíîâèçèòíûõãðàììàòèê âûãëÿäèò ñëåäóþùèì îáðàçîì:Àëãîðèòì B.6. Âû÷èñëåíèå àòðèáóòîâ â îäíîâèçèòíîéãðàììàòèêå.procedure âèçèò_â_ïîääåðåâî (n);begin âû÷èñëèòü íàñëåäóåìûå àòðèáóòû I(X);â ñîîòâåòñòâèè ñ ëèíåéíûì ïîðÿäêîì ñèìâîëîâïðàâîé ÷àñòè ïðàâèëàdo âèçèò_â_ïîääåðåâî (n);âû÷èñëèòü ñèíòåçèðóåìûå àòðèáóòû S(X)end;begin âèçèò_â_ïîääåðåâî(r) {r êîðåíü}end.B.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
