// automate.c // << Algorithmique du texte >> // Maxime Crochemore, Christophe Hancart et Thierry Lecroq // Vuibert, 2001. #include <stdio.h> #include "chl.h" #include "automate.h" static int compteur = 0; int *visite; Etat nouvelEtat() { Etat etat; etat = (Etat)malloc(sizeof(struct _etat)); if (etat == NULL) error("nouvelEtat"); etat->indic = FEUILLE; etat->terminal = FAUX; etat->nom = compteur++; etat->sortie = -1; etat->ls = NULL; return(etat); } void fixerCible(Etat etat, Lettre a, Etat cible) { int b; Etat bCible; if (etat->indic == FEUILLE) { etat->indic = a; etat->cible = cible; } else if (etat->indic == FOURCHE) etat->succ[a] = cible; else if (etat->indic == a) etat->cible = cible; else { b = etat->indic; bCible = etat->cible; etat->succ = (Etat *)calloc(CARDA, sizeof(Etat)); if (etat->succ == NULL) error("fixerCible"); etat->succ[a] = cible; etat->succ[b] = bCible; etat->indic = FOURCHE; } } Etat cible(Etat etat, Lettre a) { if (etat->indic == FEUILLE) return(NULL); else if (etat->indic == FOURCHE) return(etat->succ[a]); else if (etat->indic == a) return(etat->cible); else return(NULL); } void copieCibles(Etat p, Etat q) { if (q->indic == FOURCHE) { p->succ = (Etat *)malloc(CARDA*sizeof(Etat)); if (p->succ == NULL) error("copieCibles"); memcpy(p->succ, q->succ, CARDA*sizeof(Etat)); p->indic = FOURCHE; } else if (q->indic != FEUILLE) { p->indic = q->indic; p->cible = q->cible; } } Automate nouvelAutomate() { Automate automate; automate = (Automate)malloc(sizeof(struct _automate)); if (automate == NULL) error("nouvelAutomate"); automate->initial = nouvelEtat(); automate->initial->ls = automate->initial; return(automate); } void ecrireEtat(Etat etat) { Lettre a; if (!visite[etat->nom]) { visite[etat->nom] = VRAI; printf("état %d sortie %d", etat->nom, etat->sortie); if (terminal(etat)) printf(" terminal"); printf("\n"); if (etat->indic != FEUILLE) if (etat->indic == FOURCHE) { for (a = PREMIERELETTRE; a <= DERNIERELETTRE; ++a) if (etat->succ[a] != NULL && etat->succ[a]->nom != 0) { printf(" delta(%d, %c) = %d\n", etat->nom, a, etat->succ[a]->nom); ecrireEtat(etat->succ[a]); } } else { if (etat->cible->nom != 0) { printf(" delta(%d, %c) = %d\n", etat->nom, etat->indic, etat->cible->nom); ecrireEtat(etat->cible); } } } } void ecrireAutomate(Automate automate) { visite = (int *)calloc(compteur, sizeof(int)); if (visite == NULL) error("ecrireAutomate"); ecrireEtat(initial(automate)); free(visite); }