Next: Úmluvy značení Up: Kombinátory parserů Previous: Kombinátory parserů Obsah Index
Vlastnost, která má z hlediska jejich praktického používání největší význam, je možnost jejich efektivního a zároveň srozumitelného popisu. Jedním z prostředků, který umožňuje dostatečně přesný popis všech jazykových konstrukcí jazyka, konkrétně všech jeho syntaktických struktur, je gramatika.
V rámci teoretického zkoumání gramatik a jazyků byly tyto rozděleny do tříd a ukázalo se, že pro jednotlivé třídy gramatik existují třídy automatů tak, že pro danou gramatiku lze sestrojit automat, který popisuje stejný jazyk. Z hlediska praktické použitelnosti mají největší význam bezkontextové jazyky -- jazyky generované gramatikami typu 2 v Chomského hierarchii, a proto se budeme věnovat především jim.
Gramatika je deklarativní popise jazyka. Pro jeho zpracování se obvykle používá vhodnější procedurální popis ve formě automatu. Vztah mezi automaty a gramatikami pak umožňuje pro danou gramatiku sestrojit automat provádějící syntaktickou analýzu jazyka, jenž generuje -- parser.
Parser je program, jehož vstupem je lineární text. Úkolem parseru je provést jeho analýzu -- lexikální a syntaktický rozklad na jednotlivé komponenty a jejich syntézu. Výsledek své práce vydává parser ve formě vhodné datové struktury reprezentující strukturu daného textu, kterou je zpravidla jistá forma syntaktického stromu.
Parsery jsou obvykle vytvářeny buď pomocí automatizovaných konstruktorů nebo ručně. V prvním případě tvůrce parseru používá deklarativní popis jazyka, zatímco při ručním vytváření popis procedurální. U obou přístupů je práce na straně programátora prakticky stejná, liší se však ve způsobu, jímž je získán funkční parser.
Při teoretickém zkoumání struktury problému vytváření konstruktorů parserů bezkontextových jazyků bylo pro jejich část již dosaženo takových výsledků, že na základě známých podkladů je v současné době napsání programu pro tento účel rutinní záležitostí nevyžadující již téměř žádné programátorské invence. Také proto je zpravidla používán první z výše uvedených způsobů -- parsery jsou konstruovány pomocí speciálních nástrojů obvykle nazývaných generátory parserů. Ve světě imperativních programovacích jazyků je asi nejznámějším a rovněž nejpoužívanějším programem bison, jenž společně s generátorem lexikálních analyzátorů flex tvoří velmi silný nástroj.
Také ve funkcionálním programování se můžeme setkat s množstvím generátorů parserů. Za všechny jmenujme alespoň Ratatosk [16], Happy [17] a ml-lex/ml-yacc [].
Druhou možností, jak lze parsery konstruovat, je jejich ruční vytváření. Téměř každý, kdo používá rekurzivní techniky při programování v imperativních jazycích, se někdy setkal s programátorskou technikou nazývanou recursive descent parsing. Je to metoda syntaktické analýzy provádějící rozklad vstupního textu shora dolů pomocí množiny rekurzivních procedur. S každým neterminálním symbolem gramatiky je pak asociována procedura a způsob vzájemného volání jednotlivých procedur je dán samotnou gramatikou.
Do této kategorie lze zařadit také způsob vytváření parserů, který si získal všeobecnou oblibu v lazy funkcionálních jazycích. Parsery jsou zde modelovány velmi přirozeně přímo jako funkce. Větší parsery jsou vytvářeny po částech z parserů menších pomocí funkcionálů. Tyto funkce vyššího řádu jsou zde obvykle nazývány kombinátory parserů. Kombinátorový rozklad je v mnoha směrech silnější než běžně používané metody. Umožňuje pracovat s nejednoznačnými gramatikami s možností backtrackingu v případech, které si to vyžadují -- ovšem se všemi důsledky na efektivitu takto provedeného parsingu. Vytváření parserů tímto způsobem je velmi rychlé a navíc je výsledný zdrojový text snadno pochopitelný a modifikovatelný.
Dobrým úvodem do kombinátorového vytváření parserů je Hutton [6]
a Fokker [4], použití funkcionálních monád je celkem podrobně
rozebráno v Hutton & Meijer [7] a deterministickým
kombinátorům je věnována práce Swierstra & Duponcheel [14].
Diplomová práce představuje výše zmíněné kombinátory parserů jako elegantní techniku pro vytváření parserů. Budeme se věnovat přenesení této myšlenky do jazyka Prolog, který je nejrozšířenějším jazykem logického programování. Vyjdeme přitom ze základu položeného v práci Hric [5]. Hlavním cílem této práce bude vytvoření knihovny parserů a jejich konstruktorů, která by umožňovala tvorbu syntaktických analyzátorů určených především pro zpracování umělých jazyků. Pokusíme se také navrhnout lepší syntaxi pro podporu programování vyššího řádu a přenést další techniky, jež se osvědčily ve světě funkcionálního programování.
Předloženou práci je možno zhruba rozdělit do pěti částí. První část tvoří kapitola 1 věnovaná programování vyššího řádu -- přehlednému a úspornému programátorskému stylu, na jehož základě byla knihovna vytvořena. V této části jsou též vytvořeny prakticky použitelné predikáty převzaté z funkcionálního programování. Kapitola 2 představuje jádro knihovny, jímž jsou kombinátory, mutátory a generátory parserů. V třetí části, která se skládá z kapitol 3, 4 a 5, jsou vytvořeny konstruktory parserů pro typické úlohy syntaktické analýzy. Kapitola 6 a 7 se věnuje módům parserů a jejich hlavní aplikaci, kterou jsou deterministické konstruktory parserů. A konečně kapitola 8 ukazuje na dvou praktických úlohách použití knihovny. V přílohách je k dispozici dokumentace ladícího nástroje a přehled definovaných operátorů.
Nedílnou součástí diplomové práce je implementace knihovny, její referenční příručka a ukázkové programy v elektronické podobě.
Ve fragmentech zdrojových kódů v textu práce je kladen důraz spíše na eleganci -- naopak knihovna samotná je implementována se snahou o co největší efektivitu, a proto si v některých případech tuto eleganci nezachovává. Vnitřní definice predikátů v textu práce a v kódu knihovny se tak v některých případech liší, jejich rozhraní je však identické.