Analyse Lexicale

Compilation
Chebieb
2.01
Décembre 2020
 Table des matières

Objectifs 3

Introduction 4

I - Définition et rôle de l'analyse lexicale 5

1. Comment se définissent les langages de programmation ...................................................................................... 5

2. Définition de l'analyse lexicale ................................................................................................................................... 7

II - Notions de base pour l'analyse lexicale 8

1. Concepts de base pour l'analyse lexicale ................................................................................................................. 9

1.1. Rappel et définitions .............................................................................................................................................................. 9

1.2. Les langages réguliers et les expressions régulières .......................................................................................................... 10

1.3. Les automates d'états fini .................................................................................................................................................... 12

Bibliographie 15

Webographie 16
 Objectifs

Définir l'activité "analyse lexicale" dans le processus de compilation

Énoncer les concepts de bases de l'analyse lexicale
Expliquer le fonctionnement d'un analyseur lexical
Appliquer les algorithmes nécessaires pour la création des analyseurs
lexicaux
Mettre en œuvre un analyseur lexical avec un générateur automatique

3
 Introduction

Dans ce chapitre nous allons aborder la notion d’analyse lexicale et comment fabriquer un analyseur lexical :

- Le déroulement de l'analyse lexicale se base sur un automate d'état fini (AF) qui permet de reconnaître ou
rejeter les différents mots du langage source.

- La fabrication d'un analyseur lexical est une implémentation d'un automate d'état fini déterministe (AFD).
- Cet AFD est construit d'une façon automatique à partir de la spécification de la forme (motif ou pattern) des
mots du langage source sous forme d'un langage régulier.

Les principales notions abordée seront :

1. Définition et rôle de l'analyse lexicale

2. Notions de base pour l'analyse lexicale
3. Les outils pour le développement de l'analyseur lexical

4
 Définition et rôle de l'analyse lexicale

I Définition et rôle de
l'analyse lexicale

1. Comment se définissent les langages de programmation

C'est quoi un programme ?

Un texte regroupant une suite d'instructions avec des données combinées pour commander un processeur (une
machine physique ou virtuelle dite aussi automate)

C'est quoi un langage de programmation?

Le programme possède une structure obéissant à des règles

Les règles fixent l'ensemble des signes et symboles à utiliser et la manière avec laquelle les utiliser

Ces règles définissent un langage de programmation

La description des langages de programmation

Les langages de programmations possèdent une description sur trois niveaux :

1. Le lexique : un ensemble de mots et de symboles à utiliser dite unités lexicales

2. La syntaxe : un ensemble de règles de combinaison des mots et des symboles pour former les commandes ou
les instructions
3. La sémantique : les actions opérationnelles lancées par le processeur suite aux combinaisons former par
l'auteur du programme

 Exemple : Description standardisée du langage MS C#

C# est décrit par une spécification ECMA. Ci après quelques pages du sommaire de la spécification qui concerne le
niveau lexical et syntaxique ainsi que sémantique

5
Comment se définissent les langages de programmation

6
 Définition de l'analyse lexicale

 Fondamental : Langage et compilateur

A chaque langage ainsi défi sont associée un ou plusieurs compilateur pour pouvoir traduire les programmes vers
des instructions du processeurs (machine) qui doit les exécuter

2. Définition de l'analyse lexicale

L'analyse lexicale est l'étape frontale de la chaîne de compilation. Elle consiste à vérifier le flux représentant le code
source pour :

- Identifier les mots du langage utilisés dans le code source et les codifier dans un flux de sortie. Ces mots sont
les UNITÉS LEXICALES (TOKENS) du code source.
- Éliminer les mots inutiles ou superflus qui ne sont pas destinés à être traduit dans le langage cible de la
compilation : les blancs, les tabulations, les sauts de ligne et les commentaires .....
- Signaler les mots qui ne font pas partie du langage : erreurs lexicales

Analyse lexicale

7
Notions de base pour l'analyse lexicale

II Notions de base pour

l'analyse lexicale

8
 Rappel et définitions

1. Concepts de base pour l'analyse lexicale

1.1. Rappel et définitions

 Rappel : L'alphabet

Ensemble de symboles utilisés pour former des combinaisons servant dans une notation donnée dans un domaine
donné. Formellement un alphabet est un ensemble fini non-vide de lettres ou symboles. Il est généralement noté Σ.

