École Polytechnique

INF564 – Compilation

Jean-Christophe Filliâtre

analyse lexicale et syntaxique

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 1

 analyse syntaxique

l’objectif de l’analyse syntaxique est de reconnaı̂tre les phrases appartenant

à la syntaxe du langage

son entrée est la syntaxe concrète, c’est-à-dire une suite de caractères, et

sa sortie est la syntaxe abstraite

on découpe ce travail en deux étapes

• l’analyse lexicale, qui découpe le texte source en  mots  appelés
lexèmes (tokens)
• l’analyse syntaxique proprement dite, qui reconnaı̂t les suites de
mots légales

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 2

 exemple

source = suite de caractères ..

.
↓
fun x -> (* ma fonction *) analyse syntaxique
x+1 ↓

syntaxe abstraite
↓
analyse lexicale Fun
↓
"x" App
suite de lexèmes App Const

fun x -> x + 1 Op Var 1

.. + "x"
.

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 3

 analyse lexicale

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 4

 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é

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 5

 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)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 6

 les commentaires

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

note : les commentaires sont parfois exploités par certains outils (javadoc,
ocamldoc, etc.), qui les traitent alors différemment dans leur propre
analyse lexicale

val length : ’a list -> int

(** Return the length (number of elements) of ...

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 7

 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

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 8

 expressions régulières

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 9

 syntaxe

on se donne un alphabet A

r ::= ∅ langage vide

|  mot vide
| a caractère a ∈ A
| rr concaténation
| r |r alternative
| r? étoile

conventions : l’étoile a la priorité la plus forte, puis la concaténation, puis

enfin l’alternative

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 10

 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 ) = {w1 w2 | w1 ∈ L(r1 ) ∧ w2 ∈ L(r2 )}
L(r1 | r2 ) = L(r1 ) ∪ L(r2 )
L(r ?) = n≥0 L(r n ) où r 0 = , r n+1 = r r n
S

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 11

 exemples

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|)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 12

 constantes entières

constantes entières décimales, éventuellement précédées de zéros

(0|1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)?

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 13

 identificateurs

identificateurs composés de lettres, de chiffres et du souligné, et

commençant par une lettre

(a|b| . . . |z|A|B| . . . |Z ) (a|b| . . . |z|A|B| . . . |Z | |0|1| . . . |9)?

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 14

 constantes flottantes

constantes flottantes (3.14 2. 1e-12 6.02e23 etc.)

d d ? (.d ? | ( | .d?)(e|E ) (| + |−)d d?)

avec d = 0|1| . . . |9

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 15

 commentaires

les commentaires de la forme (* ... *), non imbriqués, peuvent

également être définis de cette manière

( * * ? r1 | r2 ? * * ? )

où r1 = tous les caractères sauf * et )

et r2 = tous les caractères sauf *

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 16

 commentaires imbriqués

les expressions régulières ne sont pas assez expressives pour définir les
commentaires imbriqués (le langage des mots bien parenthésés n’est pas
régulier)

on expliquera plus loin comment contourner ce problème

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 17

 automates finis

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 18

 automate fini

Définition
Un automate fini sur un alphabet A est un quadruplet (Q, T , I , F ) où
• Q est un ensemble fini d’états
• T ⊆ Q × A × Q un ensemble de transitions
• I ⊆ Q un ensemble d’états initiaux
• F ⊆ Q un ensemble d’états terminaux

exemple : Q = {0, 1}, T = {(0, a, 0), (0, b, 0), (0, a, 1)}, I = {0}, F = {1}
a
0 1

a, b

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 19

 langage

un mot a1 a2 . . . an ∈ A? est reconnu par un automate (Q, T , I , F ) ssi

a a a
s0 →1 s1 →2 s2 · · · sn−1 →n sn

avec s0 ∈ I , (si−1 , ai , si ) ∈ T pour tout i, et sn ∈ F

le langage défini par un automate est l’ensemble des mots reconnus

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 20

 résultat

Théorème (de Kleene)

Les expressions régulières et les automates finis définissent les mêmes
langages.

a
0 1
(a|b) ? a
a, b

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 21

 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
0..9
0 1

0..9

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 22

 identificateurs

expression régulière

(a|b| . . . |z|A|B| . . . |Z ) (a|b| . . . |z|A|B| . . . |Z | |0|1| . . . |9)?

automate
a..zA..Z
0 1

a..zA..Z 0..9

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 23

 constantes flottantes

expression régulière

d d ? (.d ? | ( | .d?)(e|E ) (| + |−)d d?)

où d = 0|1| . . . |9

automate
+,-
3 4

e,E 0..9
e,E 0..9

0..9 .
0 1 2 5

0..9 0..9 0..9

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 24

 commentaires

expression régulière


