commit cbdf7ff1c00482d86a65906faf690dba98bf2ce5
parent 177c4d6e5683de3102c29562e85afa05a512b999
Auteur: Loïc Daignault-Pichette <loic@asteride.xyz>
Date: Sat, 25 Apr 2026 21:10:11 -0400
Interpréter les transducteurs
Diffstat:
| M | Makefile | | | 4 | ++-- |
| M | itfd.c | | | 191 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | itfd.h | | | 33 | +++++++++++++++++++++++++++++++++ |
| M | mishka.c | | | 28 | ++++++++++++++++++++++++++++ |
4 fichiers modifiés, 254 insertions(+), 2 suppressions(-)
diff --git a/Makefile b/Makefile
@@ -2,7 +2,7 @@
.SUFFIXES: .c .o
CC = cc
-COPTS = -Wall -Wextra -Wpedantic -std=c99 -O0 #-DNDEBUG -O3 -flto
+COPTS = -Wall -Wextra -Wpedantic -Wno-implicit-fallthrough -std=c99 -O0 #-DNDEBUG -O3 -flto
.c.o:
${CC} ${COPTS} ${CPPOPTS} -c "$<"
@@ -13,7 +13,7 @@ attvtfd: attvtfd.o tampex.o tfm.o att.o tfd.o
${CC} ${COPTS} -o "$@" attvtfd.o tampex.o tfm.o att.o tfd.o
mishka: mishka.o itfd.o
- ${CC} ${COPTS} -o "$@" mishka.o itfd.o
+ ${CC} ${COPTS} -o "$@" mishka.o itfd.o tampex.o
net:
rm -rf attvtfd mishka *.o *.core
diff --git a/itfd.c b/itfd.c
@@ -1,17 +1,35 @@
#include <assert.h>
+#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>
+#include <sys/types.h>
#include "itfd.h"
+#include "tampex.h"
#include "tfd.h"
/* Lire du tampon tp au décalage dec 16 ou 32 bits. */
#define LIRE_16(tp, dec) (*(uint16_t *)((tp) + (dec)))
#define LIRE_32(tp, dec) (*(uint32_t *)((tp) + (dec)))
+struct option {
+ size_t icse; /* Indice dans la liste de symboles d’entrée. */
+ size_t icss; /* Indice dans la liste de symboles de sortie. */
+ uint32_t pos; /* Position dans le transducteur. */
+};
+
+/* Empiler l’option initialisatrice d’interp.
+ * Renvoie 0, ou -1 en cas d’erreur. */
+static int interp_init_empl(struct interp *interp);
+
+/* Empiler l’option formée apr icse, icss et pos dans interp.
+ * Renvoie 0, ou -1 en cas d’erreur. */
+static int empiler(struct interp *interp, size_t icse, size_t icss,
+ uint32_t pos);
+
struct itfd *
itfd_ouvrir(int df)
{
@@ -147,3 +165,176 @@ segmenter(struct itfd *itfd, uint8_t *cc, size_t lngrcc, uint16_t *symbs)
assert(nsymbs <= lngrcc);
return nsymbs;
}
+
+struct interp *
+interp_init(struct itfd *itfd)
+{
+ struct interp *interp;
+
+ assert(itfd);
+
+ if ((interp = malloc(sizeof(struct interp))) == NULL)
+ return NULL;
+ if ((interp->opt = tampex_init(64, sizeof(struct option))) == NULL)
+ goto erreur1;
+ if ((interp->css = tampex_init(64, sizeof(uint16_t))) == NULL)
+ goto erreur2;
+ interp->itfd = itfd;
+
+ if (interp_init_empl(interp) < 0)
+ goto erreur3;
+
+ return interp;
+
+erreur3:
+ tampex_libr(interp->css);
+erreur2:
+ tampex_libr(interp->opt);
+erreur1:
+ free(interp);
+ return NULL;
+}
+
+void
+interp_libr(struct interp *interp)
+{
+ assert(interp);
+ assert(interp->opt);
+ assert(interp->css);
+
+ tampex_libr(interp->opt);
+ tampex_libr(interp->css);
+ free(interp);
+}
+
+int
+interp_reinit(struct interp *interp, struct itfd *itfd)
+{
+ assert(interp);
+ assert(interp->opt);
+ assert(interp->css);
+ assert(itfd);
+
+ tampex_reinit(interp->opt);
+ tampex_reinit(interp->css);
+ interp->itfd = itfd;
+
+ if (interp_init_empl(interp) < 0)
+ return -1;
+
+ return 0;
+}
+
+static int
+interp_init_empl(struct interp *interp)
+{
+ assert(interp);
+
+ return empiler(interp, 0, 0, 4);
+}
+
+ssize_t
+interpreter(struct interp *interp, uint16_t *cse, size_t nsymbs)
+{
+ uint16_t *tf; /* Adresse du début du transducteur. */
+ uint16_t ntrans; /* Nombre de transitions. */
+ uint16_t se, ss; /* Symboles d’entrée et de sortie. */
+ size_t pos; /* Position dans le transducteur. */
+ size_t ipile; /* Indice dans la pile. */
+ size_t icse, icss; /* Indices dans les chaînes d’entrée et de
+ sortie. */
+ bool trouve; /* Si une transition exacte a été trouvée. */
+ bool final; /* Si un état est final. */
+
+ assert(interp);
+ assert(cse);
+
+ tf = (uint16_t *)interp->itfd->trans;
+
+ while (tampex_nelem(interp->opt)) {
+ /* Dépiler une transition. */
+ ipile = tampex_dpl(interp->opt);
+ icse = interp->opt[ipile].icse;
+ icss = interp->opt[ipile].icss;
+ pos = interp->opt[ipile].pos;
+
+ /* Ajouter le symbole à la chaîne de sortie. */
+ ss = tf[pos + 1];
+ if (tampex_minim((void **)&interp->css, icss + 1) < 0)
+ return -1;
+ switch (ss) {
+ case TFD_SYMB_EPSILON: break; /* Ignorer. */
+ case TFD_SYMB_IDENTITE:
+ se = tf[pos + 0];
+ if (se == TFD_SYMB_EPSILON) break;
+ assert(icse > 0);
+ interp->css[icss++] = cse[icse - 1];
+ break;
+ case TFD_SYMB_AUTRE:
+ ss = ITFD_SYMB_AUTRE;
+ /* ON TOMBE! */
+ default: /* Ajouter le symbole à la sortie. */
+ if ((ss & 0x01) != TFD_SNORMAL)
+ break;
+ interp->css[icss++] = ss;
+ }
+
+ /* Sauter au prochain état. */
+ pos = LIRE_32(tf, pos + 2) << 2;
+ ntrans = tf[pos + 0];
+ /* Si l’état est final et qu’on est à la fin de cse. */
+ final = (icse == nsymbs) && (tf[pos + 1] & 0x1);
+ pos += 4;
+ trouve = 0;
+ /* Parcourir les transitions. */
+ for (; ntrans--; pos += 4) {
+ if ((icse >= nsymbs) && (tf[pos + 0] != TFM_SYMB_EPSILON))
+ continue;
+ switch (tf[pos + 0]) {
+ case TFM_SYMB_AUTRE:
+ if (!trouve) {
+ if (empiler(interp, icse + 1, icss, pos) < 0)
+ return -1;
+ }
+ break;
+ case TFM_SYMB_EPSILON:
+ if (empiler(interp, icse, icss, pos) < 0)
+ return -1;
+ break;
+ case TFM_SYMB_IDENTITE:
+ if (empiler(interp, icse + 1, icss, pos) < 0)
+ return -1;
+ break;
+ default:
+ se = cse[icse];
+ if ((tf[pos + 0] >> 1) != (se >> 1))
+ break;
+ if ((tf[pos + 0] & 0x01) != TFD_SNORMAL)
+ break;
+ if ((se & 0x01) != ITFD_SYMB_REC)
+ break;
+ if (empiler(interp, icse + 1, icss, pos) < 0)
+ return -1;
+ trouve = 1;
+ }
+ }
+ if (final)
+ return icss + 1;
+ }
+
+ return 0;
+}
+
+static int
+empiler(struct interp *interp, size_t icse, size_t icss, uint32_t pos)
+{
+ ssize_t ipile;
+
+ if ((ipile = tampex_empl((void **)&interp->opt)) < 0)
+ return -1;
+ interp->opt[ipile].icse = icse;
+ interp->opt[ipile].icss = icss;
+ interp->opt[ipile].pos = pos;
+
+ return 0;
+}
diff --git a/itfd.h b/itfd.h
@@ -1,10 +1,14 @@
#ifndef ITFD_H
#define ITFD_H
+#include <stdbool.h>
#include <stdint.h>
+#include <sys/types.h>
/* Interpréter un transducteur fini sur le disque. */
+#define ITFD_SYMB_BAS ((256 << 1) | 0x00) /* N’importe quel symbole du bas. */
+
struct itfd {
int df; /* Descripteur de fichier. */
uint8_t *f; /* Contenu du fichier. */
@@ -22,6 +26,13 @@ struct itfd {
size_t trans_lngr; /* Longueur du transducteur. */
};
+/* Mémoire d’interprétation. */
+struct interp {
+ struct itfd *itfd;
+ struct option *opt; /* Tampex d’options. */
+ uint16_t *css; /* Chaîne de symboles de sortie. */
+};
+
/* Ouvrir un fichier tfd pour l’interpréter.
* Renvoie un pointeur vers une structure itfd, ou NULL en cas d’erreur. */
struct itfd *itfd_ouvrir(int df);
@@ -42,4 +53,26 @@ int itfd_fermer(struct itfd *itfd);
size_t segmenter(struct itfd *itfd, uint8_t *cc, size_t lngrcc,
uint16_t *symbs);
+#define ITFD_SYMB_AUTRE (0x100 | ITFD_SYMB_NREC)
+
+#define ITFD_SYMB_REC 0x01
+#define ITFD_SYMB_NREC 0x00
+
+/* Initialiser un interpréteur du transducteur itfd.
+ * Renvoie une mémoire d’interprétation, ou NULL.*/
+struct interp *interp_init(struct itfd *itfd);
+
+/* Libérer la mémoire d’interprétation interp. */
+void interp_libr(struct interp *interp);
+
+/* Réinitialiser la mémoire d’interprétation interp pour interpréter itfd.
+ * Renvoie 0, ou -1 en cas d’erreur. */
+int interp_reinit(struct interp *interp, struct itfd *itfd);
+
+/* Appliquer l’interpréteur interp à la chaîne de symboles d’entrée cse
+ * contenant nsymbs symboles.
+ * Renvoie 0 si aucune correspondance n’a été trouvée ou le nombre de symboles
+ * de sorties produits + 1, ou -1 en cas d’erreur. */
+ssize_t interpreter(struct interp *interp, uint16_t *cse, size_t nsymbs);
+
#endif
diff --git a/mishka.c b/mishka.c
@@ -14,6 +14,8 @@ main(int argc, char **argv)
size_t nsymbs;
size_t lngr;
size_t i;
+ struct interp *interp;
+ ssize_t rv;
if ((df = open("a", O_RDONLY)) < 0)
return 1;
@@ -40,5 +42,31 @@ main(int argc, char **argv)
}
}
+ if ((interp = interp_init(itfd)) == NULL)
+ return 1;
+
+ printf("---\n");
+
+ while ((rv = interpreter(interp, symbs, nsymbs)) > 0) {
+ printf("\n");
+ for (i = 0; i < ((size_t)rv - 1); i++) {
+ if (!(interp->css[i] & 0x01)) {
+ printf("*%c (%d)\n", interp->css[i] >> 1, interp->css[i] >> 1);
+ } else {
+ fwrite(itfd->symbs + 1 + (interp->css[i] >> 1),
+ 1,
+ itfd->symbs[interp->css[i] >> 1],
+ stdout);
+ printf(" (%d)\n", interp->css[i] >> 1);
+ }
+ }
+ }
+ if (rv == -1)
+ return 1;
+
+ interp_libr(interp);
+ if (itfd_fermer(itfd) < 0)
+ return 1;
+
return 0;
}
