B3) Règles de dérivation

Comment une grammaire génère

Une grammaire, c’est un ensemble de règles. Mais comment ces règles s’appliquent-elles pour produire des résultats concrets ?

Où se situe cet article ?

Après avoir défini les B1 (probabilités) et le B2 (vocabulaire) de BP3, cet article détaille comment les règles s’appliquent. Les cinq modes de dérivation (ORD, RND, LIN, SUB, SUB1) sont formalisés en SOS (Structural Operational Semantics, sémantique opérationnelle structurelle) dans l’article L6.

Pourquoi c’est important ?

Avoir une grammaire ne suffit pas. Encore faut-il savoir comment l’utiliser. Une grammaire définit les règles du jeu, mais pas la stratégie pour jouer.

Prenons une analogie culinaire. Une recette vous dit que vous pouvez ajouter du sel « à volonté » et que vous pouvez cuire le plat « au four ou à la poêle ». Mais dans quel ordre faites-vous les choses ? Salez-vous avant ou après la cuisson ? Choisissez-vous d’abord le mode de cuisson ?

De même, une grammaire offre souvent plusieurs règles applicables simultanément. La stratégie de dérivation détermine laquelle appliquer en premier, et cette stratégie peut changer radicalement le comportement du système. BP3 va plus loin : il propose cinq modes de dérivation différents, chacun adapté à un style de génération.

L’idée en une phrase

Une dérivation est une séquence d’applications de règles de production qui transforme le symbole de départ en une chaîne de terminaux ; la stratégie (ordre, choix) détermine le résultat.

Expliquons pas à pas

Anatomie d’une règle de production

Une règle de production (ou règle de réécriture) a la forme :

 

A → α

 

Elle se lit : « Le symbole A peut être remplacé par la séquence α (alpha — une chaîne quelconque de symboles) ».

Encart : La règle de production comme instruction

Pensez à une règle de production comme une instruction de substitution dans un traitement de texte :

  • « Remplacer A par xyz »

Chaque fois que vous voyez A dans votre texte de travail, vous POUVEZ le remplacer par xyz. Vous n’êtes pas obligé (il peut y avoir d’autres règles pour A), mais c’est une option valide.

Composants :

  • A : le côté gauche, appelé LHS (Left-Hand Side, littéralement « côté main gauche »). C’est ce qu’on remplace. Dans une grammaire context-free (hors-contexte, cf. L2), c’est toujours UN SEUL non-terminal.
  • α : le côté droit, appelé RHS (Right-Hand Side, « côté main droite »). C’est par quoi on remplace. Peut être une séquence de terminaux et/ou non-terminaux, ou même la chaîne vide (ε).
  • → : la flèche de production, qui indique le sens du remplacement (de gauche vers droite)

Exemples :

S → A B           (S devient la séquence A puis B)
A → a A           (A devient 'a' suivi de A - récursion)
A → a             (A devient simplement 'a')
B → b             (B devient 'b')

 

La dérivation : de S à w

Une dérivation est une séquence de formes intermédiaires, chacune obtenue en appliquant une règle à la précédente. C’est le « chemin » qui mène du symbole de départ S à une chaîne finale w.

Notation :

Encart : Les flèches de dérivation

Symbole Nom Signification Exemple
=> dérivation simple exactement UNE étape S => A B
=>* dérivation étoile ZÉRO ou plusieurs étapes S =>* abc (S peut être abc, ou y arriver en plusieurs étapes, ou S = abc directement)
=>+ dérivation plus UNE ou plusieurs étapes S =>+ abc (au moins une règle a été appliquée)

>
L’étoile (*) et le plus (+) sont des conventions empruntées aux expressions régulières :

  • Étoile = « zéro ou plus »
  • Plus = « un ou plus »

Exemple complet :

Grammaire :

S → A B
A → a A | a
B → b B | b

 

Dérivation de aab :

S
=> A B        (S → A B)
=> a A B      (A → a A)
=> a a B      (A → a)
=> a a b      (B → b)

 

