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