Transformation afn en afd

Soyez le premier à donner votre avis sur cette source.

Snippet vu 17 217 fois - Téléchargée 27 fois

Contenu du snippet

pour ceux qui cherche un programme qui transforme un afn en afd

Source / Exemple :


///////////////////////////////////////////////////////////////////////////
// Transformation AFN en AFD
//
#include <stdio.h>
#include <stdlib.h>

///////////////////////////////////////////////////////////////////////////
//
//
#define EPSILON		-1
#define NOETAT		-1

///////////////////////////////////////////////////////////////////////////
// A F N
//
typedef struct ptr_list* ptr_list_t;
struct ptr_list
{
	int        info;
	ptr_list_t suiv;
};

typedef struct ptr_trans* ptr_trans_t;
struct ptr_trans
{
	int		    e, s;
	ptr_list_t	vers_e;
	ptr_trans_t suiv;
};

typedef struct
{
	ptr_list_t	letat;
	ptr_list_t	lsymb;
	ptr_trans_t	ltrans;
}afn_t;

///////////////////////////////////////////////////////////////////////////
// A F D
//
typedef struct ptr_detat* ptr_detat_t;
struct ptr_detat
{
	int			e;
	ptr_list_t	letat;
	ptr_detat_t suiv;
};

typedef struct ptr_dtrans* ptr_dtrans_t;
struct ptr_dtrans
{
	int			 de, s, fe;
	ptr_dtrans_t suiv;
};

typedef struct
{
	ptr_detat_t	 ldetat;
	ptr_list_t	 lsymb;
	ptr_dtrans_t ltrans;
}afd_t;

///////////////////////////////////////////////////////////////////////////
// P R O T O T Y P E
//
afn_t* saisie_afn();
void   affiche_afd(afd_t*);
afd_t* afn2afd(afn_t*);
void   free_afn(afn_t*);
void   free_afd(afd_t*);

///////////////////////////////////////////////////////////////////////////
// F O N C T I O N   M A I N
//
void main()
{
	// Variables locales
	afn_t *afn;
	afd_t *afd;

	// Création de l'AFN
	afn = saisie_afn();

	// Transformation de l'AFN
	afd = afn2afd(afn);

	// Affichage des resultats
	affiche_afd(afd);

	// Libération de la mémoire
	free_afn(afn);
	free_afd(afd);
}

///////////////////////////////////////////////////////////////////////////
//
//
void free_list(ptr_list_t p)
{
	while (p)
	{
		ptr_list_t q = p;
		p = p->suiv;
		free(q);
	}
}

///////////////////////////////////////////////////////////////////////////
//
//
void free_afn(afn_t *afn)
{
	ptr_trans_t q, p = afn->ltrans;

	free_list(afn->letat);
	free_list(afn->lsymb);
	while (p)
	{
		q = p;
		p = q->suiv;
		free_list(q->vers_e);
		free(q);
	}
}

///////////////////////////////////////////////////////////////////////////
//
//
void free_afd(afd_t *afd)
{
	ptr_detat_t  q1, p1 = afd->ldetat;
	ptr_dtrans_t q2, p2 = afd->ltrans;
	while (p1)
	{
		q1 = p1;
		p1 = q1->suiv;
		free_list(q1->letat);
		free(q1);
	}
	free_list(afd->lsymb);
	while (p2)
	{
		q2 = p2;
		p2 = p2->suiv;
		free(q2);
	}
}

