Při syntaktické analýze shora-dolů bezkontextové gramatiky občas (skoro vždy) nemáme to štěstí a pro danou levou stranu pravidla existuje více pravých stran, čili jsme v situaci, kterou nejsme schopni deterministicky rozhodnout.

Tento nedeterminismus jsme ale často schopni odstranit pomocí nápovědy, kterou je pro nás následující, dosud nezpracovaný, terminál. Pomocí něj jsme schopni ve většině případů rozhodnout, které pravidlo se má použít, tak aby byl vstup korektně zpracován - aby terminál na vrcholu zásobníku vždy odpovídal zpracovávanému znaku vstupu.

Funkce First

Pokud je na vrcholu zásobníku A dalším terminálem na vstupu je x, tak je zřejmé, že musíme provést expanzi A => B podle pravidla 1, protože jen to zajistí, že se po provedení další expanze dle pravidla 2 dostane na vrchol zásobíku právě znak x a vstup bude moci být korektně zpracován. Funkci, která zjišťuje, co vznikne přepsáním jednotlivých neterminálů na levé straně všech pravidel, se říká First.

Funkce Follow

Při překladu se může stát také méně příznivá situace, kdy je na pravé straně prázdný symbol (tato operace pouze vymaže neterminál z vrcholu zásobníku). V tento okamžik je nutno rozhodnutí, kterou větví má překlad postupovat, podřídit otázce: „Který terminál nahradí na zásobíku právě mazaný neterminál?“. Odpovědí jsou všechny terminály na pravých stranách pravidel, které jsou přímo za mazaným neterminálem (po rozvinutí všech neterminálů v daných pravidlech), této funkci říkáme Follow a má ji smysl počítat pouze tehdy, nastane-li již zmíněná situace s prázdným symbolem.

Příklad na výpočet First a Follow

Výpočet first

Nejprve udělejme výpočet funkce First. First(S) = {a, c, d}, protože pokud v prvním pravidle přepíšeme A na ε, a pak B přepíšeme podle 4. nebo 5. pravidla, tak máme na prvním místě „c“ a „d“. Pokud A přepíšeme podle 2. pravidla, tak je na prvním místě „a“. FIRST(A) = {a, ε}, což vyplývá z pravidel 2 a 3. First(B) = {c, d} dle pravidel 4 a 5.

Častým dotazem je, co se stane s First(X) pravidla X => Yzzz, pokud Y přepíšeme na ε. Do First (X) nám v tomto případě spadne i „z“.

Formálně zapsáno používáme pro bezkontextovou gramatiku , , , následující pravidla:

1. Pokud , pak .
2. Pokud , pak .
3. Pokud , pak .
4. Pokud , pak .

Výpočet Follow

Funkci Follow nám zbývá spočítat pouze pro A, protože ε patří do First(A). Follow(A) = {b, c, d}, protože pokud se podíváme na pravé strany, tak z pravé strany prvního pravidla vidíme, že za A následuje B, zajímají nás tedy prvky First(B), což jsou „c“ a „d“. Z druhého pravidla vidíme, že za A následuje „b“.

Pokud by stalo, že bychom narazili na pravidlo X => xyzYW a W můžeme přepset na ε, tak do Follow(Y) patří všechny prvky z Follow(X), protože se při přepisování bezprostředně za Y zařadí prvky zbytek prvků z pravidla Z => Xzzz. Čili do Follow(Y) patří „z“.

Také vždy platí, že do Follow startovního symbolu patří ε, protože pokud je gramatika správně sestavena, tak by měl být celý řetězec přijmut rozvinutím startovního neterminálu.

Formálně lze Follow vypočítat jako:

1. Pro startovní symbol přiřaďme .
2. Pro všechny výskyty neterminálních symbolů na pravých stranách:

   • Pokud je pravidlo ve tvaru , pak
   • Pokud je pravidlo ve tvaru a platí-li ,
     pak
3. Opakujme krok 2, dokud se změnila aspoň jedna z množin Follow(X).

Sestavení tabulky přechodů

Nyní již zbývá jen sestavit tabulku přechodů. Do řádků budeme psát neterminály, do sloupců terminály a do polí čísla pravidel, podle kterých dojde k přechodu. ε ve First ignorujeme, to nám pouze značí, že máme vyplnit i Follow. Prázdná místa značí chybu překladu. Pokud existuje buňka, kde je více čísel (přechodů), pak gramatika není LL1 a je ji třeba transformovat.

Literatura

• MÜLLER, Karel. Programovací jazyky. [s.l.] : Česká technika - nakladatelství ČVUT, 2005. 219 s.