Iterace se sémanticky relevantními separátory

Konstruktory se kterými jsme se seznámili v kapitole nám umožnily parsovat posloupnosti položek oddělené textem, který neměl z hlediska další analýzy žádný význam a tak mohl být v jejím průběhu ignorován.

V této části se budeme věnovat poněkud složitějšímu případu, kdy budou separátory nositeli sémantické informace.

Asi nejtypičtějším případem takového vstupního textu jsou aritmetické výrazy. Použijeme je tedy i v motivačním příkladu, kde budou vytvořeny z celých čísel pomocí operací násobení a podílu, které budou mít levou asociativitu. V zápisu výrazů bude také možné používat závorky. Gramatiku výše popsaných aritmetických výrazů lze vyjádřit v Backus-Naurově formě takto:

$<expr>$	$::=$	$<term>$
$<term>$	$::=$	$<expr> * <fact> \vert$
		$<expr> / <fact>$
$<fact>$	$::=$	$<int> \vert$
		$<fun> \vert$
		$( <expr> )$

S pomocí konstruktorů, které máme již k dispozici, můžeme takovou gramatiku snadno převést do jazyka Prolog přímým přepisem do notace používané v knihovně:

expr(W):-
        term(W).
term(W):-
 W :->  (expr <&>> symbolA("*") <&>> fact)
          <:
        (expr <&>> symbolA("/") <&>> fact).
fact(W):-
  W :->  int
          <:
         poorIdf <&> parentheses(commaListOf expr)<?>
          <:
         parentheses(expr).

Tento parser by nám měl pomoci analyzovat strukturu výrazu a vydat ji ve formě nějakého syntaktického stromu. Vzhledem k tomu, že jde o aritmetické výrazy, bylo by přínosnější, kdyby syntaktický strom nějakým způsobem zpracovával. My si v tomto případě ukážeme vyhodnocení výrazu, ale způsob zpracování může být mnohem obecnější -- lze si například představit, že bude generován strojový kód nebo prováděn překlad do jiné notace.

Mnohem závažnější závadou je, že tento parser není vůbec použitelný. Problém je v parseru term, který, vzhledem k asociativitě operátorů a z toho plynoucího způsobu jejich vyhodnocování, obsahuje levou rekurzi a výpočet by proto nikdy neskončil. Nejdříve odstraníme tento nedostatek.

Řešením problému s levou rekurzí je samozřejmě její nahrazení iterací. Podíváme-li se na gramatiku, tak vidíme, že aritmetický výraz je posloupností faktorů, které jsou odděleny operátory '*' a '/', jenž mají stejnou precedenci. Prvním krokem tedy může být vyjádření pomocí již dříve definovaného iterátoru:

term(W):-
 W :->    
        (expr <&>> 
         ((symbolA("*")<:symbolA("/")) <&>> expr)<**>) 
           <@ shownl.

Iterátor <**> se postará o to, aby výpočet skončil. Zbývá definovat predikát provádějící vyhodnocení v mutátoru aplikace sémantické operace, který zde byl nahrazen shownl, aby jsme si mohli ukázat, jaké operace bude nutné zpracovávat:

?- term(s("1/2/3")+L).
1>[/ >2, / >3]
1>[/ >2]
1>[]
L= [s([])> (1>[/ >2, / >3]), _] 
Yes

Kromě iniciální hodnoty za argumentem vždy následuje seznam, v němž je operátor společně s pravým operandem ve dvojici. Snadno lze nahlédnout, že je to varianta predikátu foldL/4. Buď můžeme použít přímo foldL/4 a na získání argumentu a operace volat v každém kroku predikát nebo definovat jeho jednoúčelovou variantu:

chainFoldl(InVal>[Op>I|IT],Out):-
        :-@ [Op,InVal,I,OutVal],
        chainFoldl(OutVal>IT,Out).
chainFoldl(Out>[],Out).

pomocí které již dosáhneme vyhodnocení:

?- term(s("1/2/3")+L).
L = [s([])>0.166667, s("/3")>0.5, _]
Yes

Jako obvykle tuto konstrukci zobecníme a vytvoříme knihovní kombinátor, který obsahuje levou faktorizaci již uvnitř své definice:

lchainedBy(P,S,W):-
 W :->
        ( P <&>> (S <&>> P)<*> ) <@ chainFoldl.

Variantu pro operátory s pravou asociativitou lze zkonstruovat analogicky. S pomocí lchainedBy již můžeme přeformulovat parser z úvodu této kapitoly tak, aby fungoval korektně:

expr(W):-
 W :->  fact
         lchainedBy 
          (symbolA("*")<:symbolA("/"))

Již se nezacyklí:

?- s("1*prumer(12,6,3)*(8/10)")+L :-> expr.
L= [s([])>5.6]
Yes

Vytvořený predikát by však mohl pracovat efektivněji. Kombinátor lchainedBy získává výsledek až po rozkladu celého vstupu ze seznamu voláním varianty foldL/4. Výhodnější by bylo provádět výpočet již v průběhu rozkladu. Vytvoříme tedy kombinátor, který sémantické akce odpovídající jednotlivým separátorům aplikuje v průběhu analýzy vstupu. Pro vyhodnocení navíc používá predikát předaný v parametru $E$:

chainL(E,P,S,W):-
 W :->
        (P<&>>S)<*@*>P-eChainL(E).

kde eChainL je analogie chainFoldl, která po každé iteraci provádí výpočet voláním vyhodnocovače $E$. Ještě si povšimněte malého triku, jenž byl použit v mutátoru <*@*>. Způsobem použitým při implementaci lchainedBy by vyhodnocení nebylo možné, protože iniciální hodnota přichází až po vynoření z rekurze. Proto nahradíme terminátor (původně přijímající prázdný vstup) parserem iniciální hodnoty. Parser se tím také zjednoduší.

Zkonstruování varianty chainR pro operátory s pravou asociativitou již není problematické.

Na motivačním příkladu bylo opět vidět, že zápis parserů může plnohodnotně nahradit gramatiky v jejich roli při specifikaci analyzovaných jazyků. Kombinátory představené v této části zjednodušují vytváření parserů podle gramatik, které popisují výrazy. Díky nim se vyhýbáme nutnosti transformací gramatik za účelem odstranění levé rekurze, která by jinak vedla k zacyklení. Rovněž se nemusíme zabývat levou faktorizací pro zefektivnění rozkladu, neboť ta je již součástí definic kombinátorů.