В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 3
Текст из файла (страница 3)
Ðåçóëüòàòîì å¼ ÿâëÿåòñÿ ëèáî àññåìáëåðíûé ìîäóëü,ëèáî îáúåêòíûé (èëè çàãðóçî÷íûé) ìîäóëü.  ïðîöåññåãåíåðàöèè êîäà ìîãóò âûïîëíÿòüñÿ íåêîòîðûå ëîêàëüíûåîïòèìèçàöèè, òàêèå êàê ðàñïðåäåëåíèå ðåãèñòðîâ, âûáîðäëèííûõ èëè êîðîòêèõ ïåðåõîäîâ, ó÷¼ò ñòîèìîñòè êîìàíäïðè âûáîðå êîíêðåòíîé ïîñëåäîâàòåëüíîñòè êîìàíä. Äëÿãåíåðàöèè êîäà ðàçðàáîòàíû ðàçëè÷íûå ìåòîäû, òàêèåêàê òàáëèöû ðåøåíèé, ñîïîñòàâëåíèå îáðàçöîâ, âêëþ÷àþùåå äèíàìè÷åñêîå ïðîãðàììèðîâàíèå, ðàçëè÷íûåñèíòàêñè÷åñêèå ìåòîäû.Êîíå÷íî, òå èëè èíûå ôàçû òðàíñëÿòîðà ìîãóò ëèáî îòñóòñòâîâàòü ñîâñåì, ëèáî îáúåäèíÿòüñÿ.
 ïðîñòåéøåì ñëó÷àå îäíîïðîõîäíîãî òðàíñëÿòîðà íåò ÿâíîé ôàçû ãåíåðàöèèïðîìåæóòî÷íîãî ïðåäñòàâëåíèÿ è îïòèìèçàöèè, îñòàëüíûåôàçû îáúåäèíåíû â îäíó, ïðè÷¼ì íåò è ÿâíî ïîñòðîåííîãîñèíòàêñè÷åñêîãî äåðåâà.14Ãëàâà 1. ÂâåäåíèåE_dkbq_kdbcZgZeba>bZ]ghklbdZDhg_qgu_Z\lhfZlulZ[ebpuh[t_dlh\KbglZdkbq_kdbcZgZeba>bZ]ghklbdZDhgl_dklgucZgZeba>bZ]ghklbdZlZ[ebpuh[t_dlh\:ljb[mlgu_]jZffZlbdb:ljb[mlbjh\Zggh_^_j_\hlZ[ebpuh[t_dlh\=_g_jZpbyijhf_`mlhqgh]hij_^klZ\e_gbyIjhf_`mlhqgZynhjfZij_nbdkgZyihklnbdkgZyljhcdbb^jKMljZgkeypbyHilbfbaZpby>_j_\hjZa[hjZDK]jZffZlbdbIhlhde_dk_fIjhf_`mlhqgZynhjfZhjb_glbjh\Zgguc]jZnIhlhdh\ucZgZeba=_g_jZpbydh^ZH[t_dlgucfh^mevLZ[ebpuj_r_gbc^bgZfbq_kdh_ijh]jZffbjh\Zgb_Ðèñ.
1.1.Ãëàâà 2.ßçûêè è èõïðåäñòàâëåíèå2.1. Àëôàâèòû, öåïî÷êè è ÿçûêèÀëôàâèò, èëè ñëîâàðü ýòî êîíå÷íîå ìíîæåñòâî ñèìâîëîâ. Äëÿ îáîçíà÷åíèÿ ñèìâîëîâ ìû áóäåì ïîëüçîâàòüñÿöèôðàìè, ëàòèíñêèìè áóêâàìè è ñïåöèàëüíûìè ëèòåðàìèòèïà #, $.Ïóñòü V àëôàâèò. Öåïî÷êà â àëôàâèòå V ýòî ëþáàÿñòðîêà êîíå÷íîé äëèíû, ñîñòàâëåííàÿ èç ñèìâîëîâ àëôàâèòà V . Ñèíîíèìîì öåïî÷êè ÿâëÿþòñÿ ïðåäëîæåíèå, ñòðîêàè ñëîâî. Ïóñòàÿ öåïî÷êà (îáîçíà÷àåòñÿ e) ýòî öåïî÷êà, âêîòîðóþ íå âõîäèò íè îäèí ñèìâîë.Êîíêàòåíàöèåé öåïî÷åê x è y íàçûâàåòñÿ öåïî÷êà xy .Çàìåòèì, ÷òî xe = ex = x äëÿ ëþáîé öåïî÷êè x.Ïóñòü x, y , z ïðîèçâîëüíûå öåïî÷êè â íåêîòîðîì àëôàâèòå. Öåïî÷êà y íàçûâàåòñÿ ïîäöåïî÷êîé öåïî÷êè xyz .
Öåïî÷êè x è y íàçûâàþòñÿ, ñîîòâåòñòâåííî, ïðåôèêñîì è ñóôôèêñîì öåïî÷êè xy . Çàìåòèì, ÷òî ëþáîé ïðåôèêñ èëè ñóôôèêñ öåïî÷êè ÿâëÿåòñÿ ïîäöåïî÷êîé ýòîé öåïî÷êè. Êðîìå òîãî, ïóñòàÿ öåïî÷êà ÿâëÿåòñÿ ïðåôèêñîì, ñóôôèêñîìè ïîäöåïî÷êîé äëÿ ëþáîé öåïî÷êè.1516Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèåÏðèìåð 2.1. Äëÿ öåïî÷êè abbba ïðåôèêñîì ÿâëÿåòñÿ ëþáàÿ öåïî÷êà èç ìíîæåñòâà L1 = {e, a, ab, abb, abbb, abbba},ñóôôèêñîì ÿâëÿåòñÿ ëþáàÿ öåïî÷êà èç ìíîæåñòâà L2 ={e, a, ba, bba, bbba, abbba}, ïîäöåïî÷êîé ÿâëÿåòñÿ ëþáàÿ öåïî÷êàèç ìíîæåñòâà L1 ∪ L2 .Äëèíîé öåïî÷êè w (îáîçíà÷àåòñÿ |w|) íàçûâàåòñÿ ÷èñëîñèìâîëîâ â íåé. Íàïðèìåð, |abababa| = 7, à |e| = 0.ßçûê â àëôàâèòå V ýòî íåêîòîðîå ìíîæåñòâî öåïî÷åêâ àëôàâèòå V .Ïðèìåð 2.2. Ïóñòü äàí àëôàâèò V = {a, b}.
Âîò íåêîòîðûåÿçûêè â àëôàâèòå V :à) L1 = ∅ ïóñòîé ÿçûê;á) L2 = {e} ÿçûê, ñîäåðæàùèé òîëüêî ïóñòóþ öåïî÷êó(çàìåòèì, ÷òî L1 è L2 ðàçëè÷íûå ÿçûêè);â) L3 = {e, a, b, aa, ab, ba, bb} ÿçûê, ñîäåðæàùèé öåïî÷êè èça è b, äëèíà êîòîðûõ íå ïðåâîñõîäèò 2;ã) L4 ÿçûê, âêëþ÷àþùèé âñåâîçìîæíûå öåïî÷êè èç a è b,ñîäåðæàùèå ÷¼òíîå ÷èñëî a è ÷¼òíîå ÷èñëî b;2ä) L5 = {an |n > 0} ÿçûê öåïî÷åê èç a, äëèíû êîòîðûõïðåäñòàâëÿþò ñîáîé êâàäðàòû íàòóðàëüíûõ ÷èñåë.Äâà ïîñëåäíèõ ÿçûêà ñîäåðæàò áåñêîíå÷íîå ÷èñëî öåïî÷åê.Ââåä¼ì îáîçíà÷åíèå V ∗ äëÿ ìíîæåñòâà âñåõ öåïî÷åê âàëôàâèòå V , âêëþ÷àÿ ïóñòóþ öåïî÷êó. Êàæäûé ÿçûê â àëôàâèòå V ÿâëÿåòñÿ ïîäìíîæåñòâîì V ∗ . Äëÿ îáîçíà÷åíèÿìíîæåñòâà âñåõ öåïî÷åê â àëôàâèòå V , êðîìå ïóñòîé öåïî÷êè, áóäåì èñïîëüçîâàòü V + .Ïðèìåð 2.3.
Ïóñòü V = {0, 1}. Òîãäà V ∗ = {e, 0, 1, 00, 01,10, 11, 000,. . .},V + = {0, 1, 00, 01, 10, 11, 000, . . .}.Ââåä¼ì íåêîòîðûå îïåðàöèè íàä ÿçûêàìè.Ïóñòü L1 è L2 ÿçûêè â àëôàâèòå V . Êîíêàòåíàöèåéÿçûêîâ L1 è L2 íàçûâàåòñÿ ÿçûê L1 L2 = {xy|x ∈ L1 , y ∈L2 }.Ïóñòü L ÿçûê â àëôàâèòå V . Èòåðàöèåé ÿçûêà L íàçûâàåòñÿ ÿçûê L∗ , îïðåäåëÿåìûé ñëåäóþùèì îáðàçîì:Àëôàâèòû, öåïî÷êè è ÿçûêè17(1) L0 = {e};(2) Ln = LLn−1 , n > 1;(3) L∗ =∞Sn=0Ln .Ïðèìåð 2.4. Ïóñòü L1 = {aa, bb} è L2 = {e, a, bb}. ÒîãäàL1 L2 = {aa, bb, aaa, bba, aabb, bbbb}, èL∗1 = {e, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, . . .}.Áîëüøèíñòâî ÿçûêîâ, ïðåäñòàâëÿþùèõ èíòåðåñ, ñîäåðæàò áåñêîíå÷íîå ÷èñëî öåïî÷åê.
Ïðè ýòîì âîçíèêàþò òðèâàæíûõ âîïðîñà.Âî-ïåðâûõ, êàê ïðåäñòàâèòü ÿçûê (òî åñòü ñïåöèôèöèðîâàòü âõîäÿùèå â íåãî öåïî÷êè)? Åñëè ÿçûê ñîäåðæèòòîëüêî êîíå÷íîå ìíîæåñòâî öåïî÷åê, îòâåò ïðîñò. Ìîæíî ïðîñòî ïåðå÷èñëèòü åãî öåïî÷êè. Åñëè ÿçûê áåñêîíå÷åí, íåîáõîäèìî íàéòè äëÿ íåãî êîíå÷íîå ïðåäñòàâëåíèå.Ýòî êîíå÷íîå ïðåäñòàâëåíèå, â ñâîþ î÷åðåäü, áóäåò ñòðîêîéñèìâîëîâ íàä íåêîòîðûì àëôàâèòîì âìåñòå ñ íåêîòîðîé èíòåðïðåòàöèåé, ñâÿçûâàþùåé ýòî ïðåäñòàâëåíèå ñ ÿçûêîì.Âî-âòîðûõ, äëÿ ëþáîãî ëè ÿçûêà ñóùåñòâóåò êîíå÷íîåïðåäñòàâëåíèå? Ìîæíî ïðåäïîëîæèòü, ÷òî îòâåò îòðèöàòåëåí. Ìû óâèäèì, ÷òî ìíîæåñòâî âñåõ öåïî÷åê íàä àëôàâèòîì ñ÷¼òíî.
ßçûê - ýòî ëþáîå ïîäìíîæåñòâî öåïî÷åê. Èç òåîðèè ìíîæåñòâ èçâåñòíî, ÷òî ìíîæåñòâî âñåõ ïîäìíîæåñòâñ÷¼òíîãî ìíîæåñòâà íåñ÷¼òíî. Õîòÿ ìû è íå äàëè ñòðîãîãî îïðåäåëåíèÿ òîãî, ÷òî ÿâëÿåòñÿ êîíå÷íûì ïðåäñòàâëåíèåì, èíòóèòèâíî ÿñíî, ÷òî ëþáîå ðàçóìíîå îïðåäåëåíèå êîíå÷íîãî ïðåäñòàâëåíèÿ âåä¼ò òîëüêî ê ñ÷¼òíîìó ìíîæåñòâóêîíå÷íûõ ïðåäñòàâëåíèé, ïîñêîëüêó íóæíî èìåòü âîçìîæíîñòü çàïèñàòü òàêîå êîíå÷íîå ïðåäñòàâëåíèå â âèäå ñòðîêè ñèìâîëîâ êîíå÷íîé äëèíû.
Ïîýòîìó ÿçûêîâ çíà÷èòåëüíîáîëüøå, ÷åì êîíå÷íûõ ïðåäñòàâëåíèé.Â-òðåòüèõ, ìîæíî ñïðîñèòü, êàêîâà ñòðóêòóðà òåõêëàññîâ ÿçûêîâ, äëÿ êîòîðûõ ñóùåñòâóåò êîíå÷íîå ïðåäñòàâëåíèå?18Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèå2.2. Ïðåäñòàâëåíèå ÿçûêîâÏðîöåäóðà ýòî êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü èíñòðóêöèé, êîòîðûå ìîãóò áûòü ìåõàíè÷åñêè âûïîëíåíû. Ïðèìåðîì ìîæåò ñëóæèòü ìàøèííàÿ ïðîãðàììà. Ïðîöåäóðà, êîòîðàÿ âñåãäà çàêàí÷èâàåòñÿ, íàçûâàåòñÿ àëãîðèòìîì.Îäèí èç ñïîñîáîâ ïðåäñòàâëåíèÿ ÿçûêà äàòü àëãîðèòì,îïðåäåëÿþùèé, ïðèíàäëåæèò ëè öåïî÷êà ÿçûêó.
Áîëåå îáùèé ñïîñîá ñîñòîèò â òîì, ÷òîáû äàòü ïðîöåäóðó, êîòîðàÿîñòàíàâëèâàåòñÿ ñ îòâåòîì ¾äà¿ äëÿ öåïî÷åê, ïðèíàäëåæàùèõ ÿçûêó, è ëèáî îñòàíàâëèâàåòñÿ ñ îòâåòîì ¾íåò¿, ëèáîâîîáùå íå îñòàíàâëèâàåòñÿ äëÿ öåïî÷åê, íå ïðèíàäëåæàùèõÿçûêó. Ãîâîðÿò, ÷òî òàêàÿ ïðîöåäóðà èëè àëãîðèòì ðàñïîçíà¼ò ÿçûê.Òàêîé ìåòîä ïðåäñòàâëÿåò ÿçûê ñ òî÷êè çðåíèÿ ðàñïîçíàâàíèÿ.
ßçûê ìîæíî òàêæå ïðåäñòàâèòü ìåòîäîì ïîðîæäåíèÿ. À èìåííî, ìîæíî äàòü ïðîöåäóðó, êîòîðàÿ ñèñòåìàòè÷åñêè ïîðîæäàåò â îïðåäåë¼ííîì ïîðÿäêå öåïî÷êèÿçûêà.Åñëè ìû ìîæåì ðàñïîçíàòü öåïî÷êè ÿçûêà íàä àëôàâèòîì V ëèáî ñ ïîìîùüþ ïðîöåäóðû, ëèáî ñ ïîìîùüþ àëãîðèòìà, òî ìû ìîæåì è ãåíåðèðîâàòü ÿçûê, ïîñêîëüêó ìûìîæåì ñèñòåìàòè÷åñêè ãåíåðèðîâàòü âñå öåïî÷êè èç V ∗ ,ïðîâåðÿòü êàæäóþ öåïî÷êó íà ïðèíàäëåæíîñòü ÿçûêó èâûäàâàòü ñïèñîê òîëüêî öåïî÷åê ÿçûêà.
Íî åñëè ïðîöåäóðàíå âñåãäà çàêàí÷èâàåòñÿ ïðè ïðîâåðêå öåïî÷êè, ìû íå ñäâèíåìñÿ äàëüøå ïåðâîé öåïî÷êè, íà êîòîðîé ïðîöåäóðà íå çàêàí÷èâàåòñÿ. Ýòó ïðîáëåìó ìîæíî îáîéòè, óñòðîèâ ïðîâåðêó òàêèì îáðàçîì, ÷òîáû ïðîöåäóðà íèêîãäà íå ïðîäîëæàëà ïðîâåðÿòü îäíó öåïî÷êó áåñêîíå÷íî. Äëÿ ýòîãî ââåä¼ìñëåäóþùóþ êîíñòðóêöèþ.Ïðåäïîëîæèì, ÷òî V èìååò p ñèìâîëîâ. Ìû ìîæåì ðàññìàòðèâàòü öåïî÷êè èç V ∗ êàê ÷èñëà, ïðåäñòàâëåííûå â áàçèñå p, ïëþñ ïóñòàÿ öåïî÷êà e. Ìîæíî çàíóìåðîâàòü öåïî÷êè â ïîðÿäêå âîçðàñòàíèÿ äëèíû è â ¾÷èñëîâîì¿ ïîðÿäêåäëÿ öåïî÷åê îäèíàêîâîé äëèíû.
Òàêàÿ íóìåðàöèÿ äëÿ öåïî÷åê ÿçûêà {a, b, c}∗ ïðèâåäåíà íà ðèñ. 2.1, à.Ïóñòü P ïðîöåäóðà äëÿ ïðîâåðêè ïðèíàäëåæíîñòè öå-Ïðåäñòàâëåíèå ÿçûêîâ19ïî÷êè ÿçûêó L. Ïðåäïîëîæèì, ÷òî P ìîæåò áûòü ïðåäñòàâëåíà äèñêðåòíûìè øàãàìè, òàê ÷òî èìååò ñìûñë ãîâîðèòüîá i-îì øàãå ïðîöåäóðû äëÿ ëþáîé äàííîé öåïî÷êè. Ïðåæäå ÷åì äàòü ïðîöåäóðó ïåðå÷èñëåíèÿ öåïî÷åê ÿçûêà L, äàäèì ïðîöåäóðó íóìåðàöèè ïàð ïîëîæèòåëüíûõ ÷èñåë.Âñå óïîðÿäî÷åííûå ïàðû ïîëîæèòåëüíûõ ÷èñåë (x, y)ìîæíî îòîáðàçèòü íà ìíîæåñòâî ïîëîæèòåëüíûõ ÷èñåë ñëåäóþùåé ôîðìóëîé:z = (x + y − 1)(x + y − 2)/2 + yÏàðû öåëûõ ïîëîæèòåëüíûõ ÷èñåë ìîæíî óïîðÿäî÷èòüâ ñîîòâåòñòâèè ñî çíà÷åíèåì z (ðèñ.
2.1, á).123456789...eabcaaabacbabb...y12x 3451 21 32 54 87 1211à3691341014515z(x, y)áÐèñ. 2.1.Òåïåðü ìîæíî äàòü ïðîöåäóðó ïåðå÷èñëåíèÿ öåïî÷åê L.Íóìåðóåì óïîðÿäî÷åííûå ïàðû öåëûõ ïîëîæèòåëüíûõ ÷èñåë (1,1), (2,1), (1,2), (3,1), (2,2), ... . Ïðè íóìåðàöèè ïàðû(i, j) ãåíåðèðóåì i-þ öåïî÷êó èç V ∗ è ïðèìåíÿåì ê öåïî÷êåïåðâûå j øàãîâ ïðîöåäóðû P. Êàê òîëüêî ìû îïðåäåëèëè,÷òî ñãåíåðèðîâàííàÿ öåïî÷êà ïðèíàäëåæèò L, äîáàâëÿåìöåïî÷êó ê ñïèñêó ýëåìåíòîâ L. Åñëè öåïî÷êà i ïðèíàäëåæèò L, ýòî áóäåò îïðåäåëåíî P çà j øàãîâ äëÿ íåêîòîðîãîêîíå÷íîãî j . Ïðè ïåðå÷èñëåíèè (i, j) áóäåò ñãåíåðèðîâàíà20Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèåöåïî÷êà ñ íîìåðîì i.
Ëåãêî âèäåòü, ÷òî ýòà ïðîöåäóðà ïåðå÷èñëÿåò âñå öåïî÷êè L.Åñëè ìû èìååì ïðîöåäóðó ãåíåðàöèè öåïî÷åê ÿçûêà,òî ìû âñåãäà ìîæåì ïîñòðîèòü ïðîöåäóðó ðàñïîçíàâàíèÿïðåäëîæåíèé ÿçûêà, íî íå âñåãäà àëãîðèòì. Äëÿ îïðåäåëåíèÿ òîãî, ïðèíàäëåæèò ëè x ÿçûêó L, ïðîñòî íóìåðóåìïðåäëîæåíèÿ L è ñðàâíèâàåì x ñ êàæäûì ïðåäëîæåíèåì.Åñëè ñãåíåðèðîâàíî x, ïðîöåäóðà îñòàíàâëèâàåòñÿ, ðàñïîçíàâ, ÷òî x ïðèíàäëåæèò L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
