Afd (titre trop court)

Télécharger le projet
Commenter

Description

implementation de la fonction AFD, et son utilisation dans un petit exemple

Source / Exemple : 


#include <stdio.h>
#include <string.h>
#include <malloc.h>

// Structure de donn?es :
const MaxState = 20;
typedef int Transition[MaxState][256];
typedef char SetOfStates[MaxState];
enum VT {CODE};

// Variables globales :
unsigned char InputTape[1024]="";
int ReadHead = 0;
char *Lexeme;
int UL;
FILE *InputFile;

// Fonctions g?n?rale :
int AFD(Transition T, SetOfStates A, int Nom) {
	int e = 0;
	int Save = ReadHead;
	unsigned char s = InputTape[ReadHead];
	while (T[e][s]!=-1) {
		e = T[e][s];
		ReadHead++;
		s = InputTape[ReadHead];
	}
	if (strchr(A,e) && e!=0) {
		Lexeme = (char *)realloc(Lexeme,ReadHead-Save);
		strncpy(Lexeme, &InputTape[Save],ReadHead-Save);
		Lexeme[ReadHead-Save] = 0;
		UL = Nom;
		return 1;
	}
	else {
		ReadHead = Save;
		return 0;
	}
}

void init(Transition &T, int val) {
	for (int e=0; e<MaxState; e++)
		for (int s=0; s<256; s++) T[e][s] = val;
}

void ErreurLexicale() {
	printf("Erreur lexicale sur le symbole : '%c'\n",InputTape[ReadHead]);
	ReadHead++;
}

char *Desig(int ul) {
	switch (ul) {
			case CODE  : return "CODE";
		    }
	return "Inconnu";
}

void ExtraireLexeme(int Nom) {
	Lexeme = (char *)realloc(Lexeme,2);
	sprintf(Lexeme,"%c",InputTape[ReadHead]);
	UL = Nom;
	ReadHead++;
}

int ChargerTampon() {
	if (InputTape[ReadHead] == 0) {
		if (fgets(InputTape, 1024, InputFile)) {
			ReadHead = 0;
			return 1;
		}
		else return 0;
	}
	else return 1;
}

Conclusion :


avant tout, AFD est l'abréviation de "Automate à état Fini Déterministe", on l'utilise lors de l'analyse du code du compilateur:
vous savez que le compilateur passe par quatre étapes pour traduire le code qu'implémente le programmeur en un code machine.
ces étapes sont:
+Interpréteur: c'est comme le compilateur sauf que le compilateur génère un fichier (.obj) et l'interpréteur traduit le code d'un langage de programmation et le place directement dans la mémoire du PC.
+Assembleur: c'est un compilateur de base, il fait 2 passes sur le code programme,la première c'est pour affecter dans un tableau à toutes les variables utilisées dans le programme leur adresses mémoires, la deuxième consiste à traduire chaque code opération (comme move) en son code binaire.
+Assemblage: je crois que vous le connaissez(exp:mov Ax,X), il emploie des registres et des mots significatifs pour le programmeur.
+Binaire: c'est le codage de 0 et 1, ca veut dire traduire toutes les instructions en binaire.
Avant d'effectuer toutes ces étapes, il faut bien s'assurer que le code tapé par le programmeur est juste d'une vue lexicale, syntaxique et sémantique pour pouvoir générer le code intermédiaire.
Alors le rôle du AFD c'est faire ces testes:
on a remarqué que la façon la plus significative pour présenter un problème c'était à l'aide des expressions régulières(une notation avec des symboles universelles) qui sera traduite en AFN(Automate Finis Non déterministe) puis en AFD qui va pouvoir extraire les lexèmes du code.
les lexèmes sont des chaines valides du langage(exp: ac01 est un lexeme qui présente un identificateur ,01ac n'est pas un lexème car l'identificateur est une chaine alphanumérique mais qui commence par UNE LETTRE), et comme ca on peut répartir notre code en nombre de lexème dont on a besoin.
->Formalisme d'un AFD:
Un automate est une machine permettant d'analyser un ruban d'entrer(défini dans le programme par Input Tape) en utilisant une tête de lecture(Read Head) qui permet de pointer sur les symboles successifs du ruban d'entrer, et pour réaliser ce travail, l'AFD se définie comme un ensemble de 5 éléments:
- un ensemble qui regroupe les symboles sur lesquels on transite d'un état à un autre.
- un ensemble qui regroupe tous les états sur lesquels on transite.
- une variable e0 qui indique l'état avec lequel on a demarré.
- un ensemble qui regroupe les états finaux.
- un tableau de transition et qui donne le résultat de la transition de chaque état sur chaque symbole s'il existe(il est traduit par la fonction transition dans le programme)
si vous avez envie de savoir plus sur les automates, n'hésitez pas à me le demander, je vous ferai un petit exemple qui les explique.
j'espere que j'ai été claire, et pardon pour tous les détails en début parce que et comme vous constatez il est impossible de comprendre la fonction si vous ne compreniez pas le pourquoi et le comment des choses.
puis pardon pour le retard parce que j'ai dû rédige tout ca ;)
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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 (ghitaik)