В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 44
Текст из файла (страница 44)
Ìíîãîïðîõîäíûå ãðàììàòèêèÏóñòü íà ïîñëåäîâàòåëüíîñòü âèçèòîâ íàëîæåíî òàêîåîãðàíè÷åíèå, ÷òîáû îíè îáðàçîâàëè ïîñëåäîâàòåëüíûå îáõîäû äåðåâà ðàçáîðà ëèáî ñâåðõó-âíèç ñëåâà-íàïðàâî, ëèáîñâåðõó-âíèç ñïðàâà-íàëåâî.Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ÷èñòîé k ïðîõîäíîé â îáîèõ íàïðàâëåíèÿõ, åñëè ñóùåñòâóåò òàêàÿïîñëåäîâàòåëüíîñòü èç k îáõîäîâ <d1 ... dl > (êàæäîå di ëèáî ñïðàâà-íàëåâî, ëèáî ñëåâà-íàïðàâî), ÷òî àòðèáóòûëþáîãî äåðåâà âûâîäà ìîãóò áûòü âû÷èñëåíû â ðåçóëüòàòåâûïîëíåíèÿ ýòîé ïîñëåäîâàòåëüíîñòè îáõîäîâ [5].322Ïðèëîæåíèå B. Àòðèáóòíûå ãðàììàòèêèÀòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ÷èñòîé ìíîãîïðîõîäíîé â îáîèõ íàïðàâëåíèÿõ (P BD), åñëè îíà ÿâëÿåòñÿ ÷èñòîé k -ïðîõîäíîé â îáîèõ íàïðàâëåíèÿõ äëÿ êàêîãîíèáóäü k .Ïðèìåð B.3.
Ñóùåñòâóþò àòðèáóòíûå ãðàììàòèêè, íåÿâëÿþùèìèñÿ ÷èñòûìè ìíîãîïðîõîäíûìè íè äëÿ êàêîãî k(Ðèñ. B.3).S¡¡xyzAaA¡@@@BxyzAxyz¡@¡@¡@xyzABxyzaAxyzaÐèñ. B.3.×èñëî íåîáõîäèìûõ ïðîõîäîâ â ýòîì ïðèìåðå çàâèñèòîò ãëóáèíû äåðåâà è ìîæåò áûòü ñêîëü óãîäíî áîëüøèì.Î÷åâèäíî, ÷òî ãðàììàòèêà ïðèìåðà B.1 íå ÿâëÿåòñÿ ÷èñòîé ìíîãîïðîõîäíîé è íåòðóäíî âèäåòü, ÷òî ãðàììàòèêàïðèìåðà B.1 ÿâëÿåòñÿ àáñîëþòíî íåçàöèêëåííîé.Òåîðåìà B.14. Çàäà÷à îïðåäåëåíèÿ òîãî, ÿâëÿåòñÿ ëèïðîèçâîëüíàÿ àòðèáóòíàÿ ãðàììàòèêà ÷èñòîé ìíîãîïðîõîäíîé â îáîèõ íàïðàâëåíèÿõ, çàâèñèò ýêñïîíåíöèàëüíî îò ðàçìåðà àòðèáóòíîé ãðàììàòèêè.B.10.
Ìíîãîïðîõîäíûå ãðàììàòèêè323Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ÷èñòîé k ïðîõîäíîé ñëåâà-íàïðàâî, åñëè àòðèáóòû ëþáîãî äåðåâàâûâîäà â íåé ìîãóò áûòü âû÷èñëåíû çà k îáõîäîâ äåðåâàâûâîäà ñëåâà-íàïðàâî [2, 5].Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ÷èñòîé ìíîãîïðîõîäíîé ñëåâà-íàïðàâî (P LR), åñëè îíà ÿâëÿåòñÿ ÷èñòîé k ïðîõîäíîé ñëåâà-íàïðàâî äëÿ êàêîãî-íèáóäü k .Òåîðåìà B.15. Çàäà÷à îïðåäåëåíèÿ òîãî, ÿâëÿåòñÿ ëèïðîèçâîëüíàÿ àòðèáóòíàÿ ãðàììàòèêà ÷èñòîé ìíîãîïðîõîäíîé ñëåâà-íàïðàâî, çàâèñèò ýêñïîíåíöèàëüíî îòðàçìåðà àòðèáóòíîé ãðàììàòèêè.Ïðèìåð B.4. Ñóùåñòâóþò àòðèáóòíûå ãðàììàòèêè,âû÷èñëÿþùèåñÿ â îáîèõ íàïðàâëåíèÿõ, íî íå âû÷èñëÿþùèåñÿ â îäíîì (ðèñ. B.4).SAxy¡@¡@¡@xyABxy¡@@¡@¡xyABxy babÐèñ. B.4.Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ïðîñòîé k ïðîõîäíîé â îáîèõ íàïðàâëåíèÿõ, åñëè ñóùåñòâóåò òàêàÿïîñëåäîâàòåëüíîñòü îáõîäîâ è òàêîå ðàçáèåíèå àòðèáóòîâA1 (X), .
. . , Am (X), m = m(X), m ∈ [1, k], êàæäîãî ñèìâîëà, ÷òî âñå àòðèáóòû èç ìíîæåñòâà Ai (X) âû÷èñëÿþòñÿ íài-îì ïðîõîäå äåðåâà [5].324Ïðèëîæåíèå B. Àòðèáóòíûå ãðàììàòèêèÀòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ïðîñòîé ìíîãîïðîõîäíîé â îáîèõ íàïðàâëåíèÿõ (SBD), åñëè îíà ÿâëÿåòñÿïðîñòîé k -ïðîõîäíîé â îáîèõ íàïðàâëåíèÿõ äëÿ êàêîãîíèáóäü k .Ãðàììàòèêà ïðèìåðà 9.2 ÿâëÿåòñÿ ïðîñòîé ìíîãîïðîõîäíîé â îáîèõ íàïðàâëåíèÿõ, íî íå ÿâëÿåòñÿ ÷èñòîé ìíîãîïðîõîäíîé ñëåâà-íàïðàâî. Ãðàììàòèêà ïðèìåðà 9.3 ÿâëÿåòñÿ ÷èñòîé ìíîãîïðîõîäíîé ñëåâà-íàïðàâî, íî íå ÿâëÿåòñÿ ïðîñòîé ìíîãîïðîõîäíîé â îáîèõ íàïðàâëåíèÿõ.
Òàê ÷òîìåæäó êëàññàìè P LR è SBD íåò îòíîøåíèÿ âêëþ÷åíèÿ.Òåîðåìà B.16. Çàäà÷à ïðîâåðêè òîãî, ÿâëÿåòñÿ ëèïðîèçâîëüíàÿ àòðèáóòíàÿ ãðàììàòèêà ïðîñòîé k ïðîõîäíîé â îáîèõ íàïðàâëåíèÿõ, ïîëèíîìèàëüíî ñëîæíà [5].Ïðèìåð B.5. Ñóùåñòâóþò ãðàììàòèêè, ÿâëÿþùèåñÿ÷èñòûìè ìíîãîïðîõîäíûìè, íî íå ÿâëÿþùèåñÿ ïðîñòûìèìíîãîïðîõîäíûìè (ðèñ. B.5).SAxy¡@¡@¡@xyABxy¡@@¡@¡a xyAC xyacÐèñ. B.5.Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ïðîñòîé k ïðîõîäíîé ñëåâà-íàïðàâî, åñëè ñóùåñòâóåò òàêîå ðàçáèåíèå àòðèáóòîâ êàæäîãî ñèìâîëà A1 (X), ..., Am (X),m = m(X), m ∈ [1, k], ÷òî âñå àòðèáóòû èç ìíîæåñòâàB.10. Ìíîãîïðîõîäíûå ãðàììàòèêè325Ai (X) âû÷èñëÿþòñÿ íà i-îì îáõîäå äåðåâà ñëåâà-íàïðàâîñâåðõó-âíèç.Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ïðîñòîé ìíîãîïðîõîäíîé ñëåâà-íàïðàâî (SLR), åñëè îíà ÿâëÿåòñÿ ïðîñòîé k ïðîõîäíîé ñëåâà-íàïðàâî äëÿ êàêîãî-íèáóäü k .Ïðèìåð B.6.
Ýòà ãðàììàòèêà ÿâëÿåòñÿ ïðîñòîé îäíîïðîõîäíîé ñïðàâà-íàëåâî, íî íå ÿâëÿåòñÿ ïðîñòîé îäíîïðîõîäíîé ñëåâà-íàïðàâî (ðèñ. B.6).S¡@¡@¡@xyAAxyaaÐèñ. B.6.Áóäåì ãîâîðèòü, ÷òî ìåæäó àòðèáóòàìè a è b èìååòìåñòî îòíîøåíèå prec, åñëè ñóùåñòâóåò ïðàâèëî âûâîäàp : X0 → X1 ... Xnp ñ âõîæäåíèÿìè àòðèáóòîâ a<j> èb<k> òàêîå, ÷òî a<j> èñïîëüçóåòñÿ â êà÷åñòâå àðãóìåíòàïðè âû÷èñëåíèè âõîæäåíèÿ b<k>.Ìåæäó àòðèáóòàìè a è b èìååò ìåñòî îòíîøåíèå L, åñëèaprecb è äëÿ êàæäîãî ïðàâèëà âûâîäà p : X0 → X1 ... Xnpñ âõîæäåíèÿìè àòðèáóòîâ a<j> è b<k> òàêèìè, ÷òî b<k>çàâèñèò îò a<j>, èìååò ìåñòî j<k .Ãðàôîì LR-ïðåäøåñòâîâàíèÿ äëÿ AG íàçîâ¼ì ãðàô,âåðøèíàìè êîòîðîãî ÿâëÿþòñÿ àòðèáóòû âñåõ ñèìâîëîâ AGè èç âåðøèíû a â âåðøèíó b èä¼ò äóãà, òîãäà è òîëüêî òîãäà, êîãäà èìååò ìåñòî îòíîøåíèå aprecb.
Åñëè èìååò ìåñòîîòíîøåíèå aLb, òî äóãà (a, b) ïîìå÷åíà ìåòêîé L, èíà÷å îíàïîìå÷åíà ìåòêîé L. Ïðèâåä¼ì àëãîðèòì ïðîâåðêè ïðèíàäëåæíîñòè êëàññó SLR, êîòîðûé îäíîâðåìåííî ïðîèçâîäèòðàçáèåíèå (åñëè ýòî âîçìîæíî) àòðèáóòîâ êàæäîãî ñèìâîëàïî îáõîäàì.Àëãîðèòì B.7.* Ïîñòðîåíèå ôóíêöèè ïðîõîäîâ pass(a) àòðèáóòîâ ñèìâîëîâ,326Ïðèëîæåíèå B. Àòðèáóòíûå ãðàììàòèêè* äàþùåé ëèáî ìèíèìàëüíûé íîìåð ïðîõîäà, íà êîòîðîì àòðèáóò* ìîæåò áûòü âû÷èñëåí, ëèáî íåîïðåäåëåíî,* åñëè àòðèáóò íå ìîæåò áûòü çàíåñ¼í íè â* îäèí èç ýëåìåíòîâ ðàçáèåíèÿ A(X), aA(X).begin ñòðîèì ãðàô LR ïðåäøåñòâîâàíèÿ äëÿ AG;Ïîëàãàåì COST(a) íåîïðåäåë¼ííîé äëÿ âñåõ âåðøèí a;m := −1; repeat m := m + 1;Ïîëîæèòü COST(a) ðàâíîé m äëÿ âñåõ âåðøèí,äëÿ êîòîðûõ COST(a) íåîïðåäåëåíî;repeat äëÿ âåðøèíû a òàêîé, ÷òî COST(a) = mïîëîæèòü COST(a) íåîïðåäåë¼ííûì;Åñëè ñóùåñòâóåò âåðøèíà b è äóãà (b, a) òàêèå, ÷òî(COST(b) = m) and (B, a) èìååò ìåòêó L)or (COST(b) íåîïðåäåëåíî)until íåëüçÿ íàéòè òàêîé âåðøèíû a,÷òî COST(a) ìîæíî ñäåëàòü íåîïðåäåë¼ííûì;until ëèáî äëÿ âñåõ a COST(a) âû÷èñëåíà,ëèáî íå ñóùåñòâóåò âåðøèíû b òàêîé,÷òî COST(b) = m; äëÿ âñåõ a ∈ Aif (COST(a) îïðåäåëåíî)then pass(a) := COST(a) + 1else pass(a) := íåîïðåäåëåíîendend.Ýòîò àëãîðèòì ëåãêî îáîáùàåòñÿ íà ïðîñòûå ìíîãîïðîõîäíûå â îáîèõ íàïðàâëåíèÿõ àòðèáóòíûå ãðàììàòèêè [5].Ñîâñåì ïðîñòûì ÷àñòíûì ñëó÷àåì LR ìíîãîïðîõîäíûõàòðèáóòíûõ ãðàììàòèê ÿâëÿþòñÿ îäíîïðîõîäíûå àòðèáóòíûå ãðàììàòèêè.Òåîðåìà B.17.
Àòðèáóòíàÿ ãðàììàòèêà ÿâëÿåòñÿLR îäíîïðîõîäíîé òîãäà è òîëüêî òîãäà, êîãäà íè îäèíèç ãðàôîâ áðàòüåâ äëÿ ïðàâèë âûâîäà íå ñîäåðæèò äóãèç X â X äëÿ i > j .B.10. Ìíîãîïðîõîäíûå ãðàììàòèêè327Òàêèì îáðàçîì ìåæäó ðàññìîòðåííûìè êëàññàìè àòðèáóòíûõ ãðàììàòèê èìååò ìåñòî âêëþ÷åíèå, ïîêàçàííîå íàðèñ.
B.7:S¡@@@P BD£ @£@@£SMP LRXVXX £SBDXXXXX1VSLR³³³³³³³³1LR¡¡AN CÐèñ. B.7.328Ïðèëîæåíèå B. Àòðèáóòíûå ãðàììàòèêèËÈÒÅÐÀÒÓÐÀ1. Jazayery M., Ogden W.F., Rounds W.C. TheIntrinsically Exponential Complexity of the CircularityProblem for Attribute Grammars // Comm. ACM. V.18 (1975). P. 697706.2. Engelfriet J., File G. Passes and Pathes of AttributeGrammars // Information and Control.
V. 49 (1981).P. 125169.3. Êíóò Ä. Ñåìàíòèêà êîíòåêñòíî-ñâîáîäíûõ ÿçûêîâ// Ñåìàíòèêà ÿçûêîâ ïðîãðàììèðîâàíèÿ. Ì.: Ìèð,1980.4. Riis H., Skyum S. K-visit Attribute Grammars // Math.System Theory. V. 15 (1981). P. 1728.5. Alblas H. Characterisation of Attribute Evaluation inPasses // Acta Informatica. V. 16 (1981). P. 427464.6. Kennedy K., Warren S.K. Automatic Generation ofEfficient Evaluators for Attribute Grammars // Conf.Record of 3d Symp.
on Principles of ProgrammingLanguages, 1976. P. 3249.7. Engelfriet J., File G. Simple Multi-Visit AttributeGrammars // Journal of Computer and System Sciences.V. 24 (1982). P. 283314.8. Engelfriet J., File G. The formal Power of One-VisitAttribute Grammars // Acta Informatica. V.
16 (1981).P. 275302.9. Bochman G.V. Semantic Evaluation from Left to Right// Comm. ACM. V. 19 (1976). P. 5562.Ïðèëîæåíèå C.Çàäà÷è ïî ðàçäåëàìêíèãèC.2. ßçûêè è èõ ïðåäñòàâëåíèåC.2.1. Àëôàâèòû, öåïî÷êè è ÿçûêè2.1.1. Ïóñòü A = {ab, c} è B = {c, ca} äâà ôîðìàëüíûõÿçûêà íàä àëôàâèòîì {a, b, c}.
Íàéòè ñëåäóþùèå ôîðìàëüíûå ÿçûêè:à) A ∪ B;á) A \ B;â) A2 ;ã) A2 \ B 2 ;ä) AB.C.2.2. Ïðåäñòàâëåíèå ÿçûêîâ2.2.1. Äëÿ ÿçûêà L = {x ∈ {a, b}∗ | |x|a − ÷¼òíîå , |x|b −íå÷¼òíîå} ïîñòðîéòåà) Äåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò;á) Ïî íåìó ðåãóëÿðíîå âûðàæåíèå;â) Ïî ýòîìó âûðàæåíèþ ãðàììàòèêó;ã) Ïî ïîëó÷åííîé ãðàììàòèêå ïåðåéäèòå ïî GN -òåîðåìå êN -àâòîìàòó.330Ïðèëîæåíèå C. Çàäà÷è ïî ðàçäåëàì êíèãèC.2.3. Ãðàììàòèêè2.3.1.
Ïðèíàäëåæèò ëè öåïî÷êà x = abaababb ÿçûêó, ïîðîæäàåìîìó ãðàììàòèêîé ñ ïðàâèëàìè:S → SaSb | ε2.3.2. Ïðèíàäëåæèò ëè öåïî÷êà x = (()())() ÿçûêó, ïîðîæäàåìîìó ãðàììàòèêîé ñ ïðàâèëàìè:S → SA | AA → (S) | ()2.3.3. Ïðèíàäëåæèò ëè öåïî÷êà x = 00011011 ÿçûêó, ïîðîæäàåìîìó ãðàììàòèêîé ñ ïðàâèëàìè:S → SS | AA → 0A1 | S | 012.3.4. Ïðèíàäëåæèò ëè öåïî÷êà x = 0111000 ÿçûêó, ïîðîæäàåìîìó ãðàììàòèêîé ñ ïðàâèëàìè:S → A0B | B1AA → BB | 0B → AA | 12.3.5. Âåðíî ëè ñîîòíîøåíèå a∗ cb∗ ∈ L(G) äëÿ ñëåäóþùåé ãðàììàòèêè G?S → Bab | aDa; A → Dc | cA; B → Sb | b;D → AB | aD.2.3.6. Âåðíî ëè ñîîòíîøåíèå ab∗ c∗ ∈ L(G) äëÿ ñëåäóþùåé ãðàììàòèêè G?S → SAS | A; A → Ac | Da | b; B → DaD;D → ABD | AB.2.3.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
