Primitivní parsery

Primitivní parsery jsou základními stavebními kameny kombinátorového vytváření parserů -- musíme tedy začít u nich. Můžeme je rozdělit do dvou skupin podle toho, zda přijímají nějakou část vstupního textu či nikoli. Jediným zástupcem první skupiny je primitivum item. Primitivy náležejícími do skupiny druhé jsou ta, která přijímají pouze prázdný vstup, sem patří epsilon, return a terminate.

V teorii gramatik je prázdný řetězec označován symbolem $\varepsilon$. V duchu této tradice tedy definujme epsilon jako primitivní parser, který přijímá prázdný vstup a jako výstup vrací prázdný syntaktický strom reprezentovaný atomem []:

epsilon(I+[I>[]]).

Druhým primitivem, které si ukážeme, je return. Parser return vždy uspěje, aniž by ze vstupu cokoli přijal. Protože výsledná hodnota, kterou vydává každý parser při úspěšném rozkladu, u něj nezávisí na vstupu, je explicitně specifikována v parametru $V$:

return(V,I+[I>V]).

Jelikož return je zobecněním epsilon, je samozřejmě možné definovat epsilon i následujícím způsobem:

epsilon(W):-
        return([],W).

Opakem k return je primitivum terminate. Parser terminate selže vždy, bez ohledu na obsah vstupu. Selhání vyjadřuje prázdný seznam úspěšných rozkladů:

terminate(_+[]).

Tím máme definována primitiva přijímající prázdný vstup a nyní již přistupme k definici parseru item, jenž přijímá z neprázdného vstupu první položku. Význam tohoto primitiva tkví především v tom, že je realizací elementární operace nad vstupem zmíněné v části . Všechny další parsery pracující se vstupem mohou tedy být pomocí něj definovány. Nechť tedy item přijme z neprázdného vstupu první položku a v případě prázdného vstupu ať selže:

item(s([S|Is])+[s(Is)>S]).
item(s([])+[]).

Tento parser je sice důležitý, ale sám o sobě není příliš přínosný. Můžeme však pomocí něj definovat jiný, který již rozeznává dané symboly. Bylo by samozřejmě možné specifikovat přípustné symboly výčtem, my však zvolíme elegantnější řešení. Pro rozlišení přípustných symbolů použijeme podmínku reprezentovanou predikátem, který bude parametrem $C$ tohoto parseru:

fulfil(C,I+L):-
        item(I+Li) 
        -> (Li=[N>R],:-@ [C,[R]] -> return(R,N+L)
                                 ;  terminate(I+L)).

Parser fulfil se nejdříve pokusí přijmout pomocí primitiva item jeden symbol ze vstupu. Jestliže uspěje, zkontroluje, zda symbol splňuje podmínku $C$ a vrátí jej pomocí primitiva return. V opačném případě signalizuje neúspěch parserem terminate. Použití primitiv není bezpodmínečně nutné, ale je patrné, že učinilo zdrojový text čitelnější.

Pomocí fulfil již můžeme definovat parser pro jednotlivé položky vstupu, jenž z pochopitelných důvodů ponese název symbol:

symbol(S,W):-
       fulfil(==(S),W).

Stejným způsobem zaveďme ještě dva parsery, které využijeme v dalším textu:

lower(W):-
       fulfil(isLwrChar,W).

upper(W):-
       fulfil(isUprChar,W).

Takto bychom mohli pokračovat a definovat další a další parsery, podobné těm výše uvedeným, jako třeba digit, bracket či consonant. Základ knihovny kombinátorů parserů tvoří sada právě takových parserů. Rovněž jsou připraveny predikáty pro klasifikaci znaků (jako isLwrChar), které lze použít společně s primitivem fulfil.

V situacích, kdy nemáme k dispozici vhodný predikát, který by mohl být podmínkou parseru fulfil, protože jeho vytváření pro jedno použití by nemělo smysl, nebo pokud získáme, třeba i za běhu, přípustné symboly ve formě již zmíněného výčtu, budeme používat parser symbols:

symbols(A,I+L):-
        item(I+Li) 
         -> (Li=[N>R],member(R,A) -> return(R,N+L)
                                  ;  terminate(I+L)).

Jako příklad si ukažme parser pro takzvané prázdné znaky. Použití fulfil s explicitně definovaným predikátem podmínky v něm raději nahradíme výčtem jednotlivých přípustných znaků:

whiteSpace(W):-
        symbols([32,9,13,10],W).

Samotné primitivní parsery, tak jak jsme je definovali, nejsou příliš silné. Teprve v následujících částech prokáží svůj skutečná význam. Představíme si konstruktory parserů, které právě pomocí manipulací s primitivy umožní vytváření parserů pro řešení reálných úloh syntaktické analýzy.