Analyse Lexicale
Analyse lexicale L'analyse lexicale est une étape cruciale dans le processus de compilation. Elle consiste à lire les caractères d'entrée et à générer une suite d'unités lexicales. Ce processus inclut également des tâches secondaires telles que l'élimination de caractères superflus, comme les commentaires et les espaces, ainsi que la gestion des numéros de ligne dans le programme source.
D'après le document Analyse Lexicale
Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source
Programming, Compilers · PDF · 8 pages
Afficher l'aperçu du document
Analyse lexicale
L'analyse lexicale est une étape cruciale dans le processus de compilation. Elle consiste à lire les caractères d'entrée et à générer une suite d'unités lexicales. Ce processus inclut également des tâches secondaires telles que l'élimination de caractères superflus, comme les commentaires et les espaces, ainsi que la gestion des numéros de ligne dans le programme source. Cela permet d'associer chaque erreur rencontrée à la ligne correspondante dans le code source.
Unités lexicales et lexèmes
Définitions clés
Une unité lexicale est définie comme une chaîne de caractères ayant une signification. Par exemple, un identificateur est une unité lexicale représentant le nom d'une variable ou d'une fonction.
- Les chaînes ‘≤’, ‘≥’, ‘<’, ‘>’ sont des opérateurs relationnels, représentés par l'unité lexicale oprel.
- Les chaînes nom, x, y, tab, multiplication sont des identificateurs.
- Les chaînes if, else, while sont des mots réservés.
- Les symboles , . ; ( ) sont des séparateurs.
Un modèle est une règle qui décrit l'écriture correcte d'une unité lexicale, tandis qu'un lexème est une chaîne de caractères qui concorde avec un modèle.
Exemples de modèles et lexèmes
Pour l'unité lexicale ident (identificateurs) en C, le modèle est :
Toute chaîne de caractères non vide composée de chiffres, lettres ou du symbole "_" et qui commence par une lettre est un identificateur.
Les lexèmes possibles incluent : moyenne, i, a1, factoriel.
Pour l'unité lexicale nombre (entier signé), le modèle est :
Toute chaîne de chiffres non vide précédée, éventuellement, du caractère ‘+’ ou du caractère ‘-‘ est un nombre.
Les lexèmes possibles incluent : -12, 83204, +0.
Pour l'unité lexicale réel, le modèle est :
Tout lexème correspondant à l'unité lexicale nombre suivi, éventuellement, du caractère ‘.’ et d'une chaîne de chiffres non vide, le tout suivi éventuellement du caractère ‘E’ ou ‘e’ et d'un lexème correspondant à l'unité lexicale nombre.
Les lexèmes possibles incluent : 12.4, 0.5e3, 10, -4e-1, -0.103e+2.
Un modèle peut être représenté par une expression régulière.
Expressions régulières
Notions de base
Un symbole est une concaténation d'un ou plusieurs caractères. Un alphabet est un ensemble fini non vide de symboles. Un mot est une concaténation d'éléments de l'alphabet. La longueur d'un mot w, notée |w|, est le nombre de symboles qui le composent.
Les opérations définies sur les mots incluent :
- Concaténation : w = w1w2
- Alternance : w = w1 | w2, notée aussi w = w1 + w2
- Puissance : wn = ww…w, n fois où n ≥ 0
- Fermeture de Kleene : L = ε | w | w2 | w3 | ...
Langages associés
Un langage associé à un alphabet A est tout sous-ensemble de A*. Par exemple, pour l'alphabet A = {a, b, c}, le langage L1 est l'ensemble des mots ayant autant de a que de b.
Les opérations sur les langages incluent :
- Union : L1 ∪ L2 = {w tq w ∈ L1 ou w ∈ L2}
- Intersection : L1 ∩ L2 = {w tq w ∈ L1 et w ∈ L2}
- Concaténation : L1L2 = {w tq w = w1w2 où w1 ∈ L1 et w2 ∈ L2}
- Fermeture de Kleene : L*
- Fermeture positive : L+ = L* \ {ε}
Langages réguliers
Un langage régulier (LR) est un langage vérifiant certaines propriétés, telles que :
- {ε} est un langage régulier sur A.
- Si a est une lettre de A, alors {a} est un langage régulier sur A.
- Si L est un langage régulier sur A, alors Ln et L* sont des langages réguliers sur A.
- Si L1 et L2 sont des langages réguliers sur A, alors L1 ∪ L2 et L1L2 sont des langages réguliers.
Un LR se décrit facilement par une expression régulière.
Automates finis
Définitions
Un automate fini (AF) est un graphe orienté avec des sommets représentant des états et des arcs représentant des transitions entre ces états. Un chemin partant de l'état initial et arrivant à un état final représente un mot du langage reconnu par cet automate.
Un automate fini M est défini comme un quintuple (Q, A, q0, F, δ) où :
- Q est l'ensemble des états de M.
- A est l'alphabet utilisé par M.
- q0 est l'état initial de M.
- F est l'ensemble des états finaux de M.
- δ est la fonction de transition entre les états de M.
Types d'automates
Il existe deux types d'automates finis :
- Automates finis non déterministes (AFND) : un état peut avoir plusieurs arcs portant la même étiquette.
- Automates finis déterministes (AFD) : chaque état ne peut pas avoir deux arcs portant la même étiquette.
Construction d'un automate fini
Pour construire un AFD à partir d'une ER, on peut utiliser l'algorithme de construction des sous-ensembles. Cet algorithme repose sur des définitions telles que :
- ε-fermeture(e) : ensemble des états accessibles depuis l'état e par des ε-transitions.
- Transiter(T, x) : ensemble des états vers lesquels il existe une transition sur le symbole x à partir d'un état e appartenant à T.
Algorithme de construction de Thompson
Cet algorithme permet de construire un AFND à partir d'une ER. Les règles de construction incluent :
- Pour ε, construire un AFND avec un nouvel état initial et un nouvel état final.
- Pour a, a ∈ A, construire l'AFND correspondant.
- Pour des ER combinées, utiliser les règles appropriées pour construire l'AFND.
Points clés à retenir
- L'analyse lexicale est essentielle pour la compilation.
- Les unités lexicales et les lexèmes sont fondamentaux pour comprendre le code source.
- Les expressions régulières décrivent des langages réguliers.
- Les automates finis représentent des langages à l'aide de graphes.
Glossaire
- Unité lexicale : chaîne de caractères ayant une signification.
- Lexème : chaîne de caractères concordant avec un modèle.
- Automate fini : graphe orienté représentant des états et transitions.
- Expression régulière : expression décrivant un langage.
- AFND : automate fini non déterministe.
- AFD : automate fini déterministe.
Questions fréquentes
Qu'est-ce qu'une unité lexicale ?
Une unité lexicale est une chaîne de caractères ayant une signification, utilisée dans le processus d'analyse lexicale pour identifier des éléments du code source.
Comment construire un automate fini à partir d'une expression régulière ?
Pour construire un automate fini à partir d'une expression régulière, on peut utiliser l'algorithme de construction de Thompson, qui suit des règles spécifiques pour créer un automate non déterministe.
Quelle est la différence entre un AFND et un AFD ?
Un AFND permet d'avoir plusieurs arcs portant la même étiquette sortant d'un état, tandis qu'un AFD ne le permet pas et n'a pas d'ε-transitions.
Qu'est-ce qu'une expression régulière ?
Une expression régulière est une expression qui décrit un langage en utilisant des symboles et des opérations telles que la concaténation, l'alternance et la fermeture de Kleene.
Comment fonctionne l'algorithme de construction de Thompson ?
L'algorithme de construction de Thompson construit un automate fini non déterministe à partir d'une expression régulière en suivant des règles de construction pour chaque élément de l'expression.
Commentaires
Aucun commentaire pour le moment. Posez la première question.