Langages de programmation et compilation

Publié par

  • cours - matière potentielle : langages formels
  • cours - matière potentielle : langages formels
Ecole Normale Superieure Langages de programmation et compilation Jean-Christophe Filliatre Cours 5 / 3 novembre 2011 Jean-Christophe Filliatre Langages de programmation et compilation 2011–2012 / cours 5 1 / 90 Analyse lexicale Quandj'etaisenfant,onm'avaitditquelePereNoeldescendaitpar lacheminee,etquelesordinateursseprogrammaientenbinaire.J'ai apprisdepuisquelaprogrammationsefaisaitdepreference dansdeslangagesdehautniveau,plusabstraitsetplusexpressifs. Jean-Christophe Filliatre Langages de programmation et compilation 2011–2012 / cours 5 2 / 90 Analyse lexicale Quand j'etais enfant, on m'avait dit que le Pere Noel descendait par la cheminee, et que les ordinateurs se programmaient en binaire.
  • automate fini
  • langages de programmation
  • funx
  • let start
  • fun
  • analyse lexicale
  • pos
  • espace espace
  • espace en espace
  • constantes entieres constantes
  • app app
  • expression reguliere
  • lexemes
  • analyzer autom
  • fun des identificateurs
  • input
  • inputs
  • expression
  • expressions
  • mots
  • mot
Publié le : mardi 27 mars 2012
Lecture(s) : 30
Source : lri.fr
Nombre de pages : 23
Voir plus Voir moins

