tfd.h (7375B)
1 #ifndef TFD_H 2 #define TFD_H 3 4 #include <stdio.h> 5 6 #include "tfm.h" 7 8 /* Le format .tfd est une représentation binaire d’un transducteur fini. Il a 9 * été conçu pour être rapide à charger et à interpréter. En particulier, son 10 * contenu n’a pas besoin d’être désérialisé pour être interprété. En revanche, 11 * l’absence de sérialisation limite la portabilité du fichier, car le boutisme 12 * de presque toutes les valeurs qu’il contient suivent le boutisme de l’hôte 13 * qui l’a compilé. 14 * 15 * Le format comprend une entête et cinq segments. L’entête contient des 16 * informations sur le fichier, de même que l’emplacement et la longueur de 17 * chacun des trois segments. Les segments sont les suivants: liste des 18 * symboles, liste d’identifiants de symbole d’entrée, liste d’identifiant de 19 * symbole de sortie, segmenteur et transducteur. 20 * 21 * L’entête contient les champs suivants: 22 * 23 * 00 01 Nombre magique (0h5407) (petit-boutisme) 24 * 02 03 Version (0) (petit-boutisme) 25 * 04 05 Témoin de boutisme (0h00FF) 26 * 06 09 Emplacement de la liste des symboles 27 * 0A 0D Longueur de la liste des symboles 28 * 0E 11 Emplacement de la liste d’identifiants de symbole d’entrée 29 * 12 15 Longueur de la liste d’identifiants de symbole d’entrée 30 * 16 19 Emplacement de la liste d’identifiants de symbole de sortie 31 * 1A 1D Longueur de la liste d’identifiants de symbole de sortie 32 * 1E 21 Emplacement du segmenteur 33 * 22 25 Longueur du segmenteur 34 * 26 29 Emplacement du transducteur 35 * 2A 2D Longueur du transducteur 36 * 37 * Le nombre magique (0h5407) sert à identifier un fichier comme un fichier au 38 * format tfd. Le champ suivant indique la version du format utilisé. Le témoin 39 * de boutisme permet de détecter le boutisme de l’hôte qui a compilé le 40 * format. Celui-ci doit écrire 0h00FF dans ce champ. Le programme interpréteur 41 * peut alors vérifier si le boutisme du fichier est compatible avec 42 * l’architecture sur laquelle il tourne. S’il lit 0h00FF, il est compatible, 43 * sinon il lira 0hFF00 et saura que le boutisme est mauvais. Le sens des 44 * paires emplacement/longueur va de soi. 45 */ 46 47 #define TFD_MAGIQUE 0x5407 /* Nombre magique. */ 48 #define TFD_VERSION 0 /* Version courante. */ 49 #define TFD_TEMOIN 0x00FF /* Témoin de boutisme. */ 50 #define TFD_ENTETE_TLL 0x2E /* Taille de l’entête. */ 51 52 /* La liste de symboles et le segmenteur de symboles permettent au transducteur 53 * de manipuler des symboles de plusieurs octets. Les identifiants de symbole 54 * renvoyés par le segmenteur et reçus et renvoyés par le transducteur sont des 55 * indices dans la liste de symboles. 56 * 57 * La liste d’identifiants de symbole d’entrée est incluse pour permettre la 58 * génération de mots d’entrée. 59 * 60 * La liste d’identifiants de symbole de sortie est incluse pour permettre la 61 * génération de mots de sortie en présence du symbole spécial AUTRE. 62 * 63 * La liste des symboles se présente comme une suite chaînes de caractères 64 * encodées à la Pascal, dans lesquelles les chaînes sont immédiatement 65 * précédées d’un octet non-signé donnant la taille de la chaîne le suivant. La 66 * longueur maximale d’un symbole est donc de 255 octets. Les symboles de 67 * longueur 0 sont interdits. 68 * 69 * Le segmenteur sert à décomposer la chaîne de caractères d’entrée en chaîne 70 * de symboles intelligibles au transducteur. Sa structure s’inspire de la 71 * structure à deux tableaux proposée par Aho (1989: « An Efficient Digital 72 * Search Algorithm by Using a Double-Array Structure »). Elle consiste en un 73 * tableau dont les cellules contiennent chacune deux champs: la base (0) et 74 * l’origine (1). Chaque champ occupe 2 octets, pour un total de 4 octets par 75 * cellule. Ces deux champs contiennent un drapeau dans leur bit de poids 76 * faible. Celui de la base marque un état comme final (1) ou comme non-final 77 * (0); celui de l’origine indique si le champ doit bel et bien être interprété 78 * comme une origine (0), ou comme un identifiant de symbole. Le champ base 79 * doit avoir une valeur supérieure à 0, sauf si le bit de poids faible est 80 * activé: alors, c’est signe que l’état ne contient pas de transition 81 * sortante. Une paire (base, origine) peut être désignée par son indice i. On 82 * passe d’une paire à l’autre par la formule 83 * 84 * i' = (segm[i][0] >> 1) + s, 85 * 86 * où s est un symbole d’entrée. Pour que la transition soit valide, les 87 * conditions suivantes doivent aussi être satisfaites: 88 * 89 * (segm[i'][1] & 0x01) == 0, 90 * (segm[i'][1] >> 1) == i. 91 * 92 * Autrement, on pourrait quitter n’importe quel état avec n’importe quel 93 * symbole. 94 * 95 * Si, cependant, le drapeau de la base d’un symbole est brandi, il s’agit 96 * d’un état final et 97 * 98 * i'' = segm[i'][0] >> 1 et 99 * symbole = segm[i''][1] >> 1. 100 * 101 * C’est-à-dire que le champ origine de l’état vers lequel il pointe représente 102 * en fait un symbole et que le champ base contient l’identifiant le l’état 103 * suivant. 104 * 105 * Enfin, si 106 * 107 * (segm[i][0] & 0x1) == 1 et 108 * (segm[i][0] >> 1) == 0, 109 * 110 * c’est que l’état ne compte aucune transition sortante. 111 * 112 * La variable symbole contient l’identifiant du symbole. Lors de 113 * l’interprétation du segmenteur, elle est mise à jour chaque fois qu’un état 114 * final est rencontré. Le segmenteur est en effet glouton: il tente de 115 * reconnaître le symbole le plus long, ignorant ses préfixes qui sont aussi 116 * des symboles. Lorsque plus aucune transition n’existe qui n’accepte le 117 * prochain symbole d’entrée, le dernier symbole assigné est retourné et la 118 * position dans le mot courante au moment où ce symbole a été assigné est 119 * restorée. 120 * 121 * Le transducteur fini est représenté suite d’états, eux-mêmes constitués 122 * d’une liste de transitions sortantes précédée d’une entête. L’entête d’un 123 * état occupe 8 octets. 124 * 125 * 00 01 Nombre de transitions sortantes (taille de la liste) 126 * 02 03 Drapeaux (bit de poids faible: si l’état est final) 127 * 04 07 Vide 128 * 129 * Les transitions d’une même liste sont ordonnées du plus grand au plus petit. 130 * Si le bit le poids faible d’un symbole est 1, le décaler d’une position vers 131 * la droite donnera un indice dans la liste de symboles; s’il est 0, il s’agit 132 * d’un symbole spécial. Les symboles spéciaux sont les suivants. 133 * 134 * AUTRE: 0 135 * EPSILON: 1 136 * IDENTITÉ: 2 137 */ 138 139 #define TFD_SYMB_AUTRE ((0 << 1) | TFD_SSPECIAL) 140 #define TFD_SYMB_EPSILON ((1 << 1) | TFD_SSPECIAL) 141 #define TFD_SYMB_IDENTITE ((2 << 1) | TFD_SSPECIAL) 142 143 #define TFD_SSPECIAL 0x00 /* Symbole spécial. */ 144 #define TFD_SNORMAL 0x01 /* Symbole normal. */ 145 146 /* Une transition de la liste de transitions occupe aussi 8 octets. 147 * 148 * 00 01 Symbole d’entrée 149 * 02 03 Symbole de sortie 150 * 04 07 Identifiant d’état 151 * 152 * Pour faciliter l’interprétation du transducteur, le premier état doit être 153 * le suivant: 154 * 155 * 00 01 1 156 * 02 07 0 157 * 08 09 TFD_SYMB_EPSILON 158 * 0A 0B TFD_SYMB_EPSILON 159 * 0C 0F 2 160 */ 161 162 /* Écrire une représentation .tfd du transducteur dans le fichier f. 163 * Renvoie 0, ou -1 en cas d’erreur. */ 164 int tfd_ecrire(FILE *f, struct tfm *tfm); 165 166 #endif