В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 42
Текст из файла (страница 42)
P.89101, 158165.12. McCarthy J. A formal definition of a subset ofALGOL // Formal Language Description for ComputerProgramming. Proc. IFIP Working Conf. Vienna(1964). P. 112. North Holland, 1966.306Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâ13. McCarthy J., Painter J. Correctness of a compiler forarithmetic expressions // Proc. Sympos. Appl. Math.Vol. 17. Amer. Math. Soc., Providence, R.I., 1967.14. McClure R.M.
TMG A syntax directed compiler //Proc. ACM Nat. Conf. 20 (1965). P. 262274.15. PL/I Definition Group of the Vienna Labratory. FormalDefinition of PL/I. IBM Technical Report TR 25.071(1966).16. Wirth N., Weber H. Euler: A generalization of ALGOL,and its formal definition // Comm. ACM 9 (1966). P.1123, 8999, 878.Ïðèëîæåíèå B.ÀòðèáóòíûåãðàììàòèêèB.1. ÂâåäåíèåÑðåäè âñåõ ôîðìàëüíûõ ìåòîäîâ îïèñàíèÿ ÿçûêîâïðîãðàììèðîâàíèÿ àòðèáóòíûå ãðàììàòèêè ïîëó÷èëè, ïîâèäèìîìó, íàèáîëüøóþ èçâåñòíîñòü è ðàñïðîñòðàíåíèå.Ïðè÷èíîé ýòîãî ÿâëÿåòñÿ òî, ÷òî ôîðìàëèçì àòðèáóòíûõãðàììàòèê îñíîâûâàåòñÿ íà äåðåâå ðàçáîðà ïðîãðàììû âÊÑ-ãðàììàòèêå, ÷òî ñáëèæàåò åãî ñ õîðîøî ðàçðàáîòàííîé òåîðèåé è ïðàêòèêîé ïîñòðîåíèÿ òðàíñëÿòîðîâ.
Âìåñòå ñ òåì âûÿñíèëîñü, ÷òî ðåàëèçàöèÿ âû÷èñëèòåëåé äëÿàòðèáóòíûõ ãðàììàòèê îáùåãî âèäà ñòàëêèâàåòñÿ ñ áîëüøèìè òðóäíîñòÿìè.  ñâÿçè ñ ýòèì áûëî ñäåëàíî ìíîæåñòâîïîïûòîê ðàññìàòðèâàòü òå èëè èíûå êëàññû àòðèáóòíûõãðàììàòèê, îáëàäàþùèìè ¾õîðîøèìè¿ ñâîéñòâàìè. Ê ÷èñëó òàêèõ ñâîéñòâ îòíîñÿòñÿ, ïðåæäå âñåãî, ïðîñòîòà àëãîðèòìà ïðîâåðêè àòðèáóòíîé ãðàììàòèêè íà çàöèêëåííîñòüè ïðîñòîòà àëãîðèòìà âû÷èñëåíèÿ àòðèáóòîâ äëÿ àòðèáóòíûõ ãðàììàòèê äàííîãî êëàññà.
 ïðåäëàãàåìîé ñòàòüå äà¼òñÿ îáçîð ðàáîò, ïîñâÿù¼ííûõ ýòèì âîïðîñàì.308Ïðèëîæåíèå B. Àòðèáóòíûå ãðàììàòèêèB.2. Îïðåäåëåíèå àòðèáóòíûõ ãðàììàòèêÏóñòü G ÊÑ-ãðàììàòèêà: G = (T, N, P, Z), ãäåT, N, P, Z, ñîîòâåòñòâåííî, ìíîæåñòâî òåðìèíàëüíûõ ñèìâîëîâ, íåòåðìèíàëüíûõ ñèìâîëîâ, ìíîæåñòâî ïðàâèë âûâîäà è àêñèîìà ãðàììàòèêè. Ïðàâèëà âûâîäà ÊÑ-ãðàììàòèêèáóäåì çàïèñûâàòü â âèäåp : X0 → X1 ... Xn(p)è áóäåì ïðåäïîëàãàòü, ÷òî G ðåäóöèðîâàííàÿ ÊÑãðàììàòèêà, òî åñòü â íåé íåò íåòåðìèíàëüíûõ ñèìâîëîâ,äëÿ êîòîðûõ íå ñóùåñòâóåò ïîëíîãî äåðåâà âûâîäà, â êîòîðîå âõîäèò ýòîò íåòåðìèíàë.
