Algoritmus 7:

Výpočet množiny DFOLLOW při průchodu kombinátorem sekvenční kompozice.

Metoda:

1. Množina je před začátkem výpočtu inicializována jako prázdná.
2. Při prvním průchodu výpočtu kombinátorem sekvenční kompozice ověř, zda parser stojící v sekvenční kompozici vpravo přijímá prázdný řetězec:
   • pokud ne, aplikuj parser stojící v sekvenční kompozici vlevo s množinou:
             
   • jestliže ano, použij předka a aplikuj parser s množinou:
             
3. Při druhém průchodu výpočtu kombinátorem sekvenční kompozice, při němž je aplikován parser použij množinu:
           

Jak lze snadno nahlédnout, při samotném rozkladu se vyjde od prázdné DFOLLOW, která se průběžně aktualizuje. Pokud za sebou bezprostředně následuje několik parserů přijímajících prázdný řetězec, průběžně se rozšiřuje. Je zřejmé, že nepotřebujeme znát kompletní množinu FOLLOW tak, jak je používána v teorii jazyků u gramatik, protože zcela postačující je DFOLLOW, kterou lze získat z pravé části derivačního stromu (obrázek ) abstraktní interpretací aktuální části parseru.

Obrázek: Strom výpočtu

Pří výpočtu množiny DFOLLOW je také, vzhledem k jejímu vztahu k množinám FIRST, důležitá volba asociativity kombinátoru sekvenční kompozice. V knihovně konstruktorů parserů je definován tento kombinátor jako operátor s pravou asociativitou (viz příloha ). Tuto volbu jsme učinili ze zřejmého důvodu -- většina rekurzivních datových struktur v jazyce Prolog, jako například pole, je definována s pravou asociativitou, čehož nezřídka využívají knihovní konstruktory.

Nevýhodou zvolené pravé asociativity je, že pokud několik bezprostředně po sobě následujících parserů v pravém podstromu přijímá prázdný řetězec, je nutné podstatně hlubší zanoření do derivačního stromu, aby bylo možné potřebnou množinu FIRST získat. V případě, že tato situace nastává často, může docházet ke znatelné ztrátě efektivity.

V knihovně jsou proto připraveny dva módy. V prvním (eFirst/0) se provádí výpočet množin FIRST opakovaně pro každou DFOLLOW. Zde se naplno projevuje vliv struktury parseru na jeho abstraktní interpretaci. V druhém módu (eFirst/1) se jednou získané výsledky ukládají, což nám umožňuje globální charakter množin FIRST. Vyhneme se tak opakovanému prohledávání pravého podstromu v módu first/0. Při prvním průchodu se vše vypočte a v následujích krocích jsou již získávány množinu FIRST jednotlivých parserů z uložených (parciálních) výsledků. Výpočet tak pro daný parser proběhne nejvýše jednou.

Zmiňme ještě druhou možnost -- situaci, kdy by byla zvolena levá asociativita kombinátoru sekvenční kompozice (viz také obrázek ).

Obrázek: Levá a pravá asociativita

V tomto případě struktura parseru v podstatě odpovídá struktuře výpočetního stromu, což je výhodné především pro abstraktní interpretaci parseru.

Pro výpočet DFOLLOW se používá identický algoritmus jako u pravé asociativity. Zde však nedochází v případě $\varepsilon$-přechodu v parseru stojícím v sekvenční kompozici vpravo při jeho abstraktní interpretaci k tak zevrubné analýze a už vůbec ne k opakovanému provádění některých jejích částí. Výsledek té její části, který se u pravé asociativity opakuje je zde získáván v průběhu rozkladu od předků -- výpočet množiny DFOLLOW zde má inkrementální charakter.

Takto efektivního výpočtu lze dosáhnout s levě asociativním kombinátorem sekvenční kompozice pouze v případě módů ukládajících mezivýsledky pro pozdější použití.

Early výpočet DFOLLOW
Množiny DFOLLOW jsou, stejně jako u FIRST, z důvodu prostorové složitosti reprezentovány seznamem podmínek. Operace nad DFOLLOW jsou prováděny tak, jak bylo popsáno výše.

Lazy výpočet DFOLLOW
Rozklad vstupního textu s použitím množiny DFOLLOW lze v některých případech zefektivnit tak, že se proces jejího výpočtu neprovádí průběžně, ale pouze se přenášejí informace k němu potřebné, aby pak mohl být ve chvíli, kdy bude DFOLLOW potřeba, proveden.

Pro přenos potřebných dat se používá zásobník parserů. Místo výpočtu množiny FIRST parseru stojícího v sekvenční kompozici vpravo se tento uloží na zásobník. Tak výpočet pokračuje až do chvíle, kdy se má použít $\varepsilon$-přechod.

Potom se množina DFOLLOW získá dle následujícího algoritmu: