Techniques de compilation

Leila Jemni Ben Ayed

Ecole Nationale des Sciences de lInformatique

Lobjectif de ce cours est d tendre les connaissances en th orie des

langages et des automates la description des

langages de

programmation et leur analyse syntaxique en vue de leur compilation. Ce

cours d crit les concepts fondamentaux des langages de programmation

en commen ant, dans une premi re partie, par donner la syntaxe et la

s mantique, en insistant davantage sur la syntaxe. La traduction en code

interm diaire et lenvironnement dex cution font lobjet de la deuxi me

partie.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

Techniques de compilation

Introduction la compilation

II. Compilateur en une seule passe

III. Analyse syntaxique

IV. Analyse s mantique

V. Traduction en code pour

machine abstraite pile

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I. Introduction la Compilation

Plan

I.1. Compilateurs

I.2. Les Grammaires non contextuelles

I.3. Phases de Compilation

I.4. Qualit dun Compilateur

I.5. Outils pour la construction de Compilateurs

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.1. Compilateurs

volution des langages:

" Langage machine

" Langage assembleur

" Langages volu s : C, PASCAL, ADA (Algorithmiques)

PROLOG (Logiques)

" Langages de 4 me g n ration

Un compilateur est un programme qui

lit un

programme crit dans un premier langage(langage

source) et le traduit en un programme quivalent

crit dans un autre langage (le langage cible).

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.1. Compilateurs

Au cours de ce processus de traduction, un r le du

compilateur est de signaler son utilisateur la

pr sence derreurs dans le programme source.

PSource

Compilateur

PAssembleur

Messages

derreur

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.2. Exemples de grammaires non

I.2.

contextuelles

1) Une grammaire qui g n re lensemble des expressions arithm tiques utilisant les op rateurs + et * et

les chiffres {0,1,...9}

G = ({Exp}, {+, *, (, ), 0, 1, &9}, Exp, R}

R = {

Exp

Exp + Exp

Exp * Exp

(Exp)

9 }

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.2. Exemples de grammaires non

I.2.

contextuelles

2) Une grammaire qui g n re lensemble des expressions bool ennes utilisant les op rateurs

arithm tiques (oparith), les op rateurs relationnels (oprel) et les op rateurs bool ens (non, et et

ou) sur les identificateurs (id) et les nombres entiers (nb)

R = {

Expb

Expr

Expa

}

Expr

non(Expb)

Expb et Expb

Expb ou Expb

Expa oprel Expa

(Expr)

Expa oparith Expa

(Expa)

G = (V, T, Expb, R)

V = {Expb, Expr, Expa}

T = {id, nb, oprel, oparith, non, et, ou, (, )}

{<, >, <=, >=, <>, =}

oprel

oparith

{+, *, /, -}

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.2. Exemples de grammaires non

I.2.

contextuelles

3) Une grammaire qui g n re une s quence non vide de d clarations suivie de D but, suivie

dune s quence non vide dinstructions suivie de Fin . Chaque instruction peut tre une

instruction daffectation (se termine par ;) ou une instruction conditionnelle avec ou sans

sinon (qui se termine par FinSi). Les types utilis s sont entier et r el. La s quence g n r e

commence par program suivi dun nom.

R = {

Program id S_DCL D but S_INST Fin

G = (V, T, P, R)

V = {P, S_DCL, DCL, S_INST, INST, Expb, Expr, Expa}

T = {Program, D but, Fin, Var, :, id, :=, ;, Si, Sinon, Fin Si, (, ),

oparith, oprel, non, et, ou, entier, r el}

INST | INST S_INST

Var L_id : TYPE;

id | id, L_id

entier | r el

S_DCL DCL | DCL S_DCL

DCL

L_id

TYPE

S_INST

INST

Expb

Expr

Expa

}

id := Expa;

Si Expb alors S_INST Fin Si

Si Expb alors S_INST Sinon S_INST Fin Si

Expr | non(Expb) | Expb et Expb | Expb ou Expb

Expa oprel Expa

(Expr)

Exp oparith Exp

(Expa)

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.2. Exemples de grammaires non

I.2.

contextuelles

V rifier que la grammaire pr c dente g n re le

programme suivant :

Program test

Var a, b : entier;

D but

