Arbres de syntaxe

Accéder aux arbres de syntaxe

Décomposition fonctionnelle : Limitations de Java

Syntaxe abstraite

Martin Odersky

20 et 27 novembre 2006
version 1.2

Syntaxe abstraite Martin Odersky 1 de 33

Arbres de syntaxe
Accéder aux arbres de syntaxe
Décomposition fonctionnelle : Limitations de Java

Plan du cours

1 Arbres de syntaxe
Actions sémantiques
Exemple : Analyseur d’expressions arithmétiques
Arbres de syntaxe

2 Accéder aux arbres de syntaxe

Décomposition orientée-objet
Décomposition fonctionnelle
Choisir le bon type de processeur

3 Décomposition fonctionnelle : Limitations de Java

Syntaxe abstraite Martin Odersky 2 de 33

 Arbres de syntaxe Actions sémantiques
Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Actions sémantiques

Un analyseur syntaxique fait généralement plus que simplement

reconnaı̂tre une syntaxe. Il peut :
évaluer du code (interpréteur) ;
émettre du code (compilateur simple passe) ;
construire une structure de données interne (compilateur
multi-passes).

De façon générale, un analyseur syntaxique réalise des actions

sémantiques :
analyseur à descente récursive : intégrées aux routines de
reconnaissance.
analyseur ascendant généré automatiquement : ajoutées à la
grammaire soumise au générateur d’analyseurs.

Syntaxe abstraite Martin Odersky 3 de 33

Arbres de syntaxe Actions sémantiques

Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Exemple : Analyseur d’expressions arithmétiques

Exemple : Les expressions arithmétiques (E.A.)

E = E "+" T | E "-" T | T.
T = T "*" F | T "/" F | F.
F = number | "(" E ")".
Que l’on peut transformer en LL(1) :
E = T { "+" T | "-" T }.
T = F { "*" F | "/" F }.
F = number | "(" E ")".

Syntaxe abstraite Martin Odersky 4 de 33

 Arbres de syntaxe Actions sémantiques
Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Exemple : Analyseur d’E.A. (action sémantique)

class Parser(in:InputStream) extends Scanner(in) {
import Tokens._
nextToken()
def expression: Unit = {
term
while (token == PLUS || token == MINUS ) { nextToken(); term }
}
def term: Unit = {
factor
while (token == MUL || token == DIV) { nextToken(); factor }
}
def factor: Unit = {
token match {
case LITERAL => nextToken()
case LPAREN =>
nextToken()
expression
if (token == RPAREN) nextToken() else error("’)’ expected")
case _ => error("illegal start of expression")
}
}

Syntaxe abstraite Martin Odersky 5 de 33

Arbres de syntaxe Actions sémantiques

Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Exemple : Analyseur d’E.A. (action sémantique : interprétation)

class Parser(in:InputStream) extends Scanner(in) {
import Tokens._
nextToken()
def expression: Int = {
var v: Int = term
while (token == PLUS || token == MINUS ) {
val operator = token; nextToken()
v = if (operator == PLUS) v + term else v - term
}
v
}
def term: Int = {
var v: Int = factor
while (token == MUL || token == DIV) {
val operator: Int = token; nextToken()
v = if (operator == MUL) v * factor else v / factor
}
v
}
def factor: Int = {
var v: Int = 0
token match {
case LITERAL => v = [Link](chars); nextToken()
case LPAREN => nextToken(); v = expression; accept(RPAREN)
case _ => error("illegal start of expression")
}
v
}}

Syntaxe abstraite Martin Odersky 6 de 33

