Zeštíhlování seznamu úspěšných rozkladů

Jak jsme se již přesvědčili, schopnost parserů vracet více než jednu derivaci v seznamu úspěšných rozkladů je sice velmi užitečná, ale rovněž může vést k jeho neočekávané expanzi. Tato expanze může dosáhnout takových rozměrů, že se parsery mohou stát jak z hlediska časové, tak prostorové složitosti nepoužitelnými.

V této části se budeme věnovat tomu, jak lze udržet rozsah seznamu úspěšných rozkladů v rozumných mezích. V úvahu přicházejí dva způsoby.

Prvním z nich je omezování počtu derivací ve struktuře LOS. Pro tento účel jsme již připravili celou sadu konstruktorů.

Největší skupinu tvoří mutátory, které ořezávají strukturu LOS pouze v závislosti na pořadí derivací v seznamu. Spoléhají přitom na konvenci, dle níž se maximální derivace nachází v hlavě seznamu a zpravidla tomu tak skutečně je. Patří sem mutátor <> a především zkracující kombinátory alternativní kompozice z předchozí části.

Poněkud větší kontrolu nad tím, které derivace odstraňujeme, nám poskytuje mutátor whole. Klade na derivace podmínku zpracování celého vstupního textu. Jeho nevýhodou je však to, že jej není možné používat v průběhu výpočtu, ale až po rozkladu celého vstupu. Slouží tedy pouze pro dodatečné odstranění nepoužitelných derivací.

Nyní si představíme nový mutátor <?. S jeho pomocí již bude možné omezit přípustné derivace v seznamu úspěšných rozkladů v závislosti na vlastnostech samotného syntaktického stromu. Podle toho, zda bude derivace splňovat danou podmínku, bude buď ve struktuře LOS ponechána nebo z ní odstraněna. Mutátor definujeme rovněž jako infixní operátor:

<?(P,Cond,I+FL):-
        I+L :-> P,
        filter(sieve(Cond),L,FL).

sieve(Cond,_>R):- :-@ [Cond,R].

Nejdříve je na vstup aplikován parser $P$. Potom jsou ze seznamu úspěšných rozkladů odstraněny derivace, jejichž výsledek nesplňuje podmínku $Cond$. Můžeme tak analyzovat syntaktické stromy i na úrovni sémantické analýzy.

Již jsme si také představili konstruktory, jenž umožňují odstraňovat ze syntaktických stromů symboly ztrácející po rozkladu smysl -- jako závorky či separátory.

Jádro těchto konstruktorů tvoří kombinátory <& a &>. Na jejich základě jsme připravili nové kombinátory pro konkrétní případy jako enclosedIn či separatedBy.

Dalším zástupcem této skupiny kombinátorů je nestedIn. Umožňuje analyzovat strukturu vnořených bloků s možností aplikace sémantických operací na výsledky. Lze tak například zachytit strukturu přijímaného textu ve formě nějaké stromové datové struktury s možností přímo provést určitý druh výpočtu:

nestedIn(P-F-C,Open and Close,W):-
 W :->
       ((Open &>
                (P <: (P-F-C nestedIn Open and Close) )<+>
                <& Close)
           <&>> ( (P <: (P-F-C nestedIn Open and Close) )<+>
                  <: return(C))
       ) <@ F.

Oblast jeho použití je poměrně rozsáhlá. Pro demonstraci si jej představíme při zpracování pseudo kódu procedurálního jazyka typu C resp. Java. Zde je možné vytvářet bloky kódu s lokální platností deklarací. Pro jednoduchost nahradíme příkaz jazyka tokenem "c;".

fooNestedBlocks(W):-
  W :->
        ((#>tokenA("c;")<#)-funNB-nil
          nestedIn
           symbol("{") and symbol("}")).

funNB(A>B,nest(A,B)).

Samozřejmě lze snadno parser upravit pro konkrétní použití. Parser fooNestedBlocks je schopen zpracovat vnořenou strukturu bloků a vydat nám její strukturovanou reprezentaci. Příkladem takového vstupu je:

{
 c;
 {
  c;
  { c; }
  c;
 }
}
c;
{
 c;
}

fooNestedBlocks ukládá elementy na jedné úrovni do seznamu a vnořené bloky reprezentuje pomocí struktury nest:

?- s("{c;{c;{c;}c;}}c;{c;}")+L :-> fooNestedBlocks(I+L).
L= [s([])>
    nest([c;, nest([c;, nest([c;], [c;])], nil)], 
         [c;, nest([c;], nil)])]
Yes

Vzhledem k možnosti parametrizace parseru nestedIn jej lze snadno použít tak, že bude zpracovávat vytvořený syntaktický strom. V následujícím příkladu se počítá hloubka vnořených bloků:

  W :->
        ((token("c;") <@ const(0))-funNBDepth-[0]
          nestedIn
           symbol("{") and symbol("}")).

funNBDepth(A>B,X):-
        maxList(A,MA), maxList(B,MB), max3(MA,MB,M), X is M+1.
maxList([H|T],Max):- foldL(max3,H,T,Max).

Místo struktury je vydáváno číslo odpovídající hloubce daného bloku. Příkaz má iniciální hloubku 0 a s každou další úrovní se tato hodnota inkrementuje. Výstupem parseru je pak maximální počet úrovní vnořených bloků:

?- s("{c;{c;{c;}c;}}c;{c;}")+L :-> fooNestedBlocksDepth(I+L).
L= [s([])>3]
Yes

Tuto část zakončíme ukázkou použití kombinátoru nestedIn v parseru vnořeného komentáře. Z mnoha variant, které se vyskytují v různých programovacích jazycích, si vybereme komentář jazyka Pascal:

pascalNestedComment(W):-
 W :-> brace(nonSymbols("{}")<*>
              &>
             nonSymbols("{}")-const(comment)-nil
              nestedIn
               symbol("{") and symbol("}")<?@>comment-id).

První úroveň komentáře je ošetřena kombinátorem brace. Další vnořené bloky jsou již analyzovány pomocí nestedIn. Struktura komentáře se do výsledku parseru neukládá a v průběhu výpočtu je na každé úrovni vydáván pouze atom comment -- ten je také výslednou hodnotou celého rozkladu:

?- s("{ 
|      This 
|       {
|        is
|       } 
|       { nested {comment}}!
|     } 
|     clrscr;")+L
|       :-> pascalNestedComment.
L= [s(" clrscr;")>comment]
Yes