a:= 10;

Si a>= 10 alors a:= 20; Fin Si

Fin

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.2. Exemples de grammaires non

I.2.

contextuelles

Le programme est transform en une s quence de

terminaux.

Program id

Var id, id : entier;

D but

id:= nb;

Si id oprel nb alors id:= nb; Fin Si

Fin

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.2. Exemples de grammaires non

I.2.

contextuelles

S_DCL

Program

DCL D but

S_INST Fin

Var L_id : TYPE ;

INST S_INST

id , L_id entier

id := Expa ;

INST

En parcourant les feuilles

de larbre de gauche

droite, on trouve le

programme analyser

Donc ce programme est

syntaxiquement correct

nb Si Expb alors S_INST Fin Si

Expr

INST

Expa oprel Expa

id := Expa ;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de Compilation

On distingue deux parties:

Analyse

" Partitionne le programme source en ses constituants et

en cr e une repr sentation interm diaire.

Synth se

" Construit

le programme

cible

partir de

repr sentation interm diaire.

" Lanalyse

utilise

dune

grammaire non contextuelle qui g n re des

programmes du langage utilis .

constituants

les

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

PSource

Analyse lexicale

Analyse Syntaxique

Analyse s mantique

G n ration de code

interm diaire

Optimisation de code

G n ration de code

machine

Gestion de la

table de

symboles

Table des

identificateurs,

mots r serv s

et constantes

Gestion des

erreurs

Leila Jemni Ben Ayed

PCible

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Les compilateurs

comportent ces deux

parties.

change

machine, on peut ne

modifier que la partie

terminale

Psource

Analyse

Partie frontale

G n ration de

code

interm diaire

PLI

Partie terminale

G n rateur de code

machine

PASS

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Interface avec lanalyseur lexical

Type dun id

Valeur dun nb

Op rateur PPQ pour oprel

Lire caract re

Entr e

Rendre

caract re

Passer unit

lexicale et ses

attributs

Analyseur

lexical

Analyseur

syntaxique

" Pour lAS, lAL retourne lUL

" Pour lAsem, il retourne le type, la port e, &

" Pour le traducteur, il retourne la valeur du nombre, lop rateur utilis , &

" Si C est une variable caract re et le prog source est dans lentr e standard alors

linstruction C = getchar(); affecte le prochain caract re dentr e C et

linstruction ungetc(C, stdin); rend lentr e standard stdin la valeur de C.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Implantation des interactions avec lanalyseur lexical

Utilise getchar();

pour lire un

caract re

Rendre caract re

En utilisant ungetc(C, stdin)

AnalLex()

analyseur

lexical

Retourne une

unit lexicale

lappelant

ValLex

Positionne la

variable globale la

valeur de lunit

lexicale

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Analyse du programme source :

A chaque langage de programmation est associ e une

grammaire non contextuelle.

Lanalyse comprend quatre phases :

Phase1: analyse lin aire (ou lexicale) au cours de laquelle

le flot de caract res formant le programme source est lu

de gauche droite et group en unit s lexicales qui sont

une suite de caract res ayant une signification collective.

Ces unit s lexicales sont les terminaux de la grammaire.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

LAl retourne une UL pour lAS

Pour lAsem, si lUL est id alors il retourne une entr e dans

la table des identificateurs pour lidentificateur trouv .

Pour le traducteur, si lUL est nb, alors il retourne sa valeur

" si lUL est oprel alors il retourne lop rateur en question

lUL est oparith alors il retourne lop rateur en

" Si

question

Quand lanalyseur lexical rencontre un identificateur non

mot cl , il le cherche dans la table des id. Sil existe alors il

retourn lentr e associ e sinon il lui cr t une entr e et

retourne le num ro dentr e.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

par exemple si on dispose de la grammaire avec les r gles

id opaff Exp

suivantes:

Exp

Les unit s lexicales associ es au mot :

id | nb | (Exp) | Exp oparith Exp

position := initiale + vitesse * 60

Sont:

lidentificateur position

Lidentificateur initiale

Lidentificateur vitesse

Le signe de multiplication oparith 7) Le nombre nb

2) Le symbole daffectation opaff

4) Le signe daddition oparith

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Le lex me est la suite de caract res du fichier source qui forme lunit

