trafi

commit 739316c4381480a4f2b4321e5a783b2ea41f0340
parent 6b95ea4b4201cde0d2c7a387ebc9c421b07f90ae
Auteur: Loïc Daignault-Pichette <loic@asteride.xyz>
Date:   Mon, 16 Feb 2026 15:27:13 -0500

Créer un automate de symboles

Diffstat:
M
Makefile
 | 
4
++--
A
tfd.c
 | 
104
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 fichiers modifiés, 106 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 tfm.o att.o
-	${CC} ${COPTS} -o "$@" attvtfd.o tampinf.o tfm.o att.o
+attvtfd: attvtfd.o tampinf.o tfm.o att.o tfd.o
+	${CC} ${COPTS} -o "$@" attvtfd.o tampinf.o tfm.o att.o tfd.o
 
 net:
 	rm -rf attvtfd *.o *.core
diff --git a/tfd.c b/tfd.c
@@ -0,0 +1,104 @@
+#include <assert.h>
+#include <stddef.h>
+
+#include "tfd.h"
+#include "tfm.h"
+
+#define TAMPON_LNGR_DEF 64
+
+/* Créer un automate au format tfm à partir des symboles d’un tfm.
+ * Renvoie un pointeur vers un tfm, ou NULL en cas d’erreur. */
+static struct tfm *automate_symbs(struct tfm *tfm, struct tampinf **ti);
+
+/* La routine fonction en parcourant tous les symboles d’un transducteur. Pour
+ * chaque caractère du symbole courant converti à un symbole, en partant de
+ * l’état zéro de l’automate de symboles, vérifier si une transition sortante
+ * correspond au symbole courant. Si non, l’ajouter à l’automate. Sauter à
+ * l’état cible et recommencer avec le caractère suivant. Une fois arrivé au
+ * bout du symbole, marquer l’état courant comme final et placer l’identifiant
+ * du symbole dans *ti à l’indice correspondant à cet état final. */
+static struct tfm *
+automate_symbs(struct tfm *tfm, struct tampinf **ti)
+{
+	struct tfm *symbs;
+	struct trans trans;
+	struct etat etat;
+	char symb[TFM_TLL_SYMB_MAX]; /* Tampon à symbole. */
+	ssize_t lngr; /* Longueur du symbole. */
+	size_t id, idp; /* Identifiants de symbole, courant et précédent. */
+	ssize_t ids; /* Identifiant de symbole dans symbs. */
+	ssize_t ie, iep; /* Identifiants d’état, courant et précédent. */
+	size_t ic; /* Indice du caractère dans symb. */
+
+	assert(tfm);
+
+	/* Initialiser l’automate de symboles. */
+	if ((symbs = tfm_init()) == NULL)
+		return NULL;
+
+	/* Initialiser le tampon infini. */
+	if ((*ti = tampinf_init(TAMPON_LNGR_DEF, sizeof(size_t))) == NULL) {
+		tfm_libr(symbs);
+		return NULL;
+	}
+
+	/* Créer le premier état. */
+	etat.final = 0;
+	etat.ntrans = 0;
+	etat.trans = 0;
+	if (tampinf_ajt(symbs->etats, 1, &etat) < 0)
+		goto erreur;
+
+	/* Parcourir les symboles. */
+	for (idp = id = 0; (lngr = tfm_parc_symbs(tfm, &id, symb,
+		    TFM_TLL_SYMB_MAX)) > 0; idp = id) {
+		/* Parcourir les caractères. */
+		for (ie = ic = 0; ic < (size_t)lngr; ic++) {
+		    /* Obtenir l’identifiant de symbole. */
+		    if (tfm_symb_id(symbs, symb + ic, 1, &ids) < 0)
+		        goto erreur;
+		    /* Obtenir le prochain état. */
+		    if (tampinf_obt(symbs->etats, ie, 1, &etat) < 0)
+		        goto erreur;
+		    /* Parcourir les transitions. */
+		    trans.prch = etat.trans;
+		    while (etat.ntrans--) {
+		        /* Obtenir la prochaine transition. */
+		        if (tampinf_obt(symbs->trans, trans.prch, 1, &trans)
+		                < 0)
+		            goto erreur;
+		        if (trans.se == ids) {
+		            ie = trans.ed;
+		            goto pcar; /* Passer au prochain caractère. */
+		        }
+		    }
+		    /* Puisqu’aucune transition adéquate n’a été trouvée, en
+		     * créer une. */
+		    etat.final = 0;
+		    etat.ntrans = 0;
+		    etat.trans = 0;
+		    iep = ie;
+		    if ((ie = tampinf_ajt(symbs->etats, 1, &etat)) < 0)
+		        goto erreur;
+		    if (tfm_ajt(symbs, iep, ie, ids, TFM_SYMB_EPSILON) < 0)
+		        goto erreur;
+
+		    pcar:;
+		}
+		/* Marquer le dernier état d’un symbole comme final. */
+		if (tfm_mfinal(symbs, ie) < 0)
+		    goto erreur;
+		/* Associer l’identifiant du symbole à l’état. */
+		if (tampinf_plc(*ti, ie, 1, &idp) < 0)
+		   goto erreur;
+	}
+	if (lngr < 0)
+		goto erreur;
+
+	return symbs;
+
+erreur:
+	tfm_libr(symbs);
+	tampinf_libr(*ti);
+	return NULL;
+}