“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 31 — #41
i
i
i
i
i
i
i
i
2.1 Définir un langage de programmation pratique
31
− Il exprime les restrictions imposées par
Grammaire hors−contexte
Ensemble de conditions
supplémentaires
(par exemple, avec EBNF)
+
− La grammaire devient sensible au contexte
des variables avant leur utilisation)
le langage (par exemple, la déclaration
− Elle est facile à lire et comprendre
− Elle définit un sur−ensemble du langage
Figure 2.2 L’approche hors-contexte pour définir la syntaxe d’un langage.
L’ambiguïté
Les grammaires hors-contexte peuvent être ambiguës, c’est-à-dire qu’il y a plusieurs
arbres syntaxiques qui correspondent à la même séquence de jetons. En voici un
exemple. Une grammaire simple pour les expressions arithmétiques qui contiennent
l’addition et la multiplication :
exp : := int | |exp op exp
op
: := + | *
L’expression 2*3+4 correspond à deux arbres syntaxiques selon la manière de lire
les deux occurrences de exp. La figure 2.3 montre les deux arbres. Dans un arbre,
la première exp est 2 et la deuxième exp est 3+4. Dans l’autre arbre, elles sont
respectivement 2*3 et 4.
En principe l’ambiguïté est une propriété que l’on veut éviter, sinon on ne sait
pas exactement quel programme on écrit. Dans l’expression 2*3+4, les deux arbres
syntaxiques donnent des résultats différents quand l’expression est évaluée : un arbre
donne 14 (le résultat de 2*(3+4)) et l’autre donne 10 (le résultat de (2*3)+4). Parfois
les règles de grammaire peuvent être changées pour enlever l’ambiguïté, mais cela les
rend plus compliquées. Il est plus commode d’ajouter des conditions supplémentaires.
Ces conditions mettent des restrictions sur le parseur afin qu’il n’y ait qu’un seul arbre
syntaxique possible. Nous disons qu’elles lèvent l’ambiguïté de la grammaire.
L’approche habituelle pour les expressions avec des opérateurs binaires, comme les
expressions arithmétiques, est d’ajouter deux conditions, la précédence et l’associativité :
– La précédence est une condition sur une expression avec des opérateurs différents, comme 2*3+4. On donne a chaque opérateur un niveau de précédence.
Les opérateurs avec des précédences élevées sont placés plus profondément dans
l’arbre syntaxique, c’est-à-dire plus loin de la racine. Si * a une précédence plus
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
2.1 Définir un langage de programmation pratique
31
− Il exprime les restrictions imposées par
Grammaire hors−contexte
Ensemble de conditions
supplémentaires
(par exemple, avec EBNF)
+
− La grammaire devient sensible au contexte
des variables avant leur utilisation)
le langage (par exemple, la déclaration
− Elle est facile à lire et comprendre
− Elle définit un sur−ensemble du langage
Figure 2.2 L’approche hors-contexte pour définir la syntaxe d’un langage.
L’ambiguïté
Les grammaires hors-contexte peuvent être ambiguës, c’est-à-dire qu’il y a plusieurs
arbres syntaxiques qui correspondent à la même séquence de jetons. En voici un
exemple. Une grammaire simple pour les expressions arithmétiques qui contiennent
l’addition et la multiplication :
exp : := int | |exp op exp
op
: := + | *
L’expression 2*3+4 correspond à deux arbres syntaxiques selon la manière de lire
les deux occurrences de exp. La figure 2.3 montre les deux arbres. Dans un arbre,
la première exp est 2 et la deuxième exp est 3+4. Dans l’autre arbre, elles sont
respectivement 2*3 et 4.
En principe l’ambiguïté est une propriété que l’on veut éviter, sinon on ne sait
pas exactement quel programme on écrit. Dans l’expression 2*3+4, les deux arbres
syntaxiques donnent des résultats différents quand l’expression est évaluée : un arbre
donne 14 (le résultat de 2*(3+4)) et l’autre donne 10 (le résultat de (2*3)+4). Parfois
les règles de grammaire peuvent être changées pour enlever l’ambiguïté, mais cela les
rend plus compliquées. Il est plus commode d’ajouter des conditions supplémentaires.
Ces conditions mettent des restrictions sur le parseur afin qu’il n’y ait qu’un seul arbre
syntaxique possible. Nous disons qu’elles lèvent l’ambiguïté de la grammaire.
L’approche habituelle pour les expressions avec des opérateurs binaires, comme les
expressions arithmétiques, est d’ajouter deux conditions, la précédence et l’associativité :
– La précédence est une condition sur une expression avec des opérateurs différents, comme 2*3+4. On donne a chaque opérateur un niveau de précédence.
Les opérateurs avec des précédences élevées sont placés plus profondément dans
l’arbre syntaxique, c’est-à-dire plus loin de la racine. Si * a une précédence plus
© Dunod – La photocopie non autorisée est un délit