lexicale. Le tableau suivant pr sente les lex mes et les unit s lexicales

associ es au mot position := initiale + vitesse * 60

R sultat

de lAL

lex me

position

initiale

vitesse

opaff

oparith

Unit lexicale

Opaff

Oparith

oparith

Pour lAS

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

par exemple si on dispose de la grammaire avec les r gles

suivantes:

DCL

Var L_ID : TYPE;

| Var L_ID : TYPE; DCL

| e

L_ID

TYPE

id | id, L_ID

entier | r el

Les unit lexicales associ es au mot (retourn es par lAL lAS):

Var a, b: entier; var c: r el;

Sont les suivantes :

Var

entier

;

Var

r el

;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

par exemple si on dispose de la grammaire avec les r gles

suivantes:

DCL

Var L_ID : TYPE;

| Var L_ID : TYPE; DCL

| e

L_ID

TYPE

id | id, L_ID

entier | r el

Table des id de variables

Lex me

Type

entier

r el

Si lAL retourne un r sultat lAS et lAsem alors le r sultat de

lAL pour le mot Var a, b: entier; var c: r el; sera :

Var

entier

;

Var

r el

;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Soit le mot a := c + 34; lAL retourne

Pour lAS : id := id oparith nb;

Pour lAsem : 1 := 3 oparith nb;

R sultat de lAL

oparith

;

c-a-d entier := r el oparith entier

Pour le traducteur : @a := @c + 34;

Table des id de variables

Lex me

Type

entier

r el

Adresse

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

par exemple si on dispose de la grammaire avec les r gles

suivantes:

DCL

DCL L_I

Var L_ID : TYPE;

| Var L_ID : TYPE; DCL

| e

id | id, L_ID

entier | r el

L_ID

TYPE

L_I

Table des id de variables

Lex me

Type

entier

r el

id := nb; | id := id; | id := nb; L_I | id := id; L_I

Si lAL retourne un r sultat lAS, lAsem et le traducteur alors le r sultat de

lAL pour le mot Var a, b: entier; var c: r el; b := 10; sera :

Var

entier

;

Var

r el

;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Var a, b: entier; var c: r el; b := 10;

Table des id de variables

Lex me

Type

entier

r el

Var

entier

;

Var

r el

;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Analyse du programme source :

les

sont

unit s

lexicales

Phase2: analyse hi rarchique (ou syntaxique) au cours de

regroup es

laquelle

hi rarchiquement en structure grammaticale.

Lanalyse syntaxique consiste v rifier que la suite dunit s

lexicales est g n r e par la grammaire du langage.

Ceci revient construire un arbre danalyse (ou syntaxique)

dont les feuilles concordent avec la suite dunit s lexicales

en les parcourant de gauche droite.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Analyse du programme source :

Phase3: analyse s mantique au cours de laquelle on

op re certain contr le pour sassurer que lassemblage des

constituants du programme a un sens. Une des op rations

principales dun Asem est

le contr le de type des

principales dun Asem est

op randes dune op ration, le contr le de la port e des

identificateurs

sous

programme, &.

au moment

lappel

dun

Dans le contr le de type,

lanalyseur s mantique peut

ins rer des op rations de conversion pour les expr dentier

vers r el.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Analyse du programme source :

Phase3: analyse s mantique

Nous distinguons deux types derreurs s mantiques:

" s mantique statique, contr l e au moment de la compilation telle

que :

Variable non d clar e

lincompatibilit de type,

la port e dune variable&

" S mantique dynamique, contr l e au moment de lex cution telle

que :

la division par z ro

les boucles infinies

le d bordement m moire

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Analyse du programme source :

Phase4: traduction en code interm diaire au cours de

laquelle la s quence dinstructions du programme est

traduite en une s quence dinstructions dans un langage

interm diaire. Par exemple : le langage pour machine

pile, le langage C, &

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Analyse du programme source :

La table des symboles contient des informations sur les

diff rents symboles et les attributs associ s. Par exemple

les identificateurs de

les mots cl s (ou r serv s) et

variables en sp cifiant lunit lexicale id et leurs attributs:

type, adresse, etc&

A chaque fois quune unit lexicale id est trouv e par lAL,

le lex me associ est ins r dans la table des symboles sil

