Zbiory First i Follow

Następująca wersja przejrzana tej strony, którą oznaczono 12 mar 2017, była oparta na tej wersji.

First_G,k(α), Follow_G,k(α) – zbiory słów nad pewnym alfabetem, służące do analizowania gramatyk formalnych, np. podczas konstruowania analizatorów składniowych (parserów). W uproszczeniu:

First_G,k(α) – to prefiksy długości k słów wyprowadzalnych z α w gramatyce G,
Follow_G,k(α) – to prefiksy długości k, fragmentów słów wyprowadzalnych z gramatyki G, znajdujące się bezpośrednio za fragmentem wyprowadzonym z α,

gdzie α to ciąg symboli z gramatyki (terminalnych i nieterminalnych); w praktyce, zwłaszcza dla Follow jest to pojedynczy symbol nieterminalny.

Zbiory te pozwalają określić czy gramatyka posiada pewne własności, np. ułatwiające analizę składniową (ang. parsing). Podczas konstrukcji parsera za ich pomocą oblicza się jakie są możliwe konfiguracje analizatora i jakie powinny być podjęte działania w danej konfiguracji.

Definicja

K-głowa napisu x, oznaczana przez k:x, to prefiks długości min (k, |x|) napisu x. Bardziej formalnie: niech $x=a_{1}a_{2}\ldots a_{n}$ wtedy:

$k:x={\begin{cases}x,&{\mbox{dla}}\quad |x|\leq k\\a_{1}\ldots a_{k},&{\mbox{dla}}\quad |x|>k\end{cases}}$ .

Dla gramatyki G=(Σ,N,P,S):

