B2) Alphabets, terminaux et non-terminaux

Le vocabulaire des grammaires

Quand on parle de « grammaire formelle », de quoi parle-t-on exactement ? Tout commence par trois ensembles fondamentaux.

Où se situe cet article ?

Cet article détaille le vocabulaire de base des grammaires hors contexte L2 appliqué à BP3. Quels sont les terminaux (notes, silences) et non-terminaux (structures) du I2 ? Comprendre ce vocabulaire est indispensable pour lire les B3.

Pourquoi c’est important ?

Avant d’écrire une seule règle de grammaire, il faut définir avec quoi on travaille. C’est comme un jeu de société : avant de jouer, on doit connaître les pièces disponibles et leurs rôles.

Dans une grammaire formelle, trois types d’objets interagissent :

Les symboles terminaux : les briques de base qui apparaissent dans le résultat final
Les symboles non-terminaux : les variables intermédiaires qui structurent la génération
L’alphabet : l’ensemble de tous les symboles disponibles

Comprendre cette distinction est essentiel pour lire, écrire et déboguer des grammaires. Sans elle, on confond les moyens (les non-terminaux) et les fins (les terminaux).

L’idée en une phrase

L’alphabet est l’ensemble des symboles de base ; les terminaux sont ce qu’on produit in fine ; les non-terminaux sont les étiquettes intermédiaires qu’on remplace jusqu’à obtenir uniquement des terminaux.

Expliquons pas à pas

Les symboles terminaux : le produit final

Les terminaux sont les symboles qui apparaissent dans la sortie finale de la grammaire. On ne peut plus les « réécrire » : ils sont là pour rester.

Exemples selon le domaine :

Domaine	Terminaux
Langue naturelle	les mots : « chat », « mange », « le »
Arithmétique	les chiffres et opérateurs : `0`, `1`, `+`, `*`, `(`, `)`
Programmation	les tokens : `if`, `while`, `=`, identifiants, nombres
Musique (occidental)	les notes et silences : `do`, `ré`, `mi`, `-`
Musique (tabla)	les bols (syllabes de percussion) : `dha`, `dhin`, `tin`, `ta`

Notation conventionnelle :

Lettres minuscules : a, b, c
Ou chaînes entre guillemets : "if", "while"
Ou symboles spéciaux : +, *, (

Les symboles non-terminaux : les variables de travail

Les non-terminaux sont des symboles intermédiaires. Ils représentent des « catégories » ou « concepts » qui seront éventuellement remplacés par des terminaux (ou d’autres non-terminaux, qui eux-mêmes seront remplacés).

Exemples :

Domaine	Non-terminaux
Langue naturelle	S (phrase), NP (groupe nominal), VP (groupe verbal)
Arithmétique	E (expression), T (terme), F (facteur)
Programmation	Statement, Expression, Block
Musique	Phrase, Motif, Cadence

Notation conventionnelle :

Lettres majuscules : S, A, B, NP
Ou mots entiers avec majuscule : Phrase, Expression
Dans BP3 : entre barres verticales |S|, |A|

L’alphabet : tout le vocabulaire disponible

L’alphabet est l’ensemble de tous les symboles que la grammaire peut manipuler.

Encart : Notations mathématiques

En théorie des langages formels, on utilise des notations mathématiques standard :

Σ (sigma majuscule) : désigne souvent l’alphabet des terminaux

V : désigne l’alphabet complet (terminaux + non-terminaux)

∪ (union) : l’opération qui combine deux ensembles. Si A = {1, 2} et B = {3, 4}, alors A ∪ B = {1, 2, 3, 4}

∩ (intersection) : les éléments communs à deux ensembles

∅ (ensemble vide) : l’ensemble qui ne contient aucun élément

Deux ensembles sont disjoints si leur intersection est vide : T ∩ N = ∅

L’alphabet complet V est l’union des terminaux (T) et non-terminaux (N) :

V = T ∪ N

Exemple concret:
- T = {a, b, c}           (les terminaux)
- N = {S, A, B}           (les non-terminaux)
- V = {a, b, c, S, A, B}  (l'alphabet complet)

Contrainte importante:
- T ∩ N = ∅ : aucun symbole n'est à la fois terminal ET non-terminal
- Cela permet de toujours savoir si un symbole doit encore être remplacé (non-terminal) ou s'il est final (terminal)

Exemple 1 : une grammaire arithmétique simple

Définissons une grammaire pour les expressions arithmétiques simples comme 2+3*4.

Terminaux (T) — les symboles qui apparaissent dans le résultat final :

T = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, *, (, ) }
    |___________________________|  |__|  |____|
          les chiffres          opérateurs parenthèses

Non-terminaux (N) — les catégories syntaxiques intermédiaires :

N = { E, T, F }

Signification:
- E = Expression (une expression complète, ex: "2+3*4")
- T = Terme (un produit, ex: "3*4")
- F = Facteur (un élément de base, ex: "4" ou "(2+3)")

Alphabet complet :

V = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, *, (, ), E, T, F }
    |_________________________________________| |_____|
                  terminaux                   non-terminaux