na pas t d j ins r et lAL retourne id et un pointeur

vers une entr e de la table des symboles.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

Exemple

On veut illustrer les phases de compilation sur lexemple

Position := Initiale + Vitesse * 60;

id := Exp;

La grammaire est la suivante :

Exp

id | nb | (Exp) | Exp + Exp | Exp * Exp

Une Contrainte s mantique doit tre v rifi e :

Lop rateur de multiplication doit tre appliqu deux

op randes de m me type (entier, entier) ou (r el, r el)

Pour notre exemple, Vitesse est un r el et 60 est un nombre

entier, il faut alors convertir 60 dentier vers r el (60.0)

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

" Analyse lexicale

id1 := id2 + id3 * nb;

" Analyse syntaxique

id := Exp

;

Exp + Exp

id Exp * Exp

id nb

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

" Analyse s mantique

Comme vitesse est un r el, un compilateur peut convertir le nombre

entier nb en r el pour pouvoir utiliser lop rateur de multiplication

Var position, Initiale,

Vitesse : r el;

Analyseur

S mantique

id := Exp

Table des id de variables

Exp + Exp

Lex me

Type

Position

Initiale

Vitesse

R el

id Exp * Exp

entier vers r el

60.0

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.3. Phases de compilation

" G n ration de code interm diaire

Temp1 := Entier vers r el(60);

Temp2 := Temp1*id3;

Temp3 := id2 + Temp2;

id1 := Temp3;

" Optimisation de code Analyse syntaxique

Temp1 := id3*60.0;

id1 := id2 + Temp1;

" G n ration de code interm diaire (Machine VON NEUMAN)

Machin registres

MOVF id3, R2

MULF #60.0, R2

MOVF id2, R1

ADDF R2, R1

MOVF R1, id1

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.4. Qualit dun compilateur

Fournir le maximum derreurs en

une seule compilation

Rapidit

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

I.5. Outils pour la construction de

compilateurs

Assembleur

Ecriture en langage volu

Constructeurs automatiques de compilateurs : LEX et YACC

Grammaire non

contextuelle du

langage

Description

des unit s

lexicales du

langage

Leila Jemni Ben Ayed

G n rateur automatique

danalyseur syntaxique

Analyseur Syntaxique

crit en C ou en LPascal

G n rateur automatique

danalyseur lexical

Analyseur lexical

crit en C ou en LPascal

Yacc

Lex

Cours Techniques de Compilation-2012-

2013

II. Analyse lexicale

Plan

II.1. Pr sentation g n rale

II.2. Automates finis et expressions r guli res

II.3. Sp cification des unit s lexicales

II.4. Reconnaissance des unit s lexicales

II.5. Conception dun g n rateur dun analyseur

lexical

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.1. Pr sentation g n rale

" Lanalyseur

lexical constitue la premi re phase dun

compilateur. Sa t che principale est de lire les caract res

dentr e et de produire comme r sultat une suite dunit s

lexicales que lanalyseur syntaxique va utiliser.

Programme

Source

Lire caract re

Rendre

caract re

Analyseur

lexical

Passer unit

lexicale et ses

attributs

Obtenir

prochaine

unit lexicale

Table des

symboles

Analyseur

syntaxique

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.1. Pr sentation g n rale

Rq. LAL est un sous programme de lAS. A la r ception de

prochaine unit , lAL lit les caract res dentr e jusqu ce quil puisse identifier

la prochaine unit lexicale.

Unit lexicale : produite la m me pour un ensemble de chaines de caract res

Mod le dune unit lexicale : r gle qui d crit une unit lexicale (Expression r guli re)

Lex me : une suite de caract res du PS qui concorde avec le mod le dune unit

lexicale.

Unit Lexicale

Lex mes

Description formelle des

mod les

const

oprel

const

< <= = <> > >=

(<+<=+=+<>+>+>=)

Pi compte D2

3 6.780 6.0

lettre(lettre+chiffre)*

Chiffre+ + chiffre+.chiffre+

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.2. Automates finis et expressions

r guli res

" Un analyseur lexical est bas sur les syst mes de transition (ou bien les

automates finis)

Un diagramme de transition pour la reconnaissance de >=

D but

autre

return(oprel, PGE)