On écrit : S =>* aab

Exemple 1 : dérivation leftmost vs rightmost

Quand plusieurs non-terminaux sont présents dans la chaîne de travail, lequel remplacer en premier ? C’est une question de stratégie de dérivation.

Encart : Pourquoi la stratégie importe ?

Pour une grammaire non-ambiguë (où chaque chaîne n’admet qu’un seul arbre de dérivation), le RÉSULTAT final est le même quelle que soit la stratégie. Mais le CHEMIN (l’ordre des étapes) diffère. Cela importe pour :

  • Les parseurs (analyseurs syntaxiques) : un parseur LL (Left-to-right, Leftmost derivation) lit de gauche à droite et utilise la dérivation leftmost ; un parseur LR (Left-to-right, Rightmost derivation) utilise rightmost
  • Le débogage : suivre une dérivation étape par étape est plus facile avec une stratégie cohérente
  • Les grammaires ambiguës : différentes stratégies peuvent mener à différentes interprétations

Leftmost (dérivation gauche, ou leftmost derivation) :
On remplace TOUJOURS le non-terminal le plus à gauche en premier. C’est comme lire un livre : on traite d’abord ce qui vient en premier.

Rightmost (dérivation droite, ou rightmost derivation) :
On remplace TOUJOURS le non-terminal le plus à droite en premier. C’est comme défaire une pile : on traite d’abord ce qui est arrivé en dernier.

Grammaire d’exemple :

S → A B
A → a
B → b

 

Dérivation leftmost de ab :

S
=> A B        (S → A B, on a A et B, A est plus à gauche)
=> a B        (A → a, on remplace A)
=> a b        (B → b, on remplace B)

 

Dérivation rightmost de ab :

