Množina FIRST

Obdobně jako v předchozím případě budeme postupovat i při výpočtu množiny FIRST, v němž použijeme také mód empty/0. Situace zde bude jen nepatrně složitější.

Nejdříve si uveďme formální definici množiny FIRST:

Definice:
Pro větnou formu v bezkontextové gramatice G=(N,T,P,S) platí:

Množina obsahuje všechny terminální symboly, které se mohou vyskytnout na začátku řetězců derivovaných z . Jestliže lze z  derivovat také prázdný řetězec, pak jej množina FIRST obsahuje rovněž.

Množinu FIRST budeme používat při rozhodování, který z parserů v alternativní kompozici vybrat. Její výpočet budeme provádět společně s určením schopnosti přijímat prázdný řetězec v módu eFirst/0, jenž bude místo seznamu úspěšných rozkladů vydávat strukturu:

Navíc je připraven mód first/0, který využívá eFirst/0 a vydává pouze množinu FIRST. FIRST nebude reprezentována výčtem výhledů, ale seznamem podmínek, které budou dostatečně přesně vymezovat její rozsah.

Ukažme si nejprve rozšíření definic základních primitiv:

epsilon(first+[]).
return(_,first+[]).
terminate(first+[]).

Primitivum item přijímá ze vstupního textu libovolnou položku:

item(first+[pcTrue]).

Parser terminálních symbolů symbol už může použít implicitní cestu výpočtu:

fulfil(C,first+[C]).
symbol(S,I+FIRST):-                  
        fulfil(==(S),I+FIRST).

FIRST sekvenční kompozice $P1$ a $P2$ je tvořena množinou FIRST($P1$). Pokud navíc $P1$ přijímá prázdný řetězec je sjednocením množin FIRST($P1$) a FIRST($P2$):

<&>(P1,P2,eFirst+eFirst(Empty,FIRST)):-
        eFirst+eFirst(Empty1,FIRST1) :-> P1,
        (Empty1=true -> first+FIRST2 :-> P2
                     ;  FIRST2=[]),
        append(FIRST1,FIRST2,FIRST),
        <&>(P1,P2,empty+Empty).
<&>(P1,P2,first+FIRST):-
        <&>(P1,P2,eFirst+eFirst(_,FIRST)).

Množina FIRST alternativní kompozice parserů $P1$ a $P2$ je vždy sjednocením množin FIRST($P1$) a FIRST($P2$):

<:>(P1,P2,first+L):-
        first+L1 :-> P1,
        first+L2 :-> P2,
        append(L1,L2,L).

Jako příklad si ukážeme parser double v módu first/0:

?- first+L :-> double.
L = [lElementOf("-0123456789"])]
Yes

Také pro tyto módy jsou připraveny predikáty $invoke$$<$$Mode$$>$, jako invokeEmpty a invokeFIRST.