Zbiory First i Follow
FirstG,k(α), FollowG,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:
- FirstG,k(α) – to prefiksy długości k słów wyprowadzalnych z α w gramatyce G,
- FollowG,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[edytuj | edytuj kod]
K-głowa napisu x, oznaczana przez k:x, to prefiks długości min (k, |x|) napisu x. Bardziej formalnie: niech wtedy:
Dla gramatyki G=(Σ,N,P,S):
- zbiór FirstG,k(α) jest zbiorem wszystkich k-głów napisów dających się wyprowadzić w G z α, czyli FirstG,k(α) = {w | istnieje x∈Σ* taki że α ⇒* x, a w=k:x};
- zbiór FollowG,k(α) zawiera wszystkie k-głowy które mogą wystąpić po α, czyli FollowG,k(α) = {w | istnieją μ, x takie że S ⇒* μαx, i w∈FirstG,k(x)}.
Jeśli nie prowadzi to do niejednoznaczności FirstG,k można skracać do Firstk, FollowG,k do Followk. Indeks k dla First i Follow można pominąć gdy ma wartość równą 1.
Obliczanie na podstawie definicji[edytuj | edytuj kod]
First[edytuj | edytuj kod]
- Jeśli X jest symbolem terminalnym, wtedy FIRST(X) = {X}
- Jeśli jest produkcja X->eps, wtedy dodajemy epsilon do FIRST(X)
- Jeśli jest produkcja X-> Y1, Y2,..Yk, wtedy
- do FIRST(X) dodajemy wszystkie z FIRST(Y1) poza epsilonem
- jeśli FIRST(Y1) zawiera epsilon, dodajemy do FIRST(X) wszystkie z FIRST(Y2) poza epsilonem
- itd
- jeśli wszystkie zawierają epsilon, wtedy dodajemy epsilon do FIRST(X)
Follow[edytuj | edytuj kod]
- Jeśli S jest symbolem startowym dodajemy znak końca strumienia $ do FOLLOW(S)
- Jeśli jest produkcja A -> αΒβ wtedy dodajemy wszystko z FIRST(β) poza epsilonem do FOLLOW(Β)
- Jeśli jest produkcja A -> αΒ wtedy dodajemy wszystko z FOLLOW(A) do FOLLOW(B)
- Jeśli jest produkcja A -> αΒβ oraz FIRST(β) zawiera epislon, również wszystko z FOLLOW(A) do FOLLOW(B)
Obliczanie dla k =1[edytuj | edytuj kod]
First[edytuj | edytuj kod]
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[edytuj | edytuj kod]
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) { //tworzymy zbiór tymczasowy tmpSet = new TokenSet(); add_rule_first(tmpSet,reguła,indeks za B); dodajemy do zbioru związanego z symbolem B wszystko z tmpSet poza epislonem jeśli coś się zmieniło changed = true; jeśli w tmpSet był epsilon, dodajemy do zbioru związanego z symbolem B wszystko ze zbioru związanego z A } } } } while (changed); } Funkcja add_rule_first przydaje się także przy sprawdzaniu warunku LL(1)
Przykład[edytuj | edytuj kod]
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[edytuj | edytuj kod]
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[edytuj | edytuj kod]
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[edytuj | edytuj kod]
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 coś zostało dodane nowego do zbioru } 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[edytuj | edytuj kod]
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ż[edytuj | edytuj kod]
Linki zewnętrzne[edytuj | edytuj kod]
- first_k-follow_k(Github) przykładowa implementacja
- www.cs.princeton.edu kalkulator liczący zbiory wraz z generowaniem tablic parsera LL