В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 41
Текст из файла (страница 41)
Äðóãèìè ñëîâàìè, ýòî îïðåäåëåíèå, âîçìîæíî, îòâå÷àåò íàøåìó îáðàçó ìûøëåíèÿ ïðè èçó÷åíèè ÿçûêà. Îïðåäåëåíèå4.1 îïåðàòîðà ïå÷àòè, íàïðèìåð, ìîæíî ëåãêî ïåðåâåñòè íàåñòåñòâåííûé ÿçûê, íàïèñàâÎïåðàòîð ìîæåò èìåòü âèä: ïå÷àòàòü ¾I¿ãäå I èäåíòèôèêàòîð. Ýòî îçíà÷àåò, ÷òî âñÿêèé ðàç ïðèâûïîëíåíèè ýòîãî îïåðàòîðà ñèìâîë íà îáîçðåâàåìîé êëåòêå ëåíòû áóäåò çàìåí¼í ñèìâîëîì, îáîçíà÷åííûì I , áåçîòíîñèòåëüíî ê òîìó, êàêîé ñèìâîë íàõîäèòñÿ â îáîçðåâàåìîéêëåòêå. Ïîñëå ýòîãî âûïîëíåíèå ïðîãðàììû ïðîäîëæèòñÿ ñA.5.
Îáñóæäåíèå301íîâîé èíñòðóêöèè, êîòîðàÿ îïðåäåëÿåòñÿ (äðóãèìè ïðàâèëàìè) êàê ñëåäóþùàÿ çà äàííûì îïåðàòîðîì¿.A.5. ÎáñóæäåíèåÈäåÿ îïðåäåëåíèÿ ñåìàíòèêè ñ ïîìîùüþ ñèíòåçèðîâàííûõ àòðèáóòîâ, ñâÿçàííûõ ñ êàæäûì íåòåðìèíàëüíûì ñèìâîëîì è ñåìàíòè÷åñêèõ ïðàâèë, ñîïîñòàâëåííûõ êàæäîìóïðàâèëó âûâîäà, ïðèíàäëåæèò Àéðîíñó [6, 7]. Ïåðâîíà÷àëüíî êàæäûé íåòåðìèíàëüíûé ñèìâîë èìåë ðîâíî îäèí àòðèáóò, íàçûâàâøèéñÿ åãî ¾òðàíñëÿöèåé¿. Ýòà èäåÿ èñïîëüçîâàëàñü Àéðîíñîì è ïîçæå äðóãèìè àâòîðàìè, îñîáåííî Ìàêëþðîì [14] ïðè ïîñòðîåíèè ¾ñèíòàêñè÷åñêè óïðàâëÿåìûõêîìïèëÿòîðîâ¿, ïåðåâîäèâøèõ ÿçûêè ïðîãðàììèðîâàíèÿ âìàøèííûé êîä.Êàê ìû âèäåëè â ðàçä.
2, ñèíòåçèðîâàííûõ àòðèáóòîâäîñòàòî÷íî (â ïðèíöèïå) äëÿ îïðåäåëåíèÿ ëþáîé ôóíêöèèíà äåðåâå âûâîäà. Íî íà ïðàêòèêå ïðèìåíåíèå íàðÿäó ñ ñèíòåçèðîâàííûìè è óíàñëåäîâàííûõ àòðèáóòîâ, êàê îïèñàíîâ äàííîé ñòàòüå, ïðèâîäèò ê çíà÷èòåëüíûì óïðîùåíèÿì.Îïðåäåëåíèå Òüþðèíãîëà, íàïðèìåð, ïîêàçûâàåò, ÷òî ëåãêî ó÷èòûâàåòñÿ ñîãëàñîâàííîñòü îïèñàíèé è èñïîëüçîâàíèéñèìâîëîâ, à òàêæå ìåæäó ìåòêàìè è îïåðàòîðàìè. Äðóãîéîáùåé îñîáåííîñòüþ ÿçûêîâ ïðîãðàììèðîâàíèÿ, îïðåäåëåíèå êîòîðîé çíà÷èòåëüíî óïðîùàåòñÿ â ðåçóëüòàòå ïðèìåíåíèÿ óíàñëåäîâàííûõ àòðèáóòîâ, ÿâëÿåòñÿ ¾áëî÷íàÿ ñòðóêòóðà¿.
Âîîáùå ãîâîðÿ, óíàñëåäîâàííûå àòðèáóòû ïîëåçíûâñÿêèé ðàç, êîãäà ÷àñòü çíà÷åíèé íåêîòîðîé êîíñòðóêöèèîïðåäåëÿåòñÿ êîíòåêñòîì, â êîòîðîì íàõîäèòñÿ ýòà êîíñòðóêöèÿ. Ìåòîä, ïðèâåä¼ííûé à ðàçä. 2, ïîêàçûâàåò,êàê ìîæíî ôîðìàëüíî îïèñûâàòü óíàñëåäîâàííûå èñèíòåçèðîâàííûå àòðèáóòû, à â ðàçä. 3 ïîêàçàíî, ÷òî ìîæíî íå ïðèíèìàòü âî âíèìàíèå ïðîáëåìó çàöèêëåííîñòè (ÿâëÿþùóþñÿ ïîòåíöèàëüíûì èñòî÷íèêîì òðóäíîñòåé ïðè èñïîëüçîâàíèè àòðèáóòîâ ðàçíûõ òèïîâ).Àâòîðó ê íàñòîÿùåìó âðåìåíè èçâåñòíî íåñêîëüêî ðàáîò, âíåñøèõ ïðèíöèïèàëüíûé âêëàä â ðåøåíèå çàäà÷è302Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâôîðìàëüíîãî îïèñàíèÿ ñåìàíòèêè ÿçûêîâ ïðîãðàììèðîâàíèÿ. Ýòî îïðåäåëåíèå Àëãîëà 60 ñðåäñòâàìè ðàñøèðåííîãîàëãîðèòìà Ìàðêîâà, äàííîå Äåáàêêåðîì [1], îïðåäåëåíèåÀëãîëà 60 ñ ïîìîùüþ λ-èñ÷èñëåíèÿ, ïðèíàäëåæàùåå Ëàíäèíó [9, 10, 11] (ñì.
òàêæå Á¼ì [2, 3], îïðåäåëåíèå ÌèêðîÀëãîëà ñ ïîìîùüþ ðåêóðñèâíûõ ôóíêöèé, ïðèìåíÿåìûõ êïðîãðàììå è ê ¾âåêòîðàì ñîñòîÿíèé¿, ïðèíàäëåæàùåå Ìàêêàðòè [12] (ñì. òàêæå Ìàêêàðòè è Ïýèíòåð [13]; îïðåäåëåíèå ÿçûêà Ýéëåð ñðåäñòâàìè ñåìàíòè÷åñêèõ ïðàâèë, ïðèìåíÿåìûõ âî âðåìÿ ñèíòàêñè÷åñêîãî àíàëèçà ïðîãðàììû,ïðåäëîæåííîå Âèðòîì è Âåáåðîì [16], è îïðåäåëåíèå ÿçûêàP L/I , äàííîå Âåíñêîé ëàáîðàòîðèåé ôèðìû IBM è îñíîâàííîå íà ðàáîòå Ìàêêàðòè è Ëàíäèíà, à òàêæå íà ïîíÿòèèàáñòðàêòíîé ìàøèíû, ââåä¼ííîì Ýëãîòîì [4, 5]. Íàèáîëååñóùåñòâåííàÿ ðàçíèöà ìåæäó ïðåäøåñòâóþùèìè ìåòîäàìèè îïèñàíèåì ÿçûêà Òüþðèíãîë, ïðèâåä¼ííûì â òàáë.
1, ñîñòîèò â òîì, ÷òî îñòàëüíûåîïðåäåëåíèÿ ïðåäñòàâëÿþò ñîáîé äîâîëüíî ñëîæíûåïðîöåññû, ïðèìåíÿåìûå êî âñåé ïðîãðàììå; ìîæíî ñêàçàòü,÷òî ÷åëîâåê, ïðåæäå ÷åì îí ïîéì¼ò îïèñàíèå ÿçûêà, äîëæåíáóäåò ïîíÿòü, êàê óñòðîåí åãî êîìïèëÿòîð. Ýòà òðóäíîñòüîñîáåííî îùóòèìà â ðàáîòå Äåáàêêåðà, îïðåäåëÿþùåãî ìàøèíó, ïîäîáíóþ Ìàðêîâñêèì àëãîðèòìàì, íî çíà÷èòåëüíîáîëåå ñëîæíóþ. Ýòà ìàøèíà èìååò îêîëî 800 êîìàíä. Íàêàæäîì øàãå âû÷èñëåíèÿ ìàøèíû íóæíî âûïîëíÿòü ïîñëåäíþþ ïðèìåíèìóþ êîìàíäó, òàê ÷òî ìû íå ìîæåì ïðîâåðèòü, íóæíî ëè âûïîëíèòü êîìàíäó íîìåð 100, äî òåõïîð, ïîêà íå óáåäèìñÿ, ÷òî îñòàëüíûå 700 êîìàíä íåïðèìåíèìû. Êðîìå òîãî, â ïðîöåññå ðàáîòû ìàøèíû ñïèñîê ïîïîëíÿåòñÿ íîâûìè êîìàíäàìè. ßñíî, ÷òî ÷èòàòåëþ ÷ðåçâû÷àéíî òðóäíî ïîíÿòü ðàáîòó òàêîé ìàøèíû èëè ôîðìàëüíî äîêàçàòü å¼ îñíîâíûå ñâîéñòâà.
Îïèñàíèå Òüþðèíãîëà,íàïðîòèâ, îïðåäåëÿåò êàæäóþ êîíñòðóêöèþ ÿçûêà òîëüêî÷åðåç å¼ ¾íåïîñðåäñòâåííîå îêðóæåíèå¿, ñâîäÿ òåì ñàìûì êìèíèìóìó âçàèìîñâÿçè ìåæäó îïðåäåëåíèÿìè ðàçíûõ ÷àñòåé ÿçûêà. Îïðåäåëåíèå ñîñòàâíûõ îïåðàòîðîâ, îïåðàòîðîâ ïåðåõîäà è ò.ä. íå âëèÿåò ñóùåñòâåííî íà îïðåäåëåíèåîïåðàòîðà ïå÷àòè; íàïðèìåð, ëþáîå èç ïðàâèë 4.1, 4.2, 4.3,A.5. Îáñóæäåíèå3034.4, 5.1, 5.3 ìîæíî âûáðîñèòü, è ïîëó÷èòñÿ ñòðîãîå îïðåäåëåíèå äðóãîãî ÿçûêà. Òàêàÿ ëîêàëèçàöèÿ è ðàçäåëåíèåñåìàíòè÷åñêèõïðàâèë ïîìîãàåò ñäåëàòü îïðåäåëåíèå áîëåå ïîíÿòíûì èêðàòêèì.Õîòÿ îïðåäåëåíèÿ îñòàëüíûõ àâòîðîâ, óïîìÿíóòûå âûøå, íå òàê ñëîæíû, êàê îïðåäåëåíèå Äåáàêêåðà, â èõ ðàáîòàõ âñ¼-òàêè ïðèñóòñòâóþò îòíîñèòåëüíî ñëîæíûå çàâèñèìîñòè ìåæäó îòäåëüíûìè ÷àñòÿìè îïðåäåëåíèÿ.
Ðàññìîòðèì, íàïðèìåð, ôîðìàëüíîå îïðåäåëåíèå ÿçûêà Ýéëåð, äàííîå Âèðòîì è Âåáåðîì [16]. Ýòî êðàòêîå îïèñàíèå âåñüìàñëîæíîãî ÿçûêà è ïîòîìó, áåçóñëîâíî, îíî ÿâëÿåòñÿ îäíèìèç íàèáîëåå óäà÷íûõ ôîðìàëüíûõ îïðåäåëåíèé. È âñ¼ æå,íåñìîòðÿ íà òî, ÷òî Âèðò è Âåáåð ïðîâåðèëè ñâî¼ îïðåäåëåíèå ñ ïîìîùüþ ìîäåëèðîâàíèÿ íà âû÷èñëèòåëüíîé ìàøèíå,âåñüìà âåðîÿòíî, ÷òî íåêîòîðûå ÷åðòû Ýéëåðà óäèâÿò åãîñîçäàòåëåé.
Ñëåäóþùàÿ ïðîãðàììà íà Ýéëåðå ñèíòàêñè÷åñêè è ñåìàíòè÷åñêè ïðàâèëüíà, õîòÿ ïîñëå ìåòêè L íèãäåíå âñòðå÷àþòñÿ äâîåòî÷èÿ:⊥ begin label L; new A; A ←0;if false then goto L else L;out 1; L; A ← A + 1; out 2;if false then go to L elseif A < 2 then go to L else out 3; L end ⊥Ðåçóëüòàòîì ðàáîòû ýòîé ïðîãðàììû áóäåò 1, 2, 2, 3!Ïðîìàõè òàêîãî ðîäà íå ÿâëÿþòñÿ íåîæèäàííîñòüþ ïðè àëãîðèòìè÷åñêîì îïðåäåëåíèè ÿçûêà. Ïðè èñïîëüçîâàíèè ìåòîäîâ ðàçä. 4 ïîäîáíûå îøèáêè ìåíåå âåðîÿòíû.Åñòü îñíîâàíèÿ óòâåðæäàòü, ÷òî íè îäíà èç ïðåäûäóùèõ ñõåì (ôîðìàëüíîãî îïðåäåëåíèÿ ñåìàíòèêè) íå â ñîñòîÿíèè äàòü òàêîãî æå êðàòêîãî è ïðîñòîãî äëÿ ïîíèìàíèÿ îïðåäåëåíèÿ Òüþðèíãîëà, êàê òî, êîòîðîå ïðåäñòàâëåíîâûøå. Êðîìå òîãî (õîòÿ äåòàëè îêîí÷àòåëüíî íå ïðîðàáîòàíû), îêàçûâàåòñÿ, ÷òî Àëãîë 60, Ýéëåð, Ìèêðî-Àëãîë èP L/1 òàêæå ìîæíî îïðåäåëèòü ìåòîäàìè ðàçä.
4, ïðè÷¼ìâñå ïðåèìóùåñòâà ïî ñðàâíåíèþ ñ îñòàëüíûìè ìåòîäàìèñîõðàíÿþòñÿ. Ïðàâäà, çäåñü àâòîð íå ìîæåò áûòü áåñïðè-304Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâñòðàñòíûì ñóäü¼é, ïîýòîìó äëÿ ïîäòâåðæäåíèÿ òàêîé òî÷êè çðåíèÿ òðåáóåòñÿ íåêîòîðûé äîïîëíèòåëüíûé îïûò.Îòìåòèì, ÷òî ñåìàíòè÷åñêèå ïðàâèëà â òîì âèäå, â êîòîðîì îíè äàíû â íàñòîÿùåé ñòàòüå, íå çàâèñÿò îò êîíêðåòíîâûáðàííîãî ìåòîäà ñèíòàêñè÷åñêîãî àíàëèçà.
Íà ñàìîì äåëå îíè ïðèâÿçàíû äàæå ê êîíêðåòíûì ôîðìàì ñèíòàêñèñà.Åäèíñòâåííîå îò ÷åãî çàâèñÿò ñåìàíòè÷åñêèå ïðàâèëà ýòîèìÿ íåòåðìèíàëà â ëåâîé ÷àñòè ñèíòàêñè÷åñêîãî ïðàâèëà èèìåíè íåòåðìèíàëîâ â ïðàâîé åãî ÷àñòè. Êîíêðåòíûå çíàêè ïóíêòóàöèè è ïîðÿäîê, â êîòîðîì íåòåðìèíàëû ðàñïîëàãàþòñÿ â ïðàâûõ ÷àñòÿõ ïðàâèë, íåñóùåñòâåííû ñ òî÷êèçðåíèÿ ñåìàíòè÷åñêèõ ïðàâèë. Òàêèì îáðàçîì, ðàññìàòðèâàåìîå çäåñü îïðåäåëåíèå ñåìàíòèêè õîðîøî ñî÷åòàåòñÿ ñèäååé Ìàêêàðòè îá ¾àáñòðàêòíîì ñèíòàêñèñå¿ [12, 13].Êîãäà ñèíòàêñèñ íåîäíîçíà÷åí â òîì ñìûñëå, ÷òî íåêîòîðûå öåïî÷êè ÿçûêà èìåþò áîëåå îäíîãî äåðåâà âûâîäà,ñåìàíòè÷åñêèå ïðàâèëà äàþò äëÿ êàæäîãî äåðåâà âûâîäàñâî¼ ¾çíà÷åíèå¿. Ïðåäïîëîæèì, íàïðèìåð, ÷òî ê ãðàììàòèêå (1.3) äîáàâëåíû ïðàâèëàL1 → BL2 ,v(L1 ) = 2l(L2 ) v(B) + V (L2 ),l(L1 ) = l(L2 ) + 1.Ãðàììàòèêà â ðåçóëüòàòå ñòàíîâèòñÿ ñèíòàêñè÷åñêèíåîäíîçíà÷íîé, íî îñòà¼òñÿ ïî-ïðåæíåìó ñåìàíòè÷åñêè îäíîçíà÷íîé, ïîñêîëüêó àòðèáóò v(N ) èìååò îäíî è òî æå çíà÷åíèå äëÿ âñåõ äåðåâüåâ âûâîäà.
Ñ äðóãîé ñòîðîíû, åñëèèçìåíèòü ïðàâèëî 5.2 îïðåäåëåíèÿ Òüþðèíãîëà ñ S → I : Síà S → S : I , ãðàììàòèêà ñòàíåò íåîäíîçíà÷íîé êàê ñèíòàêñè÷åñêè, òàê è ñåìàíòè÷åñêè.ËÈÒÅÐÀÒÓÐÀ1. de Bakker J.W. Formal definition of programminglanguages, with an approach to the definition of ALGOL60. Math. Cent. Tracts 16. Mathematical Centrum.Amsterdam, 1967.A.5. Îáñóæäåíèå3052. Böhm C. The CUCH as a formal and descriptionlanguage // Formal language description languagesfor computer programming. Proc. IFIP working Conf.Vienna (1964).
P. 266294. North Holland, 1966.3. Corrado Böhm and Wolf Cross. Introduction to theCUCH, Automata Theory / ed. by Caianiello E.R. P.3565. Academic press, 1966.4. Elgot C.C. Machine species and their computationlanguages // Formal Language Descripton Languagesfor Computer Programming. Proc. IFIP Working Conf.Vienna (1964). P. 160179. North Holland, 1966.5. Elgot C.C., Robinson A. Random-access, stored programmachines, an approach to programing languages // J.ACM 11 (1964). P. 365399.6.
Irons E.T. A sintax directed compiler for ALGOL 60//Comm. ACM 4 (1961). P. 5155.7. Irons E.T. Towards more versatile mechanicaltranslators // Proc. Sympos. Appl. Math. Vol. 15.P. 4150. Amer. Math. Soc., Providence, R.I., 1963.8. Knuth D.E. The Art of Computer Programming, I.Addison-Wesley, 1968. (Ðóññêèé ïåðåâîä: Êíóò Ä. Èñêóññòâî ïðîãðàììèðîâàíèÿ äëÿ ÝÂÌ. Ò.
1. Îñíîâíûåàëãîðèòìû. Ì.: Ìèð, 1976 ).9. Landin P.J. The mechanical evaluation of expressions //Comp. J. 6 (1964). P. 308320.10. Landin P.J. A formal description of ALGOL 60 //Formal Language Description for Computer Programming. Proc. IFIP Working Conf. Vienna (1964). P. 266294. North Holland, 1966.11. Landin P.J. A correspondence between ALGOL 60 andChurch's lambda notation // Comm. ACM 8 (1965).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
