B11) L’AST de BP3

Anatomie d’un code intermédiaire musical

29 types de nœuds, 3 niveaux d’invariants

Un fichier de grammaire BP3 est du texte. Pour le transformer en musique, il faut d’abord le transformer en arbre. Cet arbre — l’AST — a 29 types de nœuds. Chacun capture un aspect du langage BP3.

Où se situe cet article ?

L4 a introduit les AST en général. B10 a défini la grammaire formelle de BP3 (~50 productions EBNF). B7 a montré comment le transpileur traduit BP3 en SuperCollider. Ici on ouvre la boîte entre les deux : l’AST est la représentation intermédiaire qui connecte le parsing (lecture du texte) à l’émission (génération du code SC).

Vue d’ensemble : 29 nœuds en 11 catégories

L’AST de BP3 capture tout ce qu’un fichier de grammaire peut exprimer. Les 29 types de nœuds se répartissent en 11 catégories :

 

graph TD
    BPFile --> Headers
    BPFile --> GrammarBlock
    BPFile --> TemplateDef

    Headers --> Comment
    Headers --> FileRef
    Headers --> InitDirective

    GrammarBlock --> Rule
    Rule --> Weight
    Rule --> Flag
    Rule --> RHS["RHSElement (19 types)"]

    RHS --> Note
    RHS --> Rest
    RHS --> NonTerminal
    RHS --> Variable
    RHS --> Wildcard
    RHS --> Polymetric
    RHS --> SpecialFn
    RHS --> Lambda
    RHS --> HomoApply
    RHS --> Tie
    RHS --> Others["+ 9 autres"]

    style BPFile fill:#4a7ab5,stroke:#3a6aa5,color:#fff
    style GrammarBlock fill:#4a9a8a,stroke:#3a8a7a,color:#fff
    style Rule fill:#c8842a,stroke:#b8742a,color:#fff
    style RHS fill:#8a5ab5,stroke:#7a4aa5,color:#fff

 

Figure 1 — Hiérarchie de l’AST BP3. BPFile est la racine. Chaque GrammarBlock contient des Rule, chaque Rule contient des RHSElement (19 types possibles).

Les conteneurs : la structure de l’arbre

BPFile — la racine

 

BPFile(
    headers: list[Header],          # commentaires, -al., -se., INIT:
    grammars: list[GrammarBlock],   # au moins 1 bloc de grammaire
    templates: list[TemplateDef]    # optionnel — mode TEM
)

 

Invariant : len(grammars) >= 1 — un fichier BP3 sans grammaire n’a pas de sens.

GrammarBlock — un bloc de sous-grammaire

 

GrammarBlock(
    mode: str,          # "ORD", "RND", "LIN", "SUB", "SUB1", "TEM", "POSLONG"
    index: int,         # numéro du bloc (gram#1, gram#2...)
    rules: list[Rule]   # les règles de ce bloc
)

 

Chaque bloc a son propre mode de dérivation (B3). Les blocs sont séparés par ----- et dérivés séquentiellement : le moteur épuise le bloc N avant de passer au bloc N+1.

Rule — une règle de production

 

Rule(
    grammar_num: int,       # numéro du bloc
    rule_num: int,          # numéro dans le bloc
    weight: Weight,         # poids (optionnel)
    arrow: str,             # "-->" ou "<-->" ou "<--"
    flags: list[Flag],      # conditions et mutations
    lhs: list[RHSElement],  # côté gauche (1+ éléments)
    rhs: list[RHSElement]   # côté droit (0+ éléments)
)

 

Invariants : arrow ∈ {"-->", "<-->", "<--"}, len(lhs) >= 1.

Les terminaux : les feuilles de l’arbre

Nœud Champs Exemple BP3 Rôle
Note name, octave C4, do3, Sa Note musicale
Rest determined: bool - (déterminé), _ (prolongation) Silence
UndeterminedRest (aucun) ... Repos calculé par PolyMake
NonTerminal name S, Phrase, Tihai Symbole à réécrire

Rappel (B2) : les non-terminaux commencent par une majuscule et sont des noms simples dans BP3 (pas de pipes |S|). Les terminaux sont définis dans le fichier d’alphabet (-al.).

Le contrôle : poids et flags

Weight — le poids d’une règle

 

Weight(
    value: int,        # poids numérique (ex: 50)
    decrement: int,    # décrémentation (ex: 12 dans <50-12>)
    k_name: str,       # K-paramètre (ex: "K1")
    k_value: int       # valeur initiale K (ex: 5 dans <K1=5>)
)

 

Quatre formes : <3> (fixe), <50-12> (décrémental), <K1> (paramétrique), <K1=5> (paramétrique initialisé). Voir B1 et B4.

Flag — condition et mutation

 

Flag(
    name: str,      # "avart", "phase"
    op: str,        # "", "=", "+", "-", ">", "<"
    value: str      # "4", "1", None (test simple)
)

 

op="" = test de non-nullité (/avart/). op="=" = assignation (/avart=4/). Voir B4.

Les extensions context-sensitive : ce qui dépasse Type 2

Ces nœuds donnent à BP3 une expressivité au-delà des grammaires hors-contexte (L1) :

Nœud Syntaxe BP3 Rôle Article
Variable \|x\| Capture et réplique un symbole B6
Wildcard ?1, ?2 Pattern matching numéroté B6
HomoApply (=X), (:X) Master (=) et slave (:) d’un motif B6
ContextMarker LEFT, # Contexte de dérivation B6
Polymetric {v1, v2} Superposition de voix B5
SpecialFn _tempo(2) 30+ fonctions spéciales B7
Lambda lambda Production vide (ε) —

