Deux résultats pour un seul calcul
Dans une agence de location, un script calcule des frais avec 2 * 3 + 4. Une collègue trouve 10. Un autre trouve 14.
Tous deux lisent les mêmes jetons, dans le même ordre. Ils ne les ont pas regroupés de la même façon. Un compilateur doit regrouper les jetons d’une seule façon, toujours la même. Cette façon s’écrit dans une grammaire.
À la fin de cette leçon
Remarque
Je peux construire un arbre syntaxique à partir de jetons.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Grammaire | les règles qui disent quels ordres de jetons sont permis | |
| Arbre syntaxique | un arbre qui montre comment les jetons se regroupent | |
| Analyseur syntaxique | la partie du compilateur qui construit l’arbre | |
| Priorité | quel opérateur se regroupe en premier | * avant + |
| Associativité | de quel côté on regroupe deux opérateurs de même priorité | à gauche |
| Descente récursive | un analyseur avec une fonction par règle |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une grammaire dit comment les jetons se regroupent
Une grammaire est une courte liste de règles. Chaque règle nomme une partie de phrase et dit de quoi elle est faite.
Les trois règles ci-dessous donnent à * et / une priorité plus forte qu’à + et -. Une expression est faite de termes, donc les produits sont regroupés d’abord. Les parenthèses repartent de la première règle : c’est ainsi qu’elles changent l’ordre.
Exemple travaillé : trois règles pour les calculs
| Règle | Elle est faite de | Exemple |
|---|---|---|
| expression | Un terme, puis + ou - et un autre terme, autant de fois que voulu | 2 * 3 + 4 |
| terme | Un facteur, puis * ou / et un autre facteur, autant de fois que voulu | 2 * 3 |
| facteur | Un nombre, ou une expression entre parenthèses | 4 ou (3 + 4) |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une fonction pour chaque règle
Un analyseur à descente récursive a une fonction par règle. expression appelle terme, qui appelle facteur. Une parenthèse fait rappeler expression par facteur : c’est la récursion.
À chaque tour de boucle, expression prend l’arbre déjà construit comme côté gauche. C’est ce qui fait pencher le - à gauche. La démo montre cette boucle seule, avec de simples nombres comme termes.
La boucle qui fait pencher à gauche
# Un analyseur pour des calculs comme 20 - 5 - 3 : des nombres reliés par + et -.
jetons = ["20", "-", "5", "-", "3"]
pos = 0
# Le premier nombre commence l'arbre.
arbre = int(jetons[pos])
pos = pos + 1
while pos < len(jetons):
signe = jetons[pos]
droite = int(jetons[pos + 1])
# L'arbre déjà construit devient le côté gauche : le - penche à gauche.
arbre = [signe, arbre, droite]
pos = pos + 2
print(arbre)
# Remplacez les jetons par ["1", "+", "2", "-", "3", "+", "4"], puis relancez.
bison construit l’analyseur à partir d’une grammaire
Un générateur d’analyseur syntaxique comme bison lit une grammaire et écrit l’analyseur en C. Dans calc.y, la règle expr a une ligne par opérateur. Seule, elle est ambiguë : 2 * 3 + 4 pourrait se regrouper des deux façons.
Deux lignes %left tranchent. Chacune dit que ses opérateurs penchent à gauche. La ligne écrite plus bas a la priorité la plus forte.
Aller dans le dossier du compilateur
cd ~/compilerAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Vérifier que la calculatrice est construite
makeAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Les deux lignes de priorité
grep -n "%left" calc.yAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le moins penche à gauche
echo "20 - 5 - 3" | ./calcAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
La division entière aussi
echo "64 / 4 / 2" | ./calcAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Les parenthèses changent l’arbre
echo "2 * (3 + 4)" | ./calcAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Deux nombres de suite
echo "5 5" | ./calcAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une parenthèse jamais fermée
echo "(1 + 2" | ./calcAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup de gens pensent qu’un analyseur calcule de gauche à droite, donc que 4 + 2 * 3 vaut 18. La grammaire construit l’arbre, et l’arbre fixe l’ordre du calcul. La priorité place 2 * 3 plus bas : il se calcule d’abord. Le sens de lecture ne départage que des opérateurs de même priorité.
Retirer la priorité
Le prochain Run copie calc.y sans ses deux lignes %left. bison lit ensuite cette copie.
Sans priorité, bison a souvent deux choix et aucune règle pour trancher. Il nomme chaque endroit de ce genre un conflit décalage/réduction. Le dernier Run lui demande un exemple du premier.
Copier la grammaire sans priorité
sed "/%left/d" calc.y > sansprio.yAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Demander à bison de la construire
bison sansprio.yAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Montrer un conflit
bison -Wcounterexamples sansprio.y 2>&1 | head -n 3Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Pour aller plus loin
Ajoutez une puissance ^ à votre analyseur. Elle lie plus fort que * et penche à droite : 2 ^ 3 ^ 2 veut dire 2 ^ (3 ^ 2).
Ajoutez une règle entre terme et facteur. Expliquez pourquoi une boucle comme celle d’expression donne ici le mauvais arbre, et ce qu’il faut écrire à la place.