Fichier PDF

Partagez, hébergez et archivez facilement vos documents au format PDF

Partager un fichier Mes fichiers Boite à outils PDF Recherche Aide Contact



TCompilo .pdf



Nom original: TCompilo.pdf

Ce document au format PDF 1.2 a été généré par TeX output 2013.02.05:0802 / dvipdfm 0.13.2c, Copyright © 1998, by Mark A. Wicks, et a été envoyé sur fichier-pdf.fr le 14/02/2013 à 22:16, depuis l'adresse IP 197.7.x.x. La présente page de téléchargement du fichier a été vue 2294 fois.
Taille du document: 227 Ko (32 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Introduction

Analyse lexicale

Th´eorie de compilation
M. T. Bennani
Maˆıtre Assistant, FS Tunis, LISI

-Ann´ee universitaire 2012-2013M. T. Bennani Maˆıtre Assistant, FS Tunis, LISI
Cours sur la th´
eorie des langages

Introduction

Analyse lexicale

Objectifs

I

Comprendre le fonctionnement des langages de
programmation

I

Apprendre comment construire des langages de
programmation

I

Apprendre les bases de la conception des langages

I

R´ealiser des logiciels ambitieux

I

Voir l’utilisation des connaissances introduites dans la th´eorie
des langages

2 / 41

Introduction

Analyse lexicale

Objectifs

Comment fonctionne un compilateur ?

3 / 41

Introduction

Analyse lexicale

´
Etapes

De la description `a l’impl´ementation
I

Analyse lexicale (scanning) : Identifier les pi`eces logiques
d’une description

I

Analyse syntaxique (Parsing) : Identifier comment ces pi`eces
sont li´ees entre elles

I

Analyse semantique : Identifier le sens de la structure enti`ere

I

G´en´eration d’une repr´esentation interm´ediaire : Concevoir une
structure possible

I

Optimisation de la repr´esentation interm´ediaire : Simplication
de la strcuture retenue

I

G´en´eration : Fabrique la structure

I

Optimisation : Am´eliorer la structure r´esultante
4 / 41

Introduction

Analyse lexicale

´
Etapes

1. Scannning
R´esultat
Fichier source
while ( y < z ) {
int x = a + b ;
y += x ;

1

3

}

T
T
T
T
T
T
T
T
T

While
ParenGche
Identifiant y
Inferieur
Identifiant z
ParenDrte
AccoladOuvr
Int
Identifiant x

T
T
T
T
T
T
T
T
T
T

Assignation
Identifiant
Plus
Identifiant
PtVirg
Identifiant
PlusAssign
Identifiant
PtVirg
AccoladFerm

a
b
y
x

6 / 41

Introduction

Analyse lexicale

´
Etapes

2. Analyse syntaxique
Entr´ee
L’ensemble des Tokens identifi´es lors de la phase d’analyse lexicale

R´esultat

Arbre syntaxique
7 / 41

Introduction

Analyse lexicale

´
Etapes

3. Analyse semantique
Entr´ee
Arbre syntaxique ´elabor´e lors de la phase d’analyse syntaxique

R´esultat

Arbre syntaxique d´ecor´e
8 / 41

Introduction

Analyse lexicale

´
Etapes

4. G´en´eration d’une repr´esentation interm´ediaire
Entr´ee
Arbre syntaxique d´ecor´e ´elabor´e lors de la phase d’analyse
semantique

R´esultat
Une repr´esentation interm´ediaire
2

4

Loop : x
y

= a + b
= x + y
t1 = y < z
i f t 1 goto Loop

10 / 41

Introduction

Analyse lexicale

´
Etapes

5. Optimisation de la repr´esentation interm´ediaire
Entr´ee
Une repr´esentation interm´ediaire d´efinie lors de la phase de
g´en´eration

R´esultat
Une repr´esentation interm´ediaire optimis´ee
2

4

x
Loop : y

= a + b
= x + y
t1 = y < z
i f t 1 goto Loop

12 / 41

Introduction

Analyse lexicale

´
Etapes

6. G´en´eration de code
Entr´ee
Une repr´esentation interm´ediaire optimis´ee

R´esultat
Un code machine
2

4

add
Loop : add
slt
beq

$1 ,
$4 ,
$6 ,
$6 ,

$2 , $3
$1 , $4
$1 , $5
Loop

14 / 41

Introduction

Analyse lexicale

´
Etapes

7. Optimisation du code

Entr´ee
Un code machine d´efinit lors de la phase g´en´eration de code

R´esultat
Un code machine optimis´e
2

add
Loop : add
blt

$1 , $2 , $3
$4 , $1 , $4
$1 , $5 , Loop

16 / 41

Introduction

Analyse lexicale

Bibliographie

Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey-D Ullman,
”Compilateurs - Principes, techniques et outils”. 2`eme ´edition,
Pearson, 2007.

17 / 41

Introduction

Analyse lexicale

Introduction

Objectif
D´efinition 1
L’analyse lexicale (scanning) identifie les pi`eces logiques d’une
description. Elle prend en entr´ee le fichier source et g´en`ere les
tokens qui le forment.

Exemple
1

while ( i p < z )
++i p ;

while
I
I

(ip

<

z ) \n \t + + i p ;

le mot ”while” lu `a partir du fichier source repr´esente un
lex`eme
Apr`es la lecture, l’analyseur lexical retourne le Token
”T While”
19 / 41

Introduction

Analyse lexicale

Introduction

D´efinition 2
Un Token repr´esente une entit´e logique lue `a partir du code source.
Nous pouvons le rep´erer avec un type ´enum´er´e.

D´efinition 3
Un lex`eme est une partie du programme original `a partir duquel
nous construisons un Token.

w h i l e

( 1 2

<

z ) \n \t + + z ;

Remarques
I

Parfois, nous supprimons des lex`emes au lieu de les
sauvegarder pour une utilisation ult´erieure. Par exemple, nous
ignorons l’espace puisqu’il n’a aucune unfluenece sur le sens
du programme.
20 / 41

Introduction

Analyse lexicale

Introduction

Remarques (suite)
I

Le lex`eme ”12” est une valeur num´erique et non pas un
Token.

I

Dans ce cas le Token ”T IntConst” contient un attribut
permettant de sauvegarder la valeur 12.

D´efinition 4
Certains Tokens peuvent avoir des attributs qui permettent de
sauvegarder des informations suppl´ementaire au sujet du Token lui
mˆeme.

21 / 41

Introduction

Analyse lexicale

Introduction

Exemple
while

(ip

<

z ) \n \t + + i p ;

Suite `a la phase d’analyse lexicale de cette entr´ee nous aurons le
r´esultat suivant :
T Wile T ParOuv T Ident {ip}
T Inf T Ident {z} T ParFerm
T Plusplus T Ident {ip} T PtVig

22 / 41

Introduction

Analyse lexicale

Introduction

Objectifs g´en´eraux de l’analyse lexicale
I

Convertir la description physique du programme en une
s´equence de Tokens. Chaque Token repr´esente une partie
logique du code source. Par exemple, keyword, nom d’une
variable, etc.

I

Chaque Token est associ´e `a un lex`eme. Le texte actuel du
Token : ”12”, ”int”, etc.

I

Chaque Token peut avoir des attributs optionnels. C’est une
information suppl´ementaire obtenu du texte. Elle peut ˆetre
une valeur num´erique.

I

La s´equence de Tokens sera utilis´ee par le parser pour couvrir
la structure du programme.

23 / 41

Introduction

Analyse lexicale

Associer les lex`
emes aux tokens

Choix des Tokens
I

Le choix des Tokens d´epend du langage

Dans le cas g´en´eral, les Tokens peuvent ˆetre :
I

Les mots cl´es d’un langage

I

Les symboles de ponctuation

I

Les Groupes de lex`emes qui repr´esentent : identificateurs,
constantes num´eriques, chaˆınes de caract`eres, etc.

I

Les espaces blancs et les commentaires, qu’il faut supprimer.

24 / 41

Introduction

Analyse lexicale

Associer les lex`
emes aux tokens

Choix des Tokens (Suite)
Exemple
f o r ( i n t k =0; k < myArray [ 5 ] ; k++){
c o u t << k << e n d l ;
}

2

Les Tokens `a choisir
T
T
T
T

FOR T AccOuv T INT T AccFerm T OutStream
PtVirg T Assign T Inf T ParOuv T CroOuv
ParFerm T CroFerm T PlusPlus T Identifiant
IntConst

26 / 41

Introduction

Analyse lexicale

Associer les lex`
emes aux tokens

Difficult´es du scanning
I

I

La difficult´e principale est de savoir o`
u est-ce que nous devons
partitionner l’entr´ee
Si les mots cl´es sont utilis´es comme des identificateurs

Exemple1 : D´eclaration d’un template en C++
1

v e c t o r <v e c t o r <i n t >> monVecteur
(vector < (vector < (int >> monVecteur )))

Exemple2 : Utilisation des mots cl´es
1

I F THEN THEN THEN = ELSE ; ELSE ELSE = I F
IF THEN THEN THEN = ELSE ; ELSE ELSE = IF
28 / 41

Introduction

Analyse lexicale

Associer les lex`
emes aux tokens

L’association Lex`emes / Tokens
I

I

I

Les Tokens permettent de cat´egorier les lex`emes selon
l’information qu’ils donnent
Certains Tokens peuvent ˆetre associ´es `a un seul lex`eme. Par
exemple, if, while, etc.
Certains Tokens peuvent ˆetre associ´es `a plusieurs lex`emes
diff´erents. Par exemple, nom des variables, les nombres, les
chaˆınes de caract`emes, etc.

Remarque
L’association d’un ensemble de lex`emes `a un Token peut ˆetre :
I

”T Nombre” pour l’ensemble {0,1,2, ..., 19, 20, ...}

I

”T Chaine” pour l’ensemble {””, ”a”, ”b”, ...}
29 / 41

Introduction

Analyse lexicale

Associer les lex`
emes aux tokens

Description formelle
Faits
I

Un langage formel est un ensemble de chaˆınes de caract`eres.

I

Plusieurs langages infinis ont une description fini. Par
exemple: Automates finis, grammaires, expressions r´eguli`eres

Solutions
I

On peut utiliser une description compacte du langage pour
d´efinir un ensemble de chaˆınes de caract`eres

I

Les expressions r´eguli`eres une famille de description pouvant
capturer les langages r´eguliers

I

Ils offrent une description compacte et lisible des langages.
30 / 41

Introduction

Analyse lexicale

Associer les lex`
emes aux tokens

Description formelle (Suite)
I

I
I
I

Si R1 et R2 sont des expressions r´eguili`eres, R1 R2 est une
expression r´eguli`ere qui repr´esentent la concat´enation des
langages R1 et R2 .
Si R1 et R2 sont des expressions r´eguili`eres, R1 |R2 est une
expression r´eguli`ere qui repr´esentent l’union de R1 et R2 .
Si R est une expression r´eguli`ere, R ∗ est une expression
r´eguli`ere repr´esentant la fermeture de Kleene de R.
Si R est une expression r´eguli`ere, (R) est une expression
r´eguli`ere qui a le mˆeme sens que R.

Priorit´e
L’ordre de priorit´e des op´erateurs sont : (), *, sequence et union
I

ab ∗ c|d est pars´ee dans l’ordre suivant : ((a(b ∗ ))c)|d
31 / 41

Introduction

Analyse lexicale

Associer les lex`
emes aux tokens

Description formelle (Suite)

Expressions r´eguli`eres simples
I

Une chaˆıne de caract`eres contenant 00 comme sous chaˆıne :
(0|1)∗ 00(0|1)∗

I

Traiter les chaˆınes suivantes : 11011100101, 0000,
11111011110011111

I

Des chaines de longueur 4 : (0|1){4} ou (0|1)(0|1)(0|1)(0|1)

I

Traiter les chaines suivantes : 0000, 1010, 1111, 1000

32 / 41

Introduction

Analyse lexicale

Associer les lex`
emes aux tokens

Description formelle (Suite)
Expressions r´eguli`eres appliqu´ees
I

Soit l’alphabet contenant, a, @ et . o`
u a repr´esente une lettre
quelconque. L’expression r´eguli`ere exprimant une adresse
e-mail : a+ (.aa∗ )∗ @ aa∗.aa∗ (.aa∗ )∗

I

Traiter la s´equence suivante : cs12@dgi.fst.rnu.tn

I

Soit l’expression des nombre paires : (+|−)?
(0|1|2|3|4|5|6|7|8|9)∗ (0|2|4|6|8), (+|−)?[0 − 9]∗ [02468]

I

Traiter la s´equence suivante : 42, +1344

33 / 41

Introduction

Analyse lexicale

Associer les lex`
emes aux tokens

Implementation des expressions r´eguli`eres
I
I

Les expressions r´eguli`eres peuvent ˆetre impl´ement´ees `a l’aide
d’automates finis
Il existe deux types d’automates finis : non d´eterministes et
d´eterministes

Remarques
I

Revenir sur le cours th´eorie des langages pour reprendre les
op´erations sur les automates finis.

I

Une expression r´eguli`ere de longueur n peut ˆetre convertie en
un AFND avec O(n) ´etats

I

Nous pouvons savoir si une chaine de longueur m correspond
`a une expression r´eguli`ere de longueur n en un temps
´equivalent `a O(mn2 )
34 / 41

Introduction

Analyse lexicale

Ambig¨
uit´
e de l’analyse lexicale

D´efis `a relever
I

Comment determiner quels lex`emes sont associ´es `a chaque
Token ?

I

S’il y a plusieurs chemins pour analyser une entr´ee, comment
savoir lequel choisir ?

I

Comment r´epondre `a ces probl`emes d’une mani`ere efficace ?

Exemple
I

Le Token T For est associ´e au singleton for

I

Le Token T Identifiant est associ´e `a l’ensemble de chaines
d´efinis par : [A − Za − z ][A − Za − z0 − 9 ]∗

I

Soit l’entr´ee ”fort”. Quels sont les Tokens reconnus ?
35 / 41

Introduction

Analyse lexicale

Ambig¨
uit´
e de l’analyse lexicale

Exemple (Suite)
Nous pouvons avoir plusieurs r´esultats possibles :
1. T Ident = fort 2. T For = for et T Ident = t
3. T Ident = for et T Ident = t 4. T Ident = fo et T Ident = rt
5. T Ident = fo et T Ident = rt et T Ident = t 6. T Ident = f et
T Ident = ort
7. T Ident = f et T Ident = or et T Ident = t 8. T Ident = f et
T Ident = o et T Ident = rt
9. T Ident = f et T Ident = o et T Ident = r et T Ident = t

R´esolution du premier conflit
Dans le cas o`
u les Tokens sont sp´ecifi´es `a l’aide d’expressions
r´eguli`eres et pour un algorithme de type analyse Gauche-Droite,
nous choisirons le prefixe le plus long possible du texte restant
”Maximal munch”.
36 / 41

Introduction

Analyse lexicale

Ambig¨
uit´
e de l’analyse lexicale

Implementation du Maximal munch
I
I
I

Convertir les expressions r´eguli`eres en AFND
Ex´ecuter les AFND en parall`eles, en sauvegardant la derni`ere
correspondance
Si l’ensemble des automates n’arrivent plus `a r´eduire, nous
gardons la derni`ere correspondance et nous redemarrons la
recherche `a partir de ce point.

Exemple
I

T Do = do, T Double = double, T Mistere = [A-Za-z]

I

L’entr´ee `a reconnaitre est : DOUBDOUBLE

Remarque
La premi`ere simplification consiste `a relier les trois automates `a
une place de d´epart unique pour faure une association d’union et
donner un automate unique.

37 / 41

Introduction

Analyse lexicale

Ambig¨
uit´
e de l’analyse lexicale

Premier conflit (Suite)
Exemple 2
Supposons que l’entr´ee `a reconnaitre soit : DOUBLE. Deux Tokens
peuvent ˆetre candidats T Double et T Identifiant.

Resolution
I

Si deux expressions r´eguli`eres sont concurrentes, il faut retenir
celle qui a la plus grande priorit´e

I

Un moyen simple pour d´eterminer la priorit´e : Choisir la r`egle
qui est d´efinie la premi`ere

Remarque
Si aucune r`egle ne permet de r´eduire l’entr´ee, il faut rajouter une
r`egle qui permet de r´ecup´erer n’importe quel caract`ere et reporter
une erreur
38 / 41

Introduction

Analyse lexicale

Ambig¨
uit´
e de l’analyse lexicale

Second conflit
S’il y a plusieurs chemins pour analyser une entr´ee, comment
savoir lequel choisir ?
I Dans le cas pire, un AFND avec n ´
etats prend un temp de
2
O(mn ) pour reconnaitre une chaine de longueur m
I AFD mettent O(m) pour le faire
I Les ´
etapes de r´ealisation sont alors : Sp´ecification lexicale,
Expressions r´eguli`eres, AFND, AFD, Table de transition

Exemple 1
A
B
C
D

0
C
D
A
B

1
B
A
D
C
39 / 41

Introduction

Analyse lexicale

Ambig¨
uit´
e de l’analyse lexicale

1

3

5

7

i n t k T a b l e T r a n s i t i o n [ kNumEtat ] [ kNumSymbol ] =
{{0 ,0 ,1 ,3 ,7 ,1 , . . . } , . . . } ;
b o o l k T a b l e A c c e p t [ kNumEtat ] = { f a l s e , t r u e , . . . } ;
b o o l simulerAFD ( s t r i n g e n t r e e ){
int etat = 0;
f o r ( char ch : e n t r e e )
e t a t = k T a b l e T r a n s i t i o n [ e t a t ] [ ch ] ;
return kTableAccept [ e t a t ] ;

Exemple 2
Donner l’AFD ´equivalent de l’AFND d´eduit de l’exemple 1 de la
partie ”Premier conflit” puis d´erouler la reconnaissance de l’entr´ee.

41 / 41


Documents similaires


Fichier PDF luxtrust token
Fichier PDF tcompilo
Fichier PDF chap 3 compilation version finale ult
Fichier PDF finkel10
Fichier PDF whitepaper fr
Fichier PDF addcustomtoken


Sur le même sujet..