Index: app/src/lib/Makefile =================================================================== --- app/src/lib/Makefile (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/Makefile (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,20 @@ +PAR=-Wno-deprecated -m32 -O3 +PAR2=-c -Wno-deprecated -m32 -O3 -static -fpermissive +LIB_PATH=../lib +COMMON_PATH=../common + +main: auttools.o word.o copy + +auttools.o: auttools.h auttools.cc + g++ $(PAR2) auttools.cc + +word.o: word.h word.cc + g++ $(PAR2) word.cc + +clean: + rm *.o + +copy: +ifdef UTT_LIB_DIR + cp -r perl $(UTT_LIB_DIR)/ +endif Index: app/src/lib/auttools.cc =================================================================== --- app/src/lib/auttools.cc (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/auttools.cc (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,164 @@ +#include "auttools.h" +//#include "/src/cpp-comm/plx/Plx.h" + +void fullform(const char* b, const char* d, char* f) +{ + int i,j=0; + int n1, n2=0; + bool g=false; + char s1[200], s2[200], temps[200]; + while(d[j]>='0' && d[j]<='9')j++; + strncpy(temps,d,j); temps[j]='\0'; + n1=atoi(temps); + i=j; + while(!ispunct(d[j]) || d[j]=='*') j++; + strncpy(s1,d+i,j-i); + s1[j-i]='\0'; + if(d[j++]=='-') + { + i=j; + while(d[j]>='0' && d[j]<='9')j++; + strncpy(temps,d+i,j-i); temps[j]='\0'; + n2=atoi(temps); + i=j; + while(!ispunct(d[j]) || d[j]=='*') j++; + strncpy(s2,d+i,j-i); + s2[j-i]='\0'; + g=true; + } + + int blen=strlen(b); + if(g) + if(n1+n2<=blen) + { + strcpy(f,s1); + strcat(f,b+n1); + f[strlen(f)-n2]='\0'; + strcat(f,s2); + } + else + strcpy(f,""); + else + if(n1<=blen) + { + strcpy(f,b); + f[strlen(f)-n1]='\0'; + strcat(f,s1); + } + else + strcpy(f,""); +} + +void compose(char* stem, char* ending, char* form) +{ + bool suffix=true; + while(*stem) + if(*stem=='*') + { + strcpy(form,ending); + form+=strlen(ending); + suffix=false; + stem++; + } + else + *(form++)=*(stem++); + if(suffix) + { + strcpy(form,ending); + form+=strlen(ending); + } + *form='\0'; +} + +void autodescr(const char* f, const char* des, char* lemma, char* pos, char* attr) +{ + char lemd[MAXWORDLEN]; + int o,l=strcspn(des,","); + strncpy(lemd,des,l); + lemd[l]='\0'; + fullform(f,lemd,lemma); + o=l+1; + l=strcspn(des+o,"/:"); + strncpy(pos,des+o,l); + pos[l]='\0'; + o=o+l; + if(des[o]=='/') + { + o++; + strcpy(attr,des+o); + } + else + attr[0]='\0'; +} + + +int common_prefix(const char* s, const char* t) +{ + int n=0; + while(*s==*t && *s!='\0') + { s++,t++;n++; } + return n; +} + +int strdiff(const char* s, const char* t, + int& frontcut, char* prefix, int& endcut, char* suffix) +{ + int slen=strlen(s); + int tlen=strlen(t); + int ss, ss_max=0; /* ss - s shift */ + int ts, ts_max=0; /* ts - t shift */ + int common, common_max=0; + for(ss=0;sscommon_max + && (common>4 || (ss==0 && ts==0 && common>1)) ) + { + ss_max=ss; + ts_max=ts; + common_max=common; + } + // print "--", tsmax,"\n" + printf("--%d\n", ts_max); + frontcut=ss_max; + strncpy(prefix,t,ts_max); prefix[ts_max]='\0'; + endcut=slen-ss_max-common_max; + strcpy(suffix,t+ts_max+common_max); + return common_max; +} + +void fprndiff(FILE* f, const char* s, const char* t) +{ + int frontcut,endcut; + char pref[MAXWORDLEN],suff[MAXWORDLEN]; + strdiff(s,t,frontcut,pref,endcut,suff); + if(frontcut!=0 || pref[0]!='\0') + fprintf(f,"%d%s-%d%s",frontcut,pref,endcut,suff); + else + fprintf(f,"%d%s",endcut,suff); +} + +void sprndiff(char* outstr, const char* s, const char* t) +{ + int frontcut,endcut; + char pref[MAXWORDLEN],suff[MAXWORDLEN]; + strdiff(s,t,frontcut,pref,endcut,suff); + if(frontcut!=0 || pref[0]!='\0') + sprintf(outstr,"%d%s-%d%s",frontcut,pref,endcut,suff); + else + sprintf(outstr,"%d%s",endcut,suff); +} + + +void despos(const char* des, char* pos) +{ + int di=0; + int pi=0; + while(des[di]!=',' && des[di]!='\0') ++di; + if(des[di]==',') + { + ++di; + while(isupper(des[di])) pos[pi++]=des[di++]; + } + pos[pi]='\0'; +} + Index: app/src/lib/auttools.h =================================================================== --- app/src/lib/auttools.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/auttools.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,39 @@ + +#ifndef _Auttools_h +#define _Auttools_h + +#include +#include +#include +#include + +/* #define ISALPHAG(c) ((c>='A' && c<='Z') || (c>='a' && c<='z') || \ */ +/* c=='¡' || c=='±' || c=='Æ' || c=='æ' || \ */ +/* c=='Ê' || c=='ê' || c=='£' || c=='³' || \ */ +/* c=='Ñ' || c=='ñ' || c=='Ó' || c=='ó' || \ */ +/* c=='Š' || c=='¶' || c=='¬' || c=='Œ' || \ */ +/* c=='¯' || c=='¿' || c=='*') */ + +#define MAXWORDLEN 64 + +extern void fullform(const char* b, const char* d, // in + char* f); // out + +extern void compose(char* stem, char* ending, // in + char* form); // out + +extern void autodescr(const char* f, const char* des, // in + char* lemma, char* pos, char* attr); // out + +extern int strdiff(char* s, char* t, // in + int& frontcut, char* prefix, // out + int& endcut, char* suffix); // out + +extern void fprndiff(FILE* f, const char* s, const char* t);// in + +extern void sprndiff(char* outstr, const char* s, const char* t); // in + +extern void despos(const char* des, // in + char* pos); // out + +#endif Index: app/src/lib/const.h =================================================================== --- app/src/lib/const.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/const.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,24 @@ + + + +// maksymalna dlugosc wyrazu +#define MAX_FORM 80 + +// maksymalna dlugosc opisu +#define MAX_DESC 80 + +// maksymalna dlogosc lini w pliku przejsciowym +#define MAX_LINE 1024 + +// separator pol w pliku posrednim +#define FIELD_SEP " \t\n" + +// maksymalna liczba alternatywnych opisow +#define MAX_ALT 256 + +// plik ze slownikiem dla guessa +#define GUESS_DICT_FILE "slownik.fsa" + +// katalogi z plikami konfiguracyjnymi +#define SYSTEM_CONFIG_DIR "/usr/local/etc/utt" +#define USER_CONFIG_DIR "~/.utt" Index: app/src/lib/iotools.h =================================================================== --- app/src/lib/iotools.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/iotools.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,53 @@ +#include "const.h" +#include +#include +#include +#include +#include + + +// napisy zostaj na miejscu (w line), tylko wskazniki sa ustawian +// i zara dopisywane zera s dopisywane + +inline +int parsetok(char* line, int* a, int* b, char** c, char** d, char** e, char** f) +{ + char* field; + if((field=strtok(line,FIELD_SEP))!=NULL) + *a=atoi(field); // nie sprawdzana poprawnosc + else + return 0; + if((field=strtok(NULL,FIELD_SEP))!=NULL) + *b=atoi(field); // nie sprawdzana poprawnosc + else return 1; + if((*c=strtok(NULL,FIELD_SEP))==NULL) return 2; + if((*d=strtok(NULL,FIELD_SEP))==NULL) return 3; + if((*e=strtok(NULL,FIELD_SEP))==NULL) return 4; + if((*f=strtok(NULL,FIELD_SEP))==NULL) return 6; + return 6; +} + +// napisy s kopiowane +inline +int scantok(const char* line, int* a, int* b, char* c, char* d, char* e=NULL, char* f=NULL) +{ + return sscanf(line," %d %d %s %s %s %s", a, b, c, d, e, f); +} + +inline +int printtok(char* line, int a, int b, char* c, char* d, char* e, char* f, char* parms) +{ + sprintf(line,"%04d %02d %s %s %s %s `%s\n", a, b, c, d, e, f, parms); +} + +inline +int printtok(char* line, int a, int b, char* c, char* d, char* e, char* f) +{ + sprintf(line,"%04d %02d %s %s %s %s\n", a, b, c, d, e, f); +} + +inline +int printtok(char* line, int a, int b, char* c, char* d) +{ + sprintf(line,"%04d %02d %s %s\n", a, b, c, d); +} Index: app/src/lib/matchdescr.cc =================================================================== --- app/src/lib/matchdescr.cc (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/matchdescr.cc (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,86 @@ +#include +#include + +inline +bool inline_matchattr(const char* a, const char* b) +{ + const char *p, *q; // pomocnicze wskazniki + while(*a && *b) + { + p=a; q=b; + while(isupper(*p) && isupper(*q)) // rowny prefiks + if(*p==*q) ++p, ++q; + else if(*p<*q) // a jest mniejszy + { + // przesywamy a do nastepnego atr + a=p; + while(isupper(*a)) ++a; while(islower(*a)) ++a; + goto end; + } + else + { + // przesuwamy b do nastepnego atr + b=q; + while(isupper(*b)) ++b; while(islower(*b)) ++b; + goto end; + } + + if(islower(*p) && islower(*q)) // rowne atrybuty + { + a=p; b=q; // przesuwamy wskaznik, sprawdzamy wartosci + while(*a != *b) + { + if(*a > *b && !islower(*++b)) return false; + if(*a < *b && !islower(*++a)) return false; + } + // znaleziono rowna wartosc, przesywamy a i b do nast atr + while(isupper(*a)) ++a; while(islower(*a)) ++a; + while(isupper(*b)) ++b; while(islower(*b)) ++b; + goto end; + } + + if(islower(*p)) // a jest krotszy, czyli mniejszy + { // przesuwamy a do nastepnego atrybutu + a=p; + while(islower(*a)) ++a; + goto end; + } + + if(islower(*q)) // b jest krotszy, czyli mniejszy + { // przesuwamy b do nastepnego atrybutu + b=q; + while(islower(*b)) ++b; + goto end; + } + end: ; + } + return true; +} + + +bool matchattr(const char* a, const char* b) +{ + return inline_matchattr(a,b); +} + +bool matchdescr(const char* a, const char* b) +{ + while(isupper(*a) && isupper(*b) && *a==*b) ++a, ++b; + if(*a=='\0') + if(*b=='\0' || *b=='/') return true; + else return false; + + if(*a=='/') + if(*b=='\0') return true; + else if(*b=='/') return inline_matchattr(++a, ++b); + + return false; +} + + +int main() +{ + char a[100], b[100]; + while(scanf("%s %s", a, b)==2) + printf("%s & %s = %d\n", a, b, matchdescr(a,b)); +} Index: app/src/lib/matchdescr.h =================================================================== --- app/src/lib/matchdescr.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/matchdescr.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,10 @@ + +// obie funkcje wymagaja by deskrypcje byly w postaci kanonicznej +// obslugiwane sa tylko krotkie (jednoliterowe) atrybuty + +// test czy zgadzaja sie deskrypcje +bool matchdescr(const char* a, const char* b); + +// test czy zgadaja sie same atrybuty (czyli to, co po ukosniku) +bool matchattr(const char* a, const char* b); + Index: app/src/lib/symtab.cc =================================================================== --- app/src/lib/symtab.cc (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/symtab.cc (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,171 @@ +#include "symtab.h" +#include +#include +#include +#include +//--------------------------------------------------------------------------- + +SymbolTable::SymbolTable(int n, int (*h)(const char*,int), const char* filename) + : _mx(n), _cnt(0), hash(h) +{ + _sz=first(n); + _key=new char*[_sz]; + _defind=new int[_sz]; + _hashind=new int[_sz]; + _def=new char*[_mx]; + for(int i=0; i<_sz; i++) _key[i]=NULL; + if(filename) + add_from_file(filename); +} + +//--------------------------------------------------------------------------- + +SymbolTable::SymbolTable(int n, const char* filename) + : _mx(n), _cnt(0), hash(hash1) +{ + _sz=first(n); + _key=new char*[_sz]; + _defind=new int[_sz]; + _hashind=new int[_sz]; + _def=new char*[_mx]; + for(int i=0; i<_sz; ++i) _key[i]=NULL; + if(filename) + add_from_file(filename); +} + +//--------------------------------------------------------------------------- + +SymbolTable::~SymbolTable() +{ + clear(); + delete[] _key; + delete[] _defind; + delete[] _hashind; + delete[] _def; +} + +//--------------------------------------------------------------------------- + +void SymbolTable::clear() +{ + for(int i=0; i<_sz; ++i) + if(_key[i]) + free(_key[i]); +} + +//--------------------------------------------------------------------------- + +bool SymbolTable::add_from_file(const char* filename) +{ + FILE* in=fopen(filename,"r"); + char buf[MAXKEYLEN+1]; + + if(in) + while(fscanf(in,"%s",buf)==1) + { + if(strlen(buf)==MAXKEYLEN || add(buf)<0) + return false; + } + return true; +} + +//--------------------------------------------------------------------------- + +int SymbolTable::add(const char* s) +{ + if(_cnt<_mx) + { + int ind=hash(s,_sz); + while(_key[ind]) + if(strcmp(_key[ind],s)) + ind=++ind%_sz; + else + return _defind[ind]; + _key[ind]=strdup(s); + _defind[ind]=_cnt; + _hashind[_cnt]=ind; + _def[_cnt]=_key[ind]; + _cnt++; + return _cnt-1; + } + else + return -1; +} + +//--------------------------------------------------------------------------- + +int SymbolTable::operator[](const char* s) +{ + int ind=hash(s,_sz); + while(_key[ind]) + if(strcmp(_key[ind],s)==0) + return _defind[ind]; + else + ind=++ind % _sz; + return -1; +} + +//--------------------------------------------------------------------------- + +int SymbolTable::first(unsigned int n) +{ + int fi=n; + int bound=(n/2 < MAXKEYLEN)? n/2 : MAXKEYLEN; + bool found; + do + { + found=true; + if(fi++ == MAXINT) return -1; + for(int i=2; i=4) + return abs((*((int*)(s+(l/2-2)))+(int)(*s * s[l-1])) % _sz); + else + { + int i=0; + strcpy((char*)&i,s); + return abs((i+(int)(*s * s[l-1])) % _sz); + } +} + +//--------------------------------------------------------------------------- + +int hash2(const char* s, int _sz) +{ + int l=strlen(s); + if(l>=6) + { + unsigned int i1,i2,i3; + strncpy((char*)&i1,s,sizeof(int)); + strncpy((char*)&i2,s+(l/2-2),sizeof(int)); + strncpy((char*)&i3,s+(l-4),sizeof(int)); + return abs((i1+i2+i3) % _sz); + } + else + { + int i=0; + strncpy((char*)&i,s,sizeof(int)); + return abs((i+(int)(*s * s[l-1])) % _sz); + } +} + +//--------------------------------------------------------------------------- + Index: app/src/lib/symtab.h =================================================================== --- app/src/lib/symtab.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/symtab.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,52 @@ +#ifndef _HashTable_h +#define _HashTable_h +//--------------------------------------------------------------------------- +#include +#include +//--------------------------------------------------------------------------- +int hash1(const char* s, int sz); +int hash2(const char* s, int sz); +//--------------------------------------------------------------------------- + +class SymbolTable +{ + int _mx; + int _sz; + int _cnt; + char** _key; + char** _def; + int* _defind; + int* _hashind; // s¹ tu redundancje + +public: + static const unsigned int MAXKEYLEN=2000; + + SymbolTable(int n, int (*h)(const char*,int), const char* filename=NULL); + SymbolTable(int n, const char* filename=NULL); + ~SymbolTable(); + + void clear(); + + int (*hash)(const char*, int); + + bool add_from_file(const char* filename); + + int add(const char* s); + int operator[](const char* s); + const char* operator[](int i){if(i<0||i>=_cnt)return NULL;else return _def[i];} + int index(const char* s) { return this->operator[](s); }; + int index(int i) { if(i<0||i>=_cnt) return -1; else return i; }; + int hash_index(int i) { return _hashind[i]; } + const char* symbol(int i) { if(i<0||i>=_cnt)return NULL; else return _def[i];} + + int capacity() { return _mx; } + int size() { return _sz; } + int count() { return _cnt; } + float search_rate(); + +private: + static int first(unsigned int n); +}; + +//--------------------------------------------------------------------------- +#endif Index: app/src/lib/tft.h =================================================================== --- app/src/lib/tft.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/tft.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,879 @@ +#ifndef _TFT_h +#define _TFT_h +//--------------------------------------------------------------------------- +#include +#include +#include +#include + +#include + +//#include "top.h" +#include "ttrans.h" +//--------------------------------------------------------------------------- + +/// Klasa bazowa przetwornika skoñczonego. +/** + \remark Po co ta klasa? Co dotyczy samych przej¶æ, przenie¶æ do TTrans, + resztê wcieliæ do TFT. +*/ +class FT +{ +public: + FT() : copy_default(false), print_mode(OO), ttn(0) {}; + +//print mode + enum OUTPUT { II, ///< tylko symbole wej¶ciowe + OO, ///< tylko symbole wyj¶ciowe + IOIO, ///< symbol wyj¶ciowy po wej¶ciowym + OIOI, ///< symbol wyj¶ciowy przed wej¶ciowym + IIOO, ///< ca³e wej¶cie, potem ca³e wyj¶cie + OOII ///< ca³e wyj¶cie, potem ca³e wej¶cie + + }; + +/// maks d³ugo¶æ ¶cie¿ki + static const unsigned int ftMAXPATH=500; + +/// maks d³ugo¶æ opisu typu symbolu we/wy +/** + \remark Przenie¶æ do TTrans +*/ + static const unsigned int ftTYPELEN=32; + +/// specjalny symbol dla warto¶ci 'epsilon' +/** + \remark Przenie¶æ do TTrans +*/ + static const char ftEPSILON='~'; + +/// specialny symbol dla warto¶ci 'default' +/** + \remark Przenie¶æ do TTrans +*/ + static const char ftDEFAULT='@'; + +/// domy¶lny symbol wyj¶ciowy (true-'@', flase-'~') +/** + \remark Przenie¶æ do TTrans(???) +*/ + bool copy_default; + +/// tryb wyj¶cia + OUTPUT print_mode; + +/// false, je¶li automat nie ma przej¶æ + operator bool() { return (bool)ttn; }; + + virtual const char* intype() { return itype; }; + virtual const char* outtype() { return otype; }; + +protected: + +/// liczba elementów tablicy tt + unsigned long ttn; + +/// liczba stanów + unsigned long states; + +/// liczba przej¶æ + unsigned long transitions; + +/// typ symboli wej¶ciowych (napis) +/** + \remark Przenie¶æ do TTrans(???) +*/ + char itype[ftTYPELEN]; + +/// typ symboli wyj¶ciowych (napis) +/** + \remark Przenie¶æ do TTrans(???) +*/ + char otype[ftTYPELEN]; +}; + +//--------------------------------------------------------------------------- + +/// Szablon przetwornika skoñczonego +/** + \param I - typ symbolu wej¶ciowego + \param Ipass - typ, jaki ma byæ u¿yty przy przekazywaniu symbolu we jako parametru + do funkcji (metody), równy \a I lub \a I& + \param O - typ symbolu wyj¶ciowego + \param Opass - typ, jaki ma byæ u¿yty przy przekazywaniu symbolu wy jako parametru + do funkcji (metody), równy \a O lub \a O& + \param - typ przej¶cia, musi byæ podklas± TTrans +*/ +template +class TFT : public FT +{ + + +public: + + TFT() : FT(), tt(NULL) { setiotypes(); }; + +/** +\name Metody poziomu 1 +Poziom przej¶æ. +*/ + +//@{ + +/// Test, czy przej¶cie \a t akceptuje symbol \a in. + bool accepts(long t, Ipass in) const; + +/// Test, czy lista przej¶æ dla aktualnego stanu jest kontynuowana po \a t. + bool continued(long t) const; + +/// Stan, do którego prowadzi przej¶cie \a t. +/** + \pre !empty(t) +*/ + long next(long t) const; + +/// Symbol wej¶ciowy przej¶cia \a t. + Ipass input(long t) const; + +/// Symbol wyj¶ciowy przej¶cia \a t. + Opass output(long t) const; + +/// Zwraca \c true, je¶li symbolem we przej¶cia \a t jest epsilon. + bool epsi(long t) const; + +/// Zwraca \c true, je¶li symbolem we przej¶cia \a t jest symbol domy¶lny. + bool defi(long t) const; + +/// Zwraca \c true, je¶li symbolem wy przej¶cia \a t jest epsilon. + bool epso(long t) const; + +/// Zwraca \c true, je¶li symbolem wy przej¶cia \a t jest symbol domy¶lny. + bool defo(long t) const; + +/// Indeks przej¶cia przez \a in. + long tra(long t, Ipass in) const; + +/// Indeks przej¶cia przez \a in - non-deterministic. + long tra_nd(long t, Ipass in, long nth) const; + +//@} + +/** +\name Poziom 2 +Poziom stanów. Stan (indeks stanu) = indeks jego pierwszego przej¶cia +*/ +//@{ +/// Zwraca \c true je¶li stan \a s jest pusty (nie ma z niego przej¶æ). + bool empty(long s) const { return tt[s].empty(); } + +/// Zwraca \c true je¶li stan \a s jest stanem koñcowym. + bool final(long s) const { return tt[s].final(); } + + long next(long t, Ipass in) const; + +//long trans(const I* si, I* so, long& olen) const; + + long gtra(long s, const I* w, long maxpath=ftMAXPATH) const; + +//@} + +/** +\name Poziom 3 +Poziom ... +*/ +//@{ + long cont(long s=-1, I* c=NULL) const; + + long match(const I* w=NULL, long* p=NULL) const; + + long match_nd(const I* w=NULL, long* p=NULL) const; + + long lgstmatch(const I* w, long* p, long& plen, long maxpath=ftMAXPATH) const; + + /*NOWE*/ + + long lgstpath(I*& buf, long*& path, long start=0) const; + + long pref(I*& buf, I sep, long start=0) const; + +//@} + +protected: + + TT* tt; // tablica przej¶æ + + long prn(const I* si, long* p, O* so) const; + + void prntt(ostream& os); + + void sort(); + + void setiotypes(); // NIE DZIA£A (dlaczego???) + +// friend ostream& operator<<(ostream&,const CDFA&); +// friend istream& operator>>(istream&,CDFA&); + +private: + long prn_oo(const I* si, long* p, O* so) const; + long prn_ioio(const I* si, long* p, O* so) const; + long prn_oioi(const I* si, long* p, O* so) const; + long prn_iioo(const I* si, long* p, O* so) const; + long prn_ooii(const I* si, long* p, O* so) const; +}; + + +//--------------------------------------------------------------------------- +//--------------------------------------------------------------------------- + +/** + stan = indeks pierwszego przej¶cia + + state(t) = stan, do którego nale¿y t + + symbol zerowy = symbol s, dla którego (bool)s zwraca \c false, + w przypadku znaków - '\0' +*/ + +//--------------------------------------------------------------------------- +//--------------------------------------------------------------------------- + + +template +inline +bool TFT::accepts(long t, Ipass in) const +{ return tt[t].accepts(in); } + +/// Test whether the transition list continues after \a t. +template +inline +bool TFT::continued(long t) const +{ return tt[t].continued(); } + +/** + \pre !empty(t) +*/ +template +inline +long TFT::next(long t) const +{ return tt[t].next(); } + +template +inline +Ipass TFT::input(long t) const +{ return tt[t].in(); } + +template +inline +Opass TFT::output(long t) const +{ return tt[t].out(); } + +template +inline +bool TFT::epsi(long t) const +{ return tt[t].epsi(); } + +template +inline +bool TFT::defi(long t) const +{ return tt[t].defi(); } + +template +inline +bool TFT::epso(long t) const +{ return tt[t].epso(); } + +template +inline +bool TFT::defo(long t) const +{ return tt[t].defo(); } + +/** + \param +t - indeks przej¶cia + \param +in - symbol we + \return Indeks przj¶cia (>=\a t) dla bie¿±cego stanu, które + akceptuje symbol we \a in lub -1, je¶li nie ma takiego przej¶cia +*/ +template +long TFT::tra(long t, Ipass in) const +{ + if(t<0 || t>=ttn) + return -1; + + if(empty(t)) return -1; + while(!accepts(t,in)) + if(continued(t)) + t++; + else + return -1; + return t; +} + +//--------------------------------------------------------------------------- +/// Indeks przej¶cia - wersja dla automatu niedeterministycznego. +/** + \param +t - indeks przej¶cia + \param +in - symbol we + \return Indeks przj¶cia (>=\a t) dla bie¿±cego stanu, które + akceptuje symbol we \a in lub -1, je¶li nie ma takiego przej¶cia + Je¶li nth==0, t1>=t, w przeciwnym razie t1>t. +*/ +template +long TFT::tra_nd(long t, Ipass in, long nth) const +{ + if(t<0 || t>=ttn) + return -1; + + if(nth) + if(continued(t)) + t++; + else + return -1; + else + { if(empty(t)) return -1; } + + while(!accepts(t,in)) + if(continued(t)) + t++; + else + return -1; + + return t; +} + +//} + +//--------------------------------------------------------------------------- +//---------------------------------------------------------------------------- + + +/// Funkcja przej¶cia. +/** + \param t - stan + \param in - symbol we + \return Stan, do którego mo¿na przej¶æ z \a t po wp³ywem symbolu \a in + lub -1, je¶li nie ma przej¶cia przez \a in + +*/ +template +long TFT::next(long t, Ipass in) const +{ + if(t<0 || (unsigned long)t>=ttn) + return -1; + + if(empty(t)) return -1; + while(!accepts(t,in)) + if(continued(t)) + t++; + else { + return -1; + } + + return next(t); +} + +//--------------------------------------------------------------------------- + +//---------------------------------------------------------------------------- +/// Uogólniona funkcja przejscia. +/** + \param +s - stan + \param +w - wskaŒnik pierwszego elementu ci±gu symboli we, zakoñczonego symbolem zerowym + \param maxpath maksymalna d³ugo¶æ ¶cie¿ki, domy¶lnie ftMAXPATH + \return stan osi±galny z \a s pod wp³ywem \a w (na ¶cie¿ce mog± siê pojawiæ + epsilon-przej¶cia +*/ +template +long TFT::gtra(long s, const I* w, long maxpath) const +{ + if(s<0 || (unsigned long)s>=ttn) + return -1; + + long i=0; + while(*w) + { + if(i>maxpath || empty(s)) return -1; + while(!accepts(s,*w)) + if(continued(s)) + s++; + else + return -1; + if(!epsi(s)) w++; + s=next(s); + i++; + } + return s; +} + +//---------------------------------------------------------------------------- + +/// Kontynuacja. +/** +... +\param +s stan, je¶li -1 - poszukiwane jest nastêpne rozwi±zanie +\param -c ci±g symboli we ze ¶cie¿ki prowadz±cej z \a s do + stanu koñcowego +\return d³ugo¶æ ci±gu \a c (= d³ugo¶æ ¶cie¿ki) +\remark DZIA£A TYLKO DLA ZNAKÓW!!! + EPSILON-PRZEJŠCIA NIEDOZWOLONE!!! +*/ +template +long TFT::cont(long s, I* c) const +{ + static unsigned long path[ftMAXPATH]={0}; + static unsigned long i=0; + static bool more=false; + + bool found=false; + + if(s!=-1) + { + if(s<0 || (unsigned long)s>=ttn) + more=false; + else + { + i=0; + c[0]=0; + path[0]=s; + more=true; + if(final(s)) + found=true; + } + } + + while(more && !found) + { + if(!empty(path[i]) && i0) + c[--i]=0; + else + more=false; + }while(more && !continued(path[i])); + path[i]=path[i]+1; + } + if(final(path[i])) + { + found=true; + c[i]=0; + } + } + return i; +} + +//---------------------------------------------------------------------------- +/// Dopasowannie. +/** + \remark Nie zaimplementowane. +*/ +template +long TFT::match(const I* w, long* p) const +{} + +//---------------------------------------------------------------------------- +/// Dopasowanie niedeterministyczne. +/** + \param +w - wskaŒnik pierwszego elementu ci±gu symboli we, zakoñczonego symbolem zerowym, + je¶li NULL - poszukiwane jest nastêpne rozwi±zanie + \param -p ci±g przej¶æ zakoñczony -1 + \return d³ugo¶æ dopasowania (PO CO?) +*/ +template +long TFT::match_nd(const I* w, long* p) const +{ + static bool more=false; + static I *w0, *wc; + static long s=0, *p0, *pc, *pc_bound; + + bool found=false; + + if(w) + { + wc=w0=w; + pc=p0=p; + more=true; + pc_bound=pc+ftMAXPATH; + if(final(s=0)) + { + *pc=-1; return 0; + } + } + + while(more) + { + if(*wc && pc=0) + { if(!epsi(*pc)) wc++; s=next(*pc); pc++; } + else + while(true) + { + if(pc==p0) { more=false; return -1; } + if(!epsi(*(--pc))) wc--; + if((*pc=trand(*pc,*wc,1))>=0) + { if(!epsi(*pc)) wc++; s=next(*pc); pc++; break; } + } + if(final(s)) { *pc=-1; return wc-w0; } + } + return -1; +} + +//---------------------------------------------------------------------------- +/// Najd³u¿sze dopasowanie. +/** + \param +w wskaŒnik pierwszego elementu ci±gu symboli wej¶ciowych + \param -p ¶cie¿ka + \param -plen d³ugo¶æ ¶cie¿ki + \param +maxpath maks dd³ugo¶æ ¶cie¿ki, domy¶lnie FT::ftMAXPATH + \return d³ugo¶æ skonsumowanego wej¶cia +*/ +template +long TFT + ::lgstmatch(const I* w, long* p, long& plen, long maxpath) const +{ + long s=0; + long t; + long i=0; + const char* w0=w; + long ilen=0; + while(*w && i=0) + { + if(!epsi(t)) w++; + s=next(t); + i++; + *(p++)=t; + if(final(s)) { plen=i; ilen=w-w0; } + } + *p=-1; + return ilen; +} + +//---------------------------------------------------------------------------- +/// Najd³u¿sza ¶cie¿ka. +/** + \param +buf wskaŒnik pierwszego elementu ci±gu symboli wej¶ciowych + \param -buf pozycja jeden za skonsumowanym prefiksem + \param +path wskaŒnik pierwszego elementu wektora przej¶æ + \param -path wskaŒnik jeden za ostatnim przej¶ciem + \return d³ugo¶æ skonsumowanego prefiksu (PO CO? LEPIEJ D£ ŠCIE¯KI) +*/ +template +long TFT + ::lgstpath(I*& buf, long*& path, long start) const +{ + long s=start; + long t; + const char* buf0=buf; + const long* pathlimit=path+FT::ftMAXPATH; + while(*buf && path=0) + { + if(!epsi(t)) buf++; + s=next(t); + *(path++)=t; + } + return buf-buf0; +} + +//---------------------------------------------------------------------------- +/// Najd³u¿szy prefiks. +/** + \param +buf wskaŒnik pierwszego elementu ci±gu symboli wej¶ciowych + \param -buf pozycja jeden za skonsumowanym prefiksem + \param +sep separator + \return stan po przej¶ciu przez \a sep + \remark Dzia³a tylko dla automatów deterministycznych, minimalnych, eps-wolnych, + gdzie d³. ¶cie¿ki == d³. dopasowania. +*/ +template +long TFT + ::pref(I*& buf, I sep, long start) const +{ + static long pathtab[ftMAXPATH]; + // static long* path=pathtab; + long* path=pathtab; + static bool more; + + long s; + if(*buf) // pierwsze wywo³anie + { + if(!lgstpath(buf,path,start)) + return -1; + --path; + more=true; + } + else // kolejne wywo³anie + --buf,--path; + while(more) + if(path>=pathtab) + if((s=next(next(*path),sep))>=0) { + return s; + } + else + --buf, --path; + else + { + more=false; + return -1; + } + return -1; +} + +//---------------------------------------------------------------------------- + +/* +template +long TFT::trans(const I* si, O* so, long& olen) const +{ + long p[ftMAXPATH]; + long ilen; + long plen; + if((ilen=lgstmatch(si,p,plen))>0) + olen=prn(si,p,so); + else + ilen=olen=0; + return ilen; +} +*/ +//---------------------------------------------------------------------------- + +template +long TFT::prn(const I* si, long* p, O* so) const +{ + switch(print_mode) + { + case OO: return prn_oo(si,p,so); + case IOIO: return prn_ioio(si,p,so); + case OIOI: return prn_oioi(si,p,so); + case IIOO: return prn_iioo(si,p,so); + case OOII: return prn_ooii(si,p,so); + } +} + +//---------------------------------------------------------------------------- + +template +long TFT::prn_oo(const I* si, long* p, O* so) const +{ + char* so0=so; + while(*p>=0) + { + long t=*p; + if(!epso(t)) + { + if(defo(t)) + *(so++)=*si; + else + *(so++)=output(t); + } + if(!epsi(t)) si++; + p++; + + } + return so-so0; +} + +//---------------------------------------------------------------------------- + + +template +long TFT::prn_ioio(const I* si, long* p, O* so) const +{ + char* so0=so; + while(*p>=0) + { + long t=*p; + if(!epsi(t)) + *(so++)=*si; + if(!epso(t)) + if(defo(t)) + *(so++)=*si; + else + *(so++)=output(t); + if(!epsi(t)) si++; + p++; + } + return so-so0; +} + + +//---------------------------------------------------------------------------- + +template +long TFT::prn_oioi(const I* si, long* p, O* so) const +{ + char* so0=so; + while(*p>=0) + { + long t=*p; + if(!epso(t)) + { + if(defo(t)) + *(so++)=*si; + else + *(so++)=output(t); + } + if(!epsi(t)) + *(so++)=*(si++); + p++; + } + return so-so0; +} + +//---------------------------------------------------------------------------- + +template +long TFT::prn_iioo(const I* si, long* p, O* so) const +{ + const char* si0=si; + long* p0=p; + char* so0=so; + while(*p>=0) + { + long t=*p; + if(!epsi(t)) + { + *(so++)=*si; + si++; + } + p++; + } + si=si0; + p=p0; + while(*p>=0) + { + long t=*p; + if(!epso(t)) + if(defo(t)) + *(so++)=*si; + else + *(so++)=output(t); + if(!epsi(t)) si++; + p++; + } + return so-so0; +} + +//---------------------------------------------------------------------------- + +template +long TFT::prn_ooii(const I* si, long* p, O* so) const +{ + + const char* si0=si; + long* p0=p; + char* so0=so; + while(*p>=0) + { + long t=*p; + if(!epso(t)) + { + if(defo(t)) + *(so++)=*si; + else + *(so++)=output(t); + } + if(!epsi(t)) si++; + p++; + } + si=si0; + p=p0; + while(*p>=0) + { + long t=*p; + if(!epsi(t)) + *(so++)=*(si++); + p++; + } + return so-so0; +} + +//--------------------------------------------------------------------------- + +template +void TFT::sort() +{ + long t=0; + while(t1) + { + long eps=-1; + long def=-1; + for(int i=0; i=0 && epseps) def--; + if(def>=0 && def=0) + { + memmove(tt+t0+def+1,tt+t0+def,tn-eps-2); + tt[t-2]=temp; + } + else + { + memmove(tt+t0+def+1,tt+t0+def,tn-eps-2); + tt[t-1]=temp; + } + } + while(t0 +void TFT::setiotypes() +{ + int i=0; + const char* it=typeid(I).name(); + while(*it) + if(*it==' ') + { it++; continue; } + else + itype[i++]=*(it++); + itype[i]='\0'; + + i=0; + const char* ot=typeid(O).name(); + while(*ot) + if(*ot==' ') + { ot++; continue; } + else + otype[i++]=*(ot++); + otype[i]='\0'; +}; + +//--------------------------------------------------------------------------- + +template +void TFT::prntt(ostream& os) +{ + for(long i=0; i +#include +#include +//#include + +#include "tft.h" +//--------------------------------------------------------------------------- + +template +class TFTi : public TFT > +{ +public: + TFTi() : TFT >() {}; + TFTi(const char* filename) + : TFT >() { load(filename); }; + + void read(const char* filename); + void read(istream& is=cin); + void write(const char* filename); + void write(ostream& os=cout); + void load(const char* filename); + void load(FILE* f=stdin); + void save(const char* filename); + void save(FILE* f=stdout); + void clear(); + using TFT >::ttn; + using TFT >::states; + using TFT >::transitions; + using TFT >::itype; + using TFT >::ftTYPELEN; + using TFT >::otype; + using TFT >::tt; + using TFT >::copy_default; + using TFT >::print_mode; + + +// friend istream& operator>>(istream&, TFTi&); +// friend ostream& operator<<(ostream&, const TFTi&); +}; + +//--------------------------------------------------------------------------- + +template +void TFTi::read(const char* filename) +{ + ifstream is(filename); + if(!is) { fprintf(stderr,"Failed to open input file."); exit(1); } + read(is); +} + +template +void TFTi::read(istream& is) +{ + long *si; // state-index relation + long ci=0; // current index + char ch; // character read; + int empty=0; // no of states with 0 trans? + char intype[FT::ftTYPELEN]; + char outtype[FT::ftTYPELEN]; + + clear(); + + is >> states >> transitions >> intype >> outtype; + +// if(strcmp(intype,itype)!=0 || +// strcmp(outtype,otype)!=0 && strcmp(outtype,"void")!=0) +// { is.clear(ios::badbit); goto end; }; + + while(is.peek()==' ' || is.peek()=='\t') is.get(ch); + while(is.peek()!='\n') + { + char s[20]; + is >> s; + if(strcmp(s,"COPY")==0 && strcmp(intype,outtype)==0) copy_default=true; + else if(strcmp(s,"NOCOPY")==0) copy_default=false; + else if(strcmp(s,"II")==0) print_mode=FT::II; + else if(strcmp(s,"OO")==0) print_mode=FT::OO; + else if(strcmp(s,"IOIO")==0) print_mode=FT::IOIO; + else if(strcmp(s,"OIOI")==0) print_mode=FT::OIOI; + else if(strcmp(s,"IIOO")==0) print_mode=FT::IIOO; + else if(strcmp(s,"OIOI")==0) print_mode=FT::OIOI; + while(is.peek()==' ' || is.peek()=='\t') is.get(ch); + } + + ttn=transitions+2; // 1 state without trans., 1 additional + si=new long[states]; + tt=new TTrans_i[ttn]; + + for(long cs=0;cs> cscheck; + if(cs!=cscheck) goto end; + + while(is.peek()==' ' || is.peek()=='\t') is.get(ch); + + is.get(ch); + if(!is) goto end; + switch(ch) + { + case '-': tt[ci].final(false); break; + case '+': tt[ci].final(true); break; + default: goto end; + } + tc=0, tt[ci].continued(false); + + while(is.peek()==' ' || is.peek()=='\t') is.get(ch); + while(is && is.peek()!='\n') + { + switch(is.peek()) + { + case '~': tt[ci].epsi(true); tt[ci].defi(true); is.get(ch); + break; + case '@': tt[ci].epsi(false); tt[ci].defi(true); is.get(ch); + break; + default : tt[ci].geti(is); + } + if(!is) goto end; + if(is.peek()=='/') + { + is.get(ch); + switch(is.peek()) + { + case '~': tt[ci].epso(true); tt[ci].defo(true); is.get(ch); + break; + case '@': tt[ci].epso(false); tt[ci].defo(true); is.get(ch); + break; + default : tt[ci].geto(is); + } + } + else + { + tt[ci].defo(true); + if(copy_default) tt[ci].epso(false); else tt[ci].epso(true); + } + if(!is) goto end; + + unsigned long transition; + is >> transition; + tt[ci].next(transition); + + tt[ci].continued(false); + tt[ci].empty(false); + + if(tc>0) tt[ci-1].continued(true); + tc++,ci++; + } + if(tc==0) + { + if(++empty>2) { fprintf(stderr, "Nondeterministic automaton."); exit(1); } + tt[ci].empty(true); + ci++; + } + is.get(ch); + if(ch!='\n') { is.clear(ios::badbit); goto end; } + } + + ttn=transitions+empty; + if(ttn!=ci) { is.clear(ios::badbit); goto end; }; + for(long i=0;i +void TFTi::write(const char* filename) +{ + ofstream os(filename); + if(!os) err("Failed to open output file."); + write(os); +} + +template +void TFTi::write(ostream& os) +{ + os << states << ' ' << transitions << ' '; +// os << itype << ' ' << otype << ' '; + os << "char void"; +// os << (copy_default ? "COPY" : "NOCOPY") << ' '; +// switch(print_mode) +// { +// case FT::II : os << "II"; break; +// case FT::OO : os << "OO"; break; +// case FT::IOIO: os << "IOIO"; break; +// case FT::OIOI: os << "OIOI"; break; +// case FT::IIOO: os << "IIOO"; break; +// case FT::OOII: os << "OOII"; +// } + os << '\n'; + + long* si=new long[ttn]; + long cs=0; + for(long i=0;i +void TFTi::load(const char* filename) +{ + FILE* f; + if(*filename) + f=fopen(filename,"rb"); + else + f=stdin; + if(!f) { fprintf(stderr, "Cannot open automaton file."); return; } + load(f); +} + +template +void TFTi::load(FILE* f) +{ + + clear(); + + if(fread(&ttn,sizeof(ttn),1,f)!=1) { fprintf(stderr, "Binary input error."); return;} + if(fread(&states,sizeof(states),1,f)!=1) { fprintf(stderr, "Binary input error."); return;} + if(fread(&transitions,sizeof(transitions),1,f)!=1) { fprintf(stderr, "Binary input error."); return;} + if(fread(itype,sizeof(char),ftTYPELEN,f)!=ftTYPELEN) { fprintf(stderr, "Binary input error."); return;} + if(fread(otype,sizeof(char),ftTYPELEN,f)!=ftTYPELEN) { fprintf(stderr, "Binary input error."); return;} + if(fread(©_default,sizeof(copy_default),1,f)!=1) { fprintf(stderr, "Binary input error."); return;} + if(fread(&print_mode,sizeof(print_mode),1,f)!=1) { fprintf(stderr, "Binary input error."); return;} + if((tt=new TTrans_i[ttn])==NULL) { fprintf(stderr, "Cannot allocate memory for tt."); return;} + if(fread(tt,sizeof(TTrans_i),ttn,f)!=ttn) { fprintf(stderr, "Binary input error."); return; } + fclose(f); + + +} + +//--------------------------------------------------------------------------- + +template +void TFTi::save(const char* filename) +{ + FILE* f; + if(*filename) + f=fopen(filename,"wb"); + else + f=stdout; + if(!f) err("Cannot open file."); + save(f); +} + +template +void TFTi::save(FILE* f) +{ + if(fwrite(&ttn,sizeof(ttn),1,f)!=1) { fprintf(stderr,"Binary output error."); exit(1); } + if(fwrite(&states,sizeof(states),1,f)!=1) { fprintf(stderr,"Binary output error."); exit(1); } + if(fwrite(&transitions,sizeof(transitions),1,f)!=1) { fprintf(stderr,"Binary output error."); exit(1); } + if(fwrite(itype,sizeof(char),ftTYPELEN,f)!=ftTYPELEN) { fprintf(stderr,"Binary output error."); exit(1); } + if(fwrite(otype,sizeof(char),ftTYPELEN,f)!=ftTYPELEN) { fprintf(stderr,"Binary output error."); exit(1); } + if(fwrite(©_default,sizeof(copy_default),1,f)!=1) { fprintf(stderr,"Binary output error."); exit(1); } + if(fwrite(&print_mode,sizeof(print_mode),1,f)!=1) { fprintf(stderr,"Binary output error."); exit(1); } + if(fwrite(tt,sizeof(TTrans_i),ttn,f)!=ttn) { fprintf(stderr,"Binary output error."); exit(1); } + fclose(f); +} + +//--------------------------------------------------------------------------- + +template +void TFTi::clear() +{ + if(tt) delete[] tt; + ttn=0; +} + +//--------------------------------------------------------------------------- +/* +template +istream& operator>>(istream& is, TFTi& ft) +{ + long *si; // state-index relation + long ci=0; // current index + char ch; // character read; + int empty=0; // no of states with 0 trans? + char intype[FT::ftTYPELEN]; + char outtype[FT::ftTYPELEN]; + + ft.clear(); + + is >> ft.states >> ft.transitions >> intype >> outtype; + + if(strcmp(intype,ft.itype)!=0 || + strcmp(outtype,ft.otype)!=0 && strcmp(outtype,"void")!=0) + { is.clear(ios::badbit); return is; }; + + while(is.peek()==' ' || is.peek()=='\t') is.get(ch); + while(is.peek()!='\n') + { + char s[20]; + is >> s; + if(strcmp(s,"COPY")==0 && strcmp(intype,outtype)==0) ft.copy_default=true; + else if(strcmp(s,"NOCOPY")==0) ft.copy_default=false; + else if(strcmp(s,"II")==0) ft.print_mode=FT::II; + else if(strcmp(s,"OO")==0) ft.print_mode=FT::OO; + else if(strcmp(s,"IOIO")==0) ft.print_mode=FT::IOIO; + else if(strcmp(s,"OIOI")==0) ft.print_mode=FT::OIOI; + else if(strcmp(s,"IIOO")==0) ft.print_mode=FT::IIOO; + else if(strcmp(s,"OIOI")==0) ft.print_mode=FT::OIOI; + while(is.peek()==' ' || is.peek()=='\t') is.get(ch); + } + + ft.ttn=ft.transitions+2; // 1 state without trans., 1 additional + si=new long[ft.states]; + ft.tt=new TTrans_i[ft.ttn]; + + for(long cs=0;cs> ch; while(ch!='+' && ch!='-'); + switch(ch) + { + case '-': ft.tt[ci].final(false); break; + case '+': ft.tt[ci].final(true); break; + default: return is; + } + tc=0, ft.tt[ci].continued(false); + while((is.get(ch),ch==' ')) + { + if(!is) return is; + switch(is.peek()) + { + case '~': ft.tt[ci].epsi(true); ft.tt[ci].defi(true); is.get(ch); + break; + case '@': ft.tt[ci].epsi(false); ft.tt[ci].defi(true); is.get(ch); + break; + default : ft.tt[ci].geti(is); + } + if(!is) return is; + if(is.peek()=='/') + { + is.get(ch); + switch(is.peek()) + { + case '~': ft.tt[ci].epso(true); ft.tt[ci].defo(true); is.get(ch); + break; + case '@': ft.tt[ci].epso(false); ft.tt[ci].defo(true); is.get(ch); + break; + default : ft.tt[ci].geto(is); + } + } + else + { + ft.tt[ci].defo(true); + if(ft.copy_default) ft.tt[ci].epso(false); else ft.tt[ci].epso(true); + } + if(!is) return is; + + unsigned long transition; + is >> transition; + ft.tt[ci].next(transition); + + ft.tt[ci].continued(false); + + ft.tt[ci].empty(false); + if(tc>0) ft.tt[ci-1].continued(true); + tc++,ci++; + } + if(tc==0) + { + if(++empty>2) err("Nondeterministic automaton."); + ft.tt[ci].empty(true); + ci++; + } + if(ch!='\n') { is.clear(ios::badbit); return is; } + } + + ft.ttn=ft.transitions+empty; + if(ft.ttn!=ci) { is.clear(ios::badbit); return is; }; + for(long i=0;i +ostream& operator<<(ostream& os, const TFTi& ft) +{ + os << ft.states << ' ' << ft.transitions << ' ' + << ft.itype << ' ' << ft.otype << ' '; + os << (ft.copy_default ? "COPY" : "NOCOPY") << ' '; + switch(ft.print_mode) + { + case FT::II : os << "II"; break; + case FT::OO : os << "OO"; break; + case FT::IOIO: os << "IOIO"; break; + case FT::OIOI: os << "OIOI"; break; + case FT::IIOO: os << "IIOO"; break; + case FT::OOII: os << "OOII"; + } + os << ' ' << '\n'; + + long* si=new long[ft.ttn]; + long cs=0; + for(long i=0;i +class TFTiv : public TFTi +{ +public: + TFTiv() : TFTi() {}; + TFTiv(const char* filename) : TFTi(filename) {}; +}; + +//--------------------------------------------------------------------------- + +template +class TFTir : public TFTi +{ +public: + TFTir() : TFTi() {}; +}; + +//--------------------------------------------------------------------------- +#endif Index: app/src/lib/ttrans.h =================================================================== --- app/src/lib/ttrans.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/ttrans.h (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,204 @@ +#ifndef _TTransi_h +#define _TTransi_h +//--------------------------------------------------------------------------- +#include +//--------------------------------------------------------------------------- + +//! The template for a transition with input and output symbols stored internally. +/*! + A state is identified with the set of its outgoing transitions. + The state index is the index of the first transition for it. + A state with no outgoing transition is represented as an empty transition. +*/ +template +class TTrans_i +{ +public: +//private: +//! Input symbol + I i; +//! Output symbol + O o; + +public: + +//! state is final + static const unsigned char BITf=0x01; +//! transition list is continued + static const unsigned char BITc=0x02; +//! no transition + static const unsigned char BITe=0x04; +//! epsilon input + static const unsigned char BITepsi=0x08; +//! default input + static const unsigned char BITdefi=0x10; +//! epsilon output + static const unsigned char BITepso=0x20; +//! default output + static const unsigned char BITdefo=0x40; + +//! Flags + unsigned char flags; + +//! The index of the next state + long nxt; + +//! Input symbol. +//! \return The input symbol of the transition. + Ipass in() const { return i; } + +//! Output symbol. +//! \return The output symbol of the transition. + Opass out() const { return o; } + +//! Set the input symbol. +//! \param in input symbol + void in(Ipass in) { i=in; } + +//! Set the output symbol. +//! \param out output symbol + void out(Opass out) { o=out; } + +//! remark Is this needed? + I& iref() { return i; } + +//! remark Is this needed? + O& oref() { return o; } + +//! Test whether an input symbol is accepted. +//! \remark Simplified. Should rely on a test function provided by the user. + bool accepts(Ipass in) { return defi() || in==i; } + +//! Next state. +//! \return Destination state of the transition. + long next() const { return nxt; }; + +//! Set the next state. +//! \param t destination state of the transition + void next(long t) { nxt=t; }; + +//! Is the state final? +//! \return \c true if the state is final, false otherwise. + bool final() const { return flags&BITf; }; + +//! Set the \b final flag. +//! \param b \c true if the state is final, \c false otherwise. + void final(bool b) { if(b) flags|=BITf; else flags&=~BITf; }; + +//! Is the transition list continued? +//! \return \c true if the transition is not the last transition for the state, +//! \c false otherwise. + bool continued() const { return flags&BITc; }; + +//! Set the \b continuation flag. +//! \param b \c true if the transition is not the last one for the state, \c false otherwise. + void continued(bool b) { if(b) flags|=BITc; else flags&=~BITc; }; + +//! Is the transition empty? +//! \return \c true if the transition is empty (represents a state with no outgoing transitions), +//! \c false otherwise. + bool empty() const { return flags&BITe; }; + +//! Set the \b empty flag. +//! \param b \c true if the transition is empty, \c false otherwise. + void empty(bool b) { if(b) flags|=BITe; else flags&=~BITe; }; + + bool epsi() const { return flags&BITepsi; }; + void epsi(bool b) { if(b) flags|=BITepsi; else flags&=~BITepsi; }; + + bool defi() const { return flags&BITdefi; }; + void defi(bool b) { if(b) flags|=BITdefi; else flags&=~BITdefi; }; + + bool epso() const { return flags&BITepso; }; + void epso(bool b) { if(b) flags|=BITepso; else flags&=~BITepso; }; + + bool defo() const { return flags&BITdefo; }; + void defo(bool b) { if(b) flags|=BITdefo; else flags&=~BITdefo; }; + + void geti(istream&); + void geto(istream&); + +// friend ostream& operator<<(ostream& os, const TTrans_i& t); + +}; + +//--------------------------------------------------------------------------- + +template +void getsym(istream& is, char& c) +{ + is >> c; + if(c=='\\') + { + is.get(c); + switch(c) + { + case 'n':c='\n';break; + case 't':c='\t';break; + } + } +} + +template +void getsym(istream& is, T& s) +{ is >> s; } + +//--------------------------------------------------------------------------- + +template +void TTrans_i::geti(istream& is) +{ getsym(is,iref()); }; + +template +void TTrans_i::geto(istream& is) +{ getsym(is,oref()); }; + +//--------------------------------------------------------------------------- +/* +template +ostream& operator<<(ostream& os, const TTrans_i& t) +{ + os << (t.final() ? '+' : '-'); + os << ' '; + + if(!t.empty()) + { + if(t.defi()) + os << (t.epsi() ? '~' : '@'); + else + switch(t.in()) + { + case ' ': os << "\\ "; break; + case '\n': os << "\\n"; break; + case '\t': os << "\\t"; break; + default: os << t.in(); + } + + os << '/'; + + if(t.defo()) + os << (t.epso() ? '~' : '@'); + else + switch(t.out()) + { + case ' ': os << "\\ "; break; + case '\n': os << "\\n"; break; + case '\t': os << "\\t"; break; + default: os << t.out(); + } + + os << ' ' << t.next(); + } + + os << '\n'; + + if(!t.continued()) + os << '\n'; + + return os; +} +*/ + +//--------------------------------------------------------------------------- +#endif + Index: app/src/lib/word.cc =================================================================== --- app/src/lib/word.cc (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) +++ app/src/lib/word.cc (revision 25ae32e4c2354e0ed6756bbe1de83f39cd814652) @@ -0,0 +1,199 @@ +//--------------------------------------------------------------------------- +#include "word.h" +#include "auttools.h" +#include +//--------------------------------------------------------------------------- +//--------------------------------------------------------------------------- + +void Word::autodescr(const char* fo, const char* de) +{ + strcpy(f,fo); + // len=strlen(f); + + char lemd[MAXDESCRLEN]; + int i=strcspn(de,","); + strncpy(lemd,de,i); + lemd[i]='\0'; + if(isdigit(lemd[0])) + fullform(f,lemd,l); // je¶li lemat zakodowany + else + strcpy(l,lemd); // je¶li lemat w pe³nej postaci + strcpy(d,de+i+1); +} + +//--------------------------------------------------------------------------- +int Word::cmp_w(Word a, Word b) { + return (a.w_suf() > b.w_suf()); +} +//--------------------------------------------------------------------------- + +istream& operator>>(istream& is, Word& w) +{ + char temp[Word::MAXLEN+1]; + char c; + + int i=0; + while(i'; + return os; +} + +//--------------------------------------------------------------------------- +Words::~Words() { + // for (int i=0; imax && !tab[i].returned) { + max = w; + result = i; + } + } + if (result != -1) + tab[result].returned = 1; + return result; +} + +//--------------------------------------------------------------------------- +void Words::sort() { + std::sort(tab.begin(), tab.end(), Word::cmp_w); +} + +//--------------------------------------------------------------------------- + +int Words::add(const char* fo) +{ + int i = find(fo); + if(i!=-1) { + return i; + } + + if (cnt>=tab.capacity()-1) + tab.resize(tab.size()*2); + + tab[cnt].form(fo); + tab[cnt].w_suf(0.0); + + // if(cntform(fo); + tab[cnt]->w_suf(0.0); + tab[cnt]->w_pref(0.0);*/ + return cnt++; + // } + //return -1; +} + +//--------------------------------------------------------------------------- + +int Words::add(const char* fo, const char* des) +{ + char d[Word::MAXDESCRLEN]; + int l=strcspn(des,","); + int ok=1; + if( *(des+l) == ',' ) + { + strcpy(d,des+l+1); + // printf("\t%s->%s,\n", des, d); + int i=find(fo, d); + if(i!=-1) + return i; + } + else + ok=0; + + if (cnt>=tab.capacity()-1) + tab.resize(tab.size()*2); + + tab[cnt].form(fo); + if(ok) + tab[cnt].autodescr(fo, des); + else + tab[cnt].autodescr(fo, "?,?"); + + tab[cnt].w_suf(0.0); + tab[cnt].returned = 0; + /* + // if(cntform(fo); + tab[cnt]->autodescr(fo,des); + tab[cnt]->w_suf(0.0); + tab[cnt]->w_pref(0.0); + // printf("ok!\n");*/ + return cnt++; + // } + // printf("hm\n"); + return -1; +} + +//--------------------------------------------------------------------------- +void Words::prn(ostream& os) +{ + for(int i=0; i"; +} + +//--------------------------------------------------------------------------- + +ostream& operator<<(ostream& os, Words& tab) +{ + /* for(int i=0; i + +#include +//--------------------------------------------------------------------------- + +using namespace std; + +class Word +{ +public: + static const int MAXLEN=64; // dac do global + static const int MAXDESCRLEN=80; // dac do global + +private: + /// word form + char f[MAX_FORM]; // w wolnej chwili nazwy mozna zamienic na dluzsze + + /// length + int _len_suf; // dlugosc dopasowania koncowki... + // int _len_pref; // ... i prefiksu + + /// lemma + char l[MAX_FORM]; + + /// description + char d[MAX_DESC]; + + /// weight (probability) + float _w_suf; + // float _w_pref; +public: + static int cmp_w(Word a, Word b); + + Word() : _len_suf(-1) { *f='\0'; returned=0; }; + Word(const char* fo, const char* des) : _len_suf(-1) { autodescr(fo,des); _w_suf=1.0; returned=0; }; + + Word(const Word& w); + + char* form() { return f; } // przywrocic const + char* lemma() { return l; } // przywrocic const + char* descr() { return d; } + float w_suf() { return _w_suf; }; + int len_suf() { return _len_suf; } + + + void form(const char* s) { strcpy(f,s); } + void lemma(const char* s) { strcpy(l,s); } + void descr(const char* s) { strcpy(d,s); }; + void w_suf(float x) { _w_suf=x; }; + void len_suf(int n) { _len_suf=n; }; + + bool operator==(const Word& w); + bool operator!=(const Word& w); + int cmp(const Word&); + int cmpi(const Word&); + + char* operator!() { return f; }; + + operator bool() { return _len_suf>0; }; + + char* str() { return f; } + + void autodescr(const char* fo, const char* des); + + friend istream& operator>>(istream& is, Word& m); + friend ostream& operator<<(ostream& os, Word& m); + + bool returned; + +}; + +inline Word::Word(const Word& word) +{ strcpy(f,word.f); strcpy(l,word.l); strcpy(d,word.d); _len_suf=word._len_suf; _w_suf=word._w_suf; returned = 0; } + +//--------------------------------------------------------------------------- + +inline bool Word::operator==(const Word& w) +{return _len_suf==w._len_suf && + !strcmp(f,w.f) && !strcmp(l,w.l) && !strcmp(d,w.d); } + +//--------------------------------------------------------------------------- + +inline bool Word::operator!=(const Word& w) +{return _len_suf!=w._len_suf || + strcmp(f,w.f) || strcmp(l,w.l) || strcmp(d,w.d);} + +//--------------------------------------------------------------------------- + +inline int Word::cmp(const Word& w) { return strcmp(f,w.f); } + +//--------------------------------------------------------------------------- + +//inline int Word::cmpi(const Word& w) { return PL.cmpi(f,w.f); } + +//--------------------------------------------------------------------------- +//--------------------------------------------------------------------------- +//--------------------------------------------------------------------------- + +class Words +{ + private: + int find(const char* word); + int find(const char* word, const char* descr); + public: + + static const int MAX=1024; + + Words() : cnt(0) {tab.resize(MAX); }; + ~Words(); + Word& operator[](int i) { return tab[i]; } + int count() const { return cnt; } + void clear() { cnt=0; tab.clear(); } + int add(const char* fo); + int add(const char* fo, const char* des); + + /* zwraca index nastepnego wyniku, podczas pierwszego wywolania + * zwraca index wyniku o najwiekszej wadze, przy drugim wywolaniu + * wynik z druga najwyzsza waga, itd. + * Jezeli nie ma juz wynikow - zwraca -1. + */ + int next(); + + void sort(); + + void prn(ostream& os); + +// friend class Lem; +// friend class AuxLem; + friend ostream& operator<<(ostream& os, Words& tab); + vector tab; + int cnt; + +}; + +//--------------------------------------------------------------------------- + +#endif +