22a - Příklad na vytváření LL tabulky

Máme zadefinovánu gramatiku s epsilon pravidly:

1. S → XCd
2. X → AB
3. A → aAB
4. A → ε
5. B → bB
6. B → ε
7. C → cCd
8. C → ε

Nejprve spočítáme množiny Empty.

1. Pro jakýkoli terminál je množina Empty ∅, jelikož je ničím v nula krocích nahradit.
2. Dále řešíme, zda jdou v nula krocích odmazat neterminály
   1. A, B, C jdou odmazat - pravidla 4, 6, 8
   2. dále nás zajímá pravidlo 2, jelikož, X jde nahradit neterminály A a B a ty jdou nahradit ε ⇒ X jde odmazat
   3. S nejde smazat, jelikož tam vždy zůstane terminál d

Pak vyřešíme množinu First

1. Pro jakýkoli terminál je množina First množina obsahující daný terminál ⇒ v nula krocích nemůžeme z terminálu nagenerovat nic jiného než samotný terminál
2. Dále řešíme neterminály
   1. v počátku nastavíme First každého neterminálu na prázdnou množinu
   2. prázdnou množinu plníme prvními neterminály, které můžou nastat po rozgenerování (! zde je třeba dát pozor, pokud je první rozgenerovaný prvek další neterminál - je třeba řešit First tohoto neterminálu a zároveň musíme kouknout na množinu Empty, jestli náhodou nejde odmazat - v takovém případě, bychom koukali ještě na další prvek za tímto neterminálem)
   3. je dobré procházet gramatiku odspodu
      1. First(C) je {c}, pravidlo 7 … terminál c nejde odmazat, tzn. takto nechávám
      2. First(B) je {b}, pravdilo 5
      3. First(A) je {a}, pravidlo 3
      4. First(X) obsahuje First(A) - tzn {a}, pravidlo 2 a jelikož A jde odmazat (Empty(A) = {ε}), First(X) obsahuje zároveň First(B) - tzn {b} - tedy výsledek je sjednocení {a,b}
      5. First(S) - je intuitivní, obsahuje First(X), jelikož X jde smazat, tak přidáme First(C) a jelikož toto také můžeme odmazat a dojdeme k terminálu d, který přidáme do First(S) a končíme

Nakonec vyřešíme Follow

1. Nejprve to celé zainicializujeme tím, že dáme do Follow(S) {$} a ostatní Follow budou prázdné množiny
2. Dále se budeme koukat na pravé strany pravidel a řešit, co může následovat po daném terminálu
   • začněme pěkně z vrchu od pravidla 1, kde pravá strana je XCd
     1. po neterminálu C může následovat pouze d - d, přidáme do Follow(C)
     2. po neterminálu X následuje neterminál C - First(C) přidáme do Follow(X) a jelikož C můžeme odmazat, přidáme tam ještě Follow(C) - tzn. do Follow(X) přidáme First(C) ∪ Follow(C) = {c,d}
   • dále se posuneme na pravidlo 2 a jeho pravou stranu AB
     1. B končí rozgenerovávání neterminálu X - to znamená, že po B následuje to samé, co po X - tzn. do Follow(B) přidáme Follow(X)
     2. dále vidíme, že po A následuje B tzn. do Follow(A) přidáme First(B) a jelikož B jde odmazat, přidáme zároveň Follow(B)
   • a takto intuitivně pokračujeme až k poslednímu pravidlu (pravidla, kde na pravé straně máme terminály a epsilony nás nezajímají)

Když už máme spočítány tři množiny First, Follow a Empty, budeme chtít sestavit samotnou tabulku. Nejprve si budeme muset sestavit množinu Predict ⇒ nepočítá se pro neterminály, ale pro celá pravidla

1. V každém případě do Predict(levá strana) dáme First(pravá strana)
2. Pokud pravá strana jde odmazat, přidáme do Predict(levá strana) ještě Follow(levá strana)

1. S → XCd … {a,b,c,d} //First(XCd)
2. X → AB … {a,b,c,d} //First(AB) ∪ Follow(X)
3. A → aAB … {a} //First(aAb)
4. A → ε … {b,c,d} //First(ε) ∪ Follow(A)
5. B → bB … {b} //First(bB)
6. B → ε … {c,d} //First(ε) ∪ Follow(B)
7. C → cCd … {c} //First(C)
8. C → ε … {d} //First(ε) ∪ Follow(C)

Samotné sestavení tabulky

V každém políčko musí být maximálně jedno pravidlo, jinak tabulka pravidel není deterministická a těžko ji naimplementujeme. Číslo nám totiž říká, které pravidlo se uplatní. Pokud ovšem načteme terminál a nejde na něj uplatnit žádné pravidlo, znamená to, že program je syntakticky špatně.