В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 9
Текст из файла (страница 9)
Íà äèàãðàììå âûäåëÿþòñÿíà÷àëüíîå è çàêëþ÷èòåëüíûå ñîñòîÿíèÿ (â ïðèìåðàõ íèæå,ñîîòâåòñòâåííî, âõîäÿùåé ñòðåëêîé è äâîéíûì êîíòóðîì).Ïðèìåð 3.3. Ïóñòü L = L(r), ãäå r = (a|b)∗ a(a|b)(a|b).à) Íåäåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò M , äîïóñêàþùèé ÿçûê L:M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}},ãäå ôóíêöèÿ ïåðåõîäîâ D îïðåäåëÿåòñÿ òàê:D(1, a) = {1, 2}, D(3, a) = {4},D(1, b) = {1},D(2, b) = {3},D(2, a) = {3},D(3, b) = {4}.Äèàãðàììà àâòîìàòà ïðèâåäåíà íà ðèñ. 3.3. à.á) Äåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò M , äîïóñêàþùèéÿçûê L:M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}},3.2. Êîíå÷íûå àâòîìàòû53ãäå ôóíêöèÿ ïåðåõîäîâ D îïðåäåëÿåòñÿ òàê:D(1, a) = 2, D(5, a) = 8,D(1, b) = 1, D(5, b) = 6,D(2, a) = 4, D(6, a) = 2,D(2, b) = 7, D(6, b) = 1,D(3, a) = 3, D(7, a) = 8,D(3, b) = 5, D(7, b) = 6,D(4, a) = 3, D(8, a) = 4,D(4, b) = 5, D(8, b) = 7.Äèàãðàììà àâòîìàòà ïðèâåäåíà íà ðèñ.
3.3. á.EDDDEDEEEDDEZDDEDEEDDEDE[Ðèñ. 3.3.Ïðèìåð 3.4. Äèàãðàììà àâòîìàòà, äîïóñêàþùåãî ìíîæåñòâî ÷èñåë â äåñÿòè÷íîé çàïèñè, ïðèâåäåíà íà ðèñ. 3.4.Ïðèìåð 3.5. Àíàëèç öåïî÷åê.à) Ïðè àíàëèçå öåïî÷êè w = ababa àâòîìàò èç ïðèìåðà 3.3,à, ìîæåò ñäåëàòü ñëåäóþùóþ ïîñëåäîâàòåëüíîñòü òàêòîâ:(1, ababa) ` (1, baba) ` (1, aba) ` (2, ba) ` (3, a) ` (4, e).Ñîñòîÿíèå 4 ÿâëÿåòñÿ çàêëþ÷èòåëüíûì, îòñþäà, öåïî÷êàw äîïóñêàåòñÿ ýòèì àâòîìàòîì.á) Ïðè àíàëèçå öåïî÷êè w = ababab àâòîìàò èç ïðèìåðà 3.3,á, äîëæåí ñäåëàòü ñëåäóþùóþ ïîñëåäîâàòåëüíîñòü òàêòîâ:54Ãëàâà 3.
Ëåêñè÷åñêèé àíàëèç'LJLW('LJLW'LJLW'LJLW('LJLW 'LJLW'LJLWÐèñ. 3.4.(1, ababab) ` (2, babab) ` (7, abab) ` (8, bab) ` (7, ab) `(8, b) ` (7, e).Òàê êàê ñîñòîÿíèå 7 íå ÿâëÿåòñÿ çàêëþ÷èòåëüíûì, öåïî÷êà w íå äîïóñêàåòñÿ ýòèì àâòîìàòîì.3.3. Àëãîðèòìû ïîñòðîåíèÿ êîíå÷íûõ àâòîìàòîâ3.3.1. Ïîñòðîåíèå íåäåòåðìèíèðîâàííîãîêîíå÷íîãî àâòîìàòà ïî ðåãóëÿðíîìóâûðàæåíèþÐàññìîòðèì àëãîðèòì ïîñòðîåíèÿ ïî ðåãóëÿðíîìó âûðàæåíèþ íåäåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà, äîïóñêàþùåãî òîò æå ÿçûê.Àëãîðèòì 3.1. Ïîñòðîåíèå íåäåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ïî ðåãóëÿðíîìó âûðàæåíèþ.Âõîä. Ðåãóëÿðíîå âûðàæåíèå r â àëôàâèòå T .Âûõîä.
ÍÊÀ M , òàêîé ÷òî L(M ) = L(r).Ìåòîä. Àâòîìàò äëÿ âûðàæåíèÿ ñòðîèòñÿ êîìïîçèöèåéèç àâòîìàòîâ, ñîîòâåòñòâóþùèõ ïîäâûðàæåíèÿì. Íà êàæäîì øàãå ïîñòðîåíèÿ ñòðîÿùèéñÿ àâòîìàò èìååò â òî÷íîñòèîäíî çàêëþ÷èòåëüíîå ñîñòîÿíèå, â íà÷àëüíîå ñîñòîÿíèå íåòïåðåõîäîâ èç äðóãèõ ñîñòîÿíèé è íåò ïåðåõîäîâ èç çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ â äðóãèå.3.3. Àëãîðèòìû ïîñòðîåíèÿ êîíå÷íûõ àâòîìàòîâ551. Äëÿ âûðàæåíèÿ e ñòðîèòñÿ àâòîìàòLHIÐèñ. 3.5.2.
Äëÿ âûðàæåíèÿ a (a ∈ T ) ñòðîèòñÿ àâòîìàòLDIÐèñ. 3.6.3. Ïóñòü M (s) è M (t) ÍÊÀ äëÿ ðåãóëÿðíûõ âûðàæåíèé s è t ñîîòâåòñòâåííî.à) Äëÿ âûðàæåíèÿ s|t àâòîìàò M (s|t) ñòðîèòñÿ êàêïîêàçàíî íà ðèñ. 3.7. Çäåñü i íîâîå íà÷àëüíîåñîñòîÿíèå è f íîâîå çàêëþ÷èòåëüíîå ñîñòîÿíèå. Çàìåòèì, ÷òî èìååò ìåñòî ïåðåõîä ïî e èçi â íà÷àëüíûå ñîñòîÿíèÿ M (s) è M (t) è ïåðåõîäïî e èç çàêëþ÷èòåëüíûõ ñîñòîÿíèé M (s) è M (t)â f . Íà÷àëüíîå è çàêëþ÷èòåëüíîå ñîñòîÿíèÿ àâòîìàòîâ M (s) è M (t) íå ÿâëÿþòñÿ òàêîâûìè äëÿàâòîìàòà M (s|t).H0VHLH0WÐèñ. 3.7.HI56Ãëàâà 3.
Ëåêñè÷åñêèé àíàëèçá) Äëÿ âûðàæåíèÿ st àâòîìàò M (st) ñòðîèòñÿ ñëåäóþùèì îáðàçîì:L 0V0WIÐèñ. 3.8.Íà÷àëüíîå ñîñòîÿíèå àâòîìàòà M (s) ñòàíîâèòñÿíà÷àëüíûì äëÿ íîâîãî àâòîìàòà, à çàêëþ÷èòåëüíîå ñîñòîÿíèå M (t) ñòàíîâèòñÿ çàêëþ÷èòåëüíûìäëÿ íîâîãî àâòîìàòà. Íà÷àëüíîå ñîñòîÿíèå M (t)è çàêëþ÷èòåëüíîå ñîñòîÿíèå M (s) ñëèâàþòñÿ, òîåñòü âñå ïåðåõîäû èç íà÷àëüíîãî ñîñòîÿíèÿ M (t)ñòàíîâÿòñÿ ïåðåõîäàìè èç çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ M (s).  íîâîì àâòîìàòå ýòî îáúåäèí¼ííîå ñîñòîÿíèå íå ÿâëÿåòñÿ íè íà÷àëüíûì, íè çàêëþ÷èòåëüíûì.â) Äëÿ âûðàæåíèÿ s∗ àâòîìàò M (s∗ ) ñòðîèòñÿ ñëåäóþùèì îáðàçîì:LHH0VHIHÐèñ. 3.9.Çäåñü i íîâîå íà÷àëüíîå ñîñòîÿíèå, à f íîâîåçàêëþ÷èòåëüíîå ñîñòîÿíèå.3.3. Àëãîðèòìû ïîñòðîåíèÿ êîíå÷íûõ àâòîìàòîâ573.3.2. Ïîñòðîåíèå äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ïî íåäåòåðìèíèðîâàííîìóÐàññìîòðèì àëãîðèòì ïîñòðîåíèÿ ïî íåäåòåðìèíèðîâàííîìó êîíå÷íîìó àâòîìàòó äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà, äîïóñêàþùåãî òîò æå ÿçûê.Àëãîðèòì 3.2.
Ïîñòðîåíèå äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ïî íåäåòåðìèíèðîâàííîìó.Âõîä. ÍÊÀ M = (Q, T, D, q0 , F ).Âûõîä. ÄÊÀ M 0 = (Q0 , T, D0 , q00 , F 0 ), òàêîé ÷òî L(M ) =L(M 0 ).Ìåòîä. Êàæäîå ñîñòîÿíèå ðåçóëüòèðóþùåãî ÄÊÀ ýòîíåêîòîðîå ìíîæåñòâî ñîñòîÿíèé èñõîäíîãî ÍÊÀ. àëãîðèòìå áóäóò èñïîëüçîâàòüñÿ ñëåäóþùèå ôóíêöèè:e-closure(R) (R ⊆ Q) ìíîæåñòâî ñîñòîÿíèé ÍÊÀ, äîñòèæèìûõ èç ñîñòîÿíèé, âõîäÿùèõ â R, ïîñðåäñòâîì òîëüêîïåðåõîäîâ ïî e, òî åñòü ìíîæåñòâîS=[{p|(q, e) `∗ (p, e)}q∈Rmove(R, a) (R ⊆ Q) ìíîæåñòâî ñîñòîÿíèé ÍÊÀ, â êîòîðûå åñòü ïåðåõîä íà âõîäå a äëÿ ñîñòîÿíèé èç R, òî åñòüìíîæåñòâîS=[{p|p ∈ D(q, a)}q∈RÂíà÷àëå Q0 è D0 ïóñòû. Âûïîëíèòü øàãè 1-4:(1) Îïðåäåëèòü q00 = e-closure({q0 }).(2) Äîáàâèòü q00 â Q0 êàê íåïîìå÷åííîå ñîñòîÿíèå.(3) Âûïîëíèòü ñëåäóþùóþ ïðîöåäóðó:while (â Q0 åñòü íåïîìå÷åííîå ñîñòîÿíèå R){ïîìåòèòü R;for (êàæäîãî âõîäíîãî ñèìâîëà a ∈ T ){S = e-closure(move(R, a));58Ãëàâà 3.
Ëåêñè÷åñêèé àíàëèçif (S 6= ∅){if (S ∈/ Q0 )}}}äîáàâèòü S â Q0 êàê íåïîìå÷åííîåñîñòîÿíèå;îïðåäåëèòü D0 (R, a) = S ;(4) Îïðåäåëèòü F 0 = {S|S ∈ Q0 , S ∩ F 6= ∅}.Ïðèìåð 3.6. Ðåçóëüòàò ïðèìåíåíèÿ àëãîðèòìà 3.2 ïðèâå-ä¼í íà ðèñ.
3.10.HHDHHHEHHHDD$ED%D&'EDEE(EÐèñ. 3.10.DEE3.3. Àëãîðèòìû ïîñòðîåíèÿ êîíå÷íûõ àâòîìàòîâ593.3.3. Ïîñòðîåíèå äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ïî ðåãóëÿðíîìóâûðàæåíèþÏðèâåä¼ì òåïåðü àëãîðèòì ïîñòðîåíèÿ ïî ðåãóëÿðíîìóâûðàæåíèþ äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà, äîïóñêàþùåãî òîò æå ÿçûê [3].Ïóñòü äàíî ðåãóëÿðíîå âûðàæåíèå r â àëôàâèòå T . Ê ðåãóëÿðíîìó âûðàæåíèþ r äîáàâèì ìàðêåð êîíöà: (r)#. Òàêîå ðåãóëÿðíîå âûðàæåíèå áóäåì íàçûâàòü ïîïîëíåííûì. ïðîöåññå ñâîåé ðàáîòû àëãîðèòì áóäåò èñïîëüçîâàòü ïîïîëíåííîå ðåãóëÿðíîå âûðàæåíèå.Àëãîðèòì áóäåò îïåðèðîâàòü ñ ñèíòàêñè÷åñêèì äåðåâîìäëÿ ïîïîëíåííîãî ðåãóëÿðíîãî âûðàæåíèÿ (r)# , êàæäûéëèñò êîòîðîãî ïîìå÷åí ñèìâîëîì a ∈ T ∪ {e, #}, à êàæäàÿâíóòðåííÿÿ âåðøèíà ïîìå÷åíà çíàêîì îäíîé èç îïåðàöèé:· (êîíêàòåíàöèÿ), | (îáúåäèíåíèå), ∗ (èòåðàöèÿ).Êàæäîìó ëèñòó äåðåâà (êðîìå e-ëèñòüåâ) ïðèñâîèì óíèêàëüíûé íîìåð, íàçûâàåìûé ïîçèöèåé, è áóäåì èñïîëüçîâàòü åãî, ñ îäíîé ñòîðîíû, äëÿ ññûëêè íà ëèñò â äåðåâå, è,ñ äðóãîé ñòîðîíû, äëÿ ññûëêè íà ñèìâîë, ñîîòâåòñòâóþùèéýòîìó ëèñòó.
Çàìåòèì, ÷òî åñëè íåêîòîðûé ñèìâîë èñïîëüçóåòñÿ â ðåãóëÿðíîì âûðàæåíèè íåñêîëüêî ðàç, îí èìååòíåñêîëüêî ïîçèöèé.Îáîéä¼ì äåðåâî T ñíèçó-ââåðõ ñëåâà-íàïðàâî è âû÷èñëèì ÷åòûðå ôóíêöèè: nullable,f irstpos, lastpos è f ollowpos.Òðè ïåðâûå ôóíêöèè nullable, f irstpos è lastpos îïðåäåëåíû íà óçëàõ äåðåâà, à f ollowpos íà ìíîæåñòâå ïîçèöèé. Çíà÷åíèåì âñåõ ôóíêöèé, êðîìå nullable, ÿâëÿåòñÿìíîæåñòâî ïîçèöèé. Ôóíêöèÿ f ollowpos âû÷èñëÿåòñÿ ÷åðåçòðè îñòàëüíûå ôóíêöèè.Ôóíêöèÿ f irstpos(n) äëÿ êàæäîãî óçëà n ñèíòàêñè÷åñêîãî äåðåâà ðåãóëÿðíîãî âûðàæåíèÿ äà¼ò ìíîæåñòâî ïîçèöèé,êîòîðûå ñîîòâåòñòâóþò ïåðâûì ñèìâîëàì â ïîäöåïî÷êàõ,ãåíåðèðóåìûõ ïîäâûðàæåíèåì ñ âåðøèíîé â n.
Àíàëîãè÷íî, lastpos(n) äà¼ò ìíîæåñòâî ïîçèöèé, êîòîðûì ñîîòâåòñòâóþò ïîñëåäíèå ñèìâîëû â ïîäöåïî÷êàõ, ãåíåðèðóåìûõïîäâûðàæåíèÿìè ñ âåðøèíîé n. Äëÿ óçëà n, ïîääåðåâüÿ êî-60Ãëàâà 3. Ëåêñè÷åñêèé àíàëèçòîðîãî (òî åñòü äåðåâüÿ, ó êîòîðûõ óçåë n ÿâëÿåòñÿ êîðíåì)ìîãóò ïîðîäèòü ïóñòîå ñëîâî, îïðåäåëèì nullable(n)=true,à äëÿ îñòàëüíûõ óçëîâ nullable(n)=f alse.Òàáëèöà äëÿ âû÷èñëåíèÿ ôóíêöèé nullable, f irstpos èlastpos ïðèâåäåíà íà ðèñ. 3.11.óçåë nëèñò eëèñò i(íå e)|/\uv·/\uv∗|vnullable(n)truef alsef irstpos(n)∅{i}lastpos(n)∅{i}nullable(u)f irstpos(u)lastpos(u)or∪∪nullable(v)f irstpos(v)lastpos(v)nullable(u) if nullable(u) then if nullable(v) thenandf irstpos(u)lastpos(u)nullable(v)∪∪f irstpos(v)lastpos(v)else f irstpos(u)else lastpos(v)truef irstpos(v)lastpos(v)Ðèñ.
3.11.Ïðèìåð 3.7. Íà ðèñ. 3.12 ïðèâåäåíî cèíòàêñè÷åñêîå äåðåâîäëÿ ïîïîëíåííîãî ðåãóëÿðíîãî âûðàæåíèÿ (a|b)∗ abb# ñ ðåçóëüòàòîì âû÷èñëåíèÿ ôóíêöèé f irstpos è lastpos. Ñëåâà îò êàæäîãîóçëà ðàñïîëîæåíî çíà÷åíèå f irstpos, ñïðàâà îò óçëà çíà÷åíèålastpos. Çàìåòèì, ÷òî ýòè ôóíêöèè ìîãóò áûòü âû÷èñëåíû çàîäèí îáõîä äåðåâà.Åñëè i ïîçèöèÿ, òî f ollowpos(i) åñòü ìíîæåñòâî ïîçèöèé j òàêèõ, ÷òî ñóùåñòâóåò íåêîòîðàÿ ñòðîêà . .
. cd . . .,âõîäÿùàÿ â ÿçûê, îïèñûâàåìûé ðåãóëÿðíûì âûðàæåíèåì,òàêàÿ, ÷òî ïîçèöèÿ i ñîîòâåòñòâóåò ýòîìó âõîæäåíèþ c, àïîçèöèÿ j âõîæäåíèþ d.Ôóíêöèÿ f ollowpos ìîæåò áûòü âû÷èñëåíà òàêæå çàîäèí îáõîä äåðåâà ñíèçó-ââåðõ ïî òàêèì äâóì ïðàâèëàì.3.3. Àëãîðèòìû ïîñòðîåíèÿ êîíå÷íûõ àâòîìàòîâ61^ ` ^ ` ^ ` ^ ` ^ ` ^ `^ ` ^ ` ^ ` E ^ `^ ` ^ ` ^ ` E ^ `^ ` ^ ` ^ `D ^ `^ ` _ ^ ` ^ ` D^ ` ^ ` E ^ ` Ðèñ. 3.12.ïîçèöèÿ123456f ollowpos{1, 2, 3}{1, 2, 3}{4}{5}{6}∅Ðèñ.
3.13.1. Ïóñòü n âíóòðåííèé óçåë ñ îïåðàöèåé · (êîíêàòåíàöèÿ), u è v åãî ïîòîìêè. Òîãäà äëÿ êàæäîé ïîçèöèèi, âõîäÿùåé â lastpos(u), äîáàâëÿåì ê ìíîæåñòâó çíà÷åíèéf ollowpos(i) ìíîæåñòâî f irstpos(v).2. Ïóñòü n âíóòðåííèé óçåë ñ îïåðàöèåé ∗ (èòåðàöèÿ),u åãî ïîòîìîê. Òîãäà äëÿ êàæäîé ïîçèöèè i, âõîäÿùåéâ lastpos(u), äîáàâëÿåì ê ìíîæåñòâó çíà÷åíèé f ollowpos(i)ìíîæåñòâî f irstpos(u).62Ãëàâà 3. Ëåêñè÷åñêèé àíàëèçÏðèìåð 3.8. Ðåçóëüòàò âû÷èñëåíèÿ ôóíêöèè f ollowpos äëÿðåãóëÿðíîãî âûðàæåíèÿ èç ïðåäûäóùåãî ïðèìåðà ïðèâåä¼í íàðèñ. 3.13.Àëãîðèòì 3.3.
Ïðÿìîå ïîñòðîåíèå ÄÊÀ ïî ðåãóëÿðíîìó âûðàæåíèþ.Âõîä. Ðåãóëÿðíîå âûðàæåíèå r â àëôàâèòå T .Âûõîä. ÄÊÀ M = (Q, T, D, q0 , F ), òàêîé ÷òî L(M ) =L(r).Ìåòîä. Ñîñòîÿíèÿ ÄÊÀ ñîîòâåòñòâóþò ìíîæåñòâàì ïîçèöèé.Âíà÷àëå Q è D ïóñòû. Âûïîëíèòü øàãè 1-6:(1) Ïîñòðîèòü ñèíòàêñè÷åñêîå äåðåâî äëÿ ïîïîëíåííîãîðåãóëÿðíîãî âûðàæåíèÿ (r)#.(2) Îáõîäÿ ñèíòàêñè÷åñêîå äåðåâî, âû÷èñëèòü çíà÷åíèÿôóíêöèé nullable, f irstpos, lastpos è f ollowpos.(3) Îïðåäåëèòü q0 = f irstpos(root), ãäå root êîðåíüñèíòàêñè÷åñêîãî äåðåâà.(4) Äîáàâèòü q0 â Q êàê íåïîìå÷åííîå ñîñòîÿíèå.(5) Âûïîëíèòü ñëåäóþùóþ ïðîöåäóðó:while (â Q åñòü íåïîìå÷åííîå ñîñòîÿíèå R){ïîìåòèòü R;for (êàæäîãî âõîäíîãî ñèìâîëà a ∈ T ,òàêîãî, ÷òî â R èìååòñÿ ïîçèöèÿ,êîòîðîé ñîîòâåòñòâóåò a){ïóñòü ñèìâîë a â R ñîîòâåòñòâóåòïîçèöèÿìSp1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
