tfm.h (4168B)
1 #ifndef TFM_H 2 #define TFM_H 3 4 #include <stdbool.h> 5 #include <stddef.h> 6 #include <sys/types.h> 7 8 /* L’accronyme « tfm » veut dire « transducteur fini en mémoire ». */ 9 10 /* Liste de symboles spéciaux. */ 11 #define TFM_SYMB_AUTRE ((0 << 1) | TFM_SSPECIAL) 12 #define TFM_SYMB_EPSILON ((1 << 1) | TFM_SSPECIAL) 13 #define TFM_SYMB_IDENTITE ((2 << 1) | TFM_SSPECIAL) 14 15 #define TFM_SSPECIAL 0x00 /* Symbole spécial. */ 16 #define TFM_SNORMAL 0x01 /* Symbole normal. */ 17 18 /* Une structure tfm représente un transducteur fini et renferme trois tampex 19 * pour y stocker les états, les transitions entre les états et les symboles. 20 * Les symboles sont stockés à la Pascal, c’est-à-dire que les caractères d’une 21 * chaîne sont précédés d’un octet non-signé qui en indique la taille. Un 22 * symbole peut donc contenir le caractère NUL, mais il est limité à une 23 * longueur maximale de 255 octets. */ 24 25 #define TFM_TLL_SYMB_MAX 255 /* Taille maximale d’un symbole. */ 26 27 struct tfm { 28 struct etat *etats; /* Liste des états. */ 29 struct trans *trans; /* Liste des transitions. */ 30 char *symbs; /* Liste des symboles. */ 31 bool trie; /* Si les transitions de tous les états sont triées. */ 32 }; 33 34 /* Un état contient l’identifiant de sa première transition sortante, qui est 35 * en tête d’une liste chaînée rassemblant toutes ses transitions sortantes. Si 36 * la liste est vide, trans prend la valeur de -1. Il donne aussi le nombre de 37 * transitions que cette liste contient. Il peut enfin être marqué comme final 38 * ou trié. trans est un indice dans le tampon tfm->trans. */ 39 40 struct etat { 41 ssize_t trans; /* Liste chaînée de transitions. */ 42 size_t ntrans; /* Nombre de transitions. */ 43 bool existe; /* Si l’état existe. */ 44 bool final; /* État final? */ 45 bool trie; /* Si les transitions sont triées. */ 46 }; 47 48 /* Les transitions qui partagent un même état source forment une liste chaînée 49 * et dont la taille est donnée par le champ ntrans de cet état source. Elles 50 * contiennent un symbole d’entrée et un symbole de sortie. Si le bit de poids 51 * faible d’un symbole est 1, le décaler d’une position vers la droite donnera 52 * un indice dans tfm->trans; s’il est 0, il s’agit d’un symbole spécial. ed 53 * est un indice dans le tampon tfm->etats. prch est un indice dans le tampon 54 * tfm->trans. Une valeur de -1 indique qu’il n’y a pas de prochaine 55 * transition. */ 56 57 struct trans { 58 size_t se; /* Symbole d’entrée. */ 59 size_t ss; /* Symbole de sortie. */ 60 size_t ed; /* État destination. */ 61 ssize_t prch; /* Prochaine transition. */ 62 }; 63 64 /* Initialiser un tfm. 65 * Renvoie un pointeur vers le transducteur initialisé, ou NULL en cas 66 * d’erreur. */ 67 struct tfm *tfm_init(void); 68 69 /* Libérer un transducteur. */ 70 void tfm_libr(struct tfm *tfm); 71 72 /* Ajouter au transducteur tfm une transition de l’état es à l’état ed avec les 73 * symboles d’entrée et de sortie se et ss. 74 * Renvoie 0, ou -1 en cas d’erreur. */ 75 int tfm_ajt(struct tfm *tfm, size_t es, size_t ed, ssize_t se, ssize_t ss); 76 77 /* Obtenir l’identifiant d’un symbole symb de longueur lngr dans le 78 * transducteur tfm. Si le symbole est inconnu du transducteur, il y est ajouté 79 * de manière transparente. 80 * Renvoie l’identifiant, ou -1 en cas d’erreur. 81 * Prend pour acquis que lngr n’est pas plus grand que TFM_TLL_SYMB_MAX. */ 82 ssize_t tfm_symb_id(struct tfm *tfm, char *symb, size_t lngr); 83 84 /* Placer le symbole du transducteur tfm correspondant à l’identifiant id dans 85 * le tampon symb, de taille max. 86 * Prend pour acquis que id est valide. Ne fonctionne pas pour les symboles 87 * spéciaux. Renvoie la taille du symbole, ou -1 en cas d’erreur. */ 88 ssize_t tfm_symb_obt(struct tfm *tfm, size_t id, char *symb, size_t max); 89 90 /* Marquer un état comme final. 91 * Renvoie 0, ou -1 en cas d’erreur. */ 92 int tfm_mfinal(struct tfm *tfm, size_t ietat); 93 94 /* Tester si un état est final. 95 * Renvoie un booléen, ou -1 en cas d’erreur. */ 96 int tfm_tfinal(struct tfm *tfm, size_t ietat); 97 98 /* Trier du plus grand au plus petit les transitions de tous les états du 99 * transducteur tfm. */ 100 void tfm_trier(struct tfm *tfm); 101 102 #endif