 Arbres de syntaxe Actions sémantiques
Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Arbres de syntaxe

Dans un compilateur multi-passes, l’analyseur construit

explicitement un arbre de syntaxe.
Les phases suivantes du compilateur travaillent sur l’arbre de
syntaxe et non sur le source du programme.

Un arbre de syntaxe peut-être :

un arbre de syntaxe concrète s’il correspond directement à la
grammaire non-contextuelle.
un arbre de syntaxe abstraite s’il correspond à une grammaire
simplifiée.
Dans les compilateurs, on utilise généralement un arbre de syntaxe
abstraite.

Syntaxe abstraite Martin Odersky 7 de 33

Arbres de syntaxe Actions sémantiques

Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Arbres de syntaxe concrète

Exemple : Un arbre de syntaxe concrète pour une E.A.

T
En utilisant la grammaire non-contextuelle
des expressions arithmétiques définies T * F
précédemment, on obtient pour F number
l’expression 5 * 3 l’arbre de syntaxe number 3
concrète suivant :
5

Evidemment, un tel arbre contient une grande quantité

d’information redondante.

Syntaxe abstraite Martin Odersky 8 de 33

 Arbres de syntaxe Actions sémantiques
Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Il est possible de simplifier l’arbre pour omettre cette information

redondante :
La structure en arbre permet de se passer de l’analyse du
texte : les parenthèses ne sont pas nécessaires.
Exercice : Simplifier l’arbre de syntaxe concrète
Simplifiez A * (B + C).
Les symboles terminaux peuvent être implicites.

Simplifiez if (x == 0) y = 1 else y = 2.
etc.

Syntaxe abstraite Martin Odersky 9 de 33

Arbres de syntaxe Actions sémantiques

Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Grammaire abstraite
Ces simplifications vont amener à une nouvelle grammaire
non-contextuelle plus simple : la grammaire abstraite.
Exemple : Grammaire abstraite pour les E.A.
Expr = BinOp Expr Op Expr
| IntLit int.
Op = Add | Sub | Mul | Div.

Notez que pour une grammaire concrète donnée, il existe une

multitude de grammaires abstraites possibles.

Expr = AddOp Expr Expr | SubOp Expr Expr

| MulOp Expr Expr | DivOp Expr Expr
| IntLit int.

On choisit la grammaire abstraite la plus adaptée au compilateur.

Syntaxe abstraite Martin Odersky 10 de 33
 Arbres de syntaxe Actions sémantiques
Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Arbres de syntaxe abstraite

Les arbres de syntaxe abstraite (abstract syntax tree, AST)

constituent la structure de données centrale du compilateur.
On définit un type de noeud pour chaque alternative de chaque
production de la syntaxe abstraite que l’on représente par un
ensemble de classes :
Une classe pour chaque alternative.
Une super-classe abstraite commune : dans notre cas Expr.
Les sous-arbres comme variables d’instance des classes.
Un seul constructeur par classe.
En Scala, on utilise des classes case pour représenter les noeuds.

Syntaxe abstraite Martin Odersky 11 de 33

Arbres de syntaxe Actions sémantiques

Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Exemple : Déclaration de l’AST pour les E.A.

abstract class Expr {
var pos: Int
}

case class IntLit(value: Int)

extends Expr

case class BinOp(op: Int, left: Expr, right: Expr)

extends Expr

Syntaxe abstraite Martin Odersky 12 de 33

 Arbres de syntaxe Actions sémantiques
Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Exemple : Construction de l’AST pour les E.A.

class Parser(in:InputStream) extends Scanner(in) {
nextToken()
def expression: Expr = {
var t: Expr = term
while(token == PLUS || token == MINUS ) {
val startpos: int = pos; val operator: int = token
nextToken(); t = BinOp(operator, t, term)
}
t
}
def term: Expr = {
var t: Expr = factor
while (token == MUL || token == DIV) {
val startpos: int = pos; val operator: int = token
nextToken(); t = BinOp(operator, t, factor) setPos startPos
}
t
}
def factor: Expr = {
var t: Expr = _
token match {
case LITERAL => t = IntLit([Link](chars)) setPos pos; nextToken()
case LPAREN => nextToken(); t = expression; accept(RPAREN)
case _ => error("illegal start of expression")
}
t
}}

Syntaxe abstraite Martin Odersky 13 de 33

Arbres de syntaxe Actions sémantiques

Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

Traitement des positions

Il est important de stocker des positions dans l’AST pour

pouvoir localiser les fautes qui sont détectées dans l’analyse
des noms et types.
Pour ca, on stocke un champ pos dans chaque noeud.
Exemple :

abstract class Expr {

var pos: Int = [Link]
def setPos(p: Int): [Link] = { pos = p; this }
}

Syntaxe abstraite Martin Odersky 14 de 33

