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 sept modes de dérivation (ORD, RND, LIN, SUB, SUB1, TEM, POSLONG) 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 sept 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.

Sous-grammaires et épuisement

Avant de parler des modes, un principe fondamental : une grammaire BP3 n’est pas un bloc monolithique — elle est découpée en sous-grammaires séparées par des lignes de tirets (-----).

 

gram#1[1] S --> A B C
gram#1[2] A --> dha dhin

-----

gram#2[1] B --> tirakita
gram#2[2] C --> dha ge

 

Le moteur BP3 dérive les sous-grammaires dans l’ordre, avec un principe d’épuisement : chaque bloc gram#N est dérivé jusqu’à ce que plus aucun non-terminal de ce bloc ne soit réécrivable dans le work string (la chaîne en cours de dérivation). Ce n’est qu’alors que le moteur passe au bloc suivant.

Concrètement :

  1. gram#1 s’applique d’abord — il réécrit S en A B C, puis A en dha dhin. Tant qu’il reste un non-terminal que gram#1 sait réécrire, on reste dans gram#1.
  2. Quand gram#1 est épuisé (plus rien à réécrire), on passe à gram#2 qui réécrit B et C.

Ce découpage est puissant : chaque sous-grammaire a son propre mode de dérivation. On peut avoir un gram#1 en mode ORD (déterministe) suivi d’un gram#2 en mode RND (aléatoire) — la première phase pose la structure, la seconde la remplit de variations.

 

ORD                          // gram#1 : structure déterministe
gram#1[1] S --> Phrase Phrase

-----

RND                          // gram#2 : contenu aléatoire
gram#2[1] Phrase --> dha dhin tirakita
gram#2[2] Phrase --> ta tin tirakita
gram#2[3] Phrase --> dha ge tirakita

 

En BPscript, le séparateur est ----- et le mode est déclaré par @mode:X (S5) :

 

@mode:ord
S -> Phrase Phrase

-----

@mode:random
Phrase -> dha dhin tirakita
Phrase -> ta tin tirakita
Phrase -> dha ge tirakita

 

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

BP3 ne se contente pas du non-déterminisme pur. Il propose sept modes qui définissent comment choisir parmi les règles alternatives au sein d’une sous-grammaire. 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].

 

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 :

 

RND
gram#1[1] S --> <3> A S
gram#1[2] S --> <1> x
gram#1[3] A --> <3> a b c
gram#1[4] A --> <2> a a b
gram#1[5] A --> <1> c - a

 

Calcul des probabilités :

Pour S : poids total = 3 + 1 = 4
  - P(règle 1) = 3/4 = 75% (continuer)
  - P(règle 2) = 1/4 = 25% (terminer avec x)

Pour A : poids total = 3 + 2 + 1 = 6
  - P(règle 3) = 3/6 = 50% (motif a b c — le plus fréquent)
  - P(règle 4) = 2/6 = 33% (motif a a b)
  - P(règle 5) = 1/6 = 17% (motif c - a — rare)

 

Trois exécutions possibles :

Exécution 1 : S → x                              → "x"
Exécution 2 : S → a b c S → a b c x              → "a b c x"
Exécution 3 : S → c - a S → c - a a a b S → ...  → "c - a a a b ..."

 

Résultat : Variable à chaque exécution. Les motifs pondérés plus lourd apparaissent plus souvent.

Usage : Improvisation, variation, exploration créative. Les poids modélisent la fréquence relative de chaque alternative.

Mode LIN : dérivation leftmost aléatoire

[!warning] Correction (mars 2026)

Cet article contenait initialement une description erronée du mode LIN comme « cyclique (wrap-around) ». C’est faux. La correction ci-dessous est basée sur la documentation officielle de BP3 [Bel, BP2 Grammars] et confirmée par Bernard Bel.

Principe : Parmi les règles candidates, on choisit aléatoirement une règle qui produit une dérivation leftmost (leftmost derivation — on réécrit le non-terminal le plus à gauche dans le work string). En mode analyse, c’est la dérivation rightmost qui est utilisée (rightmost derivation, context-sensitive).

C’est le pendant aléatoire de ORD : là où ORD prend la première règle candidate, LIN en choisit une au hasard parmi celles qui s’appliquent à la position la plus à gauche.

Exemple BP3 :

 

LIN
gram#1[1] S --> A B
gram#1[2] A --> a
gram#1[3] A --> c
gram#1[4] B --> b
gram#1[5] B --> d

 

Dérivation pas à pas :

S → A B                  (règle 1 — seule candidate pour S)

A est le non-terminal le plus à gauche.
Règles candidates pour A : règle 2 (A → a) et règle 3 (A → c)
Choix aléatoire → disons règle 3 :

A B → c B                (règle 3 — choisie aléatoirement)

