[Libfsd-devel] Vtora kopka

[Ivan P. <va...@ne...>]

Pichove eto posledna versija. 
Dnes po njakoe vreme shte ja slozha v CVS-a na SF.net za da mozhe da se raboti 
po-normalno.

Kakvo imame tuk:
- optimizacii po regex parse durvoto
- implementacija GFA/NFA

generirame NFA ot reguljaren izraz. vse oshte ne se poddurzhat klasove 
([...]), pochti sum gi napravil, ama ne suvsem i za tova ne sum gi vkljuchil 
tuk. mozhete da izprobvate tools/nfa [REGEX] - dumpi v dot format 
generiranija avtomat. demek neshto ot sorta bi trjabvalo da go vizualizira:

nfa "a+(ab|bc)c+" | dot -Tps -oshit.ps ; kghostview shit.ps

nachi kato cjalo vsichko e pushka, imam obache slednite neprijatni 
nabljudenija. reguljarnijat izraz ".*" napravo razcepva mraka. dori kogato 
interpretiram '.' kato "vsichki printable characters" generiranijat avtomat 
ima 191 sustojanija i 9120 transition-a!! koeto na 32-bit os oznachava grubo 
86K za nedeterminiranija avtomat. ne znam kolko mozhe da narastne tova pri 
determiniranija (principno mozhe da narastne exponencialno...)

tova naj-malkoto objasnjava zashto nikoj ne implementira reguljarni izrazi s 
krajni avtomati :)

ne sum mnogo siguren che trjabva da reshavame tozi problem (verojatno trjabva 
ako iskame njakoj da izpolzva izobshto libfsd za drugo osven za 
demonstracionni celi), no njakakvo reshenie e da pishem v transition-a 
tablica ot simvoli, a ne samo edin simvol. 

shte vidja kakvo kazvat Aho i kolegija v knigata Compilers. maj imashe neshto 
za predstavjane na krajni avtomati (algorithm na Tarjan ili neshto takova).