Weblog @ rebex.cz

Dělal jsem teď v C# jakési úpravy SQL vyžadující jeho parsování, a zadavatel navrhl použít ANTLR. Osobně mám po několika pokusech s Bisonem ke generátorům kódu vztah stále neujasněný. Programovat na vyšší úrovni je jistě fajn, ale když má pak člověk v gramatice chybu - což se mi stává s nepříjemnou pravidelností - komplikují extra úrovně abstrakce debugování a generátor, netriviální program třetí strany, je spolehlivým zdrojem opravdu netriviálních problémů. Musím nicméně uznat, že od dřevních dob jaků a bizonů udělala parsovací technologie podstatný pokrok a ANTLR je nástroj rozhodně mocný.

Pokrok má samozřejmě i své stinné stránky. Jak se ANTLR bouřlivě vyvíjí - nová velká verze 3.0 byla uvolněna letos v květnu - dokumentace se poněkud opozdila (s důležitou vyjímkou tištěné Definitivní Reference, jejíž užitečnost, nekoupiv, nemohu posoudit), a i bez dokumentace je vidět, že ANTLR není bez kazu... Jiné mé stížnosti do mailing listu se setkaly z hrobovým tichem, takže nelze vyloučit, že problém byl mezi mou klávesnicí a židlí, ale obecně i autor soudí, že netrpělivě očekávaná verze 3.1, napsaná v ANTRL 3.x - verze 3.0 je ještě pořád v ANTLR 2 - bude pro některé gramatiky generovat maličko jiné jazyky než 3.0.

Co se těch gramatik týče, ANTLR na rozdíl od YACCu derivuje pravidla zleva, jako typický ručně psaný rekurzivní parser, takže pravidla pro ANTLR nesmějí být zleva rekurzivní. Pro YACC běžné konstrukce jako

item_list
	: item
        | item_list ',' item
        ;

expr
	: expr '+' subexpr
	| subexpr
	;


subexpr
	: subexpr '*' term
	| term
	;

term
	: '(' expr ')'
	| id
	;

item_list
	: item ( ',' item )*
        ;

expr
	: subexpr ( '+' subexpr )*
	;


subexpr
	: term ( '*' term )*
	;

term
	: '(' expr ')'
	| id
	;

Syntax opakování - ANTLR má ()*, ()+ i ()?, přičemž znak za závorkou má stejný význam jako kvantifikátor regulárního výrazu - je ještě celkem mechanická změna. Hlubší problém představují gramatiky parsovatelné YACCem (LALR, pro akademicky orientované čtenáře), které nelze parsovat shora dolů s žádným konečným lookaheadem (jsou mimo LL(k)). Takové gramatiky nejsou nijak vyjímečné - LR parsery, redukující vstup zdola nahoru, jsou silnější než LL v tom smyslu, že mohou udržovat stav zahrnující více pravidel pro dlouhý úsek vstupu, dokud ho jednoznačný token nerozsekne.

ANTLR toto omezení řeší tzv. syntaktickými predikáty, což je z mého primitivního pohledu prostě syntax pro parsování metodou pokusu a omylu. Např. jedno z pravidel (gramatiky původně pro ANTLR 2.7.2) parsování podmínek v SQL je

subSearchCondition
      :
	( NOT )? (
		(bracketedSearchCondition) =>
			bracketedSearchCondition
		| predicate
	;

V jistém smyslu jednodušším příkladem syntaktického predikátu je parsování tradiční konstrukce if then else, známé svou nejednoznačností: else následující po několika vnořených if může technicky patřit ke kterémukoli z nich, a jazyky s if musí pro rozhodnutí tohoto případu specifikovat nějaké extra pravidlo, typicky že každé else patří k nejbližšímu kandidátovi. V syntaxi ANTLR (z tutorialu původně pro ANTLR 2.7.2):

ifStatement
	: 'if' '(' expression
		')' statement
			( ( 'else' ) => 'else' statement )?
	;

Pro ladění gramatik existuje sofistikované GUI, ANTLRWorks, které má ovšem z mého hlediska zásadní nevýhodu: podporuje pouze Javu, rodnou platformu ANTLR. Pro celkový projekt to není až takový problém - javovská třída generátoru se dá spustit z příkazové řádky, začlenění generovaného kódu do spustitelného programu je popsáno v online dokumentaci a build se dá automatizovat pro NAnt, ale interaktivní debugger se do takového postroje cpe špatně, takže většinu gramatik jsem testoval přidáním akcí a spuštěním testovacího programu.

ifStatement
@init { string curExpr = null; }
	: 'if' '(' e = expression {
			curExpr = $e.returnValue;
		} ')' statement {
			Console.WriteLine("then of {0}", curExpr);
		} ( ( 'else' ) => 'else' statement {
			Console.WriteLine("else of {0}", curExpr);
		} )?
	;

Akce jsou psány zhruba v tom programovacím jazyce, který ANTLR generuje - kromě Javy je podporováno i C#, C a další. Kód akce není zkopírován do výstupu generátoru zcela beze změn, nýbrž je interpretován jako šablona pro knihovnu StringTemplate, která ho integruje s generovaným parserem, tj. hlavně nahrazuje jména začínající '$' skutečnými vnitřními proměnnými parseru. Blok @init je užitečný pro lokální deklarace: ANTLR ho umisťuje na začátek funkce implementující specifikované pravidlo a garantuje, že se v průběhu parsování odpovídající části vstupu vykoná právě jednou - což pro kód akcí přirozeně neplatí.

V příkladu nahoře je proměnná e automaticky deklarována jako lokální proměnná metody ifStatement, s typem vraceným metodou expression. Generované metody defaultně nevracejí nic co bych chtěl zpracovávat (buď void, nebo interní typy, podle stylu gramatiky), ale je možné přidat specifické hodnoty - např. expression použitá výše má deklarovaný atribut returnValue, který se nastavuje v jejích akcích:

expression returns [ string returnValue ]
	: Number { $returnValue = $Number.text; }
	| Identifier { $returnValue = $Identifier.text; }
	;

Pravidla lexeru takto dekorovat nelze - vracejí vždy instanci třídy Token, mezi jejíž standardní atributy patří zejména text (v C#; Java má metody getText() a setText()).

Semantické rozdíly lexeru a parseru jsou vůbec mnohem podstatnější, než by naivní uživatel mohl soudit z jejich analogické syntaxe. Patrně nejzásadnějším je, že pravidla lexeru nemají hierarchii - kdykoli lexer rozezná na vstupu token, zahrne do něj co nejvíc znaků a je mu jedno, je-li výsledek z hlediska parseru platný nebo ne. V jednoduchých případech - např. pro tokeny '<', '<=' a '=' - je nejdelší možný token správně, ale často je nutné nastavit ho ručně v akci, např.

fragment
Digit : '0'..'9' ;

fragment
Integer :;

fragment
Real :;

Number :
	'.' { $type = '.'; } ( (Digit)+ { $type = Real; } )?
	| (Digit)+ { $type = Integer; } ( '.' (Digit)* { $type = Real; } )?
	;

A to je snad všechno, co člověk potřebuje, aby mohl ze vstupního kódu udělat tradiční AST - byť samozřejmě zdaleka ne všechno co ANTLR umí. Jen namátkou, má semantické predikáty, stav sdílený mezi pravidly, dvoudimenzionální parsování stromovými gramatikami a spoustu dalších vymožeností, jejichž systematický popis zabral knihu - kdybych s ním měl začít znova, nehledal bych dokumentaci po blozích, ale šel bych ke kováři a investoval padesát dolarů do primárního zdroje...