Re: [Libfsd-devel] cvs update

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

ima novosti v CVS-a - naj-veche bugfixes. dobavih dfa.{c,h} s basic 
interface-a (kuhi metodi) i v momenta se opitvam da napravija konstruirane ot 
NFA (demek determinizacija). 

kato go svursha tova mislja da pospra s kodiraneto, zashtoto mnogo se 
natrupaha neshtata i stava vse po-nevuzmozhno da se napishat autotestove.

ta kato stana duma za autotests, mnogo mislih kak mozhe da se definirat. 
znachi imame njakakvi grafi, obache reda na transitionite ili nomeracijata na 
sustojanijata ne e ot znachenie. znachi promerno mozhem da zadadem grafa na 
avtomata po njakakuv nachin (XML?) obache sled tova ne trjabva da durzhim na 
naredbi. toest opirame do izomorfizum na grafi, puk tova pochti sigurno e 
NP-complete (maj beshe otvoren problema). ne che shte e grizha za malki 
grafcheta, no vse pak.. tova mi se vizhda edinstvenija kaduren variant kojto 
da proverjava strukturata na generiranite avtomati. drug variant za testvane, 
no ne tolkova izcherpatelen e da zadavame reguljaren izraz i njakakuv broj 
accepted i non-accapted putishta. toest za reguljarnija izraz a+b mozhem da 
zadadem che generiranija avtomat trjabva da razpoznava aaaaaaaab i ab, no 
trjabva da othvyrli a, abb, bb, x i oshte mnogo neshta. 
tova ima predimstvoto che njama da ni vurzhe strukturata na generiranite 
avtomati, t.e. ako utre smenim algorituma za konstruirane njama da trjabva da 
prepravjame testovete, no puk ne e tolkova sigurno. ama puk kato se zamislja 
mnogo lesno shte se dobavjat test case-ove.. ne znam - kakvo mislite?

za reguljarnite izrazi kato che li naj-dobre e da se opisva parse-durvoto. tam 
taka ili inache naredbata na decata ima znachenie...


On Friday 07 October 2005 09:38, Ivan Peikov wrote:
> Commitnal sum poslednata mi versija ot vkushti.
> Edinstvenata po-goljama promjana e che v transitionite (nfa_trans_t) veche
> ima ne simvoli (nfa_alpha_t), range-ove (nfa_range_t). Suotvetno
> konstrukcijata e leko promenena (i sushto taka zavurshena -- predi njamashe
> support za character lists vuv REX parse durvetata).
> Taka che sega vseki reguljaren izraz kojto se poddurzha ot REX parsera si
> ima ekvivalenten avtomat.
>
> Attachvam kakvo se generira za reguljarnija izraz
> "[[:alpha:]][[:alnum:]_]*". Rezultatite mislja sa neprilichno dobri.
> Parsvaneto (na NC-mashinata mi) na tozi reguljaren izraz izjazhda ~20usec,
> a NFA konstrukcijata po tozi REX ~60usec. Tova oznachava che ima megdan za
> determinirane i pak shte sme v obozrimi granici. Pametta ne sum ja gledal,
> no kakto pisah predi, garantirano e che e linejna po reguljarnija izraz ako
> njama iteracija, i e kvadratichna, kogato ima.