Jednoduchá iterace

V první části této kapitoly, jejímž tématem je iterovaná aplikace parserů, se budeme věnovat její nejobyčejnější variantě, kterou je iterace jednoduchá.

A začneme motivačním příkladem. Definujme parser prologVar přijímající identifikátor prologovské proměnné. Její identifikátor začíná velkým písmenem nebo znakem '_' a je tvořen libovolnou posloupností písmen, číslic a znaku '_':

prologVar(W):-
 W :->
        ((upper <:> symbol("_")) <&> prologVarBody).

prologVarBody(W):-
 W :->  
         (fulfil(isDigitChar_) <&> prologVarBody
          <:>
         epsilon).

S konstrukcí iterací objevující se v prologVarBody, kterou lze obecně vyjádřit v Backusově normální formě jako:

$\begin{displaymath}<p*> ::= <p> <p*>\vert\varepsilon\end{displaymath}$

se můžeme setkat velmi často. V předchozím textu byla použita například v parseru nat. Jistě si lze snadno představit mnoho dalších parserů s podobnou strukturou. Příkladně parser řetězce prázdných znaků (white space), písmen či znaků speciálních.

Aby jsme nemuseli zbytečně definovat množství různých parserů s podobnou strukturou, zavedeme pro tuto konstrukci iterátor, který mutuje parser tak, že je opakovaně aplikován na vstupní text.

Tak jako byla BNF dodatečně obohacena o operaci iterace i my obohatíme naši knihovnu o jí odpovídající konstruktor, neboť si to svým významem nepochybně zaslouží:

<**>(P,W):-
 W :->
        (P <&> P<**>
          <:>
         epsilon).

Protože jsme použili kombinátor <&>, je výsledek vydán ve formě seznamu. Protože mutátor vrací všechny možné přípustné rozklady, znamená to, že pokud selže v

-té iteraci, jeho výstupem bude seznam úspěšných rozkladů obsahující

výsledků pro každou z

až

úspěšných aplikací parseru

. Dle zavedené konvence budou výsledky seřazeny v pořadí podle klesající délky.

Ve většině případů se budeme zajímat pouze o první rozklad ze struktury LOS, ve kterém je daný parser úspěšně aplikován v největším možném počtu. Ovšem, že bychom mohli použít diamant pro dodatečné oříznutí seznamu úspěšných rozkladů, my jej ale vložíme přímo do varianty mutátoru <**> ořezávající LOS již v průběhu výpočtu:

<<*>>(P,W):-
 W :->
        (P <&> P<<*>>
          <:>
         epsilon <>).

Co touto mírnou modifikací získáme? Především omezíme paměťovou, ale také časovou složitost. Původní mutátor <**> nejdříve zanořením na dno rekurze vytvoří nejdelší derivaci. Pak se při vynořování uplatňují primitiva epsilon, díky nimž se v jeho průběhu vytvoří zbylé derivace. Oříznutím v <<*>> však zůstává v seznamu úspěšných rozkladů nejvýše jedna derivace -- a to právě ta maximální. Není tedy nutné řetězit výsledky přebytečných derivací (v <&>). Při

úspěšných aplikacích parseru

tedy ušetříme $\sum_{j=1}^{i} j~- i$ řetězení.

Vraťme se k příkladu prologovské proměnné z úvodu této části a použijme právě vytvořený iterátor:

prologVar(W):-
 W :->
        ((upper <:> symbol("_")) 
           <&> 
            fulfil(isDigitChar_)<<*>>).

V případech jiných parserů bude potřeba zpracovávat či řetězit výsledky po jednotlivých aplikacích iterovaného parseru vlastním způsobem. Dostat pod kontrolu i řetězení umožníme konstruktorem:

% <*@*>(+Parser,+Bottom-Function,?Wrapper)
<*@*>(P,B-F,W):-
 W :->
        (P <&>> P<*@*>B-F <@ F
          <:>
         B).

Tento mutátor je dostatečně obecný na to, aby umožňoval specifikovat jak operaci, kterou se mají výsledky po iteracích modifikovat, tak parser fungující jako terminátor. Pomocí <*@*> lze zavést parser vydávající výsledek v n-tici:

<**>>(P,W):-
 W :->
        (P <*@*>return(nil)-id).

či vyjádřit <**> jiným způsobem:

<**>(P,W):-
 W :->
        (P <*@*>epsilon-tuple2List).

Stejně jako v případě mutátoru <**>, je i pro <*@*> definována diamantová verze. Konvence pro pojmenovávání iterátorů je zřejmá z tabulky

. Číslo

v ní určuje počet úspěšných aplikací parseru. V posledním řádku je uveden maximální počet derivací v seznamu úspěšných rozkladů.

**Tabulka:** Mutátory pro 0 a více iterací
Počet iterací	Základní	Diamantové	Výsledek
$i \geq 0$	`<**>`	`<<*>>`	seznam
$i \geq 0$	`<@>`	`<<*@>>`	dle param.
$i \geq 0$	`<**>>`		n-tice
Derivací v LOS

Právě diamantovou verzi použijeme pro vytvoření dvou mutátorů parserů, jenž modifikují daný parser tak, že ignoruje prázdné znaky předcházející resp. následující za akceptovanou sentencí:

#>(P,W):-
 W :->
     ( whiteSpace<<*@>>return(whiteSpace)-sndTuple &> P ).

<#(P,W):-
 W :->
     ( P <& whiteSpace<<*@>>return(whiteSpace)-sndTuple ).