 Arbres de syntaxe Actions sémantiques
Accéder aux arbres de syntaxe Exemple : Analyseur d’expressions arithmétiques
Décomposition fonctionnelle : Limitations de Java Arbres de syntaxe

pos est commun à tous les types d’arbres ; c’est pourquoi il

est membre de la classe Tree.
pos ne fait pas partie du constructeur des classes, ceci afin de
ne pas ((polluer)) le filtrage de motif :
setPos doit être appelée juste après la construction de la
classe — c’est une sorte de post-constructeur.
setPos retourne this : il est ainsi possible de chaı̂ner l’appel
à setPos directement au constructeur :
val prog = Program(classes, main) setPos pos;

Syntaxe abstraite Martin Odersky 15 de 33

Arbres de syntaxe Décomposition orientée-objet

Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Accéder aux AST

Définition : Processeur
Conceptuellement, un processeur (processor) est une action en une
seule traversée de l’AST

Dans un compilateur, un processeur est par exemple :

une action qui donne à chaque noeud de l’arbre un type ;
une optimisation ;
la génération du code machine ;
etc.

Syntaxe abstraite Martin Odersky 16 de 33

 Arbres de syntaxe Décomposition orientée-objet
Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Il est important que les processeurs d’arbres puissent accéder à

l’AST de manière flexible.
Comment les processeurs accèdent-ils à l’arbre ?
Une solution inefficace est d’utiliser isInstanceOf pour trouver
le type du noeud syntaxique.
Exemple : Processeur grossier
if ([Link][NumLit])
[Link][NumLit].value

Une bonne solution est la décomposition orientée-objet.

Une meilleure solution est la décomposition fonctionnelle (les
((visiteurs))).

Syntaxe abstraite Martin Odersky 17 de 33

Arbres de syntaxe Décomposition orientée-objet

Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Nous allons maintenant présenter à la fois la décomposition

orientée-objet et fonctionnelle en utilisant l’exemple des expressions
arithmétiques.
On considère :
Deux types de noeuds : BinOp et IntLit.
Deux types d’actions : eval et toString.
La méthode s’applique de la même manière pour des langages
comme Zwei (25 noeuds et 2 processeurs) ou Scala (44 noeuds et
16 processeurs).

Syntaxe abstraite Martin Odersky 18 de 33

 Arbres de syntaxe Décomposition orientée-objet
Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Décomposition orientée-objet
Dans cette technique, chaque processeur d’arbre P est représenté
par une méthode virtuelle def P dans chaque classe d’arbre.
La méthode est abstraite dans la classe Expr et implémentée
dans chaque sous-classe.
Pour traiter une sous-expression e, il suffit d’appeler e.P, sa
méthode correspondant au processeur.

Exemple : Décomposition orientée-objet sur les E.A.

Pour implanter notre exemple :
on définit les méthodes eval et toString dans les classes
BinOp et IntLit ;
les méthodes eval et toString sont abstraites dans la classe
Expr, donc elles peuvent être invoquées sur chaque arbre ;
ce qu’elles font va dépendre du type concret de l’arbre.
Syntaxe abstraite Martin Odersky 19 de 33

Arbres de syntaxe Décomposition orientée-objet

Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

abstract class Expr {

var pos: Int
def setPos(p: Int): [Link] = { pos = p; this }
override def toString: String
def eval: Int
}
case class IntLit(value: int) extends Expr {
def toString: String = [Link]
def eval: Int = value
}
case class BinOp(op: int, left: Expr, right: Expr) extends Expr {
def toString: String =
"("+[Link]+[Link](op)+[Link]+")"
def eval: Int = {
val l: int = [Link]
val r: int = [Link]
op match {
case [Link] => l + r
case [Link] => l - r
case [Link] => l * r
case [Link] => l / r
case _ => throw new InternalError()
}}}

Syntaxe abstraite Martin Odersky 20 de 33