Règles :

E → E + T | T       # Une expression est soit E+T, soit juste T
T → T * F | F       # Un terme est soit T*F, soit juste F
F → ( E ) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9   # Un facteur est (E) ou un chiffre

Encart : Lire la notation |

La barre verticale | signifie « ou ». Ainsi E → E + T | T est un raccourci pour deux règles :

E → E + T

E → T

Dérivation de 2+3*4 :

E
→ E + T          (E → E + T)
→ T + T          (E → T)
→ F + T          (T → F)
→ 2 + T          (F → 2)
→ 2 + T * F      (T → T * F)
→ 2 + F * F      (T → F)
→ 2 + 3 * F      (F → 3)
→ 2 + 3 * 4      (F → 4)

Le résultat final 2+3*4 ne contient que des terminaux. Tous les non-terminaux (E, T, F) ont été remplacés.

Exemple 2 : la notation BP3

BP3 utilise une convention visuelle claire pour distinguer terminaux et non-terminaux.

Non-terminaux BP3 : entre barres verticales

|S|      -- symbole de départ
|A|      -- un non-terminal quelconque
|Phrase| -- nom descriptif

Terminaux BP3 :

Notes musicales : do4, ré4, C4, D#5
Bols de tabla : dha, dhin, tin, ta, tirakita (symboles définis dans le fichier d’alphabet)
Silences déterminés : - (durée fixe, une unité de temps)
Silences indéterminés : _ (durée non spécifiée, calculée par le contexte)
Ellipses : ... (silence prolongé de durée indéterminée, nœud UndeterminedRest)
Symboles définis dans l’alphabet externe (-al. fichier)

Encart : Trois types de silence en BP3

BP3 distingue trois façons de « ne rien jouer » :

Notation Type Durée Usage

- Rest déterminé Fixe (1 unité) Pause explicite entre les notes

_ Rest indéterminé Calculée Remplissage temporel flexible

... UndeterminedRest Indéfinie Silence prolongé, attente

>
Le silence déterminé (-) est le plus courant : il crée une pause d’une durée fixe, comme un soupir en notation musicale. Le silence indéterminé (_) laisse le système calculer la durée en fonction du contexte temporel (utile dans les expressions polymétriques). L’ellipse (...) représente un silence de durée véritablement indéterminée — pensez-y comme un fermata (point d’orgue) qui suspend le temps.

Notation	Type	Durée	Usage
`-`	Rest déterminé	Fixe (1 unité)	Pause explicite entre les notes
`_`	Rest indéterminé	Calculée	Remplissage temporel flexible
`...`	UndeterminedRest	Indéfinie	Silence prolongé, attente

Exemple de grammaire BP3 :

