commit 7bf4bb7e931949b6f656f4ece9a539f8244017c8
parent b6468cc7ff6c2a45edb02c0db8d6b8106ba797c2
Auteur: Loïc Daignault-Pichette <loic@asteride.xyz>
Date: Thu, 12 Feb 2026 18:44:19 -0500
Créer des transducteurs finis en mémoire
Diffstat:
| M | Makefile | | | 4 | ++-- |
| A | tfm.c | | | 181 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | tfm.h | | | 80 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
3 fichiers modifiés, 263 insertions(+), 2 suppressions(-)
diff --git a/Makefile b/Makefile
@@ -9,8 +9,8 @@ COPTS = -Wall -Wextra -Wpedantic -std=c99 -O0 #-DNDEBUG -O3 -flto
tout: attvtfd
-attvtfd: attvtfd.o tampinf.o
- ${CC} ${COPTS} -o "$@" attvtfd.o tampinf.o
+attvtfd: attvtfd.o tampinf.o tfm.o
+ ${CC} ${COPTS} -o "$@" attvtfd.o tampinf.o tfm.o
net:
rm -rf attvtfd *.o *.core
diff --git a/tfm.c b/tfm.c
@@ -0,0 +1,181 @@
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "tfm.h"
+#include "tampinf.h"
+
+#define TAMPON_LNGR_DEF 64 /* Longueur par défaut des tampons. */
+
+#define TFM_COHERENT(tfm) \
+ assert((tfm)); \
+ assert((tfm)->etats); \
+ assert((tfm)->trans); \
+ assert((tfm)->symbs);
+
+/* Chercher un symbole symb de longueur lngr dans le transducteur tfm.
+ * Renvoie la position du symbole dans tfm->symbs, ou -1 s’il ne s’y trouve
+ * pas. */
+static ssize_t tfm_symb_chercher(struct tampinf *ti, char *symb, size_t lngr);
+
+struct tfm *
+tfm_init(void)
+{
+ struct tfm *tfm;
+
+ if ((tfm = malloc(sizeof(struct tfm))) == NULL)
+ return NULL;
+
+ if ((tfm->etats = tampinf_init(TAMPON_LNGR_DEF,
+ sizeof(struct etat))) == NULL) {
+ free(tfm);
+ return NULL;
+ }
+ if ((tfm->trans = tampinf_init(TAMPON_LNGR_DEF,
+ sizeof(struct trans))) == NULL) {
+ tampinf_libr(tfm->etats);
+ free(tfm);
+ return NULL;
+ }
+ if ((tfm->symbs = tampinf_init(TAMPON_LNGR_DEF,
+ sizeof(char))) == NULL) {
+ tampinf_libr(tfm->etats);
+ tampinf_libr(tfm->trans);
+ free(tfm);
+ return NULL;
+ }
+
+ TFM_COHERENT(tfm);
+
+ return tfm;
+}
+
+void
+tfm_libr(struct tfm *tfm)
+{
+ TFM_COHERENT(tfm);
+
+ tampinf_libr(tfm->etats);
+ tampinf_libr(tfm->trans);
+ tampinf_libr(tfm->symbs);
+ free(tfm);
+}
+
+int
+tfm_ajt(struct tfm *tfm, size_t es, size_t ed, ssize_t se, ssize_t ss)
+{
+ ssize_t itrans;
+ struct etat etat;
+ struct trans trans;
+ TFM_COHERENT(tfm);
+
+ /* Obtenir l’état source. */
+ if (tampinf_obt(tfm->etats, es, 1, &etat) < 0)
+ return -1;
+
+ /* Construire la nouvelle transition. */
+ trans.se = se;
+ trans.ss = ss;
+ trans.ed = ed;
+ trans.prch = etat.trans;
+
+ /* Ajouter la transition. */
+ if ((itrans = tampinf_ajt(tfm->trans, 1, &trans)) < 0)
+ return -1;
+
+ /* Mettre à jour l’état. */
+ etat.trans = itrans;
+ etat.ntrans++;
+ if (tampinf_plc(tfm->etats, es, 1, &etat) < 0)
+ return -1;
+
+ TFM_COHERENT(tfm);
+
+ return 0;
+}
+
+int
+tfm_symb_id(struct tfm *tfm, char *symb, size_t lngr, ssize_t *id)
+{
+ ssize_t pos;
+ unsigned char n;
+
+ TFM_COHERENT(tfm);
+ assert(symb);
+ assert(lngr > 0);
+ assert(id);
+
+ /* Si la taille est 1, l’identifiant du symbole est le symbole lui-même. */
+ if (lngr == 1) {
+ *id = *symb;
+ return 0;
+ }
+
+ if ((pos = tfm_symb_chercher(tfm->symbs, symb, lngr)) >= 0)
+ goto fin;
+
+ /* Le symbole n’a pas été trouvé: l’ajouter. */
+ n = lngr;
+ if ((pos = tampinf_ajt(tfm->symbs, 1, &n)) < 0)
+ return -1;
+ if (tampinf_ajt(tfm->symbs, lngr, symb) < 0)
+ return -1;
+
+fin:
+ TFM_COHERENT(tfm);
+ *id = -pos;
+ return 0;
+}
+
+int
+tfm_mfinal(struct tfm *tfm, size_t ietat)
+{
+ struct etat etat;
+
+ TFM_COHERENT(tfm);
+
+ /* Obtenir, modifier, puis écrire l’état. */
+ if (tampinf_obt(tfm->etats, ietat, 1, &etat) < 0)
+ return -1;
+ etat.final = 1;
+ if (tampinf_plc(tfm->etats, ietat, 1, &etat) < 0)
+ return -1;
+
+ TFM_COHERENT(tfm);
+ return 0;
+}
+
+int
+tfm_tfinal(struct tfm *tfm, size_t ietat)
+{
+ struct etat etat;
+
+ TFM_COHERENT(tfm);
+
+ /* Obtenir l’état. */
+ if (tampinf_obt(tfm->etats, ietat, 1, &etat) < 0)
+ return -1;
+
+ return etat.final;
+}
+
+static ssize_t
+tfm_symb_chercher(struct tampinf *ti, char *symb, size_t lngr)
+{
+ char *ctn;
+ unsigned pos;
+ unsigned n;
+
+ assert(symb);
+ assert(lngr > 1);
+
+ ctn = tampinf_ctn(ti);
+
+ for (pos = 0; tampinf_dedans(ti, pos); pos += n + 1) {
+ n = ((unsigned char *)ctn)[pos];
+ if (strncmp(symb, ctn + pos, n) == 0)
+ return 0;
+ }
+
+ return -1;
+}
diff --git a/tfm.h b/tfm.h
@@ -0,0 +1,80 @@
+#ifndef TFM_H
+#define TFM_H
+
+#include <stdbool.h>
+
+#include "tampinf.h"
+
+/* L’accronyme « tfm » veut dire « transducteur fini en mémoire ». */
+
+/* Liste de symboles spéciaux. */
+#define TFM_SYMB_EPSILON -1
+#define TFM_SYMB_ETOILE -2
+
+/* Une structure tfm représente un transducteur fini et renferme trois tampons
+ * infinis pour y stocker les états, les transitions entre les états et les
+ * symboles de plus d’un octet. Les symboles sont stocké à 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. Tous les symboles stockés
+ * de cette manière font au moins 2 octets. */
+
+struct tfm {
+ struct tampinf *etats;
+ struct tampinf *trans;
+ struct tampinf *symbs;
+};
+
+/* Un état contient l’identifiant d’une liste chaînée de ses transitions
+ * sortantes. Il donne aussi le nombre de transitions que cette liste
+ * contient. Il peut enfin est marqué comme final. */
+
+struct etat {
+ size_t trans; /* Liste chaînée de transitions. */
+ size_t ntrans; /* Nombre de transitions. */
+ bool final; /* État final? */
+};
+
+/* Les transitions qui partagent un même état source forment une liste chaînée,
+ * dont la taille est donnée dans cet état source. Les transitions ne sont pas
+ * nécessairement ordonnées. Si un symbole est long d’un octet, il est placé
+ * directement dans se ou dans ss; s’il est plus long, il est stocké dans le
+ * tampon symbs d’un tfm et c’est la négation de l’identifiant de ce symbole qui
+ * est placé dans se ou dans ss. C’est le signe qui distingue les deux
+ * méthodes. */
+
+struct trans {
+ ssize_t se; /* Symbole d’entrée. */
+ ssize_t ss; /* Symbole de sortie. */
+ size_t ed; /* État destination. */
+ size_t prch; /* Prochaine transition. */
+};
+
+/* Initialiser un tfm.
+ * Renvoie un pointeur vers le transducteur initialisé, ou NULL en cas
+ * d’erreur. */
+struct tfm *tfm_init(void);
+
+/* Libérer un transducteur. */
+void tfm_libr(struct tfm *tfm);
+
+/* Ajouter une transition de l’état es à l’état ed avec les symboles d’entrée et
+ * de sortie se et ss au transducteur tfm.
+ * 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 id d’un symbole symb de longueur lngr dans le
+ * transducteur tfm.
+ * Si le symbole est inconnu du transducteur, il est y ajouté de manière
+ * transparente. Renvoie 0, ou -1 en cas d’erreur. */
+int tfm_symb_id(struct tfm *tfm, char *symb, size_t lngr, ssize_t *id);
+
+/* Marquer un état comme final.
+ * Renvoie 0, ou -1 en cas d’erreur. */
+int tfm_mfinal(struct tfm *tfm, size_t ietat);
+
+/* Tester si un état est final.
+ * Renvoie un booléen, ou -1 en cas d’erreur. */
+int tfm_tfinal(struct tfm *tfm, size_t ietat);
+
+#endif