 Arbres de syntaxe Décomposition orientée-objet
Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Exemple : Décomposition OO sur les E.A. (classe pilote)

object Main {
def main(args: Array[String]): Unit = {
[Link]("> ")
val t: Expr = new Parser([Link]).expression
if (t != null) {
[Link]([Link] +
" evaluates to " +
[Link])
}
}
}

Syntaxe abstraite Martin Odersky 21 de 33

Arbres de syntaxe Décomposition orientée-objet

Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Décomposition fonctionnelle à filtrage de motifs

Avec cette technique, toutes les méthodes d’un traitement sont

regroupées dans un objet, le visiteur.
On utilise le filtrage de motifs pour déterminer quel type de
noeud est en train d’être traité.
Il est ainsi facile de partager du code et des données communes.

Exemple : Visiteur toString sur les E.A.

def toString(e: Expr): String = e match {
case IntLit(value) => [Link]
case BinOp(op, left, right) =>
"(" + toString(left) + [Link](op) +
toString(right) + ")"
}

Syntaxe abstraite Martin Odersky 22 de 33

 Arbres de syntaxe Décomposition orientée-objet
Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Exemple : Visiteur eval sur les E.A.

def eval(e: Expr): Int = {
e match {
case IntLit(value) =>
value
case BinOp(op, left, right) =>
val l: Int = eval(left)
val r: Int = eval(right)
op match {
case PLUS => l + r
case MINUS => l - r
case MUL => l * r
case DIV => l / r
case _ => error("malformed op")
}
}
}

Syntaxe abstraite Martin Odersky 23 de 33

Arbres de syntaxe Décomposition orientée-objet

Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Exemple : Décomposition fonctionnelle sur les E.A. (classe pilote)

def main(args: Array[String]): Unit = {
[Link]("> ")
val t: Expr = new Parser([Link]).expression
if (t != null) {
[Link](toString(t)+" evaluates to "+eval(t))
}
}

Syntaxe abstraite Martin Odersky 24 de 33

 Arbres de syntaxe Décomposition orientée-objet
Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Extensibilité

Avec un arbre de syntaxe abstraite, il peut y avoir extension dans

deux dimensions :
1 Ajouter un nouveau type de noeud, dans la décomposition :
orientée-objet ajouter une nouvelle sous-classe ;
fonctionnelle modifier chaque visiteur pour traiter le nouveau
type de noeud.
2 Ajouter un nouveau type de méthode de traitement, dans la
décomposition :
orientée-objet modifier chaque sous-classe pour y ajouter le
traitement ;
fonctionnelle ajouter un nouvel objet visiteur.

Syntaxe abstraite Martin Odersky 25 de 33

Arbres de syntaxe Décomposition orientée-objet

Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Choisir le bon type de processeur

Faciliter l’extensibilité
La décomposition OO facilite l’ajout de nouveaux types de
noeud.
Les visiteurs facilitent l’ajout de nouveaux traitements.
Faciliter la modularité
La décomposition OO permet le partage des données et du
code dans un noeud de l’arbre entre les phases.
Les visiteurs permettent le partage des données et du code
entre les méthodes d’un même traitement.

Syntaxe abstraite Martin Odersky 26 de 33

 Arbres de syntaxe Décomposition orientée-objet
Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Les arbres dans d’autres contextes

Les arbres avec plusieurs types de noeuds n’interviennent pas que

dans la compilation.
On les retrouve aussi :
dans la mise en page de texte ;
dans les documents structurés tels que HTML ou XML ;
dans les interfaces graphiques utilisateur (GUI) ;
etc.
Exercice : Composants d’une GUI
Dans une interface graphique utilisateur :
Quelle méthode d’accès à l’arbre est utilisée ?
Quel type d’extension est la plus commune ?

Syntaxe abstraite Martin Odersky 27 de 33

Arbres de syntaxe Décomposition orientée-objet

Accéder aux arbres de syntaxe Décomposition fonctionnelle
Décomposition fonctionnelle : Limitations de Java Choisir le bon type de processeur

Exemple : Extensibilité dans un compilateur et une GUI

Compilateur GUI
Vérification de typage Re-dessiner
Déplacer
Traduction PowerPC

Traduction x86 Activer

Optimisation
Scrollbar
IdExp
Menu
NumExp
PlusExp Canvas

MinusExp DialogBox
TimesExp
Text
SeqExp

Syntaxe abstraite Martin Odersky 28 de 33

