В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 21
Текст из файла (страница 21)
, vm , ëèáîïðèíàäëåæèò Π, ëèáî ÿâëÿåòñÿ Bk ∈ Γ, ãäå Bâõîäèò â u,(â) åñëè u èìååò áîëåå îäíîãî âõîæäåíèÿ ñèìâîëà B ,òî êàæäûé ñèìâîë Bk âî âñåõ v ñîîòíåñ¼í (âåðõíèì èíäåêñîì) ñ êîíêðåòíûì âõîæäåíèåì B .A → u íàçûâàþò âõîäíûì ïðàâèëîì âûâîäà, Ai ïåðåâîäîì íåòåðìèíàëà A, Ai = vi ýëåìåíòîì ïåðåâîäà,ñâÿçàííûì ñ ýòèì ïðàâèëîì ïåðåâîäà. Åñëè â ÎÑÓ-ñõåìåíåò äâóõ ïðàâèë ïåðåâîäà ñ îäèíàêîâûì âõîäíûì ïðàâèëîì âûâîäà, òî å¼ íàçûâàþò ñåìàíòè÷åñêè îäíîçíà÷íîé.Âûõîä ÎÑÓ-ñõåìû îïðåäåëèì ñíèçó ââåðõ.
Ñ êàæäîéâíóòðåííåé âåðøèíîé n äåðåâà ðàçáîðà (âî âõîäíîé ãðàì-5.2. Ñèíòàêñè÷åñêè óïðàâëÿåìûé ïåðåâîä139ìàòèêå), ïîìå÷åííîé A, ñâÿæåì îäíó öåïî÷êó äëÿ êàæäîãî Ai . Ýòà öåïî÷êà íàçûâàåòñÿ çíà÷åíèåì (èëè ïåðåâîäîì)ñèìâîëà Ai â âåðøèíå n. Êàæäîå çíà÷åíèå âû÷èñëÿåòñÿïîäñòàíîâêîé çíà÷åíèé ñèìâîëîâ ïåðåâîäà äàííîãî ýëåìåíòà ïåðåâîäà Ai = vi , îïðåäåë¼ííûõ â ïðÿìûõ ïîòîìêàõ âåðøèíû n.Ïåðåâîäîì τ (T r), îïðåäåëÿåìûì ÎÑÓ-ñõåìîé T r, íàçîâ¼ì ìíîæåñòâî {(x, y) | x èìååò äåðåâî ðàçáîðà âî âõîäíîéãðàììàòèêå äëÿ T r è y çíà÷åíèå âûäåëåííîãî ñèìâîëàïåðåâîäà Sk â êîðíå ýòîãî äåðåâà}.Ïðèìåð 5.4.
Ðàññìîòðèì ôîðìàëüíîå äèôôåðåíöèðîâàíèåâûðàæåíèé, âêëþ÷àþùèõ êîíñòàíòû 0 è 1, ïåðåìåííóþ x, ôóíêöèè sin è cos , à òàêæå îïåðàöèè ∗ è +. Òàêèå âûðàæåíèÿ ïîðîæäàåò ãðàììàòèêàE →E+T |TT →T ∗F |FF → (E) | sin (E) | cos (E) | x | 0 | 1Ñâÿæåì ñ êàæäûì èç E , T è F äâà ïåðåâîäà, îáîçíà÷åííûõèíäåêñîì 1 è 2.
Èíäåêñ 1 óêàçûâàåò íà òî, ÷òî âûðàæåíèå íåäèôôåðåíöèðîâàíî, 2 ÷òî âûðàæåíèå ïðîäèôôåðåíöèðîâàíî.Ôîðìàëüíàÿ ïðîèçâîäíàÿ ýòî E2 . Çàêîíû äèôôåðåíöèðîâàíèÿ òàêîâû:d(f (x) + g(x)) = df (x) + dg(x)d(f (x) ∗ g(x)) = f (x) ∗ dg(x) + g(x) ∗ df (x)d sin (f (x)) = cos (f (x)) ∗ df (x)d cos (f (x)) = − sin (f (x))df (x)dx = 1d0 = 0d1 = 0Ýòè çàêîíû ìîæíî ðåàëèçîâàòü ñëåäóþùåé ÎÑÓ-ñõåìîé:E →E+TE1 = E1 + T1E2 = E2 + T2E → T E1 = T1E2 = T2T → T ∗ F T 1 = T 1 ∗ F1T2 = T1 ∗ F2 + T2 ∗ F1T → F T 1 = F1T2 = F2140Ãëàâà 5.
Ýëåìåíòû òåîðèè ïåðåâîäà( VLQFRV[[( FRVFRV[VLQ[(( VLQFRV[( FRVFRV[VLQ[ (77 [7 7 VLQFRV[7 FRVFRV[VLQ[ 7)) [) ) VLQFRV[) FRVFRV[VLQ[ )[VLQ FRV ( FRV[( VLQ[(77 FRV[7 VLQ[)) FRV[) VLQ[( [( (77 [7 )) [) [Ðèñ. 5.1.F → (E)F1 = (E1 )F2 = (E2 )F → sin (E)F1 = sin (E1 )F2 = cos (E1 ) ∗ (E2 )5.3. Àòðèáóòíûå ãðàììàòèêè141F → cos (E)F →xF →0F →1F1 = cos (E1 )F2 = − sin (E1 ) ∗ (E2 )F1 = xF2 = 1F1 = 0F2 = 0F1 = 1F2 = 0Äåðåâî âûâîäà äëÿ sin (cos (x)) + x ïðèâåäåíî íà ðèñ. 5.1.5.3.
Àòðèáóòíûå ãðàììàòèêèÑðåäè âñåõ ôîðìàëüíûõ ìåòîäîâ îïèñàíèÿ ÿçûêîâ ïðîãðàììèðîâàíèÿ àòðèáóòíûå ãðàììàòèêè (ââåä¼ííûå Êíóòîì [7]) ïîëó÷èëè, ïî-âèäèìîìó, íàèáîëüøóþ èçâåñòíîñòü èðàñïðîñòðàíåíèå. Ïðè÷èíîé ýòîãî ÿâëÿåòñÿ òî, ÷òî ôîðìàëèçì àòðèáóòíûõ ãðàììàòèê îñíîâûâàåòñÿ íà äåðåâå ðàçáîðà ïðîãðàììû â ÊÑ-ãðàììàòèêå, ÷òî ñáëèæàåò åãî ñ õîðîøîðàçðàáîòàííîé òåîðèåé è ïðàêòèêîé ïîñòðîåíèÿ òðàíñëÿòîðîâ.5.3.1. Îïðåäåëåíèå àòðèáóòíûõ ãðàììàòèêÀòðèáóòíîé ãðàììàòèêîé íàçûâàåòñÿ ÷åòâ¼ðêà AG =(G, AS , AI , R), ãäå(1) G = (N, T, P, S) ïðèâåä¼ííàÿ ÊÑ-ãðàììàòèêà;(2) AS êîíå÷íîå ìíîæåñòâî ñèíòåçèðóåìûõ àòðèáóòîâ;(3) AI êîíå÷íîå ìíîæåñòâî íàñëåäóåìûõ àòðèáóòîâ,AS ∩ AI = ∅;(4) R êîíå÷íîå ìíîæåñòâî ñåìàíòè÷åñêèõ ïðàâèë.Àòðèáóòíàÿ ãðàììàòèêà AG ñîïîñòàâëÿåò êàæäîìó ñèìâîëó X èç N ∪ T ìíîæåñòâî AS (X) ñèíòåçèðóåìûõ àòðèáóòîâ è ìíîæåñòâî AI (X) íàñëåäóåìûõ àòðèáóòîâ.
Ìíîæåñòâî âñåõ ñèíòåçèðóåìûõ àòðèáóòîâ âñåõ ñèìâîëîâ èç N ∪ T142Ãëàâà 5. Ýëåìåíòû òåîðèè ïåðåâîäàîáîçíà÷àåòñÿ AS , íàñëåäóåìûõ AI . Àòðèáóòû ðàçíûõñèìâîëîâ ÿâëÿþòñÿ ðàçëè÷íûìè àòðèáóòàìè. Áóäåì îáîçíà÷àòü àòðèáóò a ñèìâîëà X êàê a(X).
Çíà÷åíèÿ àòðèáóòîâ ìîãóò áûòü ïðîèçâîëüíûõ òèïîâ, íàïðèìåð, ïðåäñòàâëÿòü ñîáîé ÷èñëà, ñòðîêè, àäðåñà ïàìÿòè è ò.ä.Ïóñòü ïðàâèëî p èç P èìååò âèä X0 → X1 X2 . . . Xn . Àòðèáóòíàÿ ãðàììàòèêà AG ñîïîñòàâëÿåò êàæäîìó ïðàâèëó pèç P êîíå÷íîå ìíîæåñòâî R(p) ñåìàíòè÷åñêèõ ïðàâèë âèäàa(Xi ) = f (b(Xj ), c(Xk ), . . . , d(Xm ))ãäå 0 6 j, k, . . .
, m 6 n, ïðè÷¼ì 1 6 i 6 n, åñëè a(Xi ) ∈AI (Xi ) (òî åñòü a(Xi ) íàñëåäóåìûé àòðèáóò), è i = 0, åñëèa(Xi ) ∈ AS (Xi ) (òî åñòü a(Xi ) ñèíòåçèðóåìûé àòðèáóò).Òàêèì îáðàçîì, ñåìàíòè÷åñêîå ïðàâèëî îïðåäåëÿåò çíà÷åíèå àòðèáóòà a ñèìâîëà Xi íà îñíîâå çíà÷åíèé àòðèáóòîâb, c, . . . , d ñèìâîëîâ Xj , Xk , . . . , Xm ñîîòâåòñòâåííî. ÷àñòíîì ñëó÷àå äëèíà n ïðàâîé ÷àñòè ïðàâèëà ìîæåò áûòü ðàâíà íóëþ, òîãäà áóäåì ãîâîðèòü, ÷òî àòðèáóòa ñèìâîëà Xi ¾ïîëó÷àåò â êà÷åñòâå çíà÷åíèÿ êîíñòàíòó¿. äàëüíåéøåì áóäåì ñ÷èòàòü, ÷òî àòðèáóòíàÿ ãðàììàòèêà íå ñîäåðæèò ñåìàíòè÷åñêèõ ïðàâèë äëÿ âû÷èñëåíèÿàòðèáóòîâ òåðìèíàëüíûõ ñèìâîëîâ.
Ïðåäïîëàãàåòñÿ, ÷òîàòðèáóòû òåðìèíàëüíûõ ñèìâîëîâ ëèáî ïðåäîïðåäåë¼ííûå êîíñòàíòû, ëèáî äîñòóïíû êàê ðåçóëüòàò ðàáîòû ëåêñè÷åñêîãî àíàëèçàòîðà.Ïðèìåð 5.5. Ðàññìîòðèì àòðèáóòíóþ ãðàììàòèêó, ïîçâîëÿþùóþ âû÷èñëèòü çíà÷åíèå âåùåñòâåííîãî ÷èñëà, ïðåäñòàâëåííîãî â äåñÿòè÷íîé çàïèñè. Çäåñü N = {N um, Int, F rac},T = {digit, .}, S = N um, à ïðàâèëà âûâîäà è ñåìàíòè÷åñêèåïðàâèëà îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì (âåðõíèå èíäåêñûèñïîëüçóþòñÿ äëÿ ññûëêè íà ðàçíûå âõîæäåíèÿ îäíîãî è òîãîæå íåòåðìèíàëà):N um → Int .
F racv(N um) = v(Int) + v(F rac)p(F rac) = 1Int → ev(Int) = 0p(Int) = 05.3. Àòðèáóòíûå ãðàììàòèêè1432)+ v(Int2 )Int1 → digit Int2v(Int1 ) = v(digit) ∗ 10p(Intp(Int1 ) = p(Int2 ) + 1F rac → ev(F rac) = 0F rac1 → digitF rac2v(F rac1 )= v(digit) ∗ 10−p(F rac ) + v(F rac2 )p(F rac2 )= p(F rac1 ) + 11Äëÿ ýòîé ãðàììàòèêèAS (N um) = {v},AS (Int) = {v, p},AS (F rac) = {v},AI (N um) = ∅,AI (Int) = ∅,AI (F rac) = {p}.Ïóñòü äàíà àòðèáóòíàÿ ãðàììàòèêà AG è öåïî÷êà, ïðèíàäëåæàùàÿ ÿçûêó, îïðåäåëÿåìîìó ñîîòâåòñòâóþùåé G =(N, T, P, S).
Ñîïîñòàâèì ýòîé öåïî÷êå ¾çíà÷åíèå¿ ñëåäóþùèì îáðàçîì. Ïîñòðîèì äåðåâî ðàçáîðà T ýòîé öåïî÷êè âãðàììàòèêå G. Êàæäûé âíóòðåííèé óçåë ýòîãî äåðåâà ïîìå÷àåòñÿ íåòåðìèíàëîì X0 , ñîîòâåòñòâóþùèì ïðèìåíåíèþp-ãî ïðàâèëà ãðàììàòèêè; òàêèì îáðàçîì, ó ýòîãî óçëà áóäåò n íåïîñðåäñòâåííûõ ïîòîìêîâ (ðèñ. 5.2).;;; ;Q Ðèñ. 5.2.Ïóñòü òåïåðü X ìåòêà íåêîòîðîãî óçëà äåðåâà è ïóñòüa àòðèáóò ñèìâîëà X .
Åñëè a ñèíòåçèðóåìûé àòðèáóò,òî X = X0 äëÿ íåêîòîðîãî p ∈ P ; åñëè æå a íàñëåäóåìûéàòðèáóò, òî X = Xj äëÿ íåêîòîðûõ p ∈ P è 1 6 j 6 n. îáîèõ ñëó÷àÿõ äåðåâî ¾â ðàéîíå¿ ýòîãî óçëà èìååò âèä,ïðèâåä¼ííûé íà ðèñ. 5.2. Ïî îïðåäåëåíèþ, àòðèáóò a èìååòâ ýòîì óçëå çíà÷åíèå v , åñëè â ñîîòâåòñòâóþùåì ñåìàíòè÷åñêîì ïðàâèëå144Ãëàâà 5. Ýëåìåíòû òåîðèè ïåðåâîäàa(Xi ) = f (b(Xj ), c(Xk ), . . . , d(Xm ))âñå àòðèáóòû b, c, . . .
, d óæå îïðåäåëåíû è èìåþò â óçëàõ ñìåòêàìè Xj , Xk , . . . , Xm çíà÷åíèÿ vj , vk , . . . , vm ñîîòâåòñòâåííî, à v = f (v1 , v2 , . . . , vm ). Ïðîöåññ âû÷èñëåíèÿ àòðèáóòîâ íà äåðåâå ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà íåëüçÿ áóäåò âû÷èñëèòü áîëüøå íè îäíîãî àòðèáóòà. Âû÷èñëåííûåâ ðåçóëüòàòå àòðèáóòû êîðíÿ äåðåâà ïðåäñòàâëÿþò ñîáîé¾çíà÷åíèå¿, ñîîòâåòñòâóþùåå äàííîìó äåðåâó âûâîäà.Çàìåòèì, ÷òî çíà÷åíèå ñèíòåçèðóåìîãî àòðèáóòà ñèìâîëà â óçëå ñèíòàêñè÷åñêîãî äåðåâà âû÷èñëÿåòñÿ ïî àòðèáóòàì ñèìâîëîâ â ïîòîìêàõ ýòîãî óçëà; çíà÷åíèå íàñëåäóåìîãîàòðèáóòà âû÷èñëÿåòñÿ ïî àòðèáóòàì ¾ðîäèòåëÿ¿ è ¾ñîñåäåé¿.Àòðèáóòû, ñîïîñòàâëåííûå âõîæäåíèÿì ñèìâîëîâ â äåðåâî ðàçáîðà, áóäåì íàçûâàòü âõîæäåíèÿìè àòðèáóòîâ âäåðåâî ðàçáîðà, à äåðåâî ñ ñîïîñòàâëåííûìè êàæäîé âåðøèíå àòðèáóòàìè àòðèáóòèðîâàííûì äåðåâîì ðàçáîðà.Ïðèìåð 5.6.
Àòðèáóòèðîâàííîå äåðåâî äëÿ ãðàììàòèêè èçïðåäûäóùåãî ïðèìåðà è öåïî÷êè w = 12.34 ïîêàçàíî íà ðèñ. 5.3.1XP Y,QWY S GLJLW,QWY GLJLWY )UDFY S ,QWY S Y GLJLW)UDF S Y Y S HÐèñ. 5.3.GLJLWY )UDFHY S 5.3. Àòðèáóòíûå ãðàììàòèêè145Áóäåì ãîâîðèòü, ÷òî ñåìàíòè÷åñêèå ïðàâèëà çàäàíû êîððåêòíî, åñëè îíè ïîçâîëÿþò âû÷èñëèòü âñå àòðèáóòû ïðîèçâîëüíîãî óçëà â ëþáîì äåðåâå âûâîäà.Ìåæäó âõîæäåíèÿìè àòðèáóòîâ â äåðåâî ðàçáîðà ñóùåñòâóþò çàâèñèìîñòè, îïðåäåëÿåìûå ñåìàíòè÷åñêèìè ïðàâèëàìè, ñîîòâåòñòâóþùèìè ïðèìåí¼ííûì ñèíòàêñè÷åñêèìïðàâèëàì.
Ýòè çàâèñèìîñòè ìîãóò áûòü ïðåäñòàâëåíû â âèäå îðèåíòèðîâàííîãî ãðàôà ñëåäóþùèì îáðàçîì.Ïóñòü T äåðåâî ðàçáîðà. Ñîïîñòàâèì ýòîìó äåðåâóîðèåíòèðîâàííûé ãðàô D(T ), óçëàìè êîòîðîãî ÿâëÿþòñÿïàðû (n, a), ãäå n óçåë äåðåâà T , a àòðèáóò ñèìâîëà,ñëóæàùåãî ìåòêîé óçëà n. Ãðàô ñîäåðæèò äóãó èç (n1 , a1 )â (n2 , a2 ) òîãäà è òîëüêî òîãäà, êîãäà ñåìàíòè÷åñêîå ïðàâèëî, âû÷èñëÿþùåå àòðèáóò a2 , íåïîñðåäñòâåííî èñïîëüçóåò çíà÷åíèå àòðèáóòà a1 . Òàêèì îáðàçîì, óçëàìè ãðàôàD(T ) ÿâëÿþòñÿ àòðèáóòû, êîòîðûå íóæíî âû÷èñëèòü, à äóãè îïðåäåëÿþò çàâèñèìîñòè, ïîäðàçóìåâàþùèå, êàêèå àòðèáóòû âû÷èñëÿþòñÿ ðàíüøå, à êàêèå ïîçæå.Ïðèìåð 5.7. Ãðàô çàâèñèìîñòåé àòðèáóòîâ äëÿ äåðåâà ðàçáîðà èç ïðåäûäóùåãî ïðèìåðà ïîêàçàí íà ðèñ. 5.4.Y1XP S1XPY,QW S,QWYGLJLWY,QWS,QWY,QWS,QW YGLJLW Y,QWS,QWYGLJLWY,QWS,QWYGLJLW Y,QWS,QWÐèñ.
5.4.146Ãëàâà 5. Ýëåìåíòû òåîðèè ïåðåâîäàÌîæíî ïîêàçàòü, ÷òî ñåìàíòè÷åñêèå ïðàâèëà ÿâëÿþòñÿêîððåêòíûìè òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãî äåðåâà âûâîäà T ñîîòâåòñòâóþùèé ãðàô D(T ) íå ñîäåðæèòöèêëîâ (òî åñòü ÿâëÿåòñÿ îðèåíòèðîâàííûì àöèêëè÷åñêèìãðàôîì).5.3.2. Êëàññû àòðèáóòíûõ ãðàììàòèê è èõðåàëèçàöèÿ îáùåì âèäå ðåàëèçàöèÿ âû÷èñëèòåëåé äëÿ àòðèáóòíûõ ãðàììàòèê âûçûâàåò çíà÷èòåëüíûå òðóäíîñòè. Ýòîñâÿçàíî ñ òåì, ÷òî ìíîæåñòâî çíà÷åíèé àòðèáóòîâ, ñâÿçàííûõ ñ äàííûì äåðåâîì, ïðèõîäèòñÿ âû÷èñëÿòü â ñîîòâåòñòâèè ñ çàâèñèìîñòÿìè àòðèáóòîâ, êîòîðûå îáðàçóþò îðèåíòèðîâàííûé àöèêëè÷åñêèé ãðàô. Íà ïðàêòèêå ñòàðàþòñÿîñóùåñòâëÿòü ïðîöåññ âû÷èñëåíèÿ àòðèáóòîâ, ïðèâÿçûâàÿåãî ê òîìó èëè èíîìó ñïîñîáó îáõîäà äåðåâà.
Ðàññìàòðèâàþò ìíîãîâèçèòíûå, ìíîãîïðîõîäíûå è äðóãèå àòðèáóòíûåâû÷èñëèòåëè. Ýòî, êàê ïðàâèëî, âåä¼ò ê îãðàíè÷åíèþ äîïóñòèìûõ çàâèñèìîñòåé ìåæäó àòðèáóòàìè, ïîääåðæèâàåìûõâû÷èñëèòåëåì.Ïðîñòåéøèìè ïîäêëàññàìè àòðèáóòíûõ ãðàììàòèê, âû÷èñëåíèÿ âñåõ àòðèáóòîâ äëÿ êîòîðûõ ìîæåò áûòü îñóùåñòâëåíî îäíîâðåìåííî ñ ñèíòàêñè÷åñêèì àíàëèçîì, ÿâëÿþòñÿ S-àòðèáóòíûå è L-àòðèáóòíûå ãðàììàòèêè.Îïðåäåëåíèå. Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ Sàòðèáóòíîé, åñëè îíà ñîäåðæèò òîëüêî ñèíòåçèðóåìûåàòðèáóòû.Íåòðóäíî âèäåòü, ÷òî äëÿ S-àòðèáóòíîé ãðàììàòèêè íàëþáîì äåðåâå ðàçáîðà âñå àòðèáóòû ìîãóò áûòü âû÷èñëåíûçà îäèí îáõîä äåðåâà ñíèçó ââåðõ. Òàêèì îáðàçîì, âû÷èñëåíèå àòðèáóòîâ ìîæíî äåëàòü ïàðàëëåëüíî ñ âîñõîäÿùèìñèíòàêñè÷åñêèì àíàëèçîì, íàïðèìåð, LR(1)-àíàëèçîì.Ïðèìåð 5.8. Ðàññìîòðèì S-àòðèáóòíóþ ãðàììàòèêó äëÿïåðåâîäà àðèôìåòè÷åñêèõ âûðàæåíèé â ÏÎËÈÇ.
Çäåñü àòðèáóòv èìååò ñòðîêîâûé òèï, k îáîçíà÷àåò îïåðàöèþ êîíêàòåíàöèè.5.3. Àòðèáóòíûå ãðàììàòèêè147Ïðàâèëà âûâîäà è ñåìàíòè÷åñêèå ïðàâèëà îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîìE1 → E2 + Tv(E 1 ) = v(E 2 ) k v(T ) k 0 +0E→Tv(E) = v(T )T →T ∗Fv(T 1 ) = v(T 2 ) k v(F ) k 0 ∗0T →Fv(T ) = v(F )F → idv(F ) = v(id)F → (E)v(F ) = v(E)Îïðåäåëåíèå. Àòðèáóòíàÿ ãðàììàòèêà íàçûâàåòñÿ Làòðèáóòíîé, åñëè ëþáîé íàñëåäóåìûé àòðèáóò ëþáîãîñèìâîëà Xj èç ïðàâîé ÷àñòè êàæäîãî ïðàâèëà X0 →X1 X2 . . . Xn ãðàììàòèêè çàâèñèò òîëüêî îò(1) àòðèáóòîâ ñèìâîëîâ X1 , X2 , . . .
, Xj−1 , íàõîäÿùèõñÿ âïðàâèëå ñëåâà îò Xj , è(2) íàñëåäóåìûõ àòðèáóòîâ ñèìâîëà X0 .Çàìåòèì, ÷òî êàæäàÿ S-àòðèáóòíàÿ ãðàììàòèêà ÿâëÿåòñÿ L-àòðèáóòíîé. Âñå àòðèáóòû íà ëþáîì äåðåâå äëÿ Làòðèáóòíîé ãðàììàòèêè ìîãóò áûòü âû÷èñëåíû çà îäèíîáõîä äåðåâà ñâåðõó-âíèç ñëåâà-íàïðàâî. Òàêèì îáðàçîì,âû÷èñëåíèå àòðèáóòîâ ìîæíî îñóùåñòâëÿòü ïàðàëëåëüíîñ íèñõîäÿùèì ñèíòàêñè÷åñêèì àíàëèçîì, íàïðèìåð, LL(1)àíàëèçîì èëè ðåêóðñèâíûì ñïóñêîì. ñëó÷àå ðåêóðñèâíîãî ñïóñêà â êàæäîé ôóíêöèè, ñîîòâåòñòâóþùåé íåòåðìèíàëó, íàäî îïðåäåëèòü ôîðìàëüíûå ïàðàìåòðû, ïåðåäàâàåìûå ïî çíà÷åíèþ, äëÿ íàñëåäóåìûõ àòðèáóòîâ, è ôîðìàëüíûå ïàðàìåòðû, ïåðåäàâàåìûåïî ññûëêå, äëÿ ñèíòåçèðóåìûõ àòðèáóòîâ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
