Popis řešení cvičení 4.

V tomto dokumentu je popsána pouze implementace výpočtu množin first a follow. Což je také součástí vzorového řešení. Toto řešení neodpovídá "přesně" zadání cvičení 4. Při popisu řešení budu využívat tuto gramatiku:

Číslo pravidla	Levá strana	Pravá strana
1)	A ->	b C
2)	A ->	B d
3)	B ->	C C
4)	B ->	b A
5)	C ->	c C
6)	C ->	epsilon

First

Množina first se určuje ke každé pravé straně každého pravidla. Je to vlastně množina terminálů, kterýma může tato pravá strana začinat. Přesnou definici najdete v přednáškách. Specialní význam má symbol epsilon (prazdné slovo). Obsahuje-li first pravé strany epsilon, znamená to, že celou tuto pravou stranu lze přepsat na prázdné slovo. Tedy naopak: first bude obsahovat epsilon jen tehdy, pokud celou tuto pravou stranu pravidla lze přepsat na epsilon.
Jednoduchý rekurzivní algoritmus pro výpočet množiny first by mohl vypdat takto:

Obsahuje-li pravá strana epsilon (pravá strana je vlastně prázdná), first bude obsahovat pouze epsilon a algoritmus končí.
Aktuální symbol je první symbol pravé strany.
Je-li aktuální symbol terminál přidej tento terminál do množiny first a skonči.
Je-li aktuální symbol neterminál proveď:
1. Rekurzivně vypočti množiny first všech pravých stran tohoto neterminálu.
2. Výsledky spoj do jedné množiny.
3. Pokud tato množina obsahuje epsilon, tak jej odeber.
4. Výsledek přidej do množiny first.
Lze-li aktuální symbol (neterminál) přepsat na prázdné slovo, zvol jako aktuální symbol další symbol pravé strany pravidla a pokračuj krokem 3. Není-li na pravé straně již žádný symbol skonči.

Tento algoritmus bude fungovat, ale pro některé gramatiky může při rekurzivním volání vzniknou cyklus a tedy nekonečná smyčka. Implementovaný algoritmus je trochu jiný. Nejprve si "bokem" připravíme sjednocení množin first všech pravidel jednoho neterminálu (výsledek z kroku 4 našeho algoritmu). Pak představený algoritmus nepotřebuje rekurzi a po jednom průchodu gramatikou skončí s požadovaný výsledkem.
Toto sjednocení množin first vytvoříme takto:
Nejprve si vytvoříme tabulku. Tato tabulka bude obsahovat tolik řádků kolik je neterminálů. Sloupců tolik, kolik je symbolů.

	A	B	C	b	c	d
A
B
C

Tuto tabulku naplníme:Procházíme pravidly gramatiky. Každé pravidlo z leva procházíme dokud nenarazíme na symbol, který nelze přepsat na prázdné slovo (buď terminál, nebo neterminál nepřepsatelný na epsilon). Pro tyto symboly umístíme značku do tabulky. Řádek je dám neterminálem na levé straně a sloupec procházeným symbolem na pravé. Pro naší gramatiku by vyplňování tabulky probíhalo takto:
Procházíme první pravidlo A->bC. První symbol je terminál, umístíme značku na řádek A do sloupce b a pokračujeme dalším pravidlem.

	A	B	C	b	c	d
A				*
B
C

Druhé pravidlo je A->Bd. Nejprve umístíme značku na řádek A do sloupce B. Protože lze B přepsat na prázdné slovo, pokračujeme dalším symbolem. To je terminál d. umístíme příslušnou značku.

	B	b	d
A	*	*	*
B
C

Třetí pravidlo je B->CC. Umístíme značku na řádek B a sloupec C. C lze přepsat na prázdné slovo. Pokračujeme dalším symbolem, což je zase C. V tabulce již příslušná značka je. Protože C se dá přepsat na prázdné slovo, pokračujeme dalším symbolem. Došli jsem na kone pravé strany. Víme, že tato pravá strana se skládá ze symbolů, které lze všechny přepsat na prázdné slovo. Celou tuto pravou stranu lze tedy přepsat na prázdné slovo.

	B	C	b	d
A	*		*	*
B		*
C

Celá vyplněná tabulka bude vypadat takto:

	B	C	b	c	d
A	*		*		*
B		*	*
C		*		*