Le nœud HomoApply a trois variantes (kind) :

  • MASTER : (= X) — première occurrence, définit le motif
  • SLAVE : (: X) — occurrences suivantes, doivent être identiques
  • REF : référence simple

Les extensions langage complet

Ces nœuds existent dans le langage BP3 complet mais ne sont pas tous couverts par le transpileur BP2SC :

Nœud Syntaxe BP3 Rôle
OutTimeObject <<C4>>, <<chik>> Objet hors-temps (trigger)
SpeedRatio /2, *3, **3, \2 4 opérateurs de vitesse/échelle
BeatSeparator . Séparateur de période
TemplateDef [1] *1/1 __*1/2 _ Définition de template structurel
Tie C4&, &C4 Liaison (notes liées)
GotoDirective _goto(N,M) Saut impératif vers une règle
TimeSig 4+4+4+4/4 Signature temporelle additive

Les invariants : ce que l’AST garantit

Trois niveaux de garanties :

Invariants structurels (vérifiables au parsing)

  • Un fichier a au moins un bloc de grammaire
  • Chaque mode est dans {ORD, RND, LIN, SUB, SUB1, TEM, POSLONG}
  • Chaque flèche est dans {-->, <-->, <--}
  • Les poids sont non-négatifs, les décréments positifs
  • Les wildcards ont un index ≥ 0

Invariants sémantiques (vérifiables à la compilation)

  • Les terminaux existent dans l’alphabet (-al.)
  • Les variables sont liées (chaque |x| a une définition)
  • Les HomoApply SLAVE référencent un MASTER existant

Invariants inter-nœuds (vérifiables à l’exécution)

  • Les flags référencés dans les gardes sont initialisés quelque part
  • Les poids K-paramétriques sont cohérents entre les blocs
  • Les numéros gram#N sont séquentiels

Le triple mapping : EBNF → AST → SC

Pour comprendre comment un motif traverse les 3 représentations, suivons <50-12> S --> A B C :

Étape Représentation
Texte BP3 gram#1[1] <50-12> S --> A B C
EBNF (B10) Production rule → weight, lhs, "-->", rhs
AST Rule(weight=Weight(50,12), arrow="-->", lhs=[NonTerminal("S")], rhs=[NonTerminal("A"), NonTerminal("B"), NonTerminal("C")])
SC (B7) Pdef(\S, Prand([Pseq([Pdef(\A), Pdef(\B), Pdef(\C)])], inf)) avec gestion des poids

Chaque couche a sa propre préoccupation : le texte est lisible, l’EBNF est vérifiable, l’AST est traitable, le SC est jouable.

Les limites : pourquoi cet AST n’est pas une IR générique

L’AST de BP3 est un code intermédiaire BP3-spécifique :

Propriété AST BP3 (29 nœuds) IR musicale générique
Nœuds BPFile, GrammarBlock, Rule Section, Voice, Note, Tempo
Dépend de Sémantique BP3 Aucune notation source
Réutilisable Non (BP3 seulement) Oui (N sources → M cibles)
Couverture Grammaires Type 2+ Toute musique

Pour parser du MusicXML, du LilyPond ou du MIDI, il faudrait un AST différent. C’est le constat qui motive la recherche d’une représentation intermédiaire musicale universelle — un sujet pour un autre article.

Ce qu’il faut retenir

  1. 29 types de nœuds en 11 catégories — de BPFile (racine) à BeatSeparator (feuille)
  2. 3 conteneurs : BPFile → GrammarBlock → Rule — la colonne vertébrale de l’arbre
  3. 19 types de RHSElement — le cœur de l’expressivité de BP3
  4. 3 niveaux d’invariants : structurels (parsing), sémantiques (compilation), inter-nœuds (exécution)
  5. Le triple mapping EBNF → AST → SC montre comment chaque motif traverse les représentations
  6. Cet AST est BP3-spécifique — il ne peut pas servir d’IR musicale générique

Pour aller plus loin

  • Aho, A.V. et al. (1986) : Compilers: Principles, Techniques, and Tools — la référence sur les AST et la compilation. DOI:10.5555/6448
  • Bel, B. & Kippen, J. (1992) : « Modelling Music with Grammars » — le formalisme sous-jacent à ces 29 nœuds

Glossaire

  • AST : Abstract Syntax Tree — représentation arborescente d’un programme après parsing
  • RHSElement : Union type des 19 types de nœuds pouvant apparaître dans le côté droit d’une règle
  • NonTerminal : Symbole pouvant être réécrit (commence par une majuscule en BP3)
  • HomoApply : Nœud d’homomorphisme — MASTER (=X) définit, SLAVE (:X) réplique
  • SpecialFn : Fonction spéciale BP3 (_tempo, _smooth, _legato, etc.) — 30+ fonctions
  • Lambda : Production vide (ε) — le non-terminal disparaît
  • OutTimeObject : Objet hors-temps <<symbole>> — déclenché sans occuper de durée
  • SpeedRatio : Opérateur de vitesse/échelle (/2, *3, **3, \2)
  • IR : Intermediate Representation — représentation intermédiaire entre le source et la cible

Liens dans la série

  • L4 — Qu’est-ce qu’un AST — les concepts généraux
  • B10 — L’EBNF de BP3 — la grammaire qui définit ce que l’AST peut contenir
  • B7 — Le transpileur — comment l’AST est traduit en SuperCollider
  • B3 — Les 7 modes — le champ mode de GrammarBlock
  • B4 — Flags et poids — les nœuds Weight et Flag
  • B5 — Polymétrie — le nœud Polymetric
  • B6 — Homomorphismes — Variable, Wildcard, HomoApply

Prérequis : L4, B7, B10
Temps de lecture : 16 min
Tags : #ast #bp3 #code-intermédiaire #représentation #nœuds

← Retour à l’index