( * * ? r1 | r2 ? * * ? )

où r1 = tous les caractères sauf * et )

et r2 = tous les caractères sauf *

automate fini
*
( * )
0 1 2 3 4
r1
r2 *

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 25

 analyseur lexical

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 26

 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)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 27

 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é

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 28

 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

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 29

 en pratique

les lexèmes sont produits un par un, à la demande (de l’analyseur

syntaxique)

l’analyseur lexical mémorise donc la position où l’analyse de l’entrée devra

reprendre

0 n
input ...déjà analysé...
↑
current pos

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 30

 en pratique

lorsqu’un nouveau lexème est demandé, on démarre dans l’état initial de

l’automate, à partir de current pos

tant qu’une transition est possible, on l’emprunte, tout en mémorisant le

dernière lexème reconnu (dernier état final rencontré)

0 n
input ... dernier lexème reconnu
↑ ↑ ↑
current pos last pos
lorsqu’une transition n’est plus possible, de deux choses l’une :
• si un lexème a été reconnu, on le renvoie et current pos prend la
valeur de last
• sinon, c’est un échec de l’analyse lexicale

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 31

 construction de l’automate
on peut construire l’automate fini correspondant à une expression régulière
en passant par l’intermédiaire d’un automate non déterministe
(Thompson, 1968)

mais on peut aussi construire directement un automate déterministe

(Berry, Sethi, 1986) ; pour (a|b) ? a(a|b) on obtient

