L0) La carte des formalismes

Comment les outils de la théorie des langages s’emboîtent

 

La série L, c’est douze articles sur les langages formels. Douze îles dans un archipel. Chaque île est un formalisme — un outil mathématique pour penser les langages. Certains décrivent la syntaxe (qu’est-ce qui est valide ?), d’autres la sémantique (qu’est-ce que ça veut dire ?), d’autres encore la traduction ou la concurrence. Entre les îles, des ponts : chaque formalisme s’appuie sur les précédents, les étend, les complète. Cet article est la carte — à lire avant le voyage.

Pourquoi une carte ?

Un compositeur qui écrit pour Bol Processor manipule une grammaire : des règles qui génèrent de la musique. Mais derrière cette grammaire se cachent des dizaines de concepts formels — la hiérarchie de Chomsky, les arbres de syntaxe abstraite (AST, Abstract Syntax Trees), la sémantique opérationnelle, les langages mildly context-sensitive…

La série L les explore un par un. Mais sans vue d’ensemble, on risque de se perdre. Quel article lire en premier ? Pourquoi faut-il comprendre les grammaires context-free avant la sémantique ? Pourquoi la polymétrie exige-t-elle des modèles de concurrence ?

Cette carte répond à ces questions. Elle montre les quatre étages de la série — et surtout, elle montre pourquoi BP3 a besoin de chacun d’entre eux.

La vue d’ensemble : quatre étages

 

