В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 40
Текст из файла (страница 40)
Åñëè q 6= q∞ è åñëè δ(q, ap ) = (s0 , k 0 , q 0 ), òî ñëåäóþùèì øàãîì âû÷èñëåíèÿáóäåò çàìåíà çíà÷åíèÿ p íà p + k , q íà q 0 è ap íà s0 . Åñëèq = q∞ , âû÷èñëåíèå çàêàí÷èâàåòñÿ. (Âû÷èñëåíèå ìîæåò íåçàêîí÷èòüñÿ; äëÿ ïðîãðàììû (4.1) ýòî ïðîèçîéä¼ò òîãäà èòîëüêî òîãäà, êîãäà aj =¾åäèíèöà¿ äëÿ âñåõ j < 0.)Òåïåðü, êîãäà ó íàñ èìååòñÿ òî÷íîå îïðåäåëåíèå ïðîãðàìì ìàøèí Òüþðèíãà, ìû õîòèì îïðåäåëèòü ïðîãðàììóìàøèíû Òüþðèíãà, ñîîòâåòñòâóþùóþ ïðîèçâîëüíîé ïðîãðàììå íà Òüþðèíãîëå (è îäíîâðåìåííî îïðåäåëèòü ñèíòàêñèñ Òüþðèíãîëà). Äëÿ ýòîãî óäîáíî ïðèíÿòü íåêîòîðîåñîãëàøåíèå î ôîðìå çàïèñè.(1) Ñåìàíòè÷åñêîå ïðàâèëî ¾âêëþ÷èòü õ â B¿, ñâÿçàííîå ñ ñèíòàêñè÷åñêèì ïðàâèëîì, îçíà÷àåò, ÷òî x äîëæåíñòàòü ýëåìåíòîì ìíîæåñòâà B , ãäå B àòðèáóò àêñèîìû Sãðàììàòèêè.
Çíà÷åíèåì B áóäåò ìíîæåñòâî âñåõ x, äëÿ êîòîðûõ ñóùåñòâóåò òàêîå ñåìàíòè÷åñêîå ïðàâèëî, ñâÿçàííîåñ êàæäûì ïðèìåíåíèåì ñîîòâåòñòâóþùåãî ñèíòàêñè÷åñêîãîïðàâèëà â äåðåâå âûâîäà. (Ýòî ïðàâèëî ìîæíî ðàññìàòðèâàòü êàê ñîêðàù¼ííóþ çàïèñü ñåìàíòè÷åñêîãî ïðàâèëàB (Xp0 ) =np[B (Xpj ) ∪(4.3)j=1∪ {x | ¾âêëþ÷èòü x â B ¿ ñâÿçàíî ñ p-ì ïðàâèëîì},ñâÿçàííîãî ñ êàæäûì ñèíòàêñè÷åñêèì ïðàâèëîì.
Çäåñü B ñèíòåçèðîâàííûé àòðèáóò, èìåþùèéñÿ ó âñåõ íåòåðìèíàëüíûõ ñèìâîëîâ. Äëÿ òåðìèíàëüíûõ ñèìâîëîâ B(x) ïóñòî. ßñíî, ÷òî ýòè ïðàâèëà ïîçâîëÿþò ïîëó÷èòü íóæíîå B(S).)A.4. Ïðîñòîé ÿçûê ïðîãðàììèðîâàíèÿ295(2) Ñåìàíòè÷åñêîå ïðàâèëî ¾îïðåäåëèòü f (x) = y ¿,ñâÿçàííîå ñ ñèíòàêñè÷åñêèì ïðàâèëîì, îçíà÷àåò, ÷òî çíà÷åíèå ôóíêöèè f â òî÷êå x áóäåò ðàâíî y ; çäåñü f àòðèáóò àêñèîìû S ãðàììàòèêè. Åñëè âñòðå÷àåòñÿ äâà ïðàâèëà,çàäàþùèõ çíà÷åíèå f (x) äëÿ îäíîãî è òîãî æå çíà÷åíèÿ x,òî âîçíèêàåò ñèòóàöèÿ îøèáêè, à äåðåâî âûâîäà, â êîòîðîìîíà âîçíèêëà, íàçûâàåòñÿ íåïðàâèëüíûì. Äàëåå, ê ôóíêöèè f ìîæíî îáðàùàòüñÿ â äðóãèõ ñåìàíòè÷åñêèõ ïðàâèëàõïðè óñëîâèè, ÷òî f (x) áóäåò èñïîëüçîâàòüñÿ òîëüêî òîãäà,êîãäà çíà÷åíèå ôóíêöèè äëÿ àðãóìåíòà x îïðåäåëåíî.
Ëþáîå äåðåâî âûâîäà, äëÿ êîòîðîãî âñòðåòèëîñü îáðàùåíèå êíåîïðåäåë¼ííîé âåëè÷èíå f (x), íàçûâàåòñÿ íåïðàâèëüíûì.(Ïðàâèëà òàêîãî òèïà âàæíû, íàïðèìåð, òîãäà, êîãäà íóæíî îáåñïå÷èòü ñîîòâåòñòâèå ìåæäó îïèñàíèåì è èñïîëüçîâàíèåì èäåíòèôèêàòîðîâ.  ïðèâåä¼ííîì íèæå ïðèìåðå â ñîîòâåòñòâèè ñ ýòèì ñîãëàøåíèåì íåïðàâèëüíûìè áóäóò ïðîãðàììû, â êîòîðûõ îäèí è òîò æå èäåíòèôèêàòîðäâàæäû âñòðå÷àåòñÿ â êà÷åñòâå ìåòêè, èëè â îïåðàòîðå ïåðåõîäà èñïîëüçóåòñÿ èäåíòèôèêàòîð, íå ÿâëÿþùèéñÿ ìåòêîé îïåðàòîðà.  ñóùíîñòè, ýòî ïðàâèëî ìîæíî ïðåäñòàâëÿòü ñåáå, àíàëîãè÷íî (1), êàê ¾âêëþ÷èòü (x, y) â f ¿, åñëèðàññìàòðèâàòü f êàê ìíîæåñòâî óïîðÿäî÷åííûõ ïàð; íåîáõîäèìî ñîîòâåòñòâåííî ââåñòè äîïîëíèòåëüíûå ïðîâåðêèíà çàöèêëåííîñòü. Ïðèçíàê ¾ïðàâèëüíî èëè íåïðàâèëüíî¿ìîæíî ñ÷èòàòü àòðèáóòîì àêñèîìû S . Ïîñòðîåíèå ñîîòâåòñòâóþùèõ ñåìàíòè÷åñêèõ ïðàâèë, àíàëîãè÷íûõ (4.3), êîòîðûå àêêóðàòíî îïðåäåëÿþò çàïèñü ¾îïðåäåëèòü f (x) = y ¿,íåñëîæíî è ïðåäîñòàâëÿåòñÿ ÷èòàòåëþ.)(3) Ôóíêöèÿ ¾íîâñèìâîë¿, â êàêîì áû ïðàâèëå îíà íèâñòðåòèëàñü, áóäåò âûðàáàòûâàòü íåêèé àáñòðàêòíûé îáúåêò, ïðè÷¼ì ïðè êàæäîì îáðàùåíèè ê ¾íîâñèìâîë¿ ýòîòîáúåêò áóäåò îòëè÷åí îò âñåõ ïîëó÷åííûõ ïðè ïðåäøåñòâîâàâøèõ îáðàùåíèÿõ ê íîâñèìâîë.
(Ýòó ôóíêöèþ ëåãêîâûðàçèòü ïðè ïîìîùè äðóãèõ ñåìàíòè÷åñêèõ ïðàâèë, íàïðèìåð èñïîëüçóÿ àòðèáóòû l èç (2.3), ïðèíèìàþùèå â ðàçíûõ âåðøèíàõ äåðåâà ðàçíûå çíà÷åíèÿ. Ôóíêöèÿ íîâñèìâîë ñëóæèò ïîäõîäÿùèì èñòî÷íèêîì ¾ñûðüÿ¿ äëÿ ïîñòðîåíèÿ ìíîæåñòâ.)296Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâÌû âèäåëè, ÷òî ñîãëàøåíèÿ (1), (2) è (3) ìîæíî çàìåíèòü äðóãèìè ñåìàíòè÷åñêèìè êîíñòðóêöèÿìè, íå èñïîëüçóþùèìè òàêèõ ñîãëàøåíèé, ñëåäîâàòåëüíî, îíè íå ÿâëÿþòñÿ ¾áàçèñíûìè¿ äëÿ ñåìàíòèêè.
Íî îíè ÷ðåçâû÷àéíî ïîëåçíû, òàê êàê ñîîòâåòñòâóþò ïîíÿòèÿì, êîòîðûìè ÷àñòîïîëüçóþòñÿ, ïîýòîìó èõ ìîæíî ñ÷èòàòü ïðèíöèïèàëüíûìèäëÿ ìåòîäà îïèñàíèÿ ñåìàíòèêè, ïðåäñòàâëåííîãî â íàñòîÿùåé ñòàòüå. Ýôôåêò îò ââåäåíèÿ òàêèõ ñîãëàøåíèé ñîñòîèòâ òîì, ÷òî óìåíüøàåòñÿ îáùåå êîëè÷åñòâî àòðèáóòîâ, ÿâíîïðèñóòñòâóþùèõ â ïðàâèëàõ, è â òîì, ÷òî óäà¼òñÿ îáîéòèñüáåç íåîïðàâäàííî äëèííûõ ïðàâèë.Òåïåðü óæå íåñëîæíî äàòü ôîðìàëüíîå îïðåäåëåíèåñèíòàêñèñà è ñåìàíòèêè Òüþðèíãîëà.Íåòåðìèíàëüíûå ñèìâîëû :P (ïðîãðàììà), S (îïåðàòîð), L (ñïèñîê îïåðàòîðîâ), I(èäåíòèôèêàòîð), O (íàïðàâëåíèå), A (ñèìâîë àëôàâèòà),D (îïèñàíèå).Òåðìèíàëüíûå ñèìâîëû:abcdefghijklmnopqrstuvwxyz .,:;`'{}àëôàâèò ïåðåéòè íà ïå÷àòàòü åñëè ñèìâîë íà ëåíòå òî ñäâèíóòüñÿ íà îäíó êëåòêó âëåâî âïðàâîÍà÷àëüíûé ñèìâîë : pÀòðèáóòû:ÈìÿàòðèáóòàQΣq0q∞δÒèï çíà÷åíèÿÌíîæåñòâîÌíîæåñòâîÝëåìåíò ìíîæåñòâà QÝëåìåíò ìíîæåñòâà QÔóíêöèÿ, îòîáðàæàþùàÿ (Q − {q∞ }) × Σâ Σ × {−1, 0, +1} × Qìåòêà Ôóíêöèÿ, îòîáðàæàþùàÿ öåïî÷êè áóêâ âýëåìåíòû ìí-âà QÖåëü ââåäåíèÿÑîñòîÿíèÿ ïðîãðàììûÑèìâîëû ïðîãðàììûÍà÷àëüíîå ñîñòîÿíèåÊîíå÷íîå ñîñòîÿíèåÔóíêöèÿ ïåðåõîäîâÒàáëèöà ñîñòîÿíèéîïåðàòîðíûõ ìåòîêäëÿA.4.
Ïðîñòîé ÿçûê ïðîãðàììèðîâàíèÿÈìÿñèìâîëÒèï çíà÷åíèÿÔóíêöèÿ, îòîáðàæàþùàÿ öåïî÷êè áóêâ âýëåìåíòû ìíîæåñòâà Σñëåäó- Ýëåìåíò ìíîæåñòâà Qþùåå297Öåëü ââåäåíèÿÒàáëèöà ñèìâîëîâñèìâîëîâ ëåíòûäëÿÑîñòîÿíèå, íåïîñðåäñòâåííî ñëåäóþùåå çà îïåðàòîðîì èëè ñïèñêîì îïåðàòîðîâd±1Íàïðàâëåíèåòåêñò Öåïî÷êà áóêâÈäåíòèôèêàòîðíà÷à- Ýëåìåíò ìíîæåñòâà Q Ñîñòîÿíèå â íà÷àëå âûëîïîëíåíèÿ îïåðàòîðà èëèñïèñêà îïåðàòîðîâ (óíàñëåäîâàííûé àòðèáóò).Ñèíòàêñè÷åñêèå è ñåìàíòè÷åñêèå ïðàâèëà ñì. â òàáë. 1.Òàáëèöà 1.ÊîììåíòàðèéÁóêâû 1.1...1.26Èäåíòè- 2.1ôèêàòî- 2.2ðûÎïèñà- 3.1íèÿÑèíòàêñè÷åñêîåïðàâèëîA→a...A→zI→AI → IAÏðèìåðÑåìàíòè÷åñêîå ïðàâèëîòåêñò (A) = aäëÿ âñåõ áóêâ)òåêñò (A) = zòåêñò (I) = òåêñò (A)òåêñò (I) = òåêñò(I) òåêñò(A)D→àëôà- àëôàâèò îïðåäåëèòüñèìâîëâèò Imarilyn(òåêñò (I)) = íîâñèìâîë;âêëþ÷èòü ñèìâîë (òåêñò(I)) â Σ3.2.
D→ D, I àëôàâèò îïðåäåëèòüñèìâîëmarilyn, (òåêñò (I)) = íîâñèìâîë;jayne,âêëþ÷èòü ñèìâîë (òåêñòbrigitta(I)) â Σa...(òàê æåzmmarilyn298Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâS→ïå÷à- ïå÷àòàòü îïðåäåëèòü δ (íà÷àëîòàòü¾jayne¿(S), s)= ñèìâîë(òåêñò (I)),¾I¿0, ñëåäóþùèé (S)) äëÿâñåõ s ∈ Σ;ñëåäóþùèé (S) = íîâñèìâîë; âêëþ÷èòü ñëåäóþùèé (S) â Q.Îïåðà- 4.2 S→ñäâè- ñäâèíóòü- îïðåäåëèòü δ (íà÷àëîòîðíóòüñÿ ñÿ âëåâî (S), s) = (s, d(0), ñëåäóþñäâèãàÎíà íà îäíó ùèé (S) äëÿ âñåõ s ∈ Σ;îäíóêëåòêó ñëåäóþùèé (S) =êëåòêóíîâñèìâîë;âêëþ÷èòü ñëåäóþùèé(S) â Q.4.2.1 Î→âëåâî âëåâîd(O) = 1.4.2.2 Î→âïðàâî d(O) = +1.Îïåðà- 4.1òîðïå÷àòèÎïåðà- 4.3òîðïåðåõîäàÏóñòîé 4.4îïåðàòîðÓñëîâ- 5.1íûéîïåðàòîðâïðàâîS → ïå- ïåðåéòè îïðåäåëèòü δ (íà÷àëîðåéòè íà íà boston (S), s)= (s, 0, ìåòêà(òåêñòI(I)) äëÿ âñåõ s ∈ Σ; ñëåäóþùèé (S) = íîâñèìâîë; âêëþ÷èòü ñëåäóþùèé (S) â Q.ñëåäóþùèé (S) = íà÷àëî(S).S→S1→ åñëèåñëèñèìâîëíà ëåíòå¾I¿, òî S2îïðåäåëèòü δ (íà÷àëîñèìâîë (S1 ), s)= (s, 0, ìåòêà (ñëåíà ëåíòå äóþùèé (S2 )) äëÿ âñåõ s¾marilyn¿, ∈ Σ ñèìâîë (òåêñò (I));òîïå- îïðåäåëèòü δ (íà÷àëî÷àòàòü(S1 ), s)= (s, 0, ìåòêà (ñëå¾jayne¿äóþùèé (S2 )) äëÿ s =ñèìâîë (òåêñò (I)); íà÷àëî(S2 ) = íîâñèìâîë; ñëåäóþùèé (S1 ) = ñëåäóþùèé (S2 ); âêëþ÷èòü íà÷àëî (S2 ) â Q.A.4.
Ïðîñòîé ÿçûê ïðîãðàììèðîâàíèÿÏîìå- 5.2÷åííûéîïåðàòîðÑîñòàâ- 5.3íîéîïåðàòîðÑïèñîê 6.1îïåðàòîðîâ6.2Ïðîãðàììà7299S1 → ¾I¿: boston:îïðåäåëèòü ìåòêà (òåêñòS2ñäâèíóòü-(I))= íà÷àëî (S1 ): íà÷àëîñÿ âëåâî (S2 )=íà÷àëî (S1 ); ñëåäóíà îäíó þùèé (S1 )= ñëåäóþùèéêëåòêó (S2 ).S →{L}(ïå÷àòàòü íà÷àëî (L)=íà÷àëî (S);¾jayne¿ñëåäóþùèé (S) = ñëåäóþïåðåéòè ùèé (L).íà bostonL→Sïå÷àòàòü íà÷àëî (L)=íà÷àëî (S);¾jayne¿ñëåäóþùèé (L) = ñëåäóþùèé (S).L1 →L2 ; S ïå÷àòàòü íà÷àëî (L2 )=íà÷àëî (L1 );¾jayne¿íà÷àëî (S) = ñëåäóþùèéïåðåéòè (L2 ).íà boston ñëåäóþùèé (L1 ) = ñëåäóþùèé (S).Ð →D; L àëôàâèò q=íîâñèìâîë;marilyn, âêëþ÷èòü q0 â Q;jayne,íà÷àëî (L)=q0 ;birgittaq∞ = ñëåäóþùèé (L).ïå÷àòàòü¾jayne¿Îòìåòèì, ÷òî êàæäîìó îïåðàòîðó S ñîîòâåòñòâóåò äâàñîñòîÿíèÿ: íà÷àëî (S) ñîñòîÿíèå, ñîîòâåòñòâóþùåå ïåðâîé êîìàíäå, âõîäÿùåé â îïåðàòîð (åñëè òàêîâàÿ èìååòñÿ),ÿâëÿþùååñÿ óíàñëåäîâàííûì àòðèáóòîì ñèìâîëà S , è ñëåäóþùåå (S) ñîñòîÿíèå, ¾ñëåäóþùåå¿ çà îïåðàòîðîì, èëèñîñòîÿíèå, â êîòîðîå ïîïàäàåò ìàøèíà ïîñëå íîðìàëüíîãîâûïîëíåíèÿ îïåðàòîðà.
 ñëó÷àå îïåðàòîðà ïåðåõîäà, îäíàêî, ïðîãðàììà íå ïîïàä¼ò â ñîñòîÿíèå ñëåäóþùåå (S), ïîñêîëüêó äåéñòâèå îïåðàòîðà ñîñòîèò â ïåðåäà÷å óïðàâëåíèÿâ äðóãîå ìåñòî; î ñîñòîÿíèè ñëåäóþùåå (S) ìîæíî ñêàçàòü,÷òî îíî ñëåäóåò çà îïåðàòîðîì ¾ñòàòè÷åñêè¿ èëè ¾òåêñòóàëüíî¿, à íå ¾äèíàìè÷åñêè¿ â õîäå âûïîëíåíèÿ ïðîãðàììû. òàáë. 1 ñëåäóþùåå (S) ÿâëÿåòñÿ ñèíòåçèðîâàííûìàòðèáóòîì; ìîæíî ñîñòàâèòü àíàëîãè÷íûå ñåìàíòè÷åñêèå300Ïðèëîæåíèå A.
Ñåìàíòèêà ÊÑ-ÿçûêîâïðàâèëà, â êîòîðûõ àòðèáóò ñëåäóþùåå (S) áóäåò óíàñëåäîâàííûì. Ïðè ýòîì, ïðàâäà, ïðîãðàììû, âêëþ÷àþùèå ïóñòûå îïåðàòîðû, áóäóò íåñêîëüêî ìåíåå ýôôåêòèâíû (ñì.ïðàâèëî 4.4). Àíàëîãè÷íî, îáà àòðèáóòà íà÷àëî (S) è ñëåäóþùåå (S) ìîãóò áûòü ñäåëàíû ñèíòåçèðîâàííûìè, íî ýòîáóäåò ñòîèòü äîïîëíèòåëüíûõ èíñòðóêöèé â ïðîãðàììå ìàøèíû Òüþðèíãà ïðè ðåàëèçàöèè ñïèñêà îïåðàòîðîâ.Íàø ïðèìåð ìîã áû áûòü ïðîùå, åñëè áû ìû èñïîëüçîâàëè ìåíåå òðàäèöèîííóþ ôîðìó èíñòðóêöèé ìàøèíû Òüþðèíãà.
Ïðèíÿòîå íàìè îïðåäåëåíèå òðåáóåò, ÷òîáû êàæäàÿ èíñòðóêöèÿ âêëþ÷àëà äåéñòâèÿ ÷òåíèÿ, ïå÷àòè è ñäâèãà ÷èòàþùåãî óñòðîéñòâà. Ìàøèíà Òüþðèíãàïðåäñòàâëÿåòñÿ ïðè ýòîì â âèäå íåêîåé îäíî-ïëþñ-îäíîàäðåñíîé âû÷èñëèòåëüíîé ìàøèíû, â êîòîðîé êàæäàÿ èíñòðóêöèÿ îïðåäåëÿåò ìåñòîïîëîæåíèå (ñîñòîÿíèå) ñëåäóþùåé èíñòðóêöèè. Ìåòîä îïðåäåëåíèÿ ñåìàíòè÷åñêèõ ïðàâèë, èñïîëüçîâàííûé â ýòîì ïðèìåðå, ãäå àòðèáóò ñëåäóþùåå (S) ÿâëÿåòñÿ ñèíòåçèðîâàííûì, à íà÷àëî (S) óíàñëåäîâàííûì, ãîäèòñÿ è äëÿ âû÷èñëèòåëüíîé ìàøèíû èëèàâòîìàòà, â êîòîðîì n + 1-ÿ èíñòðóêöèÿ âûïîëíÿåòñÿ ïîñëå n-é.
 ýòîì ñëó÷àå (ñëåäóþùåå (S) íà÷àëî (S)) åñòü÷èñëî èíñòðóêöèé, ¾ñêîìïèëèðîâàííûõ¿ äëÿ îïåðàòîðà S .Ñîçäà¼òñÿ âïå÷àòëåíèå, ÷òî òàêîå îïðåäåëåíèå Òüþðèíãîëà ïðèáëèæàåò íàñ ê æåëàííîé öåëè: ïðèäàòü òî÷íûéñìûñë òåì ïîíÿòèÿì, êîòîðûå âñòðå÷àþòñÿ â íåôîðìàëüíîì ðóêîâîäñòâå ïî ÿçûêó äëÿ ïðîãðàììèñòà, ïðè÷¼ì ñäåëàòü ýòî íóæíî ñîâåðøåííî ôîðìàëüíî è îäíîçíà÷íî.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
