Problems presenting features of interest

ANTLR v základech softwarové komponenty

vbarta — Fri, 18 Jan 2008 12:17:00 GMT

Před pár měsíci jsem se tu šířil o generátoru parserů ANTLR a jeho použití při tvorbě front-endu transformujícího SQL do formátu vyžadovaného různými databázovými backendy (teoreticky je SQL standartizovaný jazyk, ovšem v praxi vidí prodejci databází příliš mnoho výhod v produktové diferenciaci, než aby standartizovali úplně všechno). Předchozí post se omezil na obecný přehled a první dojmy, ale jelikož jsem od doby jeho napsání zmiňovanou komponentu nejen úspěšně dokončil, ale dokonce ukecal zákazníka aby ji uvolnil jako Open Source, mám příležitost vrátit se k tématu podrobněji.

Komponenta se jmenuje MacroScope, a zvenčí se tváří jako víceméně obyčejný datový provider. Interně ovšem nepracuje přímo s databází, nýbrž deleguje na "opravdového" providera, a při té příležitosti přepisuje SQL specifikované aplikací tak, aby mu vnitřní provider rozumněl. Úpravy SQL jsou specifikovány nad jeho gramatikou ("Oracle nezná SELECT TOP, ale zato má funkci ROWNUM, pomocí které se dá zkonstruovat tentýž výsledek"), takže pro jejich implementaci je prakticky nezbytné SQL parsovat - a tam právě přišel ke slovu ANTLR.

Pro parsování SQL se ANTLR rozhodně osvědčil - už proto že je to úloha dost běžná, aby ji už někdo skoro udělal (pravda, pro starou verzi ANTLR, pouze SELECT a pouze pro MS SQL Server - MacroScope podporuje i Oracle a na zvláštní přání publika dokonce MS Access - ale pořád mnohem lepší než vynalézat kolo). Další velká výhoda formální gramatiky je dokumentační: podporovaná varianta SQL je přesně to co specifikuje soubor MacroScope.g. Popsat tu variantu slovně je fakticky dost obtížné - je to podmnožina definic INSERT, SELECT, UPDATE a DELETE v SQL 92, s přidanými nekompatibilními konstrukcemi z podporovaných backendů, takže když člověka zajímají detaily, řekněme jak napsat datum, je formální definice nezastupitelná:

MAccessDateTime :
	'#' Digit Digit Digit Digit '-'
		Digit Digit '-' Digit Digit ' '
		Digit Digit ':' Digit Digit ':' Digit Digit
		'#'
	;

Iso8601DateTime :
	Digit Digit Digit Digit '-'
		Digit Digit '-' Digit Digit ( 't' | ' ' )
		Digit Digit ':' Digit Digit ':' Digit Digit
	;

A je to jasné... Nad lexikálními pravidly buduje MacroScope objektový model, tj. např. pro to datum

educationalSimplification returns [ INode value ] :
	// subset of an MS Access-specific format
	| MAccessDateTime {
		$value = new LiteralDateTime($MAccessDateTime.text);
	}
	// subset of ISO 8601 recommended for SQL Server 2005
	| Iso8601DateTime {
		$value = new LiteralDateTime($Iso8601DateTime.text);
	}
	;

INode je základní interface definující protokol společný pro všechny podstromy SQL, od konstant až po kompletní příkaz. Protokol je to velmi prostý:

    public interface INode
    {
        INode Clone();

        void Traverse(IVisitor visitor);
    }
}

Veškeré transformace, včetně transformace stromu na řetězec, dělají Návštěvníci. Technicky by visitor mohl dělat i to klonování, ale rozhodl jsem se že než být purista, napíšu to radši srozumitelně. Testy na živých programátorech bylo zjištěno, že výsledný model je v zásadě použitelný pro automatizované úpravy SQL (typicky přidávání podmínek - je mnohem čistší, srozumitelnější a bezpečnější přidat objekt než hledat v řetězci "WHERE"), akorát je dost velký a uživatelé ne vždy vědí kterou třídu instancializovat - ale to už nemá s ANTLR moc společného...