-gr.MiniMélodie

gram#1[1] |S| → |A| |B|
gram#1[2] |A| → do4 ré4 mi4
gram#1[3] |A| → mi4 ré4 do4
gram#1[4] |B| → - fa4 sol4

Identification :

Non-terminaux : |S|, |A|, |B|
Terminaux : do4, ré4, mi4, fa4, sol4, -

Une dérivation possible :

|S|
→ |A| |B|           (règle 1)
→ do4 ré4 mi4 |B|   (règle 2)
→ do4 ré4 mi4 - fa4 sol4   (règle 4)

Résultat : une séquence de six éléments, tous terminaux.

L’alphabet originel — un fichier de bols de tabla :

Historiquement, le premier alphabet de BP n’était pas do4, ré4, mi4 mais des syllabes de percussion indienne. Voici à quoi ressemble un fichier d’alphabet tabla (-al.Tabla) :

-al.Tabla
dha dhin tin ta tirakita ga ghe ki na tun ra

Chaque symbole est un bol — une frappe spécifique du tabla avec son timbre propre :

Bols résonants (frappés avec la paume sur le bāyāṅ, le fût grave) : dha, dhin, ghe, ga
Bols secs (frappés du bout des doigts sur le dāyāṅ, le fût aigu) : tin, ta, ki, na, tun, ra
Bols combinés (séquences rapides) : tirakita (= ti-ra-ki-ta, quatre frappes en accéléré)

Une grammaire de tabla utiliserait ces bols exactement comme notre grammaire mélodique utilise do4 et ré4 :

-gr.Tintal_Theka

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

Cette grammaire génère le theka (pattern de base) du tintāl, le cycle rythmique indien le plus courant (16 temps en 4 groupes de 4). Les non-terminaux |Vibhag1|…|Vibhag4| structurent les quatre sections du cycle ; les terminaux dha, dhin, tin, ta sont les bols joués.

Trois types de terminaux musicaux :

Système	Notation	Terminaux BP3	Exemple d’alphabet (`-al.*`)
Français	do, ré, mi, fa, sol, la, si	`do4`, `ré4`, `mi4`…	`-al.Mohanam` : `C4 D4 E4 G4 A4`
Anglo-saxon	C, D, E, F, G, A, B	`C4`, `D#5`, `Bb3`…	`-al.Jazz` : `C4 E4 G4 Bb4`
Indien (tabla)	dha, dhin, tin, ta…	`dha`, `dhin`, `tin`…	`-al.Tabla` : `dha dhin tin ta tirakita`
Indien (sargam)	Sa, Re, Ga, Ma, Pa, Dha, Ni	`Sa`, `Re`, `Ga`…	`-al.Raga` : `Sa Re Ga Ma Pa Dha Ni`

Les trois systèmes de notation sont strictement équivalents du point de vue formel : ce sont tous des alphabets finis de symboles terminaux. BP3 est cross-culturel par design — il a été conçu dès l’origine pour traiter aussi bien les bols du tabla que les notes occidentales [Bel1998].

La notation |x| pour la longueur

En théorie des langages formels, la notation |x| (avec un seul symbole minuscule) désigne la longueur d’une chaîne.

|abc| = 3      (trois symboles)
|ε| = 0        (ε = chaîne vide, zéro symbole)
|aabb| = 4

Attention à ne pas confondre avec BP3 !

|S| en BP3 = le non-terminal S
|w| en théorie = la longueur de la chaîne w

Le contexte permet généralement de lever l’ambiguïté.

Conventions de notation récapitulées

Encart : Les lettres grecques en théorie des langages

Les informaticiens théoriciens utilisent souvent des lettres grecques par convention :

ε (epsilon — chaîne vide) : la chaîne de longueur zéro (zéro caractère)

α, β, γ (alpha, bêta, gamma — chaînes quelconques) : des séquences mêlant terminaux et non-terminaux

