Konstruktory parserů

Tato kapitola je prvním seznámením s kombinátorovým přístupem konstrukce parserů. Naším hlavním cílem bude představení základních myšlenek a zavedení důležitých pojmů.

Jak bylo zmíněno v úvodu, přípustná logická struktura vstupu parserů je definována gramatikou. Protože prakticky nejpoužívanější třídou gramatik jsou gramatiky bezkontextové, budeme věnovat pozornost především jim. Pro jejich reprezentaci je velmi často používána Backusova normální forma (Backus-Naurova forma), zkráceně BNF. Necháme se tedy touto notací vést při budování základu knihovny.

Gramatiky jsou v BNF vytvářeny pomocí operace řetězení a operace alternativy. Naším prvním cílem tedy bude vytvoření potřebných kombinátorů parserů, které budou odpovídat výše uvedeným operacím.

Nemalou pozornost věnujeme také způsobu zápisu parserů. Pokusíme se o to, aby měl co možná nejblíže k deklarativní notaci gramatik. Naše úsilí bude směřovat k tomu, aby například pravidlu gramatiky zapsanému v BNF jako:

$<expr> ::= <term> <addop> <fact> \vert <fact>$

odpovídal následující zdrojový kód parseru:

 expr(W):- 
  W :->     term <&> addop <&> fact <:> fact.

Dosáhneme toho vhodným návrhem knihovny a využitím prostředků, které nám náš implemetační jazyk poskytuje.

V první části této kapitoly navrhneme vhodné rozhraní parserů, v další vytvoříme stavební kameny -- primitivní parsery a nakonec si ukážeme první zástupce kombinátorů nejen pro operace používané v BNF.