Deterministické konstruktory parserů

Existuje mnoho různých metod syntaktické analýzy. Kombinátory parserů pracují vzhledem ke způsobu své implementace v jazyce Prolog a jeho výpočetní strategii algoritmem syntaktické analýzy shora dolů.^C.1Terminálním symbolům gramatiky analyzovaného jazyka odpovídají parsery terminálních symbolů (jako symbol a token) a neterminálním parsery vytvořené pomocí konstruktorů.

Při analýze shora dolů se buduje derivační strom. Začíná se od počátečního symbolu gramatiky (kořene derivačního stromu) a postupně jsou doplňovány jeho hrany a uzly směrem shora dolů tj. od kořenového uzlu k uzlům listovým.

Derivace se vyznačují tím, že při každém kroku nahrazují nejlevější neterminální symbol ve větné formě (sentenci s neterminály). Takové derivace se nazývají levé derivace.

Při analýze tedy vždy nahrazujeme nejlevější neterminální symbol pravou stranou pravidla (je volán parser neterminálního symbolu stojící v sekvenční kompozici nejvíce vlevo). Pravých stran může existovat několik -- množina pravidel se stejným neterminálním symbolem na levé straně odpovídá v kombinátorech parserů alternativní kompozici parserů vytvořených dle jejich pravých stran.

Základní problém spočívá ve výběru pravidla pro náhradu aktuálního symbolu (tj. ve výběru alternativy). Při řešení tohoto problému přicházejí v úvahu následující přístupy:

1. Tradiční kombinátory parserů^C.2
   Provést výběr jednoho pravidla. Ukáže-li se později, že výběr nebyl správný, je třeba proces analýzy vrátit a vybrat pravidlo jiné. Tento postup se nazývá analýza s návratem čili backtracking.

   Přestože je počet návratů omezen, je zřejmé, že analýza s návratem je časově náročná a kromě toho je zdrojem komplikací při dalších fázích zpracování vstupu (např. v překladačích plnění tabulek symbolů apod. nelze odestát).

2. Deterministické kombinátory parserů^C.3
   Provést výběr správné alternativy na základě doplňujících informací získaných v průběhu dosavadní analýzy a podle toho, v jakém kontextu je náhrada neterminálního symbolu prováděna.

   Tento typ analýzy se nazývá deterministická syntaktická analýza. Její nevýhodou je, že ji nelze použít pro všechny bezkontextové gramatiky.

Bezkontextové jazyky, které lze analyzovat pomocí deterministických analyzátorů se nazývají deterministické bezkontextové jazyky a tvoří jejich zajímavou podmnožinu z hlediska praktického použití. Výše popsané gramatiky se nazývají LL() protože čtou vstupní řetězec zleva doprava, vytvářejí levý rozklad a přitom používají informaci o nejbližších symbolech.

Uveďme několik nejdůležitějších vlastností deterministických jazyků:

Efektivnost rozkladu.

Pro libovolný deterministický bezkontextový jazyk lze sestrojit syntaktický analyzátor pracující v lineárním čase s lineárním paměťovým prostorem.

Snadná lokalizace chyb.

Protože deteterministický syntaktický analyzátor pracuje bez návratů, může určit poměrně jednoduše místo chyby -- je nalezena přesně ve chvíli, kdy se objeví.

U syntaktické analýzy s návratem tomu tak není -- díky navracení nelze příčinu neúspěchu jednoznačně určit. Navracení totiž nastává buď při výskytu chyby nebo při testování špatné větve výpočtu a tyto situace nelze jednoznačně odlišit.

Snadné napojení následného zpracování.

Typickým příkladem využití této vlastnosti jsou již zmíněné překladače. Neexistují zde problémy s odebíráním získaných tokenů z tabulek symbolů a podobně. Zároveň lze některé části sémantické analýzy včlenit přímo do syntaktického analyzátoru a obě fáze do jisté míry spojit.

Automatizovatelnost.

Analyzátory lze vytvářet pomocí standardních algoritmů, které vytvářejí rozkladové tabulky.

Až dosud jsme vytvářeli pomocí konstruktorů parsery, které prováděly analýzu vstupního textu nedeterministicky. Tento způsob má dvě hlavní výhody:

• Parsery je možné konstruovat rychle a není nutné se zabývat jejich analýzou, ani případnými komplikacemi při výpočtu (pokud nejsou např. příčinou zacyklení). Z hlediska ručního vytváření je to bezpochyby pohodlnější cesta.
• Nedeterministický parser je zpravidla menší než parser deterministický. Cenou za rychlý parser mohou být výrazně větší požadavky na prostor, ve kterém je kód parseru uložen.

Nevýhody nedeterministického způsobu analýzy jsou všeobecně známé -- obecně nesrovnatelně větší prostorová, ale především časová složitost. Proto má nepochybně smysl, aby jsme se deterministickými parsery zabývali i v této práci. Naším cílem bude nejen umožnit, ale navíc také usnadnit programátorovi jejich vytváření. Na rozdíl od běžně používaných postupů v nástrojích pro generování parserů se bude většina analýzy, která bývá prováděna offline provádět online -- tedy v průběhu rozkladu. Důvodem je samozřejmě ruční konstrukce parserů.

V centru našeho zájmu budou analyzátory pracující algoritmem shora dolů -- konkrétně analyzátory LL(1) jazyků.