///////////////////////////////////////////////////////////////////////////
// 
//
void list_inserer(ptr_list_t *ptr, int e)
{
	ptr_list_t p = (ptr_list_t)malloc(sizeof(struct ptr_list));
	p->info = e;
	p->suiv = 0;
	if (*ptr)
	{
		ptr_list_t q;
		for (q = *ptr; q->suiv; q = q->suiv);
		q->suiv = p;
	}
	else

  • ptr = p;
} /////////////////////////////////////////////////////////////////////////// // // afn_t* saisie_afn() { int nbr_etat, nbr_symb, nbr, i, j, k, e; afn_t *afn; ptr_trans_t tr; afn = (afn_t*)malloc(sizeof(afn_t)); afn->letat = 0; afn->lsymb = 0; afn->ltrans = 0; // La list des etats printf("Donner le nombre des etats: "); scanf("%d", &nbr_etat); for (i = 0; i < nbr_etat; i++) list_inserer(&afn->letat, i); /* La list des symboles */ printf("Donner le nombre des symboles (sans compter l'epsilon): "); scanf("%d", &nbr_symb); for (i = 0; i < nbr_symb; i++) list_inserer(&afn->lsymb, i); // La list des transition for (i = 0; i < nbr_etat; i++) for (j = -1; j < nbr_symb; j++) { if (j == -1) printf("De l'etat '%d' combien d'etat vous pouvez atteindre avec le symbole epsilon: ", i); else printf("De l'etat '%d' combien d'etat vous pouvez atteindre avec le symbole %c: ", i, 'a' + j); scanf("%d", &nbr); if (nbr) { tr = (ptr_trans_t)malloc(sizeof(struct ptr_trans)); tr->e = i; tr->s = j; tr->vers_e = 0; for (k = 0; k < nbr; k++) { printf("Vous pouvez atteindre l'etat ? "); scanf("%d", &e); list_inserer(&tr->vers_e, e); } tr->suiv = afn->ltrans; afn->ltrans = tr; } } return (afn); } /////////////////////////////////////////////////////////////////////////// // // void affiche_afd(afd_t *afd) { ptr_detat_t d; ptr_list_t s; d = afd->ldetat; printf(" |"); for (s = afd->lsymb; s; s = s->suiv) printf(" %c |", 'a' + s->info); printf("\n"); for (d = afd->ldetat; d; d = d->suiv) { ptr_dtrans_t ldtr; printf("%c |", 'A' + d->e); for (ldtr = afd->ltrans; ldtr; ldtr = ldtr->suiv) if (ldtr->de == d->e) printf(" %c |", 'A' + ldtr->fe); printf("\n"); } } /////////////////////////////////////////////////////////////////////////// // // void afd_ajouter_etat(ptr_detat_t *ldetat, int e, ptr_list_t letat) { ptr_detat_t lde; ptr_list_t p; lde = (ptr_detat_t)malloc(sizeof(struct ptr_detat)); lde->e = e; lde->letat = 0; lde->suiv = 0; for (p = letat; p; p = p->suiv) list_inserer(&lde->letat, p->info); if (*ldetat) { ptr_detat_t q; for (q = *ldetat; q->suiv; q = q->suiv); q->suiv = lde; } else
  • ldetat = lde;
} /////////////////////////////////////////////////////////////////////////// // // int is_in_list(ptr_list_t letat, int e) { ptr_list_t p; for (p = letat; p; p = p->suiv) if (p->info == e) return (1); return (0); } /////////////////////////////////////////////////////////////////////////// // // int epsilon_arc(afn_t* afn, int se, int fe) { ptr_trans_t p; ptr_list_t q; for (p = afn->ltrans; p; p = p->suiv) if ((p->e == se) && (p->s == EPSILON)) for (q = p->vers_e; q; q = q->suiv) if (q->info == fe) return (1); return (0); } /////////////////////////////////////////////////////////////////////////// // // void empiler_etat(ptr_list_t *p, int e) { ptr_list_t q = (ptr_list_t)malloc(sizeof(struct ptr_list)); q->info = e; q->suiv = *p;
  • p = q;
} /////////////////////////////////////////////////////////////////////////// // // int depiler_etat(ptr_list_t *letat) { int e; ptr_list_t p; if (*letat) { e = (*letat)->info; p = *letat;
  • letat = p->suiv;