Samozřejmě neexistuje jídlo zdarma a generátor kódu přináší kromě výhod i komplikace. Například takový build funguje pro jednoduché projekty úplně automaticky z IDE Visual Studia, ale s generováním kódu moc nepočítá. Visual Studio má jakési háky, ale logiku dodatečných kroků bych stejně musel programovat ručně v nějakém dalším jazyce, "podporované" .BAT soubory používat nebudu a NAnt nové uživatele zarazí IMHO méně než řekněme Perl. Kromě toho jsem stejně chtěl integrovat i unit testy používající NUnit, takže build komponenty dělá NAnt. Na druhé straně pro ruční práci s projektem (tj. hlavně debugování) má IDE Visual Studia své výhody, takže jsem se ho pokusil do buildu zahrnout: na nejvyšší úrovní je build kontrolován ručně psaným skriptem, ale všechny ostatní buildovací skripty jsou generované pomocí XSLT (NAnt na to má příkaz) z projektových souborů Visual Studia. Transformace bohužel není dost obecná aby se dala beze změn používat i v dalších projektech - vždycky se najde nějaký speciální případ, který je třeba hardcodovat - nicméně v rámci jednoho projektu je celkem stabilní. Tato organizace umožňuje používat IDE Visual Studia pro veškerý vývoj (včetně přidávání souborů do projektu) kromě změn gramatiky a spouštění unit testů. Celkem se osvědčila - největší nevýhodou je že po přidání souboru musím před spuštěním NAntu uložit projekt - a rozhodně ji zkusím i při dalších příležitostech.

Jak už jsem se zmiňoval v předchozím postu, ANTLR je živý projekt, bouřlivě se vyvíjí a není vždycky možné izolovat MacroScope od jeho nekompatibilních změn, jakkoli by to bylo žádoucí. Pro překlad existujících zdrojáků není ANTLR nezbytný (generovaný kód a binární verze ANTLR runtimu jsou součástí distribuce), ale jakékoli změny gramatiky vyžadují jeho instalaci - na Windows není automatická, ale na druhé straně na aplikaci v Javě to není tak hrozné. Co se cílové platformy týče, MacroScope jsem zkoušel na XP a Vistě, které celkem žádné problémy nedělaly. Pro frontend k mnoha databázím Windows CE asi není až tak zajímavou platformou, ale viděl jsem projekt na PDA, ve kterém by se ANTLR uplatnil, konkrétně pro parsování konfigurace obsahující jakési vzorečky. Takové projekty by ovšem vyžadovaly otestování a možná i úpravy ANTLR runtimu pro .NET CF, a jeho rekompilace z nových zdrojáků by skoro určitě nefungovala s ANTLR 3.01, což je poslední release ANTLR. Zdrojáky pro C# bohužel nejsou jeho součástí - nějak se u nich zrovna měnil maintainer, a identifikovat použitelnou verzi v repozitáři by byla pěkná otrava - takže na drastické úpravy asi bude lepší počkat na ANTLR 3.1, jehož release se očekává každým dnem. Podle toho co jsem z nové verze viděl, určitě bude obsahovat mnoho zajímavých změn.

ANTLR aneb jak nebýt jelen

vbarta — Sat, 01 Sep 2007 08:22:00 GMT

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
	;

jsou v ANTLRu ilegální a je nutné je přepsat na

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 próze "když se vstup dá parsovat jako ozávorkovaná podmínka, je to ozávorkovaná podmínka, jinak to musí být predikát". Mimochodem token NOT je token, protože začíná velkým písmenem. ANTLR generuje separátní lexer a parser, ale oba ze stejné gramatiky - pravidla pro lexer a pro parser jsou syntakticky rozlišena velikostí jejich prvního písmena.

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 )?
	;

Někteří lidé prý vidí, že tato konstrukce má správnou semantiku - a my ostatní si to můžeme otestovat...

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; } )?
	;

Fragmenty jsou tokeny používané pouze v definici jiných tokenů - jinými slovy lexer je nikdy nerozeznává.

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...

Tygr v českém rybníce

vbarta — Mon, 02 Jul 2007 18:08:00 GMT

Pro vyhledávání na českém internetu už léta používám českou jedničku, nicméně poslední dobou nelze přehlédnout, že se o náš rybníček zajímá i jistý světový vyhledávač, a tak jsem začal přemýšlet, nestačil-li by všem mým dotazům jeden.

Obrázek z Daily Mail

Problém samozřejmě je, že jakkoli existují i tygři, kterým by se ryby (úplně jedno jak dravé) měly ve vlastním zájmu vyhnout, ne všem velkým šelmám voda vyhovuje. Méně metaforicky, je pro dotazy v češtině lepší používat vyhledávač obecný, nebo specializovaný? Na takovou otázku pochopitelně existuje řada odpovědí (včetně "42"); níže je pouze jeden skromný pokus konkretizovat ji pro mé potřeby a tím pádem v jistém smyslu částečně možná i zodpovědět.