Ñ êàæäûì ñèìâîëîì X ∈ N ∪Tñâÿæåì ìíîæåñòâî A(X) àòðèáóòîâ ñèìâîëà X . Íåêîòîðûåèç ìíîæåñòâ A(x) ìîãóò áûòü ïóñòû. Çàïèñü a(X) îçíà÷àåò,÷òî a ∈ A(X).Ñ êàæäûì ïðàâèëîì âûâîäà p ∈ P ñâÿæåì ìíîæåñòâîF ñåìàíòè÷åñêèõ ïðàâèë, èìåþùèõ ñëåäóþùóþ ôîðìó:a0 (i0 ) = f pa0 (i0 )(a1 (i1 ), ... , aj (ij )),ãäå ik ∈ [0, np ] íîìåð ñèìâîëà ïðàâèëà p, à ak (ik ) àòðèáóò ñèìâîëà Xik , òî åñòü ak (ik ) ∈ A(Xik ). òàêîì ñëó÷àå áóäåì ãîâîðèòü, ÷òî a0 <i0 > ¾çàâèñèò¿ îò a1 (i1 ), ...
, aj (ij ) èëè ÷òî a0 (i0 ) ¾âû÷èñëÿåòñÿ ïî¿a1 (i1 ), ... , aj (ij ).  ÷àñòíîì ñëó÷àå j ìîæåò áûòü ðàâíî íóëþ, òîãäà áóäåì ãîâîðèòü, ÷òî àòðèáóò a0 (i0 ) ¾ïîëó÷àåò âêà÷åñòâå çíà÷åíèÿ êîíñòàíòó¿.ÊÑ-ãðàììàòèêó, êàæäîìó ñèìâîëó êîòîðîé ñîïîñòàâëåíî ìíîæåñòâî àòðèáóòîâ, à êàæäîìó ïðàâèëó âûâîäà ìíîæåñòâî ñåìàíòè÷åñêèõ ïðàâèë, áóäåì íàçûâàòü àòðèáóòíîé ãðàììàòèêîé (AG).Íàçîâ¼ì àòðèáóò a(X0 ) ñèíòåçèðóåìûì, åñëè îäíîìóèç ïðàâèë âûâîäà p : X0 → X1 ... Xnp ñîïîñòàâëåíîñåìàíòè÷åñêîå ïðàâèëî a(0) = f a(0)(...). Íàçîâ¼ì àòðèáóò a(Xi ) íàñëåäóåìûì, åñëè îäíîìó èç ïðàâèë âûâîäàp : X0 → X1 ...
Xnp ñîïîñòàâëåíî ñåìàíòè÷åñêîå ïðàâèëîa(i) = f a(i)(...), I ∈ [1, np ]. Ìíîæåñòâî ñèíòåçèðóåìûõàòðèáóòîâ ñèìâîëà X îáîçíà÷èì ÷åðåç S(X), íàñëåäóåìûõàòðèáóòîâ ÷åðåç I(X).B.3. Àòðèáóòèðîâàííîå äåðåâî ðàçáîðà309Ïóñòü ïðàâèëó âûâîäà p : X0 → X1 ... Xnp ïðèïèñàíîñåìàíòè÷åñêîå ïðàâèëî a0 (i0 ) = f pa0 (i0 )(a1 (i1 ), ... , aj (ij )).Áåç ñíèæåíèÿ îáùíîñòè áóäåì ñ÷èòàòü, ÷òî ak (ik ) ∈ I(X0 )∪npn = 1S(Xn ), k ∈ [1, j] òî åñòü àòðèáóò ìîæåò çàâèñåòüòîëüêî îò íàñëåäóåìûõ àòðèáóòîâ ñèìâîëà ëåâîé ÷àñòè èñèíòåçèðóåìûõ àòðèáóòîâ ñèìâîëîâ ïðàâîé ÷àñòè (ó ñëîâèåÁîøìàíà). Êðîìå òîãî, áóäåì ñ÷èòàòü, ÷òî çíà÷åíèå àòðèáóòîâ òåðìèíàëüíûõ ñèìâîëîâ êîíñòàíòû, òî åñòü èõ çíà÷åíèÿ îïðåäåëåíû, íî äëÿ íèõ íåò ñåìàíòè÷åñêèõ ïðàâèë,îïðåäåëåÿþùèõ èõ çíà÷åíèÿ.B.3.
Àòðèáóòèðîâàííîå äåðåâî ðàçáîðàÅñëè äàíà àòðèáóòíàÿ ãðàììàòèêà AG è öåïî÷êà, ïðèíàäëåæàùàÿ ÿçûêó, îïðåäåëÿåìîìó G, òî ìîæíî ïîñòðîèòüäåðåâî ðàçáîðà ýòîé öåïî÷êè â ãðàììàòèêå G.  ýòîì äåðåâå êàæäàÿ âåðøèíà ïîìå÷åíà ñèìâîëîì ãðàììàòèêè G.Ïðèïèøåì òåïåðü êàæäîé âåðøèíå ìíîæåñòâî àòðèáóòîâ,ñîïîñòàâëåííûõ ñèìâîëó, êîòîðûì ïîìå÷åíà ýòà âåðøèíà.Àòðèáóòû, ñîïîñòàâëåííûå âõîæäåíèÿì ñèìâîëîâ â äåðåâîðàçáîðà, áóäåì íàçûâàòü âõîæäåíèÿìè àòðèáóòîâ â äåðåâî ðàçáîðà, à äåðåâî ñ ñîïîñòàâëåííûìè êàæäîé âåðøèíåàòðèáóòàìè àòðèáóòèðîâàííûì äåðåâîì ðàçáîðà.Ìåæäó âõîæäåíèÿìè àòðèáóòîâ â äåðåâî ðàçáîðà ñóùåñòâóþò çàâèñèìîñòè, îïðåäåëÿåìûå ñåìàíòè÷åñêèìè ïðàâèëàìè, ñîîòâåòñòâóþùèìè ïðèìåí¼ííûì ñèíòàêñè÷åñêèìïðàâèëàì.Äëÿ êàæäîãî ñèíòàêñè÷åñêîãî ïðàâèëà p ∈ P îïðåäåëèìD(p) ãðàô çàâèñèìîñòåé àòðèáóòîâ ñèìâîëîâ, âõîäÿùèõâ ïðàâèëî p, êàê îðèåíòèðîâàííûé ãðàô, âåðøèíàìè êîòîðîãî ñëóæàò àòðèáóòû ñèìâîëîâ, âõîäÿùèõ â ïðàâèëî p, èâ êîòîðîì èä¼ò äóãà èç âåðøèíû b(i) â âåðøèíó a(j) òîãäàè òîëüêî òîãäà, êîãäà ñèíòàêñè÷åñêîìó ïðàâèëó p ñîïîñòàâëåíî ñåìàíòè÷åñêîå ïðàâèëîa(j) = f pa(j)(...
, b(i), ...), i, j ∈ [0, n].310Ïðèëîæåíèå B. Àòðèáóòíûå ãðàììàòèêèÃðàô çàâèñèìîñòåé D(t) äåðåâà ðàçáîðà t öåïî÷êè, ïðèíàäëåæàùåé ÿçûêó ãðàììàòèêè G, îïðåäåëèì êàê îðèåíòèðîâàííûé ãðàô, ïîëó÷åííûé îáúåäèíåíèåì ãðàôîâ çàâèñèìîñòåé âñåõ ïðèìåí¼ííûõ â t ñèíòàêñè÷åñêèõ ïðàâèë.B.4.
ÍåçàöèêëåííûåãðàììàòèêèàòðèáóòíûåÀòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ í åçàöèêëåííîé, åñëè ãðàôû çàâèñèìîñòåé äåðåâüåâ âñåõ öåïî÷åê, ïðèíàäëåæàùèõ ÿçûêó, îïðåäåëÿåìîìó ãðàììàòèêîé G, íå ñîäåðæàòöèêëîâ, è ç àöèêëåííîé, åñëè ñóùåñòâóåò õîòÿ áû îäíà öåïî÷êà, ïðèíàäëåæàùàÿ ÿçûêó, äëÿ äåðåâà ðàçáîðà êîòîðîéãðàô D(t) ñîäåðæèò îðèåíòèðîâàííûé öèêë.Òåîðåìà B.1. Çàäà÷à îïðåäåëåíèÿ òîãî, ÿâëÿåòñÿ ëèäàííàÿ àòðèáóòíàÿ ãðàììàòèêà çàöèêëåííîé, èìååòýêñïîíåíöèàëüíóþ âðåìåííóþ ñëîæíîñòü, òî åñòü ñóùåñòâóåò êîíñòàíòà c > 0 òàêàÿ, ÷òî ëþáîé àëãîðèòì, ïðîâåðÿþùèé íà çàöèêëåííîñòü ïðîèçâîëüíóþàòðèáóòíóþ ãðàììàòèêó ðàçìåðà n, äîëæåí ðàáîòàòüáîëåå, ÷åì 2cn/log n øàãîâ íà áåñêîíå÷íî áîëüøîì ÷èñëå ãðàììàòèê [1, 2].Êíóòîì [3] áûë ïðåäëîæåí àëãîðèòì ïðîâåðêè àòðèáóòíûõ ãðàììàòèê íà çàöèêëåííîñòü.Ïóñòü D(p) ãðàô çàâèñèìîñòåé àòðèáóòîâ ïðàâèëàâûâîäà p, à Gi ïðîèçâîëüíûé îðèåíòèðîâàííûé ãðàô,âåðøèíàìè êîòîðîãî ñëóæàò àòðèáóòû ñèìâîëà Xi ïðàâîé÷àñòè ïðàâèëà âûâîäà p. Îáîçíà÷èì Dp [G1 , ...
, Gnp ] îðèåíòèðîâàííûé ãðàô, ïîëó÷åííûé èç D(p) äîáàâëåíèåì äóã,èäóùèõ èç b(i) â a(i), åñëè â ãðàôå Gi åñòü äóãà èç b â a. ×åðåç à îáîçíà÷èì ìíîæåñòâî îðèåíòèðîâàííûõ ãðàôîâ ñ âåðøèíàìè àòðèáóòàìè ñèìâîëà X , ÷åðåç Dp [G1 , ... , Gnp ] îðèåíòèðîâàííûé ãðàô, âåðøèíàìè êîòîðîãî ñëóæàò àòðèáóòû ñèìâîëà X â ïðàâèëå âûâîäà p : X0 → X1 ...
Xnp è âêîòîðîì èä¼ò äóãà èç âåðøèíû b â âåðøèíó a òîãäà è òîëüêîòîãäà, êîãäà â Dp [G1 , ... , Gnp ] åñòü ïóòü èç b(0) â a(0).B.5. Ïîñëåäîâàòåëüíîñòè è êîððåêòíîñòü311Àëãîðèòì B.1. (Àëãîðèòì Êíóòà). Ïðîâåðêà àòðèáóòíîé ãðàììàòèêè íà çàöèêëåííîñòü.beginfor X ∈ N do Γx := 0 end;for X ∈ T do Γx := {A(X)} end;{A(X) ãðàô ñî ìíîæåñòâîì âåðøèí-ìíîæåñòâîìàòðèáóòîâ ñèìâîëà X è ïóñòûì ìíîæåñòâîì äóã}finish := false; cycle := false;while (not finish) and (not cycle) doif (∃ p : X0 → X1 ... Xnp ) & (∃ Gi ∈ Γxi , i ∈ [0, np ])òàêèå, ÷òî Dp [G1 ...
Gnp ] ñîäåðæèò öèêëthen cycle := trueelse if (∃ p : X0 → X1 ... Xnp ) & (∃ Gi (Γx , i ∈ [0, np ])òàêèå, ÷òî Dp [G1 ... Gnp ] ∈ Γx0then Γx0 := Γx0 {Dp [G1 ... Gnp ]}else finish := trueend endend end.Òåîðåìà B.2. Àòðèáóòíàÿ ãðàììàòèêà AG íåçàöèêëåíà òîãäà è òîëüêî òîãäà, êîãäà íè îäèí èç ãðàôîâDp [G1 ... Gnp ] íå ñîäåðæèò îðèåíòèðîâàííûõ öèêëîâ,òî åñòü êîãäà àëãîðèòì B.1. çàêàí÷èâàåòñÿ ñî çíà÷åíèåì cycle = f alse.Òåîðåìà B.3. Àëãîðèòì Êíóòà ïðîâåðêè íà çàöèêëåííîñòü àòðèáóòíîé ãðàììàòèêè ðàçìåðà n òðåáóåò âîáùåì ñëó÷àå exp(cn2 ) øàãîâ.B.5. Âû÷èñëèòåëüíûåïîñëåäîâàòåëüíîñòè è êîððåêòíîñòü.Îïðåäåëåíèå âèçèòàÍàçîâ¼ì âû÷èñëèòåëüíîé ïîñëåäîâàòåëüíîñòüþ [4] äëÿäåðåâà âûâîäà t â AG ïîñëåäîâàòåëüíîñòü âèäà:cs = (n1 , A1 )(n2 , A2 )(n2 , A2 ) ...
(nr , Ar ),ãäå 1) nj âíóòðåííÿÿ âåðøèíà t (â ÷àñòíîñòè, êîðåíü);312Ïðèëîæåíèå B. Àòðèáóòíûå ãðàììàòèêè2) åñëè nj #nj + 1, òî nj + 1 îòåö, ñûí èëè áðàò nj ;3) Aj ëèáî ïîäìíîæåñòâî ñèíòåçèðóåìûõ àòðèáóòîânj , ëèáî ïîäìíîæåñòâî íàñëåäóåìûõ àòðèáóòîâ (òî åñòü ëèáî ëèáî Aj ∈ S(Xnj )); Aj ∈ S(Xnj ));4) n1 = nr êîðåíü äåðåâà;5) àòðèáóòû Aj íå çàâèñÿò îò Aj äëÿ i > j ;6) ðàññìîòðèì êàêóþ-ëèáî âíóòðåííþþ âåðøèíó n äåðåâà t.
Òîãäà âû÷èñëèòåëüíóþ ïîñëåäîâàòåëüíîñòü cs ìîæíîçàïèñàòü â ñëåäóþùåì âèäå:cs = u1 (n, B1 )u2 (n, B2 ) ... (n, Bh )uh+1 ,ãäå ïîäïîñëåäîâàòåëüíîñòè u1 ... uh+1 íå ñîäåðæàò ýëåìåíòîâ âèäà (n, A). Òîãäàà) Bj 6 I(Xn ), åñëè j íå÷¼òíî;á) Bj 6 S(Xn ), åñëè j ÷¼òíî; â) Uj ∈ [1, n]; B = A(Xn ) âû÷èñëÿþòñÿ âñå àòðèáóòû êàæäîãî ñèìâîëà X ;ã) Bi ∩ Bj = 0, åñëè i#j âñå àòðèáóòû âû÷èñëÿþòñÿïî îäíîìó ðàçó.ä) ïóñòü cs = cs1 <n, Bj ><n1 , A1 ><n2 , A2 >...<n, Bj+1 >cs2 ; åñëè j íå÷¼òíî (÷¼òíî), òî nj âåðøèíû ïîääåðåâà ñêîðíåì n (âåðøèíû t âíå ïîääåðåâà ñ êîðíåì n).Òàêèì îáðàçîì ïðè âõîäå ¾âíèç¿ â ïîääåðåâî âû÷èñëÿþòñÿ íåêîòîðûå íàñëåäóåìûå àòðèáóòû êîðíÿ ïîääåðåâà,ïðè âîçâðàòå èç ïîääåðåâà âû÷èñëÿþòñÿ íåêîòîðûå ñèíòåçèðóåìûå àòðèáóòû êîðíÿ ïîääåðåâà.Íàçîâ¼ì íåçàöèêëåííóþ àòðèáóòíóþ ãðàììàòèêóê îððåêòíîé, åñëè äëÿ âñÿêîãî å¼ àòðèáóòèðîâàííîãî äåðåâàñóùåñòâóåò âû÷èñëèòåëüíàÿ ïîñëåäîâàòåëüíîñòü.Òåîðåìà B.4.
Íåçàöèêëåííàÿ àòðèáóòíàÿ ãðàììàòèêà êîððåêòíà òîãäà è òîëüêî òîãäà, êîãäà äëÿ êàæäîãîïðàâèëà p : X0 → X1 ... Xnp åñëè a ∈ I(Xi ), i ∈ [1, np ],òî èìååòñÿ â òî÷íîñòè îäíî ñåìàíòè÷åñêîå ïðàâèëî,ñîïîñòàâëåííîå p è îïðåäåëÿþùåå çíà÷åíèå a(Xi ), è åñëè a ∈ S(X0 ), òî èìååòñÿ â òî÷íîñòè îäíî ñåìàíòè÷åñêîå ïðàâèëî, ñîïîñòàâëåííîå p è îïðåäåëÿþùåå çíà÷åíèå a(X0 ).B.6. ×èñòûå ìíîãîâèçèòíûå ãðàììàòèêè313Òåîðåìà B.5. Ñëîæíîñòü ïðîâåðêè íåçàöèêëåííîéàòðèáóòíîé ãðàììàòèêè íà êîððåêòíîñòü ëèíåéíàïî ðàçìåðó àòðèáóòíîé ãðàììàòèêè.Ïóñòü t äåðåâî âûâîäà è n åãî âíóòðåííÿÿ âåðøèíà. Ðàññìîòðèì âû÷èñëèòåëüíóþ ïîñëåäîâàòåëüíîñòü äëÿ tâèäàcs = cs1 <n, B1 >cs2 <n, B2 >cs3 ,ãäå n âõîäèò â cs1 ÷¼òíîå ÷èñëî ðàç, è íå âõîäèò â cs2 .
Ïîñëåäîâàòåëüíîñòü cs2 îáõîäèò ïîääåðåâî ñ êîðíåì n. Áóäåìãîâîðèòü, ÷òî <n, B1 >cs2 <n, B2 > îïðåäåëÿåò âèçèò â ïîääåðåâî ñ êîðíåì n è ÷òî âåðøèíà n â ðåçóëüòàòå ýòîãî âèçèòà ïîñåùàåòñÿ îäèí ðàç. Òàêèì îáðàçîì, åñëè n âõîäèò âcs 2h ðàç, òî n ïîñåùàåòñÿ h ðàç.B.6. ×èñòûå ìíîãîâèçèòíûå ãðàììàòèêèÁóäåì ãîâîðèòü, ÷òî àòðèáóòèðîâàííîå äåðåâî k âèçèòíî, åñëè ñóùåñòâóåò âû÷èñëèòåëüíàÿ ïîñëåäîâàòåëüíîñòü cs äëÿ t òàêàÿ, ÷òî íèêàêàÿ âåðøèíà n èç t íå ïîñåùàåòñÿ áîëåå k ðàç.Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ ÷èñòîé k -âèçèòíîé(P M V ), åñëè êàæäîå àòðèáóòèðîâàííîå äåðåâî âûâîäà t âAG k -âèçèòíî [5, 7].Òåîðåìà B.6.
Äëÿ âñÿêîé êîððåêòíîé àòðèáóòíîéãðàììàòèêè ñóùåñòâóåò k òàêîå, ÷òî ãðàììàòèêàÿâëÿåòñÿ ÷èñòîé k -âèçèòíîé.Íà ñàìîì äåëå ýòî k íå ïðåâîñõîäèò ìàêñèìàëüíîãî ïîâñåì ñèìâîëàì ãðàììàòèêè ÷èñëà ñèíòåçèðóåìûõ èëè íàñëåäóåìûõ àòðèáóòîâ.Ñëåäñòâèåì ýòîãî ÿâëÿþòñÿ äâå ñëåäóþùèå òåîðåìû.Òåîðåìà B.7. Ñëîæíîñòü çàäà÷è îïðåäåëåíèÿ òîãî,ÿâëÿåòñÿ ëè ïðîèçâîëüíàÿ àòðèáóòíàÿ ãðàììàòèêà÷èñòîé k -âèçèòíîé äëÿ êàêîãî-íèáóäü k > 0, ýêñïîíåíöèàëüíà.314Ïðèëîæåíèå B. Àòðèáóòíûå ãðàììàòèêèÝòà çàäà÷à ïðîñòî ñîâïàäàåò ñ çàäà÷åé îïðåäåëåíèÿ êîððåêòíîñòè àòðèáóòíîé ãðàììàòèêè.Òåîðåìà B.8. Ñëîæíîñòü çàäà÷è îïðåäåëåíèÿ òîãî,ÿâëÿåòñÿ ëè ïðîèçâîëüíàÿ àòðèáóòíàÿ ãðàììàòèêà÷èñòîé k -âèçèòíîé äëÿ ôèêñèðîâàííîãî k òàêæå ýêñïîíåíöèàëüíà.Àòðèáóòû âñÿêîãî äåðåâà t ÷èñòîé k -âèçèòíîé àòðèáóòíîé ãðàììàòèêè ìîæíî âû÷èñëèòü ñ ïîìîùüþ ñëåäóþùåãîàëãîðèòìà:Àëãîðèòì B.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
