Grammaires formelles et dérivations

Pourquoi un tableur refuse une parenthèse oubliée

Une grammaire est un ensemble de règles qui décrit comment fabriquer tous les textes valides d’un langage. Elle permet de décider si un texte est correct, et de voir comment il est construit.

Un tableur accepte =(2+3)*4 mais refuse =(2+3*4. Une grammaire explique pourquoi : chaque parenthèse ouverte doit être fermée au même niveau. Vous allez lire des règles, dériver des textes avec elles, puis vérifier des parenthèses.

À la fin de cette leçon

Remarque

Je peux utiliser une grammaire pour décider si un texte est valide.

Mots-clés

Mot	Ce que ça veut dire	Exemple
Grammaire	un ensemble de règles qui décrit les textes valides
Règle	une ligne qui dit par quoi remplacer un symbole	P → ( P ) P
Symbole non terminal	un nom qui sera encore remplacé	P
Symbole terminal	un caractère qui reste dans le texte final	(
Dérivation	la suite de remplacements qui mène au texte
Symbole de départ	le symbole par lequel on commence

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Une grammaire remplace des symboles

Une grammaire part d’un symbole de départ et applique des règles. Chaque règle remplace un symbole non terminal par une suite de symboles.

Les symboles terminaux sont les caractères du texte final : ils ne sont plus remplacés. Voici la grammaire des parenthèses bien emboîtées. Son seul non terminal est P, et c’est aussi le symbole de départ.

Les deux règles des parenthèses

Règle	Se lit	Rôle
R1 : P → ( P ) P	P devient une parenthèse ouvrante, un P, une fermante, puis un autre P	Emboîte et enchaîne
R2 : P → vide	P disparaît	Arrête la dérivation

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Exemple travaillé : dériver (())

Étape	Texte obtenu	Règle appliquée
0	P	Départ
1	( P ) P	R1 sur P
2	( ( P ) P ) P	R1 sur le premier P
3	( ( ) P ) P	R2 sur le premier P
4	( ( ) ) P	R2 sur le premier P
5	( ( ) )	R2 sur le dernier P : fini

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Vérifier un texte : lire les règles à l’envers

Dériver fabrique un texte valide. Pour vérifier un texte donné, on fait l’inverse : on remplace une suite de symboles par le non terminal qui la produit.

Pour les parenthèses, la règle R1 lue à l’envers efface une paire collée (). Si le texte devient vide, il vient de la grammaire. S’il reste des symboles et aucune paire à effacer, il est incorrect.

Exemple travaillé : réduire ([]{}) puis ([)]

Texte	Paire collée effacée	Texte restant
([]{})	[]	({})
({})	{}	()
()	()	vide : texte valide
([)]	Aucune : [ et ) sont collés	([)] : texte incorrect

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Effacer les paires, étape par étape

Code: python

# On efface les paires "()" jusqu'à ce qu'il n'en reste plus.
texte = "(()())"
print(texte)
while "()" in texte:
    texte = texte.replace("()", "")
    print("->", texte)
if texte == "":
    print("texte équilibré")
else:
    print("texte incorrect")
# Remplacez le texte par "(()", puis relancez.

Une grammaire ambiguë donne deux arbres

Un même texte peut avoir deux arbres de dérivation. La grammaire est alors ambiguë.

Prenons 1+2*3 avec une grammaire d’expressions sans priorité. Un arbre regroupe 1+2 d’abord. L’autre regroupe 2*3 d’abord. Les deux textes sont valides, mais les résultats diffèrent.

Exemple travaillé : deux arbres pour 1+2*3

Arbre	Regroupement	Résultat
Arbre 1	(1+2)*3	9
Arbre 2	1+(2*3)	7

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Le fichier calc.y est une vraie grammaire

Le labo contient une grammaire écrite pour l’outil bison, dans ~/compiler/calc.y. Chaque règle commence par un nom suivi de deux-points. La barre | sépare les alternatives d’une même règle.

Entre l’arbre 1 et l’arbre 2, ce fichier choisit avec des lignes %left : la multiplication passe avant l’addition. Les premiers Runs lisent les règles. Les suivants construisent la calculatrice et lui envoient des parenthèses.