free(p); return (e); } else return (NOETAT); } /////////////////////////////////////////////////////////////////////////// // // ptr_list_t epsilon_fermeture(afn_t* afn, ptr_list_t T) { ptr_list_t p, e_f = 0, pile_etat = 0; int t; for (p = T; p; p = p->suiv) { /* On initialise le epsilon fermeture de T à T */ list_inserer(&e_f, p->info); /* On empile tout les etats des T */ empiler_etat(&pile_etat, p->info); } /* Tant que pile est non vide */ while ((t = depiler_etat(&pile_etat)) != NOETAT) { for (p = afn->letat; p; p = p->suiv) { /* Pour chaque etat u avec un arc de t à u etiquite epsilon */ /* u = p->e*/ if (epsilon_arc(afn, t, p->info)) { /* Si u n'appartient pas à epsilon fermeture de T */ if (!is_in_list(e_f, p->info)) { /* Ajouter u à l'epsilon fermeture de T */ list_inserer(&e_f, p->info); /* On empile u dans la pile */ empiler_etat(&pile_etat, p->info); } } } } return (e_f); } /////////////////////////////////////////////////////////////////////////// // // void afd_ajouter_trans(ptr_dtrans_t *ltrans, int de, int fe, int s) { ptr_dtrans_t dtrans = (ptr_dtrans_t)malloc(sizeof(struct ptr_dtrans)); dtrans->de = de; dtrans->fe = fe; dtrans->s = s; dtrans->suiv = 0; if (*ltrans) { ptr_dtrans_t q; for (q = *ltrans; q->suiv; q = q->suiv); q->suiv = dtrans; } else
  • ltrans = dtrans;
} /////////////////////////////////////////////////////////////////////////// // // int afd_trouve_etat(afd_t *afd, ptr_list_t letat) { ptr_detat_t dp; ptr_list_t dp_le, dp_e; for (dp = afd->ldetat; dp; dp = dp->suiv) { int nbr_element = 0; /* Sont t-il egaux en nombre d'element */ for (dp_e = dp->letat; dp_e; dp_e = dp_e->suiv, nbr_element++); for (dp_le = letat; dp_le; dp_le = dp_le->suiv, nbr_element--); if (nbr_element == 0) { for (dp_e = dp->letat; dp_e; dp_e = dp_e->suiv) { int trouve = 0; for (dp_le = letat; dp_le; dp_le = dp_le->suiv) if (dp_le->info == dp_e->info) { trouve = 1; break; } if (trouve == 0) return (NOETAT); } return (dp->e); } } return (NOETAT); } /////////////////////////////////////////////////////////////////////////// // // ptr_list_t transiter(afn_t* afn, ptr_list_t letat, int s) { ptr_list_t p, q, tran = 0; ptr_trans_t tr; for (p = letat; p; p = p->suiv) for (tr = afn->ltrans; tr; tr = tr->suiv) if ((tr->e == p->info) && (tr->s == s)) for (q = tr->vers_e; q; q = q->suiv) list_inserer(&tran, q->info); return (tran); } /////////////////////////////////////////////////////////////////////////// // // afd_t* afn2afd(afn_t *afn) { afd_t *afd; ptr_list_t L = 0, U, s; ptr_detat_t p; int ee, e = 0; afd = (afd_t*)malloc(sizeof(afd_t)); afd->ldetat = 0; afd->lsymb = 0; afd->ltrans = 0; /* L'AFN et l'AFD ont les même symboles */ for (s = afn->lsymb; s; s = s->suiv) list_inserer(&afd->lsymb, s->info); list_inserer(&L, 0); U = epsilon_fermeture(afn, L); afd_ajouter_etat(&afd->ldetat, e++, U); for (p = afd->ldetat; p; p = p->suiv) { for (s = afn->lsymb; s; s = s->suiv) { /* Netoyage de mémoire */ free_list(L); free_list(U); L = transiter(afn, p->letat, s->info); U = epsilon_fermeture(afn, L); ee = afd_trouve_etat(afd, U); if (ee == NOETAT) { /* On lui donne un nom */ ee = e++; afd_ajouter_etat(&afd->ldetat, ee, U); } afd_ajouter_trans(&afd->ltrans, p->e, ee, s->info); } } free_list(L); free_list(U); return (afd); }

A voir également

Ajouter un commentaire Commentaires
Messages postés
43
Date d'inscription
mercredi 17 novembre 2010
Statut
Membre
Dernière intervention
3 juin 2012
1
@Offlake toi aussi tu es beaucoup plus meilleur que tout le monde ...

@SoulReaver : merci pour ton code. Toutefois n'hésite pas à bien commenter tes sources.
Messages postés
190
Date d'inscription
mercredi 3 septembre 2008
Statut
Membre
Dernière intervention
17 janvier 2009

Mon code source est beaucoup plus meilleur que le votre
il fait tout les cas contrairement au votre
voici le lien:
http://www.cppfrance.com/codes/DETERMINISATION-AUTOMATE-ETAT-FINI_48035.aspx
mon MSN:
sami_inf@hotmail.fr
Messages postés
1
Date d'inscription
jeudi 10 mai 2007
Statut
Membre
Dernière intervention
2 avril 2008

merci pour ces lignes de code vous ne savez pas a quel point il m'ont était util
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
4
complexités des diverses fonctions ?
Messages postés
16
Date d'inscription
dimanche 19 octobre 2003
Statut
Membre
Dernière intervention
21 juin 2006

AFD:automate fini deterministe.
AFN:automate fini non deterministe

ils sont utilisés pour l'analyse lexicale dans les compilateurs.
Afficher les 6 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_mido123)