B est maintenant le non-terminal le plus à gauche.
Règles candidates pour B : règle 4 (B → b) et règle 5 (B → d)
Choix aléatoire → disons règle 4 :

c B → c b                (règle 4 — choisie aléatoirement)

 

Résultat possible : c b (parmi 4 résultats possibles : a b, a d, c b, c d)

Différence avec RND : En mode RND, les règles sont choisies aléatoirement sans contrainte de position. En mode LIN, le choix aléatoire est contraint : on ne considère que les règles applicables à la position la plus à gauche. C’est un non-déterminisme plus discipliné — la dérivation progresse toujours de gauche à droite, mais avec de la variation à chaque position.

Usage : Quand on veut du non-déterminisme contrôlé : la structure progresse de gauche à droite (comme en lecture), mais le contenu varie à chaque exécution.

Mode SUB : substitution globale

Principe : Quand un non-terminal est développé, TOUTES ses occurrences dans le work string sont remplacées simultanément par le même développement. C’est un « Remplacer tout ».

[!warning] Correction (mars 2026)

La version initiale de cet article illustrait SUB avec un tihāī (cadence indienne). Cette analogie était musicologiquement incorrecte : le tihāī utilise des expressions parenthésées ((= A)(= Gap)(: A)(: Gap)(: A)) et des templates, pas le mode SUB simple. L’exemple a été remplacé par un alphabet neutre.

Exemple BP3 :

 

SUB
gram#1[1] S --> A - A - A
gram#1[2] A --> a b c
gram#1[3] A --> d e f

 

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 (A → a b c).
         TOUTES les occurrences de A sont remplacées SIMULTANÉMENT :

         A - A - A → a b c - a b c - a b c

 

Résultat : a b c - a b c - a b c — les trois A sont identiques.

En mode RND, chaque A serait développé indépendamment : le premier pourrait devenir a b c, le deuxième d e f, le troisième a b c. Le mode SUB garantit l’uniformité des substitutions.

Usage : Cohérence thématique (toutes les apparitions d’un motif sont identiques), canons stricts, p-substitutions (substitutions parallèles) pour les séquences automatiques infinies.

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. C’est un mode plus rapide que SUB, utilisable quand on sait que la première substitution produit directement des terminaux.

Exemple BP3 :

 

SUB1
gram#1[1] S --> A - A - A
gram#1[2] A --> a b
gram#1[3] A --> c d e
gram#1[4] A --> f g

 

Dérivation pas à pas :

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

Étape 2 : On remplace seulement le PREMIER A (le plus à gauche).
         Supposons règle 2 :
         → a b - A - A

Étape 3 : On remplace le prochain A (maintenant le plus à gauche).
         Supposons règle 3 :
         → a b - c d e - A

Étape 4 : Dernier A. Supposons règle 4 :
         → a b - c d e - f g

 

Résultat : a b - c d e - f g — chaque A est développé indépendamment, contrairement à SUB.

Différence cruciale avec SUB : En mode SUB, les trois A auraient été identiques. En mode SUB1, chaque A est développé séparément, permettant des variations — antécédent et conséquent différents, développement progressif.

Usage : Développement thématique (chaque occurrence évolue), structures asymétriques. Plus rapide que SUB car il ne cherche qu’une occurrence à chaque pas.

Mode TEM : templates structurels

Principe : Le mode TEM (Templates) génère un catalogue exhaustif de squelettes structurels — toutes les formes que la grammaire peut produire, sans les terminaux concrets. BP3 dérive exhaustivement les sous-grammaires marquées TEM et stocke les résultats comme gabarits réutilisables.

Le résultat est stocké dans une section TEMPLATES: du fichier grammaire :

 

TEMPLATES:
[1] *1/1 __*1/2 _
[5] *1/1 (@0 _)(@1 )

 

Chaque template est un squelette : les positions (_, __) indiquent où se placent les motifs, les groupes (@N ...) référencent les sous-grammaires dont le résultat est inséré. Les ratios (*1/1, *1/2) indiquent les rapports de vitesse.

Usage : En mode ANAL (reconnaissance, cf. B8), les templates pré-calculés permettent de tester rapidement si une séquence appartient au langage — on compare aux squelettes plutôt que de re-dériver. Si aucun template ne matche, la séquence est rejetée sans backtracking.

Mode POSLONG : position + longueur maximale

Principe : POSLONG (Position + Longest) est une variante de SUB1 avec un critère de désambiguïsation supplémentaire. Comme SUB1, il remplace une seule occurrence à la fois (la plus à gauche). Mais quand plusieurs règles sont candidates à la même position, POSLONG sélectionne celle qui produit la dérivation la plus longue.

L’algorithme, visible dans Compute.c:1375-1399, procède en trois étapes :

  1. Trouver la position minimale (leftmost) : parmi toutes les règles candidates, on retient celles qui matchent le plus à gauche
  2. Sélectionner la longueur maximale (longest) : parmi les candidates à la même position, on retient celle qui produit la dérivation la plus longue
  3. Appliquer : la règle sélectionnée remplace la première occurrence

