commit 5ca56d9bf1a793879188fdcb7dba607f6015663a
parent ffd28e8db2f60d01b6905db723b926d6cdb750ac
Auteur: Loïc Daignault-Pichette <loic@asteride.xyz>
Date: Tue, 7 Apr 2026 11:40:26 -0400
Créer le segmenteur; un premier jet
Diffstat:
| M | Makefile | | | 4 | ++-- |
| M | attvtfd.c | | | 3 | ++- |
| M | tfd.c | | | 609 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------- |
| M | tfd.h | | | 108 | +++++++++++++++++++++++++++++++++++++++++++++---------------------------------- |
4 fichiers modifiés, 518 insertions(+), 206 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 tampex.o tfm.o att.o
- ${CC} ${COPTS} -o "$@" attvtfd.o tampex.o tfm.o att.o
+attvtfd: attvtfd.o tampex.o tfm.o att.o tfd.o
+ ${CC} ${COPTS} -o "$@" attvtfd.o tampex.o tfm.o att.o tfd.o
net:
rm -rf attvtfd *.o *.core
diff --git a/attvtfd.c b/attvtfd.c
@@ -1,6 +1,7 @@
#include <stdio.h>
#include "att.h"
+#include "tfd.h"
#include "tfm.h"
int
@@ -24,7 +25,7 @@ main(int argc, char **argv)
return 1;
}
- if (att_ecrire(ftfd, tfm) < 0) {
+ if (tfd_ecrire(ftfd, tfm) < 0) {
fprintf(stderr, "attvtf: erreur dans l’écriture du fichier .att\n");
return 1;
}
diff --git a/tfd.c b/tfd.c
@@ -1,234 +1,531 @@
#include <assert.h>
-#include <stddef.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 64
-
-/* Obtenir la liste des symboles d’un transducteur.
- * Renvoie un pointeur vers cette liste, ou NULL en cas d’erreur. */
-static struct tampinf *symboles_liste(struct tfm *tfm);
-
-/* Obtenir un index d’une liste de symboles telle que renvoyée par
- * tampinf_liste.
- * Renvoie un pointeur vers l’index, ou NULL en cas d’erreur. */
-static struct tampinf *symboles_index(struct tampinf *liste);
-
-/* 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);
+#define TAMPON_LNGR_DEF 1
+
+/* 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 (se) et de sortie (ss)
+ * 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,
+ uint16_t **ss);
+
+/* Créer le segmenteur à partir d’une liste de symboles d’entrée.
+ * 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);
+
+/* Trouver une paire libre dans le segmenteur.
+ * Renvoie l’indice de la paire trouvée, ou -1 en cas d’erreur. */
+static ssize_t segmenteur_libre(uint16_t (**segm)[2]);
+
+/* Trouver la paire de base dans le segmenteur segm de l’état ietat dans
+ * l’automate tfm.
+ * Renvoie l’indice de la base, ou -1 en cas d’erreur. */
+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);
int
tfd_ecrire(FILE *f, struct tfm *tfm)
{
- struct tampinf *liste; /* Liste de symboles. */
- struct tampinf *index; /* Index de symboles. */
- size_t pos, tll;
+ 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, *tss; /* 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. */
assert(f);
assert(tfm);
+ dec = TFD_ENTETE_TLL;
+ if (fseek(f, dec, SEEK_SET) != 0)
+ return -1;
+
/* Écrire le nombre magique. */
- fputc((TFD_MAGIQUE >> 8) & 0xff, f);
- fputc((TFD_MAGIQUE >> 0) & 0xff, f);
+ entete[0x00] = (TFD_MAGIQUE >> 8) & 0xFF;
+ entete[0x01] = (TFD_MAGIQUE >> 0) & 0xFF;
/* Écrire la version. */
- fputc((TFD_VERSION >> 8) & 0xff, f);
- fputc((TFD_VERSION >> 0) & 0xff, f);
+ 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;
+
+ dec += lngr;
- /* Liste de symboles. */
- if ((liste = symboles_liste(tfm)) == NULL)
+ /* É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, &tss) < 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)
return -1;
- /* Index des symboles. */
- if ((index = symboles_index(liste)) == NULL)
+ dec += lngr;
+
+ /* Écrire la liste des identifiants de symbole de sortie. */
+ entete[0x14] = (dec >> 24) & 0xFF;
+ entete[0x15] = (dec >> 16) & 0xFF;
+ entete[0x16] = (dec >> 8) & 0xFF;
+ entete[0x17] = (dec >> 0) & 0xFF;
+ lngr = tampex_esp(tss);
+ entete[0x18] = (lngr >> 24) & 0xFF;
+ entete[0x19] = (lngr >> 16) & 0xFF;
+ entete[0x1a] = (lngr >> 8) & 0xFF;
+ entete[0x1b] = (lngr >> 0) & 0xFF;
+ res = fwrite(tse, 1, lngr, f);
+ tampex_libr(tss);
+ if (res != (ssize_t) lngr)
return -1;
- /* Écrire la position de l’index des symboles. */
- pos = TFD_ENTETE_FIN;
- fputc((pos >> 24) & 0xff, f);
- fputc((pos >> 16) & 0xff, f);
- fputc((pos >> 8) & 0xff, f);
- fputc((pos >> 0) & 0xff, f);
-
- /* Écrire la taille de l’index des symboles. */
- tll = tampinf_esp(index);
- fputc((tll >> 24) & 0xff, f);
- fputc((tll >> 16) & 0xff, f);
- fputc((tll >> 8) & 0xff, f);
- fputc((tll >> 0) & 0xff, f);
-
- /* Écrire la position de la liste de symboles. */
- pos += tll;
- fputc((pos >> 24) & 0xff, f);
- fputc((pos >> 16) & 0xff, f);
- fputc((pos >> 8) & 0xff, f);
- fputc((pos >> 0) & 0xff, f);
-
- /* Écrire la taille de la liste de symboles. */
- tll = tampinf_esp(liste);
- fputc((tll >> 24) & 0xff, f);
- fputc((tll >> 16) & 0xff, f);
- fputc((tll >> 8) & 0xff, f);
- fputc((tll >> 0) & 0xff, f);
+ dec += lngr;
+
+ /* Écrire le segmenteur. */
+ entete[0x1c] = (dec >> 24) & 0xFF;
+ entete[0x1d] = (dec >> 16) & 0xFF;
+ entete[0x1e] = (dec >> 8) & 0xFF;
+ entete[0x1f] = (dec >> 0) & 0xFF;
+ if ((segm = segmenteur(liste, tse)) == NULL)
+ return -1;
+ tampex_libr(liste);
+ tampex_libr(tse);
+ lngr = tampex_esp(segm);
+ entete[0x1c] = (lngr >> 24) & 0xFF;
+ entete[0x1d] = (lngr >> 16) & 0xFF;
+ entete[0x1e] = (lngr >> 8) & 0xFF;
+ entete[0x1f] = (lngr >> 0) & 0xFF;
+ res = fwrite(segm, 1, lngr, f);
+ if (res != (ssize_t) lngr)
+ return -1;
+
+ /*for (size_t z = 0; tampex_dedans(segm, z); z++) {
+ printf("%lu\t%s%d\t%s%d\n",
+ z,
+ segm[z][0] & 0x01 ? "*" : "",
+ segm[z][0]>>1,
+ segm[z][1] & 0x01 ? "*" : "",
+ segm[z][1]>>1);
+ }*/
+
+ tampex_libr(segm);
+
+ entete[TFD_ENTETE_TLL-1] = 0xFF;
+
+ /* Écrire l’entête. */
+ if (fseek(f, 0, SEEK_SET) != 0)
+ return -1;
+ if (fwrite(entete, 1, TFD_ENTETE_TLL, f) != TFD_ENTETE_TLL)
+ return -1;
return 0;
}
-static struct tampinf *
-symboles_liste(struct tfm *tfm)
+static char *
+symboles_liste(struct tfm *tfm, uint32_t **corr)
{
- struct tampinf *liste;
+ char *liste; /* Liste de symboles. */
+ size_t i; /* Indice dans liste. */
char symb[TFM_TLL_SYMB_MAX]; /* Tampon à symbole. */
- size_t id, tll;
- unsigned char n;
+ size_t isymb, isymbc; /* Identifiant de symbole (courant). */
+ ssize_t lngr; /* Longueur d’un symbole. */
assert(tfm);
- /* Initialiser la liste. */
- if ((liste = tampinf_init(TAMPON_LNGR_DEF, sizeof(char))) == NULL)
+ /* 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;
/* Parcourir les symboles. */
- id = 0;
- while ((tll = tfm_parc_symbs(tfm, &id, symb, TFM_TLL_SYMB_MAX)) > 0) {
- n = tll;
- if (tampinf_ajt(liste, 1, &n) < 0)
- goto erreur;
- if (tampinf_ajt(liste, tll, symb) < 0)
- goto erreur;
+ 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;
-erreur:
- tampinf_libr(liste);
+erreur2:
+ tampex_libr(*corr);
+erreur1:
+ tampex_libr(liste);
return NULL;
}
-static struct tampinf *
-symboles_index(struct tampinf *liste)
+static int
+symboles_id(struct tfm *tfm, uint32_t *corr, uint16_t **se, uint16_t **ss)
{
- struct tampinf *index;
- char *ctn; /* Contenu de la liste. */
- size_t pos; /* Position dans la liste. */
- unsigned n; /* Taille d’un symbole. */
+ char *dejala; /* Indique si l’identifiant est déjà dans se (& 1) ou
+ dans ss (& 2). */
+ size_t ise; /* Indice dans se. */
+ size_t iss; /* Indice dans ss. */
+ 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(tfm);
+ assert(corr);
+
+ /* Initialiser les listes et le dejala. */
+ if ((*se = tampex_init(TAMPON_LNGR_DEF, sizeof **se)) == NULL)
+ return -1;
+ if ((*ss = tampex_init(TAMPON_LNGR_DEF, sizeof **ss)) == NULL)
+ goto erreur1;
+ if ((dejala = tampex_init(TAMPON_LNGR_DEF, sizeof *dejala)) == NULL)
+ goto erreur2;
+
+ ise = iss = 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 erreur3;
+ /* Ne pas ajouter le symbole s’il est déjà là. */
+ if (!(dejala[isymb] & 1)) {
+ if (tampex_minim((void **)se, ise) < 0)
+ goto erreur3;
+ (*se)[ise++] = corr[isymb];
+ dejala[isymb] |= 1;
+ }
+ }
+
+ /* Ignorer les symboles spéciaux. */
+ if ((isymb = tfm->trans[itrans].ss) >= 0) {
+ if (tampex_minim((void **)&dejala, isymb) < 0)
+ goto erreur3;
+ /* Ne pas ajouter le symbole s’il est déjà là. */
+ if (!(dejala[isymb] & 2)) {
+ if (tampex_minim((void **)ss, iss) < 0)
+ goto erreur3;
+ (*ss)[iss++] = corr[isymb];
+ dejala[isymb] |= 2;
+ }
+ }
+ }
+ }
+
+ tampex_libr(dejala);
+ return 0;
+
+erreur3:
+ tampex_libr(dejala);
+erreur2:
+ tampex_libr(ss);
+erreur1:
+ tampex_libr(se);
+ return -1;
+}
+
+static uint16_t (*
+segmenteur(char *liste, uint16_t *tse))[2]
+{
+ struct tfm *symbs; /* Automate des symboles. */
+ uint32_t *finaux; /* Identifiants de symboles associés aux états
+ finaux. */
+ uint16_t (*pile)[2]; /* Pile: (i, e). */
+ ssize_t ipile; /* Indice dans la pile. */
+ uint16_t (*segm)[2]; /* Segmenteur (base, orig). */
+ ssize_t base;
+ uint16_t petat, pbase;
+ size_t ntrans, itrans;
+ unsigned char c;
assert(liste);
+ assert(tse);
- /* Initialiser l’index des symboles. */
- if ((index = tampinf_init(TAMPON_LNGR_DEF, sizeof(size_t))) == NULL)
+ /* Initialiser la pile. */
+ if ((pile = tampex_init(TAMPON_LNGR_DEF, sizeof *pile)) == NULL)
return NULL;
- /* Obtenir le contenu de la liste de symboles. */
- if ((ctn = tampinf_ctn(liste)) == NULL)
- goto erreur;
+ /* Initialiser le segmenteur. */
+ if ((segm = tampex_init(TAMPON_LNGR_DEF, sizeof *segm)) == NULL)
+ goto erreur1;
+
+ /* Créer l’automate de symboles. */
+ if ((symbs = automate_symbs(liste, tse, &finaux)) == NULL)
+ goto erreur2;
+
+ /* Empiler le premier état. */
+ if ((ipile = tampex_empl((void **)&pile)) < 0)
+ goto erreur3;
+ 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];
+
+ /* Si petat est un état final. */
+ if (tfm_tfinal(symbs, petat)) {
+ 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;
+ }
- /* Parcourir les symboles. */
- for (pos = 0; tampinf_dedans(liste, pos); pos += n + 1) {
- n = ((unsigned char *)ctn)[pos];
- if (tampinf_ajt(index, 1, &pos) < 0)
- goto erreur;
- }
+ /* S’il y a des transitions sortantes. */
+ if ((ntrans = symbs->etats[petat].ntrans) > 0) {
+ if ((base = segmenteur_base(&segm, symbs, petat)) < 0)
+ goto erreur3;
+ segm[pbase][0] = (base << 1) | 0x00;
+ for (itrans = symbs->etats[petat].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;
+ if ((ipile = tampex_empl((void **)&pile)) < 0)
+ goto erreur3;
+ pile[ipile][0] = base + c;
+ pile[ipile][1] = symbs->trans[itrans].ed;
+ }
+ } else {
+ segm[pbase][0] = (0 << 1) | 0x01;
+ }
+ } while (tampex_nelem(pile));
+
+ tfm_libr(symbs);
+ tampex_libr(finaux);
+ tampex_libr(pile);
- return index;
+ return segm;
-erreur:
- tampinf_libr(liste);
+erreur3:
+ tfm_libr(symbs);
+ tampex_libr(finaux);
+erreur2:
+ tampex_libr(segm);
+erreur1:
+ tampex_libr(pile);
return NULL;
}
-/* 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)
+static int
+segmenteur_tlibre(uint16_t (**segm)[2], size_t i)
{
- 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. */
+ 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);
+
+ for (i = 1;; i++) {
+ switch (segmenteur_tlibre(segm, i)) {
+ case 0: continue;
+ case 1: return i;
+ default: return -1;
+ }
+ }
+
+ assert(0);
+}
+static ssize_t
+segmenteur_base(uint16_t (**segm)[2], struct tfm *tfm, size_t ietat)
+{
+ size_t i;
+ size_t itrans, ntrans;
+ char c;
+
+ assert(segm);
assert(tfm);
+ for (i = 1;; i++) {
+ for (itrans = tfm->etats[ietat].trans,
+ ntrans = tfm->etats[ietat].ntrans;
+ ntrans--; itrans = tfm->trans[itrans].prch) {
+ assert(tfm->trans[itrans].se >= 0);
+
+ if (tfm_symb_obt(tfm, tfm->trans[itrans].se, &c, 1) != 1)
+ return -1;
+ switch (segmenteur_tlibre(segm, i + (unsigned char)c)) {
+ case 0: goto encore;
+ case 1: continue;
+ default: return -1;
+ }
+ }
+ return i;
+ encore:;
+ }
+
+ 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
+ * 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)
+{
+ struct tfm *symbs; /* Automate de symboles. */
+ size_t pos; /* Position courante la liste. */
+ 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. */
+
+ assert(liste);
+ assert(se);
+ assert(finaux);
+
/* 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;
- }
+ /* Initialiser *finaux. */
+ if ((*finaux = tampex_init(TAMPON_LNGR_DEF, sizeof(size_t))) == NULL)
+ goto erreur1;
/* Créer le premier état. */
- etat.final = 0;
- etat.ntrans = 0;
- etat.trans = 0;
- if (tampinf_ajt(symbs->etats, 1, &etat) < 0)
- goto erreur;
+ if (tampex_minim((void **)&symbs->etats, 0) < 0)
+ goto erreur2;
/* 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. */
+ for (isymb = 0; tampex_dedans(se, isymb); isymb++) {
+ pos = se[isymb];
+ /* Obtenir la longueur du symbole. */
+ lngr = ((unsigned char *)liste)[pos++];
+
+ /* Parcourir les caractères du symbole. */
+ for (ietat = 0; lngr--; pos++) {
+
+ /* Chercher une transition sortante pour liste[pos]. */
+ for (ntrans = symbs->etats[ietat].ntrans,
+ itrans = symbs->etats[ietat].trans;
+ ntrans--;
+ 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. */
+ ietat = symbs->trans[itrans].ed;
+ goto pcar;
}
}
- /* 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;
+
+ /* Aucune transition adéquate n’a été trouvée. En ajouter
+ * une. */
+ 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;
+ if (tfm_ajt(symbs, ietatp, ietat, id, id) < 0)
+ goto erreur2;
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 (tfm_mfinal(symbs, ietat) < 0)
+ goto erreur2;
+ if (tampex_minim((void **)finaux, ietat) < 0)
+ goto erreur2;
+ (*finaux)[ietat] = isymb;
}
- if (lngr < 0)
- goto erreur;
return symbs;
-erreur:
+erreur2:
+ tampex_libr(*finaux);
+erreur1:
tfm_libr(symbs);
- tampinf_libr(*ti);
return NULL;
}
diff --git a/tfd.h b/tfd.h
@@ -8,75 +8,89 @@
/* Le format .tfd est une représentation binaire du transducteur. 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
- * dispense d’un maximum de recherche. L’asbsence de sérialisation et de
- * désérialisation freine la portabilité du fichier. En particulier, le format
- * utilise le boutisme de l’hôte qui le compile.
+ * 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 cinq segments, indexés dans une entête placée en
- * début de fichier. Les segments sont les suivants: index des symboles, liste
- * de symboles, segmenteur, automate, tableau des identifiants de symbole de
- * sortie.
+ * début de fichier. Les segments sont les suivants:
+ *
+ * - liste des symboles,
+ * - liste des identifiants de symbole d’entrée
+ * - liste des identifiants de symbole de sortie
+ * - segmentaur
+ * - automate
*
* L’entête contient les champs suivants:
*
* 00 02 Nombre magique (0h5407)
* 02 04 Version (0)
- * 04 06 Position de l’index des symboles
- * 06 08 Taille du l’index des symboles
- * 08 0a Position de la liste de symboles
- * 0a 0c Taille de la liste de symboles
- * 0c 0e Position du segmenteur
- * 0e 10 Taille du segmenteur
- * 10 12 Position de l’automate
- * 12 14 Taille de l’automate
- * 14 16 Position des identifiants de symbole de sortie
- * 16 18 Taille des identifiants de symbole de sortie
+ * 04 08 Décalage de la liste des symboles
+ * 08 0c Taille de la liste des symboles
+ * 0c 10 Décalage de la liste des identifiants de symbole d’entrée
+ * 10 14 Taille de la liste des identifiants de symbole d’entrée
+ * 14 18 Décalage de la liste des identifiants de symbole de sortie
+ * 18 0c Taille de la liste des identifiants de symbole de sortie
+ * 0c 20 Décalage du segmenteur
+ * 20 24 Taille du segmenteur
+ * 24 28 Décalage de l’automate
+ * 28 2c Taille de l’automate
*/
#define TFD_MAGIQUE 0x5407
#define TFD_VERSION 0
-#define TFD_ENTETE_FIN 0x18
+#define TFD_ENTETE_TLL 0x2c
/* 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.
*
- * L’index des symboles est un tableau de pointeurs vers les symboles de la
- * liste de symboles. Les identifiants de symbole sont des indices dans l’index
- * des symboles.
- *
- * 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 et l’origine. Chaque champ occupe 2 octets, pour
- * un total de 4 octets par cellule. Ces deux champs contiennent un drapeau dans
- * leur bit le plus à droite. 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.
- * 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
+ * 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 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]).
+ * 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
*
- * i' = paire[i].base >> 1 + s,
+ * i' = (paire[i][0] >> 1) + s,
*
- * où s est un symbole d’entrée. Pour que la transition soit valide, il faut en
- * plus satisfaire les équation suivante:
+ * où s est un symbole d’entrée. Pour que la transition soit valide, les
+ * conditions suivantes doivent aussi être satisfaites:
*
- * paire[i'].orig & 1 == 0,
- * paire[i'].orig >> 1 == i.
+ * (paire[i'][1] & 1) == 0,
+ * (paire[i'][1] >> 1) == i.
*
* Autrement, on pourrait quitter n’importe quel état avec n’importe quel
* symbole.
- * Si, cependant, le drapeau de la base d’un symbole est brandi,
*
- * i'' = paire[i'].base >> 1 et
- * symbole = paire[i''].orig >> 1.
+ * 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.
+ *
+ * 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.
*
- * La variable symbole contient l’identifiant du symbole. Elle est mise à jour
- * chaque fois qu’un état final est rencontré parce que le segmenteur est
- * 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 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
+ * 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
@@ -94,7 +108,7 @@
* 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 le plus à droite du champ origine. Les drapeaux de la base et de
+ * 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:
*