 Arbres de syntaxe
Accéder aux arbres de syntaxe
Décomposition fonctionnelle : Limitations de Java

Le motif de conception ((visiteur))

Les langages ne supportant pas le filtrage de motif (comme Java)
rendent la décomposition fonctionnelle plus difficile.
Le motif de conception (design pattern) ((visiteur)) permet de
contourner cette difficulté :
Un objet visiteur contient pour chaque type K d’arbre une
méthode (appelée caseK) qui peut traiter les arbres de ce
type.
L’arbre contient uniquement une méthode de traitement
générique qui ne fait qu’appliquer un objet visiteur donné.

Référence : Motif de conception ((visiteur))

Design Patterns, Elements of Reusable OO Software, E. Gamma,
R. Helm, R. Johnson et J. Vlissides ; Addison-Wesley, 2000.

Syntaxe abstraite Martin Odersky 29 de 33

Arbres de syntaxe
Accéder aux arbres de syntaxe
Décomposition fonctionnelle : Limitations de Java

Exemple Java : Arbre visitable pour les E.A.

(Les constructeurs ont été omis)
public abstract class Expr {
int pos;
public abstract void apply(Visitor v);
static class IntLit extends Expr {
int value;
public void apply(Visitor v) { [Link](this); }
}
static class BinOp extends Expr {
int operator;
Expr left, right;
public void apply(Visitor v) { [Link](this); }
}
public interface Visitor {
public void caseIntLit(IntLit tree);
public void caseBinOp(BinOp tree);
}
}

Syntaxe abstraite Martin Odersky 30 de 33

 Arbres de syntaxe
Accéder aux arbres de syntaxe
Décomposition fonctionnelle : Limitations de Java

Exemple Java : Un visiteur ToString pour les E.A.

public class ToString implements [Link] {
String result;
public void caseIntLit(IntLit expr) {
result = [Link]([Link]);
}
public void caseBinOp(BinOp expr) {
result = "("
+ visit([Link])
+ [Link]([Link])
+ visit([Link]) + ")";
}
public static String visit(Expr tree) {
ToString v = new ToString();
[Link](v);
return [Link];
}
}

Syntaxe abstraite Martin Odersky 31 de 33

Arbres de syntaxe
Accéder aux arbres de syntaxe
Décomposition fonctionnelle : Limitations de Java

Exemple Java : Un visiteur Eval pour les E.A.

public class Eval implements [Link] {
int result;
public void caseIntLit(IntLit expr) {
result = [Link];
}
public void caseBinOp(BinOp expr) {
int l = visit([Link]);
int r = visit([Link]);
switch ([Link]) {
case [Link] : result = l + r; break;
case [Link]: result = l - r; break;
case [Link] : result = l * r; break;
case [Link] : result = l / r; break;
default: throw new InternalError();
}}
public static int visit(Expr tree) {
Eval v = new Eval();
[Link](v);
return [Link];
}
}

Syntaxe abstraite Martin Odersky 32 de 33

 Arbres de syntaxe
Accéder aux arbres de syntaxe
Décomposition fonctionnelle : Limitations de Java

Exemple Java : Décomposition par visiteur (classe pilote)

class Main {
public static void main(String[] args) {
[Link]("> ");
Expr t = new Parser([Link]).expression();
if (t != null) {
[Link]([Link](t) +
" evaluates to " +
[Link](t));
}
}
}

Syntaxe abstraite Martin Odersky 33 de 33