В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 7
Текст из файла (страница 7)
. . + k n 6 nk n . Òîëüêîýòè ñòðîêè ìîãóò áûòü â ëþáîì Ti . Çíà÷èò, Tm = Tm−1 äëÿíåêîòîðîãî m 6 nk n . Òàêèì îáðàçîì, ïðîöåäóðà, âû÷èñëÿþùàÿ Ti äëÿ âñåõ i > 1 äî òåõ ïîð, ïîêà íå áóäóò íàéäåíû äâà ðàâíûõ ìíîæåñòâà, ãàðàíòèðîâàííî çàêàí÷èâàåòñÿ,çíà÷èò, ýòî àëãîðèòì.Ëèíåéíî-îãðàíè÷åííûé àâòîìàò (ËÎÀ) - ýòî íåäåòåðìèíèðîâàííàÿ ìàøèíà Òüþðèíãà ñ îäíîé ëåíòîé, êîòîðàÿíèêîãäà íå âûõîäèò çà ïðåäåëû |w| ÿ÷ååê, ãäå w âõîä.
Ôîðìàëüíî, ëèíåéíî-îãðàíè÷åííûé àâòîìàò îáîçíà÷àåòñÿ êàêM = (Q, Σ, Γ, D, q0 , F ). Îáîçíà÷åíèÿ èìåþò òîò æå ñìûñë,÷òî è äëÿ ìàøèí Òüþðèíãà. Q - ýòî ìíîæåñòâî ñîñòîÿíèé,F ⊆ Q - ìíîæåñòâî çàêëþ÷èòåëüíûõ ñîñòîÿíèé, Γ - ìíîæåñòâî ëåíòî÷íûõ ñèìâîëîâ, Σ ⊆ Γ - ìíîæåñòâî âõîäíûõñèìâîëîâ, q0 ∈ Q - íà÷àëüíîå ñîñòîÿíèå, D- îòîáðàæåíèå èçQ × Γ â ïîäìíîæåñòâî Q × Γ × {L, R}.40Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèåΣ ñîäåðæèò äâà ñïåöèàëüíûõ ñèìâîëà, îáû÷íî îáîçíàc è $, - ëåâûé è ïðàâûé êîíöåâûå ìàðêåðû, ñî÷àåìûõ °îòâåòñòâåííî.
Ýòè ñèìâîëû ðàñïîëàãàþòñÿ ñíà÷àëà ïî êîíöàì âõîäà è èõ ôóíêöèÿ - ïðåäîòâðàòèòü ïåðåõîä ãîëîâêèçà ïðåäåëû îáëàñòè, â êîòîðîé ðàñïîëîæåí âõîä.Êîíôèãóðàöèÿ M è îòíîøåíèå |−M , ñâÿçûâàþùåå äâåêîíôèãóðàöèè, åñëè âòîðàÿ ìîæåò áûòü ïîëó÷åíà èç ïåðâîé ïðèìåíåíèåì D, îïðåäåëÿþòñÿ òàê æå, êàê è äëÿìàøèí Òüþðèíãà. Êîíôèãóðàöèÿ M îáîçíà÷àåòñÿ êàê(q, A1 , A2 , ... , An , i), ãäå q ∈ Q, A1 , A2 , ...
, An ∈ Γ, i - öåëîåîò 1 äî n. Ïðåäïîëîæèì, ÷òî (p, A, L) ∈ D(q, Ai ) è i > 1.Áóäåì ãîâîðèòü, ÷òî(q, A1 , A2 ... An , i)|−M (p, A1 , A2 ... Ai−1 AAi+1 ... An , i − 1).Åñëè (p, A, R) ∈ D(q, Ai ) è i < n, áóäåì ãîâîðèòü, ÷òî(q, A1 , A2 , ... , An , i)|−M (p, A1 , A2 ...
Ai−1 AAi+1 ... An , i + 1).Òî åñòü M ïå÷àòàåò A ïîâåðõ Ai , ìåíÿåò ñîñòîÿíèå íà pè ïåðåäâèãàåò ãîëîâêó âëåâî èëè âïðàâî, íî íå çà ïðåäåëûîáëàñòè, â êîòîðîé ñèìâîëû ðàñïîëàãàëèñü èñõîäíî. Êàêîáû÷íî, îïðåäåëèì îòíîøåíèå |−∗M êàê(q, α, i)|− ∗M (q, α, i) èåñëè (q1 , α1 , i1 )|− ∗M (q2 , α2 , i2 ) è (q2 , α2 , i2 )|− ∗(q3 , α3 , i3 ),òî (q1 , α1 , i1 )|− ∗M (q3 , α3 , i3 ).c , $ } )∗ßçûê, äîïóñêàåìûé M - ýòî {w | w ∈ (Σ \ { °cè (q0 , °w$,1)|− ∗ (q, α, i) äëÿ íåêîòîðîãî q ∈ F , α ∈ Γ∗ èöåëîãî i}.Áóäåì íàçûâàòü M äåòåðìèíèðîâàííûì, åñëè D(q, A)ñîäåðæèò íå áîëåå îäíîãî ýëåìåíòà äëÿ ëþáûõ q ∈ Q, A ∈ Γ.Íå èçâåñòíî, ñîâïàäàåò ëè êëàññ ìíîæåñòâ, äîïóñêàåìûõäåòåðìèíèðîâàííûìè è íåäåòåìèíèðîâàííûìè ËÎÀ.
ßñíî,÷òî ëþáîå ìíîæåñòâî, äîïóñêàåìîå íåäåòåðìèíèðîâàííûìËÎÀ, äîïóñêàåòñÿ íåêîòîðîé äåòåðìèíèðîâàííîé ÌÒ. Îäíàêî, ÷èñëî ÿ÷ååê ëåíòû, òðåáóåìîé ýòîé ÌÒ, ìîæåò ýêñïîíåíöèàëüíî çàâèñåòü îò äëèíû âõîäà.Êëàññ ìíîæåñòâ, äîïóñêàåìûõ ËÎÀ, â òî÷íîñòè ñîâïàäàåò ñ êëàññîì êîíòåêñòíî - çàâèñèìûõ ÿçûêîâ.Ñâÿçü ëèíåéíî-îãðàíè÷åííûõ àâòîìàòîâ è ÊÇ-ÿçûêîâ41Òåîðåìà 2.7. Åñëè L - êîíòåêñòíî-çàâèñèìûé ÿçûê,òî L äîïóñêàåòñÿ ËÎÀ.Äîêàçàòåëüñòâî. Ïóñòü G = (VN , VT , P, S) - êîíòåêñòíîçàâèñèìàÿ ãðàììàòèêà.
Ïîñòðîèì ËÎÀ M òàêîé, ÷òî îíäîïóñêàåò ÿçûê L(G). Íå âäàâàÿñü â äåòàëè ïîñòðîåíèÿM , ïîñêîëüêó îí äîâîëüíî ñëîæåí, ðàññìîòðèì ñõåìó åãîðàáîòû.  êà÷åñòâå ëåíòî÷íûõ ñèìâîëîâ áóäåì ðàññìàòðèâàòü ïàðû (s1i , s2i ), ãäå s1i ∈ Σ, Σ = VT ∪ {@, $}, s2i ∈ Γ, Γ =VT ∪ VN ∪ {B}.  íà÷àëüíîé êîíôèãóðàöèè ëåíòà ñîäåðæèò(@, B), (a1 , B), ... (an , B), ($, B), ãäå a1 ...an = w - âõîäíàÿöåïî÷êà, n=|w|. Öåïî÷êó ñèìâîëîâ s11 ...s1n áóäåì íàçûâàòü¾ïåðâûì òðåêîì¿, s21 ...s2n - ¾âòîðûì òðåêîì¿. Ïåðâûé òðåêáóäåò ñîäåðæàòü âõîäíóþ ñòðîêó x ñ êîíöåâûìè ìàðêåðàìè.
Âòîðîé òðåê áóäåò èñïîëüçîâàòüñÿ äëÿ âû÷èñëåíèé. Íàïåðâîì øàãå M ïîìåùàåò ñèìâîë S â ñàìîé ëåâîé ÿ÷åéêåâòîðîãî òðåêà. Çàòåì M âûïîëíÿåò ïðîöåäóðó ãåíåðàöèè âñîîòâåòñòâèè ñî ñëåäóþùèìè øàãàìè:1. Ïðîöåäóðà âûáèðàåò ïîäñòðîêó ñèìâîëîâ α èç âòîðîãî òðåêà òàêóþ, ÷òî α → β ∈ P .2. Ïîäñòðîêà α çàìåíÿåòñÿ íà β , ïåðåìåùàÿ, åñëè íåîáõîäèìî, âïðàâî ñèìâîëû ñïðàâà îò α. Åñëè ýòà îïåðàöèÿ ìîãëà áû ïðèâåñòè ê ïåðåìåùåíèþ ñèìâîëà çàïðàâûé êîíöåâîé ìàðêåð, ËÎÀ îñòàíàâëèâàåòñÿ.3. Ïðîöåäóðà íåäåòåðìèíèðîâàííî âûáèðàåò ïåðåéòè íàøàã 1 èëè çàâåðøèòüñÿ.Íà âûõîäå èç ïðîöåäóðû ïåðâûé òðåê âñå åù¼ ñîäåðæèò ñòðîêó x, à âòîðîé òðåê ñîäåðæèò ñòðîêó γ òàêóþ, ÷òîS ⇒∗G γ.
ËÎÀ ñðàâíèâàåò ñèìâîëû ïåðâîãî òðåêà ñ ñîîòâåòñòâóþùèìè ñèìâîëàìè âòîðîãî òðåêà. Åñëè ñðàâíåíèåíåóñïåøíî, ñòðîêè ñèìâîëîâ ïåðâîãî è âòîðîãî òðåêîâ íåîäèíàêîâû è ËÎÀ îñòàíàâëèâàåòñÿ áåç äîïóñêà. Åñëè ñòðîêè îäèíàêîâû, ËÎÀ îñòàíàâëèâàåòñÿ è äîïóñêàåò.Åñëè x ∈ L(G), òî ñóùåñòâóåò íåêîòîðàÿ ïîñëåäîâàòåëüíîñòü øàãîâ, íà êîòîðîé ËÎÀ ñòðîèò x íà âòîðîì òðåêå42Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèåè äîïóñêàåò âõîä. Àíàëîãè÷íî, äëÿ òîãî, ÷òîáû ËÎÀ äîïóñòèë x, äîëæíà ñóùåñòâîâàòü ïîñëåäîâàòåëüíîñòü øàãîâòàêàÿ, ÷òî x ìîæåò áûòü ïîñòðîåí íà âòîðîì òðåêå.
Òàêèìîáðàçîì, äîëæåí áûòü âûâîä x èç S â G.Îòìåòèì ñõîæåñòü ýòèõ ðàññóæäåíèé è ðàññóæäåíèéâ ñëó÷àå ïðîèçâîëüíîé ãðàììàòèêè. Òîãäà ïðîìåæóòî÷íûå ñåíòåíöèàëüíûå ôîðìû ìîãëè èìåòü äëèíó, ïðîèçâîëüíî áîëüøóþ ïî ñðàâíåíèþ ñ äëèíîé âõîäà. Êàê ñëåäñòâèå, òðåáîâàëàñü âñÿ ìîùü ìàøèí Òüþðèíãà.  ñëó÷àåêîíòåêñòíî-çàâèñèìûõ ãðàììàòèê ïðîìåæóòî÷íûå ñåíòåíöèàëüíûå ôîðìû íå ìîãóò áûòü äëèííåå âõîäà.Òåîðåìà 2.8. Åñëè L äîïóñêàåòñÿ ËÎÀ, òî L - êîíòåêñòíî - çàâèñèìûé ÿçûê.Äîêàçàòåëüñòâî. Êîíñòðóêöèÿ ÊÇà ïî ËÎÀ àíàëîãè÷íàêîíñòðóêöèè ãðàììàòèêè òèïà 0, ìîäåëèðóþùåé ìàøèíóÒüþðèíãà. Ðàçëè÷èå çàêëþ÷àòñÿ â òîì, ÷òî íåòåðìèíàëûÊÇà äîëæíû óêàçûâàòü íå òîëüêî òåêóùåå è èñõîäíîå ñîäåðæèìîå ÿ÷ååê ëåíòû ËÎÀ, íî è òî, ÿâëÿåòñÿ ëè ÿ÷åéêàñîñåäíåé ñïðàâà èëè ñëåâà ñ êîíöåâûì ìàðêåðîì.
Êðîìåòîãî, ñîñòîÿíèå ËÎÀ äîëæíî êîìáèíèðîâàòüñÿ ñ ñèìâîëîìïîä ãîëîâêîé, ïîñêîëüêó ÊÇÃ íå ìîæåò èìåòü ðàçäåëüíûåñèìâîëû äëÿ êîíöåâûõ ìàðêåðîâ è ñîñòîÿíèÿ ËÎÀ, òàê êàêýòè ñèìâîëû äîëæíû áûëè áû áûòü çàìåíåíû íà e, êîãäàñòðîêà ïðåâðàùàåòñÿ â òåðìèíàëüíóþ.Òåîðåìà 2.9.
Ñóùåñòâóþò ðåêóðñèâíûå ìíîæåñòâà,íå ÿâëÿþùèåñÿ êîíòåêñòíî - çàâèñèìûìè.Äîêàçàòåëüñòâî. Âñå ñòðîêè â {0, 1}∗ ìîæíî çàíóìåðîâàòü. Ïóñòü xi − i-îå ñëîâî. Ìû ìîæåì çàíóìåðîâàòü âñåãðàììàòèêè òèïà 0, òåðìèíàëüíûìè ñèìâîëàìè êîòîðûõÿâëÿþòñÿ 0 è 1. Ïîñêîëüêó èìåíà ïåðåìåííûõ íå âàæíû èêàæäàÿ ãðàììàòèêà èìååò êîíå÷íîå èõ ÷èñëî, ìîæíî ïðåäïîëîæèòü, ÷òî ñóùåñòâóåò ñ÷¼òíîå ÷èñëî ïåðåìåííûõ.Ïðåäñòàâèì ïåðåìåííûå â äâîè÷íîé êîäèðîâêå êàê 01,011, 0111, 01111 è ò.ä. Ïðåäïîëîæèì, ÷òî 01 âñåãäà ÿâëÿåòñÿÑâÿçü ëèíåéíî-îãðàíè÷åííûõ àâòîìàòîâ è ÊÇ-ÿçûêîâ43ñòàðòîâûì ñèìâîëîì.
Êðîìå òîãî, â ýòîé êîäèðîâêå òåðìèíàë 0 áóäåò ïðåäñòàâëÿòüñÿ êàê 00, à òåðìèíàë 1 êàê 001.Ñèìâîë ¾→¿ ïðåäñòàâëÿåòñÿ êàê 0011, à çàïÿòàÿ êàê 00111.Ëþáàÿ ãðàììàòèêà ñ òåðìèíàëàìè 0 è 1 ìîæåò áûòü ïðåäñòàâëåíà ñòðîêîé ïðàâèë, èñïîëüçóþùåé ñòðåëêó (0011) äëÿðàçäåëåíèÿ ëåâîé è ïðàâîé ÷àñòåé, è çàïÿòîé (00111) äëÿðàçäåëåíèÿ ïðàâèë. Ñòðîêè, ïðåäñòàâëÿþùèå ñèìâîëû, èñïîëüçóåìûå â ïðàâèëàõ, - ýòî 00, 001 è 01i äëÿ i = 1, 2, ...Ìíîæåñòâî èñïîëüçóåìûõ ïåðåìåííûõ îïðåäåëÿåòñÿ íåÿâíî ïðàâèëàìè.Îòìåòèì, ÷òî íå âñå ñòðîêè èç 0 è 1 ïðåäñòàâëÿþò ãðàììàòèêè, è íå îáÿçàòåëüíî ÊÇÃ. Îäíàêî, ïî äàííîé ñòðîêåëåãêî ìîæíî ñêàçàòü, ïðåäñòàâëÿåò ëè îíà ÊÇÃ. i-þ ãðàììàòèêó ìîæíî íàéòè, ãåíåðèðóÿ äâîè÷íûå ñòðîêè â îïèñàííîì ïîðÿäêå ïîêà íå ñãåíåðèðóåòñÿ i-ÿ ñòðîêà, ÿâëÿþùàÿñÿÊÇÃ. Ïîñêîëüêó èìååòñÿ áåñêîíå÷íîå ÷èñëî ÊÇÃ, èõ ìîæíîçàíóìåðîâàòü â íåêîòîðîì ïîðÿäêå G1 , G2 , ...Îïðåäåëèì L = {xi |xi ∈/ L(Gi )}.
L ðåêóðñèâíî. Ïî ñòðîêå xi ëåãêî ìîæíî îïðåäåëèòü i è çàòåì îïðåäåëèòü Gi . Ïîòåîðåìå 2.6. èìååòñÿ àëãîðèòì, îïðåäåëÿþùèé äëÿ xi ïðèíàäëåæèò ëè îí L(Gi ), ïîñêîëüêó Gi ÊÇÃ. Òàêèì îáðàçîìèìååòñÿ àëãîðèòì äëÿ îïðåäåëåíèÿ äëÿ ëþáîãî x ïðèíàäëåæèò ëè îí G.Ïîêàæåì òåïåðü, ÷òî L íå ãåíåðèðóåòñÿ íèêàêîé ÊÇãðàììàòèêîé. Ïðåäïîëîæèì, ÷òî L ãåíåðèðóåòñÿ ÊÇãðàììàòèêîé Gi .
Âî-ïåðâûõ, ïðåäïîëîæèì, ÷òî xi ∈ L. Ïîñêîëüêó L(Gi ) = L, xi ∈ L(Gi ). Íî òîãäà ïî îïðåäåëåíèþxi ∈/ L(Gi ) - ïðîòèâîðå÷èå. Òàêèì îáðàçîì ïðåäïîëîæèì,÷òî xi ∈/ L. Ïîñêîëüêó L(Gi ) = L, xi ∈/ L(Gi ). Íî òîãäàïî îïðåäåëåíèþ xi ∈ L(Gi ) - ñíîâà ïðîòèâîðå÷èå.
Èç ÷åãî ìîæíî çàêëþ÷èòü, ÷òî L íå ãåíåðèðóåòñÿ Gi . Ïîñêîëüêóïðèâåä¼ííûé âûøå àðãóìåíò ñïðàâåäëèâ äëÿ êàæäîé ÊÇãðàììàòèêè Gi â ïåðå÷èñëåíèè, è ïîñêîëüêó ïåðå÷èñëåíèåñîäåðæèò âñå ÊÇ-ãðàììàòèêè, ìîæíî çàêëþ÷èòü, ÷òî L íåÊÇ-ÿçûê. Ïîýòîìó L - ðåêóðñèâíîå ìíîæåñòâî, íå ÿâëÿþùååñÿ êîíòåêñòíî-çàâèñèìûì.Ãëàâà 3.Ëåêñè÷åñêèé àíàëèçÎñíîâíàÿ çàäà÷à ëåêñè÷åñêîãî àíàëèçà ðàçáèòü âõîäíîé òåêñò, ñîñòîÿùèé èç ïîñëåäîâàòåëüíîñòè îäèíî÷íûõñèìâîëîâ, íà ïîñëåäîâàòåëüíîñòü ñëîâ, èëè ëåêñåì, òî åñòüâûäåëèòü ýòè ñëîâà èç íåïðåðûâíîé ïîñëåäîâàòåëüíîñòèñèìâîëîâ.
Âñå ñèìâîëû âõîäíîé ïîñëåäîâàòåëüíîñòè ñ ýòîéòî÷êè çðåíèÿ ðàçäåëÿþòñÿ íà ñèìâîëû, ïðèíàäëåæàùèåêàêèì-ëèáî ëåêñåìàì, è ñèìâîëû, ðàçäåëÿþùèå ëåêñåìû(ðàçäåëèòåëè).  íåêîòîðûõ ñëó÷àÿõ ìåæäó ëåêñåìàìè ìîæåò è íå áûòü ðàçäåëèòåëåé. Ñ äðóãîé ñòîðîíû, â íåêîòîðûõ ÿçûêàõ ëåêñåìû ìîãóò ñîäåðæàòü íåçíà÷àùèå ñèìâîëû(íàïðèìåð, ñèìâîë ïðîáåëà â Ôîðòðàíå).  Ñè ðàçäåëèòåëüíîå çíà÷åíèå ñèìâîëîâ-ðàçäåëèòåëåé ìîæåò áëîêèðîâàòüñÿ(¾\¿ â êîíöå ñòðîêè âíóòðè "...").Îáû÷íî âñå ëåêñåìû äåëÿòñÿ íà êëàññû.
Ïðèìåðàìè òàêèõ êëàññîâ ÿâëÿþòñÿ ÷èñëà (öåëûå, âîñüìåðè÷íûå, øåñòíàäöàòèðè÷íûå, äåéñòâèòåëüíûå è ò.ä.), èäåíòèôèêàòîðû,ñòðîêè. Îòäåëüíî âûäåëÿþòñÿ êëþ÷åâûå ñëîâà è ñèìâîëûïóíêòóàöèè (èíîãäà èõ íàçûâàþò ñèìâîëû-îãðàíè÷èòåëè).Êàê ïðàâèëî, êëþ÷åâûå ñëîâà ýòî íåêîòîðîå êîíå÷íîåïîäìíîæåñòâî èäåíòèôèêàòîðîâ.  íåêîòîðûõ ÿçûêàõ (íàïðèìåð, ÏË/1) ñìûñë ëåêñåìû ìîæåò çàâèñåòü îò å¼ êîíòåêñòà è íåâîçìîæíî ïðîâåñòè ëåêñè÷åñêèé àíàëèç â îòðûâåîò ñèíòàêñè÷åñêîãî.Ãëàâà 3. Ëåêñè÷åñêèé àíàëèç45Äëÿ îñóùåñòâëåíèÿ äâóõ äàëüíåéøèõ ôàç àíàëèçà ëåêñè÷åñêèé àíàëèçàòîð âûäà¼ò èíôîðìàöèþ äâóõ òèïîâ: äëÿñèíòàêñè÷åñêîãî àíàëèçàòîðà, ðàáîòàþùåãî âñëåä çà ëåêñè÷åñêèì, ñóùåñòâåííà èíôîðìàöèÿ î ïîñëåäîâàòåëüíîñòèêëàññîâ ëåêñåì, îãðàíè÷èòåëåé è êëþ÷åâûõ ñëîâ, à äëÿ êîíòåêñòíîãî àíàëèçàòîðà, ðàáîòàþùåãî âñëåä çà ñèíòàêñè÷åñêèì, ñóùåñòâåííà èíôîðìàöèÿ î êîíêðåòíûõ çíà÷åíèÿõîòäåëüíûõ ëåêñåì (èäåíòèôèêàòîðîâ, ÷èñåë è ò.ä.).Òàêèì îáðàçîì, îáùàÿ ñõåìà ðàáîòû ëåêñè÷åñêîãî àíàëèçàòîðà òàêîâà.
Ñíà÷àëà âûäåëÿåòñÿ îòäåëüíàÿ ëåêñåìà(ïðè ýòîì, âîçìîæíî, èñïîëüçóþòñÿ ñèìâîëû-ðàçäåëèòåëè).Êëþ÷åâûå ñëîâà ðàñïîçíàþòñÿ ÿâíûì âûäåëåíèåì íåïîñðåäñòâåííî èç òåêñòà, ëèáî ñíà÷àëà âûäåëÿåòñÿ èäåíòèôèêàòîð, à çàòåì äåëàåòñÿ ïðîâåðêà íà ïðèíàäëåæíîñòü åãîìíîæåñòâó êëþ÷åâûõ ñëîâ.Åñëè âûäåëåííàÿ ëåêñåìà ÿâëÿåòñÿ îãðàíè÷èòåëåì, òîýòîò îãðàíè÷èòåëü (òî÷íåå, íåêîòîðûé åãî ïðèçíàê) âûäà¼òñÿ êàê ðåçóëüòàò ëåêñè÷åñêîãî àíàëèçà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
