Pro a proti

V této kapitole se pokusíme o shrnutí výhod a nevýhod kombinátorového vytváření parserů.

Hlavní přednosti metody a vylepšení, kterých bylo dosaženo v rámci této práce, lze shrnout v následujících bodech:

Kombinátorové vytváření parserů má, především díky tomu, že je postaveno na programování vyššího řádu, online charakter; parsery lze vytvářet za běhu bez nutnosti konzultování kódu nových analyzátorů do interpretu, které je nezbytné u ostatních používaných metod, například u gramatik definitních klauzulí (DCG viz například Clocksin & Mellish [3]). Díky kolonám je navíc možné vytvářet za běhu i kód určený pro sémantickou analýzu prováděnou v rámci rozkladu.

Parsery vytvořené pomocí konstruktorů provádějí rozklad metodou analýzy s návratem. Jsou silnější než běžně používané metody, které se omezují pouze na jednoznačné gramatiky, protože umožňují analyzovat inherentně nejednoznačné jazyky. Nedeterministické parsery jsou zpravidla menší než parsery deterministické, ale méně efektivní -- analýza s návratem je časově náročná a kromě toho je zdrojem komplikací, pokud na ni navazuje analýza sémantická.

I při použití nedeterministických parserů lze dosáhnout relativně uspokojivých výsledků, protože lze libovolný parser vytvořený z knihovních konstruktorů spustit v pseudodeterministickém módu umožňujícím použití výhledů pro zefektivnění rozkladu. Takový parser může být vytvořen poměrně snadno, protože se programátor nemusí zabývat řešením problémů, které nastávají při výskytu kolizí v kódu parseru deterministického.

Parsery lze snadno vytvářet pomocí připravené sady konstruktorů.

Díky poměrně silné podpoře zavádění uživatelských operátorů v jazyce Prolog se podařilo dosáhnout přirozeného a čitelného zápisu kódu parserů, který umožňuje jejich snadnou modifikovatelnost. Způsob zápisu je velmi blízký notaci gramatik, takže může do určité míry nahradit jejich roli při popisu zpracovávaného jazyka. Navíc je tento popis zárověň funkčním analyzátorem.

Nahrazením backtrackingu seznamem úspěšných rozkladů se podařilo dosáhnout lepší časové složitosti, protože tak bylo odstraněno navracení způsobené výběrem nesprávné cesty při rozkladu.

Připravené módy a ladící systém, jehož součástí je také metainterpret, usnadňuje efektivní vyhledávání a odstraňování chyb z parserů

Pomocí módů se podařilo dosáhnout toho, že lze analyzovat jazyky generované LL(1) gramatikami algoritmem deterministické syntaktické analýzy.

Díky blízkému vztahu kombinátorů a gramatik lze aplikovat množství transformací, které byly původně určeny pro gramatiky, na knihovní parsery. Navíc lze tyto transformace zabudovat přímo do definic konstruktorů, aby se jimi tvůrce parserů nemusel zabývat.

Vzhledem k tomu, že jsou parsery vytvářeny ručně, lze získat větší kontrolu nad procesem rozkladu vstupního textu. Díky tomu lze řešit různé podúlohy rozkladu vhodnou metodou případ od případu místo použití obecného algoritmu. Příkladem může být implementace zotavovacích strategií při výskytu chyby ve vstupním textu v módech ll1/4 a pseudoll1/4, kterou je možné provést konkrétně pro danou syntaktickou konstrukci, ve které nastala a dosáhnout tak větší účinnosti, než kdyby byla použita nějaká univerzální strategie aplikovaná ve všech případech.