C’est la stratégie leftmost-longest match — la même heuristique que les expressions régulières POSIX utilisent pour la correspondance de motifs.

Différence avec SUB1 :

Critère SUB1 POSLONG
Occurrences remplacées Une (la plus à gauche) Une (la plus à gauche)
Choix parmi les règles candidates Selon les poids (RND) ou l’ordre (ORD) La plus longue dérivation
Déterminisme Variable (selon le mode de choix) Oui (le critère de longueur tranche)

Restrictions : Les mêmes que SUB et SUB1 — pas de flags (/flags/), pas de _goto, pas de « Produce all items » (CompileGrammar.c:613-695, ProduceItems.c:757).

Usage : Utile quand la grammaire contient des règles de longueurs différentes et qu’on veut systématiquement le motif le plus développé — par exemple pour la translittération où le match le plus long est le plus spécifique.

Encart : Les sept 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 Variation positionnelle Chaque position reçoit un contenu aléatoire, mais la progression reste gauche→droite
SUB Substitution globale Toutes les occurrences d’un non-terminal remplacées simultanément
SUB1 Développement progressif Chaque occurrence d’un motif est développée indépendamment
TEM Squelettes structurels Catalogue exhaustif des formes possibles
POSLONG Translittération Match le plus long à la position la plus à gauche

>
Les cinq premiers modes émergent directement de l’observation de la musique réelle [Bel1998]. TEM et POSLONG sont des extensions pour des usages spécialisés — l’exploration structurelle et la correspondance de motifs déterministe.

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 (leftmost) Aléatoire parmi les leftmost Indépendantes Oui, leftmost
SUB Substitution Aléatoire ou séquentiel Toutes identiques Variable
SUB1 Substitution 1 Aléatoire ou séquentiel Une à la fois Variable
TEM Templates Exhaustif (toutes les dérivations) — Oui (exhaustif)
POSLONG Position + Longest Leftmost + longest match Une à la fois Oui

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 du non-déterminisme qui progresse de gauche à droite ? → 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
  • Vous voulez cataloguer toutes les formes structurelles possibles ? → TEM
  • Vous voulez le match le plus long à chaque position ? → POSLONG

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 :

TikZ diagram

Figure 1 — Arbre de syntaxe pour la derivation de aab (S \(\to\) A B, A \(\to\) a a, B \(\to\) b). Les non-terminaux sont en bleu, les terminaux en orange.

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 sept modes qui vont bien au-delà :

– ORD : ordre fixe des règles
– RND : choix aléatoire pondéré
– LIN : leftmost, choix al\’eatoire
– SUB : substitution globale (cohérence)
– SUB1 : substitution une occurrence à la fois
– TEM : dérivation exhaustive pour générer un catalogue de squelettes structurels (TEMPLATES:)
– POSLONG : comme SUB1, mais sélectionne la dérivation la plus longue (leftmost-longest match)

  • Le mode choisi transforme radicalement le comportement génératif de la même grammaire.
  • Modes vs directions : les sept modes ci-dessus définissent la stratégie de dérivation d’une sous-grammaire individuelle. BP3 possède aussi trois directions qui déterminent l’utilisation globale de la grammaire : PROD (production), ANAL (reconnaissance) et TEMP (templates). 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 (exploration structurelle exhaustive) de BP3. QAVAID (inférence de grammaires) était un programme Prolog II séparé, non intégré à BP3

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. Utilise des structures grammaticales complexes (sous-grammaires, templates), pas simplement le mode SUB1.
  • 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 — la règle candidate est choisie aléatoirement parmi celles qui produisent une dérivation leftmost (le non-terminal le plus à gauche est réécrit en premier).
  • Mode de dérivation : Dans BP3, stratégie de sous-grammaire pour choisir et appliquer les règles (ORD, RND, LIN, SUB, SUB1, TEM, POSLONG).
  • ORD (mode BP3) : Mode Ordered, où les règles sont appliquées dans l’ordre séquentiel du fichier.
  • POSLONG (mode BP3) : Mode Position + Longest, variante de SUB1 qui sélectionne la dérivation la plus longue parmi les règles candidates à la position la plus à gauche. Stratégie leftmost-longest match.
  • 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 des cadences indiennes.
  • 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.
  • TEM (mode BP3) : Mode Templates, qui dérive exhaustivement une sous-grammaire pour générer un catalogue de squelettes structurels (section TEMPLATES:).
  • Leftmost derivation : Stratégie de dérivation qui réécrit toujours le non-terminal le plus à gauche dans le work string. En mode LIN de BP3, le choix parmi les règles applicables à cette position est aléatoire.

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

← Retour à l’index