Množina First a Follow

First_G,k(α), Follow_G,k(α) jsou množiny řetězců (dále budeme používat termín slov) nad pevnou abecedou sloužící k analýze formálních gramatik, např. při konstrukci syntaktických analyzátorů (parserů). Jednoduše řečeno:

First_G,k(α) jsou prefixy délky k slov generovaných z řetězce α v gramatice G,
Follow_G,k(α) jsou prefixy délky k fragmentů slov generovaných z gramatiky G, které mohou bezprostředně následovat za fragmentem vygenerovaným z řetězce α,

kde α je řetězec terminálních a neterminálních symbolů z gramatiky; v praxi, především při výpočtu množin Follow, je zpravidla jediný neterminální symbol.

Tyto množiny umožňují určovat, zda má gramatika určité vlastnosti, které mohou usnadňovat syntaktickou analýzou (anglicky parsing). Při konstrukci analyzátoru se pomocí nich zjišťuje, jaké jsou možné konfigurace analyzátoru, a jaké akce mají být provedeny v dané konfiguraci.

Definice editovat

K-hlava řetězce x, značíme k:x, je prefix délky min (k, |x|) řetězce x. Formálněji: nechť $x=a_{1}a_{2}\ldots a_{n}$ , pak:

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

Pro gramatiku G=(Σ,N,P,S) definujeme:

množinu First_G,k(α) jako množinu všech k-hlav řetězců, které lze získat v gramatice G z řetězce α, tj. First_G,k(α) = {v | existuje x∈Σ^* takový že α ⇒^* x, a v=k:x};
množinu Follow_G,k(α) jako množinu, která obsahuje všechny k-hlav, které se mohou objevit po α, tj. Follow_G,k(α) = {v | existují μ, x takové že S ⇒^* μαx, a v∈First_G,k(x)}.

Pokud nemůže dojít k nedorozumění, zkracujeme First_G,k na First_k a Follow_G,k na Follow_k. Pro k=1 se vynechává index k u First a Follow. .

Výpočet pro k=1 editovat

First editovat

Množinu First můžeme určovat pro terminální symboly, neterminální symboly nebo pro řetězce symbolů. Pokud x je terminálním symbolem, pak First(x) = {x}. Pro neterminální symbol X používáme následující algoritmus:

všechny množiny pro jednotlivé neterminální symboly inicializujeme jako prázdné
pro každé pravidlo tvaru X → aα přidáme do First(X) symbol a
pro každé pravidlo X → ε přidáme do First(X) prázdný řetězec ε
pro každé pravidlo tvaru X → Y₁ Y₂ ... Y_k a pro "a" takové, že všechny Y₁ ... Y_a-1 jsou neterminály nebo First(Y_j) pro každé j=1...a-1 obsahují ε, doplnit každý symbol různý od ε z First(Y_j) j=1...a do First(X); pokud ε je obsaženo ve všech First(Y_j) j=1...k, pak je třeba přidat do First(X) také ε
v každém průchodu provedeme body 2, 3, 4 výše uvedeného algoritmu na další pravidla; opakujeme tak dlouho, dokud v poslední iterací nepřidáme do žádné z množin žádný symbolu. Výhodnější je obrácené pořadí prohledávání pravidel, protože pro symbol, pro který počítáme First, budou symboly, které používáme, obvykle definované později.

Ukázková implementace může vypadat takto:

set First[počet_neterminálů]; //tabulka množin First pro jednotlivé neterminální symboly
inicializujeme všechny množiny First jako prázdné;//bod 1
void make_First_sets(void)
{
  bool changed; //v aktuálním průchodu smyčkou byly přidány nové symboly
  do
  {
    changed = false;
    for (X přes všechny neterminální symboly (od posledního))
    {
        for (přes všechna pravidla, která mají tento neterminální symbol na levé straně (od posledního))
        {
          bool je_epsilon=true; //symbol pravé strany pravidel může ho změnit na false
          for (přes symboly na pravé straně pravidla)
          // když je pravidlo tvaru X->epsilon, tuto smyčku neprovádíme
          {
            if (symbol je terminál)
            { // bod 2 pokud neterminál je na počátku pravidla
              // a pokud Y1Y2...Yk mají všechny Yi mají epsilon
               je_epsilon=false;
               přidej symbol do FirsSets[X];
               if (něco jsme přidali) changed=true;
               break;// protože nebylo epsilon
            }
            else
            { //bod 4
              //symbol je neterminální, nazveme ho Y;
              do First[X] přidáme symboly z First[Y]; kromě epsilonu
              if (něco jsme přidali) changed=true;
              if First[Y] neobsahuje epsilon
              {
                je_epsilon=false;
                break;//protože nebyl epsilon
              }
            }
          }
          // konec smyčky po symbolech z pravé strany pravidla
          // nebo bylo pravidlo X->epsilon (bod 3)
          if (je_epsilon) // všechny byly neterminály a obsahovaly epsilon
          { // pokud se provedla celá smyčka, znamená to, že všechny Yi obsahovaly epsilon
            přidej epsilon do FirsSets[X]
            if (něco jsme přidali) changed=true;
          }
        }
    }
  }
  while (changed);
}

Pro řetězce terminálních a neterminálních symbolů pracujeme jako v bodě 4 výše uvedeného algoritmu – pokud máme spočítat First(α) a α je řetězcem tvaru Y₁ Y₂ ... Y_k, pak podobným způsobem jako jsme vypočítali množinu symbolů přidaných do First(X) dostaneme množina First(α).

Follow editovat

V praxi (například při konstrukci SLR analyzátorů) počítáme množinu Follow pro všechny neterminální symboly. Pak lze použít následující algoritmus:

