Re: [Libfsd-devel] Tva-onova

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

ami ne che ne mozhe, obache povecheto algoritmi za koito se seshtam sa ot 
vida: "ami stignah do njakakuv state i sega za vsichki states, do koito imam 
transition ot tozi state napravi edi kakvo si". i za tova mi se vidja 
naj-udachno (razbiraj efektivno) da imame direkten dostup do transitionite ot 
vseki state

On Monday 19 September 2005 15:38, Georgi Mungov wrote:
> ami moje bi vmesto list transitions v state-a da sa v multimap ?
>
> On Saturday 17 September 2005 10:37, Ivan Peikov wrote:
> > Privet!
> >
> > Za da ne zamira "proekta" (:]) dokato Pesho go trese predpizpitna treska
> > (uspeh, Pesho!), eto kakvo e polozhenieto i kakvi vuprosi me zanimavat.
> >
> > Znachi do tuk imam implementnat parser-a na reguljarni izrazi, kojto e
> > pochti POSIX-compatible (ostavat mnogo malko featuri da se dobavjat, ama
> > za sega me murzi, puk i te sa njakvi dosta nenuzhni - nikoga ne bjah
> > chuval za collating sequences i equivallence classes v reguljarni izrazi
> > predi da procheta spesifikacijata). Taka che za momenta tozi parser shte
> > svurshi rabota. Edinstveno ostavat da se napravjat testove i malko da se
> > pozagladjat njakoi rubove :).
> >
> > Mislja che ottuk mozhem da zapochnem da pravim avtomatite. Struva mi se
> > naj-dobre da zapochnem s njakakuv vid general avtomati (GFA - General
> > Finite Automaton), kojto da e abstrakten i da njama azbuka. Tuk idva
> > purvijat vupros. Izglezhda edinstvenoto, koeto razlichava vsichki vidove
> > avtomati i transduceri za koito se seshtam e azbukata. Primerno za NFA
> > tova shte sa njakakvi simvoli, a za transducerite azbukata sa dvojki ot
> > naj-obshto simvol i output string. Toest trjabva tozi GFA da se napravi
> > taka che sled tova da mozhe s neshto kato konfiguracija da se napravi
> > proizvolen drug avtomat. Za momenta varianta, do kojto sum go dobutal, e
> > da ima slednite obekti
> >
> >
> > *************************************************************
> >
> > struct trans;
> > struct state;
> >
> > struct gfa {
> >   struct state *states; // Head of the list of states
> >   struct state *start; // Head of the list of starting states
> >   struct state *final; // Head of the list of final states
> >   pool_t state_pool; // Pool from which the states are allocated
> >   pool_t trans_pool; // Pool from which the transitions are allocated
> >   size_t state_nr;   // Number of states - used for assigning next state
> > id // --- Some overridable methods for managing transitions
> > ----------------- insert_func_t *insert; // Transition inserting function
> >   remove_func_t *remove; // Transition removing function
> >   search_func_t *search; // Transition searching function
> >
> > };
> >
> > struct state {
> >   struct trans *incoming; // List of incoming transitions
> >   struct trans *outgoing; // List of outgoing transitions
> >   struct state *start; // Link in list of start states (NULL if
> > non-start) struct state *final; // Link in list of final states (NULL if
> > non-final) struct state *next;  // Link in list of all states
> >   struct gfa *parent; // The automaton this state is part of
> >   size_t id; // Id for dumping and accessing purposes
> >   // More stuff?...
> > };
> >
> > struct trans {
> >   struct state *src; // Where from
> >   struct state *dst; // Where to
> >   struct trans *src_next; // Link in the list of transitions for src
> >   struct trans *dst_next; // Link in the list of transitions for dst
> >   // Intentionally no symbol -- this is an abstract transition
> > };
> >
> > // --- Example: NFA transition
> >
> > struct nfa_trans {
> >   struct trans base; // Should be first for lists and casts to work
> >   char alpha;
> > };
> >
> >
> > *************************************************************
> >
> >
> >
> > Neshto ej takova.. Puk posle kato se initializira konkreten avtomat shte
> > se podava size-a na alphabet symbola i taka shte se inicializira
> > trans_pool. Sushto shte se podavat i konkretni funkcii za
> > insert/remove/search na transition, koito obshto vzeto shte vzimat
> > src_state, symbol, dst_state i shte pravjat kakvoto tam se nalaga.
> >
> > Tuk veche idva vuprosa za efektivnostta. Mozhe da vi pravi vpechatlenie
> > che baja pamet shte jade tova zhivotno, obache puk shte ima vsichki
> > neobhodimi vruzki, koeto se nadjavam da ulesni algoritmite posle.
> >
> > Stoi sushto vuprosa kak shte sa podredeni transitionite za daden state.
> > Za momenta shte e dummy list bez nikakva naredba, obache se seshtate che
> > tova ni kachva slozhnostta na izpulnenie na avtomat vurhu dadena duma.
> > Tova e edna ot prichinite da zabija insert/remove/search operaciite kato
> > function pointers - edin vid vseki konkreten avtomat shte si reshava kak
> > da gi redi, i tursi. Mozhe za momenta da gi ostavim po tozi nachin puk v
> > budeshte ako se poluchi mnogo tezhko naistina da mislim kak da se
> > optimizira. Obshto vzeto ima megdan.
> >
> >
> > Ta tova e obshto vzeto predlozhenieto za sega. Kakvo mislite?
> > Mozhe da obsudim na zhivo Pesho kato si vzeme durzhavnija s otlichie, i
> > bez tova shte trjabva da cherpi ne edna i dve biri po povoda :)
> >
> >
> > Ajde do kukane i pishete ako neshto
> >
> >
> >
> > -------------------------------------------------------
> > SF.Net email is sponsored by:
> > Tame your development challenges with Apache's Geronimo App Server.
> > Download it for free - -and be entered to win a 42" plasma tv or your
> > very own Sony(tm)PSP.  Click here to play:
> > http://sourceforge.net/geronimo.php
> > _______________________________________________
> > 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 09/19/05 05:46:51
> ---------------------------------------------------------------------------
>--- 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.
> ===========================================================================
>===
>
>
>
> -------------------------------------------------------
> SF.Net email is sponsored by:
> Tame your development challenges with Apache's Geronimo App Server.
> Download it for free - -and be entered to win a 42" plasma tv or your very
> own Sony(tm)PSP.  Click here to play: http://sourceforge.net/geronimo.php
> _______________________________________________
> Libfsd-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/libfsd-devel