Použití parserů vytvořených pomocí knihovny umožňuje zavedení uživatelsky definované syntaxe do prologovských programů (uživatelsky přívětivý formát vstupu programů, konfigurační soubory, ...) a snadnější psaní textových aplikací. Uplatnění mohou nalézt, díky lehkosti s jakou je lze vytvářet, při importu dat a textové komunikaci mezi různými aplikacemi a Prologem nebo při unifikaci zdrojů, jejímž příkladem může být použití při zpracování zdrojů textové povahy na Internetu. Lze je také použít v prototypovacím systému, což je oblast ve které je Prolog často nasazován.

Pokusme se ještě o srovnání generátorů a konstruktorů parserů. Množina kombinátorů, kterou nabízí formální systém pro popis přijímaného jazyka v generátorech, je zpravidla pevně dána, zatímco v konstruktorech parserů lze tuto množinu libovolně rozšiřovat. Díky tomu lze parsery vytvářet rychleji, neboť jsou k dispozici konstruktory pro typické syntaktické kostrukce a není tedy nutné vytvářet množství různých, ale velmi podobných definic. Popis vstupního jazyka je zde hutnější a srozumitelnější.

Na druhou stranu generátory zpravidla provádějí při vytváření parseru analýzu, která následně umožňuje provádět rozklad velmi efektivně. To u konstruktorů není možné, protože fáze specifikace je zároveň fází vytváření parseru -- případná analýza tedy musí být prováděna online.

Nevýhody:

Metoda kombinátorového vytváření parserů pochází ze světa funkcionálního programování, kde se osvědčila v lazy funkcionálních jazycích. Vzhledem k rozhodnutí použít seznam úspěšných rozkladů pro uchovávání výsledků bylo nutné se vyrovnat s důsledky přechodu do jazyka s early povahou, kterým Prolog je. Za účelem řešení vzniklých problémů bylo představeno množství různě účinných technik ořezávání struktury LOS. Chování, které bylo ve světě lazy funkcionálních jazyků zadarmo -- zde muselo být implementováno, což může být za určitých okolností příčinou ztráty efektivity.

Víceméně podobným problémem je i programování vyššího řádu, na kterém metoda stojí. Protože jeho podpora zatím není standardní součástí jazyka Prolog (ve většině moderních interpretů se ale v nějaké formě nachází) situace musela být řešena vlastní implementací. Protože jsme chtěli, aby si knihovna zachovala nezávislost na konkrétním interpretu, byla do implementačního jazyka přidána dodatečně a to samozřejmě za cenu určité režie, na rozdíl od situace, kdy by byla jeho integrální součástí. Nicméně použité řešení umožňuje ušít ji na míru danému interpretu takovým způsobem, že kód který zprostředkovává jednotné rozhraní může být snadno v implementaci jazyka Prolog s kvalitním překladačem vyoptimalizován již při zavádění programu.

Prolog se hodí především pro zpracování krátkých vstupů s velmi nejednoznačnou gramatikou (přirozený jazyk). Při analýze umělých jazyků je však situace přesně opačná -- zpracovávány jsou dlouhé vstupy s gramatikami, které jsou deterministické.

S tím souvisí i způsob reprezentace vstupního textu^9.1v interpretech, který obvykle není příliš efektivní. Tento problém se částečně podařilo vyřešit zavedením módů umožňujících přijímání vstupu i z jiných zdrojů (soubory viz ).

Pro praktickou použitelnost parseru má zásadní význam, aby pracoval pokud možno v lineárním čase a prostoru. Toho se podařilo dosáhnout pro LL(1) gramatiky -- odpovídá to výpočetní strategii Prologu. Současným standardem jsou však LALR(1) analyzátory, které pokrývají výrazně větší část bezkontextových jazyků než LL(1). Tyto analyzátory provádějí rozklad algoritmem syntaktické analýzy opačně než kombinátorové parsery -- tedy zdola nahoru.

Jak plyne z této kapitoly, má vytváření parserů pomocí knihovny konstruktorů parserů řadu specifik. O tom, zda je knihovna vhodná pro řešení dané úlohy, se lze rozhodnout třeba na základě výše uvedeného hodnocení.