В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 39
Текст из файла (страница 39)
Òàêèì îáðàçîì, çàäà÷à ¾ßâëÿþòñÿëè ñåìàíòè÷åñêèå ïðàâèëà êîððåêòíûì?¿ ñâîäèòñÿ ê çàäà÷å¾Ñîäåðæàò ëè îðãðàôû D(T ) îðèåíòèðîâàííûå öèêëû?¿Êàæäûé îðãðàô D(T ) ìîæíî ðàññìàòðèâàòü êàê ñóïåðïîçèöèþ ìåíüøèõ îðãðàôîâ Dp , ñîîòâåòñòâóþùèõ ïðàâèëàì Xp0 → Xp1 · · · Xpnp ãðàììàòèêè, 1 6 p 6 m. Âîáîçíà÷åíèÿõ ðàçä. 2 îðãðàô Dp èìååò óçëû (Xpj , α) äëÿA.3. Ïðîâåðêà íà çàöèêëåííîñòü2890 6 j 6 np , α ∈ A(Xpj ) è äóãè èç (Xpki , α) â (Xpj , α) äëÿ0 6 j 6 np , α ∈ A0 (Xpj ), åñëè j = 0, α ∈ A1 (Xpj ), åñëèj > 0, ki = ki (p, j, α), αi = αi (p, j, α), 1 6 i 6 t(p, j, α).Äðóãèìè ñëîâàìè, Dp îòðàæàåò ñâÿçè, êîòîðûå ïîðîæäàþòâñå ñåìàíòè÷åñêèå ïðàâèëà, ñîîòâåòñòâóþùèå p-ìó ñèíòàêñè÷åñêîìó ïðàâèëó.
Íàïðèìåð, øåñòè ïðàâèëàì ãðàììàòèêè (1.5) ñîîòâåòñòâóþò øåñòü ñëåäóþùèõ îðãðàôîâ:ªD1 : •v(B) • s(B)D2 : •v(B) • s(B)D3 : •v(L) • l(L) • s(L)D4 : •v(L1 ) • l(L1 ) • s(L1 )6PiPP PP¢̧¢̧¢P P Pq¢¢¢® PP P•v(L2 ) • l(L2 ) • s(L2 ) • v(B) • s(B)¡ª¡•v(B) • s(B)D5 : •v(N ) • l(L) • s(L)6•v(L) • l(L) • s(L)(3.2)D6 : •v(N )iPP©* P©PP©R•v(L1 ) • l(L1 ) • s(L1 ) • v(L2 ) • l(L2 ) • s(L2 )Îðãðàô (3.1) ïîëó÷àåòñÿ â ðåçóëüòàòå ¾îáúåäèíåíèÿ¿òàêèõ ïîäãðàôîâ. Âîîáùå, åñëè T èìååò â êà÷åñòâå ìåòêèêîðíÿ òåðìèíàë, D(T ) íå ñîäåðæèò äóã. Åñëè êîðåíü äåðåâàT ïîìå÷åí íåòåðìèíàëüíûì ñèìâîëîì, T èìååò âèäXp0"b" ¢ bb" ¢b"¢b"b"¢T1T2...(3.3)T npäëÿ íåêîòîðîãî p, ãäå Tj äåðåâî âûâîäà, ó êîòîðîãî êîðåíü ïîìå÷åí ñèìâîëîì Xpj , ãäå 1 6 j 6 np .  ïåðâîìñëó÷àå ãîâîðÿò, ÷òî T äåðåâî âûâîäà òèïà 0, âî âòîðîì ñëó÷àå T íàçûâàåòñÿ äåðåâîì âûâîäà òèïà ð .
Âñîîòâåòñòâèè ñ ýòèì îïðåäåëåíèåì äëÿ òîãî, ÷òîáû ïî Dp ,D(T1 ), ... , D(Tnp ) ïîñòðîèòü D(T ), íóæíî äëÿ âñåõ j, 1 6j 6 np ñîâìåñòèòü óçëû, ñîîòâåòñòâóþùèå àòðèáóòàì ñèìâîëà Xpj ãðàôà Dp ñ ñîîòâåòñòâóþùèìè óçëàìè (îòâå÷àþùèìè òåì æå àòðèáóòàì êîðíÿ äåðåâà Tj ) â ãðàôå D(Tj ).Äëÿ ïðîâåðêè òîãî, ñîäåðæèò ëè ãðàô D(T ) îðèåíòèðîâàííûé öèêë, íàì ïîíàäîáèòñÿ åù¼ îäíî ïîíÿòèå.
Ïóñòü p 290Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâíîìåð ïðàâèëà âûâîäà. Îáîçíà÷èì ÷åðåç Gj ïðîèçâîëüíûéîðãðàô (1 6 j 6 np ), ìíîæåñòâî óçëîâ êîòîðîãî ÿâëÿåòñÿïîäìíîæåñòâîì ìíîæåñòâà A(Xpj ) àòðèáóòîâ ñèìâîëà Xpj .ÏóñòüDp [G1 , ... , Gnp ](3.4)îðãðàô, ïîëó÷åííûé èç Dp äîáàâëåíèåì äóã, èäóùèõ èç(Xpj , α) â (Xpj , α0 ), åñëè â ãðàôå Gj åñòü äóãà èç α â α0 .Íàïðèìåð, åñëèvG1 = •l•Is•vG2 = •s•Iè åñëè D4 îðèåíòèðîâàííûé ãðàô èç (3.2), òî D4 (G1 , G2 )èìååò âèäD4 : •v(L1 ) • l(L1 ) • s(L1 )PiP¢̧¢̧ PP¢ PPPPq¢¢P P¢®•v(L2 ) • l(L2 ) • s(L2 ) • v(B) • s(B)YIÒåïåðü ìîæíî âîñïîëüçîâàòüñÿ ñëåäóþùèì àëãîðèòìîì.Äëÿ ëþáîãî X ∈ V S(X) áóäåò íåêîòîðûì ìíîæåñòâîì îðèåíòèðîâàííûõ ãðàôîâ ñ óçëàìè èç A(X).
Ñíà÷àëà äëÿ âñåõX ∈ N S(X) ïóñòî, à äëÿ X ∈/ N S(X) ñîñòîèò èç åäèíñòâåííîãî ãðàôà ñ ìíîæåñòâîì óçëîâ A(X) è íå ñîäåðæàùåãî äóã. Áóäåì äîáàâëÿòü ê ìíîæåñòâàì S(X) íîâûå îðãðàôû ïðè ïîìîùè ñëåäóþùåé ïðîöåäóðû äî òåõ ïîð, ïîêà âS(X) íå ïåðåñòàíóò ïîÿâëÿòüñÿ íîâûå ýëåìåíòû. Âûáåðåìöåëîå p, 1 6 p 6 m è äëÿ êàæäîãî j , 1 6 j 6 np , âûáåðåì îðãðàô Dj0 ∈ S(Xpj ).
Çàòåì äîáàâèì â S(Xp0 ) îðãðàôñ ìíîæåñòâîì óçëîâ A(Xpo ), îáëàäàþùèé òåì ñâîéñòâîì,÷òî â í¼ì äóãà îò α ê α0 èä¼ò òîãäà è òîëüêî òîãäà, êîãäà âîðãðàôåDp [D10 , ... , Dn0 p ](3.5)ñóùåñòâóåò îðèåíòèðîâàííûé ïóòü èç (Xp0 , α) â (Xp0 , α0 ).ßñíî, ÷òî ýòîò ïðîöåññ ðàíî èëè ïîçäíî çàêîí÷èòñÿ è íîâûåA.3. Ïðîâåðêà íà çàöèêëåííîñòü291îðãðàôû ïåðåñòàíóò ïîðîæäàòüñÿ, ïîñêîëüêó âîîáùå ñóùåñòâóåò ëèøü êîíå÷íîå ÷èñëî îðèåíòèðîâàííûõ ãðàôîâ. ñëó÷àå ãðàììàòèêè (1.5) àëãîðèòì ïîñòðîèò ñëåäóþùèå ìíîæåñòâà:½¾½¾vvlsvlsS(N ) =;S(L) =;....
, ...O½¾vsv sS(B) =; S(0) = S(1) = {}... , . .MÏóñòü T äåðåâî âûâîäà ñ êîðíåì X , è ïóñòü D0 (T ) îðèåíòèðîâàííûé ãðàô ñ ìíîæåñòâîì óçëîâ A(X), ó êîòîðîãî åñòü äóãà èç α â α0 òîãäà è òîëüêî òîãäà, êîãäà â D(T )ñóùåñòâóåò îðèåíòèðîâàííûé ïóòü èç (X, α) â (X, α0 ). Ïîêàæåì, ÷òî ïîñëå îêîí÷àíèÿ ðàáîòû îïèñàííîãî âûøå àëãîðèòìà äëÿ âñåõ X ∈ V S(X) ýòî ìíîæåñòâî âñåõ D0 (T ),ãäå T äåðåâî âûâîäà ñ êîðíåì X 6 . Äåéñòâèòåëüíî, ïîñòðîåíèå íå äîáàâëÿåò ê S(X) íîâûõ îðèåíòèðîâàííûõ ãðàôîâ,íå ÿâëÿþùèõñÿ D0 (T ). Àëãîðèòì ìîæíî äàæå ëåãêî îáîáùèòü òàê, ÷òîáû äëÿ êàæäîãî ãðàôà èç S(X) îí ïå÷àòàëíà âûõîäå ñîîòâåòñòâóþùåå äåðåâî âûâîäà T . Îáðàòíî, åñëè T äåðåâî âûâîäà, ìû ìîæåì ïîêàçàòü èíäóêöèåé ïî÷èñëó óçëîâ äåðåâà T , ÷òî D0 (T ) ïðèíàäëåæèò íåêîòîðîìó ìíîæåñòâó S(X).  ïðîòèâíîì ñëó÷àå T äîëæíî èìåòüâèä (3.3) è D(T ) ¾ñîñòàâëåí¿ èç Dp D(T1 ), ...
, D(Tnp ). Ïîèíäóêöèè è âñëåäñòâèå òîãî, ÷òî ïðè j 6= j 0 èç D(Tj ) âD(Tj 0 ) íå ïðîõîäèò äóã âíå Dp , äóãè â D(T1 ), ... , D(Tnp ),ñîñòàâëÿþùåé ðàññìàòðèâàåìûé ïóòü ãðàôà D(T ), ìîæíîçàìåíèòü ñîîòâåòñòâóþùèìè äóãàìè â Dp [D0 1, ... , Dn0 p ], ãäåDj0 ∈ S(Xpj ), 1 6 j 6 np . Ïîýòîìó îðèåíòèðîâàííûé ãðàô,âêëþ÷àåìûé â S(Xp0 ) íà áàçå Dp [D0 1, ... , Dn0 p ], ïðîñòî ñîâïàäàåò ñ D0 (T ).6 Åñëè, êàê îïðåäåëÿëîñü âûøå, êîíöåâûìè óçëàìè T ìîãóò áûòüòîëüêî òåðìèíàëüíûå ñèìâîëû, òî S(X) áóäåò ñîäåðæàòü âñå D0 (T ),à íå ñîâïàäàòü ñî ìíîæåñòâîì âñåõ D0 (T ). ×òîáû íå âíîñèòü â ïîñëåäóþùèå ïîñòðîåíèÿ íåñóùåñòâåííûõ èñïðàâëåíèé, ïðîùå â ýòîìàáçàöå ñ÷èòàòü T ëþáûì äåðåâîì âûâîäà ñ êîðíåì X (òî åñòü íå îáÿçàòåëüíî ïðîäîëæåííûì äî òåðìèíàëîâ). Ïðèì.
ðåä.292Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâÂûøåïðèâåä¼ííûé àëãîðèòì ðåøàåò çàäà÷ó, ïîñòàâëåííóþ â ýòîì ðàçäåëå.Òåîðåìà. Ñåìàíòè÷åñêèå ïðàâèëà, äîáàâëåííûå ê ãðàììàòèêå òàê, êàê ýòî ñäåëàíî â ðàçä. 2, ÿâëÿþòñÿ êîððåêòíûìè òîãäà è òîëüêî òîãäà, êîãäà íè îäèí èç îðèåíòèðîâàííûõ ãðàôîâ (3.5) íè ïðè êàêîì âûáîðå p èD10 ∈ S(Xp1 ), ... , Dn0 p ∈ S(Xnp ) íå ñîäåðæèò îðèåíòèðîâàííûõ öèêëîâ.Äîêàçàòåëüñòâî. Åñëè (3.5) ñîäåðæèò îðèåíòèðîâàííûéöèêë, òî, êàê áûëî ïîêàçàíî âûøå, íåêîòîðûé D(T ) ñîäåðæèò îðèåíòèðîâàííûé öèêë.
Íàîáîðîò, åñëè T äåðåâî ñ íàèìåíüøèì âîçìîæíûì ÷èñëîì óëîâ, òàêîå, ÷òîD(T ) ñîäåðæèò îðèåíòèðîâàííûé öèêë, òî T äîëæíî èìåòüâèä (3.3), à D(T ) ¾ñîñòàâëÿåòñÿ¿ èç Dp ; D(T1 ), ... , D(Tnp ).Èç ìèíèìàëüíîñòè T ñëåäóåò, ÷òî îðèåíòèðîâàííûé öèêëâêëþ÷àåò ïî ìåíüøåé ìåðå îäíó äóãó ãðàôà Dp , è, ñëåäîâàòåëüíî, ìîæíî, ðàññóæäàÿ, êàê âûøå, âñå äóãè, îáðàçóþùèåýòîò öèêë è ëåæàùèå â îäíîì èç ãðàôîâ D(T1 ), ... , D(Tnp ),çàìåíèòü äóãàìè ãðàôà (3.5).A.4.
Ïðîñòîé ÿçûê ïðîãðàììèðîâàíèÿÑåé÷àñ ìû ïðîäåìîíñòðèðóåì, êàê îïèñàííûé âûøå ìåòîä ñåìàíòè÷åñêîãî îïðåäåëåíèÿ ìîæíî ïðèìåíÿòü ê ÿçûêàì ïðîãðàììèðîâàíèÿ. Äëÿ ïðîñòîòû èçó÷èì ôîðìàëüíîåîïðåäåëåíèå íåáîëüøîãî ÿçûêà, îïèñûâàþùåãî ïðîãðàììûäëÿ ìàøèí Òüþðèíãà.Ìàøèíà Òüþðèíãà (â êëàññè÷åñêîì ñìûñëå) ðàáîòàåò ñáåñêîíå÷íîé ëåíòîé, êîòîðóþ ìîæíî ïðåäñòàâëÿòü ñåáå ðàçäåë¼ííîé íà êëåòêè. Ìàøèíà ìîæåò ñ÷èòûâàòü èëè çàïèñûâàòü ñèìâîëû íåêîòîðîãî êîíå÷íîãî àëôàâèòà â îáîçðåâàåìóþ â íåêîòîðûé ìîìåíò êëåòêó, à òàêæå ñäâèãàòü ÷èòàþùåå óñòðîéñòâî íà îäíó êëåòêó âïðàâî èëè âëåâî.
Ñëåäóþùàÿ ïðîãðàììà, íàïðèìåð, ïðèáàâëÿåò åäèíèöó ê öåëîìóA.4. Ïðîñòîé ÿçûê ïðîãðàììèðîâàíèÿ293÷èñëó, ïðåäñòàâëåííîìó â äâîè÷íîì âèäå, è ïå÷àòàåò òî÷êóñïðàâà îò ýòîãî ÷èñëà. Ïðåäïîëàãàåòñÿ, ÷òî â íà÷àëå è âêîíöå ðàáîòû ïðîãðàììû ÷èòàþùåå óñòðîéñòâî íàõîäèòñÿíà ïåðâîé ïóñòîé êëåòêå ñïðàâà îò ÷èñëà.Àëôàâèò ïðîáåë, åäèíèöà, íóëü, òî÷êà ;ïå÷àòàòü ¾òî÷êà¿; ïåðåéòè íà âûïîëíèòü ;òåñò: åñëè ñèìâîë íà ëåíòå ¾åäèíèöà ¿, òî{ïå÷àòàòü ¾íóëü ¿;(4.1)âûïîëíèòü : ñäâèíóòüñÿ âëåâî íà îäíó êëåòêó;ïåðåéòè íà òåñò };ïå÷àòàòü ¾åäèíèöà ¿;âîçâðàò: ñäâèíóòüñÿ âïðàâî íà îäíó êëåòêó;åñëè ñèìâîë íà ëåíòå ¾íóëü ¿, òî ïåðåéòè íà âîçâðàò.×èòàòåëü, ïî-âèäèìîìó, íàéä¼ò ýòîò ÿçûê ïðîãðàììèðîâàíèÿ äîñòàòî÷íî ïðîçðà÷íûì äëÿ òîãî, ÷òîáû ïîíÿòü åãî,ïðåæäå ÷åì áóäåò äàíî êàêîå-ëèáî ôîðìàëüíîå îïðåäåëåíèå, õîòÿ ýòî è íå îáÿçàòåëüíî.
Ïðèâåä¼ííàÿ âûøå ïðîãðàììà íå ÿâëÿåòñÿ ïðèìåðîì èñêóñíîãî ïðîãðàììèðîâàíèÿ. Îíà ëèøü èëëþñòðèðóåò íåêîòîðûå ÷åðòû ïðîñòîãîÿçûêà, ðàññìàòðèâàåìîãî â íàñòîÿùåì ðàçäåëå.Ïîñêîëüêó êàæäûé ÿçûê ïðîãðàììèðîâàíèÿ íóæíî êàêòî íàçûâàòü, íàçîâ¼ì íàø ÿçûê Òüþðèíãîëîì. Âñÿêàÿ ïðàâèëüíàÿ ïðîãðàììà íà Òüþðèíãîëå îïðåäåëÿåò ïðîãðàììóäëÿ ìàøèíû Òüþðèíãà; áóäåì ãîâîðèòü, ÷òî ïðîãðàììà äëÿìàøèíû Òüþðèíãà ñîñòîèò èç:• ìíîæåñòâà ¾ñîñòîÿíèé¿ Q,• ìíîæåñòâà ¾ñèìâîëîâ¿ Σ,• ¾íà÷àëüíîãî ñîñòîÿíèÿ¿ q0 ∈ Q,• ¾êîíå÷íîãî ñîñòîÿíèÿ¿ q∞ ∈ Q,• è ¾ôóíêöèè ïåðåõîäîâ¿ δ , îòîáðàæàþùåé ìíîæåñòâî(Q−{q∞ })×Σ â Σ×{−1, 0, +1}×Q. Åñëè δ(q, s) = (s0 , k 0 , q 0 ),òî ýòî îçíà÷àåò, ÷òî åñëè ìàøèíà íàõîäèòñÿ â ñîñòîÿíèè qè îáîçðåâàåò ñèìâîë s, òî îíà ïå÷àòàåò ñèìâîë s0 , ñäâèãàåò÷èòàþùåå óñòðîéñòâî íà k êëåòîê âïðàâî (ñäâèãó íà îäíó êëåòêó âëåâî ñîîòâåòñòâóåò ñëó÷àé k = 1) è ïåðåõîäèòâ ñîñòîÿíèå q 0 . Ôîðìàëüíî ïðîãðàììà ìàøèíû Òüþðèíãàîïðåäåëÿåò âû÷èñëåíèå äëÿ ëåíòû ñ ¾ëþáûì íà÷àëüíûì294Ïðèëîæåíèå A.
Ñåìàíòèêà ÊÑ-ÿçûêîâñîäåðæèìûì¿, òî åñòü äëÿ ëþáîé áåñêîíå÷íîé â îáå ñòîðîíû ïîñëåäîâàòåëüíîñòè... , a−3 , a−2 , a−1 , a0 , a1 , a2 , a3 , ...(4.2)ýëåìåíòîâ àëôàâèòà Σ ñëåäóþùèì îáðàçîì.  ïðîèçâîëüíûé ìîìåíò âû÷èñëåíèÿ ñóùåñòâóåò ¾òåêóùåå ñîñòîÿíèå¿q ∈ Q è öåëî÷èñëåííàÿ âåëè÷èíà ¾ïîëîæåíèå ÷èòàþùåãîóñòðîéñòâà¿ p. Âíà÷àëå q = q0 è p = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