Σ (sigma majuscule — alphabet terminal) : l’ensemble des symboles terminaux

λ (lambda — chaîne vide) : parfois utilisé comme alternative à ε

Élément	Notation standard	Notation BP3	Explication
Terminal	`a`, `b`, `+`, `"mot"`	`do4`, `-`, symboles d’alphabet	Les briques de base finales
Non-terminal	`S`, `A`, `NP`, `Expression`	\|S\|, \|A\|, \|Phrase\|	Les variables intermédiaires
Chaîne de terminaux	`w`, `x`, `y`	—	Une séquence de symboles finaux
Chaîne mixte	`α`, `β`, `γ`	—	Peut contenir terminaux ET non-terminaux
Chaîne vide	`ε` ou `λ`	`_epsilon()` ou `lambda`	La chaîne de longueur zéro
Longueur	\|w\|	—	Nombre de symboles dans w
Alphabet terminaux	`Σ` ou `T`	fichier `-al.*`	L’ensemble des terminaux
Alphabet non-terminaux	`N` ou `V_N`	symboles \|…\| dans les règles	L’ensemble des non-terminaux

Pourquoi la distinction est-elle importante ?

1. Pour savoir quand on a terminé

Une dérivation est complète quand il ne reste plus aucun non-terminal. Si vous avez encore un |A| dans votre sortie, ce n’est pas un résultat valide.

2. Pour définir le langage généré

Le langage d’une grammaire G est l’ensemble de toutes les chaînes de terminaux qu’on peut dériver depuis le symbole de départ.

Encart : Décoder la notation mathématique

La formule L(G) = { w dans T* | S =>* w } se lit :

L(G) : le langage (L) de la grammaire G

T* : l’ensemble de TOUTES les chaînes possibles formées avec des terminaux, y compris la chaîne vide. L’étoile (*) signifie « zéro ou plusieurs répétitions ».

Si T = {a, b}, alors T* = {ε, a, b, aa, ab, ba, bb, aaa, …}

S =>* w : S se dérive en w en zéro ou plusieurs étapes. Le * après => signifie « zéro ou plusieurs applications de règles ».

{ ... | ... } : notation ensembliste. { x | condition } signifie « l’ensemble de tous les x qui satisfont la condition ».

Donc en français : « L(G) est l’ensemble de toutes les chaînes w faites uniquement de terminaux, telles qu’on peut passer de S à w par des applications de règles. »

3. Pour implémenter un parseur

Un parseur (analyseur syntaxique) est un programme qui prend une chaîne de symboles en entrée et détermine sa structure grammaticale. Par exemple, un parseur pour les expressions arithmétiques prend « 2 + 3 * 4 » et construit un arbre montrant que la multiplication a priorité sur l’addition.

Un token est une unité lexicale de base reconnue par le parseur : un mot, un nombre, un opérateur, etc. Les tokens sont les terminaux de la grammaire.

Le parseur doit distinguer les tokens d’entrée (terminaux) des catégories syntaxiques qu’il construit (non-terminaux). Confondre les deux mène à des bugs subtils.

4. Pour BP3 : distinguer ce qui joue de ce qui structure

Dans BP3, les terminaux produisent du son (notes, silences). Les non-terminaux organisent la structure mais ne produisent rien directement. Cette distinction est fondamentale pour le transpileur (convertisseur de code source à source) BP2SC (B7) qui doit générer du code SuperCollider jouable.

Ce qu’il faut retenir

Les terminaux sont les symboles finaux qui apparaissent dans la sortie. En musique : les notes. En programmation : les tokens.
Les non-terminaux sont des variables intermédiaires qui structurent la génération. Ils sont tous remplacés avant la fin.
L’alphabet est l’ensemble de tous les symboles (terminaux + non-terminaux).
BP3 utilise la convention |symbole| pour les non-terminaux, ce qui les rend visuellement distincts.
La notation |x| en théorie formelle désigne la longueur, pas un non-terminal.