Par exemple Σ = {0, 1} représente un alphabet pour une notation représentant les nombres binaires !

 Rappel : Le mot

Nommé aussi "chaîne". C'est une succession de symboles formée en combinant les symboles d'un alphabet. Le mot
est généralement noté ω. Le nombre de symboles formant un mot ω est la longueur de ce mot notée |ω|.

Si cette longueur est nul on parle alors du mot vide noté "ε" qui ne contient aucun symbole |ε| = 0

 Méthode : La concaténation

C'est une loi de composition interne sur un alphabet représentant l'opération qui crée un mot sur l'alphabet formé des
caractères du premier mot suivis de ceux du second. Elle est noté .

La longueur du mot formé par concaténation est la somme des longueurs des de mots concaténés.

 Exemple

Soit un alphabet Σ = {a, b, c} et soit deux mots sur cette alphabet tq ω1=a et ω2 = b.

La concaténation de ω1 et ω2 sera le mot ω3 formé sur l'alphabet Σ tq

 Fondamental

Si ω est un mot sur l'alphabet Σ alors :

ε.ω=ω.ε=ω

ωn signifie la concaténation n fois le mot ω. Si n=2 alors ω2 = ω.ω et si n= 0 alors ω0 = ε

Σ* est le monoïde libre en/sur Σ : tout les mots construits sur l'alphabet Σ par concaténation

 Exemple

Soit un alphabet le monoïde libre sur est

 Définition : Le langage

On désigne par "langage" un ensemble de mots formés sur un alphabet donnée.

9
Les langages réguliers et les expressions régulières

Formellement un langage noté L sur un alphabet Σ est un sous ensemble de Σ * :

Un langage peut être infini ( ), fini ( ) ou vide ( ).

 Méthode : Les opérations sur les langages

Soit deux langages L1 et L2 sur un alphabet donné Σ. L1 est L2 sont des sous ensembles de Σ* alors les opérations

suivantes sont possibles sur ces langages :

- La concaténation :

- Union :

- Intersection:

- Itération: ou fermeture d'un langage :

- Itération positive ou fermeture positive d'un langage :

Cette itération est appelée aussi la fermeture ou l'étoile de Kleene du nom de celui qui l'a introduit *

 Définition : Le lexique et le lexème

Le lexique d'un langage est la manière de former les mots sur un alphabet donné.

Le lexème est la succession de caractères appartenant à une chaîne donnée qui peut former un mot d'un langage.

 Exemple

Soit le langage L défini sur l'alphabet Σ tel que :

- Le lexique de ce langage est cette forme qui signifie plus de "a" que de "0" dans les mots de L
- La chaîne n'est pas un mot du langage L mais il contient un lexème

1.2. Les langages réguliers et les expressions régulières

 Rappel : Langages réguliers ou rationnels

Un langage régulier sur un alphabet est un sous ensemble d'un monoïde sur un alphabet, qui peut-être construit avec
les opérations : union, itération et concaténation.

 Rappel : Propriétés des langages réguliers

Un langage régulier L sur un alphabet Σ est défini récursivement :

- sont des langages réguliers ;

- est un langage régulier ;
- Si deux langages sont réguliers sur alors :
sont aussi des langages réguliers sur ;

– Il n'y a pas d'autre langages réguliers sur Σ

10
 Les automates d'états fini

 Rappel : Langage régulier et grammaires

Dans la classification de Chomsky, ces langages sont engendrée par des grammaires régulières droites ou une
grammaires régulières gauches (il sont de type 3)

 Fondamental : Expression régulière et lexique d'un langage

Une expression régulière est une façon concise de décrire le lexique d'un langage régulier. C'est à dire la forme
générale des mots d'un langage régulière. Elles ont été définies par Kleene*récursivement sur l'alphabet du langage
qu'elles décrivent :

Soit un alphabet Σ et un langage L, une expression régulière (R) qui décrit L est R(L) :

- est l'expression qui décrit le langage vide ;

- l'expression qui décrit le langage
- est une expression qui décrit le langage
- Pour deux expressions régulières décrivant deux langages :

-
-
- (fermeture de Kleene).

 Exemple

