Algoritmus 6:

Vytvoření rozkladové tabulky pro LL(1) gramatiku.

Vstup:     LL(1) gramatika G=(N,T,P,S).
Výstup:     Rozkladová tabulka R pro gramatiku G.
Metoda:  

Rozkladová tabulka R je definována na kartézském součinu .
  1. Je-li pravidlo v $P$, pak pro všechna
    .
  2. Je-li pravidlo v $P$ , pak , pro všechna
    .
  3. chyba ve všech ostatních případech.
Z algoritmu je zřejmé, že množiny FIRST pravých stran pravidel se stejným neterminálem na straně levé musí být vzájemně disjunktní. Navíc musí platit, že pokud některá z pravých stran přijímá prázdný řetězec, musejí být vzájemně disjunktní i s množinou FOLLOW. Formálně vyjádřeno musí platit, že pokud jsou libovolná dvě různá pravidla v P, pak:

  1. To platí ovšem i pro $\varepsilon$.
  2. Pokud lze z  derivovat prázdný řetězec, pak musí navíc platit:
V případě, že by nebyly množiny disjunktní, bylo by přípustné použití více než jednoho pravidla a nemohlo by tedy být učiněno jednoznačné rozhodnutí. Tím se vyjasňuje motivace pro zavedení módů empty/0, first/0 a použití množiny FOLLOW.

Obraťme proto nyní svou pozornost ke konstruktorům parserů a rozeberme situaci zde. Pravidla obsahující $\varepsilon$-přechod zde odpovídají alternativním kompozicím, v nichž je některá z alternativ schopna přijímat prázdný řetězec.

Zjišťujeme, že v kombinátorech parserů narazíme při vytváření množiny FOLLOW na zásadní problém:

Na rozdíl od gramatik u parserů nemáme k dispozici explicitní reprezentaci gramatiky, kterou parser realizuje. Nelze tedy určit, kde všude se neterminál, jenž je zde reprezentován alternativní kompozicí, nachází.
Situace je komplikována tím, že se alternativní kompozice může predikátem navíc libovolně prolínat. Bohužel nám nepomůže ani abstraktní interpretace parseru, při které by se určovalo, ze kterých míst je predikát volán. Při takové analýze parseru by totiž musela být každá alternativní kompozice nějakým způsobem jednoznačně identifikována. To by bylo možné jedině v případě, že by náš implementační jazyk obsahoval speciální formu reflection.C.4

Důvodem, proč bychom reflection potřebovali je, že se syntakticky stejné alternativní kompozice, které jsou však z hlediska sémantického odlišné, mohou nacházet nejen v různých částech parseru, ale dokonce i v rámci jediné klauzule.

V případě, že bychom nebyli schopni od sebe různé alternativní kompozice odlišit, mohlo by dojít k chybnému rozšíření množiny FOLLOW o symboly, které do ní nepatří a následně buď k detekci neexistujících kolizí (konflikt množiny FIRST a jedné z alternativ nesprávně přidaného symbolu z FOLLOW) nebo k neoprávněnému použití $\varepsilon$-přechodu (konflikt s ostatními alternativami nebyl při ověřování vzájemné disjunktnosti množin detekován, použije se tedy $\varepsilon$-přechod pomocí nesprávně přidaného symbolu, což následně způsobí chybu, jejíž příčinu nelze jednoznačně určit).

Situace však není tak beznadějná, jak by se na první pohled mohlo zdát. Provedeme-li rozbor derivačního stromu zjistíme, že ve skutečnosti ke korektnímu rozkladu nepotřebujeme kompletní množinu FOLLOW, ale bude nám stačit pouze její část, jež je v dané chvíli aktuální. Tuto množinu budeme nazývat dynamická FOLLOW -- DFOLLOW.

Hlavní myšlenka, která za jejím výpočtem stojí, je následující: v dané chvíli postačuje k rozkladu jen určitá část množiny FOLLOW, jež obsahuje pouze ty symboly, které se mohou v této části výpočtu skutečně vyskytnout. Tato poněkud vágní formulace bude upřesněna v části [*]. Charakter množiny DFOLLOW je tedy na rozdíl od FOLLOW lokální. Její výpočet tedy vzhledem k její lokální povaze, nemůže být prováděn pomocí abstraktní interpretace parseru, ale až v průběhu samotného rozkladu přímo v módu provádějícím deterministickou syntaktickou analýzu.

dvorka 2013-12-31