Tabulka se vlastně skládá ze dvou částí. První, což je čtvercová část indexovaná neterminály a zbytku. Procházíme první částí. Je-li na procházeném řádku značka v nějakém sloupci, příčteme k tomuto řádku, celý řádek označený jako tento sloupec. V našem konkrétním případě je první značka v řádku A u sloupce B. Přičteme tedy řádek B k řádku A.

	B	C	b	c	d
A	*	*	*		*
B		*	*
C		*		*

Takto procházíme tabulku a přičítáme řádky, dokud dochází v tabulce ke změnám. Projdeme li celou první částí tabulky a tabulka se nezmění, algoritmus končí. Výsledek je tedy tabulka:

	B	C	b	c	d
A	*	*	*	*	*
B		*	*	*
C		*		*

Získali jsme tabulku, kde jsou požadované množiny. Tedy sjednocení množin first všech pravých stran daného neterminálu. Pro A to je (b,c,d), pro B (b,c) a pro C (c)
Jsme tedy schopni jednoduše zjistit first kteréhokoliv pravidla.
Například A->Bd:

První symbol je B do množiny first přidáme b,c.
Protože lze B přepsat na prázdné slovo, pokračujeme dalším symbolem.
Další symbol je terminál d, přidáme jej do množiny first a výpočet končí.

Výsledná množina first je tedy (b,c,d).

Follow

Množina follow se zjišťuje ke každému neterminálu. Obsahuje terminály, které mohou nacházet bezprostředně za danám neterminálem (viz přednášky). Speciální význam má symbol espilon, který symbolizuje konec vstupu. Množina follow daného neterminálu tento symbol obsahuje tehdy a jen tehdy, pokud za tímto neterminálem nemusí být žádný další symbol. Epsiolon je tedy automaticky za startovním neterminálem.
Jednoduchý algoritnus, který vypočte množinu follov neterminálu by mohl vypadat takto:

Follow startovního neterminálu obsahuje epsilon
Projdi všechny pravé strany všech pravidel gramatiky.
Pro každý výskyt neterminálu, jehož follow zjišťujeme proveď:
1. Pravou stranu za daným neterminálem si označíme alfa (hledáme li follow neterminálu A, a máme pravou stranu BcADBa, bude alfa=DBa
2. Zjistíme first alfa (viz předchozí část) a tuto množinu přidáme do hledané množiny follow (použijeme first bez sysmbolu epsilon)
3. Lze-li alfa přepsat na prázdné slovo, rekurzívně zjistíme follow neterminálu na levé straně a tento follow přidáme do naší množiny

Při implementaci se opět vyhneme problémum s rekurzí pomocí uzávěru připravené tabulky. Tvořená tabulka bude stejné jako v případě množin first. Pro follow bude ale mít o jede sloupec víc. Tento sloupec bude pro symbol epsilon. Pro náš příklad bude tato tabulka vypadat takto:

	A	B	C	b	c	d	epsilon
A							*
B
C

Nejprve opět naplníme tabulku. Procházíme pravidly gramatiky. Pro každý neterminál aplikujeme postup popsaný v bodu 3 představeného algoritmu. Jen nezjišťujeme rekurzivně follow neterminálu na levé straně, ale umístíme značku do sloupce s tímto označením.
Pro první pravidlo A->bC. obsahuje jediný neterminál C. Za tímto neterminálem už není žádný symbol. Řetězec alfa je tedy prázdný (lze jej přepsat na prázdné slovo). Přidáme tedy značku do řádku C na pozici A.

	C	epsilon
A		*
B
C	*

Druhé pravidlo je A->Bd. obsahuje jediný neterminál B. First řetezce alfa=(d) je (d). Nelze je přepsat na prázdné slovo, proto umístíme jen jedinou značku a to do řádku B a sloupce d.

	A	d	epsilon
A			*
B		*
C	*

Celá vyplněná tabulka bude:

	A	B	C	c	d	epsilon
A		*				*
B					*
C	*	*	*	*

Opět procházíme první části tabulky a přičítáme řádky, dokud dochází ke změnám (stejně jako při výpočtu množin first). Výsledek bude:

	A	B	C	c	d	epsilon
A		*			*	*
B					*
C	*	*	*	*	*	*

Tato tabulka již přímo obsahuje follow jednotlivých neterminálů. Pro náš příklad to je: follow(A)={d, espilon}, folllo(B)={d}, follow(C)={c,d,epsilon}