Kombinátory parserů

První kategorií, se kterou se seznámíme, jsou kombinátory parserů. Kombinátory mají mezi konstruktory parserů výsadní postavení. Jsou ztělesněním samotné myšlenky kombinátorového přístupu při vytváření parserů, která je prezentována v této práci, a jako takové mají mezi konstruktory nejpočetnější zastoupení.

Kombinátor je predikát provádějící kompozici několika parserů, jejímž výsledkem je parser nový. Snad v každé gramatice se objevuje zřetězení, proto asi nejběžnější operací nad parsery je jejich sekvenční kompozice. Definujme tedy kombinátor pro tento účel:

% <&>>(+Parser1, +Parser2, ?Wrapper)
<&>>(P1,P2,I+L):-
        I+L1 :-> P1,
        <&>>^(P2,L1,L-[]).

% <&>>^(+Parser2, +LosOfP1, -ComposedLosOfP1P2)
<&>>^(_,[],D-D).
<&>>^(P2,[N>R|L1s],L12-D):-
        N+L2 :-> P2,
        mapListDL(fstTuple *>* (const(R) *>* sndTuple),L2,L12-D_),
        <&>>^(P2,L1s,D_-D).

Kombinátor <&>> postupně aplikuje na vstup parsery $P1$ a $P2$. Jejich výsledky potom zkombinuje.

Na vstup $I$ je tedy nejdříve aplikován parser $P1$. Jeho výstupem je seznam úspěšných rozkladů $L1$ délky $n$. Ten může obsahovat několik, jednu nebo dokonce žádnou derivaci. Jak bylo uvedeno, každá položka tohoto seznamu se skládá z nezpracovaného zbytku vstupu a výsledku:

$$NotParsedRest1>Result1$$

Pomocný predikát <&>>^ aplikuje na každý zbytek vstupu $NotParsedRest1$ parser $P2$. Každou aplikací druhého parseru na zbytek v $i$-té položce $L1$ získává nový seznam $L2_i$. Následně provede zkombinování výsledků obou parserů pomocí predikátu mapListDL a tím vytvoří seznam $L12_i$. Schematicky má položka seznamu $L12_i$ tvar:

$$NotParsedRest12>(Result1>Result2)$$

Predikát mapListDL se od mapList liší pouze tím, že jeho výstupem je seznam v rozdílové reprezentaci. Rozdílové seznamy $L12_1$,...,$L12_n$ musí být ve výsledném seznamu $L$ zřetězeny a právě rozdílová reprezentace nám umožní efektivní provedení této operace.