Thread: [Libfsd-devel] Tva-onova

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

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

Thread: [Libfsd-devel] Tva-onova

libfsd-devel