commit 6bba0ec8dc617d4f59aeda294d4c7282a31e4e47
parent 5d1207c89094b0c740ce0c9fc6285ce6a47b78b0
Auteur: Loïc Daignault-Pichette <loic@asteride.xyz>
Date: Sat, 4 Apr 2026 14:56:16 -0400
Revamper tout sauf les tfd
Diffstat:
| M | Makefile | | | 4 | ++-- |
| M | att.c | | | 62 | ++++++++++++++++++++++++++++++++++++++++---------------------- |
| M | att.h | | | 14 | +++++++------- |
| M | attvtfd.c | | | 5 | ++--- |
| A | tampex.c | | | 153 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | tampex.h | | | 47 | +++++++++++++++++++++++++++++++++++++++++++++++ |
| D | tampinf.c | | | 146 | ------------------------------------------------------------------------------- |
| D | tampinf.h | | | 42 | ------------------------------------------ |
| M | tfm.c | | | 208 | +++++++++++++++++++++++++++++++++++-------------------------------------------- |
| M | tfm.h | | | 68 | +++++++++++++++++++++++++++++++------------------------------------- |
10 fichiers modifiés, 373 insertions(+), 376 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 tfd.o
- ${CC} ${COPTS} -o "$@" attvtfd.o tampinf.o tfm.o att.o tfd.o
+attvtfd: attvtfd.o tampex.o tfm.o att.o
+ ${CC} ${COPTS} -o "$@" attvtfd.o tampex.o tfm.o att.o
net:
rm -rf attvtfd *.o *.core
diff --git a/att.c b/att.c
@@ -1,9 +1,10 @@
#include <assert.h>
#include <stddef.h>
+#include <stdio.h>
#include <string.h>
#include "att.h"
-#include "tampinf.h"
+#include "tampex.h"
#include "tfm.h"
/* Séparateurs de champs. */
@@ -34,7 +35,7 @@ static int ajt_symb(struct tfm *tfm, char *t, size_t noct, ssize_t *id);
* de symbole spéciaux. Renvoie la taille du symbole, ou -1 en cas d’erreur. */
static ssize_t symb_obt(struct tfm *tfm, ssize_t id, char *symb, size_t max);
-/* Préparer la lecture du fichier f.
+/* Lire un fichier au format .att.
* La routine se fait peut-être une idée trop stricte du format .att et n’est
* pas très flexible. */
struct tfm *
@@ -55,6 +56,7 @@ att_lire(FILE *f)
for (;;) {
/* Premier champ: état source ou état final. */
switch (lire_champ(f, champ, TFM_TLL_SYMB_MAX, &noct)) {
+ default: assert(0);
case SEP_ERR:
goto erreur;
case SEP_EOF:
@@ -77,8 +79,9 @@ att_lire(FILE *f)
/* Deuxième champ: état suivant. */
switch (lire_champ(f, champ, TFM_TLL_SYMB_MAX, &noct)) {
+ default: assert(0);
case SEP_ERR: case SEP_EOF: case SEP_NL:
- /* Une ligne ne peut contenir que deux champs. */
+ /* Une ligne ne peut contenir seulement deux champs. */
goto erreur;
case SEP_TB:
/* Sauvegarder le champ dans ed. */
@@ -88,8 +91,9 @@ att_lire(FILE *f)
/* Troisième champ: symbole d’entrée. */
switch (lire_champ(f, champ, TFM_TLL_SYMB_MAX, &noct)) {
+ default: assert(0);
case SEP_ERR: case SEP_EOF: case SEP_NL:
- /* Une ligne ne peut contenir que trois champs. */
+ /* Une ligne ne peut contenir seulement trois champs. */
goto erreur;
case SEP_TB:
/* Sauvegarder le champ dans se. */
@@ -99,6 +103,7 @@ att_lire(FILE *f)
/* Quatrième champ: symbole de sortie. */
switch (lire_champ(f, champ, TFM_TLL_SYMB_MAX, &noct)) {
+ default: assert(0);
case SEP_ERR:
case SEP_EOF: /* Doit se terminer sur une nouvelle ligne. */
case SEP_TB: /* Il ne peut y avoir plus de quatre champs. */
@@ -123,35 +128,40 @@ erreur:
int
att_ecrire(FILE *f, struct tfm *tfm)
{
- struct etat etat;
- struct trans trans;
- size_t ietat, itrans;
- char symb[TFM_TLL_SYMB_MAX];
+ size_t ietat;
+ size_t ntrans;
+ size_t itrans;
ssize_t lngr;
+ char symb[TFM_TLL_SYMB_MAX];
assert(f);
assert(tfm);
/* Parcourir les états. */
- for (ietat = 0; tampinf_dedans(tfm->etats, ietat); ietat++) {
- if (tampinf_obt(tfm->etats, ietat, 1, &etat) < 0)
- return -1;
+ for (ietat = 0; tampex_dedans(tfm->etats, ietat); ietat++) {
/* Parcourir les transitions. */
- for (itrans = etat.trans; etat.ntrans--; itrans = trans.prch) {
- if (tampinf_obt(tfm->trans, itrans, 1, &trans) < 0)
- return -1;
- fprintf(f, "%zu\t%zu\t", ietat, trans.ed);
- if ((lngr = symb_obt(tfm, trans.se, symb,
+ for (ntrans = tfm->etats[ietat].ntrans,
+ itrans = tfm->etats[ietat].trans;
+ ntrans--;
+ itrans = tfm->trans[itrans].prch) {
+ /* Afficher les états source et destination. */
+ fprintf(f, "%zu\t%zu\t", ietat, tfm->trans[itrans].ed);
+
+ /* Afficher le symbole d’entrée. */
+ if ((lngr = symb_obt(tfm, tfm->trans[itrans].se, symb,
TFM_TLL_SYMB_MAX)) < 0)
return -1;
fwrite(symb, 1, lngr, f);
fputc('\t', f);
- if ((lngr = symb_obt(tfm, trans.ss, symb,
+
+ /* Afficher le symbole de sortie. */
+ if ((lngr = symb_obt(tfm, tfm->trans[itrans].ss, symb,
TFM_TLL_SYMB_MAX)) < 0)
return -1;
fwrite(symb, 1, lngr, f);
- fputc('\n', f);
+ fprintf(f, "\n");
}
+
/* Afficher les transitions finales. */
if (tfm_tfinal(tfm, ietat))
fprintf(f, "%zu\n", ietat);
@@ -168,6 +178,7 @@ lire_champ(FILE *f, char *t, size_t max, size_t *noct)
assert(f);
assert(t);
+ assert(max > 0);
assert(noct);
/* Si déjà la fin, renvoyer EOF. */
@@ -178,7 +189,7 @@ lire_champ(FILE *f, char *t, size_t max, size_t *noct)
* jusqu’à ce que le tampon soit plein. */
for (i = 0; c != '\t' && c != '\n' && c != EOF; t[i++] = c, c = getc(f))
if (i >= max)
- return SEP_ERR;
+ return SEP_ERR;
*noct = i;
@@ -198,10 +209,11 @@ nombre(char *t, size_t noct)
size_t n;
assert(t);
+ assert(noct > 0);
for (i = n = 0; i < noct; n = n * 10 + (t[i++] - '0')) {
if (t[i] < '0' || t[i] > '9')
- return -1;
+ return -1;
}
return n;
@@ -212,15 +224,21 @@ ajt_symb(struct tfm *tfm, char *t, size_t noct, ssize_t *id)
{
assert(tfm);
assert(t);
+ assert(noct > 0);
assert(id);
/* Intercepter les symboles spéciaux. */
- if (noct == 3 && strncmp(t, "@0@", noct) == 0) {
+ if (noct == 3 && memcmp(t, "@0@", noct) == 0) {
*id = TFM_SYMB_EPSILON;
return 0;
}
- return tfm_symb_id(tfm, t, noct, id);
+ if ((*id = tfm_symb_id(tfm, t, noct)) < 0)
+ return -1;
+
+ assert(*id >= 0);
+
+ return 0;
}
static ssize_t
diff --git a/att.h b/att.h
@@ -8,24 +8,24 @@
/* Le format .att est composé de lignes et de champs. Les champs d’une même
* ligne sont séparés par un caractère de tabulation. Il existe deux types de
* lignes: l’un déclare une transition, l’autre un état comme final. On les
- * distingue selon le nombre de champs que contient la ligne. Les transitions
- * comptent quatre champs, qui sont: le numéro de l’état source, le numéro de
- * l’état destination, le symbole d’entrée et le symbole de sortie. En voici un
- * exemple:
+ * distingue selon le nombre de champs que contient la ligne. Les lignes du
+ * premier type comptent quatre champs, qui sont: l’identifiant de l’état
+ * source, l’identifiant de l’état destination, le symbole d’entrée et le
+ * symbole de sortie. Par exemple:
*
* 0 1 ᵘ u
*
* Certains symboles sont interprétés différemment par foma. La présente mise en
* œuvre reconnaît @0@ comme le symbole epsilon (ε). D’autres sont à venir.
*
- * Les lignes qui déclarent un état comme final ne comptent qu’un seul champ,
- * qu’occupe le numéro de l’état final. Par exemple:
+ * Les lignes du deuxième type ne comptent qu’un seul champ, qu’occupe
+ * l’identifiant d’un état à déclarer comme final. Par exemple:
*
* 1
*/
/* Lire le fichier f au format .att.
- * Initialise et renvoie un transducteur au format struct tfm, un NULL en cas
+ * Initialise et renvoie un transducteur au format struct tfm, ou NULL en cas
* d’erreur. */
struct tfm *att_lire(FILE *f);
diff --git a/attvtfd.c b/attvtfd.c
@@ -2,7 +2,6 @@
#include "att.h"
#include "tfm.h"
-#include "tfd.h"
int
main(int argc, char **argv)
@@ -25,8 +24,8 @@ main(int argc, char **argv)
return 1;
}
- if (tfd_ecrire(ftfd, tfm) < 0) {
- fprintf(stderr, "attvtf: erreur dans l’écriture du fichier .tfd\n");
+ if (att_ecrire(ftfd, tfm) < 0) {
+ fprintf(stderr, "attvtf: erreur dans l’écriture du fichier .att\n");
return 1;
}
diff --git a/tampex.c b/tampex.c
@@ -0,0 +1,153 @@
+#include <assert.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "tampex.h"
+
+/* Calculer l’adresse de l’entête d’un tampex. */
+#define ENTETE(te) ((Entete *)te - 1)
+
+/* Calculer l’adresse du tampon d’un tampex. */
+#define TAMPON(ent) (ent + 1)
+
+/* Tester la cohérence d’un tampex. */
+#define TAMPINF_COHERENT(te) \
+ /* Le pointeur n’est pas NULL. */ \
+ assert(ENTETE(te)); \
+ /* Un élément a une taille supérieure à zéro. */ \
+ assert((ENTETE(te))->s.tll > 0); \
+ /* Le tampon peut contenir au moins un élément. */ \
+ assert((ENTETE(te))->s.lngr > 0); \
+ /* Le nombre d’éléments est inférieur ou égal à la longueur. */ \
+ assert((ENTETE(te))->s.nelem <= (ENTETE(te))->s.lngr);
+
+/* La structure du tampon extensible a été conçue pour que son utilisation
+ * ressemble le plus possible à celle des tampons renvoyés par malloc(3). C’est
+ * donc sous cette forme qu’ils se présentent à l’utilisateur. Or, une partie
+ * de la réalité lui est cachée, car sous le tampon qui lui est renvoyé se
+ * trouve une entête contenant l’information nécessaire au bon fonctionnement
+ * des fonctions de cette bilbiothèque: la taille des éléments du tampon,
+ * exprimée en octets, la longueur du tampon, excluant l’entête et exprimée en
+ * multiples de la taille, et enfin le nombre d’éléments que contient le
+ * tampon. */
+
+/* Entête d’un tampex.
+ * L’union assure que l’entête occupe un multiple de sizeof(long) octets. Cette
+ * solution vient de la seconde édition de The C Programming Language. */
+typedef union entete {
+ struct {
+ size_t tll; /* Taille des éléments. */
+ size_t lngr; /* Longueur du tampon. */
+ size_t nelem; /* Nombre d’éléments dans le tampon. */
+ } s;
+ long alignement;
+} Entete;
+
+void *
+tampex_init(size_t lngr, size_t tll)
+{
+ Entete *ent;
+
+ assert(lngr > 0);
+ assert(tll > 0);
+
+ if ((ent = malloc(sizeof(Entete) + lngr * tll)) == NULL)
+ return NULL;
+
+ ent->s.tll = tll;
+ ent->s.lngr = lngr;
+ ent->s.nelem = 0;
+
+ /* Initialiser le tampon à zéro. */
+ tampex_reinit(TAMPON(ent));
+
+ TAMPINF_COHERENT(TAMPON(ent));
+
+ return TAMPON(ent);
+}
+
+void
+tampex_reinit(void *ti)
+{
+ TAMPINF_COHERENT(ti);
+
+ memset(ti, 0, ENTETE(ti)->s.tll * ENTETE(ti)->s.lngr);
+
+ ENTETE(ti)->s.nelem = 0;
+}
+
+void
+tampex_libr(void *ti)
+{
+ TAMPINF_COHERENT(ti);
+
+ free(ENTETE(ti));
+}
+
+void *
+tampex_minim(void *ti, size_t i)
+{
+ size_t nlngr; /* Nouvelle longueur. */
+ Entete *nent; /* Nouvelle entête. */
+ size_t nnelem; /* Nouveau nombre d’éléments. */
+
+ TAMPINF_COHERENT(ti);
+
+ /* Mettre à jour le nombre d’éléments, mais ne pas lui permettre de
+ * décroître. */
+ nnelem = ENTETE(ti)->s.nelem;
+ if (nnelem < i + 1)
+ nnelem = i + 1;
+
+ /* Ne pas agrandir le tampon s’il est déjà assez grand. */
+ if (ENTETE(ti)->s.lngr > i) {
+ ENTETE(ti)->s.nelem = nnelem;
+ TAMPINF_COHERENT(ti);
+ return ti;
+ }
+
+ /* Doubler la longueur jusqu’à ce qu’elle soit supérieure ou égale à la
+ * longueur recherchée. */
+ for (nlngr = ENTETE(ti)->s.lngr; nlngr <= i; nlngr *= 2)
+ ;
+
+ /* Agrandir le tampon et en initialiser à zéro la nouvelle partie. */
+ if ((nent = realloc(ENTETE(ti),
+ sizeof(Entete) + nlngr * ENTETE(ti)->s.tll)) == NULL)
+ return NULL;
+ memset((char *)TAMPON(nent) + nent->s.lngr * nent->s.tll, 0,
+ (nlngr - nent->s.lngr) * nent->s.tll);
+ nent->s.lngr = nlngr;
+ nent->s.nelem = nnelem;
+
+ TAMPINF_COHERENT(TAMPON(nent));
+
+ return TAMPON(nent);
+}
+
+size_t
+tampex_nelem(void *ti)
+{
+ TAMPINF_COHERENT(ti);
+
+ return ENTETE(ti)->s.nelem;
+}
+
+size_t
+tampex_esp(void *ti)
+{
+ TAMPINF_COHERENT(ti);
+
+ return ENTETE(ti)->s.nelem * ENTETE(ti)->s.tll;
+}
+
+bool
+tampex_dedans(void *ti, size_t i)
+{
+ TAMPINF_COHERENT(ti);
+
+ if (i < ENTETE(ti)->s.nelem)
+ return 1;
+ return 0;
+}
diff --git a/tampex.h b/tampex.h
@@ -0,0 +1,47 @@
+#ifndef TAMPEX_H
+#define TAMPEX_H
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <sys/types.h>
+
+/* Un tampex est un tampon extensible. Cette bibliothèque est une interface
+ * devant malloc(3), realloc(3) et free(3). Elle dispense de retenir
+ * explicitement la longueur d’un tampon, la taille des objets qui y sont
+ * placés ainsi que leur nombre. */
+
+/* Initialiser un tampon pouvant contenir au moins lngr objets de tll octets
+ * chacun.
+ * Le tampon est initialisé à zéro.
+ * Renvoie le tampon, ou NULL en cas d’erreur. */
+void *tampex_init(size_t lngr, size_t tll);
+
+/* Réinitialiser le tampon te.
+ * Son contenu est aussi réinitialisé à zéro. */
+void tampex_reinit(void *te);
+
+/* Libérer l’espace utilisé par le tampon te. */
+void tampex_libr(void *te);
+
+/* Assurer que le tampon te soit assez grand pour contenir un élément à l’index
+ * i.
+ * Renvoie l’adresse du tampon, ou NULL en cas d’erreur.
+ * Il est possible, si le tampex doit être agrandi, que le tampon doivent être
+ * déplacé. Il est donc important de toujours sauvegarder l’adresse renvoyée.
+ * Il s’en suit aussi que toute référence au contenu d’un tampex doit être
+ * relative à la position en mémoire du tampon. */
+void *tampex_minim(void *te, size_t i);
+
+/* Obtenir le nombre d’éléments contenus dans le tampon te.
+ * Ce nombre correspond à la valeur de i la plus élevée donnée à
+ * tampex_minim(). */
+size_t tampex_nelem(void *te);
+
+/* Obtenir l’espace utilisé par les éléments du tampon te. */
+size_t tampex_esp(void *te);
+
+/* Renvoie 1 si l’indice i est dans la partie utilisée du tampon, 0
+ * autrement. */
+bool tampex_dedans(void *te, size_t i);
+
+#endif
diff --git a/tampinf.c b/tampinf.c
@@ -1,146 +0,0 @@
-#include <assert.h>
-#include <stddef.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "tampinf.h"
-
-/* Calculer l’adresse de l’entête d’un taminf. */
-#define ENTETE(ti) ((Entete *)ti - 1)
-
-/* Calculer l’adresse du tampon d’un tampinf. */
-#define TAMPON(ent) (ent + 1)
-
-/* Tester la cohérence du tampon. */
-#define TAMPINF_COHERENT(ti) \
- /* Le pointeur n’est pas NULL. */ \
- assert(ENTETE(ti)); \
- /* Un élémENTETE(ti) a une taille supérieure à zéro. */ \
- assert((ENTETE(ti))->s.tll > 0); \
- /* Le tampon peut contenir au moins un élémENTETE(ti). */ \
- assert((ENTETE(ti))->s.lngr > 0); \
- /* Le nombre d’élémENTETE(ti)s est inférieur ou égal à la longueur. */ \
- assert((ENTETE(ti))->s.nelem <= (ENTETE(ti))->s.lngr);
-
-/* La structure du tampon infini a été conçue pour que son utilisation
- * ressemble le plus possible à celle des tableaux statiques. C’est donc sous
- * cette forme qu’ils se présentent à l’utilisateur. Or, une partie de la
- * réalité lui est cachée, car sous le tampon qui lui est renvoyé sous trouve
- * une entête contenant l’information nécessaires au bon fonctionnement des
- * fonctions de cette bilbiothèque: la taille des éléments du tampon, exprimée
- * en octets, la longueur du tampon, excluant l’entête et exprimée en multiples
- * de la taille, et enfin le nombre d’éléments que contient le tampon. */
-
-/* Entête d’un tampinf.
- * L’union assure que l’entête occupe un multiple de sizeof(long) octets. */
-typedef union entete {
- struct {
- size_t tll; /* Taille des éléments. */
- size_t lngr; /* Longueur du tampon. */
- size_t nelem; /* Nombre d’éléments dans le tampon. */
- } s;
- long alignement;
-} Entete;
-
-void *
-tampinf_init(size_t lngr, size_t tll)
-{
- Entete *ent;
-
- assert(lngr > 0);
- assert(tll > 0);
-
- if ((ent = malloc(sizeof(Entete) + lngr * tll)) == NULL)
- return NULL;
-
- ent->s.tll = tll;
- ent->s.lngr = lngr;
- ent->s.nelem = 0;
-
- tampinf_reinit(TAMPON(ent));
-
- TAMPINF_COHERENT(TAMPON(ent));
-
- return TAMPON(ent);
-}
-
-void
-tampinf_reinit(void *ti)
-{
- TAMPINF_COHERENT(ti);
-
- memset(ti, 0, ENTETE(ti)->s.tll * ENTETE(ti)->s.lngr);
-
- ENTETE(ti)->s.nelem = 0;
-}
-
-void
-tampinf_libr(void *ti)
-{
- TAMPINF_COHERENT(ti);
-
- free(ENTETE(ti));
-}
-
-void *
-tampinf_minim(void *ti, size_t i)
-{
- size_t nlngr; /* Nouvelle longueur. */
- Entete *nent; /* Nouvelle entête. */
- size_t nnelem; /* Nouveau nombre d’éléments. */
-
- TAMPINF_COHERENT(ti);
-
- nnelem = ENTETE(ti)->s.nelem;
- if (nnelem < i + 1)
- nnelem = i + 1;
-
- if (ENTETE(ti)->s.lngr > i) {
- ENTETE(ti)->s.nelem = nnelem;
- return ti;
- }
-
- /* Doubler la longueur jusqu’à ce quelle soit supérieure ou égale à la
- * longueur recherchée. */
- for (nlngr = ENTETE(ti)->s.lngr; nlngr <= i; nlngr *= 2)
- ;
-
- /* Agrandir le tampon et en initialiser à zéro la nouvelle partie. */
- if ((nent = realloc(ENTETE(ti),
- sizeof(Entete) + nlngr * ENTETE(ti)->s.tll)) == NULL)
- return NULL;
- memset((char *)TAMPON(nent) + nent->s.lngr * nent->s.tll, 0,
- (nlngr - nent->s.lngr) * nent->s.tll);
- nent->s.lngr = nlngr;
- nent->s.nelem = nnelem;
-
- TAMPINF_COHERENT(TAMPON(nent));
-
- return TAMPON(nent);
-}
-
-size_t
-tampinf_nelem(void *ti)
-{
- TAMPINF_COHERENT(ti);
-
- return ENTETE(ti)->s.nelem;
-}
-
-size_t
-tampinf_esp(void *ti)
-{
- TAMPINF_COHERENT(ti);
-
- return ENTETE(ti)->s.nelem * ENTETE(ti)->s.tll;
-}
-
-bool
-tampinf_dedans(void *ti, size_t i)
-{
- TAMPINF_COHERENT(ti);
-
- if (i < ENTETE(ti)->s.nelem)
- return 1;
- return 0;
-}
diff --git a/tampinf.h b/tampinf.h
@@ -1,42 +0,0 @@
-#ifndef TAMPINF_H
-#define TAMPINF_H
-
-#include <stdbool.h>
-#include <stddef.h>
-#include <sys/types.h>
-
-/* Un tampinf est un tampon qui donne l’illusion d’être infini.
- *
- * L’adresse d’un tampon n’est pas statique, et plusieurs fonctions sont
- * susceptibles de la changer. Ces fonctions renvoient toutes l’adresse
- * courante du tampon. Toute variable qui contiendrait l’adresse du tampon doit
- * être mise à jour à l’occasion de l’appel de ce genre de fonctions. */
-
-/* Initialiser un tampon.
- * La longueur est interprétée en multiples de tll. Le tampon est initialisé à
- * zéro.
- * Renvoie le tampon, ou NULL en cas d’erreur. */
-void *tampinf_init(size_t lngr, size_t tll);
-
-/* Réinitialiser le tampon ti.
- * Son contenu est aussi réinitialisé à zéro. */
-void tampinf_reinit(void *ti);
-
-/* Libérer l’espace utilisé par le tampon ti. */
-void tampinf_libr(void *ti);
-
-/* Assurer que le tampon ti puisse contenir un élément à l’index i.
- * Renvoie l’adresse du tampon, ou NULL en cas d’erreur. */
-void *tampinf_minim(void *ti, size_t i);
-
-/* Obtenir le nombre d’éléments contenus dans le tampon ti. */
-size_t tampinf_nelem(void *ti);
-
-/* Obtenir l’espace utilisé par les éléments du tampon ti. */
-size_t tampinf_esp(void *ti);
-
-/* Renvoie 1 si l’indice i est dans la partie utilisée du tampon, 0
- * autrement. */
-bool tampinf_dedans(void *ti, size_t i);
-
-#endif
diff --git a/tfm.c b/tfm.c
@@ -4,20 +4,25 @@
#include <string.h>
#include "tfm.h"
-#include "tampinf.h"
+#include "tampex.h"
#define TAMPON_LNGR_DEF 64 /* Longueur par défaut des tampons. */
+/* Tester la cohérence d’un tfm. */
#define TFM_COHERENT(tfm) \
+ /* Le pointeur n’est pas NULL. */ \
assert((tfm)); \
+ /* Le pointeur vers le tampex des états n’est pas NULL. */ \
assert((tfm)->etats); \
+ /* Le pointeur vers le tampex des transitions n’est pas NULL. */ \
assert((tfm)->trans); \
+ /* Le pointeur vers le tampex des symboles n’est pas NULL. */ \
assert((tfm)->symbs);
-/* Chercher un symbole symb de longueur lngr dans le transducteur tfm.
+/* Chercher un symbole symb de longueur lngr dans le tampon te.
* 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);
+static ssize_t tfm_symb_chercher(char *te, char *symb, size_t lngr);
struct tfm *
tfm_init(void)
@@ -27,28 +32,28 @@ tfm_init(void)
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;
- }
+ /* Initialiser les tampex. */
+ if ((tfm->etats = tampex_init(TAMPON_LNGR_DEF,
+ sizeof(struct etat))) == NULL)
+ goto erreur1;
+ if ((tfm->trans = tampex_init(TAMPON_LNGR_DEF,
+ sizeof(struct trans))) == NULL)
+ goto erreur2;
+ if ((tfm->symbs = tampex_init(TAMPON_LNGR_DEF,
+ sizeof(char))) == NULL)
+ goto erreur3;
TFM_COHERENT(tfm);
return tfm;
+
+erreur3:
+ tampex_libr(tfm->trans);
+erreur2:
+ tampex_libr(tfm->etats);
+erreur1:
+ free(tfm);
+ return NULL;
}
void
@@ -56,98 +61,99 @@ tfm_libr(struct tfm *tfm)
{
TFM_COHERENT(tfm);
- tampinf_libr(tfm->etats);
- tampinf_libr(tfm->trans);
- tampinf_libr(tfm->symbs);
+ tampex_libr(tfm->symbs);
+ tampex_libr(tfm->trans);
+ tampex_libr(tfm->etats);
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;
+ void *tetp; /* Tampinf temporaire. */
+ size_t itrans; /* Identifiant de transition. */
+
TFM_COHERENT(tfm);
- /* Obtenir l’état source. */
- if (tampinf_obt(tfm->etats, es, 1, &etat) < 0)
+ /* Assurer que l’état source existe. */
+ if ((tetp = tampex_minim(tfm->etats, es)) == NULL)
return -1;
+ tfm->etats = tetp;
- /* 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)
+ /* Ajouter une transitions. */
+ itrans = tampex_nelem(tfm->trans);
+ if ((tetp = tampex_minim(tfm->trans, itrans)) == NULL)
return -1;
+ tfm->trans = tetp;
+
+ /* Construire la nouvelle transition. */
+ tfm->trans[itrans].se = se;
+ tfm->trans[itrans].ss = ss;
+ tfm->trans[itrans].ed = ed;
+ tfm->trans[itrans].prch = tfm->etats[es].trans;
/* Mettre à jour l’état. */
- etat.trans = itrans;
- etat.ntrans++;
- if (tampinf_plc(tfm->etats, es, 1, &etat) < 0)
- return -1;
+ tfm->etats[es].trans = itrans;
+ tfm->etats[es].ntrans++;
TFM_COHERENT(tfm);
return 0;
}
-int
-tfm_symb_id(struct tfm *tfm, char *symb, size_t lngr, ssize_t *id)
+ssize_t
+tfm_symb_id(struct tfm *tfm, char *symb, size_t lngr)
{
- ssize_t pos;
- unsigned char n;
+ size_t i;
+ ssize_t id;
+ char *tip;
TFM_COHERENT(tfm);
assert(symb);
assert(lngr > 0);
- assert(id);
- /* La longueur de l’identifiant doit pouvoir entrer dans un octets. */
- if (lngr > 0xFF)
+ /* Valider la taille du symbole. */
+ if (lngr > TFM_TLL_SYMB_MAX)
return -1;
- if ((pos = tfm_symb_chercher(tfm->symbs, symb, lngr)) >= 0)
+ /* La longueur de l’identifiant doit pouvoir entrer dans un octets. */
+ assert(TFM_TLL_SYMB_MAX <= 0xFF);
+
+ if ((id = 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, n, symb) < 0)
+ i = id = tampex_nelem(tfm->symbs);
+ if ((tip = tampex_minim(tfm->symbs, i + lngr)) == NULL)
return -1;
+ tfm->symbs = tip;
+ tfm->symbs[i++] = (unsigned char) lngr;
+ memcpy(tfm->symbs + i, symb, lngr);
fin:
+ assert(id >= 0);
TFM_COHERENT(tfm);
- *id = pos;
- return 0;
+ return id;
}
ssize_t
tfm_symb_obt(struct tfm *tfm, size_t id, char *symb, size_t max)
{
- size_t lngr, i;
- char *ctn;
+ unsigned char lngr;
TFM_COHERENT(tfm);
assert(symb);
assert(max > 0);
+ assert(tampex_dedans(tfm->symbs, id));
- ctn = tampinf_ctn(tfm->symbs);
-
- assert(tampinf_dedans(tfm->symbs, id));
- lngr = *(unsigned char *)(ctn + id);
+ lngr = *(unsigned char *)(tfm->symbs + id);
/* Le symbole doit rentrer dans le tampon. */
if (lngr > max)
return -1;
/* Copier le symbole. */
- for (i = 0, ctn += id + 1; i < lngr; i++)
- symb[i] = ctn[i];
+ memcpy(symb, tfm->symbs + id + 1, lngr);
return lngr;
}
@@ -162,12 +168,14 @@ tfm_parc_symbs(struct tfm *tfm, size_t *id, char *symb, size_t max)
assert(symb);
assert(max > 0);
- if (!tampinf_dedans(tfm->symbs, *id))
+ /* Vérifier s’il reste au moins au symbole à lire. */
+ if (!tampex_dedans(tfm->symbs, *id))
return 0;
if ((lngr = tfm_symb_obt(tfm, *id, symb, max)) < 0)
- return lngr;
+ return -1;
+ /* Préparer le prochain appel. */
*id += lngr + 1;
return lngr;
@@ -176,16 +184,15 @@ tfm_parc_symbs(struct tfm *tfm, size_t *id, char *symb, size_t max)
int
tfm_mfinal(struct tfm *tfm, size_t ietat)
{
- struct etat etat;
+ struct etat *tetp;
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)
+ if ((tetp = tampex_minim(tfm->etats, ietat)) == NULL)
return -1;
+ tfm->etats = tetp;
+ tfm->etats[ietat].final = 1;
TFM_COHERENT(tfm);
return 0;
@@ -194,74 +201,41 @@ tfm_mfinal(struct tfm *tfm, size_t ietat)
int
tfm_tfinal(struct tfm *tfm, size_t ietat)
{
- struct etat etat;
+ struct etat *tetp;
TFM_COHERENT(tfm);
- /* Obtenir l’état. */
- if (tampinf_obt(tfm->etats, ietat, 1, &etat) < 0)
+ if ((tetp = tampex_minim(tfm->etats, ietat)) == NULL)
return -1;
-
- return etat.final;
+ return tfm->etats[ietat].final;
}
ssize_t
tfm_ntrans(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.ntrans;
-}
-
-ssize_t
-tfm_trans(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.trans;
-}
-
-ssize_t
-tfm_trans_prch(struct tfm *tfm, size_t itrans)
-{
- struct trans trans;
+ struct etat *tetp;
TFM_COHERENT(tfm);
- /* Obtenir la transition. */
- if (tampinf_obt(tfm->trans, itrans, 1, &trans) < 0)
+ if ((tetp = tampex_minim(tfm->etats, ietat)) == NULL)
return -1;
-
- return trans.prch;
+ return tfm->etats[ietat].ntrans;
}
static ssize_t
-tfm_symb_chercher(struct tampinf *ti, char *symb, size_t lngr)
+tfm_symb_chercher(char *ti, char *symb, size_t lngr)
{
- char *ctn;
unsigned pos;
- unsigned n;
+ unsigned char n;
+ assert(ti);
assert(symb);
+ assert(lngr > 0);
- ctn = tampinf_ctn(ti);
-
- for (pos = 0; tampinf_dedans(ti, pos); pos += n) {
- n = ((unsigned char *)ctn)[pos++];
- if (lngr == n && strncmp(symb, ctn + pos, n) == 0)
- return pos-1;
+ for (pos = 0; tampex_dedans(ti, pos); pos += n) {
+ n = ti[pos++];
+ if (lngr == n && memcmp(symb, ti + pos, n) == 0)
+ return pos - 1;
}
return -1;
diff --git a/tfm.h b/tfm.h
@@ -3,8 +3,7 @@
#include <stdbool.h>
#include <stddef.h>
-
-#include "tampinf.h"
+#include <sys/types.h>
/* L’accronyme « tfm » veut dire « transducteur fini en mémoire ». */
@@ -12,25 +11,25 @@
#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. */
+/* 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. */
#define TFM_TLL_SYMB_MAX 255 /* Taille maximale d’un symbole. */
struct tfm {
- struct tampinf *etats;
- struct tampinf *trans;
- struct tampinf *symbs;
+ struct etat *etats; /* Liste des états. */
+ struct trans *trans; /* Liste des transitions. */
+ char *symbs; /* Liste des symboles. */
};
-/* 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. trans et ntrans sont des
- * indices dans le tampon tfm.trans. */
+/* 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. */
struct etat {
size_t trans; /* Liste chaînée de transitions. */
@@ -38,11 +37,13 @@ struct etat {
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. se et ss sont des indices dans le tampon tfm.etats.
- * ed est un indice dans le tampon tfm.etats. prch est un indice dans le tampon
- * tfm.trans. */
+/* 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. */
struct trans {
ssize_t se; /* Symbole d’entrée. */
@@ -59,16 +60,16 @@ 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.
+/* 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 id d’un symbole symb de longueur lngr dans le
+/* Obtenir l’identifiant 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);
+ * Si le symbole est inconnu du transducteur, il y est ajouté de manière
+ * transparente. Renvoie l’identifiant, ou -1 en cas d’erreur. */
+ssize_t tfm_symb_id(struct tfm *tfm, char *symb, size_t lngr);
/* Placer le symbole du transducteur tfm correspondant à l’identifiant id dans
* le tampon symb, de taille max.
@@ -79,9 +80,10 @@ 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. 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. */
+ * 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.
@@ -96,12 +98,4 @@ int tfm_tfinal(struct tfm *tfm, size_t ietat);
* Renvoie ce nombre, ou -1 en cas d’erreur. */
ssize_t tfm_ntrans(struct tfm *tfm, size_t ietat);
-/* Obtenir l’identifiant de la première transition sortante d’ietat.
- * Renvoie cet identifiant, ou -1 en cas d’erreur. */
-ssize_t tfm_trans(struct tfm *tfm, size_t ietat);
-
-/* Obtenir l’identifiant de la transition suivant la transition itrans.
- * Renvoie cet identifiant, ou -1 en cas d’erreur. */
-ssize_t tfm_trans_prch(struct tfm *tfm, size_t itrans);
-
#endif
