cours-2-7

Jean-Pierre Jacquot

Informations

• Publié par: Viwyir
• Nombre de lectures: 42
• Langue: Français

Extrait

m
m
Un compilateur 1
Anatomie d'un langage
Qu'y a-t-il dans un langage ?
– Une syntaxe
• un vocabulaire (lexique)
• des règles de construction des phrases (grammaire)
– Une sémantique
• un domaine sémantique
• des règles passage des constructions syntaxiques aux objets
sémantiques (fonction d'interprétation)
– Une machine d'exécution
• actions élémentaires
• gestion des noms ! (ne pas l'oublier ...)
DEUG 2 2000
Un compilateur 2
Sémantique opérationnelle de -logo
Objectif : transformer un programme écrit en -logo en une
suite d'actions exécutables,
c'est-à-dire, écrire un compilateur
Ce dont nous disposons:
modèlegrammaire de
tortue-logo
analyseur machine
syntaxique tortue
DEUG 2 2000
Page 1m
m
m
Un compilateur 3
Sémantique opérationnelle de -logo
Objectif : transformer un programme écrit en -logo en une
suite d'actions exécutables,
Ce qui reste
c'est-à-dire, écrire un compilateur
à voirCe dont nous disposons :
modèlegrammaire de
structure sémantique
tortue-logo
analyseur termes machine
Traducteur
syntaxique -logo tortue
DEUG 2 2000
Un compilateur 4
Structure de -logo
SEQ
PROC itere(x, a, n)
SI = n 1
ALORS SEQ A x; T a QES
SINON SEQ A x; T a;
itere(x, a, - n 1)
QES
IS
CORP;
PROC poly(longueur, nbcote)
SEQ
DEF angle PAR / 360 nbcote FED;
itere(longueur, angle, nbcote)
QES
CORP;
A 50; poly(50,4);
C ROUGE; poly(50, 6);
C BLEU ; poly(50,12)
QES
DEUG 2 2000
Page 2Un compilateur 5
Structure de -logo
SEQ
PROC itere(x, a, n) définition d'une procédure
SI = n 1
ALORS SEQ A x; T a QES nom
SINON SEQ A x; T a;
liste de paramètres
itere(x, a, - n 1)}
corps QES
IS
CORP;
PROC poly(longueur, nbcote)
SEQ
définition d'un nom
DEF angle PAR / 360 nbcote FED;
itere(longueur, angle, nbcote) application d'une procédure
QES
CORP;
A 50; poly(50,4);
C ROUGE; poly(50, 6);
commande élémentaire
C BLEU ; poly(50,12)
QES
DEUG 2 2000
Un compilateur 6
Syntaxe abstraite
Codage des structures d'un langage
fait abstraction des mots-clés
facilite le calcul
Concrètement : un type terme Caml
type prg =
Tourne of expr
| Avance of expr
| Colore of string
| Appfonc of string*expr list
| Cond of expr*prg*prg
| Proc of string*l_pars*prg
| Def of string*expr
| Seq of prg list
DEUG 2 2000
Page 3m
Un compilateur 7
Du concret à l'abstrait
PROC itere(x, a, n) Texte en -logo
SI = n 1
ALORS SEQ A x; T a QES
SINON SEQ A x; T a;
itere(x, a, - n 1)
Valeur Caml QES
IS
CORP
Proc
("itere", ["x"; "a"; "n"],
Cond
(Egal (Id "n", Cst 1.0),
Seq [Avance (Id "x"); Tourne (Id "a")],
Seq
[Avance (Id "x");
Tourne (Id "a");
Appfonc ("itere", [Id "x"; Id "a"; Moins (Id "n", Cst 1.0)])])))
DEUG 2 2000
Un compilateur 8
Du concret à l'abstrait
L'analyseur syntaxique retourne le terme « abstrait »
Lexèmes
structure de lalet p_prg = function
phraseétiquette ....
| [< 'L_Couleur; c=(p_couleur) >] -> Colore c
| [< nf=(p_ident); 'L_Parouv; pla=(p_l_args); 'L_Parfer>] -> Appfonc (nf, pla)
| [< 'L_Proc; dn= (p_ident); 'L_Parouv; plp=(p_l_pars); 'L_Parfer;
p=(p_prg); 'L_Corp>] -> Proc (dn, plp, p)
| [< 'L_Def; dn= (p_ident); 'L_Par; p=(p_expr); 'L_Fed>] -> Def (dn, p)
....
DEUG 2 2000
Page 4m
Un compilateur 9
Domaine sémantique
Que trouve-t-on dans un programme -logo ?
• Des expressions
• valeurs numériques
• valeurs booléennes (comparaisons)
• Des actions
» élémentaires :
• avancer, tourner, colorer
» composites :
• conditionelles
• exécutions de procédures
• Des définitions
• noms
• procédures
DEUG 2 2000
Un compilateur 10
Domaine sémantique
valeurs
numériques actions
listes
valeurs listes
de noms
booléennes d'actions
noms
DEUG 2 2000
Page 5Un compilateur 11
Domaine sémantique
valeurs
numériques actions
listes
valeurs listes
de noms
booléennes d'actions
fermetures
noms
DEUG 2 2000
Un compilateur 12
Domaine sémantique
valeurs
numériques actions
listes
valeurs listes
de noms
booléennes d'actions
fermetures
valeurs
noms
DEUG 2 2000
Page 6Un compilateur 13
Domaine sémantique
environnement
valeurs
numériques actions
listes
valeurs listes
de noms
booléennes d'actions
fermetures
valeurs
noms
DEUG 2 2000
Un compilateur 14
Statégie de compilation
Dépendante de 4 considérations :
» la nature des noms
• A quoi sont-ils associés ?
• Comment sont-ils « résolus »
» le codage des valeurs
• numériques et booléennes
• actions
» le modèle de calcul de la machine tortue
• actions de base
• moteur
» la nature des procédures
• relation entre paramètres et arguments
• représentation d'une procédure
• mécanisme d'exécution
DEUG 2 2000
Page 7Un compilateur 15
Les noms
Comme en Caml :
Un nom n'existe qu'à travers une liaison
» d'où une notion d'environnement
Un nom est remplacé le plus tôt possible par la valeur liée
» d'où la nécessité de définir un nom avant de l'utiliser
Contrairement à Caml
les noms de procédures, de paramètres et les autres ont des
traitements légèrement différents
Tactique
le compilateur remplace tous les noms (hors ceux de
procédures et de paramètres) par leur valeur
DEUG 2 2000
Un compilateur 16
Les valeurs
Comme en Caml
Les valeurs sont typées
• Nous utilisons des termes (étiquettes)
Certaines valeurs restent sous forme « symbolique »
• Lorsqu'il y a un nom de paramètre
Contrairement à Caml
Il n'y a pas de contrôle de types
Il n'y a que 2 types de valeurs simples
Tactique
Les valeurs sont calculées directement par le compilateur
DEUG 2 2000
Page 8Un compilateur 17
Codage des valeurs
type valeur = let rec s_exp =
Nombre of float function env ->
| Bool of bool function
| Symbolique of expr Plus (ag, ad) ->
| Fermeture of ((string list)* let sag = s_exp env ag
environnement* and sad = s_exp env ad
(actions list)) in add_val (sag, sad)
let add_val = function
Nombre ag, Nombre ad -> Nombre (ag +. ad)
| Symbolique ag,Nombre ad -> Symbolique (Plus (ag, Cst ad))
| Nombre ag,Symbolique ad -> Symbolique (Plus (Cst ag, ad))
| Symbolique ag,Symbolique ad -> Symbolique (Plus (ag, ad))
| _, _ -> failwith "add_val, arguments incompatibles ";;
DEUG 2 2000
Un compilateur 18
Les procédures
Comme en Caml
Une procédure est une valeur : une fermeture
Une procédure peut avoir des noms locaux
• (liste des paramètres)*envronnement*(liste d'actions)
Contrairement à Caml
Toutes les procédures peuvent être récursives
• on ne peut pas remplacer leur nom à la compilation
• toutes les procédures doivent avoir des noms différents
Une procédure n'est pas une fonction : elle ne retourne pas de
valeur
Tactique
La machine tortue gèrera les appels de procédures
DEUG 2 2000
Page 9m
m
Un compilateur 19
La machine -logo
machine -logo =
machine tortue + traitement des conditionnelles et des
procédures
type actions =
Move of valeur
| Turn of valeur
| Pen of color
| Apply of (string*(valeur list))
| Branch of (valeur*(actions list)*(actions list));;
DEUG 2 2000
Un compilateur 20
Appel de procédure
Nous procédons comme en Caml
1 - recherche de la fermeture dans l'environnement
2 - valuation des paramètres
» création d'un environnement local
3 - remplacement des paramètres par les arguments
» parcourt de la liste d'actions
» parcourt de l'environnement de la fermeture
» remplacement des valeurs « symboliques »
• on utiilser le compilateur d'expression pour cela
4 - appel récursif d