Principes et Techniques des
Compilateurs
Année Universitaire 2013 / 2014
Plan
⚫ Généralités
⚫ Unité lexicale, Lexème et Modèles
⚫ Définition régulière
⚫ Diagramme de transition
2
Rôle de l’analyseur lexical
⚫ Lire les caractères du texte d'entrée.
⚫ Supprimer les blancs, les commentaires, etc.
⚫ Former des unités lexicales .
⚫ Passer des couples <unité lexicale, valeur lexicale> à l'Analyseur Syntaxique.
⚫ Relier les messages d’erreurs issus du compilateur au code source.
Schéma usuel d’implémentation de l’analyseur lexical –
interaction avec l’analyseur syntaxique
TOKEN COURANT
Programme
Analyseur Analyseur
source
lexical Syntaxique
TOKEN PROCHAIN
Table de symboles
3
Unités lexicales, lexèmes et modèles
A propos d’une unité lexicale reconnue dans le texte source on doit distinguer trois notions
importantes :
⚫ L’unité lexicale.
⚫ le lexème.
⚫ le modèle.
4
Unités lexicales, lexèmes et modèles
Unité lexicale
Pour la plupart des langages de programmation, les constructions suivantes sont traitées
comme des unités lexicales :
⚫ Mots clés.
⚫ Opérateurs arithmétiques
⚫ Opérateurs logiques
⚫ Identificateurs.
⚫ Séparateurs ( ‘(’, ‘)’, ‘,’, ‘:’, etc.)
5
Unités lexicales, lexèmes et modèles
Lexème
Un lexème est une suite de caractères du programme source qui concordent avec le modèle de
l’unité lexicale. Exemple :
const max_length = 256;
Dans la déclaration précédente, la chaîne de caractères max_length est un lexème de l’unité
lexicale Identifier.
6
Unités lexicales, lexèmes et modèles
Modèle
le modèle sert à spécifier l’unité lexicale.
⚫ Pour les mots réservés tels que const, if, while, etc. le lexème et le modèle
coïncident généralement. Le modèle de l’unité lexicale const est la chaîne const.
⚫ Pour une unité lexicale rel_oper qui représente les opérateurs relationnels, le modèle
est l’ensemble des opérateurs relationnels : <, < =, ==, >=, >, !=
⚫ Pour décrire précisément les modèles des unités lexicales plus complexes tels que les
identificateurs et les nombres, on utilise les expressions régulières .
⚫ Des langages et outils permettent d’engendrer une reconnaissance efficace par automates
finis des expressions régulières.
7
Unités lexicales, lexèmes et modèles
Unité lexicale Lexèmes Description informelle des modèles
const const const
if if if
rel_oper < , <= , == , != , >= , > < | <= | == | != | >= | >
identifier e pi length Lettre suivie de lettres ou de chiffres ou le caractère ‘_’
8
Les définitions régulières
Les définitions régulières permettent de donner des noms à des ER définies sur un alphabet à
partir de symboles de base et de les utiliser comme s’ils étaient des symboles de .
⚫ d1 → r1
⚫ d2 → r2
⚫ …
⚫ dn → rn
di est un nom distinct et chaque ri est une ER sur les symboles de ∪{d1, d2, …, di-1}.
9
Rappel : Les expressions régulières
Exemple
letter → A | B | … | Z | a | b | … | z
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
identifier → letter (letter | digit)*
number → digit+
10
Diagrammes de transitions
⚫ Les diagrammes de transitions décrivent les actions qui sont réalisées quand l’analyseur
syntaxique appelle un analyseur lexical pour fournir la prochaine unité lexicale.
⚫ Un état initial du diagramme.
⚫ En entrant dans un état on lit le prochain caractère. Si l’étiquette d’un arc sortant de l’état
courant concorde avec le caractère d’entrée on passe à l’état pointé par cet arc. Autrement
on signale une erreur.
11
Diagrammes de transitions
Exemples begin < = return (relop, LE)
0 1 2
>
3 return (relop, DIFF)
other
= 4 * return (relop, LT)
> 5 return (relop,EQ)
6 = 7 return (relop, GE)
other *
8 return (relop, GT)
Diagramme de transition pour les opérateurs de relation
État d’acceptation
Letter | digit
begin letter other *
9 10 11
Diagramme de transition pour les identificateurs
12
Réalisation de Diagrammes de transitions
begin < =
0 1 2
>
3
other
= 4 *
> 5
6 =
7
other
Letter | digit 8 *
letter other *
9 10
digit digit
digit . digit other *
19 20 21 22
digit
digit other *
23 24
13