return(oprel, PGQ)

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.2. Automates finis et expressions

r guli res

Un diagramme de transition pour la reconnaissance

de >=

D but

autre

return(oprel, PGE)

return(oprel, PGQ)

Ce diagramme fonctionne comme suit:

Son tat de d part est l tat 0. Dans l tat 0, on lit le prochain caract re de lentr e. On suit larc

> depuis l tat 0 vers l tat 1 si le caract re dentr e est >. Sinon, on na r ussi reconna tre ni >

ni >=. En atteignant l tat 1, on lit le prochain caract re dentr e. Larc tiquet = entre l tat 1

et l tat 2 doit tre suivi si le caract re dentr e est = et le diagramme reconna t >= (PGE).

Autrement, larc tiquet autre conduit l tat 3. Le diagramme reconna t ainsi > (PGQ) et

recule dun caract re dans lentr e. On utilise une * pour signaler les tats dans lesquels ce

recul dans lentr e doit tre fait.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.2. Automates finis et expressions

r guli res

Un diagramme de transition pour la

reconnaissance des op rateurs de relation

D but

autre

return(oprel, PPE)

return(oprel, DIF)

return(oprel, PPQ)

return(oprel, EGA)

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

autre

return(oprel, PGE)

return(oprel, PGQ)

II.2. Automates finis et expressions

r guli res

Un diagramme de transition pour la reconnaissance

des identificateurs et des mots cl s

lettre, chiffre

D but

lettre

autre

return(UnilexId(), RangerId())

Laction sp cifi e par le symbole * permet de reculer dune position sur le

fichier source apr s la consommation dun symbole autre quune lettre ou

un chiffre.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.2. Automates finis et expressions

r guli res

Les fonctions RangerId() et UnilexId()

La fonction RangerId() a acc s au tampon o lunit lexicale identificateur a t

localis e. On examine la table des symboles et si on trouve le lex me avec

lidentificateur mot cl , RangerId() rend 0. Si on trouve le lex me comme variable du

programme, RangerId() rend un pointeur vers une entr e dans la table des symboles. Si

on ne trouve pas le lex me dans la table des symboles, il y est plac en tant que

variable et un pointeur vers cette nouvelle entr e est retourn .

La fonction UnilexId() recherche le lex me dans la table des symboles. Si le lex me est

un mot cl , lunit lexicale correspondante est retourn e; autrement, lunit lexicale id

est retourn e.

NB.

Le diagramme de transition ne change pas si on doit reconna tre de nouveaux mots

cl s; on initiale simplement la table des symboles avec les nouvelles chaines et les

nouvelles unit s lexicales.

En pratique, la table des symboles peut tre r partie sur deux tables: table des

mots cl s et table des identificateurs de variables.

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.3. Sp cification des unit s lexicales

Expressions r guli res

Les expressions r guli res sont une notation importante pour

sp cifier des mod les dunit s lexicales.

Exemples:

Soit L lensemble {A, B, &, Z, a, b, &z} et C lensemble {0, 1, &9}

L+C ou(L C) est lensemble des lettres et des chiffres

LC est lensemble des chaines form es dune lettre suivie

dun chiffre

L4 est lensemble des chaines de quatre lettres

L* est lensemble de toutes les lettres, y compris e , la

chaine vide.

L(L+C)* est lensemble de toutes les chaines de lettres et

de chiffres commen ant par une lettre.

C+ est lensemble de toutes les chaines dau moins un

chiffre (repr sentations d cimales des entiers naturels)

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.3. Sp cification des unit s lexicales

D finitions r guli res

Soit S un alphabet de symboles de base, une d finition r guli re est une suite de

d finitions de la forme :

O chaque di est un nom distinct et chaque ri est une expression r guli re sur les

symboles de S

{d1, d2, &, di-1}

Exemples:

Lettre

chiffre

A|B|&|Z|a|b|&|z

0|1|&|9

Lettre(Lettre + Chiffre)*

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.4. Reconnaissance des unit s

lexicales

Nous utilisons les diagrammes de transition pour reconna tre des unit s lexicales

Exemple:

Consid rons le fragment de la grammaire suivant:

Instr

si expr alors instr

| si expr alors instr sinon instr

| id opaff id pv

| id opaff nb pv

