В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 37
Текст из файла (страница 37)
 ñòàòüå èçó÷àåòñÿ âîïðîñ î òîì, êàê âûãëÿäèò ïðîöåññ âû÷èñëåíèÿ àòðèáóòîâ, êîãäà íåêîòîðûå àòðèáóòû ÿâëÿþòñÿ ¾ñèíòåçèðîâàííûìè¿, ò.å. çàâèñÿò òîëüêî îò àòðèáóòîâ ïîòîìêîâ ðàññìàòðèâàåìîãî íåòåðìèíàëà, à äðóãèå - ¾óíàñëåäî1 Knuth D.E. Semantics of Context-Free Languages, MathematicalSystems Theory, 2, 2, 1968, 127146.Knuth D.E. Semantics of Context-Free Languages: Correction,Mathematical Systems Theory, 5, 1, 1971, 179. ïåðâîíà÷àëüíîì òåêñòå àëãîðèòì òåîðåìû î ïðîâåðêå çàöèêëåííîñòè áûë íåâåðíûì, è ïîçäíåå àâòîð äàë äðóãîé åãî âàðèàíò. Ïðèâåä¼ííûé â íàñòîÿùåé êíèãå òåêñò ñêîìïèëèðîâàí èç äâóõ âûøåóêàçàííûõñòàòåé.
