Remerciez-le!

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

Université Mohammed V - Agdal Faculté des sciences Département d'Informatique C

Université Mohammed V - Agdal Faculté des sciences Département d'Informatique Cours de Compilation Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 Cours de Compilation SMI - S5 Prof. M.D. RAHMANI mrahmani@fsr.ac.ma 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.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 Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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 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 Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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: 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. Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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 d'entrée lexicale prochaine syntaxique unité lexicale traitement des erreurs Interaction entre analyseur lexical et analyseur syntaxique. Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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. Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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. 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... Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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 ASCII : l'alphabet informatique - Une chaîne ou un mot sur un alphabet Σ Σ Σ Σ est une séquence finie de symboles extraits de cet ensemble. Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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'∈Σ ∗ - 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. Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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 - 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é. Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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} - Concaténation de L et M : LM = { st / s ∈L et t ∈M} - Fermeture de Kleene de L : L* = Li L* dénote un nombre quelconque (même nul) de concaténation de L. On note L0 = {ε ε ε ε} - Fermeture positive de L : L+ = Li Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 11 U ∞ =0 i U ∞ =1 i 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, - 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. Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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. 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. Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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 ε ε ε ε. 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. Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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. Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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} (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) Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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. 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 Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 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. 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 Prof. M.D. RAHMANI Compilation SMI- S5 2013/14 18 3- Spécification des unités lexicales Conventions: uploads/Management/ compilation-3-pdf.pdf