terme oprel terme

| terme

| nb

expr

terme

O si, alors, sinon, oprel, id et nb engendrent les ensembles de chaines donn es par

les d finitions r guli res suivantes:

alors

sinon

oprel

alors

sinon

< | <= | = | <> | > | >=

lettre(lettre|chiffre)*

opaff

chiffre+

;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.4. Reconnaissance des unit s

lexicales

Le mot en entr e dans le fichier source est le suivant :

si a1 >= b alors a1

10;

lex me

type

Mots cl s

alors

Lanalyseur lexical retourne la s quence suivante dunit s

lexicales avec leurs attributs:

oprel

PGE

alors

opaff

;

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.4. Reconnaissance des unit s

lexicales

Rq. On suppose que les lex mes sont s par s par un

espace consistant dune suite non vide de blancs,

tabulations et fins de lignes. Notre analyseur lexical

doit liminer ces espaces en comparant une chaine

avec la d finition r guli re suivante :

D lim

d lim+

blanc | tabulation | fin de ligne

Si lanalyseur lexical trouve une correspondance avec

bl, il ne retourne pas lunit lexicale lanalyseur

lunit

syntaxique.

lexicale qui suit le blanc et le retourne lanalyseur

syntaxique.

Il continue pour

rechercher

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.4. Reconnaissance des unit s lexicales

Syst me de transition associ un analyseur lexical

bl, tab, \n

D but

Echec()

autre

EOF

l, c

autre

return(UnilexId(), RangerId())

return(nb, val)

return(oprel, PPE)

return(oprel, DIF)

return(oprel, PPQ)

return(oprel, EGA)

return(EOF, 0)

autre

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

return(oprel, PGE)

return(oprel, PGQ)

II.4. Reconnaissance des unit s lexicales

Syst me de transition associ un analyseur lexical

Init(Val)

bl, tab, \n

l, c

D but

Add(Val, c)

autre

Add(Val, c)

autre

return(UnilexId(), RangerId())

return(nb, conv(val))

return(oprel, PPE)

return(oprel, DIF)

Erreur()

autre

EOF

autre

return(oprel, PPQ)

return(oprel, EGA)

return(EOF, 0)

autre

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

return(oprel, PGE)

return(oprel, PGQ)

II.4. Reconnaissance des unit s lexicales

Code C dun analyseur lexical

Unilex AnalLex() / Unilex est une chaine si Alalex retourne uniquement lunit lexicale/

{

/* Unilex est un entier si Analex retourne lunit lexicale et chaque unit est d finie comme une

constante*/

While(1)

/* Unilex est un enregistrement si Analex

retourne lunit lexicale et un attribut*/

{

Switch(etat)

{

case 0: Init(Chaine); car = carsuivant();

if(car == || car == \t || car = \n)

{ etat = 0; debutlex ++; }

else if( car == <) etat = 5;

else if (car == =) etat = 9;

else if (car == >) etat = 10;

else if (isletter(car)) Ajouter(car, chaine);

etat = 1;

else if(isdigit(car)) Ajouter(car, chaine);

etat = 3;

else if(car == EOF) etat = 13;

else Erreur();

case 1: car = carsuiv();

if(isletter(car) || isdigit(car))

ajouter(car, chaine);;

else etat = 2;

break;

case 2: Reculer(1); RangerId(); return(UniLexId()); /*

cas o lanalyseur lexical retourne uniquement

*/lunit lexicale sinon, il faut utiliser un

enregistrement (symbole)*/

&&&&.

case 3: car = carsuiv();

if(isdigit(car)) ajouter(car, chaine);

else etat = 4;

break;

case 4 : Reculer(1); Return(NB); case 6: Return(Oprel);

&&&&&

case 13: Return(EOF);

}

Leila Jemni Ben Ayed

Cours Techniques de Compilation-2012-

2013

II.4. Reconnaissance des unit s lexicales

Code C dun analyseur lexical (cas du retour dun enregistrement dans une

variable globale symbole deux champs (UL, Att))

Unilex AnalLex() / Unilex est une chaine si Alalex retourne uniquement lunit lexicale/

{

/* Unilex est un entier si Analex retourne lunit lexicale et chaque unit est d finie comme une

constante*/

While(1)...