В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 15
Текст из файла (страница 15)
Ðàññìîòðèì ãðàììàòèêó àðèôìåòè÷åñêèõ âûðàæåíèé G=({E, E 0 , T, T 0 , F }, {id, +, ∗, (, )}, P, E) ñ ïðàâèëàìè:E → T E0T 0 → ∗F T 000E → +T ET0 → e0E →eF → (E)T → FT0F → id.Òàáëèöà ïðåäñêàçûâàþùåãî àíàëèçàòîðà äëÿ ýòîé ãðàììàòèêè ïðèâåäåíà íà ðèñ. 4.3. Ïóñòûå êëåòêè òàáëèöû ñîîòâåòñòâóþò ýëåìåíòó ¾îøèáêà¿.96Ãëàâà 4.
Ñèíòàêñè÷åñêèé àíàëèçÍåòåðÂõîäíîé ñèìâîëìèíàëid+*()$EE →T E 0E →T E 0E0E 0→+T E 0E 0→e E 0→e00TT →F TT →F TT0T 0 →e T 0 →∗F T 0T 0→e T 0→eFF →idF →(E)Ðèñ. 4.3.Ïðè ðàçáîðå âõîäíîé öåïî÷êè id + id ∗ id$ àíàëèçàòîð ñîâåðøàåò ïîñëåäîâàòåëüíîñòü øàãîâ, èçîáðàæ¼ííóþíà ðèñ. 4.4. Çàìåòèì, ÷òî àíàëèçàòîð îñóùåñòâëÿåò â òî÷íîñòè ëåâûé âûâîä. Åñëè çà óæå ïðîñìîòðåííûìè âõîäíûìè ñèìâîëàìè ïîìåñòèòü ñèìâîëû ãðàììàòèêè â ìàãàçèíå,òî ìîæíî ïîëó÷èòü â òî÷íîñòè ëåâûå ñåíòåíöèàëüíûå ôîðìû âûâîäà. Äåðåâî ðàçáîðà äëÿ ýòîé öåïî÷êè ïðèâåäåíî íàðèñ. 4.5.4.3.2.
Ôóíêöèè F IRST è F OLLOWÏðè ïîñòðîåíèè òàáëèöû ïðåäñêàçûâàþùåãî àíàëèçàòîðà íàì ïîòðåáóþòñÿ äâå ôóíêöèè F IRST è F OLLOW .Ïóñòü G = (N, T, P, S) ÊÑ-ãðàììàòèêà. Äëÿ α ïðîèçâîëüíîé öåïî÷êè, ñîñòîÿùåé èç ñèìâîëîâ ãðàììàòèêè,îïðåäåëèì F IRST (α) êàê ìíîæåñòâî òåðìèíàëîâ, ñ êîòîðûõ íà÷èíàþòñÿ ñòðîêè, âûâîäèìûå èç α. Åñëè α ⇒∗ e, òîe òàêæå ïðèíàäëåæèò F IRST (α).Îïðåäåëèì F OLLOW (A) äëÿ íåòåðìèíàëà A êàê ìíîæåñòâî òåðìèíàëîâ a, êîòîðûå ìîãóò ïîÿâèòüñÿ íåïîñðåäñòâåííî ñïðàâà îò A â íåêîòîðîé ñåíòåíöèàëüíîé ôîðìå ãðàììàòèêè, òî åñòü ìíîæåñòâî òåðìèíàëîâ a òàêèõ,÷òî ñóùåñòâóåò âûâîä âèäà S ⇒∗ αAaβ äëÿ íåêîòîðûõα, β ∈ (N ∪T )∗ .
Çàìåòèì, ÷òî ìåæäó A è a â ïðîöåññå âûâîäà ìîãóò íàõîäèòüñÿ íåòåðìèíàëüíûå ñèìâîëû, èç êîòîðûõ4.3. Ïðåäñêàçûâàþùèé ðàçáîð ñâåðõó-âíèçÌàãàçèíE$T E0$F T 0E0$id T 0 E 0 $T 0E0$E0$+T E 0 $T E0$F T 0E0$id T 0 E 0 $T 0E0$∗F 0 T 0 E 0 $F T 0E0$id T 0 E 0 $T 0E0$E0$$Âõîäid + id ∗ id$id + id ∗ id$id + id ∗ id$id + id ∗ id$+id ∗ id$+id ∗ id$+id ∗ id$id ∗ id$id ∗ id$id ∗ id$∗id$∗id$id$id$$$$97ÂûõîäE → T E0T → FT0F → idT0 → eE 0 → +T ET → FT0F → idT 0 → ∗F T 0F → idT0 → eE0 → eÐèñ. 4.4.âûâîäèòñÿ e.
Åñëè A ìîæåò áûòü ñàìûì ïðàâûì ñèìâîëîìíåêîòîðîé ñåíòåíöèàëüíîé ôîðìû, òî $ òàêæå ïðèíàäëåæèò F OLLOW (A).Ðàññìîòðèì àëãîðèòìû âû÷èñëåíèÿ ôóíêöèè F IRST .Àëãîðèòì 4.3. Âû÷èñëåíèå F IRST äëÿ ñèìâîëîâ ÊÑãðàììàòèêè.Âõîä. ÊÑ-ãðàììàòèêà G = (N, T, P, S).Âûõîä. Ìíîæåñòâî F IRST (X) äëÿ êàæäîãî ñèìâîëàX ∈ (N ∪ T ).Ìåòîä. Âûïîëíèòü øàãè 13:(1) Åñëè X òåðìèíàë, òî ïîëîæèòü F IRST (X) = {X};åñëè X íåòåðìèíàë, ïîëîæèòü F IRST (X) = ∅.(2) Åñëè â P èìååòñÿ ïðàâèëî X → e, òî äîáàâèòü e êF IRST (X).98Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèç(7( )7LG H)LG7(7H)7LGHÐèñ. 4.5.3) Ïîêà íè ê êàêîìó ìíîæåñòâó F IRST (X) íåëüçÿ óæåáóäåò äîáàâèòü íîâûå ýëåìåíòû, âûïîëíÿòü:do { continue = false;Äëÿ êàæäîãî íåòåðìèíàëà XÄëÿ êàæäîãî ïðàâèëà X → Y1 Y2 ...Yk{i=1; nonstop = true;while (i 6 k && nonstop){äîáàâèòü F IRST (Yi ) \ {e} ê F IRST (X );if (Áûëè äîáàâëåíû íîâûå ýëåìåíòû)continue = true;if (e ∈/ FIRST (Yi ) nonstop = false;else i+ = 1;}if (nonstop) {äîáàâèòü e ê F IRST (X);continue = true;} } }while (continue);Àëãîðèòì 4.4.
Âû÷èñëåíèå F IRST äëÿ öåïî÷êè.Âõîä. ÊÑ-ãðàììàòèêà G = (N, T, P, S).Âûõîä. Ìíîæåñòâî F IRST (X1 X2 . . . Xn ), Xi ∈ (N ∪ T ).4.3. Ïðåäñêàçûâàþùèé ðàçáîð ñâåðõó-âíèç99Ìåòîä. Âûïîëíèòü øàãè 13:(1) Ïðè ïîìîùè àëãîðèòìà 4.3. âû÷èñëèòü F IRST (X) äëÿêàæäîãî X ∈ (N ∪ T ).(2) Ïîëîæèòü F IRST (X1 X2 . . . Xn ) = ∅.(3) {i = 1; nonstop = true;while (i 6 n && nonstop){äîáàâèòü F IRST (Xi ) \ {e} ê F IRST (u);if (e ∈/ F IRST (Xi )nonstop = false;else i+ = 1;}if (nonstop) {äîáàâèòü e ê F IRST (u);} }Ðàññìîòðèì àëãîðèòì âû÷èñëåíèÿ ôóíêöèè F OLLOW .Àëãîðèòì 4.5.
Âû÷èñëåíèå F OLLOW äëÿ íåòåðìèíàëîâ ãðàììàòèêè.Âõîä. ÊÑ-ãðàììàòèêà G = (N, T, P, S).Âûõîä. Ìíîæåñòâî F OLLOW (X) äëÿ êàæäîãî çíàêàX ∈ N.Ìåòîä. Âûïîëíèòü øàãè 14:(1) Ïîëîæèòü F OLLOW (X) = ∅ äëÿ êàæäîãî çíàêà X ∈N.(2) Äîáàâèòü $ ê F OLLOW (S).(3) Åñëè â P eñòü ïðàâèëî âûâîäà A → αBβ , ãäå α, β ∈(N ∪T )∗ , òî âñå ýëåìåíòû èç F IRST (β), çà èñêëþ÷åíèåìe, äîáàâèòü ê F OLLOW (B).(4) Ïîêà íè÷åãî íåëüçÿ áóäåò äîáàâèòü íè ê êàêîìó ìíîæåñòâó F OLLOW (X), âûïîëíÿòü:åñëè â P åñòü ïðàâèëî A → αB èëè A → αBβ , α, β ∈(N ∪ T )∗ , ãäå F IRST (β) ñîäåðæèò e (β ⇒∗ e), òî âñåýëåìåíòû èç F OLLOW (A) äîáàâèòü ê F OLLOW (B).íååÏðèìåð 4.4. Ðàññìîòðèì ãðàììàòèêó èç ïðèìåðà 4.3. Äëÿ100Ãëàâà 4.
Ñèíòàêñè÷åñêèé àíàëèçF IRST (E) = F IRST (T ) = F IRST (F ) = {(, id}F IRST (E 0 ) = {+, e}F IRST (T 0 ) = {∗, e}F OLLOW (E) = F OLLOW (E 0 ) = { ), $}F OLLOW (T ) = F OLLOW (T 0 ) = {+, ), $}F OLLOW (F ) = {+, ∗, ), $}Íàïðèìåð, id è ëåâàÿ ñêîáêà äîáàâëÿþòñÿ ê F IRST (F ) íàøàãå 3 ïðè i = 1, ïîñêîëüêó F IRST (id) = {id} è F IRST (”(”) ={”(”} â ñîîòâåòñòâèè ñ øàãîì 1. Íà øàãå 3 ïðè i = 1, â ñîîòâåòñòâèè ñ ïðàâèëîì âûâîäà T → F T 0 , ê F IRST (T ) äîáàâëÿþòñÿòàêæå id è ëåâàÿ ñêîáêà. Íà øàãå 2 â F IRST (E 0 ) âêëþ÷àåòñÿ e.Òàêæå ïðè âû÷èñëåíèè ìíîæåñòâ F OLLOW íà øàãå 2 âF OLLOW (E) âêëþ÷àåòñÿ $.
Íà øàãå 3, íà îñíîâàíèè ïðàâèëà F → (E), ê F OLLOW (E) äîáàâëÿåòñÿ òàêæå ïðàâàÿ ñêîáêà.Íà øàãå 4, ïðèìåí¼ííîì ê ïðàâèëó E → T E 0 , â F OLLOW (E 0 )âêëþ÷àþòñÿ $ è ïðàâàÿ ñêîáêà. Ïîñêîëüêó E 0 ⇒∗ e, îíè òàêæåïîïàäàþò è âî ìíîæåñòâî F OLLOW (T ).  ñîîòâåòñòâèè ñ ïðàâèëîì âûâîäà E → T E 0 , íà øàãå 3 â F OLLOW (T ) âêëþ÷àþòñÿè âñå ýëåìåíòû èç F IRST (E 0 ), îòëè÷íûå îò e.Îïðåäåëèì òåïåðü ôóíêöèþ F IRSTk (α), ãäå k íàòóðàëüíîå ÷èñëî è α ∈ (N ∪ Σ)∗ .F IRSTk (α) = {w ∈ Σ∗ | ëèáî |w| < k è α ⇒G w, ëèáî|w| = k è α ⇒G wx äëÿ íåêîòîðîãî x ∈ Σ∗ }.Åñëè α ∈ Σ∗ , òî F IRSTk (α) = {w}, ãäå w ýòî ïåðâûåk ñèìâîëîâ öåïî÷êè α ïðè |α| > k è w = α ïðè |α| < k .Ïðèâåä¼ì àëãîðèòì âû÷èñëåíèÿ ôóíêöèè F IRSTk (β),ãäå β = X1 X2 ... Xn ∈ (N ∪ Σ)∗ .Îïðåäåëåíèå.
Ïóñòü Σ íåêîòîðûé àëôàâèò. Åñëè L1 èL2 ïîäìíîæåñòâà Σ∗ , òî ïîëîæèìL1 ⊕k L2 = {w| äëÿ íåêîòîðûõ x ∈ L1 è y ∈ L2ëèáî w = xy , åñëè |xy| 6 k ,ëèáî w ñîñòîèò èç ïåðâûõ k ñèìâîëîâöåïî÷êè xy}Ëåììà 4.1. Äëÿ ëþáîé ÊÑ-ãðàììàòèêè G = (N , Σ,P , S) è ëþáûõ α, β ∈ (N ∪ Σ)∗F IRSTk (αβ) = F IRSTk (α) ⊕k F IRSTk (β)4.3. Ïðåäñêàçûâàþùèé ðàçáîð ñâåðõó-âíèç101Äîêàçàòåëüñòâî îñòàâëÿåì ÷èòàòåëþ â êà÷åñòâå óïðàæíåíèÿ.Aëãîðèòì 4.6.
Âû÷èñëåíèå ôóíêöèè F IRSTk (β).Âõîä. ÊÑ-ãðàììàòèêà G = (N, Σ, P, S) è öåïî÷êà β =X1 X2 ... Xn ∈ (N ∪ Σ)∗ .Âûõîä. F IRSTk (β).Ìåòîä. Òàê êàê ïî ïîñëåäíåé ëåììåF IRSTk (β) = F IRSTk (X1 ) ⊕k F IRSTk (X2 ) ⊕k ...... ⊕k F IRSTk (Xn ),òî äîñòàòî÷íî ïîêàçàòü, êàê íàéòè F IRSTk (X) äëÿ X ∈ N .Åñëè X ∈ Σ ∪ {e}, òî î÷åâèäíî, ÷òî F IRSTk (X) = {X}.Îïðåäåëèì ìíîæåñòâà Fi (X) äëÿ êàæäîãî X ∈ N ∪ Σ èâîçðàñòàþùèõ çíà÷åíèé i > 0:(1) Fi (a) = {a} äëÿ âñåõ a ∈ Σ è i > 0:(2) F0 (A) = {x | x ∈ Σ∗k è ñóùåñòâóåò ïðàâèëî A → xαèç P , äëÿ êîòîðîãî ëèáî |x| = k , ëèáî |x| < k è α = e}.(3) Äîïóñòèì, ÷òî F0 , F1 , ...
, Fi−1 óæå îïðåäåëåíû äëÿâñåõ A ∈ N . ÒîãäàFi (A) = Fi−1 (A) ∪ {x|A → Y1 ... Yn ïðèíàäëåæèò P èx ∈ Fi−1 (Y1 ) ⊕k Fi−1 (Y2 ) ⊕k ... ⊕k Fi−1 (Yn )}(4) Òàê êàê Fi−1 (A) ⊆ Fi (A) ⊆ Σ∗k äëÿ âñåõ A è i, òî âêîíöå êîíöîâ ìû äîéä¼ì äî òàêîãî i, ÷òî Fi−1 (A) = Fi (A)äëÿ âñåõ A ∈ N . Òîãäà ïîëîæèì F IRSTk (A) = Fi (A) äëÿýòîãî çíà÷åíèÿ i.4.3.3.
Êîíñòðóèðîâàíèå òàáëèöû ïðåäñêàçûâàþùåãî àíàëèçàòîðàÄëÿ êîíñòðóèðîâàíèÿ òàáëèöû ïðåäñêàçûâàþùåãî àíàëèçàòîðà ïî ãðàììàòèêå G ìîæåò áûòü èñïîëüçîâàí àëãîðèòì, îñíîâàííûé íà ñëåäóþùåé èäåå. Ïðåäïîëîæèì, ÷òîA → α ïðàâèëî âûâîäà ãðàììàòèêè è a ∈ F IRST (α).Òîãäà àíàëèçàòîð äåëàåò ðàçâ¼ðòêó A ïî α, åñëè âõîäíûìñèìâîëîì ÿâëÿåòñÿ a. Òðóäíîñòü âîçíèêàåò, êîãäà α = eèëè α ⇒∗ e.  ýòîì ñëó÷àå íóæíî ðàçâåðíóòü A â α, åñëèòåêóùèé âõîäíîé ñèìâîë ïðèíàäëåæèò F OLLOW (A) èëèåñëè äîñòèãíóò $ è $ ∈ F OLLOW (A).102Ãëàâà 4. Ñèíòàêñè÷åñêèé àíàëèçÀëãîðèòì 4.7.
Ïîñòðîåíèå òàáëèöû ïðåäñêàçûâàþùåãî àíàëèçàòîðà.Âõîä. ÊÑ-ãðàììàòèêà G = (N, T, P, S).Âûõîä. Òàáëèöà M [A, a] ïðåäñêàçûâàþùåãî àíàëèçàòîðà, A ∈ N , a ∈ T ∪ {$}.Ìåòîä. Äëÿ êàæäîãî ïðàâèëà âûâîäà A→α ãðàììàòèêèâûïîëíèòü øàãè 1 è 2. Ïîñëå ýòîãî âûïîëíèòü øàã 3.(1) Äëÿ êàæäîãî òåðìèíàëà a èç F IRST (α) äîáàâèòü A→αê M [A, a].(2) Åñëè e ∈ F IRST (α), äîáàâèòü A → α ê M [A, b] äëÿêàæäîãî òåðìèíàëà b èç F OLLOW (A).
Êðîìå òîãî, åñëè e ∈ F IRST (α) è $ ∈ F OLLOW (A), äîáàâèòü A → αê M [A, $].(3) Ïîëîæèòü âñå íåîïðåäåë¼ííûå âõîäû ðàâíûìè ¾îøèáêà¿.Ïðèìåð 4.5. Ïðèìåíèì àëãîðèòì 4.7 ê ãðàììàòèêå èç ïðèìåðà 4.3. Ïîñêîëüêó F IRST (T E 0 ) = F IRST (T ) = {(, id }, âñîîòâåòñòâèè ñ ïðàâèëîì âûâîäà E → T E 0 âõîäû M [E, ( ] èM [E, id ] ñòàíîâÿòñÿ ðàâíûìè E → T E 0 . ñîîòâåòñòâèè ñ ïðàâèëîì âûâîäà E 0 → +T E 0 çíà÷åíèåM [E 0 , +] ðàâíî E 0 → +T E 0 .
 ñîîòâåòñòâèè ñ ïðàâèëîì âûâîäàE 0 → e çíà÷åíèÿ M [E 0 , )] è M [E 0 , $] ðàâíû E 0 → e, ïîñêîëüêóF OLLOW (E 0 ) = { ), $}.Òàáëèöà àíàëèçà, ïîñòðîåííàÿ ïî àëãîðèòìó 4.7. äëÿ ýòîéãðàììàòèêè, ïðèâåäåíà íà ðèñ. 4.3.4.3.4. LL(1)-ãðàììàòèêèÀëãîðèòì 4.7 ïîñòðîåíèÿ òàáëèöû ïðåäñêàçûâàþùåãî àíàëèçàòîðà ìîæåò áûòü ïðèìåí¼í ê ëþáîé ÊÑãðàììàòèêå. Îäíàêî äëÿ íåêîòîðûõ ãðàììàòèê ïîñòðîåííàÿ òàáëèöà ìîæåò èìåòü íåîäíîçíà÷íî îïðåäåë¼ííûå âõîäû. Íàïðèìåð, íåòðóäíî äîêàçàòü, ÷òî åñëè ãðàììàòèêà ëåâîðåêóðñèâíà èëè íåîäíîçíà÷íà, òàáëèöà áóäåò èìåòü ïîêðàéíåé ìåðå îäèí íåîäíîçíà÷íî îïðåäåë¼ííûé âõîä.Ãðàììàòèêè, äëÿ êîòîðûõ òàáëèöà ïðåäñêàçûâàþùåãîàíàëèçàòîðà íå èìååò íåîäíîçíà÷íî îïðåäåë¼ííûõ âõîäîâ,4.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
