Mutátory parserů

Při seznamování se s konstruktory parserů pokračujme představením jejich druhé kategorie, kterou jsou mutátory. Jak samotný název napovídá, mutátor vytváří z již existujícího parseru, který je jeho parametrem, parser nový, jenž je nějakým způsobem modifikován -- vytváří tedy jeho mutaci.

Nejdříve vytvoříme dva mutátory upravující daný parser tak, že ten sice pracuje stejně, ale svůj výsledný seznam úspěšných rozkladů nějakým způsobem zeštíhluje.

Prvním z nich je mutátor nazývaný diamant. Jak jsme se již přesvědčili, může seznam úspěšných rozkladů obsahovat větší počet derivací. Obvykle jsou nezbytné pro další zpracování vstupu, avšak v určité fázi se pro nás mohou stát již nezajímavými a potřebovali bychom se jich zbavit.

Obvykle jedinou relevantní derivací ve struktuře LOS je maximální derivace, stejně jako tomu bylo v příkladě použití parseru nat. Pro takové oříznutí seznamu úspěšných rozkladů nám bude sloužit mutátor <>:

% <>(+Parser, ?Wrapper)
<>(P,I+L):-
 I+L_ :-> P,
        ( L_==[] -> L=[] ; L_=[L__|_],L=[L__]).

Použitím diamantu získáme parser vydávající seznam úspěšných rozkladů obsahující nejvýše jednu derivaci. Tato derivace je získána v případě úspěchu z hlavy původní struktury LOS.

Slíbeným druhým mutátorem je whole. Modifikací daného parseru vytvoří nový parser, který pracuje stejným způsobem a navíc zaručuje, že každá derivace obsažená ve struktuře LOS zpracovala celý vstup:

% whole(+Parser, ?Wrapper)
whole(P,I+L):-
 I+Lt :-> P,
        filter(fstTupleSEmpty,Lt,L).

Od parseru $P$ je získán seznam úspěšných rozkladů. Predikátem vyššího řádu filter jsou z něj odstraněny pomocí predikátu fstTupleEmpty derivace, které nezpracovaly celý vstup.

V předchozích částech jsme zkonstruovali několik parserů u nichž se projevila určitá vada spočívající v tom, že jejich výsledky sice správně zachycovaly strukturu vstupního textu, ale jejich syntaktický strom nebyl příliš vhodný pro další zpracování. Za všechny uveďme parser num. Spíše než n-tice cifer tvořící přijaté číslo by jako výsledek parseru byla vhodnější samotná hodnota tohoto čísla. Podobných příkladů bychom jistě našli ještě mnoho.

Tento typ problému je jako šitý na míru řešení právě pomocí mutátorů. Vytvoříme tedy důležitý mutátor parserů, jenž transformuje parser tak, že ten na svoje výsledky aplikuje danou sémantickou operaci ve formě predikátu:

% <@(+Parser, +Function, ?Wrapper)
<@(P,F,I+L):-
        I+L_ :-> P,
        mapList(fstTuple *>* (F =-> sndTuple),L_,L).

Mutátor nejprve aplikuje na vstup parser $P$. Následně na výsledek v každé položce seznamu úspěšných rozkladů aplikuje pomocí predikátu vyššího řádu mapList daný predikát $F$. První argument mapList nejdříve pomocí selektoru sndTuple vyjme z derivace $NotParsed>Result$ druhou položku tj. výsledek parseru a na něj aplikuje daný predikát. Z výsledku aplikace a nezpracovaného zbytku vstupu je pomocí konstruktoru dvojice *>*/2 následně vytvořena opět položka struktury LOS. Výsledný seznam $L$ má stejnou délku a liší se od původního v tom, že na všechny výsledky byl aplikován predikát $F$.

Predikát <@ je rovněž definován jako operátor a jeho priorita je zvolena tak, aby byla minimalizována nutnost závorkování.

Právě definovaný mutátor využijeme k definovaní parseru digit, jehož výsledkem bude hodnota přijaté číslice. Převod je realizován v predikátu ascii2Atom:

digit(W):-
 W :->
        (fulfil(isDigit) <@ ascii2Atom).

Zatím ještě posečkáme s novou verzí parseru přirozených čísel a raději vytvoříme parser souřadnice bodu v rovině reprezentovaný jako dvě čísla oddělená čárkou a uzavřená v hranatých závorkách -- poslouží nám jako inspirace při vytváření dalších kombinátorů:

point2D(W):-
 W :->
        (symbol("[")
          <&>>
         nat <&>> symbol(",") <&>> nat
          <&>>
         symbol("]")).

V mnoha oblastech, ať už v matematice či v programování, je často používáno pro strukturování zápisu uzavírání jeho částí mezi dva symboly, jenž mají povahu závorek. Může jít kupříkladu o dvojici souřadnic v příkladu nebo o argumenty prologovské struktury, jenž jsou ohraničeny dvojicí ( a ). Funkci těchto symbolů však po zpracování parserem přebírá syntaktický strom a tak je jejich další uchovávání ve výsledku zpravidla zbytečné.

