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é A.Mira, Bejaia Faculté des Sciences Exactes Département d'Informatiq

Université A.Mira, Bejaia Faculté des Sciences Exactes Département d'Informatique Cours de Compilation Mme D.Boulahrouz boukredera@hotmail.com 1. Le rôle d'un analyseur lexical 2. Principe d'un analyseur lexical 3. Terminologie 4. Rappels sur les langages et expressions régulières 5. Spécification des unités lexicales 6. Reconnaissance des unités lexicales 7. Réalisation d’un analyseur lexical. Chapitre 02 Analyse Lexicale D.Boulahrouz Analyse Lexicale 2015/16 Chapitre 02 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. Il découpe et regroupe les caractères d’entrée en mots ou lexèmes. Analyseur Lexical 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. D.Boulahrouz Analyse Lexicale 2015/16 1. Le rôle d'un Analyseur Lexical L’interaction entre analyseur lexical et analyseur syntaxique peut être schématisée comme suit: unité lexicale et attributs prochaine unité lexicale texte d'entrée Analyse lexicale Analyse syntaxique reste traitement des erreurs table des symboles D.Boulahrouz Analyse Lexicale 2015/16 2. Principe d’un Analyseur Lexical D.Boulahrouz Analyse Lexicale 2015/16 L’analyseur lexical consiste à partir d'un programme qui est une suite de caractères séparés par des blancs à : • Spécifier les différentes entités lexicales (les mots) du langage, parmi ces entités, on reconnaît :  Les identificateurs.  Les mots clés (Les mots réservés).  Les constantes.  Les séparateurs. • Éliminer les blancs, ainsi que les commentaires. • Codifier les différentes entités lexicales. • Construire la table des symboles. • Gérer les erreurs Lexicales 3. Terminologie D.Boulahrouz Analyse Lexicale 2015/16 - Unité lexicale (token): Une unité lexicale est une suite de caractères qui a une signification collective : identificateur, entier, opérateur etc. c’est un symbole terminal de la grammaire du langage. - Modèle: est une règle associée à une unité lexicale qui décrit l’ensemble des chaînes qui peuvent correspondre à cette unité lexicale: expression régulière - lexème: est une suite de caractères du texte d'entrée qui concorde avec le modèle d’une unité lexicale. Exemple: 35 est un lexème (un mot) qui appartient à l'unité lexicale (la classe) nombre. 3. Terminologie D.Boulahrouz Analyse Lexicale 2015/16 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... Remarques: 3. Terminologie D.Boulahrouz Analyse Lexicale 2015/16 position := 50 + vitesse*temps Exemple1 Les 7 lexèmes constitués sont : «position» «:=» «50» «+» «vitesse» «*» « temps» Les 03 Unités lexicales correspondantes sont: nb, id et op - «positions», «vitesse» et «temps» sont des lexèmes de l’unité lexicale id - «*», «+» et «:=» sont des lexèmes de l ’unité lexicale op - « 50 » est un lexème de l ’unité lexicale nb 3. Terminologie D.Boulahrouz Analyse Lexicale 2015/16 Lorsque le scanner reconnaît une unité lexicale, il la transmet au parser avec plusieurs informations (attributs) qui s ’y rattachent Exemple : position := 50 + vitesse*temps Le scanner transmet au parser : (id, «position») (op, affectation) (nb, 50) (op, add) (id, «vitesse») (op, mult) (id, «temps») Attributs des unités lexicales 3. Terminologie D.Boulahrouz Analyse Lexicale 2015/16 Soit la portion du programme Pascal suivante: Begin i:= i+j; If (i=j) then i:=0; End. Exemple2 Déterminer les Tokens (Unités lexicales) et les lexèmes correspondants 3. Terminologie D.Boulahrouz Analyse Lexicale 2015/16 Soit la portion du programme Pascal suivante: Begin i:= i+j; If (i=j) then i:=0; End. Exemple2 Tokens Lexèmes Mot clé Begin, if, then, end Identificateur i, j Opérateur arithmétique + Séparateur ; . Parenthèses ( ) Affectation := Nombre 0 Opérateur Comparaison = 4. Rappels sur les Langages & Expressions Régulières 4.1 Chaînes et langages - Alphabet : ensemble fini de symboles appelé caractères Exemple: {0,1}  l'alphabet binaire - Mot ou une chaine (sur un alphabet) : suite finie de caractères. - Le mot vide sera note E; - l’opération de concaténation de deux mots m1 et m2 est notée par simple juxtaposition m1 m2 . - La longueur d'une chaîne s est notée: |s| - La longueur de la chaîne vide notée  est - L'ensemble des mots sur l'alphabet Définitions générales: D.Boulahrouz Analyse Lexicale 2015/16 Soit une chaîne s : - préfixe de s : chaîne obtenue en supprimant un nombre quelconque (même nul) de symboles à la fin de s. - suffixe de s: chaîne obtenue en supprimant un nombre quelconque (même nul) de symboles au début de s. - sous-chaîne de s: chaîne obtenue en supprimant un préfixe et un suffixe. - Un langage est un ensemble quelconque de chaînes construites sur un alphabet fixé. - Reconnaissance : étant donné un mot m et un langage L, est-ce que m ∈ L ? Définitions générales: D.Boulahrouz Analyse Lexicale 2015/16 4.1 Chaînes et langages 4.2 Opérations sur les langages: D.Boulahrouz Analyse Lexicale 2015/16 D.Boulahrouz Analyse Lexicale 2015/16 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: Exemples: - 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. 4.2 Opérations sur les langages: 4.3 Expressions régulières D.Boulahrouz Analyse Lexicale 2015/16 Une expression régulière est une notation qui permet de décrire un ensemble (une classe) de chaînes de caractères. Expressions réguliè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. * 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 zéro ou une fois. 4.3 Expressions régulières D.Boulahrouz Analyse Lexicale 2015/16 Expressions régulières 4.3 Expressions régulières D.Boulahrouz Analyse Lexicale 2015/16 Expressions régulières Les langages dénotés par les expressions régulières sont appelés langages réguliers. D.Boulahrouz Analyse Lexicale 2015/16 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} Exemples: 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) 4.3 Expressions régulières D.Boulahrouz Analyse Lexicale 2015/16 Exemples d'expressions régulières: 4.3 Expressions régulières Expressions régulières D.Boulahrouz Analyse Lexicale 2015/16 Définitions régulières D.Boulahrouz Analyse Lexicale 2015/16 Exemples de définitions régulières:: 4.3 Expressions régulières Opérations sur les langages: D.Boulahrouz Analyse Lexicale 2015/16 Exemples de définitions régulières:: uploads/Management/ moncoursanalyselexicale-partie1.pdf