Re: [Libfsd-devel] Vtora kopka + transition explosion problem

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

razbira se. bil sum pijan kato sum go pisal :) shte go slozha da destroyva 
predi da go initializira.

po problema sus transition explosion-a.
vchera mislih za edno reshenie, koeto ni spasjava zadnicite, obache pravi 
avtomatite malko po-trudni za programirane.

reshenieto e prosto - vmesto simvol v transition-ite shte pazim range ot 
simvoli. tova shte iziskva tochno oshte edin byte. izobshto ako simvol ot 
azbukata se predstavja s X byte-a ni trjabvat tochno oshte X byte-a za da 
predstavim range ot simvoli (v purvite X pishem base simvola na range-a, vuv 
vtorite po-izbor - ili kraja na range-a ili broja simvoli vlizashti v range-a 
sled base)

s kakvo tova prestavjane e po-dobro. ami dokazuemo e che transitionite 
polucheni pri konstruiraneto na NFA (po tazi shema) sa <= broja na simvolite 
v regular expression-a ako njama +/*. +/* operaciite vdigat na kvadrat broja 
na transitionite v avtomata kum kojto sa prilozheni (ako trjabva da sum 
tochen, uvelichava s broja na krajnite po broja na nachalnite, koeto e 
po-malko, no pak e ot porjaduka na O(n^2)). 
specialno v sluchaja za kojto spomenah v prednija mail ".*", "." generira 2 
sustojanija i slaga transition s range 0-255 na nego. sled tova zvezdata 
dobavja edno krajno sustojanie ot koeto s nishto ne se izliza (za da machne 
epsilon) i dobavja cikul ot nachalnoto kum nego si pak s label 0-255. toest 
transitionite stavat 2, a sustojanijata 3 - dosta po-dobre ot 9120 kum 191..
tova predstavjane sushto taka e dobro za predstavjane na clasovete ot simvoli 
- neshta kato [[:alpha:]0-9], se predstavjat super trivialno s ranges. 

loshoto na range-ovete e che pravjat implementacijata malko po-trudna. 
predstavjaneto veche ne tochno tova koeto chovek ima predvid kato si misli za 
graph/avtomat. predpolagam obache che shte trjabva da zhiveem s tova, 
zashtoto v purvonachalnija variant avtomatite sa absolutno neizpolzvaemi..

mnenija, drugi idei?


On Tuesday 04 October 2005 18:14, Georgi Mungov wrote:
> rex_parser_parse ne e li dobre da si destroy-va scanner-a nakraia ili da
> destroy-va staria v nachaloto. sega ako napravish 2 puti
>
> rex_parser_parse()
> rex_parser_parse()
>
> shte leak-nesh
>
> On Tuesday 04 October 2005 09:58, Ivan Peikov wrote:
> > 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).
>
> "Tumbleweed E-mail Firewall <tumbleweed.com>" made the following
>  annotations on 10/04/05 08:23:49
> ---------------------------------------------------------------------------
>--- This e-mail, including attachments, may include confidential and/or
> proprietary information, and may be used only by the person or entity to
> which it is addressed.  If the reader of this e-mail is not the intended
> recipient or his or her authorized agent, the reader is hereby notified
> that any dissemination, distribution or copying of this e-mail is
> prohibited. If you have received this e-mail in error, please notify the
> sender by replying to this message and delete this e-mail immediately.
> ===========================================================================
>===
>
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by:
> Power Architecture Resource Center: Free content, downloads, discussions,
> and more. http://solutions.newsforge.com/ibmarch.tmpl
> _______________________________________________
> Libfsd-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/libfsd-devel