В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 38
Текст из файла (страница 38)
Ñ êàæäûì ñèìâîëîì X ∈ V ñâÿçûâàåòñÿ êîíå÷íîå ìíî-A.2. Ôîðìàëüíûå ñâîéñòâà283æåñòâî àòðèáóòîâ A(X). A(X) ðàçáèâàåòñÿ íà äâà íåïåðåñåêàþùèõñÿ ìíîæåñòâà: ìíîæåñòâî ñèíòåçèðîâàííûõ àòðèáóòîâ A0 (X) è ìíîæåñòâî óíàñëåäîâàííûõ àòðèáóòîâ A1 (X).Ìíîæåñòâî A1 (S) äîëæíî áûòü ïóñòûì (òî åñòü íà÷àëüíûé ñèìâîë S íå äîëæåí èìåòü óíàñëåäîâàííûõ àòðèáóòîâ);àíàëîãè÷íî, ìíîæåñòâî A0 (X) ïóñòî, åñëè X òåðìèíàëüíûé ñèìâîë. Êàæäûé àòðèáóò α èç ìíîæåñòâà A(X) èìååò(âîçìîæíî, áåñêîíå÷íîå) ìíîæåñòâî çíà÷åíèé Vα .
Äëÿ êàæäîãî âõîæäåíèÿ X â äåðåâî âûâîäà ñåìàíòè÷åñêèå ïðàâèëàïîçâîëÿþò îïðåäåëèòü îäíî çíà÷åíèå èç ìíîæåñòâà Vα äëÿñîîòâåòñòâóþùåãî àòðèáóòà.Ïóñòü P ñîñòîèò èç m ïðàâèë, è ïóñòü p-å ïðàâèëî èìååòâèäXp0 → Xp1 Xp2 ... Xpnp ,(2.1)ãäå np > 0, Xp0 ∈ N è Xpj ∈ V äëÿ 1 6 j 6 np .Ñåìàíòè÷åñêèìè ïðàâèëàìè íàçûâàþòñÿ ôóíêöèè fpjα ,îïðåäåë¼ííûå äëÿ âñåõ 1 6 p 6 m, 0 6 j 6 np è íåêîòîðûõ α ∈ A0 (Xpj ), åñëè j = 0, èëè α ∈ A1 (Xpj ), åñëè j > 0.Êàæäàÿ òàêàÿ ôóíêöèÿ ïðåäñòàâëÿåò ñîáîé îòîáðàæåíèå èçVα1 ×Vα2 ×...×Vαt â Vα äëÿ íåêîòîðîãî t = t(p, j, α) > 0, ãäåâñå αi = αi (p, j, α) ÿâëÿþòñÿ àòðèáóòàìè íåêîòîðûõ Xpki ,ïðè 0 6 ki = ki (p, j, α) 6 np , 1 6 i 6 t. Äðóãèìè ñëîâàìè, êàæäîå ñåìàíòè÷åñêîå ïðàâèëî îòîáðàæàåò çíà÷åíèÿíåêîòîðûõ àòðèáóòîâ ñèìâîëîâ Xp0 , Xp1 , ...
, Xpnp è çíà÷åíèå íåêîòîðîãî àòðèáóòà ñèìâîëà Xpj .Ãðàììàòèêà (1.5), íàïðèìåð, ïðåäñòàâëÿåòñÿ â âèäåG = ({0, 1, ¾.¿, B, L, N }, {B, L, N }, N, {B → 0, B → 1,L → B , L → LB , N → L, N → L.L}).Àòðèáóòàìè çäåñü ÿâëÿþòñÿA0 (B) = {v},A1 (B) = {s},A0 (L) = {v, l},A1 (L) = {s},A0 (N ) = {v},A1 (N ) = ∅è A0 (x) = A1 (x) = ∅äëÿ x ∈ {0, 1, .}. Ìíîæåñòâàìè çíà÷åíèé àòðèáóòîâ áóäóòVv = {ðàöèîíàëüíûå ÷èñëà}, Vs = Vl = {öåëûå ÷èñëà}. Òèïè÷íûì ïðèìåðîì ïðàâèë âûâîäà ñëóæèò ÷åòâ¼ðòîå ïðàâèëî X40 → X41 X42 , ãäå n4 = 2, X40 = X41 = L, X42 = B . Òàê284Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâæå òèïè÷íî è ñåìàíòè÷åñêîå ïðàâèëî f40v , ñîîòâåòñòâóþùåå ýòîìó ïðàâèëó âûâîäà. Îíî îïðåäåëÿåò v(X40 ) ÷åðåçäðóãèå àòðèáóòû; â äàííîì ñëó÷àå f40v îòîáðàæàåò Vv × Vvâ Vv ñîãëàñíî ôîðìóëå f40v (x, y) = x + y . (Ýòî åñòü íå ÷òîèíîå, êàê ïðàâèëî v(L1 ) = v(L2 ) + v(B) èç (1.5); èñïîëüçóÿäîâîëüíî ãðîìîçäêóþ çàïèñü, ââåä¼ííóþ â ïðåäûäóùåì àáçàöå, ïîëó÷èì:t(4, 0, v) = 2, α1 (4, 0, v) = α2 (4, 0, v) = v,k1 (4, 0, v) = 1, k2 (4, 0, v) = 2).Ñåìàíòè÷åñêèå ïðàâèëà èñïîëüçóþòñÿ äëÿ ñîïîñòàâëåíèÿ öåïî÷êàì ÊÑ ÿçûêà ¾çíà÷åíèÿ¿ ñëåäóþùèì îáðàçîì2 .Äëÿ ëþáîãî âûâîäà òåðìèíàëüíîé öåïî÷êè t èç S ïðè ïîìîùè ñèíòàêñè÷åñêèõ ïðàâèë ïîñòðîèì îáû÷íîå äåðåâî âûâîäà.
À èìåííî, êîðíåì äåðåâà áóäåò S , à êàæäûé óçåë ïîìå÷àåòñÿ ëèáî òåðìèíàëüíûì ñèìâîëîì, ëèáî íåòåðìèíàëîìXp0 , ñîîòâåòñòâóþùèì ïðèìåíåíèþ p-ãî ïðàâèëà äëÿ íåêîòîðîãî p; â ïîñëåäíåì ñëó÷àå ó ýòîãî óçëà áóäåò np íåïîñðåäñòâåííûõ ïîòîìêîâ.Xp0"b" ¢ bb" ¢"bb"¢b"¢Xp1Xp2...(2.2)XpnpÏóñòü òåïåðü X ìåòêà íåêîòîðîãî óçëà äåðåâà è ïóñòüα ∈ A(X) àòðèáóò ñèìâîëà X . Åñëè α ∈ A0 (X), òîX = Xp0 äëÿ íåêîòîðîãî p, åñëè æå α ∈ A1 (X), òî X = Xpjäëÿ íåêîòîðûõ j è p.  îáîèõ ñëó÷àÿõ äåðåâî ¾â ðàéîíå¿ýòîãî óçëà èìååò âèä (2.2).
Ïî îïðåäåëåíèþ àòðèáóò α èìååò â ýòîì óçëå çíà÷åíèå v , åñëè â ñîîòâåòñòâóþùåì ñåìàíòè÷åñêîì ïðàâèëåfpjα : Vα1 × ... × Vαt → Vα(2.3)2 Íà ñàìîì äåëå çíà÷åíèå çäåñü ïðèïèñûâàåòñÿ äåðåâó âûâîäà öåïî÷êè, à íå åé ñàìîé. Åñëè ãðàììàòèêà íåîäíîçíà÷íà, ýòî íå îäíî èòî æå (ñì. ïîñëåäíþþ ñòðàíèöó ñòàòüè). Ïðèì. ïåðåâ.A.2. Ôîðìàëüíûå ñâîéñòâà285âñå àòðèáóòû α1 , ...
, αt óæå îïðåäåëåíû è èìåþò â óçëàõñ ìåòêàìè Xpk1 , ... , Xpkt çíà÷åíèÿ v1 , ... , vt ñîîòâåòñòâåííî, à v = fpjα (v1 , ... , vt ). Ïðîöåññ âû÷èñëåíèÿ àòðèáóòîâ íàäåðåâå ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà íåëüçÿ áóäåò âû÷èñëèòü áîëüøå íè îäíîãî àòðèáóòà. Âû÷èñëåííûå â ðåçóëüòàòå àòðèáóòû êîðíÿ äåðåâà ïðåäñòàâëÿþò ñîáîé ¾çíà÷åíèå¿,ñîîòâåòñòâóþùåå äàííîìó äåðåâó âûâîäà (1.6).Åñòåñòâåííî ïîòðåáîâàòü, ÷òîáû ñåìàíòè÷åñêèå ïðàâèëàäàâàëè âîçìîæíîñòü âû÷èñëèòü âñå àòðèáóòû ïðîèçâîëüíîãî óçëà â ëþáîì äåðåâå âûâîäà. Åñëè ýòî óñëîâèå âûïîëíÿåòñÿ, áóäåì ãîâîðèòü, ÷òî ñåìàíòè÷åñêèå ïðàâèëà çàäàíûêîððåêòíî 3 .
Ïîñêîëüêó äåðåâüåâ âûâîäà, âîîáùå ãîâîðÿ,áåñêîíå÷íî ìíîãî, âàæíî óìåòü îïðåäåëÿòü ïî ñàìîé ãðàììàòèêå, ÿâëÿþòñÿ ëè êîððåêòíûìè å¼ ñåìàíòè÷åñêèå ïðàâèëà. Àëãîðèòì ïðîâåðêè ýòîãî ñâîéñòâà ïðèâåä¼í â ðàçä.A.3.Îòìåòèì, ÷òî ýòîò ìåòîä îïðåäåëåíèÿ ñåìàíòèêè îáëàäàåò òàêîé æå ìîùíîñòüþ, êàê è âñÿêèé äðóãîé âîçìîæíûé ìåòîä, â òîì ñìûñëå, ÷òî çíà÷åíèå ëþáîãî àòðèáóòà â ëþáîì óçëå ìîæåò ïðîèçâîëüíûì îáðàçîì çàâèñåòüîò ñòðóêòóðû âñåãî äåðåâà. Ïðåäïîëîæèì, íàïðèìåð, ÷òîâ ÊÑ ãðàììàòèêå âñåì ñèìâîëàì, êðîìå S , ïðèïèñàíî ïîäâà óíàñëåäîâàííûõ àòðèáóòà: l (¾ïîëîæåíèå¿) è t (¾äåðåâî¿), à âñåì íåòåðìèíàëàì, êðîìå òîãî, ïî îäíîìó ñèíòåçèðîâàííîìó àòðèáóòó s (¾ïîääåðåâî¿).
Çíà÷åíèÿìè l áóäóòêîíå÷íûå ïîñëåäîâàòåëüíîñòè ïîëîæèòåëüíûõ öåëûõ ÷èñåë{a1 · a2 · ... · ak }, îïðåäåëÿþùèå ìåñòîíàõîæäåíèå óçëà â äåðåâå â ñîîòâåòñòâèè ñ ñèñòåìîé îáîçíà÷åíèÿ Äüþè (ñì. [8],ñòð. 388389)4 . Àòðèáóòû t è s ïðåäñòàâëÿþò ñîáîé ìíîæåñòâî óïîðÿäî÷åííûõ ïàð (l, X), ãäå l ïîëîæåíèå óçëà, à X ñèìâîë ãðàììàòèêè, îáîçíà÷àþùèé ìåòêó óçëàñ ïîëîæåíèåì l. Ñåìàíòè÷åñêèìè ïðàâèëàìè äëÿ êàæäîãîñèíòàêñè÷åñêîãî ïðàâèëà (2.1) ñëóæàò3  îðèãèíàëå well defined. Ïðèì. ðåä.4 Íåçíàêîìûì ñ ýòîé ñèñòåìîé îáîçíà÷åíèé íå îáÿçàòåëüíî îáðà-ùàòüñÿ çà ñïðàâêîé ïî óêàçàííîìó àäðåñó: ïðèíöèï ñèñòåìû ëåãêîóñìàòðèâàåòñÿ èç ôîðìóë (2.4). Ïðèì. ðåä.286Ïðèëîæåíèå A.
Ñåìàíòèêà ÊÑ-ÿçûêîâ½l(Xpj ) =½l(Xpj ) =l(Xp0 ) · j ,j,åñëè Xp0 6= S;åñëè Xp0 = S;t(Xp0 ) ,s(Xp0 ) ,åñëè Xp0 6= S;åñëè Xp0 = S;s(Xp0 ) = {(l(Xp0 ), Xp0 )|Xp0 6= S} ∪np[(2.4){s(Xpj )|Xpj ∈ N }.j=1Ñëåäîâàòåëüíî, äëÿ äåðåâà (1.2), íàïðèìåð, ìû èìååìs(N ) = {(1, L), (2, ·), (3, L),(1.1, L), (1.2, B), (3.1, L), (3.2, B),(1.1.1, L), (1.1.2, B), (1.2.1, 1), (3.1.1, B), (3.2.1, 1),(1.1.1.1, L), (1.1.1.2, B), (1.1.2.1, 0), (3.1.1.1, 0),(1.1.1.1.1, B), (1.1.1.2.1, 1), (1.1.1.1.2.1, 1)}.ßñíî, ÷òî ýòà çàïèñü ñîäåðæèò âñþ èíôîðìàöèþ î äåðåâå âûâîäà. Ñîãëàñíî ñåìàíòè÷åñêèì ïðàâèëàì (2.4), àòðèáóò t âî âñåõ óçëàõ (êðîìå êîðíÿ) ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî, õàðàêòåðèçóþùåå âñ¼ äåðåâî âûâîäà; àòðèáóò lîïðåäåëÿåò ìåñòîíàõîæäåíèå ýòèõ óçëîâ.
Îòñþäà ñðàçó ñëåäóåò, ÷òî ëþáàÿ ìûñëèìàÿ ôóíêöèÿ, îïðåäåë¼ííàÿ íà äåðåâå âûâîäà, ìîæåò áûòü ïðåäñòàâëåíà êàê àòðèáóò ïðîèçâîëüíîãî óçëà, ïîñêîëüêó ýòà ôóíêöèÿ èìååò âèä f (t, l),äëÿ íåêîòîðîãî f . Àíàëîãè÷íî, ìîæíî ïîêàçàòü, ÷òî äëÿîïðåäåëåíèÿ çíà÷åíèÿ, ñâÿçàííîãî ñ ïðîèçâîëüíûì äåðåâîì âûâîäà, äîñòàòî÷íî òîëüêî ñèíòåçèðîâàííûõ àòðèáóòîâ, ïîñêîëüêó ñèíòåçèðîâàííûé àòðèáóò w, âû÷èñëÿåìûéïî ôîðìóëåw(Xp0 ) = {(0, Xp0 )} ∪np[{(j · α, X) |j=1(α, X) ∈ w(Xpj ), Xpj ∈ N }(2.5)A.3. Ïðîâåðêà íà çàöèêëåííîñòü287â êîðíå äåðåâà ïîëíîñòüþ îïðåäåëÿåò âñ¼ äåðåâî5 .
Êàæäîå ñåìàíòè÷åñêîå ïðàâèëî, îïðåäåëÿåìîå ìåòîäàìè ýòîãîðàçäåëà, ìîæíî ðàññìàòðèâàòü êàê ôóíêöèþ ýòîãî àòðèáóòà w. Ñëåäîâàòåëüíî, îïèñàííûé îáùèé ìåòîä ïî ñóùåñòâó íå áîëåå ìîùåí, ÷åì ìåòîä, âîâñå íå èñïîëüçóþùèéíàñëåäîâàííûõ àòðèáóòîâ. Ïðàâäà, ýòî óòâåðæäåíèå íå ñëåäóåò ïîíèìàòü êàê ïðàêòè÷åñêóþ ðåêîìåíäàöèþ, ïîñêîëüêó ñåìàíòè÷åñêèå ïðàâèëà, íå èñïîëüçóþùèå óíàñëåäîâàííûõ àòðèáóòîâ, áóäóò çà÷àñòóþ ãîðàçäî áîëåå ñëîæíûìè(à òàêæå ìåíåå ïîíèìàåìûìè è ïðàêòè÷íûìè), ÷åì ïðàâèëà, âêëþ÷àþùèå àòðèáóòû îáîèõ òèïîâ.
Åñëè äîïóñòèòü,÷òîáû àòðèáóòû â êàæäîì óçëå äåðåâà ìîãëè çàâèñåòü îòâñåãî äåðåâà, òî ñåìàíòè÷åñêèå ïðàâèëà ÷àñòî ìîãóò ñòàòüïðîùå è áóäóò ëó÷øå ñîîòâåòñòâîâàòü íàøåìó ïîíèìàíèþïðîöåññà âû÷èñëåíèÿ.A.3. Ïðîâåðêà íà çàöèêëåííîñòüÐàññìîòðèì òåïåðü àëãîðèòì, ïðîâåðÿþùèé, ÿâëÿåòñÿëè êîððåêòíîé ñèñòåìà ñåìàíòè÷åñêèõ ïðàâèë, îïðåäåë¼ííàÿ â ïðåäûäóùåì ðàçäåëå. Äðóãèìè ñëîâàìè, ìû õîòèìçíàòü, êîãäà ñåìàíòè÷åñêèå ïðàâèëà ïîçâîëÿþò âû÷èñëèòüçíà÷åíèå ëþáîãî àòðèáóòà ëþáîãî óçëà ïðîèçâîëüíîãî äåðåâà âûâîäà.
Ìîæíî ñ÷èòàòü, ÷òî ãðàììàòèêà íå ñîäåðæèò¾áåñïîëåçíûõ¿ ïðàâèë âûâîäà, òî åñòü ÷òî êàæäîå ïðàâèëî èç P ó÷àñòâóåò â âûâîäå õîòÿ áû îäíîé òåðìèíàëüíîéöåïî÷êè.Ïóñòü T ïðîèçâîëüíîå äåðåâî âûâîäà, ñîîòâåòñòâóþùåå äàííîé ãðàììàòèêå; ìåòêàìè êîíöåâûõ óçëîâ ìîãóòáûòü òîëüêî òåðìèíàëüíûå ñèìâîëû, êîðíþ æå ðàçðåøèìèìåòü ìåòêîé íå òîëüêî àêñèîìó, íî è ëþáîé ñèìâîë èç V .Òîãäà ìîæíî îïðåäåëèòü îðèåíòèðîâàííûé ãðàô D(T ), ñîîòâåòñòâóþùèé T , âçÿâ â êà÷åñòâå åãî óçëîâ óïîðÿäî÷åííûåïàðû (X, α), ãäå X óçåë äåðåâà T , à α àòðèáóò ñèìâîëà, ñëóæàùåãî ìåòêîé óçëà X .
Äóãà èç (X1 , α1 ) â (X2 , α2 )5Snp ïðàâîé ÷àñòè ôîðìóëû íóæíî/ N }. Ïðèì. ðåä.j=1 {(j · 0, x) | x ∈äîáàâèòüåù¼÷ëåí288Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâïðîâîäèòñÿ â òîì è òîëüêî â òîì ñëó÷àå, êîãäà ñåìàíòè÷åñêîå ïðàâèëî, âû÷èñëÿþùåå àòðèáóò α2 , íåïîñðåäñòâåííîèñïîëüçóåò çíà÷åíèå àòðèáóòà α1 . Íàïðèìåð, åñëè T äåðåâî (1.2), à â êà÷åñòâå ñåìàíòè÷åñêèõ ïðàâèë âçÿòû ïðàâèëà(1.5), òî îðãðàô D(T ) áóäåò èìåòü òàêîé âèä:•v(L) • l(L) • s(L)•v(N )XX: y»XX»»»yXX©©S* ©X©*¼X©©wX•v(L)•l(L)•s(L)XyXX XX •v(B) • s(B)X6 6 XXIX?X XXz•v(L)l(L) • s(L)X •v(B) • s(B)XyX• XXXXX6 6 X?X XXXz•v(L) • l(L) • s(L)X •v(B) • s(B)´+́6I•v(B) • s(B)R•v(L)• l(L) • s(L):»»:»»»»»9AU»» »» »•v(L) • l(L) • s(L) •v(B) • s(B)6¡¡ª•v(B) • s(B)I(3.1)IÄðóãèìè ñëîâàìè, óçëàìè ãðàôà D(T ) ñëóæàò àòðèáóòû, çíà÷åíèÿ êîòîðûõ íóæíî âû÷èñëèòü, à äóãè îïðåäåëÿþò çàâèñèìîñòè, ïîäðàçóìåâàþùèå, êàêèå àòðèáóòû âû÷èñëÿþòñÿ ðàíüøå, à êàêèå ïîçæå (1.6).ßñíî, ÷òî ñåìàíòè÷åñêèå ïðàâèëà ÿâëÿþòñÿ êîððåêòíûìè òîãäà è òîëüêî òîãäà, êîãäà íè îäèí èç îðãðàôîâ D(T )íå ñîäåðæèò îðèåíòèðîâàííîãî öèêëà.
Äåëî â òîì, ÷òî åñëè â ãðàôå íåò îðèåíòèðîâàííûõ öèêëîâ, òî ìîæíî ïðèìåíèòü õîðîøî èçâåñòíóþ ïðîöåäóðó, ïîçâîëÿþùóþ ïðèñâîèòü çíà÷åíèÿ âñåì àòðèáóòàì (ñì. [8], ñòð. 465466). Åñëèæå â íåêîòîðîì ãðàôå D(T ) åñòü îðèåíòèðîâàííûé öèêë,òî ââèäó òîãî ÷òî ãðàììàòèêà íå ñîäåðæèò áåñïîëåçíûõïðàâèë, ìîæíî óòâåðæäàòü, ÷òî ñóùåñòâóåò îðèåíòèðîâàííûé öèêë â íåêîòîðîì ãðàôå D(T ), ó êîòîðîãî ìåòêîé êîðíÿ äåðåâà T ñëóæèò S . Äëÿ òàêîãî äåðåâà T âñå àòðèáóòûâû÷èñëèòü íå óäà¼òñÿ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
