Remerciez-le!

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

SAOUDI Lalia Analyse lexicale 2007/2008 Page 6 II. Analyse lexicale 1. Introduc

SAOUDI Lalia Analyse lexicale 2007/2008 Page 6 II. Analyse lexicale 1. Introduction : L'analyse lexicale constitue la première phase de compilation ; elle consiste à segmenter un texte source en un ensemble de mots qu’on appelle traditionnellement «tokens» (leur terme exact est «lexème», ce qui signifie unité lexicale, que l’analyseur syntaxique va utiliser ; cette interaction est implantée en faisant de l’analyseur lexical un sous programme de l’analyseur syntaxique, à la réception d’une commande « prochaine unité lexicale » émanant de l’analyseur syntaxique, l’analyseur lexical lit les caractères d’entrées jusqu’à ce qu’il puisse identifier la prochaine unité lexicale. Unité lexicale Pgm source-- analyseur lexical---------------------- analyseur syntaxique <---------------------- Obtenir prochaine unité lexicale Table des symboles Il peut également réaliser certaines taches secondaires, une de ces tâches est l’élimination dans le programme source des commentaires et des espaces qui apparaissent sous formes de caractères blanc tabulation ou fin de ligne. Une autre tâche consiste à relier les messages d’erreur issus du compilateur au programme source par exemple un analyseur lexical peut associer un message d’erreur au numéro de ligne. 2 . Unité lexicale Définition : Une unité lexicale est une suite de caractères qui a une signification collective Exemple : Les chaines <,>,= sont des opérateurs relationnels, l’unité lexicale est OPREL par exemple Définition Un modèle est une règle associe à unité lexicale qui décrit l’ensemble des chaines du programme qui peuvent correspondre à cette unité lexicale Définition : on appelle lexème toute suite de caractère du pgm source qui concorde avec le modèle d’une unité lexicale. Exemple L’unité lexicale IDENT (identificateur) en C a pour modèle toute suite non vide de caractère composé de chiffre, lettre, ou des symboles et qui commence par une lettre Exemple de lexème pour cette unité lexicale sont a ; b ; montant, tot1…. Pour décrire un modèle d’une unité lexicale on utilisera les expressions régulières. SAOUDI Lalia Analyse lexicale 2007/2008 Page 7 3 .Rappels: Dans cette partie, nous introduisons quelques notions de base de la théorie des langages Les expressions régulières est une notation importante pour spécifier des modèles. Chaque modèle reconnait un ensemble de chaines. Rappels de notation On appellera alphabet un ensemble fini dont les éléments seront appelés lettres. Exemple : 0,1 sont les lettres de l’alphabet binaire Un mot sur un alphabet A est une suite finie d’éléments de A. Un mot de longueur n composé des lettres a1, a2……., an sera noté a1a2 …an, le mot vide est noté ε La concaténation de deux mots w1 et w2 est notée w1w2 L’ensemble des mots sur A est noté A* Un langage sur un alphabet A est un ensemble de mots de A* Opérations sur les langages L U M= {s/sϵL ou sϵM} LM={st/sϵL et tϵM} L*=U i=0 Li L+=U i=1Li 4. Expression régulière Une expression régulière est une formule close permettant de désigner un ensemble de chaines de caractères construites à partir d’un alphabet ∑ (éventuellement augmentée de la chaine vide). On appelle cet ensemble de chaîne de caractère un langage. Une expression régulière est une notation pour décrire un langage régulier. Soit ∑ un alphabet (un ensemble de lettres), une expression régulière est donc 1. Les éléments de ∑, ε et Ø sont des expressions régulières. 2 .Si α et β sont des expressions régulières, alors (α | β), (αβ) et α* sont des expressions régulières. (α | β)représente l’union, (αβ) la concaténation et α * la répétition (C’est donc l’union des concaténations de α avec lui même zéro fois (c’est `a dire la chaîne vide) ou plus. ε est l’élément neutre par rapport à la concaténation et Ø est l’ensemble vide de caractère, neutre par rapport à l’union. On peut éviter les parenthèses dans des expressions régulières si l’on adopte les conventions suivantes : 1- * a la plus haute priorité et est associatif à gauche 2- La concaténation a la deuxième plus haute priorité 3- / a la plus faible priorité Exemple : SAOUDI Lalia Analyse lexicale 2007/2008 Page 8 1-Selon ces conventions, (a)/ ((b)* (c)) <-->à a/b*c Les deux expressions dénotent l’ensemble des chaines qui ont soit un seul a ou un nombre quelconque ; ou nul ; de b suivi par un c 2 - Soit C={a,b} 1. l’expression réguliere a |b dénote l’ensemble {a,b} 2. L’expression régulière (a |b) (a |b) dénote {aa,ab,ba,bb} l’ensemble de toutes les chaines de a et b de longueur 2 3. L’expression régulière a* dénote l’ensemble de toutes les chaines formées d’un nombre quelconque de a, c. à. d {ε,a,aa,aaa, ……………..} 4. l’expression régulière a|a*b dénote l’ensemble contenant la chaine a et toutes les chaines constituées d’un nombre quelconque de a (éventuellement nul) suivi de b. Notations abrégées : 1. Au moins une instance : r + =rr* 2. Zéro ou une instance : r ? c une abréviation de r| ε 3. ε r°= ε 4. Classes de caractères : la notation [abc] où a,b,c sont des symboles d’alphabets dénote l’expression régulière a/b/c Une classe de caractères comme [a-z] dénote l’expression réguliere a/b/c…../z On peut décrire un identificateur comme Identificateur = lettre (lettre | chiffre|sep)* Tel que lettre=[a-zA-Z] Chiffre=[0-9 ] Sep=_ 5.Reconnaissance des unités lexicales Un reconnaisseur pour un langage est un pgm qui prend en entrée une chaine x et répond oui si x est un mot du langage et non autrement. On compile une expression réguliere en un reconnaisseur en construisant un diagramme de transition généralisé appelé automate fini. Pour illustrer cette section nous allons nous donner comme exemple le problème de la reconnaissance des unités lexicales INFEG, DIFF, INF, EGAL, SUPEG, SUP, IDENTIF, respectivement définies par les expressions régulières <=, <>, <, =, >=, > et lettre(lettre/chiffre)*. Par exemple, figure suivante montre les diagrammes traduisant la reconnaissance des unités lexicales INFEG, DIFF, INF, EGAL, SUPEG, SUP et IDENTIF. SAOUDI Lalia Analyse lexicale 2007/2008 Page 9 Les automates fini peut être déterministes ou non ; sont capables de reconnaitre exactement ce que les expressions régulières peuvent dénoter, cependant il ya un conflit temps / espace ; alors les AFD peuvent conduire à des reconnaiseurs plus rapide que les AFND ; un AFD peut être beaucoup volumineux qu’un AFND. Les automates finis non déterministe Un automate fini non déterministe (AFND) est un quintuplet A=(Q , ,δ,q0, F), où -Q est in ensemble fini d’états -  est un alphabet - δ : Q x  u { ε }  Q est la fonction de transition -q0 est l’état initial - F est l’ensemble des états terminaux ou finaux Un automate non-déterministe est un automate qui présente la particularité suivante : Plusieurs arcs reconnaissant le même caractère peuvent « sortir » du même état. Il peut y avoir des transitions, notées ε, qui ne correspondent à une aucune reconnaissance de caractères. Le langage reconnu par un automate (Q , ,δ,q0, F) est l’ensemble des mots w tels qu il existe q F tel que q0---w q SAOUDI Lalia Analyse lexicale 2007/2008 Page 10 Présentation de l’automate : Un automate est souvent représenté par un graphe orienté dont les sommets sont les états et les arêtes étiquetées correspondent aux transitions, on distingue les états d’acceptations que l’on entourera d’un cercle et l’état initial. Exemple : construire l’AFN qui reconnait le langage ( a/b) * abb. Le langage défini par un AFN est l’ensemble des chaines d’entrée qu’il accepte. Un AFN accepte une chaine d’entrée x si et seulement s’il existe un certain chemin dans le graphe de transition entre l’état initial et l’état final Automate fini déterministe. L’automate est dit déterministe lorsque 1. la fonction δ associe à chaque couple (état, lettre) un état unique 2. aucun état n’a de ε transition 6. EXPRESSIONS REGULIERES ET AUTOMATES Pour être capable de construire un automate qui reconnaisse un langage régulier quelconque, il suffit d’avoir un mécanisme qui reconnait chaque lettre, puis un mécanisme qui reconnait la Concaténation, l’union et la fermeture de langages reconnus. Construction d’un AFN à partir d’une expression réguliere : Donnée : une expression réguliere r sur un alphabet ∑ Résultats : Un AFN qui connait L(r) SAOUDI Lalia Analyse lexicale 2007/2008 Page 11 Méthode : On décompose d’abord r en ses sous expressions. Puis, en utilisant les règles 1 et 2, on construit des automates pour chacune des symboles de base c.à.d. soit ε soit les symboles de l’alphabet Ensuite en se guidant sur la structure syntaxique de l’expression régulière r, on combine récursivement les AFN de chaque sous expression de r, en utilisant la règle 3 jusqu’à obtenir l’AFN pour l’expression complète Si les expressions régulières r 1 et r 2 sont reconnues respectivement par les automates A1 et A2, avec q0 comme état initial et q comme un état final alors 0-si r= Ø alors l’automate a deux états distincts q0 et q sans transition entre eux (q n’est donc pas atteignable) 1-si r=ε alors l’automate a un seul état q0=q et pas de transitions. 2-Si R=a alors on met une seule transition entre q0 et q. 3- Si r=(r1|r2) Un automate connaissant r1|r2 uploads/s3/ analyse-lex.pdf