“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 30 — #40
i
i
i
i
i
i
i
i
30
2
• La programmation déclarative
Comment lire les grammaires
Il faut commencer par un symbole non terminal comme int. Lire la règle correspondante de gauche à droite donne une séquence de jetons selon le schéma suivant :
– Chaque symbole terminal rencontré est ajouté à la séquence.
– Pour chaque symbole non terminal rencontré, lisez sa règle de grammaire et
remplacez le non terminal par la séquence de jetons qu’il définit.
– Chaque fois qu’il y a un choix (le symbole « | »), choisissez une des alternatives.
La grammaire peut être utilisée pour vérifier qu’une instruction est légale et pour
générer des instructions.
Les grammaires hors-contexte et sensibles au contexte
Tout ensemble de mots s’appelle un langage formel. Par exemple, l’ensemble de
toutes les instructions générées par une grammaire et un symbole non terminal font un
langage formel. Les techniques pour définir des grammaires peuvent être classifiées
selon leur expressivité, c’est-à-dire selon les caractéristiques des langages qu’elles
peuvent générer. Par exemple, le formalisme EBNF défini ci-dessus définit une classe
de grammaires que l’on appelle grammaires hors-contexte. Elles s’appellent ainsi
parce que l’expansion d’un non terminal, comme digit, donne toujours la même
séquence indépendamment de la position du non terminal dans une règle.
Pour la plupart des langages de programmation pratiques, il n’y a pas de grammaire
hors-contexte qui génère exactement l’ensemble des programmes légaux. Par exemple,
dans beaucoup de langages une variable doit être déclarée avant son utilisation. Cette
condition ne peut pas être exprimée dans une grammaire hors-contexte parce que
l’expansion du non terminal qui génère la variable dépend des variables déjà déclarées.
C’est une dépendance du contexte. Une grammaire qui contient un non terminal dont
l’utilisation dépend du contexte dans lequel il est utilisé s’appelle une grammaire
sensible au contexte.
La syntaxe de la plupart des langages de programmation pratiques est donc définie en deux parties (voir figure 2.2) : une grammaire hors-contexte et un ensemble
de conditions supplémentaires imposées par le langage. Nous gardons la grammaire
hors-contexte au lieu d’un formalisme plus expressif parce qu’elle est simple à lire et
à comprendre. Elle a une importante propriété de localité : un symbole non terminal
peut être compris en examinant seulement les règles qui le définissent ; les règles
(parfois beaucoup plus nombreuses) qui l’utilisent peuvent être ignorées. La grammaire hors-contexte est corrigée en imposant des conditions supplémentaires, comme
la restriction « déclaration avant utilisation » des variables. Avec ces conditions, la
grammaire devient sensible au contexte.
i
i
i
i
i
i
i
i
30
2
• La programmation déclarative
Comment lire les grammaires
Il faut commencer par un symbole non terminal comme int. Lire la règle correspondante de gauche à droite donne une séquence de jetons selon le schéma suivant :
– Chaque symbole terminal rencontré est ajouté à la séquence.
– Pour chaque symbole non terminal rencontré, lisez sa règle de grammaire et
remplacez le non terminal par la séquence de jetons qu’il définit.
– Chaque fois qu’il y a un choix (le symbole « | »), choisissez une des alternatives.
La grammaire peut être utilisée pour vérifier qu’une instruction est légale et pour
générer des instructions.
Les grammaires hors-contexte et sensibles au contexte
Tout ensemble de mots s’appelle un langage formel. Par exemple, l’ensemble de
toutes les instructions générées par une grammaire et un symbole non terminal font un
langage formel. Les techniques pour définir des grammaires peuvent être classifiées
selon leur expressivité, c’est-à-dire selon les caractéristiques des langages qu’elles
peuvent générer. Par exemple, le formalisme EBNF défini ci-dessus définit une classe
de grammaires que l’on appelle grammaires hors-contexte. Elles s’appellent ainsi
parce que l’expansion d’un non terminal, comme digit, donne toujours la même
séquence indépendamment de la position du non terminal dans une règle.
Pour la plupart des langages de programmation pratiques, il n’y a pas de grammaire
hors-contexte qui génère exactement l’ensemble des programmes légaux. Par exemple,
dans beaucoup de langages une variable doit être déclarée avant son utilisation. Cette
condition ne peut pas être exprimée dans une grammaire hors-contexte parce que
l’expansion du non terminal qui génère la variable dépend des variables déjà déclarées.
C’est une dépendance du contexte. Une grammaire qui contient un non terminal dont
l’utilisation dépend du contexte dans lequel il est utilisé s’appelle une grammaire
sensible au contexte.
La syntaxe de la plupart des langages de programmation pratiques est donc définie en deux parties (voir figure 2.2) : une grammaire hors-contexte et un ensemble
de conditions supplémentaires imposées par le langage. Nous gardons la grammaire
hors-contexte au lieu d’un formalisme plus expressif parce qu’elle est simple à lire et
à comprendre. Elle a une importante propriété de localité : un symbole non terminal
peut être compris en examinant seulement les règles qui le définissent ; les règles
(parfois beaucoup plus nombreuses) qui l’utilisent peuvent être ignorées. La grammaire hors-contexte est corrigée en imposant des conditions supplémentaires, comme
la restriction « déclaration avant utilisation » des variables. Avec ces conditions, la
grammaire devient sensible au contexte.