Remerciez-le!

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

Analyse lexicale Compilation, 3LMD 2011 -2012 Université de Biskra Mr. Meadi M.

Analyse lexicale Compilation, 3LMD 2011 -2012 Université de Biskra Mr. Meadi M.Nadjib 4 Chapitre 02 : Analyse lexicale 1. Introduction 2. Définitions 3. Expressions régulières 4. Automates 5. Erreurs Lexicales 6. Mis en œuvre d'un analyseur lexical 7. Outil Lex (générateur d’analyseur Lexical) 1. Introduction L'analyseur lexical constitue la première étape d'un compilateur. Sa tâche principale est de lire les caractères d'entrée et de produire comme résultat une suite d'unités lexicales que l'analyseur syntaxique aura à traiter. En plus, l'analyseur lexical réalise certaines tâches secondaires comme l'élimination de caractères superflus (commentaires, tabulations, fin de lignes, ...), et gère aussi les numéros de ligne dans le programme source pour pouvoir associer à chaque erreur rencontrée par la suite la ligne dans laquelle elle intervient. Analyseur lexical Table des symboles Analyseur syntaxique U.L U.L suivante Code source Analyse sémantique Analyseur Lexicale Ensemble des lexèmes Code source Messages d’erreurs Analyse lexicale Compilation, 3LMD 2011 -2012 Université de Biskra Mr. Meadi M.Nadjib 5 2. Définitions 1. Une unité lexicale est une suite de caractères qui a une signification collective. 2. Un lexème toute suite de caractère du programme source qui concorde avec le modèle d'une unité lexicale. 3. Un modèle (Règle lexicale) est une règle associée à une unité lexicale qui décrit l'ensemble des chaînes du programme qui peuvent correspondre à cette unité lexicale. 4. Attributs : informations concernant le lexème (champs dans la table des symboles) ; Exemples  L'unité lexicale IDENT (identificateurs) en C a pour modèle : toute suite non vide de caractères composée de chiffres, lettres ou du symbole "_" et qui commencent par une lettre. Des exemples de lexèmes pour cette unité lexicale sont : truc, i, a1, ajouter_valeur ...  L'unité lexicale NOMBRE (entier signé) a pour modèle : toute suite non vide de chiffres précédée éventuellement d'un seul caractère parmi. Comme par exemple : -12, 83204, +0 ...  L'unité lexicale REEL a pour modèle : tout lexème correspondant à l'unité lexicale NOMBRE suivi éventuellement d'un point et d'une suite (vide ou non) de chiffres, le tout suivi éventuellement du caractère E ou e et d'un lexème correspondant à l'unité lexicale NOMBRE. Cela peut également être un point suivi d'une suite de chiffres, et éventuellement du caractère E ou e et d'un lexème correspondant à l'unité lexicale NOMBRE. Exemples de lexèmes : 12.4, 0.5e3, 10., -4e-1, -.103e+2 3. Erreurs Lexicales Peu d'erreurs sont détectables au seul niveau Lexical : Plusieurs stratégies sont possibles : - mode panique : on ignore les caractères qui posent problème et on continue. Cette technique se contente de refiler le problème à l'analyseur syntaxique - transformations du texte source : insérer un caractère, remplacer, échanger, etc. Elle se fait en calculant le nombre minimum de transformations à apporter au mot qui pose problème pour en obtenir un qui ne pose plus de problèmes. Cette technique de récupération d'erreur est très peu utilisée en pratique car elle est trop coûteuse à implanter. 4. Expressions régulières Une expression régulière est une notation pour décrire un langage régulier. Soit A un alphabet (un ensemble de lettres), une expression régulière est donc: 1. Les éléments de A,  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 (un nombre quelconque de fois).  est l’élément neutre par rapport à la concaténation et  est l’ensemble vide de caractère, neutre par rapport à l’union. Exemple : (a|b)*abb, Identificateur = alpha (alpha | numer)* En fait, les expressions régulières sont beaucoup plus puissantes que ce dont on a besoin lorsqu’on fait de l’analyse lexicale. Analyse lexicale Compilation, 3LMD 2011 -2012 Université de Biskra Mr. Meadi M.Nadjib 6 Exemple On décrit les lexèmes par des expressions régulières. Les mots clés: "for", "if" Les variables: ['a'-'z']+ ['0'-'9']* Les entiers: ['0'-'9']+ Les symboles: '(', ')', '+', '*', '=' Le lexème vide: (' ' | '\n') L’ordre de priorité Les opérateurs ∗, concaténation et | sont associatifs à gauche, et vérifient 1. ∗ 2. concaténation 3. | Définitions régulières La nomination des expressions régulières est dite une définition régulière. Ces noms seront utilisés pour construire d’autres expressions régulières. On écrit donc d1 → r1 d2 → r2 . . . dn → rn où chaque di est un nom distinct et chaque ri est une expression régulière sur l’alphabet Σ U {d1,d2,di-1} Exemple Voici quelques définitions régulières, et notamment celles de identificateur et nombre, qui définissent les identificateurs et les nombres du langage Pascal : lettre → A | B | . . . | Z | a | b | . . . | z chiffre → 0 | 1 | . . . | 9 identificateur → lettre ( lettre | chiffre )∗ chiffres → chiffre chiffre ∗ frac → . chiffres | ε Exp → ( E (+ | - | ε) chiffres ) | ε nombre → chiffres frac exp Notations abrégées Pour alléger certaines écritures, on complète la définition des expressions régulières en ajoutant les notations suivantes :  Soit x une expression régulière, définissant le langage L(x) ; alors (x)+ est une expression régulière, qui définit le langage (L(x))+ ,  Soit x une expression régulière, définissant le langage L(x) ; alors (x)? est une expression régulière, qui définit le langage L(x) ∪ { ε },  Si c1 , c2,. . ck sont des caractères, l’expressions régulière c1 |c2 |... |ck peut se noter [c1 c2 ... ck],  L’expression [c1–c2] désigne la séquence de tous les caractères c tels que c1 ≤ c ≤ c2 . Exemple Les définitions de lettre et chiffre données ci-dessus peuvent donc se réécrire : lettre → [A–Za–z] chiffre → [0–9] Analyse lexicale Compilation, 3LMD 2011 -2012 Université de Biskra Mr. Meadi M.Nadjib 7 5. Automates Un automate à états finis (AEF) est défini par  un ensemble fini E d'états  un état e0 distingué comme étant l'état initial  un ensemble fini T d'états distingués comme états finaux (ou états terminaux)  un alphabet Σ des symboles d'entrée  une fonction de transition A  E  E qui à tout couple formé d'un état et d'un symbole de fait correspondre un ensemble (éventuellement vide) d'états :  (ei,a)={ei1,…,ein} Les automates sont souvent donnés sous la forme d'un graphe: les états sont les nœuds du graphe et les arcs correspondent à la fonction de transition. Exemple Σ={a,b}, E={0,1,2,3}, e0=0, T={3} δ(0,a)={0,1}, δ(0,b)={0}, δ(1,b)={2}, δ(2,b)={3}, Représentation graphique : Construction d'un AFN à partir d'une E.R. Pour une expression régulière s, on note A(s) un automate reconnaissant cette expression. 1. automate acceptant la chaîne vide 2. automate acceptant la lettre a 3. automate acceptant (r)(s) 1. mettre une ε -transition de chaque état terminal de A(r) vers l'état initial de A(s) 2. les états terminaux de A(r) ne sont plus terminaux 3. le nouvel état initial est celui de A(r) 4. (l'ancien état initial de A(s) n'est plus état initial) 4. automate reconnaissant r|s 1. créer un nouvel état initial q 2. mettre une ε-transition de q vers les états initiaux de A(r) et A(s) 3. (les états initiaux de A(r) et A(s) ne sont plus états initiaux) 5. automate reconnaissant r+ Analyse lexicale Compilation, 3LMD 2011 -2012 Université de Biskra Mr. Meadi M.Nadjib 8 6. Mise en œuvre d'un analyseur lexical A) A la main Un automate peut très facilement être simulé par un algorithme. C'est encore plus facile si l'automate est déterministe. Alors, on peut écrire un programme reconnaissant tout mot de tout langage régulier. Ainsi, si l'on veut faire l'analyse lexicale d'un langage régulier, il suffit d'écrire un programme simulant l'automate qui lui est associé. Exemples Start 1 alpha 2 numer 3 4 oparith-{/} < alpha ou numer numer 6 8 > = 5 = 7 = 9 10 = : 11 ; 13 14 / * * 12 / != * != / 15 buffer=&Buffer[0]; while(1) { c = lireChar(); switch(etat){ case: 0 switch(type(c)){ buffer*=c;buffer++; case ALPHA: etat=1;break; case NUMER: etat=2;break; case OPARITH-{/}: etat=3; break; case '<': etat=4; break; case '>': etat=6; break; case '=': etat=8; break; case ':': etat=9; break; case ';': etat=11; break; case '/': etat=12; break; default: erreur;} break; case 1: if (type(c) == ALPHA ou type(c) == NUMER) { buffer*=c;buffer++; etat=1;} else {buffer*='\0'; remettreCar(); return(ajouter_token(Buffer,TYPE_IDENT));} break; Analyse lexicale Compilation, 3LMD 2011 -2012 Université de Biskra Mr. Meadi M.Nadjib 9 case 2: if (type(c) == NUMER){ buffer*=c;buffer++; etat=2;} else { buffer*='\0';remettreCar(); return(ajouter_token(Buffer,TYPE_NUMER));} break; case 3: return(ajouter_token(Buffer,TYPE_OPER)); break; {{à finir!!}} } B) Automatiquement Il existe des outils pour écrire des programmes simulant des automates à partir de simples définitions régulières. Par exemple : flex uploads/s3/ analyse-lexicale 1 .pdf