S
=> A B        (S → A B, on a A et B, B est plus à droite)
=> A b        (B → b, on remplace B d'abord)
=> a b        (A → a, on remplace A)

 

Résultat identique, chemin différent.

Pour les grammaires non ambiguës, leftmost et rightmost produisent le même résultat. La différence devient importante pour les parseurs et les grammaires ambiguës.

Exemple 2 : quand l’ordre change le résultat (grammaires non déterministes)

Avec des règles alternatives, le choix de la règle (pas seulement du symbole) affecte le résultat.

Grammaire :

S → A B
A → a | aa
B → b | bb

 

Dérivations possibles de S :

S => A B => a B => a b        → "ab"
S => A B => a B => a bb       → "abb"
S => A B => aa B => aa b      → "aab"
S => A B => aa B => aa bb     → "aabb"

 

Quatre résultats différents selon les choix. C’est le non-déterminisme des grammaires.

Les cinq modes de BP3 : stratégies de dérivation

BP3 ne se contente pas du non-déterminisme pur. Il propose cinq modes qui définissent comment choisir parmi les règles alternatives. Ces modes transforment la grammaire en différents types de générateurs.

Mode ORD : séquentiel strict

Principe : Les règles sont appliquées dans l’ordre où elles sont écrites dans le fichier de grammaire. Pour chaque non-terminal, on utilise sa première règle disponible, puis on passe à la suivante quand la première a été épuisée.

Exemple BP3 — un theka de tintāl :

Le theka est le pattern de base d’un tāla (cycle rythmique indien), joué en ostinato par le tabla. C’est l’exemple parfait du mode ORD : le theka est toujours le même, déterministe, joué identiquement à chaque cycle [BelKippen1992a].

 

-mo.ORD
gram#1[1] |S| → |Vibhag1| |Vibhag2| |Vibhag3| |Vibhag4|
gram#1[2] |Vibhag1| → dha dhin dhin dha
gram#1[3] |Vibhag2| → dha dhin dhin dha
gram#1[4] |Vibhag3| → dha tin tin ta
gram#1[5] |Vibhag4| → ta dhin dhin dha

 

Dérivation pas à pas :

Étape 1: |S|
         → |Vibhag1| |Vibhag2| |Vibhag3| |Vibhag4|      (règle 1)

Étape 2: |Vibhag1| → dha dhin dhin dha                  (règle 2)
Étape 3: |Vibhag2| → dha dhin dhin dha                  (règle 3)
Étape 4: |Vibhag3| → dha tin tin ta                     (règle 4)
Étape 5: |Vibhag4| → ta dhin dhin dha                   (règle 5)

 

Résultat : dha dhin dhin dha | dha dhin dhin dha | dha tin tin ta | ta dhin dhin dha

C’est le theka du tintāl — le cycle de 16 temps le plus courant en musique hindustanie. Toujours le même, 100% déterministe. Notez le contraste entre les sections thali (vibhāg 1-2, bols résonants dha/dhin) et la section khali (vibhāg 3, bols secs tin/ta).

Usage : Générer des séquences fixes : thekas, gammes, exercices techniques, tout pattern où la répétabilité est essentielle.

Mode RND : aléatoire pondéré

Principe : Parmi toutes les règles applicables pour un non-terminal, une est choisie aléatoirement selon les poids spécifiés. Le poids <N> indique l’importance relative de la règle.

Exemple BP3 — une improvisation de tabla :

En performance, le tabliste improvise autour du theka en choisissant parmi un répertoire de motifs (bols). Les motifs résonants (section thali) sont plus fréquents que les motifs secs (section khali) — exactement ce que les poids permettent de modéliser [BelKippen1992a].

 

-mo.RND
gram#1[1] |S| → <3> |Motif| |S|
gram#1[2] |S| → <1> |Sam|
gram#1[3] |Motif| → <3> dha tirakita dhin
gram#1[4] |Motif| → <2> dha dhin dhin dha
gram#1[5] |Motif| → <1> tin - ta

 

Calcul des probabilités :

Pour |S| : poids total = 3 + 1 = 4
  - P(règle 1) = 3/4 = 75% (continuer l'improvisation)
  - P(règle 2) = 1/4 = 25% (atterrir sur sam, le premier temps)

Pour |Motif| : poids total = 3 + 2 + 1 = 6
  - P(règle 3) = 3/6 = 50% (motif orné, le plus fréquent)
  - P(règle 4) = 2/6 = 33% (motif theka classique)
  - P(règle 5) = 1/6 = 17% (motif sec, rare — section khali)

 

Trois exécutions possibles :

Exécution 1: |S| → |Sam|                                    → "sam"
Exécution 2: |S| → dha tirakita dhin |S| → dha tirakita dhin |Sam|
Exécution 3: |S| → tin - ta |S| → tin - ta dha dhin dhin dha |S| → ...

 

Résultat : Variable à chaque exécution. Les motifs résonants (dha) dominent, les motifs secs (tin) sont rares — fidèle à la pratique réelle du tabla.

Usage : Improvisation, variation, exploration créative. Idéal pour modéliser la liberté contrôlée de l’improvisation indienne.

Mode LIN : linéaire cyclique

Principe : Comme ORD, les règles sont appliquées dans l’ordre. Mais quand on atteint la dernière règle, on revient à la première (comportement cyclique, appelé wrap-around en anglais — littéralement « enroulement »).

Exemple BP3 — un ostinato de tāla cyclique :

La musique indienne est fondamentalement cyclique : le tāla (cycle rythmique) tourne en boucle, revenant inlassablement au sam (premier temps). Le mode LIN est le mécanisme naturel pour encoder cette circularité.

 

-mo.LIN
gram#1[1] |S| → |Bol| |Bol| |Bol| |Bol| |Bol| |Bol| |Bol| sam
gram#1[2] |Bol| → dha
gram#1[3] |Bol| → dhin
gram#1[4] |Bol| → ta

 

Dérivation pas à pas :

|S| → |Bol| |Bol| |Bol| |Bol| |Bol| |Bol| |Bol| sam   (règle 1)

Développement cyclique de chaque |Bol| :
|Bol| #1 → dha   (règle 2)
|Bol| #2 → dhin  (règle 3)
|Bol| #3 → ta    (règle 4)
|Bol| #4 → dha   (retour à règle 2 -- wrap-around!)
|Bol| #5 → dhin  (règle 3)
|Bol| #6 → ta    (règle 4)
|Bol| #7 → dha   (retour à règle 2)

 

Résultat : dha dhin ta dha dhin ta dha sam

Le cycle de trois bols se répète indéfiniment : dha, dhin, ta, dha, dhin, ta… comme un tāla qui tourne jusqu’au retour sur sam.

Usage : Parfait pour les ostinatos (motifs répétés en boucle), les cycles de tāla, les patterns rythmiques circulaires. En musique indienne, tout accompagnement de tabla repose sur ce principe cyclique [Bel2001].

Mode SUB : substitution globale

Principe : Quand un non-terminal est développé, TOUTES ses occurrences dans la chaîne sont remplacées simultanément par le même développement. C’est une substitution « globale », comme un « Remplacer tout » dans un éditeur de texte.

Exemple BP3 — un tihāī (cadence indienne) :

Le tihāī est une cadence fondamentale de la musique indienne : un motif est répété exactement trois fois pour atterrir sur sam (le premier temps du cycle). Les trois répétitions doivent être identiques — c’est exactement ce que le mode SUB garantit [BelKippen1992a].

 

-mo.SUB
gram#1[1] |S| → |A| - |A| - |A|
gram#1[2] |A| → dha tirakita dhin dhin
gram#1[3] |A| → tin ta dha ghe

 

Dérivation pas à pas :

Étape 1: |S|
         → |A| - |A| - |A|      (règle 1)

Étape 2: On choisit comment développer |A|
         Supposons qu'on choisit la règle 2 (dha tirakita dhin dhin)
         TOUS les |A| deviennent dha tirakita dhin dhin SIMULTANÉMENT:

         |A| - |A| - |A|
         → dha tirakita dhin dhin - dha tirakita dhin dhin - dha tirakita dhin dhin

 

Résultat : dha tirakita dhin dhin - dha tirakita dhin dhin - dha tirakita dhin dhin (les trois |A| sont identiques)

C’est LA structure du tihāī : le même motif, trois fois, séparé par des silences calibrés pour que la troisième répétition tombe exactement sur sam. En mode RND, chaque |A| serait développé indépendamment, ce qui détruirait la structure du tihāī — les trois motifs pourraient différer.

Usage musical :

  • Tihāī : cadence indienne par excellence — 3× le même motif pour résoudre sur sam
  • Cohérence thématique : si |A| représente un thème, toutes ses apparitions sont identiques
  • Canons stricts : les voix jouent exactement le même motif

Mode SUB1 : substitution première occurrence

Principe : À chaque étape, seule la première occurrence (la plus à gauche) de chaque non-terminal est remplacée. Les autres occurrences du même symbole attendent leur tour.

Exemple BP3 — un kayda avec variations progressives :

Le kayda est une composition de tabla fondée sur un thème (mukhra) qui revient plusieurs fois avec des variations progressives. Contrairement au tihāī (mode SUB, où les répétitions sont identiques), le kayda développe chaque apparition du thème indépendamment — c’est exactement ce que fait SUB1 [BelKippen1992a].

 

-mo.SUB1
gram#1[1] |S| → |A| - |A| - |A|
gram#1[2] |A| → dha dhin dhin dha
gram#1[3] |A| → dha tirakita dhin dhin dha
gram#1[4] |A| → dha dhin tirakita dha tirakita dhin dha

 

Dérivation pas à pas :

Étape 1: |S|
         → |A| - |A| - |A|          (règle 1)

Étape 2: |A| - |A| - |A|
         On remplace seulement le PREMIER |A| (le plus à gauche)
         → dha dhin dhin dha - |A| - |A|     (premier |A| → règle 2, thème simple)

Étape 3: dha dhin dhin dha - |A| - |A|
         → dha dhin dhin dha - dha tirakita dhin dhin dha - |A|    (deuxième |A| → règle 3, orné)

Étape 4: → dha dhin dhin dha - dha tirakita dhin dhin dha - dha dhin tirakita dha tirakita dhin dha
         (troisième |A| → règle 4, très orné)

 

Résultat : Trois variations du thème, chacune plus développée que la précédente.

Différence cruciale avec SUB :
En mode SUB (tihāī), les trois |A| auraient été identiques. En mode SUB1 (kayda), chaque |A| est développé indépendamment, permettant un développement progressif — du simple au complexe, comme dans la pratique réelle du kayda.

Usage musical :

  • Kayda : thème et variations progressives du tabla — le cœur du répertoire de Lucknow
  • Développement progressif : chaque répétition d’un thème peut évoluer
  • Structures asymétriques : antécédent et conséquent différents

Encart : Les cinq modes et la pratique du tabla

Chaque mode de dérivation de BP3 correspond naturellement à un aspect de la performance de tabla, ce qui n’est pas un hasard : BP a été conçu pour modéliser exactement ces pratiques [BelKippen1992a] :

Mode Pratique du tabla Description
ORD Theka (ostinato) Le pattern de base du tāla, toujours identique, joué mécaniquement
RND Improvisation Le tabliste choisit parmi un répertoire de motifs, certains plus fréquents que d’autres
LIN Cycle de tāla Le cycle rythmique tourne indéfiniment, revenant au point de départ
SUB Tihāī (cadence) Un motif répété 3 fois à l’identique pour résoudre sur sam
SUB1 Kayda (thème & variations) Un thème qui revient avec des développements progressifs

>
Cette correspondance directe entre formalisme informatique et pratique musicale indienne montre que les modes de BP3 ne sont pas des abstractions arbitraires : ils émergent de l’observation de la musique réelle [Bel1998].

Tableau récapitulatif des modes

Mode Signification Choix des règles Occurrences multiples Déterminisme
ORD Ordered (ordonné) Séquentiel, dans l’ordre du fichier Indépendantes Oui, 100%
RND Random (aléatoire) Aléatoire selon les poids Indépendantes Non
LIN Linear (linéaire) Cyclique (retour au début) Indépendantes Oui, cyclique
SUB Substitution Aléatoire ou séquentiel Toutes identiques Variable
SUB1 Substitution 1 Aléatoire ou séquentiel Une à la fois Variable

Encart : Choisir le bon mode

  • Vous voulez une séquence fixe et reproductible ? → ORD
  • Vous voulez de la variété contrôlée ? → RND avec des poids ajustés
  • Vous voulez un pattern qui boucle ? → LIN
  • Vous voulez que les répétitions soient identiques ? → SUB
  • Vous voulez un développement progressif où chaque répétition peut évoluer ? → SUB1

Visualiser une dérivation : l’arbre de syntaxe

Une dérivation peut être représentée sous forme d’arbre de syntaxe (voir aussi L4) :

  • La racine est le symbole de départ
  • Chaque noeud non-terminal a pour enfants les symboles de son développement
  • Les feuilles sont les terminaux

Exemple :

Grammaire :

S → A B
A → a a
B → b

 

Arbre pour aab :

       S
      / \
     A   B
    / \   |
   a   a  b

 

Lecture des feuilles de gauche à droite : a a b

Les parseurs construisent ces arbres pour analyser du code ou du texte.

Ce qu’il faut retenir

  • Une règle de production A → α indique qu’on peut remplacer A par α.
  • Une dérivation est une séquence de remplacements depuis le symbole de départ jusqu’aux terminaux.
  • Leftmost et rightmost sont deux stratégies pour choisir quel non-terminal remplacer en premier.
  • BP3 propose cinq modes qui vont bien au-delà :

– ORD : ordre fixe des règles
– RND : choix aléatoire pondéré
– LIN : cycle à travers les règles
– SUB : substitution globale (cohérence)
– SUB1 : substitution une occurrence à la fois

  • Le mode choisi transforme radicalement le comportement génératif de la même grammaire.
  • Direction : les cinq modes ci-dessus sont des modes de production (génération). BP3 possède aussi deux autres directions : le mode ANAL (reconnaissance — la grammaire vérifie si une séquence appartient au langage) et le mode TEMP (gabarit — génération sous contraintes). Voir B8.

Pour aller plus loin

  • Livre de référence : Aho, Lam, Sethi & Ullman, Compilers: Principles, Techniques, and Tools (le « Dragon Book »), chapitre 4
  • Documentation BP3 : Bol Processor – Produce All Items
  • Modes BP3 : Bol Processor – Grammar Control
  • Visualisation : Syntax Tree Generator
  • Les modes dans leur contexte originel : Bel, B. & Kippen, J. (1992), « Modelling Music with Grammars: Formal Language Representation in the Bol Processor » — description des modes ORD, RND, SUB appliqués au tabla
  • Vue d’ensemble : Bel, B. (1998), « Migrating Musical Concepts — An Overview of the Bol Processor », Computer Music Journal 22(2)
  • Au-delà de la production : B8 — les modes ANAL (reconnaissance) et TEMP (gabarit) de BP3, et QAVAID pour l’inférence de grammaires

Glossaire

  • Arbre de syntaxe : Représentation arborescente d’une dérivation, avec le symbole de départ à la racine et les terminaux aux feuilles.
  • Kayda : Composition de tabla avec un thème fixe (mukhra) et des variations systématiques. Correspond au mode SUB1 de BP3.
  • Khali : Section « sans résonance » d’un cycle de tāla, où les bols secs (tin, ta) dominent.
  • Dérivation : Séquence d’applications de règles transformant le symbole de départ en chaîne de terminaux.
  • Leftmost (dérivation gauche) : Stratégie qui remplace toujours le non-terminal le plus à gauche.
  • LHS (Left-Hand Side) : Partie gauche d’une règle de production, c’est-à-dire le symbole qu’on remplace. En français : « côté gauche ».
  • LIN (mode BP3) : Mode Linear, où les règles sont appliquées cycliquement : après la dernière, on revient à la première.
  • Mode de dérivation : Dans BP3, stratégie globale pour choisir et appliquer les règles (ORD, RND, LIN, SUB, SUB1).
  • ORD (mode BP3) : Mode Ordered, où les règles sont appliquées dans l’ordre séquentiel du fichier.
  • Ostinato : Motif musical court répété obstinément tout au long d’un passage ou d’une pièce.
  • Sam : Premier temps du cycle de tāla — le point de résolution vers lequel convergent les tihāī et les cadences.
  • Theka : Pattern de base d’un tāla, joué par le tabla en ostinato. Correspond au mode ORD de BP3.
  • Tihāī : Cadence indienne où un motif est répété exactement trois fois pour atterrir sur sam. Correspond au mode SUB de BP3.
  • Tintāl : Le tāla le plus courant en musique hindustanie : 16 temps en 4 vibhāg de 4 temps.
  • Vibhāg : Section d’un tāla (ex : le tintāl a 4 vibhāg).
  • RHS (Right-Hand Side) : Partie droite d’une règle de production, c’est-à-dire ce par quoi on remplace. En français : « côté droit ».
  • Rightmost (dérivation droite) : Stratégie qui remplace toujours le non-terminal le plus à droite.
  • RND (mode BP3) : Mode Random, où les règles sont choisies aléatoirement selon leurs poids.
  • Règle de production : Instruction de la forme A → α indiquant qu’on peut réécrire A en α.
  • SUB (mode BP3) : Mode Substitution, où toutes les occurrences d’un même non-terminal sont remplacées identiquement.
  • SUB1 (mode BP3) : Mode Substitution 1, où seule la première occurrence d’un non-terminal est remplacée à chaque étape.
  • Wrap-around : Comportement cyclique où, après avoir atteint la fin d’une séquence, on revient au début.

Prérequis : B1 (PCFG), B2 (Alphabets), L6 (SOS)
Temps de lecture : 8 min
Tags : #dérivation #grammaires #BP3 #modes #génération #parsing