flowchart TD
    subgraph E1["🧩 Étage 1 — SYNTAXE"]
        direction LR
        L1["L1
Hiérarchie de
Chomsky"]
        L2["L2
Grammaires
context-free"]
        L3["L3
EBNF"]
        L4["L4
AST"]
        L1 --> L2 --> L3 --> L4
    end

    subgraph E2["🔍 Étage 2 — SÉMANTIQUE"]
        direction LR
        L5["L5
Trois
sémantiques"]
        L6["L6
SOS"]
        L7["L7
Dénotationnelle"]
        L8["L8
Axiomatique"]
        L5 --> L6
        L5 --> L7
        L5 --> L8
    end

    subgraph E3["🚀 Étage 3 — EXTENSIONS"]
        direction LR
        L9["L9
MCSL"]
        L10["L10
Grammaires
d'attributs"]
    end

    subgraph E4["🔄 Étage 4 — TRADUCTION & CONCURRENCE"]
        direction LR
        _sp[" "]:::spacer
        classDef spacer fill:transparent,stroke:transparent,color:transparent;
        L11["L11
Sémantiques
avancées"]
        L12["L12
Petri / CCS"]
    end

    E1 --> E2
    E1 --> E3
    E2 --> E4
    E3 --> E4

 

Chaque étage pose une question fondamentale :

Étage Question Articles
1 — Syntaxe « Qu’est-ce qui est valide ? » L1, L2, L3, L4
2 — Sémantique « Qu’est-ce que ça veut dire ? » L5, L6, L7, L8
3 — Extensions « Comment aller au-delà ? » L9, L10
4 — Traduction & Concurrence « Comment traduire et paralléliser ? » L11, L12

Étage 1 — La syntaxe : qu’est-ce qui est valide ?

La première question à poser devant un langage — qu’il soit de programmation, musical ou naturel — c’est : quelles séquences de symboles sont valides ? Les quatre premiers articles construisent les outils pour y répondre.

L1 — La hiérarchie de Chomsky pose le cadre fondamental. Noam Chomsky a classé tous les langages possibles en quatre types, du plus simple (Type 3, les langages réguliers — pensez aux expressions régulières) au plus complexe (Type 0, les langages récursivement énumérables — aussi puissants qu’une machine de Turing). À chaque type correspond une machine capable de le reconnaître : automate fini, automate à pile, automate linéairement borné, machine de Turing. C’est le cadastre des langages.

L2 — Les grammaires context-free zoome sur le Type 2, le cœur de presque tout. Les grammaires context-free (CFG, Context-Free Grammars) permettent l’imbrication : des parenthèses dans des parenthèses, des structures dans des structures. C’est ce qui permet à BP3 d’imbriquer des sous-grammaires dans des grammaires, et ce qui rend la musique plus qu’une simple séquence plate de notes.

L3 — EBNF fournit la notation pour écrire ces grammaires. EBNF (Extended Backus-Naur Form) est à la grammaire ce que la notation musicale est à la musique : un langage pour écrire un langage. C’est en EBNF qu’on écrit la spécification formelle de BP3.

L4 — Les arbres de syntaxe abstraite montre ce qui reste après le parsing. Quand un parser (analyseur syntaxique) lit un texte BP3, il produit un AST — un arbre qui capture la structure sans le bruit syntaxique. C’est cet arbre que le transpileur BP2SC va parcourir pour produire du code SuperCollider.

Application à la musique

La hiérarchie de Chomsky éclaire directement les limites de chaque format musical :

  • MIDI est essentiellement un langage de Type 3 (régulier) — une séquence d’événements sans imbrication. C’est ce qui le rend simple mais expressif seulement pour des séquences plates.
  • MusicXML est un langage de Type 2 — son schéma XSD décrit une structure arborescente imbriquée. C’est ce qui lui permet de représenter la notation musicale avec ses mesures, voix, et dynamiques.
  • BP3 est un langage de Type 2+ — context-free dans sa base, mais avec des mécanismes (flags, variables) qui le poussent au-delà.

 

flowchart LR
    T["Texte BP3"] -->|"Grammaire
(EBNF)"| P["Parser"]
    P -->|"Analyse
syntaxique"| AST["AST
(25 nœuds)"]
    AST -->|"Transpileur
BP2SC"| SC["Code
SuperCollider"]

 

Étage 2 — La sémantique : qu’est-ce que ça veut dire ?

Avoir une syntaxe valide ne suffit pas. La phrase « la note joue le silence » est syntaxiquement correcte mais sémantiquement absurde. Les quatre articles suivants posent la question du sens.

L5 — Les trois sémantiques présente les trois approches fondamentales. Depuis les années 1960, l’informatique a développé trois façons de donner un sens aux programmes :

  • Opérationnelle : on décrit comment le programme s’exécute, pas à pas. « Pour évaluer 2 + 3, on additionne et on obtient 5. »
  • Dénotationnelle : on décrit ce que le programme calcule, comme une fonction mathématique. « 2 + 3 dénote la valeur 5. »
  • Axiomatique : on décrit ce qu’on peut prouver sur le programme. « Si x > 0 avant, alors x + 1 > 1 après. »

Trois regards sur le même objet — comme un architecte (plan), un maçon (construction) et un inspecteur (vérification) regardent le même bâtiment.

 

flowchart TD
    Q["Un programme
P"]
    OP["🔧 Opérationnelle
'Comment ça s'exécute ?'
→ Règles de transition"]
    DN["📐 Dénotationnelle
'Quelle fonction ça calcule ?'
→ Domaines mathématiques"]
    AX["✅ Axiomatique
'Que peut-on prouver ?'
→ Pré/post-conditions"]

    Q --> OP
    Q --> DN
    Q --> AX

 

L6 — SOS développe l’approche opérationnelle de Plotkin. La Structural Operational Semantics (sémantique opérationnelle structurelle) formalise l’exécution d’un programme par des règles d’inférence. C’est l’outil idéal pour décrire les cinq modes de dérivation de BP3 (ORD, RND, LIN, SUB, SUB1) — chacun définit comment une grammaire génère des séquences musicales.

L7 — La sémantique dénotationnelle modélise les programmes comme des fonctions mathématiques. Élégante, mais elle bute sur un problème : la stochasticité. BP3 utilise des tirages aléatoires (mode RND, poids décrémentaux) — un programme BP3 ne calcule pas une séquence mais un ensemble de séquences possibles. La sémantique dénotationnelle classique peine à capturer cette nature probabiliste.

L8 — La sémantique axiomatique permet de prouver des propriétés. La logique de Hoare dit : « Si cette condition est vraie avant l’exécution, alors cette autre condition sera vraie après. » Pour BP3, c’est utile pour prouver des invariants — par exemple, qu’une grammaire avec certains flags produit toujours des séquences de longueur bornée. Mais les limites apparaissent vite face au non-déterminisme.

Pourquoi BP3 a besoin de la SOS

Des trois approches, c’est la sémantique opérationnelle qui convient le mieux à BP3. Pourquoi ? Parce que BP3 est un système de réécriture : on part d’un symbole initial, on applique des règles, et on obtient progressivement une séquence musicale. Chaque pas de réécriture est une transition — exactement ce que la SOS formalise. L’article L6 construit les règles qui rendent cette intuition rigoureuse.

Étage 3 — Au-delà de Chomsky : quand le Type 2 ne suffit plus

Les grammaires context-free (Type 2) sont puissantes, mais elles ont des limites. Deux articles explorent ce qui se passe quand on a besoin de plus.

L9 — Au-delà de Chomsky (MCSL) explore la zone située entre le Type 2 et le Type 1 : les langages mildly context-sensitive (MCSL). Cette zone abrite des formalismes inventés pour le langage naturel — TAG (Tree-Adjoining Grammars), CCG (Combinatory Categorial Grammars), MCFG (Multiple Context-Free Grammars) — mais qui s’appliquent remarquablement bien à la musique. Steedman (1984) a utilisé les CCG pour formaliser l’improvisation jazz. Et BP3, quand ses flags sont bornés, se situe précisément dans cette zone mildly context-sensitive.

L10 — Les grammaires d’attributs enrichissent les arbres syntaxiques avec des propriétés calculées. Inventées par Knuth en 1968, elles permettent d’attacher des informations (type, valeur, contrainte) à chaque nœud de l’arbre. Les flags de BP3 fonctionnent exactement comme des « attributs hérités globaux » : ils transportent de l’information à travers l’arbre de dérivation, modifiant le comportement des règles. Comprendre les grammaires d’attributs, c’est comprendre pourquoi les flags permettent à BP3 de dépasser le Type 2.

 

flowchart LR
    T3["Type 3
Régulier
(MIDI)"]
    T2["Type 2
Context-free
(MusicXML, BP3 base)"]
    MCSL["MCSL
Mildly CS
(BP3 + flags bornés)"]
    T1["Type 1
Context-sensitive
(BP3 + LHS multi)"]
    T0["Type 0
Turing-complet
(BP3 + flags non bornés)"]

    T3 --> T2 --> MCSL --> T1 --> T0

    style MCSL fill:#e8f5e9,stroke:#2e7d32,stroke-width:3px

 

La position de BP3

Le résultat clé (démontré dans R1) :

  • Sans flags : BP3 est context-free (Type 2) — Théorème 4.1
  • Avec flags bornés : BP3 est mildly context-sensitive — Théorème 4.2
  • Avec LHS multi-symboles : BP3 atteint le Type 1 — Proposition 4.1
  • Avec flags non bornés : BP3 est probablement Turing-complet — Conjecture 4.1

C’est un résultat élégant : les mêmes mécanismes qui rendent BP3 expressif musicalement (les flags) sont ceux qui le font monter dans la hiérarchie de Chomsky.

Étage 4 — Traduction et concurrence : les dernières pièces

Le quatrième étage couvre deux problèmes que la syntaxe et la sémantique classiques ne suffisent pas à traiter : traduire un langage en un autre, et exécuter plusieurs processus en parallèle.

L11 — Au-delà des trois sémantiques présente trois sémantiques supplémentaires :

  • La sémantique traductionnelle définit le sens d’un programme par sa traduction dans un autre langage. C’est exactement ce que fait BP2SC : le sens d’un programme BP3 est donné par le code SuperCollider qu’il produit. Le diagramme de Morris (1969) capture cette idée :

 

flowchart LR
    SRC["Programme
BP3"]
    IR["Représentation
intermédiaire
(AST)"]
    TGT["Code
SuperCollider"]

    SRC -->|"Analyse
(front-end)"| IR
    IR -->|"Génération
(back-end)"| TGT
    SRC -.->|"Sémantique
traductionnelle"| TGT

 

  • La sémantique de processus modélise des systèmes qui communiquent et s’exécutent en parallèle. C’est la base formelle pour la polymétrie — quand BP3 superpose plusieurs flux temporels indépendants.
  • La sémantique algébrique définit les opérations sur les programmes comme une structure algébrique (monoïde, groupe). Utile pour les transformations musicales (transposition, inversion).

L12 — Réseaux de Petri et algèbres de processus fournit les outils concrets pour la concurrence. Les réseaux de Petri modélisent des systèmes à ressources partagées par des jetons circulant dans un graphe. Les algèbres de processus (CCS de Milner, CSP de Hoare) formalisent la communication entre processus parallèles via la bisimulation — deux processus sont « équivalents » s’ils ne peuvent pas être distingués de l’extérieur.

La polymétrie comme problème de concurrence

La polymétrie de BP3 — la capacité de superposer des flux temporels à des ratios différents (3 contre 4, 5 contre 7) — est formellement un problème de composition parallèle. L’article L12 montre comment les outils de la théorie de la concurrence (opérateur | de CCS, synchronisation de Petri nets) capturent exactement cette superposition.

La synthèse : pourquoi BP3 a besoin de tout ça

Chaque formalisme de la série L éclaire un aspect différent de BP3. Le tableau suivant résume ces connexions :

Formalisme Question Article Application BP3
Hiérarchie de Chomsky Où se situe BP3 ? L1 Position dans la hiérarchie (Type 2 → MCSL → Turing)
Grammaires context-free Quelle est la base de BP3 ? L2 Règles de réécriture, récursion
EBNF Comment écrire la grammaire ? L3 Spécification formelle de BP3
AST Quel arbre le parser produit-il ? L4 25 types de nœuds, pipeline du transpileur
Sémantique opérationnelle Comment les règles s’exécutent ? L6 5 modes de dérivation formalisés
Sémantique dénotationnelle Quelle distribution BP3 calcule-t-il ? L7 Limites avec la stochasticité
Sémantique axiomatique Que peut-on prouver sur BP3 ? L8 Terminaison, longueur bornée
MCSL (TAG, CCG) Pourquoi BP3 dépasse le Type 2 ? L9 Flags bornés → mildly CS
Grammaires d’attributs Que sont les flags formellement ? L10 Flags ≈ attributs hérités globaux
Sém. traductionnelle Que signifie « traduire en SC » ? L11 BP2SC = sémantique traductionnelle
Sém. de processus Comment formaliser la polymétrie ? L11 Superposition de flux = composition parallèle
Réseaux de Petri / CCS Quel modèle pour le parallélisme ? L12 Polymétrie comme réseau de Petri temporel

Le diagramme final montre le cycle complet — de la grammaire BP3 au son :

 

flowchart LR
    G["Grammaire
BP3"] -->|"L2, L3"| P["Parsing"]
    P -->|"L4"| AST["AST"]
    AST -->|"L6"| SEM["Sémantique
opérationnelle"]
    SEM -->|"L11"| TR["Transpilation
(BP2SC)"]
    TR -->|"L12"| SON["Son
(polymétrie)"]

    style G fill:#fff3e0,stroke:#e65100
    style SON fill:#e8f5e9,stroke:#2e7d32

 

Parcours de lecture recommandés

L’Index propose plusieurs parcours thématiques. En voici un supplémentaire, spécifique à la série L :

Parcours minimaliste (le strict nécessaire pour comprendre BP3)

L1 → L2 → L4 → L5 → L6

Cinq articles. Avec ceux-là, vous comprenez la base syntaxique (L1-L2), la structure de données du transpileur (L4), et la formalisation de l’exécution (L5-L6).

Parcours complet (toute la série)

L1 → L2 → L3 → L4 → L5 → L6 / L7 / L8 → L9 → L10 → L11 → L12

Les trois sémantiques (L6, L7, L8) se lisent indépendamment après L5. Les extensions (L9, L10) complètent la syntaxe. L11 et L12 ferment la boucle avec la traduction et la concurrence.

Parcours « BP3 dans la hiérarchie »

L1 → L2 → L9 → L10

Quatre articles pour comprendre où BP3 se situe et pourquoi les flags le font monter dans la hiérarchie.

Glossaire compact

Terme Définition Article
AST (Abstract Syntax Tree) Arbre représentant la structure d’un programme, sans bruit syntaxique L4
CFG (Context-Free Grammar) Grammaire dont les règles remplacent un symbole indépendamment du contexte L2
CCS (Calculus of Communicating Systems) Algèbre de processus pour modéliser la concurrence L12
EBNF (Extended Backus-Naur Form) Notation standardisée pour écrire des grammaires L3
Flag Variable globale dans BP3 qui modifie le comportement des règles B4
MCSL (Mildly Context-Sensitive Language) Langage entre Type 2 et Type 1 — zone des TAG, CCG, et BP3+flags L9
Parsing Analyse syntaxique : transformer un texte en arbre (AST) L4
Réseau de Petri Modèle de système concurrent par jetons et transitions L12
Sémantique opérationnelle Donner le sens d’un programme en décrivant son exécution L6
SOS (Structural Operational Semantics) Variante structurelle de la sémantique opérationnelle (Plotkin, 1981) L6
TAG (Tree-Adjoining Grammar) Grammaire qui opère par adjonction d’arbres — mildly context-sensitive L9
Transpileur Programme qui traduit du code source vers un autre langage source B7

Pour aller plus loin

Tags : #langages-formels #carte #navigation #BP3 #vue-ensemble