commit 1391d1083f7d84e0d485ccf8e05559b39a2fb2bb
parent b68fefc0121d0e9da9b75826d8d9f4d8812bb1b1
Auteur: Loïc Daignault-Pichette <loic@asteride.xyz>
Date: Fri, 10 Apr 2026 16:38:16 -0400
Mettre à jour la documentation du format tfd
Diffstat:
| M | tfd.h | | | 136 | +++++++++++++++++++++++++++++++++++++++++++++++++------------------------------ |
1 fichier modifié, 84 insertions(+), 52 suppressions(-)
diff --git a/tfd.h b/tfd.h
@@ -6,66 +6,76 @@
#include "tfm.h"
/* Le format .tfd est une représentation binaire d’un transducteur fini. Il a
- * été conçu pour être rapide à charger et à interpréter: nul besoin de le
- * désérialiser pour l’interpréter, et les structures de données qu’il utilise
- * dispensent d’un maximum de recherche. L’absence de sérialisation et de
- * désérialisation limite la portabilité du fichier. En particulier, le format
- * utilise le boutisme de l’hôte qui l’a compilé.
- *
- * Le format est composé de trois segments, indexés dans une entête placée en
- * début de fichier. Les segments sont les suivants:
- *
- * - liste des symboles,
- * - segmenteur
- * - automate
- *
+ * été conçu pour être rapide à charger et à interpréter. En particulier, son
+ * contenu n’a pas besoin d’être désérialisé pour être interprété. En revanche,
+ * l’absence de sérialisation limite la portabilité du fichier, car le boutisme
+ * de presque toutes les valeurs qu’il contient suivent le boutisme de l’hôte
+ * qui l’a compilé.
+ *
+ * Le format comprend une entête et trois segments. L’entête contient des
+ * informations sur le fichier, de même que l’emplacement et la longueur de
+ * chacun des trois segments. Les segments sont les suivants: liste des
+ * symboles, segmenteur et transducteur.
+ *
* L’entête contient les champs suivants:
*
- * 00 01 Nombre magique (0h5407)
- * 02 03 Version (0)
+ * 00 01 Nombre magique (0h5407) (petit-boutisme)
+ * 02 03 Version (0) (petit-boutisme)
* 04 05 Témoin de boutisme (0h00FF)
- * 06 09 Décalage de la liste des symboles
- * 0A 0D Taille de la liste des symboles
- * 0e 11 Décalage du segmenteur
- * 12 15 Taille du segmenteur
- * 16 19 Décalage du transducteur
- * 1A 1D Taille du transducteur
+ * 06 09 Emplacement de la liste des symboles
+ * 0A 0D Longueur de la liste des symboles
+ * 0e 11 Emplacement du segmenteur
+ * 12 15 Longueur du segmenteur
+ * 16 19 Emplacement du transducteur
+ * 1A 1D Longueur du transducteur
+ *
+ * Le nombre magique (0h5407) sert à identifier un fichier comme un fichier au
+ * format tfd. Le champ suivant indique la version du format utilisé. Le témoin
+ * de boutisme permet de détecter le boutisme de l’hôte qui a compilé le
+ * format. Celui-ci doit écrire 0h00FF dans ce champ. Le programme interpréteur
+ * peut alors vérifier si le boutisme du fichier est compatible avec
+ * l’architecture sur laquelle il tourne. S’il lit 0h00FF, il est compatible,
+ * sinon il lira 0hFF00 et saura que le boutisme est mauvais. Le sens des
+ * paires emplacement/longueur va de soi.
*/
-#define TFD_MAGIQUE 0x5407
-#define TFD_VERSION 0
-#define TFD_TEMOIN 0x00FF
-#define TFD_ENTETE_TLL 0x1E
+#define TFD_MAGIQUE 0x5407 /* Nombre magique. */
+#define TFD_VERSION 0 /* Version courante. */
+#define TFD_TEMOIN 0x00FF /* Témoin de boutisme. */
+#define TFD_ENTETE_TLL 0x1E /* Taille de l’entête. */
-/* La liste des symboles se présente comme une suite chaînes de caractères
+/* La liste de symboles et le segmenteur de symboles permettent au transducteur
+ * de manipuler des symboles de plusieurs octets. Les identifiants de symbole
+ * renvoyés par le segmenteur et reçus et renvoyés par le transducteur sont des
+ * indices dans la liste de symboles.
+ *
+ * La liste des symboles se présente comme une suite chaînes de caractères
* encodées à la Pascal, dans lesquelles les chaînes sont immédiatement
- * précédées d’un octet donnant la taille de la chaîne le suivant.
- *
- * La liste des identifiants de symbole d’entrée sont une suite d’adresses
- * relatives au début de la liste des symboles. Ces sont par ces indices que
- * les symboles d’entrée sont identifiés dans le segmenteur et dans le
- * transducteur. Elle facile la recherche dans le transducteur.
- *
- * La structure du segmenteur s’inspire de la structure à deux tableaux
- * proposée par Aho (1989: « An Efficient Digital Search Algorithm by Using a
- * Double-Array Structure »). Elle consiste en un tableau dont les cellules
- * contiennent chacune deux champs: la base (0) et l’origine (1). Chaque champ
- * occupe 2 octets, pour un total de 4 octets par cellule. Ces deux champs
- * contiennent un drapeau dans leur bit de poids faible. Celui de la base
- * marque un état comme final (1) ou comme non-final (0); celui de l’origine
- * indique si le champ doit bel et bien être interprété comme une origine (0),
- * ou comme un identifiant de symbole. Le champ base doit avoir une valeur
- * supérieure à 0, sauf si le bit de poids faible est activé: alors, c’est
- * signe que l’état ne contient pas de transition sortante. Une paire (base,
- * origine) représente un état. Un état peut être désigné par son indice i. On
- * passe d’un état à l’autre par la formule
+ * précédées d’un octet non-signé donnant la taille de la chaîne le suivant. La
+ * longueur maximale d’un symbole est donc de 255 octets. Les symboles de
+ * longueur 0 sont interdits.
+ *
+ * Le segmenteur sert à décomposer la chaîne de caractères d’entrée en chaîne
+ * de symboles intelligibles au transducteur. Sa structure s’inspire de la
+ * structure à deux tableaux proposée par Aho (1989: « An Efficient Digital
+ * Search Algorithm by Using a Double-Array Structure »). Elle consiste en un
+ * tableau dont les cellules contiennent chacune deux champs: la base (0) et
+ * l’origine (1). Chaque champ occupe 2 octets, pour un total de 4 octets par
+ * cellule. Ces deux champs contiennent un drapeau dans leur bit de poids
+ * faible. Celui de la base marque un état comme final (1) ou comme non-final
+ * (0); celui de l’origine indique si le champ doit bel et bien être interprété
+ * comme une origine (0), ou comme un identifiant de symbole. Le champ base
+ * doit avoir une valeur supérieure à 0, sauf si le bit de poids faible est
+ * activé: alors, c’est signe que l’état ne contient pas de transition
+ * sortante. Une paire (base, origine) peut être désignée par son indice i. On
+ * passe d’une paire à l’autre par la formule
*
* i' = (segm[i][0] >> 1) + s,
*
* où s est un symbole d’entrée. Pour que la transition soit valide, les
* conditions suivantes doivent aussi être satisfaites:
*
- * (segm[i'][1] & 1) == 0,
+ * (segm[i'][1] & 0x01) == 0,
* (segm[i'][1] >> 1) == i.
*
* Autrement, on pourrait quitter n’importe quel état avec n’importe quel
@@ -83,8 +93,8 @@
*
* Enfin, si
*
- * (segm[i][0] & 1) == 1 et
- * (segm[i][0] >> 1) == 0,
+ * (segm[i][0] & 0x1) == 1 et
+ * (segm[i][0] >> 1) == 0,
*
* c’est que l’état ne compte aucune transition sortante.
*
@@ -94,10 +104,32 @@
* reconnaître le symbole le plus long, ignorant ses préfixes qui sont aussi
* des symboles. Lorsque plus aucune transition n’existe qui n’accepte le
* prochain symbole d’entrée, le dernier symbole assigné est retourné et la
- * position dans le mot entrée courante au moment où ce symbole a été assigné
- * est restorée.
+ * position dans le mot courante au moment où ce symbole a été assigné est
+ * restorée.
+ *
+ * Le transducteur fini est représenté suite d’états, eux-mêmes constitués
+ * d’une liste de transitions sortantes précédée d’une entête. L’entête d’un
+ * état occupe 8 octets.
+ *
+ * 00 01 Nombre de transitions sortantes (taille de la liste)
+ * 02 03 Drapeaux (bit de poids faible: si l’état est final)
+ * 04 07 Vide
*
- * Le transducteur fini est représenté par une liste de transitions. */
+ * Les transitions d’une même liste sont ordonnées du plus petit au plus grand.
+ * Si le bit le poids faible d’un symbole est 0, le décaler d’une position vers
+ * la droite donnera un indice dans la liste de symboles; s’il est 1, il s’agit
+ * d’un symbole spécial. Les symboles spéciaux sont les suivants.
+ *
+ * AUTRE: 0
+ * EPSILON: 1
+ * IDENTITÉ: 2
+ *
+ * Une transition de la liste de transitions occupe aussi 8 octets.
+ *
+ * 00 01 Symbole d’entrée
+ * 02 03 Symbole de sortie
+ * 04 07 Identifiant d’état
+ */
/* Écrire une représentation .tfd du transducteur dans le fichier f.
* Renvoie 0, ou -1 en cas d’erreur. */
