Re: [Libfsd-devel] Vtora kopka + transition explosion problem
Status: Planning
Brought to you by:
vanio
From: Ivan P. <va...@ne...> - 2005-10-05 08:05:25
|
On Wednesday 05 October 2005 10:33, Georgi Mungov wrote: > 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. mhm, prav si - realno e list ot ranges, no ako slozhim list ot ranges v transition-a, naj-malkoto ni trjabva oshte edno nivo na vlozhenost, oshte edin pool za ranges i za tova mi se stori dobur kompromisa da ima samo po edin range v transition. pri tekushtata implementacija harchim mjasto kolkoto 6 pointera na transition i mislja che mozhem da preglutnem tova razhishtenie ako zhivota ni shte se oprosti > > Vidiah che si fixiral azbukata na ASCII. Mojem li da predstavim togava > range-a (ili ranges) sus bitset ne mi se iska da fixirame na ASCII, a predstavjane s bitset ni vruzva dosta seriozno da rabotim s 1-byte simvol (za Unicode bitseta bi bil 16K...) purvonachalnata ideja da typedef-na nfa_alpha_t beshe eventualna vuzmozhnost utre da go napravim wchar_t, i tazi vuzmozhnost zavisi edinstveno ot lipsata na konstrukcii, eksponencialni po sizeof(nfa_alpha_t) ne e kazano che sega trjabva da pravim unicode versija, no e hubavo pone da njama prechki na nivo design, koito da go pravjat nevuzmozhno > > 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. > =========================================================================== >=== > > > > ------------------------------------------------------- > 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 |