všechny množiny pro neterminální symboly inicializujeme jako prázdné s výjimkou množiny pro počáteční symbol Z, která bude obsahovat znak konce proudu $
pro každé pravidlo A → αBβ a všechny symboly náležející do First(β) různé od ε obsažené ve Follow(B) (v množinách Follow vystupuje speciální symbol $, ale není tam ε, který je v množinách First)
pro každé pravidlo A → αB nebo A → αBβ, pro které First(β) obsahuje ε, přidáme do Follow(B) všechny symboly z Follow(A)
při každém průchodu aplikujeme body 2, 3 výše uvedeného algoritmu na další pravidla a v každém pravidle na každý neterminální symbol na pravé straně pravidla; opakujeme tak dlouho, až v poslední iterací nepřidáme žádný symbol do žádné množiny.

set Follow[počet_neterminálů]; //tabulka množin Follow pro každý neterminálního symbolu
// v konkrétní implementaci může být set třídou obsahující množinu terminálních symbolů plus
//znak konce proudu, na rozdíl od typu množiny pro First, kde místo toho tohoto měl způsobovat epsilon
inicializujeme všechny množiny Follow jako prázdné
s výjimkou množiny Follow[počáteční] inicializovaný na $//bod 1
void make_Follow_sets(First)
{
  bool changed; // v aktuálním průchodu smyčkou byly přidány nové symboly
  do
  {
    changed = false;
    for (A přes všechny neterminální symboly)
    {
        for (přes všechna pravidla, která mají na levé straně tento neterminální symbol)
        {
           for (B přes neterminální symboly na pravé straně pravidel)
           {
             bool je_epsilon=true;  // element řetězce beta může ho změnit na false;
             for (b po prvcích beta) // tj. symbolech nacházejících se za B až do konce pravidel
             {
               if (b je terminál)
               { //součást bodu 2
                 do Follow[B] přidat b;
                 if (něco jsme přidali) changed=true; //když předtím nebyl tento symbol v množině
                 je_epsilon=false;
                 break;//smyčkou po beta
               }
               else //bod 2
               { //b je neterminálním
                 do Follow[B] přidáme symboly kromě epsilenu z First[b];
                 if (něco jsme přidali) changed=true;
                 if (First[b] ne obsahuje epsilona)
                 {
                    je_epsilon=false;
                    break;
                 }
               }
             }
             if (je_epsilon)
             {  //bod 3
               do Follow[B] přidáme symboly z Follow[A]; //spolu se symbolem $
               if (něco jsme přidali) changed=true;
             }
           }
        }
    }
  }
  while (changed);
}

Příklad editovat

Máme gramatiku

(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 → a

Pokud pro tuto gramatiku chceme vytvořit analyzátor, doplníme ji novým počátečním neterminálním symbolem Z a pravidlem:

(0) Z → E

First editovat

Pomocí algoritmu pro výpočet množin First vytváříme pro tuto gramatiku postupně množiny First pro jednotlivé neterminální symboly v postupných iteracích:

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

V dalších pravidlech (od 8 do 0) přidáváme symboly do množin First pro jednotlivé neterminální symboly:

8: a do F

7: ( do F

6: ε do T'

5: * do T'

4: ( a do T

3: ε do E'

2: + do E'

1: ( a do E

0: ( a do Z

Při druhém průchodu by mohla něco případně doplnit pravidla 4, 1 a 0 (jejichž pravá strana začíná neterminálem). Ale nic již přidané nebude, protože ostatní množiny First(F) se nezměnily.

Follow editovat

Postupná konstrukce množin Follow pro neterminální symboly v iteracích:

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

Follow(Z) obsahuje symbol konce proudu $. V dalších pravidlech a pro další neterminální symboly objevující se na pravé straně pravidel přidáme do množin Follow symboly pro jednotlivé neterminální symboly:

0:Z → E

$ do Follow(E) z Follow(Z)

1:E → T E'

pro T z pkt 2 všechny z First(E') kromě ε, tj. + do Follow(T); z pkt 3 protože ε je obsaženo v Follow(E), proto do Follow(T) z Follow(E) neboli $
pro E' z pkt 3 do Follow(E') z Follow(E) neboli $

2:E' → + T E'

pro T z pkt 2 všechny bez ε z First(E') již byly;z pkt 3 z Follow(E') do Follow(T) symbol $ který již byl
z Follow(E') do Follow(E') – nic se ne změní

3:E' → ε

přeskakujeme

4:T → F T'

pro F z pkt 2 doplnit bez ε z First(T') neboli * do Follow(F); z bodu 3 z Follow(T) do Follow(F) neboli {$,+}
pro T' z pkt 3 z Follow(T) do Follow(T') neboli {$,+}

5:T' → * F T'

pro F z pkt 2 přidat z First(T') kromě ε neboli * do Follow(F) – již přidané; z pkt 3 z Follow(T') do Follow(F) ale symboly {$,+} tam již jsou
pro T' z pkt 3 z Follow(T') do Follow(T') – bez změn

6:T' → ε

přeskakujeme

7:F → ( E )

pro E z pkt 2 přidáme First(')')=')' do Follow(E); bod 3 nelze použít

8:F → a

na pravé straně pravidla není neterminální symbol

Druhý průchod:

1:E → T E'

pro T z Follow(E) do Follow(T) přidáme ')'
pro E' z Follow(E) do Follow(E') přidáme ')'

4:T → F T'

pro F z Follow(T) do Follow(F) přidáme ')'
pro T'z Follow(T) do Follow(T') přidáme ')'

Odkazy editovat

Reference editovat

V tomto článku byl použit překlad textu z článku Zbiory First i Follow na polské Wikipedii.

Související články editovat

Konstrukce LR analyzátorů