В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 8
Текст из файла (страница 8)
Åñëè âûäåëåííàÿëåêñåìà ÿâëÿåòñÿ êëþ÷åâûì ñëîâîì, òî âûäà¼òñÿ ïðèçíàêñîîòâåòñòâóþùåãî êëþ÷åâîãî ñëîâà. Åñëè âûäåëåííàÿ ëåêñåìà ÿâëÿåòñÿ èäåíòèôèêàòîðîì âûäà¼òñÿ ïðèçíàê èäåíòèôèêàòîðà, à ñàì èäåíòèôèêàòîð ñîõðàíÿåòñÿ îòäåëüíî.Íàêîíåö, åñëè âûäåëåííàÿ ëåêñåìà ïðèíàäëåæèò êàêîìóëèáî èç äðóãèõ êëàññîâ ëåêñåì (íàïðèìåð, ëåêñåìà ïðåäñòàâëÿåò ñîáîé ÷èñëî, ñòðîêó è ò.ä.), òî âûäà¼òñÿ ïðèçíàêñîîòâåòñòâóþùåãî êëàññà, à çíà÷åíèå ëåêñåìû ñîõðàíÿåòñÿîòäåëüíî.Ëåêñè÷åñêèé àíàëèçàòîð ìîæåò áûòü êàê ñàìîñòîÿòåëüíîé ôàçîé òðàíñëÿöèè, òàê è ïîäïðîãðàììîé, ðàáîòàþùåéïî ïðèíöèïó ¾äàé ëåêñåìó¿.  ïåðâîì ñëó÷àå (ðèñ. 3.1.,à) âûõîäîì àíàëèçàòîðà ÿâëÿåòñÿ ôàéë ëåêñåì, âî âòîðîì (ðèñ. 3.1., á) ëåêñåìà âûäà¼òñÿ ïðè êàæäîì îáðàùåíèè ê àíàëèçàòîðó (ïðè ýòîì, êàê ïðàâèëî, ïðèçíàê êëàññà ëåêñåìû âîçâðàùàåòñÿ êàê ðåçóëüòàò ôóíêöèè ¾ëåêñè÷åñêèé àíàëèçàòîð¿, à çíà÷åíèå ëåêñåìû ïåðåäà¼òñÿ ÷åðåçãëîáàëüíóþ ïåðåìåííóþ).
Ñ òî÷êè çðåíèÿ îáðàáîòêè çíà÷åíèé ëåêñåì, àíàëèçàòîð ìîæåò ëèáî ïðîñòî âûäàâàòü çíà÷åíèå êàæäîé ëåêñåìû, ïðè ýòîì ïîñòðîåíèå òàáëèö îáúåê-46Ãëàâà 3. Ëåêñè÷åñêèé àíàëèçòîâ (èäåíòèôèêàòîðîâ, ñòðîê, ÷èñåë è ò.ä.) ïåðåíîñèòñÿ íàáîëåå ïîçäíèå ôàçû, ëèáî îí ìîæåò ñàìîñòîÿòåëüíî ñòðîèòü òàáëèöû îáúåêòîâ.  ýòîì ñëó÷àå â êà÷åñòâå çíà÷åíèÿëåêñåìû âûäà¼òñÿ óêàçàòåëü íà âõîä â ñîîòâåòñòâóþùóþòàáëèöó.LbiAgZq_gb_KbglZgZebaZlhjLbie_dk_fuAgZq_gb_LZ[ebpZE_dkZgZebaZlhjZ[Ðèñ.
3.1.Ðàáîòà ëåêñè÷åñêîãî àíàëèçàòîðà çàäà¼òñÿ íåêîòîðûìêîíå÷íûì àâòîìàòîì. Îäíàêî, íåïîñðåäñòâåííîå îïèñàíèåêîíå÷íîãî àâòîìàòà íåóäîáíî ñ ïðàêòè÷åñêîé òî÷êè çðåíèÿ. Ïîýòîìó äëÿ çàäàíèÿ ëåêñè÷åñêîãî àíàëèçàòîðà, êàêïðàâèëî, èñïîëüçóåòñÿ ëèáî ðåãóëÿðíîå âûðàæåíèå, ëèáîïðàâîëèíåéíàÿ ãðàììàòèêà. Âñå òðè ôîðìàëèçìà (êîíå÷íûõ àâòîìàòîâ, ðåãóëÿðíûõ âûðàæåíèé è ïðàâîëèíåéíûõãðàììàòèê) èìåþò îäèíàêîâóþ âûðàçèòåëüíóþ ìîùíîñòü. ÷àñòíîñòè, ïî ðåãóëÿðíîìó âûðàæåíèþ èëè ïðàâîëèíåéíîé ãðàììàòèêå ìîæíî ñêîíñòðóèðîâàòü êîíå÷íûé àâòîìàò, ðàñïîçíàþùèé òîò æå ÿçûê.3.1. Ðåãóëÿðíûå ìíîæåñòâà è âûðàæåíèÿÂâåä¼ì ïîíÿòèå ðåãóëÿðíîãî ìíîæåñòâà, èãðàþùåãîâàæíóþ ðîëü â òåîðèè ôîðìàëüíûõ ÿçûêîâ.3.1. Ðåãóëÿðíûå ìíîæåñòâà è âûðàæåíèÿ47Ðåãóëÿðíîå ìíîæåñòâî â àëôàâèòå T îïðåäåëÿåòñÿ ðåêóðñèâíî ñëåäóþùèì îáðàçîì:(1) ∅ (ïóñòîå ìíîæåñòâî) ðåãóëÿðíîå ìíîæåñòâî â àëôàâèòå T ;(2) {e} ðåãóëÿðíîå ìíîæåñòâî â àëôàâèòå T (e ïóñòàÿöåïî÷êà);(3) {a} ðåãóëÿðíîå ìíîæåñòâî â àëôàâèòå T äëÿ êàæäîãî a ∈ T ;(4) åñëè P è Q ðåãóëÿðíûå ìíîæåñòâà â àëôàâèòå T ,òî ðåãóëÿðíûìè ÿâëÿþòñÿ è ìíîæåñòâà(à) P ∪ Q (îáúåäèíåíèå),(á) P Q (êîíêàòåíàöèÿ, òî åñòü ìíîæåñòâî {pq|p ∈P, q ∈ Q}),∞S(â) P ∗ (èòåðàöèÿ: P ∗ =P n );n=0(5) íè÷òî äðóãîå íå ÿâëÿåòñÿ ðåãóëÿðíûì ìíîæåñòâîì âàëôàâèòå T .Èòàê, ìíîæåñòâî â àëôàâèòå T ðåãóëÿðíî òîãäà è òîëüêî òîãäà, êîãäà îíî ëèáî ∅, ëèáî {e}, ëèáî {a} äëÿ íåêîòîðîãî a ∈ T , ëèáî åãî ìîæíî ïîëó÷èòü èç ýòèõ ìíîæåñòâïðèìåíåíèåì êîíå÷íîãî ÷èñëà îïåðàöèé îáúåäèíåíèÿ, êîíêàòåíàöèè è èòåðàöèè.Ïðèâåä¼ííîå âûøå îïðåäåëåíèå ðåãóëÿðíîãî ìíîæåñòâàïîçâîëÿåò ââåñòè ñëåäóþùóþ óäîáíóþ ôîðìó åãî çàïèñè,íàçûâàåìóþ ðåãóëÿðíûì âûðàæåíèåì.Ðåãóëÿðíîå âûðàæåíèå â àëôàâèòå T è îáîçíà÷àåìîå èìðåãóëÿðíîå ìíîæåñòâî â àëôàâèòå T îïðåäåëÿþòñÿ ðåêóðñèâíî ñëåäóþùèì îáðàçîì:(1) ∅ ðåãóëÿðíîå âûðàæåíèå, îáîçíà÷àþùåå ðåãóëÿðíîå ìíîæåñòâî ∅;(2) e ðåãóëÿðíîå âûðàæåíèå, îáîçíà÷àþùåå ðåãóëÿðíîåìíîæåñòâî {e};(3) a ðåãóëÿðíîå âûðàæåíèå, îáîçíà÷àþùåå ðåãóëÿðíîåìíîæåñòâî {a};48Ãëàâà 3.
Ëåêñè÷åñêèé àíàëèç(4) åñëè p è q ðåãóëÿðíûå âûðàæåíèÿ, îáîçíà÷àþùèåðåãóëÿðíûå ìíîæåñòâà P è Q ñîîòâåòñòâåííî, òî(à) (p|q) ðåãóëÿðíîå âûðàæåíèå, îáîçíà÷àþùåå ðåãóëÿðíîå ìíîæåñòâî P ∪ Q,(á) (pq) ðåãóëÿðíîå âûðàæåíèå, îáîçíà÷àþùåå ðåãóëÿðíîå ìíîæåñòâî P Q,(â) (p∗ ) ðåãóëÿðíîå âûðàæåíèå, îáîçíà÷àþùåå ðåãóëÿðíîå ìíîæåñòâî P ∗ ;(5) íè÷òî äðóãîå íå ÿâëÿåòñÿ ðåãóëÿðíûì âûðàæåíèåì âàëôàâèòå T .Ìû áóäåì îïóñêàòü ëèøíèå ñêîáêè â ðåãóëÿðíûõ âûðàæåíèÿõ, äîãîâîðèâøèñü î òîì, ÷òî îïåðàöèÿ èòåðàöèèèìååò íàèâûñøèé ïðèîðèòåò, çàòåì èä¼ò îïåðàöèè êîíêàòåíàöèè, íàêîíåö, îïåðàöèÿ îáúåäèíåíèÿ èìååò íàèìåíüøèéïðèîðèòåò.Êðîìå òîãî, ìû áóäåì ïîëüçîâàòüñÿ çàïèñüþ p+ äëÿ îáîçíà÷åíèÿ pp∗ . Òàêèì îáðàçîì, çàïèñü (a|((ba)(a∗ ))) ýêâèâàëåíòíà a|ba+ .Òàêæå, ìû áóäåì èñïîëüçîâàòü çàïèñü L(r) äëÿ ðåãóëÿðíîãî ìíîæåñòâà, îáîçíà÷àåìîãî ðåãóëÿðíûì âûðàæåíèåì r.Ïðèìåð 3.1.
Íåñêîëüêî ïðèìåðîâ ðåãóëÿðíûõ âûðàæåíèéè îáîçíà÷àåìûõ èìè ðåãóëÿðíûõ ìíîæåñòâ:à) a(e|a)|b îáîçíà÷àåò ìíîæåñòâî {a, b, aa};á) a(a|b)∗ îáîçíà÷àåò ìíîæåñòâî âñåâîçìîæíûõ öåïî÷åê,ñîñòîÿùèõ èç a è b, íà÷èíàþùèõñÿ ñ a;â) (a|b)∗ (a|b)(a|b)∗ îáîçíà÷àåò ìíîæåñòâî âñåõ íåïóñòûõ öåïî÷åê, ñîñòîÿùèõ èç a è b, òî åñòü ìíîæåñòâî {a, b}+ ;ã) ((0|1)(0|1)(0|1))∗ îáîçíà÷àåò ìíîæåñòâî âñåõ öåïî÷åê, ñîñòîÿùèõ èç íóëåé è åäèíèö, äëèíû êîòîðûõ äåëÿòñÿ íà 3.ßñíî, ÷òî äëÿ êàæäîãî ðåãóëÿðíîãî ìíîæåñòâà ìîæíî íàéòè ðåãóëÿðíîå âûðàæåíèå, îáîçíà÷àþùåå ýòî ìíîæåñòâî, è íàîáîðîò.
Áîëåå òîãî, äëÿ êàæäîãî ðåãóëÿðíîãîìíîæåñòâà ñóùåñòâóåò áåñêîíå÷íî ìíîãî îáîçíà÷àþùèõ åãîðåãóëÿðíûõ âûðàæåíèé.3.1. Ðåãóëÿðíûå ìíîæåñòâà è âûðàæåíèÿ49Áóäåì ãîâîðèòü, ÷òî ðåãóëÿðíûå âûðàæåíèÿ ðàâíû èëèýêâèâàëåíòíû (=), åñëè îíè îáîçíà÷àþò îäíî è òî æå ðåãóëÿðíîå ìíîæåñòâî.Ñóùåñòâóþò àëãåáðàè÷åñêèå çàêîíû, ïîçâîëÿþùèå îñóùåñòâëÿòü ýêâèâàëåíòíîå ïðåîáðàçîâàíèå ðåãóëÿðíûõ âûðàæåíèé.Ëåììà.
Ïóñòü p, q è r ðåãóëÿðíûå âûðàæåíèÿ. Òîãäàñïðàâåäëèâû ñëåäóþùèå ñîîòíîøåíèÿ:(1) p|q = q|p;(7)pe = ep = p;(2) ∅∗ = e;(8)∅p = p∅ = ∅;(3) p|(q|r) = (p|q)|r;(9)p∗ = p|p∗ ;(4) p(qr) = (pq)r;(10) (p∗ )∗ = p∗ ;(5) p(q|r) = pq|pr;(11) p|p = p;(6) (p|q)r = pr|qr;(12) p|∅ = p.Ñëåäñòâèå. Äëÿ ëþáîãî ðåãóëÿðíîãî âûðàæåíèÿ ñóùåñòâóåò ýêâèâàëåíòíîå ðåãóëÿðíîå âûðàæåíèå, êîòîðîåëèáî åñòü ∅, ëèáî íå ñîäåðæèò â ñâîåé çàïèñè ∅. äàëüíåéøåì áóäåì ðàññìàòðèâàòü òîëüêî ðåãóëÿðíûåâûðàæåíèÿ, íå ñîäåðæàùèå â ñâîåé çàïèñè ∅.Ïðè ïðàêòè÷åñêîì îïèñàíèè ëåêñè÷åñêèõ ñòðóêòóð áûâàåò ïîëåçíî ñîïîñòàâëÿòü ðåãóëÿðíûì âûðàæåíèÿì íåêîòîðûå èìåíà, è ññûëàòüñÿ íà íèõ ïî ýòèì èìåíàì.
Äëÿ îïðåäåëåíèÿ òàêèõ èì¼í ìû áóäåì èñïîëüçîâàòü çàïèñü âèäàd1 = r1d2 = r2...dn = rnãäå di ðàçëè÷íûå èìåíà, à êàæäîå ri ðåãóëÿðíîå âûðàæåíèå íàä ñèìâîëàìè T ∪{d1 , d2 , . . . , di−1 }, òî åñòü ñèìâîëàìè îñíîâíîãî àëôàâèòà è ðàíåå îïðåäåë¼ííûìè ñèìâîëàìè(èìåíàìè). Òàêèì îáðàçîì, äëÿ ëþáîãî ri ìîæíî ïîñòðîèòü ðåãóëÿðíîå âûðàæåíèå íàä T , ïîâòîðíî çàìåíÿÿ èìåíàðåãóëÿðíûõ âûðàæåíèé íà îáîçíà÷àåìûå èìè ðåãóëÿðíûåâûðàæåíèÿ.Ïðèìåð 3.2. Íåñêîëüêî ïðèìåðîâ èñïîëüçîâàíèÿ èì¼í äëÿîáîçíà÷åíèÿ ðåãóëÿðíûõ âûðàæåíèé.50Ãëàâà 3.
Ëåêñè÷åñêèé àíàëèçà) Ðåãóëÿðíîå âûðàæåíèå äëÿ ìíîæåñòâà èäåíòèôèêàòîðîâ.Letter = a|b|c| . . . |x|y|zDigit = 0|1| . . . |9Identif ier = Letter(Letter|Digit)∗á) Ðåãóëÿðíîå âûðàæåíèå äëÿ ìíîæåñòâà ÷èñåë â äåñÿòè÷íîéçàïèñè.Digit = 0|1| . . . |9Integer = Digit+F raction = .Integer|eExponent = (E(+| − |e)Integer)|eN umber = Integer F raction Exponent3.2.
Êîíå÷íûå àâòîìàòûÐåãóëÿðíûå âûðàæåíèÿ, ââåä¼ííûå ðàíåå, ñëóæàò äëÿîïèñàíèÿ ðåãóëÿðíûõ ìíîæåñòâ. Äëÿ ðàñïîçíàâàíèÿ ðåãóëÿðíûõ ìíîæåñòâ ñëóæàò êîíå÷íûå àâòîìàòû.Íåäåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò (ÍÊÀ) ïîîïðåäåëåíèþ åñòü ïÿò¼ðêà M = (Q, T, D, q0 , F ), ãäå(1) Q êîíå÷íîå ìíîæåñòâî ñîñòîÿíèé;(2) T êîíå÷íîå ìíîæåñòâî äîïóñòèìûõ âõîäíûõ ñèìâîëîâ (âõîäíîé àëôàâèò);(3) D ôóíêöèÿ ïåðåõîäîâ (îòîáðàæàþùàÿ ìíîæåñòâîQ×(T ∪{e}) âî ìíîæåñòâî ïîäìíîæåñòâ ìíîæåñòâà Q),îïðåäåëÿþùàÿ ïîâåäåíèå óïðàâëÿþùåãî óñòðîéñòâà;(4) q0 ∈ Q íà÷àëüíîå ñîñòîÿíèå óïðàâëÿþùåãî óñòðîéñòâà;(5) F ⊆ Q ìíîæåñòâî çàêëþ÷èòåëüíûõ ñîñòîÿíèé.Ðàáîòà êîíå÷íîãî àâòîìàòà ïðåäñòàâëÿåò ñîáîé íåêîòîðóþ ïîñëåäîâàòåëüíîñòü øàãîâ, èëè òàêòîâ. Òàêò îïðåäåëÿåòñÿ òåêóùèì ñîñòîÿíèåì óïðàâëÿþùåãî óñòðîéñòâà èâõîäíûì ñèìâîëîì, îáîçðåâàåìûì â äàííûé ìîìåíò âõîäíîé ãîëîâêîé.
Ñàì øàã ñîñòîèò èç èçìåíåíèÿ ñîñòîÿíèÿ è,âîçìîæíî, ñäâèãà âõîäíîé ãîëîâêè íà îäíó ÿ÷åéêó âïðàâî(ðèñ. 3.2.).3.2. Êîíå÷íûå àâòîìàòû51Khklhygb_IjhqblZggZyqZklv\oh^ghcp_ihqdbDL_dmsbc\oh^ghckbf\heG_ijhqblZggZyqZklv\oh^ghcp_ihqdbÐèñ. 3.2.Íåäåòåðìèíèçì àâòîìàòà çàêëþ÷àåòñÿ â òîì, ÷òî, âîïåðâûõ, íàõîäÿñü â íåêîòîðîì ñîñòîÿíèè è îáîçðåâàÿ òåêóùèé ñèìâîë, àâòîìàò ìîæåò ïåðåéòè â îäíî èç, âîîáùåãîâîðÿ, íåñêîëüêèõ âîçìîæíûõ ñîñòîÿíèé, è âî-âòîðûõ, àâòîìàò ìîæåò äåëàòü ïåðåõîäû ïî e.Ïóñòü M = (Q, T, D, q0 , F ) ÍÊÀ.
Êîíôèãóðàöèåé àâòîìàòà M íàçûâàåòñÿ ïàðà (q, w) ∈ Q × T ∗ , ãäå q òåêóùååñîñòîÿíèå óïðàâëÿþùåãî óñòðîéñòâà, à w öåïî÷êà ñèìâîëîâ íà âõîäíîé ëåíòå, ñîñòîÿùàÿ èç ñèìâîëà ïîä ãîëîâêîéè âñåõ ñèìâîëîâ ñïðàâà îò íåãî. Êîíôèãóðàöèÿ (q0 , w) íàçûâàåòñÿ íà÷àëüíîé, à êîíôèãóðàöèÿ (q, e), ãäå q ∈ F çàêëþ÷èòåëüíîé (èëè äîïóñêàþùåé). Òàêòîì àâòîìàòà Míàçûâàåòñÿ áèíàðíîå îòíîøåíèå `, îïðåäåë¼ííîå íà êîíôèãóðàöèÿõ M ñëåäóþùèì îáðàçîì: åñëè p ∈ D(q, a), ãäåa ∈ T ∪ {e}, òî (q, aw) ` (p, w) äëÿ âñåõ w ∈ T ∗ .Áóäåì îáîçíà÷àòü ñèìâîëîì `+ (`∗ ) òðàíçèòèâíîå (ðåôëåêñèâíî-òðàíçèòèâíîå) çàìûêàíèå îòíîøåíèÿ `.Áóäåì ãîâîðèòü, ÷òî àâòîìàò M äîïóñêàåò öåïî÷êó w,åñëè (q0 , w) `∗ (q, e) äëÿ íåêîòîðîãî q ∈ F . ßçûêîì, äîïóñêàåìûì, (ðàñïîçíàâàåìûì, îïðåäåëÿåìûì) àâòîìàòîì M ,(îáîçíà÷àåòñÿ L(M )), íàçûâàåòñÿ ìíîæåñòâî âõîäíûõ öåïî÷åê, äîïóñêàåìûõ àâòîìàòîì M .
Òî åñòü,52Ãëàâà 3. Ëåêñè÷åñêèé àíàëèçL(M ) = {w|w ∈ T ∗ è (q0 , w) `∗ (q, e)äëÿ íåêîòîðîãî q ∈ F }.Âàæíûì ÷àñòíûì ñëó÷àåì íåäåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ÿâëÿåòñÿ äåòåðìèíèðîâàííûé êîíå÷íûéàâòîìàò, êîòîðûé íà êàæäîì òàêòå ðàáîòû èìååò âîçìîæíîñòü ïåðåéòè íå áîëåå ÷åì â îäíî ñîñòîÿíèå è íå ìîæåòäåëàòü ïåðåõîäû ïî e.Ïóñòü M = (Q, T, D, q0 , F ) ÍÊÀ. Áóäåì íàçûâàòü Mäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì (ÄÊÀ), åñëèâûïîëíåíû ñëåäóþùèå äâà óñëîâèÿ:(1) D(q, e) = ∅ äëÿ ëþáîãî q ∈ Q, è(2) D(q, a) ñîäåðæèò íå áîëåå îäíîãî ýëåìåíòà äëÿ ëþáûõq ∈ Q è a ∈ T.Òàê êàê ôóíêöèÿ ïåðåõîäîâ ÄÊÀ ñîäåðæèò íå áîëåå îäíîãî ýëåìåíòà äëÿ ëþáîé ïàðû àðãóìåíòîâ, äëÿ ÄÊÀ ìûáóäåì ïîëüçîâàòüñÿ çàïèñüþ D(q, a)=p âìåñòî D(q, a)={p}.Êîíå÷íûé àâòîìàò ìîæåò áûòü èçîáðàæåí ãðàôè÷åñêè ââèäå äèàãðàììû, ïðåäñòàâëÿþùåé ñîáîé îðèåíòèðîâàííûéãðàô, â êîòîðîì êàæäîìó ñîñòîÿíèþ ñîîòâåòñòâóåò âåðøèíà, à äóãà, ïîìå÷åííàÿ ñèìâîëîì a ∈ T ∪ {e}, ñîåäèíÿåò äâåâåðøèíû p è q , åñëè p ∈ D(q, a).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