Analyse lexicale
´Ecole Normale Sup´erieure
Langages de programmation Quandj’´etaisenfant,onm’avaitditqueleP`ereNo¨eldescendaitpar
lachemin´ee,etquelesordinateursseprogrammaientenbinaire.J’aiet compilation
apprisdepuisquelaprogrammationsefaisaitdepr´ef´erence
dansdeslangagesdehautniveau,plusabstraitsetplusexpressifs.
Jean-Christophe Filliˆatre
Cours 5 / 3 novembre 2011
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 1 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 2 / 90
Analyse lexicale Analyse lexicale
Quand j’´etais enfant, on m’avait dit que le P`ere No¨el descendait par la
l’analyse lexicale est le d´ecoupage du texte source en mots
chemin´ee, et que les ordinateurs se programmaient en binaire. J’ai appris
depuis que la programmation se faisait de pr´ef´erence dans des langages de de mˆeme que dans les langues naturelles, ce d´ecoupage en mots facilite le
haut niveau, plus abstraits et plus expressifs. travail de la phase suivante, l’analyse syntaxique
introduction de la th`ese de X. Leroy ces mots sont appel´es des lex`emes (tokens)
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 3 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 4 / 90Analyse lexicale : exemple Les blancs
...source = suite de caract`eres
les blancs (espace, retour chariot, tabulation, etc.) jouent un rˆole dans↓
l’analyse lexicale ; ils permettent notamment de s´eparer deux lex`emesanalyse syntaxique
fun x → (* ma fonction *)
(semaine prochaine)
x+1 ainsi funx est compris comme un seul lex`eme (l’identificateur funx) et↓
fun x est compris comme deux lex`emes (le mot cl´e fun et
syntaxe abstraite↓ l’identificateur x)
analyse lexicale
Fun
↓ de nombreux blancs sont n´eanmoins inutiles (comme dans x + 1 )
"x" App et simplement ignor´es
suite de lex`emes
App Const
les blancs n’apparaissent pas dans le flot de lex`emes renvoy´e
fun x -> x + 1 Op Var 1
... + "x"
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 5 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 6 / 90
Les blancs Les commentaires
les commentaires jouent le rˆole de blancs
fun(* et hop *)x → x + (* j’ajoute un *) 1
les conventions diff`erent selon les langages,
et certains des caract`eres blancs peuvent ˆetre significatifs
ici le commentaire (* et hop *) joue le rˆole d’un blanc significatif
(s´epare deux lex`emes) et le commentaire (* j’ajoute un *) celui d’un
blanc inutile
exemples :
les tabulations pour make
note : les commentaires sont parfois exploit´es par certains outilsretours chariot et espaces de d´ebut de ligne en Python ou en Haskell
(ocamldoc, javadoc, etc.), qui les traitent alors diff´eremment dans leur(l’indentation d´etermine la structure des blocs)
propre analyse lexicale
val length : α list → int
(** Return the length (number of elements) of ...
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 7 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 8 / 90Quels outils Expressions r´eguli`eres : syntaxe et s´emantique
pour r´ealiser l’analyse lexicale, on va utiliser r ::= ∅ L(∅) =∅
| L() ={}des expressions r´eguli`eres pour d´ecrire les lex`emes
| a L(a) ={a}des automates finis pour les reconnaˆıtre
| r r L(r r ) ={w w | w ∈ L(r )∧ w ∈ L(r )}1 2 1 2 1 1 2 2
| r| r L(r | r ) = L(r )∪ L(r )1 2 1 2S
n 0 n+1 n| r? L(r?) = L(r ) ou` r = , r = r rn≥0on exploite notamment la capacit´e `a construire automatiquement un
automate fini d´eterministe reconnaissant le langage d´ecrit par une
expression r´eguli`ere (cf. cours langages formels)
conventions : l’´etoile a la priorit´e la plus forte, puis la concat´enation, puis
enfin l’alternative
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 9 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 10 / 90
Exemples Reconnaissance de lex`emes
expression
sur l’alphabet{a, b}
lex`eme r´eguli`ere automate
mots de trois lettres f u n
0 1 2 3(a|b)(a|b)(a|b) mot cl´e fun f u n
mots se terminant par un a
+
0 1(a|b)? a symbole + +
mots alternant a et b
- >(b|)(ab)? (a|) 0 1 2
symbole -> ->
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 11 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 12 / 90Constantes enti`eres Identificateurs
identificateurs compos´es de lettres, de chiffres et du soulign´e, et
constantes enti`eres d´ecimales, ´eventuellement pr´ec´ed´ees de z´eros
commen¸ cant par une lettre
expression r´eguli`ere
expression r´eguli`ere
(0|1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)?
(a|b|...|z|A|B|...|Z ) (a|b|...|z|A|B|...|Z||0|1|...|9)?
automate
automate
0..9
0 1 a..zA..Z
0 1
0..9
a..zA..Z 0..9
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 13 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 14 / 90
Constantes flottantes Commentaires
constantes flottantes de Caml
les commentaires de la forme (* ... *), mais non imbriqu´es, peuvent
´egalement ˆetre d´efinis de cette mani`ere
expression r´eguli`ere
expression r´eguli`ere
d d? (.d?| (|.d?)(e|E ) (| +|−)d d?)

( * * ? a| b ? * * ? )
ou` d = 0|1|...|9
ou` a = tous les caract`eres sauf * et )automate
et b = tous les caract`eres sauf *
+,-
3 4
automate fini
e,E 0..9e,E 0..9 *
( )*
0 1 2 3 4
0..9 . a0 1 2 5
b *
0..9 0..9 0..9
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 15 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 16 / 906
6
6
Commentaires imbriqu´es Analyseur lexical
un analyseur lexical est un automate fini pour la r´eunion de toutes les
expressions r´eguli`eres d´efinissant les lex`emes
les expressions r´eguli`eres ne sont pas assez expressives pour d´efinir les
commentaires imbriqu´es (le langage des mots bien parenth´es´es n’est pas
le fonctionnement de l’analyseur lexical, cependant, est plus complexe quer´egulier)
la simple reconnaissance d’un mot par un automate, car
on expliquera plus loin comment contourner ce probl`eme il faut d´ecomposer un mot (le source) en une suite de mots reconnus
il peut y avoir des ambigu¨ıt´es
il faut construire les lex`emes (les ´etats finaux contiennent des actions)
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 17 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 18 / 90
Ambigu¨ıt´es Analyseur lexical
exemple : le mot cl´e fun et les identificateursle mot funx est reconnu par l’expression r´eguli`ere des identificateurs,
mais contient un pr´efixe reconnu par une autre expression r´eguli`ere (fun)
f u n
0 1 2 3⇒ on fait le choix de reconnaˆıtre le lex`eme le plus long possible
=u
=n a..z=f
le mot fun est reconnu par l’expression r´eguli`ere du mot cl´e fun mais
4aussi par celle des identificateurs
a..z⇒ on classe les lex`emes par ordre de priorit´e
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 19 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 20 / 90Analyseur lexical Un peu de programmation
programmons un analyseur lexical
on introduit un type d’automates finis d´eterministes
type automaton = {l’analyseur lexical doit donc m´emoriser le dernier ´etat final rencontr´e, le
initial : int; (* etat´ = entier *)cas ´ech´eant
trans : int Cmap.t array; (* ´etat -> char -> etat´ *)
action : action array; (* ´etat -> action *)lorsqu’il n’y a plus de transition possible, de deux choses l’une :
}
aucune position finale n’a ´et´e m´emoris´ee⇒ ´echec de l’analyse lexicale
avec
on a lu le pr´efixe wv de l’entr´ee, avec w le lex`eme reconnu par le
type action =
dernier ´etat final rencontr´e⇒ on renvoie le lex`eme w, et l’analyse
| NoAction (* pas d’action = pas un ´etat final *)
red´emarre avec v pr´efix´e au reste de l’entr´ee
| Action of string (* nature du lex` eme *)
et
module Cmap = Map.Make(Char)
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 21 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 22 / 90
Un petit analyseur lexical Un petit analyseur lexical
l’objectif est d’´ecrire une fonction analyzer qui prend un automate et une
chaˆıne `a analyser, et renvoie une fonction de calcul du prochain lex`eme
la table de transitions est pleine pour les ´etats (tableau) et creuse pour les
caract`eres (AVL)
soit
on se donne
val analyzer :
automaton → string → (unit → string × string)let transition autom s c =
try Cmap.find c autom.trans.(s) with Not found → -1
note : on pourrait ´egalement renvoyer la liste des lex`emes, mais on adopte
ici la m´ethodologie qui est utilis´ee en pratique dans l’interaction entre
analyse lexicale et analyse syntaxique
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 23 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 24 / 90Un petit analyseur lexical Un petit analyseur lexical
utilisation : on m´emorise la position courante dans l’entr´ee `a l’aide d’une r´ef´erence
current pos
# let next token = analyzer autom "fun funx";;
# next token ();;
let analyzer autom input =
- : string * string = ("keyword", "fun") let n = String.length input in
let current pos = ref 0 in (* position courante *)
# next token ();; fun () →
...
- : string * string = ("space", " ")
0 n# next token ();;
input ...d´ej`a analys´e...
- : string * string = ("ident", "funx") ↑
current pos
# next token ();;
Exception: Failure "´echec". note : l’application partielle de analyzer est cruciale
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 25 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 26 / 90
Un petit analyseur lexical Un petit analyseur lexical
let analyzer autom input =
let n = String.length input in on d´etermine alors si une transition est possible
let current pos = ref 0 in
fun () →
let rec scan last state pos =
let rec scan last state pos =
let state’ =
(* on s’appr^ete a` examiner le caract` ere pos *)
if pos = n then -1
...
else transition autom state input.[pos]
in
in
scan None autom.initial !current pos
if state’ ≥ 0 then
(* une transition vers state’ *) ...
0 n else
input ... dernier lex`eme reconnu (* pas de transition possible *) ...
↑ ↑ ↑
current pos last pos
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 27 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 28 / 906
6
6
Un petit analyseur lexical Un petit analyseur lexical
si au contraire aucune transition n’est possible, on examine last pour
si oui, on met `a jour last, le cas ´ech´eant, et on appelle scan
d´eterminer le r´esultat
r´ecursivement sur state’
else match last with
if state’ ≥ 0 then
| None →
let last = match autom.action.(state’) with
failwith "´echec"
| NoAction → last
| Some (last pos, action) →
| Action a → Some (pos + 1, a)
let start = !current pos in
in
current pos := last pos;
scan last state’ (pos + 1)
action, String.sub input start (last pos - start)
0 n
last a la forme Some (p, a) ou`
input ... lex`eme reconnu
p est la position qui suit le lex`eme reconnu ↑ ↑ ↑
a est l’action (le type du lex`eme) current pos last pos pos
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 29 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 30 / 90
Un petit analyseur lexical Un petit analyseur lexical
testons avec
let autom = {un mot cl´e : fun
initial = 0;des identificateurs : (a..z)(a..z)?
trans = [| ... |];
des blancs : espace espace?
action = [|
(*0*) NoAction;
(*1*) Action "ident";f u n
0 1 2 3 (*2*)
(*3*) Action "keyword";
=uespace =n (*4*) "ident";a..z=f
(*5*) Action "space";
|]5 4
}
espace a..z
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 31 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 32 / 90Un petit analyseur lexical Autres possibilit´es
# let next token = analyzer autom "fun funx";;
# next token ();;
il y a bien surˆ d’autres possibilit´es pour programmer un analyseur lexical
- : string * string = ("keyword", "fun")
exemple : n fonctions mutuellement r´ecursives, une par ´etat de l’automate
# next token ();; let rec state0 pos = match input.[pos] with
| ’f’ → state1 (pos + 1)
- : string * string = ("space", " ") | ’a’..’e’ | ’g’..’z’ → state4 (pos + 1)
| ’ ’ → state5 (pos + 1)
# next token ();; | → failwith "´echec"
- : string * string = ("ident", "funx") and state1 pos = match input.[pos] with
| ...
# next token ();;
Exception: Failure "´echec".
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 33 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 34 / 90
Outils
en pratique, on dispose d’outils qui construisent les analyseurs lexicaux `a
construction de l’automatepartir de leur description par des expressions r´eguli`eres et des actions
c’est la grande famille de lex : lex, flex, jflex, ocamllex, etc.
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 35 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 36 / 90Algorithme de Thompson Construction directe
on peut construire l’automate fini correspondant `a une expression r´eguli`ere mais on peut aussi construire directement un automate d´eterministe
en passant l’interm´ediaire d’un automate non d´eterministe
id´ee de d´epart : on peut mettre en correspondance les lettres d’un mot
reconnu et celles apparaissant dans l’expression r´eguli`ere
R R1 2
exemple : le mot aabaab est reconnu par (a|b)? a(a|b), de la mani`ere
suivante
R1 a (a|b)? a(a|b)
R a (a|b)? a(a|b)
R b (a|b)? a(a|b)2
a (a|b)? a(a|b)
a (a|b)? a(a|b)
b (a|b)? a(a|b)on peut ensuite d´eterminiser, voire minimiser cet automate
cf. cours de langages formels
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 37 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 38 / 90
Construction directe Transitions
distinguons les diff´erentes lettres de l’expression r´eguli`ere :
pour construire les transitions de s `a s il faut d´eterminer les lettres qui1 2(a|b )? a (a|b )1 1 2 3 2
peuvent apparaˆıtre apr`es une autre dans un mot reconnu (follow)
on va construire un automate dont les ´etats sont des ensembles de lettres
exemple : toujours avec r = (a|b )? a (a|b ), on a1 1 2 3 2
l’´etat s reconnaˆıt les mots dont la premi`ere lettre appartient `a s
follow(a , r) ={a , a , b}1 1 2 1
exemple : l’´etat{a , a , b} reconnaˆıt les mots dont la premi`ere est soit un1 2 1
a correspondant `a a ou a , soit un b correspondant `a b1 2 1
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 39 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 40 / 90

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.