Zmíněná konstrukce je natolik běžná, že se vyplatí vytvořit dva nové kombinátory, jenž následně umožní ignorovat závorky a jim podobné přebytečné symboly a do výsledku je neukládat. Pomůže nám při tom právě definovaný mutátor pro aplikaci sémantické akce:

% <&(+Parser1, +Parser2, ?Wrapper)
<&(P1,P2,W):-
 W :->
        (P1 <&>> P2 <@ fstTuple).

Na vstup jsou sice aplikovány oba parsery, pomocí selektoru fstTuple je ale výsledek druhého parseru z výsledku odstraněn. Výsledkem sekvenční kompozice parserů $P1$ a $P2$ provedené kombinátorem <& jsou tedy derivace obsahující pouze výsledek parseru $P1$ a nezpracovaný zbytek vstupu odpovídající aplikaci obou parserů. Parser $P2$ tedy zpracovává část vstupu, např. závorku, ale ta se ve výsledném syntaktickém stromu neobjeví.

% &>(+Parser1, +Parser2, ?Wrapper)
&>(P1,P2,W):- 
 W :-> 
        (P1 <&>> P2 <@ sndTuple).

Kombinátor &> je symetrickou variantou k <& -- rovněž aplikuje na vstup jak parser $P1$ tak $P2$, v derivacích však na rozdíl od <& ignoruje výsledek parseru $P1$.

Zajdeme ještě dál a definujeme kombinátor speciálně pro uzávorkované výrazy:

enclosedIn(P,SO and SC,W):-
 W :->
        (SO &> P <& SC).

Parametr $SO$ resp. $SC$ je parserem sentence, která otevírá resp. uzavírá blok. $P$ je parserem samotného uzávorkovaného výrazu a jeho výsledek tvoří výstup parseru, jenž kombinátor enclosedIn vytváří.

V knihovně kombinátorů jsou pro nejpoužívanější typy závorek připraveny odpovídající kombinátory definované pomocí enclosedIn.

Přínos těchto nově zavedených kombinátorů je ve dvou věcech. Jednak zčitelňují vytvářený zdrojový kód a dále umožňují zeštíhlovat seznam úspěšných rozkladů a tím otevírají cestu k efektivnějším parserům:

parentheses(P,W):-
        W :-> P enclosedIn symbol("(") and symbol(")").        
brackets(P,W):-
        W :-> P enclosedIn symbol("[") and symbol("]").        
brace(P,W):-
        W :-> P enclosedIn symbol("{") and symbol("}").        
angled(P,W):-
        W :-> P enclosedIn symbol("<") and symbol(">").

nebo také:

prologEnvelope(P,W):-
        W :-> P enclosedIn (symbol(":") &> symbol("-")) 
                             and
                            symbol(".").

Nejen při analyzování zdrojových textů se často setkáváme s tím, že chceme přijmout statický řetězec, jakým je například klíčové slovo. Jednotky vstupu, které jsou z hlediska syntaktické analýzy dále nedělitelné, zde bývají obvykle nazývány tokeny. Příkladem může být řetězec ":-" v kombinátoru prologEnvelope. Zkonstruujme tedy parser pro tento účel a nazvěme jej právě token:

% token(+String, ?Wrapper)
token([H|T],W):-
        W :-> (symbol([H]) <&>> token(T) <@ tuple2List).       
token([],W):-
        W :-> epsilon.

Parser token přijímá daný řetězec, jenž je v případě úspěchu jedinou derivací struktury LOS. Aby mohl být výsledek vydán jako řetězec, konvertujeme n-tici v průběhu výpočtu na seznam pomocí predikátu tuple2List/2. Seznam je standardní datovou strukturou jazyka Prolog, a proto je v mnoha situacích reprezentace výsledku v této formě z hlediska dalšího zpracování nejvýhodnější. Proto definujme variantu kombinátoru sekvenční kompozice pro tento případ:

% <&>(+Parser1, +Parser2, ?Wrapper)
<&>(P1,P2,W):-
 W :->
        (P1 <&>> P2 <@ tuple2List).

Konečně máme připraveno vše potřebné, abychom mohli definovat parser pro přirozená čísla, jenž byl zmíněn několikrát v průběhu této části:

% natural(?Wrapper)
nat(W):-
        W :-> ( digit <&> nat <:> epsilon <> ).
natural(W):-
        W :-> ( digit <&> nat <@ foldL(evalNatural,0) ).

evalNatural(Acc,I,Result):-
        Result is Acc*10 + I.

Parser natural přijímá přirozené číslo a jako výsledek vydává jeho hodnotu. Výsledný seznam úspěšných rozkladů obsahuje nejvýše jednu derivaci. Reprezentace výsledku nat ve formě seznamu umožní výpočet hodnoty čísla pomocí foldL/4. Použitím nově definovaných konstruktorů <&>, <> a <@ jsme dosáhli praktické použitelnosti tohoto parseru.

Tuto část zakončíme inovovanou definicí motivačního příkladu, který stál na jejím počátku:

point2D(W):-
 W :->
        brackets(natural <&>> symbol(",") &> natural).

a příkladem jejího použití:

?- s("[12,36]")+L :-> point2D.
L= [s([])> (12>36)]
Yes