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

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

Moje bi po skoro e list ot ranges zashtoto [0-9A-Za-z] sa realno 3 range-a
No togava mai shte stane mnogo tromavo.

Vidiah che si fixiral azbukata na ASCII. Mojem li da predstavim togava range-a 
(ili ranges) sus bitset

On Wednesday 05 October 2005 09:07, Ivan Peikov wrote:
> 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
>
> -------------------------------------------------------
> 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

"Tumbleweed E-mail Firewall <tumbleweed.com>" made the following
 annotations on 10/05/05 00:42:16
------------------------------------------------------------------------------
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.
==============================================================================