Soit l'alphabet . Les expressions suivantes peuvent être formées :

 Attention : Priorités des opérations sur les expressions régulières

La priorité des opérations lors de la construction des expressions régulières est dans l'ordre décroissant suivant:

- l'itération ,
- la concaténation
- l'union .

Les ( ) peuvent être donc utilisée pour les sous expressions comme

 Rappel : Théorème de Kleene

Les langages réguliers sur un alphabet (décrit par des expressions régulières) sont reconnaissables par automates
d'états finis (voir les détails dans :Kleen*Eilenberg*). En d'autres termes

- Soit un alphabet et un ensemble de langages réguliers R(L) (décrits en expressions régulières).

- Soit AF(L) ensemble de langages reconnues par des Automates d'états finis (AF).

11
Les automates d'états fini

1.3. Les automates d'états fini

 Définition : Automate d'état fini (formalisme de Moore) (AF)

Un automate d'état fini (théorème de Moore) est une structure :

: un alphabet

: ensemble fini d'états

:la fonction de transition

l'état initial de l'automate

: ensemble des états finaux

 Fondamental : Reconnaissance d'un langage

Un langage L sur un alphabet Σ reconnu par un automate AF est l'ensemble .

Cette ensemble est noté L(AF).

Un AF représente un machine à états ayant une tête de lecture qui

avance sur un flux d'entrée caractère par caractères

Automate d'États Finis

 Définition : Automate d'états finis déterministe (AFD)

C'est un automate déterministe est caractérisé par :

- L'absence de transition vide dite \varepsilon-\text{transition}

- Il ne peut exister qu'une transition au plus à partir d'un état e avec un symbole s

12
 Les automates d'états fini

Représentation graphique de

 Définition : Automate d'états finis non déterministe (AFND ou AFN))

C'est un automate non déterministe est reconnu par :

- Présence de transition vide dite

- Présence possible de plus d'une transition d'un état e avec un symbole s

La représentation graphique de :

Exemple AFN

 Méthode : Définition et Implémentation d'un AFD

Les automates déterministes "AFD" sont :

- Non intuitifs à définir mais relativement simple à implémenter par programme. On aura besoin :

- Table de transition TransTable : structure de donnée représentant l'AFN précisément

l'ensemble des états possibles de :

- Une fonction de transition : utilise la TransTable pour déterminer le prochain état

à atteindre avec l'entrée c
- Une fonction de lecture du flux qui retourne le caractère lu sur le flux d'entrée
- Si la retrouve l'état final alors le flux est reconnu par l'automate
"ACCEPTATION"
- Si elle ne retourne aucun état dans la table alors le flux est rejeté et la chaîne est non reconnue

 Méthode : Définition et Implémentation d'un AFN

Les automates non déterministes "AFN" sont :

13
Les automates d'états fini

- Plus intuitifs à définir mais pas simple à implémenter par programme. On aura besoin :

- D'une Table de transition TransTable : structure de donnée représentant l'AFN

précisément l'ensemble des états possibles de :
- D'une méthode de transformation en AFD pour pouvoir les implémenter

14
 Bibliographie

Bibliographie

Janusz A. Brzozowski Canonical regular expressions and minimal state graphs for definite events
Proceedings of the Symposium on Mathematical Theory of Automata, Polytechnic Institute of Brooklyn, New
York, Wiley April 1962-1963

Samuel Eilenberg Automata, Languages and Machines Vol. A, Academic Press 1974

Victor M. Glushkov The abstract theory of automata Russian Mathematical Surveys, vol. 16 1961

John Hopcroft An n log n algorithm for minimizing states in a finite automaton Proc. Internat. Sympos.,
Technion, Haifa, New York, Academic Press 1971

Edward F. Moore Gedanken-experiments on sequential machines in Automata studies Princeton, N. J.

Princeton University Press coll. Annals of mathematics studies 1956

Stephen Cole Kleene Representation of events in nerve nets and finite automata C.E. Shannon and J.
McCarthy, Automata Studies, vol. 34, Princeton, N. J., Princeton University Press, coll. « Annals of
Mathematics Studies 1956

15
Webographie

Webographie

[Link]/software/flex

JavaCC

[Link]/~appel/modern/java/JLex

[Link]

[Link]

[Link]

16