В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 16
Текст из файла (страница 16)
Ïðåäñêàçûâàþùèé ðàçáîð ñâåðõó-âíèç103íàçûâàþòñÿ LL(1)-ãðàììàòèêàìè. Ïðåäñêàçûâàþùèé àíàëèçàòîð, ïîñòðîåííûé äëÿ LL(1)-ãðàììàòèêè, íàçûâàåòñÿLL(1)-àíàëèçàòîðîì. Ïåðâàÿ áóêâà L â íàçâàíèè ñâÿçàíà ñòåì, ÷òî âõîäíàÿ öåïî÷êà ÷èòàåòñÿ ñëåâà íàïðàâî, âòîðàÿ Lîçíà÷àåò, ÷òî ñòðîèòñÿ ëåâûé âûâîä âõîäíîé öåïî÷êè, 1 ÷òî íà êàæäîì øàãå äëÿ ïðèíÿòèÿ ðåøåíèÿ èñïîëüçóåòñÿîäèí ñèìâîë íåïðî÷èòàííîé ÷àñòè âõîäíîé öåïî÷êè.Äîêàçàíî, ÷òî àëãîðèòì 4.7 äëÿ êàæäîé èç LL(1)-ãðàììàòèê G ñòðîèò òàáëèöó ïðåäñêàçûâàþùåãî àíàëèçàòîðà,ðàñïîçíàþùåãî âñå öåïî÷êè èç L(G) è òîëüêî ýòè öåïî÷êè.Íåòðóäíî äîêàçàòü òàêæå, ÷òî åñëè G LL(1)-ãðàììàòèêà,òî L(G) äåòåðìèíèðîâàííûé ÊÑ-ÿçûê.Ñïðàâåäëèâ òàêæå ñëåäóþùèé êðèòåðèé LL(1)-ãðàììàòèêè.
Ãðàììàòèêà G = (N, T, P, S) ÿâëÿåòñÿ LL(1)-ãðàììàòèêîé òîãäà è òîëüêî òîãäà, êîãäà äëÿ êàæäîé ïàðû ïðàâèëA → α, A → β èç P(òî åñòü ïðàâèë ñ îäèíàêîâîé ëåâîé ÷àñòüþ) âûïîëíÿþòñÿñëåäóþùèå 2 óñëîâèÿ:(1) F IRST (α) ∩ F IRST (β) = ∅;(2) Åñëè e∈F IRST (α), òî F IRST (β)∩F OLLOW (A)= ∅.ßçûê, äëÿ êîòîðîãî ñóùåñòâóåò ïîðîæäàþùàÿ LL(1)ãðàììàòèêà, íàçûâàþò LL(1)-ÿçûêîì. Äîêàçàíî, ÷òî ïðîáëåìà îïðåäåëåíèÿ, ïîðîæäàåò ëè ãðàììàòèêà LL-ÿçûê, ÿâëÿåòñÿ àëãîðèòìè÷åñêè íåðàçðåøèìîé.LI6(E66WKHQLILI ( WKHQ 6 HOVH 6EDDÐèñ. 4.6.( WKHQELI6HOVH 6D(WKHQ 6ED104Ãëàâà 4.
Ñèíòàêñè÷åñêèé àíàëèçÏðèìåð 4.6. Íåîäíîçíà÷íàÿ ãðàììàòèêà íå ÿâëÿåòñÿLL(1). Ïðèìåðîì ìîæåò ñëóæèòü ñëåäóþùàÿ ãðàììàòèêà G =({S, E}, {if, then, else, a, b}, P, S) ñ ïðàâèëàìè:S → if E then S | if E then S else S | aE→bÝòà ãðàììàòèêà ÿâëÿåòñÿ íåîäíîçíà÷íîé, ÷òî èëëþñòðèðóåòñÿ íà ðèñ. 4.6.4.4.LL(k)-ãðàììàòèêèÎïðåäåëåíèå. ÊÑ-ãðàììàòèêà G = (N, Σ, P, S) íàçûâàåòñÿ LL(k)-ãðàììàòèêîé äëÿ íåêîòîðîãî ôèêñèðîâàííîãîk , åñëè èç(1)S ⇒∗i ωAα ⇒l ωβα ⇒∗ ωxè(2)S ⇒∗i ωAα ⇒l ωγα ⇒∗ ωy , äëÿ êîòîðûõ èçF IRSTk (x) = F IRSTk (y), âûòåêàåò, ÷òî β = γ .Ãîâîðÿ ìåíåå ôîðìàëüíî, G áóäåò LL(k)- ãðàììàòèêîé,åñëè äëÿ äàííîé öåïî÷êè ωAα ∈ (N ∪ Σ)∗ è ïåðâûõ k ñèìâîëîâ (åñëè îíè åñòü), âûâîäÿùèõñÿ èç Aα, ñóùåñòâóåò íåáîëåå îäíîãî ïðàâèëà, êîòîðîå ìîæíî ïðèìåíèòü ê A, ÷òîáû ïîëó÷èòü âûâîä êàêîé-íèáóäü òåðìèíàëüíîé öåïî÷êè,íà÷èíàþùåéñÿ ñ ω è ïðîäîëæàþùåéñÿ óïîìÿíóòûìè k òåðìèíàëàìè.Ãðàììàòèêà íàçûâàåòñÿ LL(k)-ãðàììàòèêîé, åñëè îíàLL(k)-ãðàììàòèêà äëÿ íåêîòîðîãî k .Ïðèìåð 4.7.
Ðàññìîòðèì ãðàììàòèêó G = ({S, A, B}, {0, 1,a, b}, P, S), ãäå P ñîñòîèò èç ïðàâèëS → A | B,A → aAb | 0,B → aBbb | 1.Çäåñü L(G) = an 0bn | n > 0 ∪ an 1b2n | n > 0. G íå ÿâëÿåòñÿ LL(k)-ãðàììàòèêîé íè äëÿ êàêîãî k. Èíòóèòèâíî, åñëè ìûíà÷èíàåì ñ ÷òåíèÿ äîñòàòî÷íî äëèííîé öåïî÷êè, ñîñòîÿùåé èçñèìâîëîâ a, òî íå çíàåì, êàêîå èç ïðàâèë S → A è S → B áûëîïðèìåíåíî ïåðâûì, ïîêà íå âñòðåòèì 0 èëè 1.4.5. Ñëåäñòâèÿ îïðåäåëåíèÿ LL(k)-ãðàììàòèêè105Îáðàùàÿñü ê òî÷íîìó îïðåäåëåíèþ LL(k)-ãðàììàòèêè, ïîëîæèì ω = α = e, β = A, γ = B, x = ak 0bk è y = ak 1b2k .Òîãäà âûâîäûS ⇒0l S ⇒l A ⇒∗l ak 0bkS ⇒0l S ⇒l B ⇒∗l ak 1b2kñîîòâåòñòâóþò âûâîäàì (1) è (2) îïðåäåëåíèÿ. Ïåðâûå k ñèìâîëîâ öåïî÷åê x è y ñîâïàäàþò. Îäíàêî çàêëþ÷åíèå β = γ ëîæíî.Òàê êàê k çäåñü âûáðàíî ïðîèçâîëüíî, òî G íå ÿâëÿåòñÿ LLãðàììàòèêîé.4.5. Ñëåäñòâèÿ îïðåäåëåíèÿ LL(k)ãðàììàòèêèÒåîðåìà 4.6.
ÊÑ-ãðàììàòèêà G = (N, Σ, P, S) ÿâëÿåòñÿ LL(k)-ãðàììàòèêîé òîãäà è òîëüêî òîãäà, êîãäàäëÿ äâóõ ðàçëè÷íûõ ïðàâèë A → β è A → γ èç Ð ïåðåñå÷åíèå F IRSTk (βα) ∩ F IRSTk (γα) ïóñòî ïðè âñåõòàêèõ ωAα, ÷òî S ⇒∗l ωAα.Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü. Äîïóñòèì, ÷òî ω, A,α, β è γ óäîâëåòâîðÿþò óñëîâèÿì òåîðåìû, à F IRSTk (βα)∩F IRSTk (γα) ñîäåðæèò x. Òîãäà ïî îïðåäåëåíèþ F IRSTäëÿ íåêîòîðûõ y è z íàéäóòñÿ âûâîäûS ⇒∗l ωAα ⇒l ωβα ⇒∗l ωxyèS ⇒∗l ωAα ⇒l ωγα ⇒∗l ωxz.(Çàìåòèì, ÷òî çäåñü ìû èñïîëüçîâàëè òîò ôàêò, ÷òî N íåñîäåðæèò áåñïîëåçíûõ íåòåðìèíàëîâ, êàê ýòî ïðåäïîëàãàåòñÿ äëÿ âñåõ ðàññìàòðèâàåìûõ ãðàììàòèê.) Åñëè |x| < k,òî y = z = e. Òàê êàê β 6= γ , òî G íå LL(k)-ãðàììàòèêà.Äîñòàòî÷íîñòü. Äîïóñòèì, ÷òî G íå LL(k)-ãðàììàòèêà. Òîãäà íàéäóòñÿ òàêèå äâà âûâîäàS ⇒∗l ωAα ⇒l ωβα ⇒∗l ωxèS ⇒∗l ωAα ⇒l ωγα ⇒∗l ωy ,106Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèç÷òî öåïî÷êè x è y ñîâïàäàþò â ïåðâûõ k ïîçèöèÿõ, íî β 6= γ .Ïîýòîìó A → β è A → γ - ðàçëè÷íûå ïðàâèëà èç P è êàæäîå èç ìíîæåñòâ F IRSTk (βα) è F IRSTk (γα) ñîäåðæèò öåïî÷êó F IRSTk (x), ñîâïàäàþùóþ ñ öåïî÷êîé F IRSTk (y).Ïðèìåð 4.8.
Ãðàììàòèêà G, ñîñòîÿùàÿ èç äâóõ ïðàâèëS → aS | a, íå áóäåò LL(1)-ãðàììàòèêîé, òàê êàêF IRST1 (aS) = F IRST1 (a) = a.Èíòóèòèâíî ýòî ìîæíî îáúÿñíèòü òàê: âèäÿ ïðè ðàçáîðå öåïî÷êè, íà÷èíàþùåéñÿ ñèìâîëîì a, òîëüêî ýòîò ïåðâûé ñèìâîë,ìû íå çíàåì, êàêîå èç ïðàâèë S → aS èëè S → a íàäî ïðèìåíèòü ê S . Ñ äðóãîé ñòîðîíû, G - ýòî LL(2)-ãðàììàòèêà. Âñàìîì äåëå, â îáîçíà÷åíèÿõ òîëüêî ÷òî ïðåäñòàâëåííîé òåîðåìû, åñëè S ⇒∗l ωAα, òî A = S è α = e. Òàê êàê äëÿ S äàíûòîëüêî äâà óêàçàííûõ ïðàâèëà, òî β = aS è γ = a.
ÏîñêîëüêóF IRST2 (aS) = aa è F IRST2 (a) = a, òî ïî ïîñëåäíåé òåîðåìå Gáóäåò LL(2)-ãðàììàòèêîé.4.5.1. Óäàëåíèå ëåâîé ðåêóðñèèÎñíîâíàÿ òðóäíîñòü ïðè èñïîëüçîâàíèè ïðåäñêàçûâàþùåãî àíàëèçà ýòî íàõîæäåíèå òàêîé ãðàììàòèêè äëÿâõîäíîãî ÿçûêà, ïî êîòîðîé ìîæíî ïîñòðîèòü òàáëèöó àíàëèçà ñ îäíîçíà÷íî îïðåäåë¼ííûìè âõîäàìè. Èíîãäà ñ ïîìîùüþ íåêîòîðûõ ïðîñòûõ ïðåîáðàçîâàíèé ãðàììàòèêó,íå ÿâëÿþùóþñÿ LL(1), ìîæíî ïðèâåñòè ê ýêâèâàëåíòíîéLL(1)-ãðàììàòèêå.
Ñðåäè ýòèõ ïðåîáðàçîâàíèé íàèáîëååýôôåêòèâíûìè ÿâëÿþòñÿ ëåâàÿ ôàêòîðèçàöèÿ è óäàëåíèåëåâîé ðåêóðñèè. Çäåñü íåîáõîäèìî ñäåëàòü äâà çàìå÷àíèÿ.Âî-ïåðâûõ, íå âñÿêàÿ ãðàììàòèêà ïîñëå ýòèõ ïðåîáðàçîâàíèé ñòàíîâèòñÿ LL(1), è, âî-âòîðûõ, ïîñëå òàêèõ ïðåîáðàçîâàíèé ïîëó÷àþùàÿñÿ ãðàììàòèêà ìîæåò ñòàòü ìåíåå ïîíèìàåìîé.Íåïîñðåäñòâåííóþ ëåâóþ ðåêóðñèþ, òî åñòü ðåêóðñèþâèäà A → Aα, ìîæíî óäàëèòü ñëåäóþùèì ñïîñîáîì. Ñíà÷àëà ãðóïïèðóåì A-ïðàâèëà:A → Aα1 | Aα2 | .
. . | Aαm | β1 | β2 | . . . | βn ,4.5. Ñëåäñòâèÿ îïðåäåëåíèÿ LL(k)-ãðàììàòèêè107ãäå íèêàêàÿ èç ñòðîê βi íå íà÷èíàåòñÿ ñ A. Çàòåì çàìåíÿåìýòîò íàáîð ïðàâèë íàA → β1 A0 | β2 A0 | . . . | βn A0A0 → α1 A0 | α2 A0 | . . . | αm A0 | eãäå A0 íîâûé íåòåðìèíàë. Èç íåòåðìèíàëà A ìîæíî âûâåñòè òå æå öåïî÷êè, ÷òî è ðàíüøå, íî òåïåðü íåò ëåâîéðåêóðñèè. Ñ ïîìîùüþ ýòîé ïðîöåäóðû óäàëÿþòñÿ âñå íåïîñðåäñòâåííûå ëåâûå ðåêóðñèè, íî íå óäàëÿåòñÿ ëåâàÿ ðåêóðñèÿ, âêëþ÷àþùàÿ äâà èëè áîëåå øàãà. Ïðèâåä¼ííûé íèæå àëãîðèòì 4.8 ïîçâîëÿåò óäàëèòü âñå ëåâûå ðåêóðñèè èçãðàììàòèêè.Àëãîðèòì 4.8. Óäàëåíèå ëåâîé ðåêóðñèè.Âõîä.
ÊÑ-ãðàììàòèêà G áåç e-ïðàâèë (âèäà A → e).Âûõîä. ÊÑ-ãðàììàòèêà G0 áåç ëåâîé ðåêóðñèè, ýêâèâàëåíòíàÿ G.Ìåòîä. Âûïîëíèòü øàãè 1 è 2.(1) Óïîðÿäî÷èòü íåòåðìèíàëû ãðàììàòèêè G â ïðîèçâîëüíîì ïîðÿäêå.(2) Âûïîëíèòü ñëåäóþùóþ ïðîöåäóðó:for (i=1;i<=n;i++){for (j=1;j<=i-1;j++){ïóñòü Aj → β1 |β2 | . . .
|βk - âñå òåêóùèå ïðàâèëàäëÿ Aj ;çàìåíèòü âñå ïðàâèëà âèäà Ai → Aj αíà ïðàâèëà Ai → β1 α|β2 α| . . . |βk α;}óäàëèòü ïðàâèëà âèäà Ai → Ai ;óäàëèòü íåïîñðåäñòâåííóþ ëåâóþ ðåêóðñèþ âïðàâèëàõ äëÿ Ai ;}Ïîñëå (i − 1)-é èòåðàöèè âíåøíåãî öèêëà íà øàãå 2 äëÿëþáîãî ïðàâèëà âèäà Ak → As α, ãäå k < i, âûïîëíÿåòñÿ s >k .  ðåçóëüòàòå íà ñëåäóþùåé èòåðàöèè (ïî i) âíóòðåííèéöèêë (ïî j ) ïîñëåäîâàòåëüíî óâåëè÷èâàåò íèæíþþ ãðàíèöóïî m â ëþáîì ïðàâèëå Ai → Am α, ïîêà íå áóäåò m > i.108Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçÇàòåì, ïîñëå óäàëåíèÿ íåïîñðåäñòâåííîé ëåâîé ðåêóðñèèäëÿ Ai -ïðàâèë, m ñòàíîâèòñÿ áîëüøå i.Àëãîðèòì 4.8 ïðèìåíèì, åñëè ãðàììàòèêà íå èìååò eïðàâèë (ïðàâèë âèäà A → e). Èìåþùèåñÿ â ãðàììàòèêå eïðàâèëà ìîãóò áûòü óäàëåíû ïðåäâàðèòåëüíî. Ïîëó÷àþùàÿñÿ ãðàììàòèêà áåç ëåâîé ðåêóðñèè ìîæåò èìåòü e-ïðàâèëà.4.5.2.
Ëåâàÿ ôàêòîðèçàöèÿOñíîâíàÿ èäåÿ ëåâîé ôàêòîðèçàöèè â òîì, ÷òî â òîìñëó÷àå, êîãäà íåÿñíî, êàêóþ èç äâóõ àëüòåðíàòèâ íàäî èñïîëüçîâàòü äëÿ ðàçâ¼ðòêè íåòåðìèíàëà A, íóæíî èçìåíèòüA-ïðàâèëà òàê, ÷òîáû îòëîæèòü ðåøåíèå äî òåõ ïîð, ïîêàíå áóäåò äîñòàòî÷íî èíôîðìàöèè äëÿ ïðèíÿòèÿ ïðàâèëüíîãî ðåøåíèÿ.Åñëè A → αβ1 | αβ2 äâà A-ïðàâèëà è âõîäíàÿ öåïî÷êà íà÷èíàåòñÿ ñ íåïóñòîé ñòðîêè, âûâîäèìîé èç α, ìû íåçíàåì, ðàçâîðà÷èâàòü ëè ïî ïåðâîìó ïðàâèëó èëè ïî âòîðîìó. Ìîæíî îòëîæèòü ðåøåíèå, ðàçâåðíóâ A → αA0 . Òîãäàïîñëå àíàëèçà òîãî, ÷òî âûâîäèìî èç α, ìîæíî ðàçâåðíóòüïî A0 → β1 èëè ïî A0 → β2 .
Ëåâîôàêòîðèçîâàííûå ïðàâèëàïðèíèìàþò âèäA → αA0A0 → β1 | β2Àëãîðèòì 4.9. Ëåâàÿ ôàêòîðèçàöèÿ ãðàììàòèêè.Âõîä. ÊÑ-ãðàììàòèêà G.Âûõîä. Ëåâîôàêòîðèçîâàííàÿ ÊÑ-ãðàììàòèêà G0 , ýêâèâàëåíòíàÿ G.Ìåòîä. Äëÿ êàæäîãî íåòåðìèíàëà A íàéòè ñàìûé äëèííûé ïðåôèêñ α, îáùèé äëÿ äâóõ èëè áîëåå åãî àëüòåðíàòèâ.Åñëè α 6= e, òî åñòü ñóùåñòâóåò íåòðèâèàëüíûé îáùèé ïðåôèêñ, çàìåíèòü âñå A-ïðàâèëàA → αβ1 | αβ2 | . .
. | αβn | z,ãäå z îáîçíà÷àåò âñå àëüòåðíàòèâû, íå íà÷èíàþùèåñÿ ñ α,íàA → αA0 | z4.5. Ñëåäñòâèÿ îïðåäåëåíèÿ LL(k)-ãðàììàòèêè109A0 → β1 | β2 | . . . | βnãäå A0 íîâûé íåòåðìèíàë. Ïðèìåíÿòü ýòî ïðåîáðàçîâàíèå, ïîêà íèêàêèå äâå àëüòåðíàòèâû íå áóäóò èìåòü îáùåãîïðåôèêñà.Ïðèìåð 4.9. Ðàññìîòðèì âíîâü ãðàììàòèêó óñëîâíûõîïåðàòîðîâ èç ïðèìåðà 4.6:S → if E then S | if E then S else S | aE→bÏîñëå ëåâîé ôàêòîðèçàöèè ãðàììàòèêà ïðèíèìàåò âèäS → if E then SS 0 | aS 0 → else S | eE→bÊ ñîæàëåíèþ, ãðàììàòèêà îñòà¼òñÿ íåîäíîçíà÷íîé, à çíà÷èò,è íå LL(1)-ãðàììàòèêîé.4.5.3. Ðåêóðñèâíûé ñïóñêÂûøå áûë ðàññìîòðåí îäèí èç âàðèàíòîâ òàáëè÷íîóïðàâëÿåìîãî ïðåäñêàçûâàþùåãî àíàëèçà, êîãäà ìàãàçèíÿâíî èñïîëüçîâàëñÿ â ïðîöåññå ðàáîòû àíàëèçàòîðà.
Âîçìîæåí èíîé âàðèàíò ïðåäñêàçûâàþùåãî àíàëèçà, â êîòîðîìêàæäîìó íåòåðìèíàëó ñîïîñòàâëÿåòñÿ ïðîöåäóðà (âîîáùåãîâîðÿ, ðåêóðñèâíàÿ), è ìàãàçèí îáðàçóåòñÿ íåÿâíî ïðè âûçîâàõ òàêèõ ïðîöåäóð. Ïðîöåäóðû ðåêóðñèâíîãî ñïóñêà ìîãóò áûòü çàïèñàíû, êàê ïîêàçàíî íèæå. ïðîöåäóðå A äëÿ ñëó÷àÿ, êîãäà èìååòñÿ ïðàâèëî A →ui , òàêîå, ÷òî ui ⇒∗ e (íàïîìíèì, ÷òî íå ìîæåò áûòü áîëüøå îäíîãî ïðàâèëà, èç êîòîðîãî âûâîäèòñÿ e), ïðèâåäåíûäâà âàðèàíòà 1.1 è 1.2.  âàðèàíòå 1.1 äåëàåòñÿ ïðîâåðêà,ïðèíàäëåæèò ëè ñëåäóþùèé âõîäíîé ñèìâîë F OLLOW (A).Åñëè íåò âûäà¼òñÿ îøèáêà.
 âàðèàíòå 1.2 ýòîãî íå äåëàåòñÿ, òàê ÷òî àíàëèç îøèáêè îòêëàäûâàåòñÿ íà ïðîöåäóðó,âûçâàâøóþ A.void A(){ // A → u1 | u2 | . . . | ukif (InSym ∈ F IRST (ui )) // òîëüêî îäíîìó!if (parse(ui ))result("A → ui ");110Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçelse error();else}//Âàðèàíò 1:if (èìååòñÿ ïðàâèëî A → ui òàêîå, ÷òî ui ⇒∗ e)//Âàðèàíò 1.1if (InSym ∈ F OLLOW (A))result("A → ui ");else error();//Êîíåö âàðèàíòà 1.1//Âàðèàíò 1.2:result("A → ui ");//Êîíåö âàðèàíòà 1.2//Êîíåö âàðèàíòà 1//Âàðèàíò 2:if (íåò ïðàâèëà A → ui òàêîãî, ÷òî ui ⇒∗ e)error();//Êîíåö âàðèàíòà 2boolean parse(u){ // èç u íå âûâîäèòñÿ e!}v = u;while (v 6= e){ // v = Xzif (X - òåðìèíàë a)if (InSym 6= a)return(false);else InSym = getInsym();else // X - íåòåðìèíàë BB ();v = z;}return(true);4.5.4.
Âîññòàíîâëåíèå ïðîöåññà àíàëèçàïîñëå ñèíòàêñè÷åñêèõ îøèáîê ïðèâåä¼ííûõ ïðîãðàììàõ ðåêóðñèâíîãî ñïóñêà áûëàèñïîëüçîâàíà ïðîöåäóðà ðåàêöèè íà ñèíòàêñè÷åñêèå îøèá-4.6. Ðàçáîð ñíèçó-ââåðõ òèïà ñäâèã-ñâ¼ðòêà111êè error().  ïðîñòåéøåì ñëó÷àå ýòà ïðîöåäóðà âûäà¼òäèàãíîñòèêó è çàâåðøàåò ðàáîòó àíàëèçàòîðà. Íî ìîæíîïîïûòàòüñÿ íåêîòîðûì ðàçóìíûì îáðàçîì ïðîäîëæèòü ðàáîòó.
Äëÿ ðàçáîðà ñâåðõó âíèç ìîæíî ïðåäëîæèòü ñëåäóþùèé ïðîñòîé àëãîðèòì.Åñëè â ìîìåíò îáíàðóæåíèÿ îøèáêè íà âåðõóøêå ìàãàçèíà îêàçàëñÿ íåòåðìèíàëüíûé ñèìâîë A è äëÿ íåãî íåòïðàâèëà, ñîîòâåòñòâóþùåãî âõîäíîìó ñèìâîëó, òî ñêàíèðóåì âõîä äî òåõ ïîð, ïîêà íå âñòðåòèì ñèìâîë ëèáî èçF IRST (A), ëèáî èç F OLLOW (A).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
