commit 8055e62c92a91be5da513e22c24a41b74a9b45c5
parent ebf979c814c6c17fcbc50c985004393d8d07f800
Auteur: Loïc Daignault-Pichette <loic@asteride.xyz>
Date: Fri, 10 Apr 2026 17:02:17 -0400
Mettre à jour la documentation du tfm
Diffstat:
| M | tfm.h | | | 61 | ++++++++++++++++++++++++++++--------------------------------- |
1 fichier modifié, 28 insertions(+), 33 suppressions(-)
diff --git a/tfm.h b/tfm.h
@@ -8,16 +8,19 @@
/* L’accronyme « tfm » veut dire « transducteur fini en mémoire ». */
/* Liste de symboles spéciaux. */
-#define TFM_SYMB_EPSILON -1
-#define TFM_SYMB_IDENTITE -2
-#define TFM_SYMB_AUTRE -3
+#define TFM_SYMB_AUTRE ((0 << 1) | TFM_SSPECIAL)
+#define TFM_SYMB_EPSILON ((1 << 1) | TFM_SSPECIAL)
+#define TFM_SYMB_IDENTITE ((2 << 1) | TFM_SSPECIAL)
+
+#define TFM_SSPECIAL 0x00 /* Symbole spécial. */
+#define TFM_SNORMAL 0x01 /* Symbole normal. */
/* Une structure tfm représente un transducteur fini et renferme trois tampex
* pour y stocker les états, les transitions entre les états et les symboles.
* Les symboles sont stockés à la Pascal, c’est-à-dire que les caractères d’une
- * chaîne sont précédés d’un octet qui en indique la taille. Un symbole peut
- * donc contenir le caractère NUL, mais il est limité à une longueur maximale
- * de 255 octets. */
+ * chaîne sont précédés d’un octet non-signé qui en indique la taille. Un
+ * symbole peut donc contenir le caractère NUL, mais il est limité à une
+ * longueur maximale de 255 octets. */
#define TFM_TLL_SYMB_MAX 255 /* Taille maximale d’un symbole. */
@@ -29,12 +32,13 @@ struct tfm {
};
/* Un état contient l’identifiant de sa première transition sortante, qui est
- * en tête d’une liste chaînée rassemblant toutes ses transitions sortantes. Il
- * donne aussi le nombre de transitions que cette liste contient. Il peut enfin
- * être marqué comme final. trans est un indice dans le tampon tfm->trans. */
+ * en tête d’une liste chaînée rassemblant toutes ses transitions sortantes. Si
+ * la liste est vide, trans prend la valeur de -1. Il donne aussi le nombre de
+ * transitions que cette liste contient. Il peut enfin être marqué comme final
+ * ou trié. trans est un indice dans le tampon tfm->trans. */
struct etat {
- ssize_t trans; /* Liste chaînée de transitions. -1 marque la fin. */
+ ssize_t trans; /* Liste chaînée de transitions. */
size_t ntrans; /* Nombre de transitions. */
bool existe; /* Si l’état existe. */
bool final; /* État final? */
@@ -42,18 +46,19 @@ struct etat {
};
/* Les transitions qui partagent un même état source forment une liste chaînée
- * et dont la taille est donnée par le champ ntrans de cet état source. Les
- * transitions d’une liste ne suivent pas d’ordre particulier. S’ils sont
- * positifs, se et ss sont des indices dans le tampon tfm->symbs; s’ils sont
- * strictement négatifs, ils contiennent des symboles spéciaux. ed est un
- * indice dans le tampon tfm->etats. prch est un indice dans le tampon
- * tfm->trans. */
+ * et dont la taille est donnée par le champ ntrans de cet état source. Elles
+ * contiennent un symbole d’entrée et un symbole de sortie. Si le bit de poids
+ * faible d’un symbole est 1, le décaler d’une position vers la droite donnera
+ * un indice dans tfm->trans; s’il est 0, il s’agit d’un symbole spécial. ed
+ * est un indice dans le tampon tfm->etats. prch est un indice dans le tampon
+ * tfm->trans. Une valeur de -1 indique qu’il n’y a pas de prochaine
+ * transition. */
struct trans {
- ssize_t se; /* Symbole d’entrée. */
- ssize_t ss; /* Symbole de sortie. */
+ size_t se; /* Symbole d’entrée. */
+ size_t ss; /* Symbole de sortie. */
size_t ed; /* État destination. */
- ssize_t prch; /* Prochaine transition. -1 marque la fin. */
+ ssize_t prch; /* Prochaine transition. */
};
/* Initialiser un tfm.
@@ -67,13 +72,11 @@ void tfm_libr(struct tfm *tfm);
/* Ajouter au transducteur tfm une transition de l’état es à l’état ed avec les
* symboles d’entrée et de sortie se et ss.
* Renvoie 0, ou -1 en cas d’erreur. */
-
int tfm_ajt(struct tfm *tfm, size_t es, size_t ed, ssize_t se, ssize_t ss);
/* Obtenir l’identifiant d’un symbole symb de longueur lngr dans le
- * transducteur tfm.
- * Si le symbole est inconnu du transducteur, il y est ajouté de manière
- * transparente.
+ * transducteur tfm. Si le symbole est inconnu du transducteur, il y est ajouté
+ * de manière transparente.
* Renvoie l’identifiant, ou -1 en cas d’erreur.
* Prend pour acquis que lngr n’est pas plus grand que TFM_TLL_SYMB_MAX. */
ssize_t tfm_symb_id(struct tfm *tfm, char *symb, size_t lngr);
@@ -84,15 +87,6 @@ ssize_t tfm_symb_id(struct tfm *tfm, char *symb, size_t lngr);
* spéciaux. Renvoie la taille du symbole, ou -1 en cas d’erreur. */
ssize_t tfm_symb_obt(struct tfm *tfm, size_t id, char *symb, size_t max);
-/* Parcourir les symboles du transducteurs tfm.
- * Un symbole est placé dans le tampon symb, de taille max, à chaque appel.
- * L’identifiant id est un pointeur vers l’identifiant du prochain symbole à
- * lire. Il est normalement initialisé à 0 avant le parcours. Cette fonction
- * n’exporte que les symboles non-spéciaux.
- * Renvoie la taille du symbole, 0 s’il ne reste plus de symbole à lire, ou -1
- * en cas d’erreur. */
-ssize_t tfm_parc_symbs(struct tfm *tfm, size_t *id, char *symb, size_t max);
-
/* Marquer un état comme final.
* Renvoie 0, ou -1 en cas d’erreur. */
int tfm_mfinal(struct tfm *tfm, size_t ietat);
@@ -101,7 +95,8 @@ int tfm_mfinal(struct tfm *tfm, size_t ietat);
* Renvoie un booléen, ou -1 en cas d’erreur. */
int tfm_tfinal(struct tfm *tfm, size_t ietat);
-/* Trier les transitions de tous les états du transducteur tfm. */
+/* Trier du plus grand au plus petit les transitions de tous les états du
+ * transducteur tfm. */
void tfm_trier(struct tfm *tfm);
#endif
