commit c854ce34459acf777d0c39b035d719e4169a7c20
parent 53c246c8978eeebefb90199c2e52a289712c57f6
Auteur: Loïc Daignault-Pichette <loic@asteride.xyz>
Date: Tue, 7 Apr 2026 22:04:11 -0400
Simplifier la construction du segmenteur
Diffstat:
| M | tfd.c | | | 451 | +++++++++++++++++++++++++++++++++++-------------------------------------------- |
| M | tfd.h | | | 99 | +++++++++++++++++++++++++++----------------------------------------------------- |
2 fichiers modifiés, 230 insertions(+), 320 suppressions(-)
diff --git a/tfd.c b/tfd.c
@@ -1,36 +1,24 @@
#include <assert.h>
+#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
-#include <stdlib.h>
#include <string.h>
#include "tampex.h"
#include "tfd.h"
#include "tfm.h"
-#define TAMPON_LNGR_DEF 1
+#define TAMPON_LNGR_DEF 64
-/* Obtenir la liste des symboles du transducteur tfm.
- * corr est un tampex qui donne la correspondance entre les identifiants de
- * symbole du tfm (id) et leur indice (i) dans la liste, de telle sorte que
- * corr[id] == i.
- * Renvoie un pointeur vers un tampex contenant cette liste, ou NULL en cas
- * d’erreur. */
-static char *symboles_liste(struct tfm *tfm, uint32_t **corr);
-
-/* Obtenir la liste des identifiants de symbole d’entrée du transducteur tfm.
- * Renvoie un pointeur vers un tampex contenant cette liste, ou NULL en cas
- * d’erreur. */
-static int symboles_id(struct tfm *tfm, uint32_t *corr, uint16_t **se);
+/* Écrire la valeur val dans le tampon te, en préservant le boutisme de
+ * l’hôte. ecrire_16() écrit deux octets et ecrire_32() en écrit 4.
+ * Renvoie un pointer vers l’octet suivant le dernier écrit. */
+static uint8_t *ecrire_16(uint8_t *tp, uint16_t val);
+static uint8_t *ecrire_32(uint8_t *tp, uint32_t val);
-/* Créer le segmenteur à partir d’une liste de symboles d’entrée.
+/* Créer le segmenteur de symboles.
* Renvoie un pointeur vers un tampex, ou NULL en cas d’erreur. */
-static uint16_t (*segmenteur(char *liste, uint16_t *se))[2];
-
-/* Tester si la paire à l’indice i dans le segmenteur segm est libre.
- * Renvoie 1 si elle est libre et 0 si elle ne l’est pas, ou -1 en cas
- * d’erreur. */
-static int segmenteur_tlibre(uint16_t (**segm)[2], size_t i);
+static void *segmenteur(struct tfm *tfm);
/* Trouver une paire libre dans le segmenteur.
* Renvoie l’indice de la paire trouvée, ou -1 en cas d’erreur. */
@@ -42,23 +30,27 @@ static ssize_t segmenteur_libre(uint16_t (**segm)[2]);
static ssize_t segmenteur_base(uint16_t (**segm)[2], struct tfm *tfm,
size_t ietat);
-/* Créer un automate au formant tfm à partir d’une liste de symboles d’entrée.
- * Renvoie un pointeur vers un tfm, ou NULL en cas d’erreur, et donne la liste
- * des identifiants des de symbole associés aux états finaux dans ids. */
-static struct tfm *automate_symbs(char *liste, uint16_t *se,
- uint32_t **finaux);
+/* Tester si la paire à l’indice i dans le segmenteur segm est libre.
+ * Renvoie 1 si elle est libre et 0 si elle ne l’est pas, ou -1 en cas
+ * d’erreur. */
+static int segmenteur_tlibre(uint16_t (**segm)[2], size_t i);
+
+/* Créer un automate au format tfm à partir d’une liste de symboles d’entrée.
+ * Renvoie un pointeur vers un tfm, ou NULL en cas d’erreur. */
+static struct tfm *automate_symbs(struct tfm *tfm, uint32_t **finaux);
+
+/* Créer la liste des identifiants de symbole utilisés comme symboles d’entrée.
+ * Renvoie un pointeur vers un tampex, ou NULL en cas d’erreur. */
+static uint16_t *symboles_entree(struct tfm *tfm);
int
tfd_ecrire(FILE *f, struct tfm *tfm)
{
- unsigned char entete[TFD_ENTETE_TLL]; /* Contenu de l’entête. */
- size_t dec; /* Décalage actuel dans le fichier. */
- char *liste; /* Tampons extensibles. */
- uint16_t *tse; /* Autres tampons extensibles. */
- uint32_t *corr; /* Correspondance entre les identifiants de symbole. */
- uint16_t (*segm)[2]; /* Segmenteur. */
- size_t lngr; /* Longueur du tampon. */
- ssize_t res; /* Résultat d’une opérations. */
+ uint8_t ent[TFD_ENTETE_TLL]; /* Contenu de l’entête. */
+ uint8_t *pent; /* Pointeur vers l’entête. */
+ size_t dec; /* Décalage courant dans le fichier. */
+ void *te; /* Pointeur réutilisable vers un tampon extensible. */
+ size_t lngr; /* Longueur d’un tampon. */
assert(f);
assert(tfm);
@@ -67,204 +59,97 @@ tfd_ecrire(FILE *f, struct tfm *tfm)
if (fseek(f, dec, SEEK_SET) != 0)
return -1;
+ pent = ent;
+
/* Écrire le nombre magique. */
- entete[0x00] = (TFD_MAGIQUE >> 8) & 0xFF;
- entete[0x01] = (TFD_MAGIQUE >> 0) & 0xFF;
+ *pent++ = (TFD_MAGIQUE >> 8) & 0xFF;
+ *pent++ = (TFD_MAGIQUE >> 0) & 0xFF;
/* Écrire la version. */
- entete[0x02] = (TFD_VERSION >> 8) & 0xFF;
- entete[0x03] = (TFD_VERSION >> 0) & 0xFF;
-
- /* Écrire la liste de symboles. */
- entete[0x04] = (dec >> 24) & 0xFF;
- entete[0x05] = (dec >> 16) & 0xFF;
- entete[0x06] = (dec >> 8) & 0xFF;
- entete[0x07] = (dec >> 0) & 0xFF;
- if ((liste = symboles_liste(tfm, &corr)) == NULL)
- return -1;
- lngr = tampex_esp(liste);
- entete[0x08] = (lngr >> 24) & 0xFF;
- entete[0x09] = (lngr >> 16) & 0xFF;
- entete[0x0A] = (lngr >> 8) & 0xFF;
- entete[0x0B] = (lngr >> 0) & 0xFF;
- res = fwrite(liste, 1, lngr, f);
- if (res != (ssize_t) lngr)
- return -1;
+ *pent++ = (TFD_VERSION >> 8) & 0xFF;
+ *pent++ = (TFD_VERSION >> 0) & 0xFF;
- dec += lngr;
+ /* Écrire le témoin de boutisme. */
+ pent = ecrire_16(pent, TFD_TEMOIN);
- /* Écrire la liste des identifiants de symbole d’entrée. */
- entete[0x0C] = (dec >> 24) & 0xFF;
- entete[0x0D] = (dec >> 16) & 0xFF;
- entete[0x0E] = (dec >> 8) & 0xFF;
- entete[0x0F] = (dec >> 0) & 0xFF;
- if (symboles_id(tfm, corr, &tse) < 0)
- return -1;
- tampex_libr(corr);
- lngr = tampex_esp(tse);
- entete[0x10] = (lngr >> 24) & 0xFF;
- entete[0x11] = (lngr >> 16) & 0xFF;
- entete[0x12] = (lngr >> 8) & 0xFF;
- entete[0x13] = (lngr >> 0) & 0xFF;
- res = fwrite(tse, 1, lngr, f);
- if (res != (ssize_t) lngr)
+ /* Écrire la liste de symboles.
+ * Le format de la liste des symboles du tfd et du tfm est le même. */
+ lngr = tampex_esp(tfm->symbs);
+ if (fwrite(tfm->symbs, 1, lngr, f) != lngr)
return -1;
+ pent = ecrire_32(pent, dec);
+ pent = ecrire_32(pent, lngr);
dec += lngr;
/* Écrire le segmenteur. */
- entete[0x14] = (dec >> 24) & 0xFF;
- entete[0x15] = (dec >> 16) & 0xFF;
- entete[0x16] = (dec >> 8) & 0xFF;
- entete[0x17] = (dec >> 0) & 0xFF;
- if ((segm = segmenteur(liste, tse)) == NULL)
+ if ((te = segmenteur(tfm)) == NULL)
return -1;
- tampex_libr(liste);
- tampex_libr(tse);
- lngr = tampex_esp(segm);
- entete[0x18] = (lngr >> 24) & 0xFF;
- entete[0x19] = (lngr >> 16) & 0xFF;
- entete[0x1a] = (lngr >> 8) & 0xFF;
- entete[0x1b] = (lngr >> 0) & 0xFF;
- res = fwrite(segm, 1, lngr, f);
- if (res != (ssize_t) lngr)
+ lngr = tampex_esp(te);
+ if (fwrite(te, 1, lngr, f) != lngr)
return -1;
+ tampex_libr(te);
+ pent = ecrire_32(pent, dec);
+ pent = ecrire_32(pent, lngr);
- tampex_libr(segm);
-
- entete[TFD_ENTETE_TLL-1] = 0xFF;
+ dec += lngr;
/* Écrire l’entête. */
if (fseek(f, 0, SEEK_SET) != 0)
return -1;
- if (fwrite(entete, 1, TFD_ENTETE_TLL, f) != TFD_ENTETE_TLL)
+ if (fwrite(ent, 1, TFD_ENTETE_TLL, f) != TFD_ENTETE_TLL)
return -1;
return 0;
}
-static char *
-symboles_liste(struct tfm *tfm, uint32_t **corr)
+static uint8_t *
+ecrire_16(uint8_t *tp, uint16_t val)
{
- char *liste; /* Liste de symboles. */
- size_t i; /* Indice dans liste. */
- char symb[TFM_TLL_SYMB_MAX]; /* Tampon à symbole. */
- size_t isymb, isymbc; /* Identifiant de symbole (courant). */
- ssize_t lngr; /* Longueur d’un symbole. */
-
- assert(tfm);
+ assert(tp);
- /* Initialiser les tampons. */
- if ((liste = tampex_init(TAMPON_LNGR_DEF, sizeof *liste)) == NULL)
- return NULL;
- if ((*corr = tampex_init(TAMPON_LNGR_DEF, sizeof *corr)) == NULL)
- goto erreur1;
+ *tp++ = ((unsigned char *)(&val))[0];
+ *tp++ = ((unsigned char *)(&val))[1];
- /* Parcourir les symboles. */
- isymb = isymbc = i = 0;
- while ((lngr = tfm_parc_symbs(tfm, &isymb, symb,
- TFM_TLL_SYMB_MAX)) > 0) {
- if (tampex_minim((void **)corr, isymbc) < 0)
- goto erreur2;
- (*corr)[isymbc] = i;
- if (tampex_minim((void **)&liste, i + lngr) < 0)
- goto erreur2;
- liste[i++] = (unsigned char)lngr;
- memcpy(liste + i, symb, lngr);
- i += lngr;
- isymbc = isymb;
- }
- if (lngr < 0)
- goto erreur2;
-
- return liste;
-
-erreur2:
- tampex_libr(*corr);
-erreur1:
- tampex_libr(liste);
- return NULL;
+ return tp;
}
-static int
-symboles_id(struct tfm *tfm, uint32_t *corr, uint16_t **se)
+static uint8_t *
+ecrire_32(uint8_t *tp, uint32_t val)
{
- char *dejala; /* Indique si l’identifiant est déjà dans se. */
- size_t ise; /* Indice dans se. */
- size_t ietat; /* Identifiant d’état. */
- size_t ntrans; /* Nombre de transitions depuis un état. */
- size_t itrans; /* Identifiant de transition. */
- ssize_t isymb; /* Identifiant de symbole .*/
+ assert(tp);
- assert(tfm);
- assert(corr);
+ *tp++ = ((unsigned char *)(&val))[0];
+ *tp++ = ((unsigned char *)(&val))[1];
+ *tp++ = ((unsigned char *)(&val))[2];
+ *tp++ = ((unsigned char *)(&val))[3];
- /* Initialiser les listes et le dejala. */
- if ((*se = tampex_init(TAMPON_LNGR_DEF, sizeof **se)) == NULL)
- return -1;
- if ((dejala = tampex_init(TAMPON_LNGR_DEF, sizeof *dejala)) == NULL)
- goto erreur1;
-
- ise = 0;
-
- /* Parcourir les états. */
- for (ietat = 0; tampex_dedans(tfm->etats, ietat); ietat++) {
- /* Parcourir les transitions. */
- for (itrans = tfm->etats[ietat].trans,
- ntrans = tfm->etats[ietat].ntrans;
- ntrans--; itrans = tfm->trans[itrans].prch) {
- /* Ignorer les symboles spéciaux. */
- if ((isymb = tfm->trans[itrans].se) >= 0) {
- if (tampex_minim((void **)&dejala, isymb) < 0)
- goto erreur2;
- /* Ne pas ajouter le symbole s’il est déjà là. */
- if (!dejala[isymb]) {
- if (tampex_minim((void **)se, ise) < 0)
- goto erreur2;
- (*se)[ise++] = corr[isymb];
- dejala[isymb] = 1;
- }
- }
- }
- }
-
- tampex_libr(dejala);
- return 0;
-
-erreur2:
- tampex_libr(dejala);
-erreur1:
- tampex_libr(se);
- return -1;
+ return tp;
}
-static uint16_t (*
-segmenteur(char *liste, uint16_t *tse))[2]
+static void *
+segmenteur(struct tfm *tfm)
{
+ uint16_t (*segm)[2]; /* Segmenteur (base, origine). */
struct tfm *symbs; /* Automate des symboles. */
- uint32_t *finaux; /* Identifiants de symboles associés aux états
- finaux. */
- uint16_t (*pile)[2]; /* Pile: (i, e). */
+ uint32_t *finaux; /* Symboles correspondants aux états finaux. */
+ size_t (*pile)[2]; /* Pile: (indice dans segm, état). */
ssize_t ipile; /* Indice dans la pile. */
- uint16_t (*segm)[2]; /* Segmenteur (base, orig). */
+ uint16_t isegm; /* Indice dans le segmenteur. */
+ size_t ietat, ntrans, itrans;
ssize_t base;
- uint16_t petat, pbase;
- size_t ntrans, itrans;
unsigned char c;
- assert(liste);
- assert(tse);
-
- /* Initialiser la pile. */
- if ((pile = tampex_init(TAMPON_LNGR_DEF, sizeof *pile)) == NULL)
- return NULL;
+ assert(tfm);
- /* Initialiser le segmenteur. */
+ /* Initialiser le segmenteur et la pile. */
if ((segm = tampex_init(TAMPON_LNGR_DEF, sizeof *segm)) == NULL)
+ return NULL;
+ if ((pile = tampex_init(TAMPON_LNGR_DEF, sizeof *pile)) == NULL)
goto erreur1;
/* Créer l’automate de symboles. */
- if ((symbs = automate_symbs(liste, tse, &finaux)) == NULL)
+ if ((symbs = automate_symbs(tfm, &finaux)) == NULL)
goto erreur2;
/* Empiler le premier état. */
@@ -273,43 +158,43 @@ segmenteur(char *liste, uint16_t *tse))[2]
assert(ipile == 0);
pile[ipile][0] = 0;
pile[ipile][1] = 0;
-
do {
/* Dépiler. */
ipile = tampex_dpl(pile);
- pbase = pile[ipile][0];
- petat = pile[ipile][1];
+ isegm = pile[ipile][0];
+ ietat = pile[ipile][1];
- /* Si petat est un état final. */
- if (tfm_tfinal(symbs, petat)) {
+ /* Si ietat est un état final. */
+ if (tfm_tfinal(symbs, ietat)) {
if ((base = segmenteur_libre(&segm)) < 0)
goto erreur3;
- segm[pbase][0] = (base << 1) | 0x01;
- pbase = base;
- segm[pbase][0] = 1; /* Réverver. */
- segm[pbase][1] = (finaux[petat] << 1) | 0x01;
+ segm[isegm][0] = (base << 1) | 0x01;
+ isegm = base;
+ segm[isegm][0] = 1; /* Réserver. Sera réécrit. */
+ segm[isegm][1] = (finaux[ietat] << 1) | 0x01;
}
/* S’il y a des transitions sortantes. */
- if ((ntrans = symbs->etats[petat].ntrans) > 0) {
- if ((base = segmenteur_base(&segm, symbs, petat)) < 0)
+ if ((ntrans = symbs->etats[ietat].ntrans) > 0) {
+ if ((base = segmenteur_base(&segm, symbs, ietat)) < 0)
goto erreur3;
- segm[pbase][0] = (base << 1) | 0x00;
- for (itrans = symbs->etats[petat].trans; ntrans--;
+ segm[isegm][0] = (base << 1) | 0x00;
+ for (itrans = symbs->etats[ietat].trans;
+ ntrans--;
itrans = symbs->trans[itrans].prch) {
assert(symbs->trans[itrans].se >= 0);
if (tfm_symb_obt(symbs, symbs->trans[itrans].se,
(char *)&c, 1) != 1)
goto erreur3;
- segm[base + c][0] = 1; /* Réserver la paire. */
- segm[base + c][1] = (pbase << 1) | 0x00;
+ segm[base + c][0] = 1; /* Réserver la paire. */
+ segm[base + c][1] = (isegm << 1) | 0x00;
if ((ipile = tampex_empl((void **)&pile)) < 0)
goto erreur3;
- pile[ipile][0] = base + c;
- pile[ipile][1] = symbs->trans[itrans].ed;
+ pile[ipile][0] = base + c;
+ pile[ipile][1] = symbs->trans[itrans].ed;
}
} else {
- segm[pbase][0] = (0 << 1) | 0x01;
+ segm[isegm][0] = (0 << 1) | 0x01;
}
} while (tampex_nelem(pile));
@@ -323,33 +208,19 @@ erreur3:
tfm_libr(symbs);
tampex_libr(finaux);
erreur2:
- tampex_libr(segm);
-erreur1:
tampex_libr(pile);
+erreur1:
+ tampex_libr(segm);
return NULL;
}
-static int
-segmenteur_tlibre(uint16_t (**segm)[2], size_t i)
-{
- int ret;
- assert(segm);
-
- if (tampex_minim((void **)segm, i) < 0)
- return -1;
- if ((*segm)[i][0] == 0)
- ret = 1;
- else
- ret = 0;
- return ret;
-}
-
static ssize_t
segmenteur_libre(uint16_t (**segm)[2])
{
size_t i;
assert(segm);
+ assert(*segm);
for (i = 1;; i++) {
switch (segmenteur_tlibre(segm, i)) {
@@ -370,6 +241,7 @@ segmenteur_base(uint16_t (**segm)[2], struct tfm *tfm, size_t ietat)
char c;
assert(segm);
+ assert(*segm);
assert(tfm);
for (i = 1;; i++) {
@@ -393,45 +265,62 @@ segmenteur_base(uint16_t (**segm)[2], struct tfm *tfm, size_t ietat)
assert(0);
}
-/* La routine fonctionne en parcourant tous les symboles d’un transducteur.
- * À chaque nouveau symbole, il parcourt l’automate de symboles à partir de son
+static int
+segmenteur_tlibre(uint16_t (**segm)[2], size_t i)
+{
+ assert(segm);
+ assert(*segm);
+
+ if (tampex_minim((void **)segm, i) < 0)
+ return -1;
+ if ((*segm)[i][0] == 0)
+ return 1;
+ else
+ return 0;
+}
+
+/* La routine fonctionne en parcourant tous les symboles d’un transducteur. À
+ * chaque nouveau symbole, il parcourt l’automate de symboles à partir de son
* premier état et passe d’état en état en suivant les caractères du symbole et
* en ajoutant les transitions manquantes. */
static struct tfm *
-automate_symbs(char *liste, uint16_t *se, uint32_t **finaux)
+automate_symbs(struct tfm *tfm, uint32_t **finaux)
{
- struct tfm *symbs; /* Automate de symboles. */
- size_t pos; /* Position courante la liste. */
+ struct tfm *symbs;
+ uint16_t *se; /* Liste de symboles d’entrée. */
+ size_t pos; /* Position courante dans la liste de symboles. */
uint16_t isymb; /* Indice d’un symbole. */
- int lngr; /* Longueur du symbole .*/
- size_t ietat, ietatp; /* Identifiants des états courant et
- précédent. */
- size_t ntrans; /* Nombre de transitions. */
- size_t itrans; /* Identifiant de transiton. */
ssize_t id; /* Identifiant de symbole. */
- char c; /* Caractère. */
+ size_t ietat, ietatp; /* Identifiants des états courant et
+ précédent. */
+ unsigned char lngr; /* Longueur d’un symbole. */
+ size_t ntrans, itrans;
+ char c;
- assert(liste);
- assert(se);
+ assert(tfm);
assert(finaux);
/* Initialiser l’automate de symboles. */
if ((symbs = tfm_init()) == NULL)
return NULL;
- /* Initialiser *finaux. */
- if ((*finaux = tampex_init(TAMPON_LNGR_DEF, sizeof(size_t))) == NULL)
+ if ((se = symboles_entree(tfm)) == NULL)
goto erreur1;
+ /* Initialiser *finaux. */
+ if ((*finaux = tampex_init(TAMPON_LNGR_DEF, sizeof(uint32_t))) == NULL)
+ goto erreur2;
+
/* Créer le premier état. */
if (tampex_minim((void **)&symbs->etats, 0) < 0)
- goto erreur2;
+ goto erreur3;
/* Parcourir les symboles. */
for (isymb = 0; tampex_dedans(se, isymb); isymb++) {
- pos = se[isymb];
+ pos = se[isymb]; /* Position courante. */
+
/* Obtenir la longueur du symbole. */
- lngr = ((unsigned char *)liste)[pos++];
+ lngr = tfm->symbs[pos++];
/* Parcourir les caractères du symbole. */
for (ietat = 0; lngr--; pos++) {
@@ -443,10 +332,10 @@ automate_symbs(char *liste, uint16_t *se, uint32_t **finaux)
itrans = symbs->trans[itrans].prch) {
if (tfm_symb_obt(symbs, symbs->trans[itrans].se,
&c, 1) != 1)
- goto erreur2;
- if (c == liste[pos]) {
- /* La bonne transition a été trouvée. Passer au
- * prochain caractère et au prochain état. */
+ goto erreur3;
+ if (c == tfm->symbs[pos]) {
+ /* La bonne transition a été trouvée. Passer au
+ * prochain caractère et au prochain état. */
ietat = symbs->trans[itrans].ed;
goto pcar;
}
@@ -457,28 +346,82 @@ automate_symbs(char *liste, uint16_t *se, uint32_t **finaux)
ietatp = ietat;
ietat = tampex_nelem(symbs->etats);
if (tampex_minim((void **)&symbs->etats, ietat) < 0)
- goto erreur2;
- if ((id = tfm_symb_id(symbs, liste + pos, 1)) < 0)
- goto erreur2;
+ goto erreur3;
+ if ((id = tfm_symb_id(symbs, tfm->symbs + pos, 1)) < 0)
+ goto erreur3;
if (tfm_ajt(symbs, ietatp, ietat, id, id) < 0)
- goto erreur2;
+ goto erreur3;
pcar:;
}
/* Marquer le dernier état d’un symbole comme final. */
if (tfm_mfinal(symbs, ietat) < 0)
- goto erreur2;
+ goto erreur3;
if (tampex_minim((void **)finaux, ietat) < 0)
- goto erreur2;
- (*finaux)[ietat] = isymb;
+ goto erreur3;
+ (*finaux)[ietat] = se[isymb];
}
+ tampex_libr(se);
return symbs;
-erreur2:
+erreur3:
tampex_libr(*finaux);
+erreur2:
+ tampex_libr(se);
erreur1:
tfm_libr(symbs);
return NULL;
}
+
+static uint16_t *
+symboles_entree(struct tfm *tfm)
+{
+ uint16_t *se;
+ size_t i; /* Indice dans se. */
+ bool *dejala; /* Indique si l’identifiant est déjà dans se. */
+ size_t ietat, ntrans, itrans;
+ ssize_t isymb; /* Identifiant de symbole. */
+
+ assert(tfm);
+
+ /* Initialiser se et dejala. */
+ if ((se = tampex_init(TAMPON_LNGR_DEF, sizeof(uint16_t))) == NULL)
+ return NULL;
+ if ((dejala = tampex_init(TAMPON_LNGR_DEF, sizeof *dejala)) == NULL)
+ goto erreur1;
+
+ i = 0;
+
+ /* Parcourir les états. */
+ for (ietat = 0; tampex_dedans(tfm->etats, ietat); ietat++) {
+ /* Parcourir les transitions. */
+ for (itrans = tfm->etats[ietat].trans,
+ ntrans = tfm->etats[ietat].ntrans;
+ ntrans--; itrans = tfm->trans[itrans].prch) {
+ /* Ignorer les symboles spéciaux. */
+ if ((isymb = tfm->trans[itrans].se) < 0)
+ continue;
+ /* Ne pas ajouter le symbole s’il est déjà la. */
+ if (tampex_minim((void **)&dejala, isymb) < 0)
+ goto erreur2;
+ if (dejala[isymb])
+ continue;
+ /* Ajouter le symbole. */
+ if (tampex_minim((void **)&se, i) < 0)
+ goto erreur2;
+ se[i++] = isymb;
+ dejala[isymb] = 1;
+ }
+ }
+
+ tampex_libr(dejala);
+ return se;
+
+erreur2:
+ tampex_libr(dejala);
+erreur1:
+ tampex_libr(se);
+ return NULL;
+}
diff --git a/tfd.h b/tfd.h
@@ -11,44 +11,45 @@
* 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 quatre segments, indexés dans une entête placée en
+ *
+ * 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,
- * - liste des identifiants de symbole d’entrée
- * - segmentaur
+ * - segmenteur
* - automate
*
* L’entête contient les champs suivants:
*
* 00 01 Nombre magique (0h5407)
* 02 03 Version (0)
- * 04 07 Décalage de la liste des symboles
- * 08 0b Taille de la liste des symboles
- * 0c 0f Décalage de la liste des identifiants de symbole d’entrée
- * 10 13 Taille de la liste des identifiants de symbole d’entrée
- * 14 17 Décalage du segmenteur
- * 18 1b Taille du segmenteur
- * 1c 1f Décalage de l’automate
- * 20 23 Taille de l’automate
+ * 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 de l’automate
+ * 1a 1d Taille de l’automate
*/
#define TFD_MAGIQUE 0x5407
#define TFD_VERSION 0
-#define TFD_ENTETE_TLL 0x24
+#define TFD_TEMOIN 0x00FF
+#define TFD_ENTETE_TLL 0x1E
/* 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.
*
- * Les listes des identifiants de symbole d’entrée et de sortie sont une suite
- * d’adresses relatives au début de la liste des symboles vers les symboles
- * d’entrée ou de sortie, respectivement.
+ * 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 chacune deux champs: la base ([0]) et l’origine ([1]).
+ * 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 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
@@ -59,13 +60,13 @@
* (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
*
- * i' = (paire[i][0] >> 1) + s,
+ * 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:
*
- * (paire[i'][1] & 1) == 0,
- * (paire[i'][1] >> 1) == i.
+ * (segm[i'][1] & 1) == 0,
+ * (segm[i'][1] >> 1) == i.
*
* Autrement, on pourrait quitter n’importe quel état avec n’importe quel
* symbole.
@@ -73,64 +74,30 @@
* Si, cependant, le drapeau de la base d’un symbole est brandi, il s’agit
* d’un état final et
*
- * i'' = paire[i'][0] >> 1 et
- * symbole = paire[i''][1] >> 1.
+ * i'' = segm[i'][0] >> 1 et
+ * symbole = segm[i''][1] >> 1.
*
* C’est-à-dire que le champ origine de l’état vers lequel il pointe représente
* en fait un symbole et que le champ base contient l’identifiant le l’état
* suivant.
*
+ * Enfin, si
+ *
+ * (segm[i][0] & 1) == 1 et
+ * (segm[i][0] >> 1) == 0,
+ *
+ * c’est que l’état ne compte aucune transition sortante.
+ *
* La variable symbole contient l’identifiant du symbole. Lors de
* l’interprétation du segmenteur, elle est mise à jour chaque fois qu’un état
- * final est rencontré, parce que le segmenteur est glouton: il tente de
+ * final est rencontré. Le segmenteur est en effet glouton: il tente de
* 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.
*
- * La structure de l’automate est aussi un tableau double. Elle s’inspire
- * cependant de l’extension de Mizobuchi, Sumitomo, Fuketa & Aoe (2000: An
- * efficient representation for implementing finite state machines based on the
- * double-array), qui augmente la structure d’Aho (1989) pour lui permettre de
- * représenter des cycles. La structure originale n’en est pas capable,
- * puisqu’elle force un état à n’avoir qu’une seule transition entrante, le
- * champ orig ne pouvant contenir qu’un seul état. La solution proposée est de
- * sélectionner une paire comme représentant canonique de l’état, les autres se
- * chargeant de vérifier l’origine et de pointer vers le représentant canonique.
- * Un drapeau placé dans le bit le plus à droite de la base indique que l’état
- * de la paire à laquelle elle appartient est canonique (0) ou non (1). Cette
- * solution ne fonctionne que pour les automates déterministes. Or,
- * contrairement aux automates finis, les transducteurs finis ne peuvent pas
- * tous être déterminisés: un symbole d’entrée peut mener à plus d’une
- * transition. La solution que je propose est de créer, dans ces cas, une liste
- * chaînée de transitions. Cette liste est signalée par un drapeau brandi dans
- * le bit de poids faible du champ origine. Les drapeaux de la base et de
- * l’origine ne peuvent être brandis en même temps. On passe d’un état à l’autre
- * par la formule:
- *
- * i' = paire[i].base >> 1 + s,
- *
- * si et seulement si
- *
- * paire[i'].orig & 1 == 0,
- * paire[i'].orig >> 1 == i.
- *
- * Si, cepedant le drapeau de la base d’un symbole est brandi,
- *
- * i'' = paire[i'].base >> 1.
- *
- * Et si c’est le drapeau de l’origine qui est brandi, paire[i'].base >> 1
- * contient l’indice vers le début de la liste de transitions. Dans cette
- * liste, le champ base contient l’indice de la prochaine paire ayant le
- * même symbole d’entrée et le champ origine l’indice de l’état vers lequel
- * pointe la transition. Une valeur de 1 dans l’origine marque la fin de la
- * liste.
- *
- * Un deuxième tableau contient les identifiants de symbole de sortie. Les
- * identifiants y sont disposés de telle sorte que l’indice dans le
- * transducteur de l’état cible d’une transition permette d’y obtenir
- * l’identifiant du symbole de sortie correspondant. */
+ * Le transducteur fini est représenté par une liste de transitions. */
/* Écrire une représentation .tfd du transducteur dans le fichier f.
* Renvoie 0, ou -1 en cas d’erreur. */
