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 Chapitre 2 1 III- L'analyse lexicale - Plan: 1- Le rôle d'

Cours de Compilation Chapitre 2 1 III- L'analyse lexicale - Plan: 1- Le rôle d'un analyseur lexical 2- Terminologie 3- Spécification des unités lexicales 3.1- Chaînes et langages 3.2- Opérations sur les langages 3.3- Expressions régulières 3.4- Définitions régulières 4- Reconnaissance des unités lexicales 5- Le langage FLEX 5.1- Structure d'un programme FLEX 5.2- Ecriture d'un analyseur lexical avec FLEX 2 III- L'analyse lexicale 6- Automates à états finis (AEF) 6.1- Automates à états finis non déterministes (AFN) 6.2- Tables de transition 6.3- Automates à états finis déterministes (AFD) 7- Grammaires régulières 8- Des expressions régulières aux automates 8.1- Conversion d'un AFN en AFD 8.2- Construction d'un AFN à partir d'une expression régulière 8.3- Minimisation du nombre d'états d'un AFD 3 1- Le rôle d'un analyseur lexical: L'analyseur lexical est chargé de lire le texte d'entrée, caractère par caractère, de la gauche vers la droite et isoler les mots et leur classe. De plus, il doit: - éliminer les blancs (espaces, tabulations, fin de lignes) et les commentaires. - détecter les erreurs et associer des messages d'erreurs. 4 1- Le rôle d'un analyseur lexical: table des symboles unité lexicale texte Analyse et attributs Analyse reste d'entrée lexicale prochaine syntaxique unité lexicale traitement des erreurs Interaction entre analyseur lexical et analyseur syntaxique. 5 2- Terminologie - Unité lexicale: est un symbole terminal de la grammaire du langage. - Modèle: est une règle qui décrit un ensemble de chaînes associées à la même unité lexicale. - lexème: est une suite de caractères du texte d'entrée qui concorde avec le modèle. Exemple: 35 est un lexème (un mot) qui appartient à l'unité lexicale (la classe) nombre. 6 2- Terminologie Remarques: Dans de nombreux langages, les classes suivantes couvrent la plupart des unités lexicales: 1- Une unité lexicale pour chaque mot clé. 2- Des unités lexicales pour les opérateurs, soit individuellement, soit par classes. 3- Une unité lexicale pour les identificateurs (noms de variables, fonctions, tableaux, structures...). 4- Une ou plusieurs unités lexicales pour les nombres et les chaînes. 5- Une unité lexicale pour chacun des signes de ponctuation, tels que les parenthèses gauche et droite, la virgule , le point-virgule... 7 3- Spécification des unités lexicales 3.1- Chaînes et langages: Définitions générales: - Un alphabet Σ ou une classe de caractères définit un ensemble fini de symboles. Exemples: {0,1} : l'alphabet binaire ASCII : l'alphabet informatique - Une chaîne ou un mot sur un alphabet Σ est une séquence finie de symboles extraits de cet ensemble. 8 3- Spécification des unités lexicales - La longueur d'une chaîne s est notée: |s| La longueur de la chaîne vide notée ε : |ε| = 0 - L'ensemble des mots sur l'alphabet Σ est noté Σ ∗ - Un mot u∈Σ ∗ est facteur du mot w ∈ Σ ∗ s'il existe v, v'∈Σ ∗ tels que: w = v u v'. - Un mot fini u est périodique si u = xn pour n≥ 2. Tout mot non périodique est dit primitif. 9 3- Spécification des unités lexicales Soit une chaîne s : - préfixe de s est une chaîne obtenue en supprimant un nombre quelconque (même nul) de symboles à la fin de s. - suffixe de s est une chaîne obtenue en supprimant un nombre quelconque (même nul) de symboles au début de s. - sous-chaîne de s est une chaîne obtenue en supprimant un préfixe et un suffixe. - sous-suite de s est une chaîne obtenue en supprimant un nombre quelconque (même nul) de symboles non nécessairement consécutifs. - Un langage est un ensemble quelconque de chaînes construites sur un alphabet fixé. 10 3- Spécification des unités lexicales 3.2- Opérations sur les langages: Soit L et M deux langages: - Union de L et M : L U M = { ∀s / s ∈ L ou s ∈ M} - Concaténation de L et M : LM = { st / s ∈ L et t ∈ M} ∞ - Fermeture de Kleene de L : L* = U i=0 Li L* dénote un nombre quelconque (même nul) de concaténation de L. On note L0 = {ε} - Fermeture positive de L : L+ = ∞ U Li i=1 11 3- Spécification des unités lexicales Exemples: Soit L = {A,B,...,Z} U {a,b,...,z} et C = {0,1,...9} A partir de L et C, nous pouvons produire d'autres langages. - L U C : ensemble des lettres et chiffres, - LC : ensemble des chaînes constituées d'une lettre suivie d'un chiffre, - L4 : ensemble des chaînes constituées de 4 lettres, - C+ : ensemble des entiers naturels, - L(LUC)* : ensemble des chaînes constituées d'une lettre suivie d'une chaîne de lettres et de chiffres ou d'une chaîne vide. 12 3- Spécification des unités lexicales 3.3- Expressions régulières: Une expression régulière est une notation qui permet de décrire un ensemble (une classe) de chaînes de caractères. Exemple: Un nombre entier non signé est une chaîne constituée d'une suite de chiffres, au moins un. L'expression régulière associée est: (chiffre)+ + est un opérateur unaire post-fixe qui veut dire un ou plusieurs fois. 13 3- Spécification des unités lexicales Les règles qui définissent les expressions régulières sur un alphabet Σ sont: ε est une expression régulière qui dénote {ε} c-à-d l'ensemble dont le seul élément est la chaîne vide ε. si a est un symbole de l'alphabet Σ, alors a est une expression régulière qui dénote {a}, c-à-d l'ensemble constitué de la chaîne a. 14 3- Spécification des unités lexicales soit r et s deux expressions régulières qui dénotent les langages L(r) et L(s), alors: (r) | (s) est une expression régulière qui dénote (L(r)) U (L(s)). (r)(s) est une expression régulière qui dénote (L(r))(L(s)). (r)* est une expression régulière qui dénote (L(r))*. Les langages dénotés par les expressions régulières sont appelés langages réguliers. 15 3- Spécification des unités lexicales Exemples: a|b*c : les chaînes constituées, soit d'un a, ou d'un nombre quelconque, éventuellement nul, de la lettre b suivie de la lettre c. a | b = {a,b} (a|b)(a|b) = {aa,ab,ba,bb} Définition: Si deux expressions r et s dénotent le même langage, on dit qu'elles sont équivalentes et on écrit: r=s Exemple: (a|b)= (b|a) 16 3- Spécification des unités lexicales Propriétés algébriques sur les expressions régulières: Soit r,s et t des expressions régulières. r|s = s|r : l'opérateur| (ou) est commutatif. r|(s|t) = (r|s)|t : l'opérateur | est associatif. (rs)t = r(st) : la concaténation est associative. r(s|t)=rs|rt :la concaténation est distributive par rapport au | ε r = r ε = r : ε est l'élément neutre de la concaténation. r* =(r|ε)* : ε est inclus dans une fermeture. r** = r* : * est idempotent Remarque: la chaîne vide ε = s0 17 3- Spécification des unités lexicales Notations: * est un opérateur unaire poste-fixe qui veut dire zéro, un ou plusieurs fois. + est un opérateur unaire poste-fixe qui veut dire un ou plusieurs fois. r+ = r r* = r*r r* = r+|ε ? est un opérateur unaire poste-fixe qui veut dire zéro ou une fois. r? = r|ε [a-z] désigne un élément (une lettre) de cette classe. [a-z] = a|b|c...|z 18 3- Spécification des unités lexicales Conventions: 1- L' opérateur unaire poste-fixe * a la plus haute priorité et est associatif à gauche. 2- Les opérateurs + et ? ont la même priorité et la même associativité que *. 2- La concaténation a la deuxième priorité et est associative à gauche. 3- Le | a la plus faible priorité et est associatif à gauche. Selon ces conventions, (a)|((b)*(c)) est équivalente à a|b*c 19 3- Spécification des unités lexicales Exemples d'expressions régulières: Un identificateur: lettre(lettre|chiffre)* = [a-zA-Z][a-zA-Z0-9]* Un entier signé ou non: (+|-)? (chiffre)+ = [+-]?[0-9]+ Un nombre décimal:(+|-)? (chiffre)+ (.(chiffre)+)? Un réel: (+|-)?(chiffre)+(.(chiffre)+)?((e|E)(+|-)?(chiffre)+)? = [+-]?[0-9]+(.[0-9]+)?((e|E)(+|-)?[0-9]+)? 20 3- Spécification des unités lexicales 3.4- Définitions régulières: Une définition régulière est une suite de définitions de la forme: d1 r1 Chaque di est un nom distinct d2 r2 et chaque ri est une expression régulière sur les symboles : Σ U {d1,d2,...,di-1} dn rn Nous allons voir quelques exemples de définitions régulières : 21 3- Spécification des unités lexicales Exemples: 1- Définition régulière d'un identificateur: lettre A|B|...|Z|a|b|...|z chiffre 0|1|2...|9 id lettre(lettre|chiffre)* 2- Définition régulière des entiers signés et non signés: chiffre 0|1|2...|9 entier [+|-]?(chiffre)+ 22 3- Spécification des unités lexicales 3- Définition régulière d'un réel: L'alphabet Σ={0,1,...,9,.,e,E,+,-} Une définition régulière sera: chiffre chiffres p_entiere p_decimale p-puissance reel 0|1|2...|9 (chiffre)+ (+|-)? chiffres (.chiffres)? ((e|E)(+|-)? chiffres)? p_entiere p_decimale p_puissance 23 4- Reconnaissance des unités lexicales Soit le fragment de grammaire des instructions conditionnelles: inst si (exp) alors inst |si (exp) alors inst sinon inst |autre_inst exp terme operel terme |terme terme id |nb Les terminaux de cette grammaire sont: si, alors, sinon, (, ), operel, id et nb. Pour les reconnaître, nous allons d'abord donner les définitions régulières associées. 24 4- Reconnaissance des unités lexicales 4.1- Définitions régulières des terminaux de la grammaire: A noter qu'il faut reconnaitre les blancs aussi pour les ignorer. uploads/Management/ chapitre-2-analyse-lexicale.pdf