Accueil > > > AFD
 AFD
 Information sur la source
 Description
implementation de la fonction AFD, et son utilisation dans un petit exemple
 Source
- #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;
- }
#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 ;)
 Historique
- 04 novembre 2004 02:11:55 :
- ajout d'une explication de la fonction plus le zip
- 30 août 2005 00:42:46 :
- a
 Sources de la même categorie
 Commentaires et avis
|
Derniers Blogs
 COMMENT MAPPER UNE VUE SQL SUR UNE COLLECTION DE COMPLEX TYPE?COMMENT MAPPER UNE VUE SQL SUR UNE COLLECTION DE COMPLEX TYPE? par Matthieu MEZIL
Avec EF, les vues doivent être mappées sur des entity types. Le problème c'est que les entity types doivent avoir une clé. Avec EF, nous avons les complex type qui n'ont pas de clé mais les vues ne peuvent pas être mappées dessus. Avec EF4, il est possibl...
Cliquez pour lire la suite de l'article par Matthieu MEZIL [WF4] UN BINDING ACTIVITY/ACTIVITYDESIGNER QUI PASSE MAL?[WF4] UN BINDING ACTIVITY/ACTIVITYDESIGNER QUI PASSE MAL? par JeremyJeanson
Certain d'entre vous on peut être vécu cette situation embarrassante après quelques temps passer avec WF4 : Au début avec mon " ActivityDesigner" , tout allait bien. Et puis un jour j'ai au des problèmes de " Binding" . Alors nous sommes allé sur le site ...
Cliquez pour lire la suite de l'article par JeremyJeanson MYTIC - SHAREPOINT 2010 : DéJà UN MYTHE MICROSOFT ?MYTIC - SHAREPOINT 2010 : DéJà UN MYTHE MICROSOFT ? par junarnoalg
La prochaine session de MyTIC aura lieu à Namur, le 23 mars prochain. Pendant presque une heure, nous parlerons de SharePoint 2010. Voici un aperçu du programme.
Accueil : 17h30 Début de la session : 18h00 - Les nouvelles int...
Cliquez pour lire la suite de l'article par junarnoalg
Logiciels
 Academy System (10.9.4.0)ACADEMY SYSTEM (10.9.4.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Xilisoft Convertisseur Vidéo Ultimate (5.1.39.0305)XILISOFT CONVERTISSEUR VIDéO ULTIMATE (5.1.39.0305)Xilisoft Convertisseur Vidéo Ultimate est un outil puissant de conversion vidéo, facile à utilise... Cliquez pour télécharger Xilisoft Convertisseur Vidéo Ultimate Xilisoft DVD Ripper Ultimate (5.0.64.0304)XILISOFT DVD RIPPER ULTIMATE (5.0.64.0304)Xilisoft DVD Ripper Ultimate est un logiciel excellent pour copier et convertir DVD vers presque ... Cliquez pour télécharger Xilisoft DVD Ripper Ultimate Rigs of Rods (63.3)RIGS OF RODS (63.3)c'est un jeu de multi-simulation camions,autobus voitures, avions, bateaux, hélicoptère avec défo... Cliquez pour télécharger Rigs of Rods
|