В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 14
Текст из файла (страница 14)
Ïðåäñòàâèì êðîíó αâ âèäå uvwxy , ãäå w - êðîíà ïîääåðåâà D1 ñ êîðíåì q è vwx êðîíà ïîääåðåâà D2 ñ êîðíåì p. Òîãäà âûñîòà ïîääåðåâàD2 íå áîëåå (n − 1) + 2 + 1 = n + 2, òàê ÷òî |vwz| 6 2n+1 .Òàêæå î÷åâèäíî, ÷òî vx =6 e, ïîñêîëüêó â ñèëó îïðåäåëåíèÿ íîðìàëüíîé ôîðìû Õîìñêîãî p èìååò äâóõ ñûíîâåé,ïîìå÷åííûõ íåòåðìèíàëàìè, èç êîòîðûõ íå âûâîäèòñÿ ïóñòàÿ öåïî÷êà.Êðîìå òîãî, S ⇒∗ uAy ⇒∗ uvAxy ⇒∗ uvwxy , à òàêæåA ⇒∗ vAx ⇒∗ vwx. Îòñþäà ïîëó÷àåì A ⇒∗ v i wxi äëÿ âñåõi > 0 è S ⇒∗ uv i wxi y äëÿ âñåõ i > 0.Ïðèìåð. Ïîêàæåì, ÷òî ÿçûê L = {an bn cn |n > 1} íå ÿâëÿåòñÿêîíòåêñòíîñâîáîäíûì ÿçûêîì.Åñëè áû îí áûë ÊÑÿçûêîì, òî ìû âçÿëè áû êîíñòàíòó k,êîòîðàÿ îïðåäåëÿåòñÿ â ëåììå î ðàçðàñòàíèè.
Ïóñòü z = ak bk ck .Òîãäà z = uvwxy . Òàê êàê |vwx| 6 k, òî â öåïî÷êå vwx íå ìîãóòáûòü âõîæäåíèÿ êàæäîãî èç ñèìâîëîâ a, b è c. Òàêèì îáðàçîì,öåïî÷êà uwy , êîòîðàÿ ïî ëåììå î ðàçðàñòàíèè ïðèíàäëåæèò L,ñîäåðæèò ëèáî k ñèìâîëîâ a, ëèáî k ñèìâîëîâ c. Íî îíà íå ìîæåòèìåòü k âõîæäåíèé êàæäîãî èç ñèìâîëîâ a, b è c, ïîòîìó, ÷òî|uwy| < 3k. Çíà÷èò, âõîæäåíèé êàêîãî-òî èç ýòèõ ñèìâîëîâ âuwy áîëüøå, ÷åì äðóãîãî è, ñëåäîâàòåëüíî, uwy ∈/ L. Ïîëó÷åííîåïðîòèâîðå÷èå ïîçâîëÿåò çàêëþ÷èòü, ÷òî L íå ÊÑ-ÿçûê.4.2. Ïðåîáðàçîâàíèÿ ÊÑ-ãðàììàòèêÐàññìîòðèì ðÿä ïðåîáðàçîâàíèé, ïîçâîëÿþùèõ ¾óëó÷øèòü¿ âèä êîíòåêñòíî-ñâîáîäíîé ãðàììàòèêè áåç èçìåíåíèÿ ïîðîæäàåìîãî åþ ÿçûêà.Íàçîâ¼ì ñèìâîë X ∈ (N ∪ T ) íåäîñòèæèìûì â ÊÑãðàììàòèêå G = (N, T, P, S), åñëè X íå ïîÿâëÿåòñÿ íè â îäíîé âûâîäèìîé öåïî÷êå ýòîé ãðàììàòèêè.
Èíûìè ñëîâàìè,90Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçñèìâîë X ÿâëÿåòñÿ íåäîñòèæèìûì, åñëè â G íå ñóùåñòâóåòâûâîäà S ⇒∗ αXβ íè äëÿ êàêèõ α, β ∈ (N ∪ T )∗ .Íàçîâ¼ì ñèìâîë X ∈ (N ∪ T ) íåñâîäèìûì (áåñïëîäíûì)â òîé æå ãðàììàòèêå, åñëè â íåé íå ñóùåñòâóåò âûâîäà âèäàX ⇒∗ xwy , ãäå w, x, y ïðèíàäëåæàò T ∗ .Î÷åâèäíî, ÷òî êàæäûé íåäîñòèæèìûé è/èëè íåñâîäèìûé ñèìâîë ÿâëÿåòñÿ áåñïîëåçíûì, êàê è âñå ïðàâèëà, åãîñîäåðæàùèå.Ïðè âíèìàòåëüíîì èçó÷åíèè âûøåïðèâåä¼ííûõ îïðåäåëåíèé ñòàíîâèòñÿ ïîíÿòíûì, ÷òî à) öåëåñîîáðàçíî èñêàòüíå íåïîñðåäñòâåííî ñàìè íåäîñòèæèìûå (èëè íåñâîäèìûå)ñèìâîëû, à ïîñëåäîâàòåëüíî îïðåäåëÿòü ìíîæåñòâî äîñòèæèìûõ (èëè ñâîäèìûõ) ñèìâîëîâ, íà÷èíàÿ ñ òåõ, êîòîðûåïî îïðåäåëåíèþ ÿâëÿþòñÿ äîñòèæèìûìè (àêñèîìà) è ñâîäèìûìè (òåðìèíàëû) âñå îñòàëüíûå ñèìâîëû îêàçûâàþòñÿ áåñïîëåçíûìè; á) îäíîâðåìåííîå îïðåäåëåíèå äîñòèæèìûõ è ñâîäèìûõ ñèìâîëîâ íåâîçìîæíî, òàê êàê ñîîòâåòñòâóþùèå ïðîöåññû èäóò â ïðîòèâîïîëîæíûõ íàïðàâëåíèÿõ (îò êîðíÿ ê ëèñòüÿì è íàîáîðîò).Àëãîðèòì 4.1.
Óñòðàíåíèå íåäîñòèæèìûõ ñèìâîëîâ.Âõîä. ÊÑ-ãðàììàòèêà G = (N, T, P, S).Âûõîä. ÊÑ-ãðàììàòèêà G0 = (N 0 , T 0 , P 0 , S) áåç íåäîñòèæèìûõ ñèìâîëîâ, òàêàÿ, ÷òî L(G0 ) = L(G).Ìåòîä. Âûïîëíèòü øàãè 14:(1) Ïîëîæèòü V0 = {S} è i = 1;(2) Ïîëîæèòü Vi = {X | â P åñòü A → αXβ è A ∈ Vi−1 } ∪Vi−1 ;(3) Åñëè Vi 6= Vi−1 , ïîëîæèòü i = i + 1 è ïåðåéòè ê øàãó 2,â ïðîòèâíîì ñëó÷àå ïåðåéòè ê øàãó 4;(4) Ïîëîæèòü N 0 = Vi ∩ N , T 0 = Vi ∩ T . Âêëþ÷èòü â P 0 âñåïðàâèëà èç P , ñîäåðæàùèå òîëüêî ñèìâîëû èç Vi .Àëãîðèòì 4.2. Óñòðàíåíèå íåñâîäèìûõ ñèìâîëîâ.Âõîä. ÊÑ-ãðàììàòèêà G = (N, T, P, S).Âûõîä.
ÊÑ-ãðàììàòèêà G0 = (N 0 , T 0 , P 0 , S) áåç íåñâîäèìûõ ñèìâîëîâ, òàêàÿ, ÷òî L(G0 ) = L(G).Ìåòîä. Âûïîëíèòü øàãè 14:4.2. Ïðåîáðàçîâàíèÿ ÊÑ-ãðàììàòèê91(1) Ïîëîæèòü N0 = T è i = 1;(2) Ïîëîæèòü Ni = {A|A → α ∈ P è α ∈ (Ni−1 )∗ } ∪ Ni−1 ;(3) Åñëè Ni 6= Ni−1 , ïîëîæèòü i = i + 1 è ïåðåéòè ê øàãó2, â ïðîòèâíîì ñëó÷àå ïîëîæèòü Ne = Ni è ïåðåéòè êøàãó 4;(4) Ïîëîæèòü G1 = ((N ∩Ne )∪{S}, T, P1 , S), ãäå P1 ñîñòîèòèç ïðàâèë ìíîæåñòâà P , ñîäåðæàùèõ òîëüêî ñèìâîëû èçNe ∪ T ;×òîáû óñòðàíèòü âñå áåñïîëåçíûå ñèìâîëû, íåîáõîäèìîïðèìåíèòü ê èñõîäíîé ãðàììàòèêå ñíà÷àëà Àëãîðèòì 4.2,à çàòåì Àëãîðèòì 4.1.Ïðèìåð. Âñå ñèìâîëû ñëåäóþùåé ãðàììàòèêèS → AS | bA → ABB→aÿâëÿþòñÿ äîñòèæèìûìè.
Ïîýòîìó íàðóøåíèå ïðåäëîæåííîãîïîðÿäêà ïðèìåíåíèÿ ê íåé àëãîðèòìîâ ïðèâåä¼ò ëèøü ê ÷àñòè÷íîìó ðåøåíèþ çàäà÷è.ÊÑ-ãðàììàòèêà áåç áåñïîëåçíûõ ñèìâîëîâ íàçûâàåòñÿïðèâåä¼ííîé. Ëåãêî âèäåòü, ÷òî äëÿ ëþáîé ÊÑ-ãðàììàòèêèñóùåñòâóåò ýêâèâàëåíòíàÿ ïðèâåä¼ííàÿ.  äàëüíåéøåì áóäåì ïðåäïîëàãàòü, ÷òî âñå ðàññìàòðèâàìûå ãðàììàòèêè ïðèâåä¼ííûå.4.2.1.
Àëãîðèòì Êîêà-ßíãåðà-ÊàñàìèÏðèâåä¼ì àëãîðèòì ñèíòàêñè÷åñêîãî àíàëèçà, ïðèìåíèìûé äëÿ ëþáîé ãðàììàòèêè â íîðìàëüíîé ôîðìå ÕîìñêîãîÀëãîðèòì Êîêà-ßíãåðà-ÊàñàìèÂõîä. ÊÑ-ãðàììàòèêà G = (N, T, P, S) â íîðìàëüíîéôîðìå Õîìñêîãî è âõîäíàÿ öåïî÷êà w = a1 a2 ... an ∈ T + .Âûõîä. Òàáëèöà ðàçáîðà T ab äëÿ w òàêàÿ, ÷òî A ∈ tijòîãäà è òîëüêî òîãäà, êîãäà A ⇒+ ai ai+1 ... ai+j−1 .Ìåòîä.(1) Ïîëîæèòü ti1 = {A | A → ai ∈ P } äëÿ êàæäîãî i. Òàê÷òî, åñëè A ∈ ti1 , òî A ⇒+ ai .92Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèç(2) Ïóñòü tij 0 âû÷èñëåíî äëÿ 1 6 i 6 n è 1 6 j 0 < j . Ïîëîæèì tij = {A | äëÿ íåêîòîðîãî 1 6 k < j ïðàâèëîA → BC ∈ P, B ∈ tik , C ∈ ti+k,j−k }.Òàê êàê 1 6 k < j , òî k < j è j − k < j .
Òàê ÷òî tik èti+k,j−k âû÷èñëÿþòñÿ ðàíüøå, ÷åì tij . Åñëè A ∈ tij , òîA ⇒BC ⇒+ ai ... ai+k−1 C ⇒+ aI ... ai+k−1 ai+k ... ai+j−1 .(3) Ïîâòîðÿòü øàã 2 äî òåõ ïîð, ïîêà íå ñòàíóò èçâåñòíûtij äëÿ âñåõ 1 6 i 6 n è 1 6 j 6 n − i + 1.Àëãîðèòì íàõîæäåíèÿ ëåâîãî ðàçáîðà ïî òàáëèöåðàçáîðà T ab.Âõîä. ÊÑ-ãðàììàòèêà G = (N, T, P, S) â íîðìàëüíîéôîðìå Õîìñêîãî ñ ïðàâèëàìè, çàíóìåðîâàííûìè îò 1 äîp, âõîäíàÿ öåïî÷êà w = a1 a2 ... an ∈ T + è òàáëèöà ðàçáîðàT ab.Âûõîä. Ëåâûé ðàçáîð öåïî÷êè w èëè ñèãíàë îøèáêà.Ìåòîä.
Ïðîöåäóðà gen(i, j, A).(1) Åñëè j = 1 è A → ai = pm , âûäàòü m.(2) Ïóñòü j > 1 è k - íàèìåíüøåå èç ÷èñåë îò 1 äî j − 1, äëÿêîòîðûõ ñóùåñòâóåò B ∈ tik , C ∈ ti+k,j−k è ïðàâèëîpm = A → BC . Âûäàòü m è âûïîëíèòü gen(i, k, B),çàòåì gen(i + k, j − k, C).Âûïîëíèòü gen(1, n, S ), åñëè S ∈ t1,n , èíà÷å îøèáêà.4.3. Ðàçáîð ñâåðõó-âíèç (ïðåäñêàçûâàþùèé ðàçáîð)4.3.1.
Àëãîðèòì ðàçáîðà ñâåðõó-âíèçÏóñòü äàíà ÊÑ-ãðàììàòèêà G = (N, T, P, S). Ðàññìîòðèì ðàçáîð ñâåðõó-âíèç (ïðåäñêàçûâàþùèé ðàçáîð) äëÿãðàììàòèêè G.Ãëàâíàÿ çàäà÷à ïðåäñêàçûâàþùåãî ðàçáîðà îïðåäåëåíèå ïðàâèëà âûâîäà, êîòîðîå íóæíî ïðèìåíèòü ê íåòåðìèíàëó. Ïðîöåññ ïðåäñêàçûâàþùåãî ðàçáîðà ñ òî÷êè çðåíèÿïîñòðîåíèÿ äåðåâà ðàçáîðà ïðîèëëþñòðèðîâàí íà ðèñ. 4.1Ôðàãìåíòû íåäîñòðîåííîãî äåðåâà ñîîòâåòñòâóþò ñåíòåíöèàëüíûì ôîðìàì. Âíà÷àëå äåðåâî ñîñòîèò òîëüêî èç4.3. Ïðåäñêàçûâàþùèé ðàçáîð ñâåðõó-âíèç666; ;; ;<<D93D=DEÐèñ. 4.1.îäíîé âåðøèíû, ñîîòâåòñòâóþùåé àêñèîìå S .  ýòîò ìîìåíò ïî ïåðâîìó ñèìâîëó âõîäíîé öåïî÷êè ïðåäñêàçûâàþùèé àíàëèçàòîð äîëæåí îïðåäåëèòü ïðàâèëî S →X1 X2 .
. . ,êîòîðîå äîëæíî áûòü ïðèìåíåíî ê S . Çàòåì íåîáõîäèìîîïðåäåëèòü ïðàâèëî, êîòîðîå äîëæíî áûòü ïðèìåíåíî ê X1 ,è ò.ä., äî òåõ ïîð, ïîêà â ïðîöåññå òàêîãî ïîñòðîåíèÿ ñåíòåíöèàëüíîé ôîðìû, ñîîòâåòñòâóþùåé ëåâîìó âûâîäó, íåáóäåò ïðèìåíåíî ïðàâèëî Y → a . . . . Ýòîò ïðîöåññ çàòåìïðèìåíÿåòñÿ äëÿ ñëåäóþùåãî ñàìîãî ëåâîãî íåòåðìèíàëüíîãî ñèìâîëà ñåíòåíöèàëüíîé ôîðìû.Íà ðèñ. 4.2 óñëîâíî ïîêàçàíà ñòðóêòóðà ïðåäñêàçûâàþùåãî àíàëèçàòîðà, êîòîðûé îïðåäåëÿåò î÷åðåäíîå ïðàâèëî ñ ïîìîùüþ òàáëèöû.
Òàêóþ òàáëèöó ìîæíî ïîñòðîèòüè íåïîñðåäñòâåííî ïî ãðàììàòèêå. Òàáëè÷íî-óïðàâëÿåìûéïðåäñêàçûâàþùèé àíàëèçàòîð èìååò âõîäíóþ ëåíòó, óïðàâëÿþùåå óñòðîéñòâî (ïðîãðàììó), òàáëèöó àíàëèçà, ìàãàçèí(ñòåê) è âûõîäíóþ ëåíòó. Âõîäíàÿ ëåíòà ñîäåðæèò àíàëèçèðóåìóþ ñòðîêó, çàêàí÷èâàþùóþñÿ ñèìâîëîì $ ìàðêåðîì êîíöà ñòðîêè. Âûõîäíàÿ ëåíòà ñîäåðæèò ïîñëåäîâàòåëüíîñòü ïðèìåí¼ííûõ ïðàâèë âûâîäà.Òàáëèöà àíàëèçà ýòî äâóìåðíûé ìàññèâ M [A, a], ãäåA íåòåðìèíàë, è a òåðìèíàë èëè ñèìâîë $. Çíà÷åíèåì M [A, a] ìîæåò áûòü íåêîòîðîå ïðàâèëî ãðàììàòèêè èëè94Ãëàâà 4.
Ñèíòàêñè÷åñêèé àíàëèç<oh^FZ]Zabg;<DEIjh]jZffZij_^kdZau\Zxs_]hZgZebaZlhjZ<uoh^=LZ[ebpZZgZebaZlhjZÐèñ. 4.2.ýëåìåíò ¾îøèáêà¿.Ìàãàçèí ìîæåò ñîäåðæàòü ïîñëåäîâàòåëüíîñòü ñèìâîëîâ ãðàììàòèêè ñ $ íà äíå.  íà÷àëüíûé ìîìåíò ìàãàçèíñîäåðæèò òîëüêî íà÷àëüíûé ñèìâîë ãðàììàòèêè íà âåðõóøêå è $ íà äíå.Àíàëèçàòîð ðàáîòàåò ñëåäóþùèì îáðàçîì. Âíà÷àëå àíàëèçàòîð íàõîäèòñÿ â êîíôèãóðàöèè, â êîòîðîé ìàãàçèí ñîäåðæèò S $, íà âõîäíîé ëåíòå w$ (w àíàëèçèðóåìàÿ öåïî÷êà), âûõîäíàÿ ëåíòà ïóñòà. Íà êàæäîì òàêòå àíàëèçàòîð ðàññìàòðèâàåò X ñèìâîë íà âåðõóøêå ìàãàçèíà è a òåêóùèé âõîäíîé ñèìâîë. Ýòè äâà ñèìâîëà îïðåäåëÿþòäåéñòâèÿ àíàëèçàòîðà.
Èìåþòñÿ ñëåäóþùèå âîçìîæíîñòè.1. Åñëè X= a = $, àíàëèçàòîð îñòàíàâëèâàåòñÿ, ñîîáùàåò îá óñïåøíîì îêîí÷àíèè ðàçáîðà è âûäà¼ò ñîäåðæèìîåâûõîäíîé ëåíòû.2. Åñëè X= a 6= $, àíàëèçàòîð óäàëÿåò X èç ìàãàçèíà èïðîäâèãàåò óêàçàòåëü âõîäà íà ñëåäóþùèé âõîäíîé ñèìâîë.3. Åñëè X òåðìèíàë, è X 6= a, òî àíàëèçàòîð îñòàíàâëèâàåòñÿ è ñîîáùàåò î òîì, ÷òî âõîäíàÿ öåïî÷êà íå ïðèíàäëåæèò ÿçûêó.4. Åñëè X íåòåðìèíàë, àíàëèçàòîð çàãëÿäûâàåò â òàáëèöó M [X, a]. Âîçìîæíû äâà ñëó÷àÿ:à) Çíà÷åíèåì M [X, a] ÿâëÿåòñÿ ïðàâèëî äëÿ X .
 ýòîìñëó÷àå àíàëèçàòîð çàìåíÿåò X íà âåðõóøêå ìàãàçè-4.3. Ïðåäñêàçûâàþùèé ðàçáîð ñâåðõó-âíèç95íà íà ïðàâóþ ÷àñòü äàííîãî ïðàâèëà, à ñàìî ïðàâèëîïîìåùàåò íà âûõîäíóþ ëåíòó. Óêàçàòåëü âõîäà íå ïåðåäâèãàåòñÿ.á) Çíà÷åíèåì M [X, a] ÿâëÿåòñÿ ¾îøèáêà¿.  ýòîì ñëó÷àå àíàëèçàòîð îñòàíàâëèâàåòñÿ è ñîîáùàåò î òîì, ÷òîâõîäíàÿ öåïî÷êà íå ïðèíàäëåæèò ÿçûêó.Ðàáîòà àíàëèçàòîðà ìîæåò áûòü çàäàíà ñëåäóþùåé ïðîãðàììîé:Ïîìåñòèòü '$', çàòåì S â ìàãàçèí;do{X=âåðõíèé ñèìâîë ìàãàçèíà;if (X - òåðìèíàë)if (X==InSym){óäàëèòü X èç ìàãàçèíà;InSym=î÷åðåäíîé ñèìâîë;}else {error(); break;}else if (X - íåòåðìèíàë)if (M[X,InSym]=="X->Y1Y2...Yk"){óäàëèòü X èç ìàãàçèíà;ïîìåñòèòü Yk,Yk-1,...Y1 â ìàãàçèí(Y1 íà âåðõóøêó);âûâåñòè ïðàâèëî X->Y1Y2...Yk;}else {error(); break;} /*âõîä òàáëèöû M ïóñò*/}while (X!='$'); /*ìàãàçèí ïóñò*/if (InSym != '$') error(); /*Íå âñÿ ñòðîêà ïðî÷èòàíà*/Ïðèìåð 4.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