Pro začátek budeme potřebovat nějakou množinu dotazů, kterou předhodíme testovaným vyhledávačům. Nejjednodušší mi připadalo (poté co jsem prozkoumal několik slepých uliček - celý tento popis je velmi souhrnný) získat jí z "našeptávače", navrhujícího populární dotazy začínající specifikovanými písmeny. Aby to bylo spravedlivé, nevezmeme našeptávač žádného z porovnávaných vyhledávačů (taky bysme mohli vzít oba, ale to je víc práce), ale nějaký jiný (co se nabízí) a zeptáme se ho, jaké dotazy navrhuje pro všechna písmena abecedy.

autorita	počet dotazů
centrum.cz	479

To bude tak akorát počet pro malý experiment, a je to množina s fascinujícím rozsahem (upřímně řečeno pro mé potřeby až příliš velkým - neumím si představit že bych hledal řekněme "operní árie dante" - ale já stejně česky moc nevyhledávám, takže se spokojím s populárním výběrem).

Získat HTML stránky s odpověďmi na zpracovávané dotazy není tak těžké - většinu technických detailů můžeme vynechat. Google se trochu cukal, ale stačilo mu podstrčit Referer a User Agent, aby se s mým klientem začal bavit - ani nevím jestli se mě snažil přesvědčit abych používal Google API a nebo to mají prostě špatně naprogramované. Co se týče API, má ho i Seznam, ale zjevně ne pro obecné dotazy, a i kdyby oba vyhledávače měly API vyhovující mým nápadům, určitě nebudou stejná. Nebudeme se párat s hledáním vchodu pro dodavatele a použijeme brutální sílu.

Na výsledcích dotazů nás zajímají hlavně linky. Dostat z HTML hodnoty atributu href elementu a je opět standardní úloha, ale problém je, že ne všechny linky jsou pro nás zajímavé. Rozeznat interní linky (do téže domény) je snadné, ale pak jsou tam inzeráty, které chceme taky ignorovat - naším cílem je zjistit kdo má lepší vyhledávač, ne kdo má víc inzerentů. Stránky každého vyhledávače mají nicméně docela pravidelnou strukturu, takže v zásadě je možné napsat skript, který vybere pouze "opravdové" linky (s přijatelným počtem chyb). Knihovna interpretující seznamy linků dokonce ani nemusí být specifická pro pouze jeden vyhledávač - abych se přiznal, nejdůležitější motivací tohoto projektu bylo, že jsem si jednu takovou napsal a chtěl ji vyzkoušet. Je veřejně přístupná, ale v tomto textu ji nebudu rozvádět - jsme koneckonců na blogu o .NET, takže pouze poznamenám, že by koneckonců bylo docela dobře možné napsat ji třeba v C#... :-)

Řekněme tedy že máme linky odpovídající jednotlivým dotazům jak na Google, tak na Seznam:

autorita	počet linků
google.cz	4762
seznam.cz	4672

A dál? No, pro začátek můžeme zjistit, jsou-li stejné. Zběžný pohled nás přesvědčí, že nejsou úplně stejné (kdyby byly, dal bych se do hledání chyby v mém programu), takže se budeme muset rozhodnout, jak vypadá "skoro stejný" výsledek a vůbec jak kvantifikovat podobnost. Po zralé úvaze (a hodu mincí) jsem se rozhodl porovnávat nikoli celá URL, ale pouze jejich hosty - jestli Seznam a Google doporučují pro tentýž dotaz různé příspěvky v jednom blogu, je to vpodstatě totéž...

autorita	počet různých hostů
google.cz	2886
seznam.cz	3313

...a pořád to nevypadá nijak zvlášť zajímavě (že má Google víc linků na hosta než Seznam je nejspíš artefakt toho, že jsem se dotazoval jen na první stránku - Google na ní má košatější stromy)...

Zajímavější je, že většina hostů je jiná pro Seznam než pro Google - společných je jich pouze 508, tj. v zhruba jeden host na dotaz. A samozřejmě se nemusíme ptát pouze na průměr, ale můžeme se podívat na jednotlivé dotazy:

Doporučují někdy Google a Seznam úplně stejnou množinu hostů?
Doporučují někdy překrývající se množiny?
Existují dotazy, na které Google a Seznam odpovídají zcela jinak?

