automate non déterministe en c

Version imprimable

Bonjour ! j'essaye actuellement de construire un AFN en c. Enfaite il faut je complete des fonctions donnée par mon prof mais je m'en sort pas.

voici ce que nous a donner mon prof

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#ifndef AFN_H
#define AFN_H
 
#define ASCII_FIRST 38
#define ASCII_LAST 127
#define MAX_SYMBOLES 90
 
struct AFN{
  int Q,lenI,lenF,lenSigma;
  int *I,*F;
  char * Sigma;
  char dico[MAX_SYMBOLES];
  int ***delta;
};
 
typedef struct AFN * AFN;
 
AFN afn_init(int Q, int nbInitiaux,int * listInitiaux, int nbFinals, int * listFinals, char *Sigma);
void afn_print(AFN A);
void afn_free(AFN A);
 
void afn_ajouter_transition(AFN A, int q1, char s, int q2);
AFN afn_finit(char *file);
int * afn_epsilon_fermeture(AFN A, int *R);
int afn_simuler(AFN A, char *s);
 
 
#endif

je voulais commencer avec afn_init qui initialise un AFN et voici ce que j'ai fait

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
AFN afn_finit(char *file){
 
  FILE* fichier=NULL;
  fichier=fopen(file,"r");
  char chaine[100]="";
  int Q,q0,nbeFinal;
 
  if (fichier != NULL)
  {
    fgets(chaine,10,fichier); //3
    sscanf(chaine,"%d",&Q);//nb d'etats
 
    fgets(chaine,10,fichier);//0
    sscanf(chaine,"%d",&q0); //nb etats initiaux
 
    int* ini=malloc(sizeof(int)*q0); // reccupere les états initiaux
    fgets(chaine,10,fichier);
    int i=0,tmp,lig=0;
 
    for(i=0;i<q0;i++)
    {
      sscanf(&chaine[lig],"%d",&tmp);
      ini[i]=tmp;
      lig=lig+tmp/10+1;
    }
 
    fgets(chaine,10,fichier);//2
    sscanf(chaine,"%d",&nbeFinal); // les etats finaux
 
    int* f=malloc(sizeof(int)*nbeFinal); //03
    fgets(chaine,10,fichier); //les etats finaux (0 et 3)
    i=0,tmp=0,lig=0;
 
    for(i=0;i<nbeFinal;i++){
      sscanf(&chaine[lig],"%d",&tmp);
      f[i]=tmp;
      lig=lig+tmp/10+1;
    }
 
 
    fgets(chaine,10,fichier); //reccuperation des symboles
    char* alphabet =malloc(sizeof(char)*strlen(chaine)); //motifab
    strcpy(alphabet,chaine);
    alphabet[strlen(alphabet)-1]='\0';
 
    AFN A=afn_init(Q,q0,ini,nbeFinal,f,alphabet);
 
 
    fclose(fichier);
    return A;
}

mon problème dans cette fonction c'est que je dois rajouter les transitions et les epsilones transition mais je ne sais pas comment faire...
Je vous remercie d'avance pour votre aide:)

26/10/2022, 19h35
edgarjacobs

Hello,

Ton prof doit avoir un petit côté sadique: avoir un triple pointeur, c'est rare. Même les plus aguerris en C évitent ce genre de variable.

Salut,

Tu bloques sur quoi ?
Le fichier contient quoi ?

Pour la structure de la fonction afn_finit(), je verrai un truc du genre :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
AFN afn_finit(char *file){
 
	// *******************
	// Déclaration des variables
	FILE* fichier;
	#define LINE_MAX_LEN (100)
	char ligne[LINE_MAX_LEN + 1];
 
	#define LIST_MAX_SIZE (100)
	int Q;
	int nbInitiaux;
	int listInitiaux[LIST_MAX_SIZE];
	int nbFinals;
	int listFinals[LIST_MAX_SIZE];
	char * Sigma;
 
 	// *******************
	// Initialisation des paramètres
	// Remarque : les valeurs choisie ne doivent pas
	// faire bugguer la fonction afn_init() car le fichier
	// peut être vide.
	Q = ???;
	char *Sigma
	nbInitiaux = 0;
	nbFinals = 0;
	Sigma = NULL;
 
	// *******************
	// Récupération du contenu du fichier
	fichier = fopen(file,"r");
	if (fichier != NULL){
		while (fgets(ligne, sizeof(ligne), file) != NULL){
			if(line_count >= LIST_MAX_SIZE){
				// Erreur : nombre max de ligne dépassé
				// => Que faire ??? Réinitialisation des paramètres par défaut ????
				break;
			}
 
			// **************
			// TODO : traitement de la ligne
			// ...
			Q = ???;
			listInitiaux[nbInitiaux] = ????;
			nbInitiaux++;
			listFinals[nbFinals] = ????;
			nbFinals++;
			*Sigma = ???;
		}
		fclose(fichier);		
	}
 
 
	// *******************
	return afn_init(Q, nbInitiaux, listInitiaux, nbFinals, listFinals, Sigma);
}

Attention dans mon exemple, listInitiaux et listFinals sont déclarés dans la stack donc en fonction de ce que fait la fonction afn_init(), il faut peut-être les déclarer dans la heap (utilisation de malloc).

Bonjour

Citation:

Envoyé par edgarjacobs

Ton prof doit avoir un petit côté sadique: avoir un triple pointeur, c'est rare. Même les plus aguerris en C évitent ce genre de variable.

Ce n'est pas tant le triple étoile, on peut arriver à faire l'abstraction (si par exemple on traite une matrice de strings, une étoile disparait de la réflexion), c'est surtout ce typedef struct AFN * AFN qui cherche à cacher l'étoile derrière un type. Ca c'est ce qu'il y a de pire dans un code.
Citation:
Envoyé par e5mm100
je voulais commencer avec afn_init qui initialise un AFN et voici ce que j'ai fait
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 AFN afn_finit(char *file){ FILE* fichier=NULL; fichier=fopen(file,"r"); char chaine[100]=""; int Q,q0,nbeFinal; if (fichier != NULL) { fgets(chaine,10,fichier); //3 sscanf(chaine,"%d",&Q);//nb d'etats fgets(chaine,10,fichier);//0 sscanf(chaine,"%d",&q0); //nb etats initiaux int* ini=malloc(sizeof(int)*q0); // reccupere les états initiaux fgets(chaine,10,fichier); int i=0,tmp,lig=0; for(i=0;i<q0;i++) { sscanf(&chaine[lig],"%d",&tmp); ini[i]=tmp; lig=lig+tmp/10+1; } fgets(chaine,10,fichier);//2 sscanf(chaine,"%d",&nbeFinal); // les etats finaux int* f=malloc(sizeof(int)*nbeFinal); //03 fgets(chaine,10,fichier); //les etats finaux (0 et 3) i=0,tmp=0,lig=0; for(i=0;i<nbeFinal;i++){ sscanf(&chaine[lig],"%d",&tmp); f[i]=tmp; lig=lig+tmp/10+1; } fgets(chaine,10,fichier); //reccuperation des symboles char* alphabet =malloc(sizeof(char)*strlen(chaine)); //motifab strcpy(alphabet,chaine); alphabet[strlen(alphabet)-1]='\0'; AFN A=afn_init(Q,q0,ini,nbeFinal,f,alphabet); fclose(fichier); return A; }
mon problème dans cette fonction c'est que je dois rajouter les transitions et les epsilones transition mais je ne sais pas comment faire...
S'il n'y avait que ça comme problème...
Moi ce que je vois, c'est que tu as par trois fois alloué de la mémoire (pour "ini", pour "f" et pour "alphabet") et que ces zones allouées ne sont ensuite récupérées nulle part (donc fuite mémoire).
C'est quand-même dommage pour "alphabet" car il semble qu'il récupère le contenu de "chaine" (chaine définie comme un tableau de 100 car mais qui n'en charge en réalité que 10 :weird:) donc on peut se dire que "alphabet" aurait pu parfaitement être lui-aussi défini comme "chaine", à savoir un tableau. Ou mieux, aurait pu ne pas exister vu qu'il existe déjà dans "chaine"...

Et comme je l'ai dit plus haut, on ne cache jamais une étoile derrière un type. Ca c'est une habitude de profs de C qui soit ne savent pas manipuler les pointeurs, soit ne savent pas apprendre à leurs élèves à les manipuler et qui préfèrent cacher la merde sous le tapis plutôt que de l'affronter. C'est bien dommage que tu sois tombé sur un tel prof mais il n'est pas trop tard pour, de ton côté, apprendre à gérer correctement et surtout sereinement les pointeurs.