Rozhraní parserů

Dříve než se pustíme do vytváření prvních parserů, navrhneme obecný tvar prologovského predikátu, kterým budou realizovány. Nejprve se zamyslíme nad použitím datových struktur pro vstup a výstup. Při návrhu samotného obecného tvaru predikátu zohledníme, které syntaktické varianty nám mohou usnadnit implementaci, nebo dokonce umožnit provádění některých optimalizací.

Vstupem parseru je lineární text. Ten může být reprezentován různými způsoby. Pro řešení naší úlohy potřebujeme, aby zvolený způsob reprezentace umožňoval následující tři operace:

1. Získání první položky.
2. Operaci posunu.
3. Rozpoznání konce vstupu.

V našem případě přicházejí v úvahu dvě reprezentace vyhovující takovým podmínkám. První z nich je prologovský seznam a druhou soubor.

Asi nejpřirozenější datovou strukturou jazyka Prolog, umožňující výše uvedené operace, je řetězec. Jak známo, prologovským řetězcem se rozumí posloupnost znaků, které jsou reprezentovány jako seznam číselných hodnot ASCII.

Získání první položky vstupu odpovídá získání hodnoty v hlavě seznamu. Posun umožňují operace nad tělem seznamu a prázdný seznam značí konec vstupu.

Jak bylo uvedeno, další vhodnou reprezentací je soubor. Získání první položky je možné pomocí jejího načtení, posun lze provést operací seek a rozpoznání konce vstupního textu odpovídá konci souboru.

Architektura knihovny kombinátorů parserů umožňuje jak práci se soubory, tak s prologovskými řetězci. Použití souborů se budeme věnovat v kapitole . Při počátečním seznámení bude pro svou názornost vhodnější forma prologovského řetězce.

Vstupní text ve formě prologovského řetězce bude ukládán do struktury s/1, aby bylo možné od sebe vzájemně odlišit jednotlivé reprezentace.

A nyní již přistupme k samotnému návrhu rozhraní parserů. Realizací triviálního akceptoru by mohl být predikát s jediným argumentem Input, který by obsahoval právě vstupní text. Predikát by uspěl, pokud by se rozklad podařil a v opačném případě by selhal. Od parseru se však očekává více. Chceme, aby výsledek provedené analýzy vydal ve formě vhodné datové struktury, jakou je například syntaktický či derivační strom. Pro tento účel poslouží výstupní argument Result. Použití právě navrženého rozhraní: $parser(+Input, -Result)$ ukazuje následující příklad:

?- parseDigit(s("111th"), Result).
Result = 1
Yes

Z příkladu je vidět závada takového návrhu. Byl by totiž použitelný pouze pro parsery zpracovávající celý vstup. Aby bylo možné pokračovat v rozkladu, musíme mít přístup ke zbytku vstupního řetězce, který se nepodařilo parseru zpracovat. Jedině tak umožníme, aby parsery na sebe mohly navazovat. Nezavedeme však do predikátu další argument, ale spojíme nezpracovaný zbytek pomocí operátoru >/2 s výsledkem a vytvoříme tak term. Pro term NotParsedRest>Result bude v následujícím textu používán termín derivace. Takovou derivací je term "37">1 z následujícího příkladu:

?- parseDigit(s("137"), D).
D = s("37")>1
Yes

Parsery tohoto typu by nám postačovaly pouze v případech, kdy je možné provést rozklad právě jedním způsobem -- například při analýze deterministických jazyků. V centru našeho zájmu však budou jazyky s nejednoznačně definovanými sentencemi -- slovy jazyka, pro které existuje více různých derivací charakterizovaných odpovídajícím počtem různých derivačních stromů. Parser by tedy měl nějakým způsobem předat na výstup všechny takové derivace. V úvahu přicházejí dvě možnosti. První z nich je použití mechanismu navracení, který je základním a velmi mocným prostředkem jazyka Prolog. V našem případě je však výhodnější shromáždit všechna řešení rozkladu v jedné datové struktuře. Ve světě funkcionálního programování je zvykem takovou explicitní datovou strukturu nazývat list of successes -- tedy seznam úspěšných rozkladů. V dalším textu pro něj budeme používat zkratku LOS. Seznam úspěšných rozkladů lze schematicky znázornit následovně: $[Rest_{1}>Result_{1}, \dots, Rest_{n}>Result_{n}]$ kde $Rest_{i}$ je nezpracovaný zbytek vstupu a $Result_{i}$ výsledek rozkladu. Použití si ukažme na příkladu parseru, který přijímá přirozená čísla:

?- parseNatural(s("76th"), LOS).
LOS = [s("th") > 76,  s("6th") > 7]
Yes

V ukázce existují dva správné rozklady, které mohou být obecně vydány v různém pořadí. Aby jsme se vyhnuli nejednoznačnostem, zavedeme konvenci, ve které se řešení řadí ve struktuře LOS podle toho, jakou část vstupního textu byla zpracována. Maximální derivace se tedy zpravidla nachází v hlavě seznamu úspěšných rozkladů.

Ještě stále však není důvod ke spokojenosti. V následujícím textu se ukáže, že je nevýhodné používat jeden argument pro vstupní text a druhý pro seznam úspěšných rozkladů. Proto opět vytvoříme z obou argumentů term -- tentokrát operátorem +/2. Nejenže spojení dvou argumentů v jeden term ušetří práci při psaní složitějších parserů, ale především umožní zefektivnit práci knihovních predikátů: $parser(+Input + -LOS)$ Nyní již přistupme k poslednímu, avšak neméně důležitému bodu návrhu rozhraní, kterým je umožnění parametrizace vytvářených parserů. Pro tento účel zvolme konvenci ve které argumenty parametrizující daný parser předcházejí vstupně/výstupnímu termu $Input+LOS$: $parser(+Arg_{1}, ..., +Arg_{n}, +Input + -LOS)$

Tímto posledním krokem jsme dokončili návrh rozhraní parserů. Dříve než se pustíme do vytváření konkrétních parserů poznamenávám, že pro zvýšení čitelnosti je navíc ve zdrojových textech pro názvy proměnných používána následující konvence:

$P$ 		...proměnná obsahující parser (Parser).

$I$ 		...vstupní text (Input).

$L$ 		...seznam úspěšných rozkladů (LOS).

$W$ 		...proměnná obsahující term $I+L$ (Wrapper).

$N$ 		...zbytek vstupu, který nebyl parserem zpracován (NotParsed).

$R$ 		...výsledek rozkladu (Result).