Množina First a Follow

Technology

12 hours ago

Author

FirstG,k(α), FollowG,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: * FirstG,k(α) jsou prefixy délky k slov generovaných z řetězce α v gramatice G, * FollowG,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 . 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_1a_2\ldots a_n, pak:

k:x = \begin{cases}x, & \mbox{pro}\quad |x|\le k \\ a_1\ldots a_k,& \mbox{pro}\quad |x|>k \end{cases}.

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

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

Pokud nemůže dojít k nedorozumění, zkracujeme FirstG,k na Firstk a FollowG,k na Followk. 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}. +more 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 → Y1 Y2 . Yk a pro "a" takové, že všechny Y1 . Ya-1 jsou neterminály nebo First(Yj) pro každé j=1. a-1 obsahují ε, doplnit každý symbol různý od ε z First(Yj) j=1. a do First(X); pokud ε je obsaženo ve všech First(Yj) 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 Y1 Y2 ... Yk, 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 ')'