b
a
{a1 , a2 , b1 } {a1 , a2 , a3 , b1 , b2 }
a
b a
b
b
{a1 , a2 , b1 , #} {a1 , a2 , a3 , b1 , b2 , #}

voir le poly page 48

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 32
 outils

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 33

 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.

on présente ici jflex (pour Java) et ocamllex (pour OCaml)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 34

 exemple minimal

pour illustrer ces outils, écrivons un analyseur lexical minimal

pour un langage d’expressions arithmétiques avec
• des constantes entières
• des parenthèses
• une soustraction

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 35

 l’outil jflex

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 36

 syntaxe

un fichier jflex porte le suffixe .flex et a la forme suivante

... préambule ...
%{
... code Java arbitraire
%}
%%
<YYINITIAL> {
expression régulière { action }
...
expression régulière { action }
}
où chaque action est un code Java
(qui le plus souvent renvoie un lexème)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 37

 exemple 1/2
on écrit un fichier Lexer.flex pour nos expressions arithmétiques
import static sym.*; /* importe les lexèmes */

%%

%class Lexer /* notre classe s’appellera Lexer */

%unicode /* les caractères sont unicode */
%cup /* analyse syntaxique avec cup */
%line /* activer le décompte des lignes */
%column /* et celui des colonnes */
%yylexthrow Exception /* on peut lever Exception */

%{
/* pas besoin de préambule Java ici */
%}
...
Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 38
 exemple 2/2
...
WhiteSpace = [ \t\r\n]+ /* raccourcis */
Integer = [:digit:]+
%%
<YYINITIAL> {
"-" { return new Symbol(MINUS, yyline, yycolumn); }
"(" { return new Symbol(LPAR, yyline, yycolumn); }
")" { return new Symbol(RPAR, yyline, yycolumn); }
{Integer}
{ return new Symbol(INT, yyline, yycolumn,
Integer.parseInt(yytext())); }
{WhiteSpace}
{ /* ignore */ }
. { throw new Exception (String.format (
"Line %d, column %d: illegal character: ’%s’\n",
yyline, yycolumn, yytext())); }
}
Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 39
 explications

• la nature des lexèmes est libre ;

on utilise ici la classe Symbol qui vient avec cup (voir plus loin)

• MINUS, LPAR, RPAR et INT sont des entiers (la nature des lexèmes)
ici produits par l’outil cup et importés depuis sym.java

• les variables yyline et yycolumn sont mises à jour automatiquement

• yytext() renvoie la chaı̂ne reconnue par l’expression régulière

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 40

 compilation

on compile le fichier Lexer.flex avec jflex

jflex Lexer.flex

on obtient un fichier Lexer.java contenant notamment

• un constructeur
Lexer(java.io.Reader)
• une méthode
Symbol next_token()

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 41

 les expressions régulières de jflex

. n’importe quel caractère

a le caractère ’a’
"foobar" la chaı̂ne "foobar" (en particulier  = "")
[caractères] ensemble de caractères (par ex. [a-zA-Z])
[^caractères] complémentaire (par ex. [^"])
[:ident:] ensemble prédéfini de caractères (par ex. [:digit:])
{ident} expression régulière définie plus haut

r1 | r2 l’alternative
r1 r2 la concaténation
r * l’étoile
def
r + une ou plusieurs répétitions de r (= r r ?)
def
r ? une ou zéro occurrence de r (=  | r )
(r ) parenthésage

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 42

 l’outil ocamllex

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 43

 syntaxe

un fichier ocamllex porte le suffixe .mll et a la forme suivante

{
... code OCaml arbitraire ...
}
rule nom = parse
| expression régulière { action }
| expression régulière { action }
| ...
{
... code OCaml arbitraire ...
}
où chaque action est un code OCaml

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 44

 exemple
let white_space = [’ ’ ’\t’ ’\n’]+
let integer = [’0’-’9’]+
rule next_token = parse
| white_space
{ next_token lexbuf }
| integer as s
{ INT (int_of_string s) }
| ’-’
{ MINUS }
| ’(’
{ LPAR }
| ’)’
{ RPAR }
| eof
{ EOF }
| _ as c
{ failwith ("illegal character" ^ String.make 1 c) }
Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 45
 explications

• on suppose ici le type suivant pour les lexèmes

type token =
| INT of int
| MINUS
| LPAR
| RPAR
| EOF
il sera construit par l’analyseur syntaxique

• contrairement à jflex
• on rappelle explicitement next token quand on ignore les blancs
• on ne manipule pas explicitement les lignes et colonnes

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 46

 l’outil ocamllex

on compile le fichier lexer.mll avec ocamllex

ocamllex lexer.mll

ce qui produit un fichier OCaml lexer.ml qui définit une fonction

val next_token: Lexing.lexbuf -> token

(on construit son argument avec la fonction Lexing.from channel)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 47

 les expressions régulières d’ocamllex

n’importe quel caractère

’a’ le caractère ’a’
"foobar" la chaı̂ne "foobar" (en particulier  = "")
[caractères] ensemble de caractères (par ex. [’a’-’z’ ’A’-’Z’])
[^caractères] complémentaire (par ex. [^ ’"’])

ident expression régulière définie plus haut

r1 | r2 l’alternative
r1 r2 la concaténation
r * l’étoile
def
r + une ou plusieurs répétitions de r (= r r ?)
def
r ? une ou zéro occurrence de r (=  | r )
(r ) parenthésage

eof la fin de l’entrée

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 48

 documentation

pour plus de détails, voir les documentations de jflex et ocamllex,

accessibles depuis
• la page du cours
• le TD 3

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 49

 récapitulation

• les expressions régulières sont à la base de l’analyse lexicale

• le travail est grandement automatisé par des outils tels que jflex
ou ocamllex

• jflex/ocamllex est plus expressif que les expressions régulières car

on peut écrire du code arbitraire dans les actions et rappeler
l’analyseur lexical récursivement sur une condition
⇒ permet notamment de reconnaı̂tre des commentaires imbriqués

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 50

 analyse syntaxique

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 51

 objectif

suite de lexèmes
fun x -> ( x + 1 )

↓
analyse syntaxique
↓

syntaxe abstraite
Fun
"x" App
App Const
Op Var 1
+ "x"

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 52

 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

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 53

 quels outils

pour l’analyse syntaxique, on va utiliser

• une grammaire non contextuelle pour décrire la syntaxe
• un automate à pile pour la reconnaı̂tre

c’est l’analogue des expressions régulières / automates finis utilisés dans

l’analyse lexicale

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 54

 grammaire non contextuelle

Définition
Une grammaire non contextuelle (ou hors contexte) est un quadruplet
(N, T , S, R) où
• 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

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 55

 exemple : expressions arithmétiques

N = {E }, T = {+, *, (, ), int}, S = E ,
et R = { (E , E +E ), (E , E *E ), (E , (E )), (E , int) }

en pratique on note les règles sous la forme

E → E +E
| E *E
| (E )
| int

les terminaux de la grammaire seront les lexèmes produits par l’analyse

lexicale
int désigne ici le lexème correspondant à une constante entière
(i.e. sa nature, pas sa valeur)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 56

 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 = u1 Xu2

avec X ∈ N, X → β ∈ R et

v = u1 βu2

exemple :
E E |{z}
* (} |{z}
| {z ) → E *( E + E} )
| {z
u1 X u2 β

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 57

 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 à droite i.e.
u2 ∈ T ? )

on note →? la clôture réflexive transitive de →

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 58

 exemple

E → E * E
→ int *E
→ int *(E )
→ int *(E +E )
→ int * ( int + E )
→ int * ( int + int )

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 59

 langage

Définition
Le langage défini par une grammaire non contextuelle G = (N, T , S, R)
est l’ensemble des mots de T ? dérivés de l’axiome, i.e.

L(G ) = { w ∈ T ? | S →? w }

dans notre exemple

int * ( int + int ) ∈ L(G )

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 60

 arbre de dérivation

Définition
À 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

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 61

 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

E
E + E
int E * E
int int
mais la dérivation droite
E → E + E → E + E * E → E + E * int → E + int * int → int + int * int

également

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 62

 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
E E
E + E E * E
int E * E E + E int
int int int int

et notre grammaire est donc ambiguë

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 63

 grammaire non ambiguë

pour ce langage-là, il est néanmoins possible de proposer une autre

grammaire, non ambiguë, qui définit le même langage

E → E +T
| T
T → T *F
| F
F → (E )
| int

cette nouvelle grammaire traduit la priorité de la multiplication sur

l’addition, et le choix d’une associativité à gauche pour ces deux opérations

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 64

 grammaire non ambiguë
ainsi, le mot int + int * int * int n’a plus qu’un seul arbre de
dérivation, à savoir
E
E + T
T T * F

F T * F int
int F int
int
correspondant à la dérivation gauche

E → E + T → T + T → F + T → int + T → int + T * F
→ int + T * F * F → int + F * F * F → int + int * F * F
→ int + int * int * F → int + int * int * int

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 65

 résultat négatif

déterminer si une grammaire est ou non ambiguë n’est pas décidable

(rappel : décidable veut dire qu’on peut écrire un programme qui, pour
toute entrée, termine et répond oui ou non)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 66

 approche

on va utiliser des critères décidables suffisants pour garantir qu’une

grammaire est non ambiguë, et pour lesquels on sait en outre décider
l’appartenance au langage efficacement (avec un automate à pile
déterministe)

les classes de grammaires définies par ces critères s’appellent

LR(0), SLR(1), LALR(1), LR(1), LL(1), etc.

avant de commencer, on a besoin de quelques définitions...

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 67

 définitions

Définition (null)
Soit α ∈ (T ∪ N)? . null(α) est vrai si et seulement si on peut dériver  à
partir de α i.e. α →? .

Définition (first)
Soit α ∈ (T ∪ N)? . first(α) est l’ensemble de tous les premiers
terminaux des mots dérivés de α, i.e. {a ∈ T | ∃w . α →? aw }.

Définition (follow)
Soit X ∈ N. follow(X ) est l’ensemble de tous les terminaux qui peuvent
apparaı̂tre après X dans une dérivation, i.e. {a ∈ T | ∃u, w . S →? uXaw }.

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 68

 calcul de null, first et follow

pour calculer null(α) il suffit de déterminer null(X ) pour X ∈ N

null(X ) est vrai si et seulement si

• il existe une production X → ,
• ou il existe une production X → Y1 . . . Ym où null(Yi ) pour tout i

problème : il s’agit d’un ensemble d’équations mutuellement récursives

~ = (null(X1 ), . . . , null(Xn )),

dit autrement, si N = {X1 , . . . , Xn } et si V
on cherche la plus petite solution d’une équation de la forme
~ = F (V
V ~)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 69

 deux exemples de telles équations

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 70

 calcul de point fixe

Théorème (existence d’un plus petit point fixe (Tarski))

Soit A un ensemble fini muni d’une relation d’ordre ≤ et d’un plus petit
élément ε. Toute fonction f : A → A croissante, i.e. telle que
∀x, y . x ≤ y ⇒ f (x) ≤ f (y ), admet un plus petit point fixe.

preuve : comme ε est le plus petit élément, on a ε ≤ f (ε)

f étant croissante, on a donc f k (ε) ≤ f k+1 (ε) pour tout k
A étant fini, il existe donc un plus petit k0 tel que f k0 (ε) = f k0 +1 (ε)
a0 = f k0 (ε) est donc un point fixe de f
soit b un autre point fixe de f
on a ε ≤ b et donc f k (ε) ≤ f k (b) pour tout k
en particulier a0 = f k0 (ε) ≤ f k0 (b) = b
a0 est donc le plus petit point fixe de f 

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 71

 remarque

le théorème de Tarski donne des conditions suffisantes mais pas nécessaires

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 72

 calcul de null

dans le cas du calcul de null, on a

A = Bool × · · · × Bool avec Bool = {false, true}

on peut munir Bool de l’ordre false ≤ true et A de l’ordre point à point

(x1 , . . . , xn ) ≤ (y1 , . . . , yn ) si et seulement si ∀i. xi ≤ yi

le théorème s’applique alors en prenant

ε = (false, . . . , false)

car la fonction calculant null(X ) à partir des null(Xi ) est croissante

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 73

 calcul de null

pour calculer les null(Xi ), on part donc de

null(X1 ) = false, . . . , null(Xn ) = false

et on applique les équations jusqu’à obtention du point fixe i.e. jusqu’à ce

que la valeur des null(Xi ) ne soit plus modifiée

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 74

 exemple

E → T E0
E0 → + T E0
|  E E0 T T0 F
T → F T0 false false false false false
T0 → * F T0 false true false true false
|  false true false true false
F → (E )
| int

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 75

 justification

pourquoi cherche-t-on le plus petit point fixe ?

⇒ par récurrence sur le nombre d’étapes du calcul précédent,

on montre que si null(X ) = true alors X →? 

⇐ par récurrence sur le nombre d’étapes de la dérivation

X →? , on montre que null(X ) = true par le calcul
précédent

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 76

 calcul de first

de même, les équations définissant first sont mutuellement récursives

[
first(X ) = first(β)
X →β

et

first() = ∅
first(aβ) = {a}
first(X β) = first(X ), si ¬null(X )
first(X β) = first(X ) ∪ first(β), si null(X )

de même, on procède par calcul de point fixe sur le produit cartésien

A = P(T ) × · · · × P(T ) muni, point à point, de l’ordre ⊆ et avec
ε = (∅, . . . , ∅)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 77

 exemple

null
E E0 T T0 F
E → T E0 false true false true false
E0 → + T E0
| 
first
T → F T0
T0 → * F T0 E E0 T T0 F
|  ∅ ∅ ∅ ∅ ∅
F → (E ) ∅ {+} ∅ {*} {(, int}
| int ∅ {+} {(, int} {*} {(, int}
{(, int} {+} {(, int} {*} {(, int}
{(, int} {+} {(, int} {*} {(, int}

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 78

 calcul de follow

là encore, les équations définissant follow sont mutuellement récursives

[ [
follow(X ) = first(β) ∪ follow(Y )
Y →αX β Y →αX β, null(β)

on procède par calcul de point fixe, sur le même domaine que pour first

on introduit un symbole spécial # dans les suivants du symbole de départ

(ce que l’on peut faire directement, ou en ajoutant une règle S 0 → S#)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 79

 exemple
null
E E0 T T0 F
false true false true false

E → T E0 first
E0 → + T E0 E E0 T T0 F
|  {(, int} {+} {(, int} {*} {(, int}
T → F T0
T0 → * F T0 follow
|  E E0 T T0 F
F → (E ) {#} ∅ ∅ ∅ ∅
| int {#, )} {#} {+, #} ∅ {*}
{#, )} {#, )} {+, #, )} {+, #} {*, +, #}
{#, )} {#, )} {+, #, )} {+, #, )} {*, +, #, )}
{#, )} {#, )} {+, #, )} {+, #, )} {*, +, #, )}

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 80

 analyse ascendante

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 81

 idée générale

l’idée consiste à lire l’entrée de gauche à droite, en cherchant à reconnaı̂tre

des membres droits de productions pour construire l’arbre de dérivation de
bas en haut (bottom-up parsing )

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 82

 fonctionnement de l’analyse

l’analyse manipule une pile qui est un mot de (T ∪ N)?

à chaque instant, deux actions sont possibles

• opération de lecture (shift en anglais) : on lit un terminal de l’entrée
et on l’empile
• opération de réduction (reduce en anglais) : on reconnaı̂t en sommet
de pile le membre droit β d’une production X → β, et on remplace β
par X en sommet de pile

dans l’état initial, la pile est vide

lorsqu’il n’y a plus d’action possible, l’entrée est reconnue si elle a été
entièrement lue et si la pile est réduite à S

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 83

 exemple

pile entrée action

 int+int*int lecture
int +int*int réduction F → int
F +int*int réduction T →F
T +int*int réduction E →T
E → E +T E +int*int lecture
| T E+ int*int lecture
T → T *F E +int *int réduction F → int
| F E +F *int réduction T →F
F → (E ) E +T *int lecture
| int E +T * int lecture
E +T *int réduction F → int
E +T *F réduction T → T *F
E +T réduction E → E +T
E succès

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 84

 analyse LR (Knuth, 1965)

comment prendre la décision lecture / réduction ?

en se servant d’un automate fini et en examinant les k premiers caractères

de l’entrée ; c’est l’analyse LR(k)
(LR signifie  Left to right scanning, Rightmost derivation )

en pratique k = 1
i.e. on examine uniquement le premier caractère de l’entrée

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 85

 analyse LR
la pile est de la forme
s0 x1 s1 . . . xn sn
où si est un état de l’automate et xi ∈ T ∪ N comme auparavant

soit a le premier caractère de l’entrée ; on regarde la transition de

l’automate pour l’état sn et l’entrée a
• si c’est un succès ou un échec, on s’arrête
• si c’est une lecture, alors on empile a et l’état résultat de la transition
• si c’est une réduction X → α, avec α de longueur p, alors on doit
trouver α en sommet de pile
s0 x1 s1 . . . xn−p sn−p |α1 sn−p+1 . . . αp sn
on dépile alors α et on empile X s, où s est l’état résultat de la
X
transition sn−p → s, i.e.
s0 x1 s1 . . . xn−p sn−p X s
Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 86
 exemple

dans l’exemple plus haut, on s’est servi de cet automate

F

+ )
10 12

( E
5
F F
E → E +T (
E + (
1 2 3
| T T
8
T
(
T → T *F 4 *
F 11 int
9
| F
*
F → (E ) int int
6

| int
T 7

int

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 87

 construction de l’automate

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 88

 automate LR(0)

fixons pour l’instant k = 0

on commence par construire un automate asynchrone

c’est-à-dire contenant des transitions spontanées


appelées -transitions et notées s1 → s2

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 89

 automate LR(0)

les états sont des items de la forme

[X → α • β]

où X → αβ est une production de la grammaire ; l’intuition est

 je cherche à reconnaı̂tre X , j’ai déjà lu α et je dois encore lire β 

les transitions sont étiquetées par T ∪ N et sont les suivantes

a
[Y → α • aβ] → [Y → αa • β]
X
[Y → α • X β] → [Y → αX • β]

[Y → α • X β] → [X → •γ] pour toute production X → γ

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 90

 exemple

E
S → E• S → •E E → int•
     int
S → E 
E → •E +E E → •(E ) E → •int
(
E → E +E    
E 
| (E ) 
+
| int E → E • +E E → E+ • E E → ( • E)
E
E
)
E → E +E • E → (E )• E → (E • )

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 91

 automate LR(0) déterministe

déterminisons l’automate LR(0)

pour cela, on regroupe les états reliés par des -transitions

les états de l’automate déterministe sont donc des ensembles d’items,

tel que

E → E+ • E
E → •E +E
E → •(E )
E → •int

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 92

 automate LR(0) déterministe

chaque état s est saturé par la propriété

si Y → α • Xβ ∈ s
et si X → γ est une production
alors X → •γ ∈ s

l’état initial est celui contenant S → •E

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 93

 exemple

E
S → •E #
E → •E +E S →E •#
E → int•
E → •(E ) int E → E • +E
E → •int

int int +
S → E (
(
E → E +E E → ( • E) E → E+ • E
| (E ) E → •E +E E E → (E • ) + E → •E +E
E → •(E ) E → E • +E E → •(E )
| int
E → •int E → •int

) E +
(

E → E +E •
E → (E )•
E → E • +E

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 94

 représentation de l’automate

en pratique, on ne travaille pas directement sur l’automate mais sur deux

tables

• une table d’actions ayant pour lignes les états et pour colonnes les
terminaux ; la case action(s, a) indique
• shift s 0 pour une lecture et un nouvel état s 0
• reduce X → α pour une réduction
• un succès
• un échec

• une table de déplacements ayant pour lignes les états et pour

colonnes les non terminaux ; la case goto(s, X ) indique l’état résultat
d’une réduction de X

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 95

 construction de la table

on construit ainsi la table action

• action(s, #) = succès si [S → E • #] ∈ s
a 0
• action(s, a) = shift s 0 si on a une transition s → s
• action(s, a) = reduce X → β si [X → β•] ∈ s, pour tout a
• échec dans tous les autres cas

on construit ainsi la table goto

X 0
• goto(s, X ) = s 0 si et seulement si on a une transition s → s

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 96

 exemple

sur notre exemple, la table est la suivante :

action goto
état ( ) + int # E
1 shift 4 shift 2 3
2 reduce E → int
3 shift 6 succès
4 shift 4 shift 2 5
5 shift 7 shift 6
6 shift 4 shift 2 8
7 reduce E → (E )
8 shift 6
reduce E → E +E

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 97

 conflits

la table LR(0) peut contenir deux sortes de conflits

• un conflit lecture/réduction (shift/reduce), si dans un état s on
peut effectuer une lecture mais aussi une réduction
• un conflit réduction/réduction (reduce/reduce), si dans un état s
deux réductions différentes sont possibles

Définition (classe LR(0))

Une grammaire est dite LR(0) si la table ainsi construite ne contient pas
de conflit.

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 98

 conflit

on a un conflit lecture/réduction dans l’état 8

E → E +E •
E → E • +E

il illustre précisément l’ambiguı̈té de la grammaire sur un mot tel que

int+int+int

on peut résoudre le conflit de deux façons

• si on favorise la lecture, on traduira une associativité à droite
• si on favorise la réduction, on traduira une associativité à gauche

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 99

 exemple d’exécution

privilégions la réduction et illustrons sur un exemple

pile entrée action

( ) int #
+ E 1 int+int+int s2
1 int 2 +int+int E → int, g3
1 s4 s2 3
1E 3 +int+int s6
2 reduce E → int
1E 3 +6 int+int s2
3 s6 ok
1E 3 + 6 int 2 +int E → int, g8
4 s4 s2 5
1E 3 +6E8 +int E → E +E , g3
5 s7 s6
1E 3 +int s6
6 s4 s2 8
1E 3 +6 int s2
7 reduce E → (E )
1E 3 + 6 int 2 # E → int, g8
8 reduce E → E +E
1E 3 +6E 8 # E → E +E , g3
1E 3 # succès

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 100

 analyse SLR(1)

la construction LR(0) engendre très facilement des conflits

on va donc chercher à limiter les réductions

une idée très simple consiste à poser action(s, a) = reduce X → β si et

seulement si
[X → β•] ∈ s et a ∈ follow(X )

Définition (classe SLR(1))

Une grammaire est dite SLR(1) si la table ainsi construite ne contient pas
de conflit.
(SLR signifie Simple LR)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 101

 exemple

la grammaire
S → E#
E → E +T
| T
T → T *F
| F
F → (E )
| int
est SLR(1)

exercice : le vérifier (l’automate contient 12 états)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 102

 limites de l’analyse SLR(1)
en pratique, la classe SLR(1) reste trop restrictive
exemple :
S → E# =
E → G =D 1 ... ...
| D 2 shift 3 ...
G → *D reduce D → G
| id .. ..
3 . .
D → G

S → •E #
E → •G =D E → G= • D
E → •D G E → G • =D = D → •G
G → •*D D → G• G → •*D
G → •id G → •id
D → •G

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 103

 analyse LR(1)

on introduit une classe de grammaires encore plus large, LR(1), au prix de

tables encore plus grandes

dans l’analyse LR(1), les items ont maintenant la forme

[X → α • β, a]

dont la signification est :  je cherche à reconnaı̂tre X , j’ai déjà lu α et je

dois encore lire β puis vérifier que le caractère suivant est a 

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 104

 analyse LR(1)
les transitions de l’automate LR(1) non déterministe sont
a
[Y → α • aβ, b] → [Y → αa • β, b]
X
[Y → α • X β, b] → [Y → αX • β, b]

[Y → α • X β, b] → [X → •γ, c] pour tout c ∈ first(βb)

l’état initial est celui qui contient [S → •α, #]

comme précédemment, on peut déterminiser l’automate et construire la

table correspondante ; on introduit une action de réduction pour (s, a)
seulement lorsque s contient un item de la forme [X → α•, a]

Définition (classe LR(1))

Une grammaire est dite LR(1) si la table ainsi construite ne contient pas
de conflit.
Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 105
 exemple
S → E#
# =
E→ G =D
| D 1 ... ... ...
G → *D 2 reduce D → G shift 3 ...
.. .. ..
| id 3 . . .
D → G

S → •E #, #
E → •G =D, #
E → •D, # E → G = • D, #
D → •G , # G E → G • =D, # = D → •G , #
G → •*D, # D → G •, # G → •*D, #
G → •id, # G → •id, #
G → •*D, =
G → •id, =

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 106

 LALR(1)
la construction LR(1) pouvant être coûteuse, il existe des approximations

la classe LALR(1) (lookahead LR) est une telle approximation, utilisée

notamment dans les outils de la famille yacc

plus d’info : voir par exemple Compilateurs : principes techniques et outils

(dit  le dragon ) de A. Aho, R. Sethi, J. Ullman, section 4.7

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 107

 autre approche

on peut également procéder par analyse descendante = expansions

successives du non terminal le plus à gauche en partant de S, en se
servant d’une table d’expansions

ce sont les classes de grammaires LL(k) ; cf poly chapitre 4

les analyseurs LL(1) sont relativement simples à écrire

mais ils nécessitent d’écrire des grammaires peu naturelles

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 108

 hiérarchies

grammaires
langages
grammaires non contextuelles

grammaires non ambiguës

SLR(1) = LALR(1) = LR(1)
LR(1)
LL(1)
LL(1)
LALR(1)
LR(0)
SLR(1)

LR(0)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 109

 conclusion

l’analyse ascendante est puissante mais le calcul des tables est complexe

le travail est automatisé par de nombreux outils

c’est la grande famille de yacc, bison, ocamlyacc, cup, menhir, . . .

(YACC signifie Yet Another Compiler Compiler )

on présente ici cup (pour Java) et menhir (pour OCaml)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 110

 exemple

on poursuit l’exemple du langage d’expressions arithmétiques avec

• des constantes entières
• des parenthèses
• une soustraction

on suppose la syntaxe abstraite et l’analyseur lexical déjà réalisés

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 111

 l’outil CUP (Java)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 112

 syntaxe

dans un fichier Parser.cup, on commence par un entête où sont déclarés

les symboles terminaux et non terminaux
terminal Integer INT;
terminal LPAR, RPAR, MINUS;

non terminal Expr file;

non terminal Expr expr;
...

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 113

 syntaxe
on écrit ensuite les règles de grammaires et les actions
start with file;

file ::=
expr:e
{: RESULT = e; :}
;

expr ::=
INT:n
{: RESULT = new Ecst(n); :}
| expr:e1 MINUS expr:e2
{: RESULT = new Esub(e1, e2); :}
| LPAR expr:e RPAR
{: RESULT = e; :}
;
Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 114
 compilation

on compile le fichier Parser.cup avec

java -jar java-cup-11a.jar -parser Parser Parser.cup

ce qui provoque ici une erreur :

Warning : *** Shift/Reduce conflict found in state #6
between expr ::= expr MINUS expr (*)
and expr ::= expr (*) MINUS expr
under symbol MINUS
Resolved in favor of shifting.

Error : *** More conflicts encountered than expected

-- parser generation aborted

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 115

 résolution du conflit

on y remédie en déclarant MINUS comme étant associatif à gauche

precedence left MINUS;
(ce qui favorisera la réduction)

s’il y a plusieurs opérateurs, on les énumère par ordre de priorité croissante

precedence left PLUS, MINUS;
precedence left TIMES, DIV, MOD;

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 116

 compilation

maintenant la commande CUP termine avec succès et produit deux fichiers

Java :

• sym.java contient la déclaration de constantes pour les lexèmes

(INT, LPAR, RPAR, etc.)

• Parser.java contient l’analyseur syntaxique et fournit notamment

un constructeur
Parser(Scanner scanner)
et une méthode
Symbol parse()

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 117

 combinaison

on combine les classes produites par jflex et CUP de la façon suivante

Reader reader = new FileReader(file);
Lexer lexer = new Lexer(reader);
Parser parser = new Parser(lexer);
Expr e = (Expr)parser.parse().value;
try {
System.out.println(e.eval());
} catch (Error err) {
System.out.println("error: " + err.toString());
System.exit(1);
}

le programme doit utiliser la bibliothèque java-cup-11a-runtime.jar

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 118

 l’outil Menhir (OCaml)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 119

 syntaxe

dans un fichier parser.mly, on commence par un entête où sont déclarés

les symboles terminaux et non terminaux
%{
(* code OCaml arbitraire *)
%}

%token MINUS LPAR RPAR EOF

%token <int> INT

%start <expr> file

...
(à la différence de CUP, il faut déclarer EOF)

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 120

 syntaxe
on écrit ensuite les règles de grammaires et les actions
%%

file:
e = expr; EOF { e }
;

expr:
| e1 = expr; MINUS; e2 = expr { Sub (e1, e2) }
| LPAR; e = expr; RPAR { e }
| i = INT { Cte i }
;

%%
(à la différence de CUP, il faut ajouter EOF)
Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 121
 compilation

on compile le fichier arith.mly de la manière suivante

menhir -v arith.mly

ce qui provoque ici un avertissement

Warning: one state has shift/reduce conflicts.
Warning: one shift/reduce conflict was arbitrarily resolved.

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 122

 conflits

lorsque la grammaire n’est pas LR(1), Menhir présente les conflits à

l’utilisateur

• le fichier .automaton contient une description de l’automate LR(1) ;

les conflits y sont mentionnés

• le fichier .conflicts contient, le cas échéant, une explication de

chaque conflit, sous la forme d’une séquence de lexèmes conduisant à
deux arbres de dérivation

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 123

 résolution du conflit

on y remédie en déclarant MINUS comme étant associatif à gauche

%left MINUS
(ce qui favorisera la réduction)

s’il y a plusieurs opérateurs, on les énumère par ordre de priorité croissante

%left PLUS MINUS
%left TIMES DIV MOD

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 124

 compilation

maintenant la commande menhir termine avec succès et produit deux

fichiers OCaml arith.ml(i) qui contiennent notamment

• la déclaration d’un type token

type token = RPAR | MINUS | LPAR | INT of int | EOF

• une fonction
val file: (Lexing.lexbuf -> token) -> Lexing.lexbuf -> int

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 125

 combinaison

on combine ocamllex et menhir de la façon suivante

let c = open_in file in

let lb = Lexing.from_file c in
let e = Parser.file Lexer.next_token lb in
...

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 126

 la suite

• TD 3
• analyse syntaxique de
mini-Turtle

• lire les chapitres 3 et 4 du poly

• prochain cours jeudi 28

• typage
• TD : début du projet

Jean-Christophe Filliâtre INF564 – Compilation analyse lexicale et syntaxique 127