Na první otázku je odpověď negativní - maximální shoda je 6 hostů (z maximálně 10 na první stránce) na jeden dotaz. Interpretoval bych to tak, že Internet je prostě plný šuntu, a i když ho vyhledávače spoustu odfiltrují, pořád ho ve výsledcích dost zbývá. Četnost dalších možností je v tabulce:

výsledek	počet dotazů
částečná shoda	419
úplně jinde	60

Google a Seznam vidí ten samý český rybníček dost jinak, aby bylo možné, že jeden z nich ho vidí líp - ale který? I kdybych chtěl ručně zkontrolovat statisticky významný zlomek těch linků (jako že mě to ani nehne), kvalitu linků na (např.) "účesy pro polodlouhé vlasy" obávám se neposoudím...

Dáme hlasovat. Zeptáme se jiných vyhledávačů (Centra a ještě jednoho) a zjistíme, na kterých dotazech se shodnou (na 197). Hosty společné těmto dotazům prohlásíme za konsensuální realitu a spočteme, kolikrát se do ní Seznam a Google trefí:

autorita	počet úspěchů
google.cz	138
seznam.cz	125

No, moc výrazný rozdíl to není... Co takhle podívat se jen na ty dotazy, na kterých se Seznam s Googlem vůbec neshodnou?

autorita	počet úspěchů
google.cz	11
seznam.cz	5

To už je relativně větší rozdíl, ovšem dostáváme se nepříjemně blízko k nule... Možná jsou ty vyhledávače přece jen všechny na jedno brdo...

Co je to jméno...

vbarta — Mon, 10 May 2004 18:38:00 GMT

...nikoli tedy růže, ale jméno System.Text.Encoding. Instance této třídy mají ne méně než čtyři jména: BodyName, EncodingName, HeaderName a WebName (a to nepočítám CodePage), jejichž dokumentace se v zásadě omezuje na příklady: "If this encoding is equivalent to UTF8Encoding, this property returns "utf-8"," jak pro BodyName, tak HeaderName - ale cožpak MIME RFC nespecifikují tatáž jména pro hlavičky a těla? ISO kódování (aspoň těch pár běžných, co jsem zkoušel - ISO-8859-{1,2,4,5} a pár dalších, které můj systém podporuje) mají naštěstí BodyName stejné jako HeaderName - a jelikož WebName (jediné jméno podporované .NET CF) je taky to samé, zdá se, že klienti .NETu vystačí s jedním kanonickým jménem - když vědí, které vybrat...

Web Services vs. přístupová práva

vbarta — Mon, 15 Mar 2004 22:48:00 GMT

.NET security se mě nějak nechce pustit - tentokrát v kontextu Web Services...

Píšu servis, který zprostředkuje přístup k databázi Exchange serveru, a píšu ho v C# - je to můj první Web Service, a tato RPC architektura i programovací jazyk jsou koneckonců vyvíjené společně, takže by se neměly nijak tlouct. Neměly...

Můj Web Service implicitně běží jako Network Service, což kupodivu není "user name" (přinejmenším log4net tvrdí, že Principal.Identity.Name je v tomto kontextu prázdný řetězec), nýbrž Windows Identity NT AUTHORITY\NETWORK SERVICE. Proč je tak složité získat pravé jméno? :-)

Network Service může ledacos, ale jednou z věcí, které nezvládá, je otevření Exchange mailboxu. Network Service nejspíš žádný mailbox nemá (což je jen dobře - těžko od tohoto účtu očekávat, že si bude číst poštu), jenže selhává, i když se pokusí otevřít mailbox někoho jiného (a kdyby jen selhával - ani si nestěžuje). CDO IDataSource.Open sice má parametry pro uživatelské jméno a heslo, ale ať jsem tam cpal cokoli, k ničemu to nevedlo...

Takže jsem se rozhodl sestoupit z výšin .NETu a impersonovat. To zafungovalo lépe - dokázal jsem se přihlásit jako administrátor. Jako jiný uživatel ale bohužel nikoli :-( - volám-li LogonUser s parametrem LOGON32_LOGON_INTERACTIVE, vysvětlí mi server, že obyčejní uživatelé nemají na interaktivní přihlášení nárok, zatímco použiju-li LOGON32_LOGON_NETWORK, dozvím se od .NETu, že vzdálení uživatelé nemají co natahovat dynamické knihovny:

System.IO.FileLoadException: Access is denied: 'ADODB'.

Člověk by očekával, že tyto dvě operace se dají provést odděleně, pod různými účty - ale dosud je mi to nepovedlo...