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 (Šablona:Vjazyce2). 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

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} \dots a_{n}$ , pak:

$k : x = {\begin{matrix} x, & pro | x | \leq k \\ a_{1} \dots a_{k}, & pro | x | > k \end{matrix}$ .

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

First

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

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

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

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

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

Reference

Šablona:Překlad

Související články

Konstrukce LR analyzátorů

Množina First a Follow

Obsah

Definice

Výpočet pro k=1

First

Follow

Příklad

First

Follow

Odkazy

Reference

Související články

Navigační menu

Množina First a Follow

Definice

Výpočet pro k=1

First

Follow

Příklad

First

Follow

Odkazy

Reference

Související články

Navigační menu

Hledat