Zbiory First i Follow

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|\leqslant 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:

definiujemy funkcję add_rule_first która dodaje do zbioru podanego jako parametr początkowe symbole możliwych wyprowadzeń z produkcji. Jako parametr może mieć indeks od którego symbolu produkcji zaczynamy – do obliczania First jest zawsze równy zero a większy od zera dla Follow.
jeśli produkcja jest postaci → ε wtedy dodajemy ε do zbioru wynikowego
jeśli jest produkcja postaci → aα wtedy dodajemy a do zbioru wynikowego
jeśli jest produkcja zaczynająca się z symboli nieterminalnych i nieterminalnych, dodajemy do zbioru wynikowego symbole z tego zbioru nieterminalnego bez ε, jeśli nie zawiera ε przerywamy pętlę, gdy zawiera, idziemy do następnego symbolu produkcji.
gdy wszystkie symbole zawierają ε, wtedy dodajemy ε do zbioru wynikowego.
funkcja zwraca false/true w zależności czy zbiór wynikowy został zmodyfikowany

Mając add_rule_first:

inicjujemy wszystkie zbiory dla poszczególnych symboli nieterminalnych jako puste
w głównej pętli ustawiamy changed na false
po wszystkich symbolach nietermianalnych
po wszystkich symbolach produkcji
wołamy add_rule_first z parametrem First[symbol nieterminalny, bieżąca reguła, indeks startowy = 0];

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

bool add_rule_first(outset, rule, index)
{
    for (po symbolach produkcji od indeksu)
    // 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 outset;
               if (cos_dodalismy) changed=true;
               break;//bo nie epsilon
            }
            else
            { //punkt 4
              //symbol jest nieterminalny, nazwiemy go Y;
              do outset 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 oznacza ż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 outset
            if (dodalismy ten epsilon bo go nie było) changed=true;
          }
    }
}

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()
{
  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 nieterminalnego (od ostatniej))
        {
          bool jest_epsilon=true; //symbol prawej strony produkcji może go zmienić na false
          bool retchanged = add_rule_first(First[X], rule, 0)
          if (retchanged) changed = true;
    }
  }
  while (changed);
}

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
w głównej pętli ustawiamy changed na false
po wszystkich nieterminalnych
po wszystkich produkcjach
jeśli jest produkcja A → αBβ wtedy wołamy add_rule_first od pozycji β z wynikowym B

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 retchanged = add_rule_first(B,reguła,indeks za B);
             if (retchanged) changed = true;
           }
        }
    }
  }
  while (changed);
}

Funkcja add_rule_first przydaje się także przy sprawdzaniu warunku LL(1)

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 ')'

Obliczanie dla k >=1

W konstrukcji dla k=1 można zauważyć że mamy zarówno ε jak i pojedyncze tokeny (W algorytmie można utożsamić ε ze znakiem końca strumienia $) czyli występują ciągi długości 0, jak i 1. Dla k>1 w zbiorach będą ciągi długości od 0 (ε) do k. Będziemy mieli operacje zarówno dołączania ciągów do zbiorów, jak i modyfikacji tych ciągów poprzez dołączanie tokenów do ciągów. Same algorytmy niewiele się zmieniają, zmienia się zarządzanie zbiorami ciągów.

 bool addFirstOfRule_k(outSet, rule, startIndex) {
    //Tworzymy tymczasowy zbiór ciągów
    tempSet;
    tempSet.eps = true;
    for (int Yidx=startIndex; Yidx < rule.v.size(); Yidx++) {
        RuleElem Y = rule.v[Yidx];
        if (Y.kind==ekTerminal)
        {
        //dodajemy numer tokenu do każdego ciągu
            tempSet.append(Y.number);
        }
        else
        {
        //dodajemy wszystkie kombinacje ze zbioru Y
            tempSet.concat(Firstk[Y.number]);
        }
        //przerywamy pętlę jeśli zostały już tylko ciągi maksymalnej długości
        if (!tempSet.concatenable()) break;
    }
    //zbió© wynikowy := zbiór wynikowy OR nasz zbiór tymczasowy
    outSet.unionWith(tempSet);
    return true jeśli
}

void makeFirstSets_k(int k) {
    bool changed;
    Tworzymy listę pustych zbiorów odpowiedniego typu
    do {
        changed = false;
        for (int Xidx=rulesByNonterminal.size() - 1; Xidx >= 0; Xidx--) {
            RulesForNonterminal &rules = rulesByNonterminal[Xidx];
            for (int XruleIdx= rules.size() - 1; XruleIdx >= 0; XruleIdx--) {
                bool reschanged = addFirstOfRule_k(Firstk[Xidx], rules[XruleIdx]);
                if (reschanged)
                    changed = true;
            }
        }
    }
    while (changed);
}

void makeFollowSets_k(int k) {
    Followk.clear();
    Tworzymy listę pustych zbiorów odpowiedniego typu
    Followk[0].eps = true;
    bool changed;
    do {
        changed = false;
        for (int Aidx=0; Aidx < rulesByNonterminal.size(); Aidx++) {
            RulesForNonterminal &rules = rulesByNonterminal[Aidx];
            for (int ruleIdx=0; ruleIdx < rules.size(); ruleIdx++) {
                for (int Bidx=0; Bidx < rules[ruleIdx].v.size(); Bidx++) {
                    RuleElem elem = rules[ruleIdx].v[Bidx];
                    if (elem.kind != ekNonterminal) continue;
                    if (addFirstOfRule_k(Followk[elem.number], rules[ruleIdx], Bidx + 1))
                        changed = true;
                }
            }
        }
    }
    while (changed);
}

Użyte struktury

Dobrze sprawdza się struktura pośrednia między mapą bitową a drzewem. Niech k=3 a maksymalna ilość tokenów=100. Wtedy poziom pierwszy to 100 wskaźników albo indeksów (co pozwoli na przykład użyć 32 bity zamiast 64 na wskaźnik w 64-bitowym trybie i umożliwi rzadsze przydzielanie wielu małych fragmentów pamięci). Załóżmy że 97 jest zerowych a są niezerowe indeksy 5.7 i 11 pokazujące na poziom drugi, mamy dodatkowo 300 indeksów, następne pokazują na tablice bitowe. Ponieważ mamy ciągi różnych długości, dobrze jest w jednym zbiorze tokenów umieścić wiele poziomów takich drzewiastych tablic bitowych – umożliwi to na też szybkie pomijanie ciągów o pełnej długości, których nie modyfikujemy.

Zobacz też

generowanie parserów LR

Linki zewnętrzne

first_k-follow_k(Github) przykładowa implementacja
usna.edu kalkulator liczący zbiory

Navigation

Nawigacja

Portale tematyczne

Zbiory First i Follow

Spis treści

Definicja

Obliczanie dla k =1

First

Follow

Przykład

First

Follow

Obliczanie dla k >=1

Użyte struktury

Zobacz też

Linki zewnętrzne