Pour aller plus loin

Livre de référence : Hopcroft, Motwani & Ullman, Introduction to Automata Theory, Languages, and Computation, chapitre 5
Documentation BP3 : Bol Processor – Pattern Grammars
Tutoriel interactif : CFG Developer
La genèse du Bol Processor : Kippen, J. & Bel, B. (1989), « The Identification and Modelling of a Percussion ‘Language' » — comment les bols sont devenus un alphabet formel
Le tabla de Lucknow : Kippen, J. (1988), The Tabla of Lucknow: A Cultural Analysis of a Musical Tradition, Cambridge University Press — le contexte ethnomusicologique dans lequel BP a été créé
Vue d’ensemble BP : Bel, B. (1998), « Migrating Musical Concepts — An Overview of the Bol Processor », Computer Music Journal 22(2) — multi-notation et migration cross-culturelle

Glossaire

Alphabet (V ou Σ) : Ensemble fini de symboles utilisables dans une grammaire. Σ désigne souvent les terminaux seuls, V l’ensemble complet.
Bol (बोल) : Syllabe mnémonique du tabla (ex : dha, dhin, tin, ta). Le « Bol » dans « Bol Processor ». Chaque bol correspond à une frappe spécifique produisant un timbre distinct.
Chaîne (ou mot) : Séquence finie de symboles. Exemple : « abc » est une chaîne de 3 symboles.
Chaîne vide (ε) : La chaîne de longueur zéro, ne contenant aucun symbole. Notée ε (epsilon) ou λ (lambda).
Dérivation : Séquence de remplacements de non-terminaux jusqu’à obtenir uniquement des terminaux.
Disjoint : Deux ensembles sont disjoints s’ils n’ont aucun élément en commun.
Étoile de Kleene () : Opération sur un ensemble qui produit toutes les chaînes possibles formées avec ses éléments, y compris la chaîne vide. Si T = {a}, alors T = {ε, a, aa, aaa, …}.
Langage : Ensemble de toutes les chaînes de terminaux dérivables depuis le symbole de départ.
Non-terminal : Symbole intermédiaire (variable) qui sera remplacé durant la dérivation. Par convention, en majuscules.
Parseur (analyseur syntaxique) : Programme qui analyse une chaîne pour en déterminer la structure grammaticale.
Rest déterminé : Silence de durée fixe, noté - en BP3. Correspond à une pause explicite d’une unité de temps.
Rest indéterminé : Silence de durée calculée par le contexte, noté _ en BP3. Utilisé dans les expressions polymétriques.
Silence prolongé (UndeterminedRest) : Silence de durée indéfinie, noté ... en BP3. Équivalent d’un point d’orgue (fermata).
Symbole de départ : Le non-terminal initial d’où commence toute dérivation (souvent S pour « Sentence » ou « Start »).
Theka : Pattern de base d’un tāla (cycle rythmique indien), joué par le tabla en ostinato. Le theka du tintāl, par exemple, est une séquence fixe de 16 bols.
Tāla : Cycle rythmique structurant la musique classique indienne (ex : tintāl = 16 temps, jhaptāl = 10 temps).
Terminal : Symbole qui apparaît dans la sortie finale et ne peut plus être réécrit. Par convention, en minuscules.
Token : Unité lexicale de base (mot, nombre, opérateur) reconnue par un parseur. Correspond aux terminaux de la grammaire.
Union (∪) : Opération ensembliste qui combine deux ensembles. A ∪ B contient tous les éléments de A et tous les éléments de B.
Vibhāg : Section d’un tāla. Le tintāl a 4 vibhāg de 4 temps chacun.

Prérequis : L2 (Grammaires context-free), I2 (Bol Processor)
Temps de lecture : 6 min
Tags : #grammaires #alphabets #terminaux #non-terminaux #BP3 #formalisme