ENI-ABT BAMAKO 2018
LANGAGE ET COMPILATION
Module4
Chargé de cours:
Dr Yacouba GOÏTA
Tél : [Link]
Email : goita_yacouba@[Link]
Compilation et langages
• Analyse lexicale avec ocamllex
• Analyse syntaxique avec menhir
2
3
Analyse lexicale
Quandj’etaisenfant,onm’avaitditquelePère
Noëldescendaitparlacheminée,etquelesord
inateursseprogrammaientenbinaire.J’aiapp
risdepuisquelaprogrammationsefaisaitdepr
éférencedansdeslangagesdehautniveau,plu
sabstraitsetplusexpressifs.
4
Analyse lexicale
• Quand j’étais enfant, on m’avait dit que le
Père Nöel descendait par la cheminée, et que
les ordinateurs se programmaient en binaire.
J’ai appris depuis que la programmation se
faisait de préférence dans des langages de
haut niveau, plus abstraits et plus expressifs.
introduction de la thèse de X. Leroy
5
Analyse lexicale
• L’analyse lexicale est le découpage du
texte source en <<mots>>.De même que
dans les langues naturelles, ce découpage
en mots facilite le travail de la phase
suivante, l’analyse syntaxique. Ces mots
sont appelés des lexèmes (tokens)
6
Analyse lexicale
• source = suite de caractères
fun x -> (* ma fonction *)
x+1
7
Les blancs
• Les blancs (espace, retour chariot, tabulation, etc.)
jouent un rôle dans l’analyse lexicale; ils permettent
notamment de séparer deux lexèmes
• Ainsi funx est compris comme un seul lexème
(l’identificateur funx) et fun x est compris comme
deux lexèmes (le mot clé fun et l’identificateur x)
• De nombreux blancs sont néanmoins inutiles
(comme dans x + 1 ) et simplement ignorés
• Les blancs n’apparaissent pas dans le flot de
lexèmes renvoyé
8
Les blancs
• Les conventions différent selon les langages, et
certains des caractères <<blancs>> peuvent être
significatifs.
• Exemples :
• les tabulations pour make
• retours chariot et espaces de début de ligne en
Python ou en Haskell (l’indentation détermine la
structure des blocs)
9
• Les commentaires jouent le rôle de blancs
• fun(* et hop *) x -> x + (* j’ ajoute un *) 1
• Ici le commentaire (* et hop *) joue le rôle
d’un blanc significatif (sépare deux
lexèmes) et le commentaire (* j’ajoute un
*) celui d’un blanc inutile
10
Les commentaires
• Note: les commentaires sont parfois
exploités par certains outils (ocamldoc,
javadoc, etc.), qui les traitent alors
différemment dans leur propre analyse
lexicale
• val length : ’a list -> int
(** Return the length (number of elements) of ...
11
Quels outils
• Pour réaliser l’analyse lexicale, on va
utiliser
– des expressions régulières pour décrire
les lexèmes
– des automates finis pour les reconnaître
• On exploite notamment la capacité à
construire automatiquement un automate
fini déterministe reconnaissant le langage
décrit par une expression régulière
12
Expressions régulières
r ::= ∅ langage vide
|𝛜 mot vide
|a caractère a ∈ A
| r r concaténation
| r | r alternative
| r * étoile
Conventions : l’´étoile a la priorité la plus forte,
puis la concaténation, puis enfin l’alternative
13
Sémantique
• Le langage défini par l’expression régulière r est
l’ensemble de mots L(r) défini par
L(∅) = ∅
L(𝛜) = {𝛜}
L(a) = {a}
L(r1 r2) = {w1w2 | w1 ∈ L(r1) ∧ w2 ∈ L(r2)}
L(r1 | r2) = L(r1) ∪ L(r2)
L(r*) = Un ≥0 L(rn) ou r0 =𝛜, rn+1 = rrn
Ces langages sont aussi reconnus par des automates
finis.
14
Exemple
Sur l’alphabet {a,b}
• mots de trois lettres
(a|b)(a|b)(a|b)
• mots se terminant par un a
(a|b)*a
• mots alternant a et b
(b| 𝛜)(ab)*(a| 𝛜)
15
Reconnaissance de lexèmes
16
Constantes entières
• Expression régulière
• (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*
• Automate
17
Identificateurs
• Expression régulière
• ( a|b| . . . |z|A|B| . . . |Z) (a|b| . . . |z|A|B| . . . |Z| |0|1| . . . |9)*
• Automate
•
18
Constantes flottantes
• Expression régulière
• dd*(.d*|(𝛜|.d*)(e|E)(𝛜|+|−)dd*)
• Ou d=0|1|...|9
• Automate
19
Commentaires
• Expression régulière
• ou r1 = tous les caractères sauf * et )
• et r2 = tous les caractères sauf *
• Automate fini
•
20
Analyseur lexical
• Un analyseur lexical est un automate fini pour la <<réunion>>
de toutes les expressions régulières définissant les lexèmes
• Le fonctionnement de l’analyseur lexical, cependant, est
différent de la simple reconnaissance d’un mot par un
automate, car
• il faut décomposer un mot (le source) en une suite de
mots reconnus
• il peut y avoir des ambiguïtés
• il faut construire les lexèmes (les états finaux
contiennent des actions)
21
Ambiguïtés
• Le mot funx est reconnu par l’expression régulière
des identificateurs,
• mais contient un préfixe reconnu par une autre
expression régulière (fun)
• ⇒ On fait le choix de reconnaître le lexème le plus
long possible
• Le mot fun est reconnu par l’expression régulière du
mot clé fun mais aussi par celle des identificateurs
• ⇒ On classe les lexèmes par ordre de priorité
22
Pas de retour en arrière
• Avec les trois expressions régulières
a , ab , bc
• un analyseur lexical va échouer sur l’entrée
abc
• ( ab est reconnu, comme plus long, puis
échec sur c)
• pourtant le mot abc appartient au langage
a|ab|bc
23
Analyseur lexical
• Exemple : le mot clé fun et les identificateurs
24
Analyseur lexical
• L’analyseur lexical doit donc mémoriser le dernier
état final rencontré, le cas échéant
• Lorsqu’il n’y a plus de transition possible, deux
possibilités :
• aucune position finale n’a été mémorisée
⇒ échec de l’analyse lexicale
• on a lu le préfixe wv de l’entrée, avec w le lexème
reconnu par le dernier état final rencontré
⇒ on renvoie le lexème w, et l’analyse redémarre
avec v préfixe au reste de l’entrée
25
Outils
• En pratique, on dispose d’outils qui
construisent les analyseurs lexicaux à
partir de leur description par des
expressions régulières et des actions
• C’est la grande famille de lex : lex, flex,
jflex, ocamllex, etc.
26
L’outil ocamllex
Un fichier ocamllex porte le suffixe .mll et a
la forme suivante
27
Syntaxe
{
... code OCaml arbitraire ...
}
rule f1 = parse
| regexp1 { action1 }
| regexp2 { action2 }
| ...
and f2 = parse
...
and fn = parse
...
{
... code OCaml arbitraire ...
28
}
L’outil ocamllex
• On compile le fichier [Link] avec
ocamllex
% ocamllex [Link]
• Ce qui produit un fichier OCaml [Link]
qui définit une fonction pour chaque
analyseur f1, . . ., fn :
29
L’outil ocamllex
• val f1 : [Link] -> type1
• val f2 : [Link] -> type2
• ...
• val fn : [Link] -> typen
30
Le type [Link]
• Le type [Link] est celui de la structure de
données qui contient l’état d’un analyseur lexical
• Le module Lexing de la bibliothèque standard
fournit plusieurs moyens de construire une valeur
de ce type
val from_channel : Pervasives.in_channel -> lexbuf
val from_string : string -> lexbuf
val from_function : (string -> int -> int) -> lexbuf
31
Les expressions régulières d’ ocamllex
32
Exemples
Identificateurs
| [’a’-’z’ ’A’-’Z’] [’a’-’z’ ’A’-’Z’ ’_’ ’0’-’9’]* { ... }
Constantes entières
| [’0’-’9’]+ { ...}
Constantes flottantes
| [’0’-’9’]+
( ’.’ [’0’-’9’]*
| (’.’ [’0’-’9’]*)? [’e’ ’E’] [’+’ ’-’]? [’0’-’9’]+ )
{ ... }
33
Raccourcis
• On peut définir des raccourcis pour des
expressions régulières
• let letter = [’a’-’z’ ’A’-’Z’]
• let digit = [’0’-’9’]
• let decimals = ’.’ digit*
• let exponent = [’e’ ’E’] [’+’ ’-’]? digit+
34
Raccourcis(suite)
rule token = parse
| letter (letter | digit | ’_’)* { ... }
| digit+ { ... }
| digit+ (decimals | decimals? exponent) { ... }
35
Ambiguïtés
• Pour les analyseurs définis avec le mot clé
parse, la règle du plus long lexème
reconnu s’applique.
• A longueur égale, c’est la règle qui apparaît
en premier qui l’emporte
| "fun" { Tfun }
| [’a’-’z’]+ as s { Tident s }
36
Ambiguïtés(suite)
• Pour le plus court, il suffit d’utiliser shortest
à la place de parse
rule scan = shortest
| regexp1 { action1 }
| regexp2 { action2 }
...
37
Récupérer le lexème
• On peut nommer la chaîne reconnue, ou
des sous-chaînes reconnues par des
sous-expressions régulières, à l’aide de la
construction as
| [’a’-’z’]+ as s { ... }
| ([’+’ ’-’]? as sign) ([’0’-’9’]+ as num) { ... }
38
Traitement des blancs
• Dans une action, il est possible de rappeler
récursivement l’analyseur lexical, ou l’un des autres
analyseurs simultanément définis.
• Le tampon d’analyse lexical doit être passé en
argument ;
• il est contenu dans la variable lexbuf
Il est ainsi très facile de traiter les blancs:
rule token = parse
| [’ ’ ’\t’ ’\n’]+ { token lexbuf }
| ...
39
Commentaires
• Pour traiter les commentaires, on peut utiliser une
expression régulière ou un analyseur dédié :
• rule token = parse
| "(*" { comment lexbuf }
| ...
and comment = parse
| "*)" { token lexbuf }
| _ { comment lexbuf }
| eof { failwith "commentaire non terminé" }
• Avantage : on traite correctement l’erreur liée à un
commentaire non fermé
40
Commentaires imbriqués
• Autre intérêt: on traite facilement les commentaires
imbriqués
• Avec un compteur
• rule token = parse
| "(*" { level := 1; comment lexbuf; token lexbuf }
| ...
and comment = parse
| "*)" { decr level; if !level > 0 then comment lexbuf }
| "(*" { incr level; comment lexbuf }
| _ { comment lexbuf }
| eof { failwith "commentaire non termin´e" }
41
Commentaires imbriqués
• ...ou sans compteur !
• rule token = parse
| "(*" { comment lexbuf; token lexbuf }
| ...
and comment = parse
| "*)" { () }
| "(*" { comment lexbuf; comment lexbuf }
| _ { comment lexbuf }
| eof { failwith "commentaire non terminé" }
• note : on a donc dépassé la puissance des expressions
régulières
42
Les quatre règles
• Quatre règles à ne pas oublier quand on écrit un
analyseur lexical
1. traiter les blancs
2. les règles les plus prioritaires en premier (par ex.
mots clés avant identificateurs)
3. signaler les erreurs lexicales (caractères illégaux, mais
aussi commentaires ou chaînes non fermées,
séquences d’échappement illégales, etc.)
4. traiter la fin de l’entrée (eof)
43
Efficacité
• Par défaut, ocamllex encode l’automate dans une
table, qui est interprétée à l’exécution
• L’option -ml permet de produire du code OCaml pur,
ou l’automate est encodé par des fonctions ; ce n’est
pas recommandé en pratique cependant
44
Efficacité(suite)
• Même en utilisant une table, l’automate
peut prendre beaucoup de place,
• en particulier s’il y a de nombreux mots
clés dans le langage
45
Efficacité(suite)
{
let keywords = [Link] 97
let () = [Link] (fun s -> [Link] keywords s ())
["and", AND; "as", AS; "assert", ASSERT;
"begin", BEGIN; ...
}
rule token = parse
| ident as s
{ try [Link] keywords s with Not_found -> IDENT s }
46
Sensibilité à la casse
• Si on souhaite un analyseur lexical qui ne
soit pas sensible à la casse, surtout ne
pas écrire
| ("a"|"A") ("n"|"N") ("d"|"D")
{ AND }
| ("a"|"A") ("s"|"S")
{ AS }
| ("a"|"A") ("s"|"S") ("s"|"S") ("e"|"E") ("r"|"R") ("t"|"T")
{ ASSERT }
| ...
47
Sensibilité à la casse(suite)
• mais plutôt
rule token = parse
| ident as s
{ let s = [Link] s in
try [Link] keywords s with Not_found -> IDENT s }
48
Compilation et dépendances
• Pour compiler (ou recompiler) les modules OCaml,
il faut déterminer les dépendances entre ces
modules, grâce à ocamldep
• Or ocamldep ne connaît pas la syntaxe ocamllex ⇒
il faut donc s’assurer de la fabrication préalable du
code OCaml avec ocamllex
49
Compilation et dépendances(suite)
• le Makefile ressemble donc `a ceci
[Link]: [Link]
ocamllex [Link]
.depend: [Link]
ocamldep *.ml *.mli > .depend
include .depend
Alternative: utiliser ocamlbuild
50
Récapitulation
• les expressions régulières sont `a la base de l’analyse
lexicale
• le travail est grandement automatisé par des outils tels
que ocamllex
• ocamllex est plus expressif que les expressions
régulières, et peut être utilisé bien au delà de l’analyse
lexicale
(note : ces transparents sont réalisés avec un
préprocesseur
ALTEX écrit à l’aide d’ocamllex)
51
52
Syntaxe abstraite
• Un programme , en tant qu’objet syntaxique (suite
de caractères), est trop difficile à manipuler. On
préfère utiliser la syntaxe abstraite.
• Ainsi les expressions
2*(k+1)
Et
(2*((k)+1))
Et
2 * (* je multiplie par deux *) ( k + 1 )
53
Syntaxe abstraite(suite)
• représentent toutes le même arbre de
syntaxe abstraite
54
Notation
• On définit une syntaxe abstraite par une
grammaire, de la manière suivante
e ::= c constante
| x variable
| e + e addition
| e × e multiplication
| ...
55
Traduction :
<<une expression e est
▪ soit une constante,
▪ soit une variable,
▪ soit l’addition de deux expressions,
▪ soit la multiplication de deux expressions,
▪ etc.>>
56
Notation
• La notation e1 + e2 de cette syntaxe
abstraite emprunte le symbole de la
syntaxe concrète
• Mais on aurait pu tout aussi bien choisir
Add(e1, e2) ou +(e1, e2), etc.
57
Représentation de la syntaxe
abstraite
• En Caml, on réalise les arbres de syntaxe
abstraite par des types récursifs
type binop = Plus | Mult | ...
type expr =
| Eint of int
| Evar of string
| Ebinop of binop * expr * expr
L’expression 2 * (k + 1) est représentée par
Ebinop (Mult, Eint 2, Ebinop(Plus, Evar "k", Eint 1))
58
Sucre syntaxique
• On appelle sucre syntaxique une construction de la
syntaxe concrète qui n’existe pas dans la syntaxe
abstraite
• Elle est donc traduite `a l’aide d’autres constructions de
la syntaxe abstraite, généralement pendant l’analyse
syntaxique
• Exemple : en Caml l’expression [e1; e2; ...; en] est du
sucre pour
• e1 :: e2 :: ... :: en :: [ ]
59
Analyse syntaxique
• L’objectif de l’analyse syntaxique est de
reconnaître les phrases appartenant à la
syntaxe du langage
• Son entrée est le flot des lexèmes
construits par l’analyse lexicale, sa sortie
est un arbre de syntaxe abstraite
60
Analyse syntaxique
• suite de lexèmes
• analyse syntaxique
61
Erreurs de syntaxe
• En particulier, l’analyse syntaxique doit
détecter les erreurs de syntaxe et
• les localiser précisément
• les identifier (le plus souvent seulement
erreur de syntaxe mais aussi <<parenthèse
non fermée>>, etc.)
• voire, reprendre l’analyse pour découvrir de
nouvelles erreurs
62
Quels outils
• Pour l’analyse syntaxique, on va utiliser
• une grammaire non contextuelle pour décrire la
syntaxe
• un automate `a pile pour la reconnaître
• C’est l’analogue des expressions régulières /
automates finis utilisés dans l’analyse lexicale
63
Grammaire non contextuelle
• Définition
• Une grammaire non contextuelle (ou hors contexte)
est un quadruplet ( N , T , S , R) ou
• N est un ensemble fini de symboles non
terminaux
• T est un ensemble fini de symboles terminaux
• S ∈ N est le symbole de départ (dit axiome)
• R ⊆ N × ( N ∪ T)* est un ensemble fini de règles
de production
64
Exemple : expressions
arithmétiques
• Symboles terminaux : +, *, (, ) , int
• Symboles non terminaux : E
• Symbole de départ : E
• Règles :
E→E+E
| E*E
| (E)
| int
int désigne ici le lexème correspondant à une
constante entière(i.e. sa nature, pas sa valeur) 65
Dérivation: Définition
• Un mot u ∈ (N ∪ T)* se dérive en un mot v ∈ (N ∪ T)*, et
on note
• u → v, s’il existe une décomposition
u = u1Xu2
• avec X ∈ N, X → β ∈ R et
v = u1 β u2
• Exemple :
66
Dérivation
• Une suite w1 → w2 → ·· · → wn est appelée une
dérivation.
• On parle de dérivation gauche (resp. droite) si
le non terminal réduit est systématiquement le
plus à gauche i.e. u1 ∈ T* (resp. le plus `a droite
i.e. u2 ∈ T*)
• On note →* la clôture réflexive transitive de →
67
Exemple
E→E*E
→ int * E
→ int * ( E )
→ int * ( E + E )
→ int * ( int + E )
→ int * ( int + int )
En particulier
E →* int * ( int + int )
68
Arbre de dérivation
• Définition
• A toute dérivation S →* w, on peut associer un
arbre de dérivation, dont les nœuds sont
étiquetés ainsi
• la racine est S
• les feuilles forment le mot w dans l’ordre infixe
• tout nœud interne X est un non terminal dont les fils
sont étiquetés par β ∈ (N ∪ T)* avec X → β une règle de
la dérivation.
Attention : ce n’est pas la même chose que l’arbre de
syntaxe abstraite
69
Exemple
• La dérivation gauche
• E → E + E → int + E → int + E * E → int + int * E →
int + int * int
• donne l’arbre de dérivation
• mais la dérivation droite
• E → E + E → E + E * E → E + E * int → E + int * int
→ int + int * int également
70
Ambiguïté
• Définition
• Une grammaire est dite ambiguë si un mot au
moins admet plusieurs arbres de dérivation
• exemple : le mot int + int * int admet les deux
arbres de dérivations
71
Ambiguïté(suite)
• Désambiguïsation : modification de la
grammaire ou ajout de priorités
⇒ on en parle la semaine prochaine
•
72
Outil
• Nous verrons dans les séances à venir comment
cette analyse est faite.
• En pratique, le travail est automatisé par de
nombreux outils qui construisent des analyseurs
syntaxiques `a partir d’une grammaire et d’actions
• C’est la grande famille de yacc, bison, ocamlyacc,
cups, menhir, . . .
(YACC signifie Yet Another Compiler Compiler)
73
L’outil Menhir
74
Menhir
• Menhir est un outil qui transforme une grammaire
en un analyseur Ocaml.
• Chaque production de la grammaire est
accompagnée d’une action
sémantique i.e. du code OCaml construisant une
valeur sémantique (typiquement un arbre de
syntaxe abstraite)
• Menhir s’utilise conjointement avec un analyseur
lexical (tel ocamllex)
75
Structure
• Un fichier Menhir porte le suffixe .mly et a
la structure suivante:
%{
... code OCaml arbitraire ...
%}
...déclaration des tokens...
...déclaration des précédences et associativités...
...déclaration des points d’entrée...
76
Structure
%%
non-terminal-1:
| production { action }
| production { action }
;
non-terminal-2:
| production { action }
...
77
Exemple : [Link]
%%
... code OCaml arbitraire ...
%token PLUS LPAR RPAR EOF
%token <int> INT
%start <int> phrase
%%
78
Exemple : [Link]
phrase:
e = expression; EOF { e }
;
expression:
| e1 = expression; PLUS; e2 = expression { e1 +
e2 }
| LPAR; e = expression; RPAR { e }
| i = INT { i }
;
79
Exemple
• On compile le fichier [Link] de la
manière suivante
% menhir -v [Link]
On obtient du code OCaml pur dans [Link](i),
qui contient notamment
• La déclaration d’un type token
type token = RPAR | PLUS | LPAR | INT of int | EOF
80
Exemple
• et, pour le non terminal déclaré avec %start, une
fonction du type
• val phrase: ([Link] -> token) -> [Link] -> int
• Comme on le voit, cette fonction prend en
argument un analyseur lexical,
• du type de celui produit par ocamllex (cf. début du
cours)
81
Conflits
• Lorsque la grammaire est ambiguë, Menhir
présente les conflits à l’utilisateur
• les fichiers .automaton et .conflicts contiennent,
le cas échéant, des informations sur les conflits
détectés
• nous aborderons ce point en détail dans les
séances à venir.
82
Conflits : avant-goût
• Sur la grammaire ci-dessus, Menhir signale
un conflit
% menhir -v [Link]
Warning: one state has shift/reduce conflicts.
Warning: one shift/reduce conflict was arbitrarily resolved.
• qui concerne l’ambiguïté entre deux lectures
possibles de l’expression 1 + 2 + 3
83
Conflits : avant-goût(suite)
1+2+3
84
Exemple
• On peut résoudre ce conflit en indiquant
que PLUS est associatif à gauche
• %token PLUS LPAR RPAR EOF
%token <int> INT
%left PLUS
%start <int> phrase
%%
• phrase:
e = expression; EOF { e }
;
85
Exemple(suite)
expression:
| e1 = expression; PLUS; e2 = expression { e1 + e2 }
| LPAR; e = expression; RPAR { e }
| i = INT { i }
;
86
Priorités
• Pour les conflits entre différents opérateurs, on
peut aussi associer des priorités aux lexèmes,
avec la convention suivante :
• l’ordre de déclaration des associativités fixe les
priorités (les premiers lexèmes ont les priorités
les plus faibles)
• plusieurs lexèmes peuvent apparaître sur la
même ligne, ayant ainsi la même priorité
87
Exemple
• Exemple :
%left PLUS MINUS
%left TIMES DIV
88
Localisations
• Pour que les phases suivante s de l’analyse
(typiquement le typage) puissent localiser les
messages d’erreur, il convient de conserver une
information de localisation dans l’arbre de syntaxe
abstraite
• Menhir fournit cette information dans $startpos et
$endpos, deux valeurs du type [Link] ;
cette information lui a ´et´e transmise par l’analyseur
lexical
89
Localisations(suite)
• Attention:
• ocamllex ne maintient automatiquement que la
position absolue dans le fichier; pour avoir les
numéros de ligne et de colonnes à jour, il faut un
traitement spécial du retour chariot dans
l’analyseur lexical.
90
Localisations(suite)
• Une façon de conserver l’information de
localisation dans l’arbre de syntaxe abstraite est
la suivante
type expression =
{ desc: desc;
loc : [Link] * [Link] }
and desc =
| Econst of int
| Eplus of expression * expression
| Eneg of expression
| ...
91
Localisations(suite)
• La grammaire peut donc ressembler à ceci
expression:
| d = desc { { desc = d; loc = $startpos, $endpos } }
;
desc:
| i = INT { Econst i }
| e1 = expression; PLUS; e2 = expression { Eplus (e1, e2) }
| ...
92
ocamllex + menhir
93
Compilation et dépendances
• Comme dans le cas d’ocamllex, il faut
s’assurer de l’application de menhir avant
le calcul des dépendances
• Le Makefile ressemble donc à ceci:
[Link]: [Link]
ocamllex [Link]
[Link] [Link]: [Link]
menhir -v [Link]
94
Compilation et dépendances(suite)
.depend: [Link] [Link] [Link]
ocamldep *.ml *.mli > .depend
include .depend
95
Récapitulation
• les grammaires non contextuelles sont à la
base de l’analyse syntaxique
• le travail est grandement automatisé par
des outils tels que menhir
• la détection et la résolution des ambiguïtés
est un point délicat
96