Ïðèì. ðåä. (Â.Ì. Êóðî÷êèíà)A.1. Ââåäåíèå277âàííûìè¿, ò.å. çàâèñÿò îò àòðèáóòîâ ïðåäêîâ äàííîãî íåòåðìèíàëà. Ïðåäñòàâëåí àëãîðèòì, ïðîâåðÿþùèé, íå ïðèâîäÿò ëè ñåìàíòè÷åñêèå ïðàâèëà ê öèêëè÷åñêîìó îïðåäåëåíèþ íåêîòîðûõ àòðèáóòîâ. Ïðèâåä¼í ïðèìåð ïðîñòîãî ÿçûêà ïðîãðàììèðîâàíèÿ, â îïðåäåëåíèè êîòîðîãî ó÷àñòâóþòêàê ñèíòåçèðîâàííûå, òàê è óíàñëåäîâàííûå àòðèáóòû. Ìåòîä îïðåäåëåíèÿ, îñíîâàííûé íà èñïîëüçîâàíèè àòðèáóòîâ,ñðàâíèâàåòñÿ ñ äðóãèìè ìåòîäàìè ôîðìàëüíîãî îïèñàíèÿñåìàíòèêè, èìåþùèìèñÿ â ëèòåðàòóðå.A.1. ÂâåäåíèåÄîïóñòèì, ÷òî íàì íóæíî äàòü òî÷íîå îïðåäåëåíèå äâîè÷íîé ñèñòåìû çàïèñè ÷èñåë.
Ýòî ìîæíî ñäåëàòü ìíîãèìèñïîñîáàìè.  äàííîì ðàçäåëå ìû ðàññìîòðèì ìåòîä, êîòîðûé ìîæåò áûòü èñïîëüçîâàí è äëÿ äðóãèõ ñèñòåì ñ÷èñëåíèÿ.  ñëó÷àå äâîè÷íîé ñèñòåìû ýòîò ìåòîä ñâîäèòñÿê îïðåäåëåíèþ, îñíîâàííîìó íà ñëåäóþùåé êîíñòåêñòíîñâîáîäíîé (ÊÑ) ãðàììàòèêå.B→0L→BN →LB→1L → LBN → L.L(1.1)Çäåñü òåðìèíàëüíûìè ñèìâîëàìè ÿâëÿþòñÿ ¾.¿, ¾0¿ è¾1¿, íåòåðìèíàëüíûìè B , L è N , îáîçíà÷àþùèå ñîîòâåòñòâåííî áèò, ñïèñîê áèòîâ è ÷èñëî. Äâîè÷íûì ÷èñëîìáóäåì ñ÷èòàòü ëþáóþ öåïî÷êó òåðìèíàëüíûõ ñèìâîëîâ, âûâîäèìóþ èç N ïðè ïîìîùè ïðàâèë (1.1).
Ýòà ãðàììàòèêàâ äåéñòâèòåëüíîñòè âûðàæàåò òîò ôàêò, ÷òî äâîè÷íîå ÷èñëî ïðåäñòàâëÿåò ñîáîé ïîñëåäîâàòåëüíîñòü èç îäíîãî èëèáîëåå íóëåé è åäèíèö, çà êîòîðîé ìîæåò ñëåäîâàòü òî÷êà è åù¼ îäíà ïîñëåäîâàòåëüíîñòü íóëåé è åäèíèö. Êðîìåòîãî, ãðàììàòèêà ïðèïèñûâàåò êàæäîìó äâîè÷íîìó ÷èñëóîïðåäåë¼ííóþ äðåâîâèäíóþ ñòðóêòóðó. Íàïðèìåð, öåïî÷êà1101.01 ïîëó÷àåò ñëåäóþùóþ ñòðóêòóðó:278Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâ³NPP³³PP³PLL.©H©HH©H©HBHBL©L©©H©HHBL©1B1©HH©H00LBB1(1.2)1Åñòåñòâåííî îïðåäåëÿòü çíà÷åíèå äâîè÷íîé çàïèñè (1.1)ñ ïîìîùüþ íåêîòîðîãî ïîøàãîâîãî ïðîöåññà, ñîïîñòàâëåííîãî å¼ ñòðóêòóðå (1.2); çíà÷åíèå âñåé äâîè÷íîé çàïèñèñòðîèòñÿ èç çíà÷åíèé îòäåëüíûõ ÷àñòåé.
Ýòî ìîæíî ñäåëàòü, ïðèïèñàâ êàæäîìó íåòåðìèíàëó àòðèáóòû ñëåäóþùèì îáðàçîì:∀ áèò B èìååò öåëî÷èñëåííûé àòðèáóò ¾çíà÷åíèå ¿,îáîçíà÷àåìûé v(B).∀ ñïèñîê áèòîâ L èìååò öåëî÷èñëåííûé àòðèáóò ¾äëèíà ¿, îáîçíà÷àåìûé l(L). ∀ ñïèñîê áèòîâ L èìååò öåëî÷èñëåííûé àòðèáóò ¾çíà÷åíèå ¿, îáîçíà÷àåìûé v(L).∀ ÷èñëî N èìååò àòðèáóò ¾çíà÷åíèå ¿, ÿâëÿþùèéñÿ ðàöèîíàëüíûì ÷èñëîì è îáîçíà÷àåìûé v(N ).(Çàìåòèì, ÷òî ó âñåõ íåòåðìèíàëîâ L ïî äâà àòðèáóòà;âîîáùå ãîâîðÿ, êàæäîìó íåòåðìèíàëó ìîæíî ïðèïèñûâàòüëþáîå æåëàåìîå ÷èñëî àòðèáóòîâ).Ãðàììàòèêó (1.1) ìîæíî òåïåðü ðàñøèðèòü òàê, ÷òîáû êàæäîìó ñèíòàêñè÷åñêîìó ïðàâèëó îòâå÷àëè ñåìàíòè÷åñêèå ïðàâèëà.B→0B→1L→BL1 → L2 BN →LN → L1 .L2v(B) = 0v(B) = 1v(L) = v(B),v(L1 ) = 2v(L2 ) + v(B),v(N ) = v(L)v(N ) = v(L1 ) + v(L2 )/2l(L2 )(1.3)l(L) = 1l(L1 ) = l(L2 ) + 1(Èíäåêñû â ÷åòâ¼ðòîì è øåñòîì ïðàâèëàõ ïðèìåíÿ-A.1.
Ââåäåíèå279þòñÿ äëÿ òîãî, ÷òîáû ðàçëè÷àòü âõîæäåíèÿ îäíîèì¼ííûõíåòåðìèíàëîâ.).  ýòèõ ñåìàíòè÷åñêèõ ïðàâèëàõ çíà÷åíèÿàòðèáóòîâ âñåõ íåòåðìèíàëîâ îïðåäåëÿþòñÿ ÷åðåç çíà÷åíèÿàòðèáóòîâ èõ íåïîñðåäñòâåííûõ ïîòîìêîâ, òàê ÷òî îêîí÷àòåëüíûå çíà÷åíèÿ îïðåäåëåíû äëÿ âñåõ àòðèáóòîâ. Ïðåäïîëàãàåòñÿ, ÷òî ñìûñë îáîçíà÷åíèé, èñïîëüçîâàííûõ äëÿ çàïèñè ñåìàíòè÷åñêèõ ïðàâèë, ïîíÿòåí. Îòìåòèì, íàïðèìåð,÷òî ñèìâîë ¾0¿ â ñåìàíòè÷åñêîì ïðàâèëå v(B) = 0 ïîíèìàåòñÿ íå òàê, êàê ñèìâîë ¾0¿ â ñèíòàêñè÷åñêîì ïðàâèëåB → 0. B ïåðâîì ñëó÷àå ¾0¿ îáîçíà÷àåò ìàòåìàòè÷åñêîåïîíÿòèå, à èìåííî ÷èñëî íóëü, âî âòîðîì íåêîòîðûé ñèìâîë, èìåþùèé ýëëèïòè÷åñêóþ ôîðìó. B êàêîì-òî ñìûñëå,òî, ÷òî ýòè äâà ñèìâîëà âûãëÿäÿò îäèíàêîâî, íå áîëåå÷åì ïðîñòîå ñîâïàäåíèå.Ñòðóêòóðó (1.2) ìîæíî ðàñøèðèòü, âûïèñàâ ÿâíî àòðèáóòû ïðè âñåõ óçëàõ.N (v=13.25)³PP³³PP³P L(v=1, l=2)L(v=13, l=4) .©H©HH©H©HL(v=6, l=3)©©HHL(v=3, l=2) B(v=0)©©HHHL(v=1, l=1) B(v=1)B(v=1)0B(v=1) L(v=0, l=1) B(v=1)1B(v=0)01(1.4)11Òàêèì îáðàçîì, ¾1101.01¿ îáîçíà÷àåò 13.25 (â äåñÿòè÷íîé çàïèñè).Òàêîé ñïîñîá îïðåäåëåíèÿ ñåìàíòèêè ÊÑ-ÿçûêîâ â ñóùíîñòè õîðîøî èçâåñòåí, òàê êàê îí óæå èñïîëüçîâàëñÿíåñêîëüêèìè àâòîðàìè.
Îäíàêî ñóùåñòâóåò âàæíîå ðàñøèðåíèå ýòîãî ìåòîäà. Èìåííî ýòî ðàñøèðåíèå è ïðåäñòàâëÿåòäëÿ íàñ èíòåðåñ.Ïðåäïîëîæèì, íàïðèìåð, ÷òî ìû õîòèì îïðåäåëèòü ñåìàíòèêó äâîè÷íîé çàïèñè äðóãèì ñïîñîáîì, áîëåå áëèçêèìê íàøåìó îáû÷íîìó å¼ ïîíèìàíèþ. Ïåðâàÿ åäèíèöà â çàïèñè ¾1101.01¿ íà ñàìîì äåëå îçíà÷àåò 8, õîòÿ â ñîîòâåòñòâèè280Ïðèëîæåíèå A. Ñåìàíòèêà ÊÑ-ÿçûêîâñ (1.4) åé ïðèïèñûâàåòñÿ çíà÷åíèå 1. Âîçìîæíî, ïîýòîìóáóäåò ëó÷øå îïðåäåëÿòü ñåìàíòèêó òàêèì îáðàçîì, ÷òîáûìåñòîïîëîæåíèå ñèìâîëà òîæå èãðàëî îïðåäåë¼ííóþ ðîëü.Ìîæíî ââåñòè ñëåäóþùèå àòðèáóòû:∀ ñèìâîë B èìååò àòðèáóò ¾çíà÷åíèå ¿, ÿâëÿþùèéñÿ ðàöèîíàëüíûì ÷èñëîì è îáîçíà÷àåìûé v(B).∀ ñèìâîë B èìååò öåëî÷èñëåííûé àòðèáóò ¾ìàñøòàá ¿,îáîçíà÷àåìûé s(B).∀ ñèìâîë L èìååò àòðèáóò ¾çíà÷åíèå ¿, ÿâëÿþùèéñÿ ðàöèîíàëüíûì ÷èñëîì è îáîçíà÷àåìûé v(L).∀ ñèìâîë L èìååò öåëî÷èñëåííûé àòðèáóò ¾äëèíà ¿, îáîçíà÷àåìûé l(L).∀ ñèìâîë L èìååò öåëî÷èñëåííûé àòðèáóò ¾ìàñøòàá ¿,îáîçíà÷àåìûé s(L).∀ ñèìâîë N èìååò àòðèáóò ¾çíà÷åíèå ¿, ïðèíèìàþùèéâ êà÷åñòâå çíà÷åíèé ðàöèîíàëüíûå ÷èñëà è îáîçíà÷àåìûév(N ).Ýòè àòðèáóòû ìîæíî îïðåäåëèòü ñëåäóþùèì îáðàçîì:Ñèíòàêñè÷åñêèåïðàâèëàÑåìàíòè÷åñêèåïðàâèëàB→0B→1L→Bv(B) = 0v(B) = 2s(B)(1.5)v(L) = v(B), s(B) = s(L),l(L) = 1v(L1 ) = v(L2 ) + v(B), s(B) = s(L1 ),s(L2 ) = s(L1 ) + 1, l(L1 ) = l(L2 ) + 1v(N ) = v(L), s(L) = 0v(N ) = v(L1 ) + v(L2 ), s(L1 ) = 0,s(L2 ) = −l(L2 )L1 → L2 BN →LN → L1 .L2Çäåñü ïðè çàïèñè ñåìàíòè÷åñêèõ ïðàâèë ïðèíÿòî ñëåäóþùåå ñîãëàøåíèå.
Ïðàâàÿ ÷àñòü êàæäîãî ïðàâèëà ïðåäñòàâëÿåò ñîáîé îïðåäåëåíèå ëåâîé ÷àñòè, òàêèì îáðàçîì,s(B) = s(L) îçíà÷àåò, ÷òî ñíà÷àëà äîëæíî áûòü âû÷èñëåíîs(L), à çàòåì ïîëó÷åííîå çíà÷åíèå ñëåäóåò ïðèñâîèòü s(B).A.1. Ââåäåíèå281Âàæíûì ñâîéñòâîì ãðàììàòèêè (1.5) ÿâëÿåòñÿ òî, ÷òîíåêîòîðûå èç àòðèáóòîâ, êîòîðûì ïðèñâàèâàþòñÿ çíà÷åíèÿ, ïðèïèñàíû íåòåðìèíàëàì, ñòîÿùèì â ïðàâîé ÷àñòè ñîîòâåòñòâóþùåãî ñèíòàêñè÷åñêîãî ïðàâèëà, â òî âðåìÿ êàêâ (1.3) àòðèáóòû ëåâûõ ÷àñòåé ñåìàíòè÷åñêèõ ïðàâèë îòíîñèëèñü òîëüêî ê íåòåðìèíàëàì, ñòîÿùèì â ëåâîé ÷àñòèñèíòàêñè÷åñêîãî ïðàâèëà.
Çäåñü ìû èñïîëüçóåì êàê ñèíòåçèðîâàííûå àòðèáóòû (âû÷èñëÿåìûå ÷åðåç àòðèáóòû ïîòîìêîâ äàííîãî íåòåðìèíàëà), òàê è óíàñëåäîâàííûå àòðèáóòû (âû÷èñëÿåìûå ÷åðåç àòðèáóòû ïðåäêîâ). Ñèíòåçèðîâàííûå àòðèáóòû âû÷èñëÿþòñÿ â äðåâîâèäíîé ñòðóêòóðå ñíèçó ââåðõ, à óíàñëåäîâàííûå ñâåðõóâíèç. Ãðàììàòèêà (1.5) âêëþ÷àåò ñèíòåçèðîâàííûå àòðèáóòû v(B), v(L), l(L), v(N ) è óíàñëåäîâàííûå àòðèáóòû s(B)è s(L), òàê ÷òî ïðè èõ âû÷èñëåíèè íåîáõîäèìî ïðîõîäèòüïî äåðåâó â îáîèõ íàïðàâëåíèÿõ.
Âû÷èñëåíèå íà ñòðóêòóðå,ñîîòâåòñòâóþùåé öåïî÷êå 1101.01, èìååò âèä:N (v=13.25)ÃÃ````ÃÃÃ`L(v=13, l=4, s=0) .L(v=.25, l=2, s=-2)©HH©©HH©H s=-2)L(v=12, l=3, s=1) B(v=1, s=0) L(v=0, l=1, s=-1) B(v=.25,PHH©© PPL(v=12, l=2, s=2) B(v=0, s=1) 1B(v=0, s=-1) 1PHH©© PP(1.6)0L(v=8, l=1, s=3) B(v=4, s=2) 0B(v=1, s=3)11Ìîæíî çàìåòèòü, ÷òî àòðèáóòû ¾äëèíà¿ ñèìâîëîâ L,ñòîÿùèõ ñïðàâà îò òî÷êè, äîëæíû áûòü âû÷èñëåíû ñíèçóââåðõ äî òîãî, êàê áóäóò âû÷èñëåíû (ñâåðõó âíèç) àòðèáóòû¾ìàñøòàá¿ è àòðèáóòû ¾çíà÷åíèå¿ (ñíèçó ââåðõ).Ãðàììàòèêà (1.5), âåðîÿòíî, íå ÿâëÿåòñÿ ¾íàèëó÷øåéâîçìîæíîé¿ ãðàììàòèêîé äëÿ ñèñòåìû äâîè÷íîé çàïèñè,íî ïîõîæå, ÷òî îíà ëó÷øå ñîãëàñóåòñÿ ñ íàøåé èíòóèöèåé,÷åì ãðàììàòèêà (1.3). (Ãðàììàòèêà, êîòîðàÿ áîëåå òî÷íîñîîòâåòñòâóåò íàøåìó òðàäèöèîííîìó òîëêîâàíèþ äâîè÷íîé íîòàöèè, ñîäåðæèò äðóãîå ìíîæåñòâî ïðàâèë âûâîäà.282Ïðèëîæåíèå A.
Ñåìàíòèêà ÊÑ-ÿçûêîâÝòè ïðàâèëà ñîïîñòàâëÿþò öåïî÷êå áèòîâ ñïðàâà îò òî÷êè èíóþ ñòðóêòóðó, âñëåäñòâèå ÷åãî àòðèáóò ¾äëèíà¿, íåèãðàþùèé ïðèíöèïèàëüíîé ðîëè, ñòàíîâèòñÿ íåíóæíûì.)Íàø èíòåðåñ ê ãðàììàòèêå (1.5) âûçâàí íå òåì, ÷òî îíàïðåäñòàâëÿåò ñîáîé èäåàëüíîå îïðåäåëåíèå äâîè÷íîé ñèñòåìû çàïèñè, à òåì, ÷òî îíà äåìîíñòðèðóåò âçàèìîäåéñòâèåóíàñëåäîâàííûõ è ñèíòåçèðîâàííûõ àòðèáóòîâ. Òîò ôàêò,÷òî ñåìàíòè÷åñêèå ïðàâèëà, ïîäîáíûå ïðàâèëàì â (1.5), íåïðèâîäÿò ê çàöèêëåííîñòè îïðåäåëåíèÿ àòðèáóòîâ, íå ÿâëÿåòñÿ î÷åâèäíûì, ïîñêîëüêó çäåñü àòðèáóòû âû÷èñëÿþòñÿ íå ïðè îäíîêðàòíîì îáõîäå äåðåâà â îäíîì íàïðàâëåíèè.Àëãîðèòì, ïðîâåðÿþùèé ñåìàíòè÷åñêèå ïðàâèëà íà çàöèêëåííîñòü, áóäåò îïèñàí íèæå.Âàæíîñòü óíàñëåäîâàííûõ àòðèáóòîâ ñîñòîèò â òîì,÷òî îíè åñòåñòâåííî âîçíèêàþò â ïðàêòèêå è â î÷åâèäíîìñìûñëå ¾äâîéñòâåííû¿ ñèíòåçèðîâàííûì àòðèáóòàì.
Õîòÿ äëÿ îïðåäåëåíèÿ ñìûñëà äâîè÷íîé çàïèñè äîñòàòî÷íîòîëüêî ñèíòåçèðîâàííûõ àòðèáóòîâ, ñóùåñòâóåò ðÿä ÿçûêîâ, äëÿ êîòîðûõ òàêîå îãðàíè÷åíèå ïðèâîäèò ê íåóêëþæåìó è íååñòåñòâåííîìó îïðåäåëåíèþ ñåìàíòèêè. Ñèòóàöèè,êîãäà âñòðå÷àþòñÿ è óíàñëåäîâàííûå, è ñèíòåçèðîâàííûåàòðèáóòû, ïðåäñòàâëÿþò ñîáîé òå ñàìûå ñëó÷àè, êîòîðûåâ ïðåäøåñòâóþùèõ îïðåäåëåíèÿõ ñåìàíòèêè âûçûâàëè ñåðü¼çíûå òðóäíîñòè.A.2. Ôîðìàëüíûå ñâîéñòâàÏðèäàäèì òåïåðü èäåå èñïîëüçîâàíèÿ ñèíòåçèðîâàííûõè óíàñëåäîâàííûõ àòðèáóòîâ áîëåå òî÷íóþ è áîëåå îáùóþôîðìó.Ïóñòü èìååòñÿ ÊÑ-ãðàììàòèêà G = (V, N, S, P ), ãäåV (êîíå÷íûé) àëôàâèò òåðìèíàëüíûõ è íåòåðìèíàëüíûõñèìâîëîâ; N ⊆ V ìíîæåñòâî íåòåðìèíàëüíûõ ñèìâîëîâ;S ∈ N ¾íà÷àëüíûé¿ ñèìâîë, íå âõîäÿùèé â ïðàâûå ÷àñòèïðàâèë, è P ìíîæåñòâî ïðàâèë.Ñåìàíòè÷åñêèå ïðàâèëà äîïîëíÿþò G ñëåäóþùèì îáðàçîì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
