Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours de compilation, Analyse lexicale Mr HAMMOUDA Mohamed USDB, 3ème année lic

Cours de compilation, Analyse lexicale Mr HAMMOUDA Mohamed USDB, 3ème année licence, SI Analyse lexicale Introduction: - Première phase d'un compilateur - Tâche principale: Lire le texte source (PS) et produire une suite d'unités lexicales (UL) pour l'analyseur syntaxique - Tâches secondaires: o Eliminer les caractères superflus (commentaires, espaces, tabulations, …) o Gérer les numéros de ligne du texte source (associer les erreurs aux lignes) Les techniques des AL peuvent être appliquées à d'autres domaines: - Moteurs de recherche - Les langages d'interrogation - Les systèmes de recherche d'information Définitions: - Unité lexicale (token): suite de caractères qui a une signification collective, exemple:  OPREL (opérateurs de relation) : >=, <=, <, >, …  ID (Identificateurs) : suite de caractères alphanumériques  MC (les mots clés) : if, else, while, … - Lexème (mot): suite de caractères du programme qui concorde avec un modèle d'une unité lexicale - Modèle (règle lexicale): est une règle associée à une unité lexicale qui décrit l'ensemble des chaînes du programme (lexèmes) qui peuvent correspondre à cette unité lexicale. Exemple la règle (ou l'expression régulière) lettre(chiffre|lettre)* pour ID. - Attribut: informations concernant le lexème (champs dans la table des symboles) Analyeur lexical Analyeur syntaxique Table de symboles PS UL Cours de compilation, Analyse lexicale Mr HAMMOUDA Mohamed USDB, 3ème année licence, SI Mise en œuvre d'un AL: (1) Définir les unités lexicales du langage. (2) Décrire chaque unité lexicale par une expression régulière (3) Construire le modèle (AEF) de chaque expression régulière L'ensemble des modèles obtenus constitue l'analyseur lexical (l'exemple de l'introduction) Principe de fonctionnement: (1) Parcourir le texte d'entrée caractère par caractère pour extraire les lexèmes. (2) Trouver pour chaque lexème son modèle correspondant. (3) Attribuer l'unité lexicale au lexème. (4) Erreur si aucun modèle ne correspond au lexème. (5) Passer au lexème suivant. (6) Fin du texte. Expressions régulières (e.r) Les e.r sont des notations qui vont nous permettre de spécifier des modèles, chaque modèle reconnaît un ensemble de sous chaînes. Une (e.r) sur un alphabet A et les langages qu'elles décrivent sont définis récursivement de la manière suivante: - ε est une e.r qui décrit {ε} - si a ϵ A, alors a est une e.r qui décrit {a} - si r est une e.r qui décrit le langage R, alors r* et r+ décrivent respectivement R* et R+ - si r et s deux e.r qui décrivent respectivement R et S alors r|s et r.s deux e.r décrivant respectivement RS et R.S - il n'y a pas d'autres e.r L'ordre de priorité: * ou +, concaténation, | Les opérateurs sont associatifs à gauche Exemple 1: Le tableau qui suit montre pour chaque mot l'expression régulière qui le génère. Mot a(ab)aab (ab)a a(aba baba) Aucune ε x aaaab x abaab x a x x aabb x aba x ababa x bbb x aaa x abbbaaa x Cours de compilation, Analyse lexicale Mr HAMMOUDA Mohamed USDB, 3ème année licence, SI Définition régulière: d1 --------------> r1 d2 --------------> r2 ………………………. di sont des noms des e.r d3 --------------> r3 ri des e.r sur {d1, d2, …} Exemple 2: les identificateurs du PASCAL: lettre --------------> A|B|…|Z|a|b|…|z| chiffre --------------> 0|1| … |9 id --------------> lettre (lettre|chiffre)* Construction d'un modèle: (1) Décrire usuellement l'ensemble des unités lexicales du langage. Exemple: Un identificateur est une suite de caractères alphanumérique dont le premier est une lettre de l'alphabet (2) Décrire chaque unité lexicale par une expression régulière. lettre  A|B|…|Z|a|b|…|z| chiffre  0|1| … |9 ident  lettre (lettre|chiffre)* (3) Construire un automate fini non déterministe (A.F.N) pour chaque expression régulière. (4) Déterminiser chaque A.F.N pour construire son automate fini déterministe (A.F.D) correspondant. (5) Minimiser l'ensemble des A.F.D obtenus. (6) Chaque A.F.D est un modèle pour une unité lexicale. 0 1 lettre lettre|chiffre Cours de compilation, Analyse lexicale Mr HAMMOUDA Mohamed USDB, 3ème année licence, SI Définition d'un AFN: un automate fini est dit non déterministe (AFN) s'il possède des ε-transitions (transitions avec ε) ou s'il existe un état qui possède plus d'une transition pour un symbole. Algorithme de passage d'une expression régulière à un AFN Exemple 3: (a|b)*c 1ère étape : a 2ème étape: b 3èmeétape : a|b 4èmeétape : (a|b)* 5èmeétape : (a|b)*c 1) a 1 2 a 2) ab 3 1 2 a b 3) a|b 1 2 0 b a 4) a* ε 1 2 a ε 5) a+ 1 2 a ε 1 0 a 1 0 b 1 0 a 2 b 3 ε ε ε ε ε 1 0 a 2 b 4 c 3 ε ε ε ε ε 1 0 a 2 b Cours de compilation, Analyse lexicale Mr HAMMOUDA Mohamed USDB, 3ème année licence, SI Construction d'un AFD à partir d'un AFN Définitions: - Un AFD est un automate qui ne possède ni des ε-transitions ni des états avec plus d'une transition sur le même symbole. - ε-fermeture(T)=T  {états atteignables par ε depuis T}, T ensemble d'états Algorithme de calcul de ε-fermeture(T): Début P:=T; / P une pile ε-fermeture(T):=T; Tantque P non vide faire depiler(e); T':= (e, ε); /* T' ensemble des états atteignables par ε */ Pour tout e' de T' Si e'n'est pas dans ε-fermeture(T) Alors ε-fermeture(T):= ε-fermeture(T){e'} empiler(e'); FinSi FinPour FinTantque Fin Exemple 4 ε-fermeture ({1}) = {1}  {2, 5, 6, 7} ε-fermeture ({8}) = {8}  {1, 2, 5, 6, 7} 1 2 3 4 5 6 7 8 c a ε ε ε ε ε a b Cours de compilation, Analyse lexicale Mr HAMMOUDA Mohamed USDB, 3ème année licence, SI Algorithme de déterminisation: Début (1) Partir de l' ε-fermeture de l'état initial (2) Rajouter dans la table de transition toutes les ε-fermetures des nouveaux états produits avec leurs transitions (3) Recommencer (2) jusqu'à ce qu'il n'y ait plus de nouvel état (4) Tous les états contenant au moins un état terminal deviennent terminaux (5) Renuméroter les états Fin Exemple 5: On reprend l'AFN de l'exemple 4 AFN Etat a b c ε →0 1 2 3 1 0,3 2 0,3 3 4 ←4 AFD Etat a b c {0} {3} {1} {0,3} {2} {0,3} {4} {1} {0,3} {1} {0,3} {2} {0,3} {4} {2} {0,3} {1} {0,3} {2} {0,3} {4} {4} - - - Renumérotation Etat a b c →0 1 2 3 1 1 2 3 2 1 2 3 ←3 - - - 4 c 3 ε ε ε ε ε 1 0 a 2 b 1 2 0 b a 3 c b b a c c Cours de compilation, Analyse lexicale Mr HAMMOUDA Mohamed USDB, 3ème année licence, SI Algorithme de minimisation d'un AFD (1) Construire deux classes: A classe des états finaux et B classe des états non finaux (2) s'il existe un symbole a et deux états e1 et e2 d'une même classe tels que (e1,a) et (e2,a) n'appartiennent pas à la même classe alors ajouter une nouvelle classe et séparer e1 et e2. (3) reprendre (2) jusqu'à ce qu'il n’y ait plus de classes à séparer (4) Les classes obtenues constituent les états de l'AFD minimisé. Exemple 6: 1 2 3 4 5 a b b b a a a a 1 2 3 45 a b b a a a uploads/Management/ analyse-lexicale.pdf