zbiór First_G,k(α) jest zbiorem wszystkich k-głów napisów dających się wyprowadzić w G z α, czyli First_G,k(α) = {w | istnieje x∈Σ^* taki że α ⇒^* x, a w=k:x};
zbiór Follow_G,k(α) zawiera wszystkie k-głowy które mogą wystąpić po α, czyli Follow_G,k(α) = {w | istnieją μ, x takie że S ⇒^* μαx, i w∈First_G,k(x).

Jeśli nie prowadzi to do niejednoznaczności First_G,k można skracać do First_k, Follow_G,k do Follow_k. Indeks k dla First i Follow można pominąć gdy ma wartość równą 1.

Obliczanie dla k =1

First

Zbiór First możemy określić dla symbolu terminalnego, symbolu nieterminalnego oraz ciągu symboli. Jeśli x jest symbolem terminalnym wtedy First(x) = {x}. Dla symbolu nieterminalnego X używamy następującego algorytmu:

inicjujemy wszystkie zbiory dla poszczególnych symboli nieterminalnych jako puste
jeśli jest produkcja postaci X → aα wtedy dodajemy a do First(X)
jeśli jest produkcja X → ε wtedy dodajemy ε do First(X)
jeśli jest produkcja postaci X → Y₁ Y₂ ... Y_k wtedy dla "i" takich że wszystkie Y₁ ... Y_i-1 są nieterminalne oraz First(Y_j) j=1...i-1 zawierają ε dodać każdy symbol różny od ε w First(Y_j) j=1...i do First(X); jeśli ε należy do wszystkich First(Y_j) j=1...k wtedy należy dodać ε do First(X)
w każdym przebiegu stosujemy punkty 2,3,4 powyższego algorytmu do kolejnych produkcji; powtarzamy tak długo aż w ostatniej iteracji nie dodamy żadnego symbolu do żadnego ze zbiorów. Korzystniejsza jest odwrotna kolejność przeglądania produkcji ponieważ dla symbolu dla którego wyznaczamy First, symbole z których korzystamy są definiowane zwykle później.

Przykładowa implementacja może być zbliżona do poniższego pseudokodu.

set [ilosc_nieterminalnych]First; //tablica zbiorów First dla każdego symbolu nieterminalnego
inicjujemy wszystkie zbiory First jako puste;//punkt 1
void make_First_sets(void)
{
  bool changed; //w jednym przebiegu pętli zostały dodane nowe symbole
  do
  {
    changed = false;
    for (X po wszystkich symbolach nieterminalnych (od ostatniego))
    {
        for (po regułach produkcji dla tego symbolu nieterminnalnego (od ostatniej))
        {
          bool jest_epsilon=true; //symbol prawej strony produkcji może go zmienić na false
          for (po symbolach prawej strony produkcji)
          // gdy produkcja jest postaci X->epsilon, nie wykonujemy tej pętli  
          {
            if (symbol jest terminalem)
            { // punkt 2 gdy nieterminalny jest na początku produkcji
              // również wykonujemy to gdy a jest po  Y1Y2...Yk i wszystkie Yi mają epsilon
               jest_epsilon=false;
               symbol do FirsSets[X];
               if (cos_dodalismy) changed=true;
               break;//bo nie epsilon
            }
            else
            { //punkt 4
              //symbol jest nieterminalny, nazwiemy go Y;
              do First[X] dodajemy symbole oprócz epsilona z First[Y];
              if (cos_dodalismy) changed=true;
              if First[Y] nie zawiera epsilona
              {
                jest_epsilon=false;
                break;//bo nie epsilon
              }
            }
          }
          // koniec pętli po symbolach prawej strony produkcji
          // lub była produkcja X->epsilon (punkt 3)
          if (jest_epsilon) //co oznaca że wszystkie były nieterminalnymi i zawierały epsilon
          { //jeśli pętla się wykonała to oznacza że wszystkie Yi zawierały epsilon
            epsilon do FirsSets[X]
            if (cos_dodalismy) changed=true;
          }
        }
    }
  }
  while (changed);
}

Dla ciągu symboli terminalnych i nieterminalnych działamy jak w punkcie 4 powyższego algorytmu - jeśli mamy obliczyć First(α) i α jest ciągiem postaci Y₁ Y₂ ... Y_k wtedy w podobny sposób jak obliczaliśmy zbiór symboli dodanych do First(X) uzyskamy zbiór First(α).

Follow

W praktyce (jak na przykład przy tworzeniu parserów SLR) zbiór Follow oblicza się dla pojedynczych symboli nieterminalnych. Stosowany jest algorytm:

inicjujemy wszystkie zbiory dla symboli nieterminalnych jako puste z wyjątkiem symbolu startowego Z zawierającego znak końca strumienia $
jeśli jest produkcja A → αBβ wtedy wszystkie symbole różne od ε należące do First(β) zawierają się w Follow(B) (W zbiorach Follow występuje symbolu specjalny $, natomiast nie ma ε które jest w zbiorach First)
jeśli jest produkcja A → αB lub A → αBβ przy czym First(β) zawiera ε wtedy do Follow(B) dodawane są wszystkie symbole z Follow(A)
w każdym przebiegu stosujemy punkty 2,3 powyższego algorytmu do kolejnych produkcji a w każdej produkcji do każdego symbolu nieterminalnego po prawej stronie produkcji; powtarzamy tak długo aż w ostatniej iteracji nie dodamy żadnego symbolu do żadnego ze zbiorów.

set [ilosc_nieterminalnych]Follow; //tablica zbiorów Follow dla każdego symbolu nieterminalnego
//w konkretnej implementacji set może być klasą zawierającą zbiór symboli terminalnych plus
//znak końca strumienia, w odróżnieniu od typu zbioru dla First gdzie zamiast tego miał obsługiwać epsilon
inicjujemy wszystkie zbiory Follow jako puste
z wyjątkiem zbioru Follow[Startowy] inicjowany na $//punkt 1
void make_Follow_sets(First)
{
  bool changed; //w jednym przebiegu pętli zostały dodane nowe symbole
  do
  {
    changed = false;
    for (A po wszystkich symbolach nieterminalnych)
    {
        for (po regułach produkcji dla tego symbolu nieterminalnego)
        {
           for (B po symbolach nieterminalnych prawej strony produkcji)
           {
             bool jest_epsilon=true;  // element ciągu beta może go zmienić na false;
             for (b po elementach beta) // czyli symbolach znajdujących się za B aż do końca produkcji
             {
               if (b jest terminalnym)
               { //część punktu 2
                 do Follow[B] dodajemy b;
                 if (cos_dodalismy) changed=true; //gdy wcześniej nie było tego symbolu z zbiorze
                 jest_epsilon=false;
                 break;//pętli po beta
               }
               else //punkt 2
               { //b jest nieterminalnym
                 do Follow[B] dodajemy symbole oprócz epsilona z First[b];
                 if (cos_dodalismy) changed=true;
                 if (First[b] nie zawiera epsilona)
                 {
                    jest_epsilon=false;
                    break;
                 }
               }
             }
             if (jest_epsilon)
             {  //punkt 3
               do Follow[B] dodajemy symbole z Follow[A]; //wraz z symbolem $
               if (cos_dodalismy) changed=true;
             }
           }
        }
    }
  }
  while (changed);
}

Przykład

Mamy gramatykę

(1) E → T E'

(2) E' → + T E'

(3) E' → ε

(4) T → F T'

(5) T' → * F T'

(6) T' → ε

(7) F → ( E )

(8) F → i

Chcąc wykorzystać gramatykę do budowy parsera, uzupełniamy ją nowym startowym symbolem nieterminalnym Z i produkcją:

(0) Z → E

First

Stosując algorytm tworzenia zbiorów First dla tej gramatyki mamy wartość zbiorów dla symboli nieterminalnych w kolejnych iteracjach:

Symbol	0	1
Z	( i	( i
E	( i	( i
E'	ε +	ε +
T	( i	( i
T'	ε *	ε *
F	( i	( i

W kolejnych produkcjach (od 8 do 0) dodajemy symbole do zbiorów First skojarzonych z symbolem nieterminalnym:

8:i do F

7:( do F

6:ε do T'

5:* do T'

4:( i do T

3:ε do E'

2:+ do E'

1:( i do E

0:( i do Z

W drugim przebiegu produkcje które mogłyby coś ewentualnie dodać to 4,1 i 0 (których prawa strona zaczyna się od nieterminalnego) ale nie zostanie nic dodane, bo ostatnio First(F) się nie zmieniło.

Follow

Wartość zbiorów Follow dla symboli nieterminalnych w kolejnych iteracjach:

Symbol	0	1	2
Z	$	$	$
E	$ )	$ )	$ )
E'	$	$ )	$ )
T	$ +	$ + )	$ + )
T'	$ +	$ + )	$ + )
F	$ + *	$ + * )	$ + * )

Follow(Z) zawiera symbol końca strumienia $. W kolejnych produkcjach i dla kolejnych symboli nieterminalnych występujących po prawej stronie produkcji dodajemy symbole do zbiorów Follow skojarzonych z symbolem nieterminalnym:

0:Z → E

$ do Follow(E) z Follow(Z)

1:E → T E'

dla T z pkt 2 wszystkie bez ε z First(E') czyli + do Follow(T); z pkt 3 ponieważ ε zawiera się w Follow(E), wtedy do Follow(T) z Follow(E) czyli $
dla E' z pkt 3 do Follow(E') z Follow(E) czyli $

2:E' → + T E'

dla T z pkt 2 wszystkie bez ε z First(E') już były;z pkt 3 z Follow(E') do Follow(T) symbol $ który już był
z Follow(E') do Follow(E') - nic się nie zmienia

3:E' → ε

pomijamy

4:T → F T'

dla F z pkt 2 dodać bez ε z First(T') czyli * do Follow(F); z punktu 3 z Follow(T) do Follow(F) czyli {$,+}
dla T' z pkt 3 z Follow(T) do Follow(T') czyli {$,+}

5:T' → * F T'

dla F z pkt 2 dodać bez ε z First(T') czyli * do Follow(F) - już dodane; z pkt 3 z Follow(T') do Follow(F) czyli {$,+} - już są
dla T' z pkt 3 z Follow(T') do Follow(T') - bez zmian

6:T' → ε

pomijamy

7:F → ( E )

dla E z pkt 2 dodajemy First(')')=')' do Follow(E); punkt 3 nie ma tu zastosowania

8:F → i

nie ma symbolu nieterminalnego po prawej stronie produkcji

Drugi przebieg:

1:E → T E'

dla T z Follow(E) do Follow(T) dodany ')'
dla E' z Follow(E) do Follow(E') dodany ')'

4:T → F T'

dla F z Follow(T) do Follow(F) dodany ')'
dla T'z Follow(T) do Follow(T') dodany ')'

Zobacz też

Generowanie parserów LR