Ano, diamantová varianta <<*@>> se má k <*@*> stejně jako <<*>> k <**>. Seznam úspěšných rozkladů je v průběhu výpočtu ořezáván. Navíc, protože nás typicky nezajímá výsledek složený z prázdných znaků, jsou tyto pomocí selektoru sndTuple v průběhu rozkladu odstraňovány a nakonec vydá celý parser jako svou výslednou hodnotu atom whiteSpace. Ale i tento atom je nakonec odstraněn v kombinátoru <& resp. &>:

?- s("[  _flippedList ]")+L :->
|       brackets( #>prologVar<# ).
L= [s("") > "_flippedList"]
Yes

Prázdné znaky umožňují používat ve zdrojových textech volný formát zápisu -- obvykle mohou být volně vkládány mezi libovolné dvě lexikální položky a slouží tak k pohodlnějšímu a čitelnějšímu zápisu.

Charakter komentářů a prázdných znaků je ve zdrojových textech podobný. Komentáře mají význam pouze pro programátora. Po analyzování zdrojového kódu význam ztrácejí a stejně jako prázdné znaky nejsou do syntaktického stromu zpravidla vkládány.

V tomto odstavci se budeme věnovat jednořádkovému komentáři, jenž je obvyklou součástí programovacích jazyků. Vytvoříme pro něj parser na příkladu jazyka Prolog. Zde začíná znakem '%' a dále pokračuje až po znak nového řádku. Parser by tedy měl přijímat vstup až po znak s ASCII kódem . Pro tento účel použijeme nový kombinátor nonSymbol:

nonSymbol(S,W):-
       fulfil(\==(S),W).

Ten akceptuje znaky různé od parametru S. V knihovně je připravena ještě spřízněná varianta nonSymbols.

Výše popsaná struktura komentáře se objevuje ve většině programovacích jazyků. Jednotlivé varianty se liší pouze v tokenu, jímž komentář začíná. Místo toho, abychom implementovali mnoho různých, ale podobných parserů, zavedeme jeden obecný kombinátor:

lineComment(T,W):-
 W :->
        (token(T) 
          &> 
           nonSymbol([10])<<*@>>return(comment)-sndTuple).

Parametr T obsahuje token, jenž uvozuje komentář. Vše až po konec řádku je ignorováno a jako výsledná hodnota je vydán atom comment.

Za všechny příklady uveďme tři následující:

prologLComment(W):-
        W :-> lineComment("%").
haskellLComment(W):-
        W :-> lineComment("--").
makeLComment(W):-
        W :-> lineComment("#").

Ale vraťme se opět k formalizmu BNF.

Jistě nebude překvapivé, když nyní představíme mutátor korespondující s další operací iterace z rozšířené Backusovy normální formy vyjádřitelnou jako:

$\begin{displaymath} <p+> ::= <p> <p*> \end{displaymath}$

Tato operace nachází uplatnění v případech, kdy se zajímáme pouze o neprázdné posloupnost výsledků -- parser tedy musí být aplikován alespoň jednou.

Definice tohoto mutátoru <++> odpovídá výše vyjádřené obecné definici. Jako jeho základ tedy použijeme <**>:

<++>(P,W):-
 W :->
        (P <&> P<**>).

Opět jsou v knihovně analogickým způsobem vytvořeny varianty <<+>> a <+@+> tohoto mutátoru, viz tabulka

**Tabulka:** Mutátory pro 1 a více iterací
Počet iterací	Základní	Diamantové	Výsledek
$i \geq 0$	`<++>`	`<<+>>`	seznam
$i \geq 0$	`<+@+>`	`<<+@>>`	dle param.
Derivací v LOS		$0 \vee 1$

Povšimněme si ještě jedné vlastnosti <++>. Zatímco u mutátoru <**> jsme se mohli spolehnou na to, že vždy uspěje a vydá alespoň jeden výsledek, v případě <++> to už neplatí. Ten může selhat a skončit pouze s prázdným seznamem úspěšných rozkladů. V případě nesprávného použití tedy může dojít ke ztrátě výsledků.

Variantu mutátoru <++> použijeme k reformulaci parseru přirozených čísel (tentokrát již skutečně poslední):

natural(W):-
 W :->
        (digit<<+>> <@ foldL(evalNatural,0)).

Poslední operací BNF, se kterou se seznámíme v této části, je operace vyjadřující volbu -- připouští tedy jednu nebo žádnou aplikaci daného parseru:

$\begin{displaymath} <p?> ::= <p> \vert \varepsilon \end{displaymath}$

Můžeme se s ní setkat, stejně jako s dříve uvedenými operacemi, i v jiných formalismech. Jedním z nich jsou již zmíněné regulární výrazy. Definujme nyní parser vydávající strukturu LOS s žádnou nebo s jednou derivací, pro změnu nejdříve v obecné verzi:

<?@?>(P,No-Yes,W):-
 W :->
        ( P <@ Yes
           <:>
          return(No)).

Mutátor <?@?> má dva přidané parametry. Prvním je konstanta

použitá v případě neexistence přípustné sentence a druhým predikát

pro transformaci získané hodnoty v případě úspěchu.

Varianta <??> je vhodná pro použití společně se seznamy. Vzhledem k její jednoduchosti ji nebudeme vyjadřovat pomocí obecnější verze, ale raději tak učiníme přímo:

<??>(P,W):-
 W :->
        ( P
           <:>
          epsilon).

Tuto část věnovanou jednoduché iteraci zakončíme příkladem.

Subsections

- Příklad:

dvorka 2013-12-31