B11) The BP3 AST

Anatomy of a Musical Intermediate Code

29 Node Types, 3 Levels of Invariants

A BP3 grammar file is text. To transform it into music, it must first be transformed into a tree. This tree — the AST — has 29 node types. Each captures an aspect of the BP3 language.

Where Does This Article Fit In?

L4 introduced ASTs in general. B10 defined the formal grammar of BP3 (~50 EBNF productions). B7 showed how the transpiler translates BP3 into SuperCollider. Here, we open the box in between: the AST is the intermediate representation that connects parsing (reading the text) to emission (generating the SC code).

Overview: 29 Nodes in 11 Categories

BP3’s AST captures everything a grammar file can express. The 29 node types are divided into 11 categories:

 

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 others"]

    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 — BP3 AST hierarchy. BPFile is the root. Each GrammarBlock contains Rules, each Rule contains RHSElements (19 possible types).

Containers: The Structure of the Tree

BPFile — The Root

 

BPFile(
    headers: list[Header],          # comments, -al., -se., INIT:
    grammars: list[GrammarBlock],   # at least 1 grammar block
    templates: list[TemplateDef]    # optional — TEM mode
)

 

Invariant: len(grammars) >= 1 — a BP3 file without a grammar makes no sense.

GrammarBlock — A Sub-grammar Block

 

GrammarBlock(
    mode: str,          # "ORD", "RND", "LIN", "SUB", "SUB1", "TEM", "POSLONG"
    index: int,         # block number (gram#1, gram#2...)
    rules: list[Rule]   # the rules of this block
)

 

Each block has its own derivation mode (B3). Blocks are separated by ----- and derived sequentially: the engine exhausts block N before moving on to block N+1.

Rule — A Production Rule

 

Rule(
    grammar_num: int,       # block number
    rule_num: int,          # number within the block
    weight: Weight,         # weight (optional)
    arrow: str,             # "-->" or "<-->" or "<--"
    flags: list[Flag],      # conditions and mutations
    lhs: list[RHSElement],  # left-hand side (1+ elements)
    rhs: list[RHSElement]   # right-hand side (0+ elements)
)

 

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

Terminals: The Leaves of the Tree

Node Fields BP3 Example Role
Note name, octave C4, do3, Sa Musical note
Rest determined: bool - (determined), _ (prolongation) Rest
UndeterminedRest (none) ... Rest calculated by PolyMake
NonTerminal name S, Phrase, Tihai Symbol to rewrite

Reminder (B2): non-terminals start with an uppercase letter and are simple names in BP3 (no pipes |S|). Terminals are defined in the alphabet file (-al.).

Control: Weights and Flags

Weight — The Weight of a Rule

 

Weight(
    value: int,        # numerical weight (e.g., 50)
    decrement: int,    # decrement (e.g., 12 in <50-12>)
    k_name: str,       # K-parameter (e.g., "K1")
    k_value: int       # initial K value (e.g., 5 in <K1=5>)
)

 

Four forms: <3> (fixed), <50-12> (decremental), <K1> (parametric), <K1=5> (parametric initialized). See B1 and B4.

Flag — Condition and Mutation

 

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

 

op="" = non-nullity test (/avart/). op="=" = assignment (/avart=4/). See B4.

Context-Sensitive Extensions: Beyond Type 2

These nodes give BP3 expressiveness beyond context-free grammars (L1):

Node BP3 Syntax Role Article
Variable \|x\| Captures and replicates a symbol B6
Wildcard ?1, ?2 Numbered pattern matching B6
HomoApply (=X), (:X) Master (=) and slave (:) of a pattern B6
ContextMarker LEFT, # Derivation context B6
Polymetric {v1, v2} Voice superposition B5
SpecialFn _tempo(2) 30+ special functions B7
Lambda lambda Empty production (ε) —

The HomoApply node has three variants (kind):

  • MASTER: (= X) — first occurrence, defines the pattern
  • SLAVE: (: X) — subsequent occurrences, must be identical
  • REF: simple reference

Full Language Extensions

These nodes exist in the full BP3 language but are not all covered by the BP2SC transpiler:

Node BP3 Syntax Role
OutTimeObject <<C4>>, <<chik>> Out-of-time object (trigger)
SpeedRatio /2, *3, **3, \2 4 speed/scale operators
BeatSeparator . Beat separator
TemplateDef [1] *1/1 __*1/2 _ Structural template definition
Tie C4&, &C4 Tie (tied notes)
GotoDirective _goto(N,M) Imperative jump to a rule
TimeSig 4+4+4+4/4 Additive time signature

Invariants: What the AST Guarantees

Three levels of guarantees:

Structural Invariants (Verifiable during Parsing)

  • A file has at least one grammar block
  • Each mode is in {ORD, RND, LIN, SUB, SUB1, TEM, POSLONG}
  • Each arrow is in {-->, <-->, <--}
  • Weights are non-negative, decrements are positive
  • Wildcards have an index ≥ 0

Semantic Invariants (Verifiable during Compilation)

  • Terminals exist in the alphabet (-al.)
  • Variables are bound (each |x| has a definition)
  • SLAVE HomoApply nodes reference an existing MASTER

Inter-node Invariants (Verifiable at Runtime)

  • Flags referenced in guards are initialized somewhere
  • K-parametric weights are consistent across blocks
  • gram#N numbers are sequential

The Triple Mapping: EBNF → AST → SC

To understand how a pattern traverses the 3 representations, let’s follow <50-12> S --> A B C:

Step Representation
BP3 Text 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)) with weight management

Each layer has its own concern: the text is readable, the EBNF is verifiable, the AST is processable, and the SC is playable.

Limitations: Why This AST Is Not a Generic IR

BP3’s AST is a BP3-specific intermediate code:

Property BP3 AST (29 nodes) Generic Musical IR
Nodes BPFile, GrammarBlock, Rule Section, Voice, Note, Tempo
Depends on BP3 semantics No source notation
Reusable No (BP3 only) Yes (N sources → M targets)
Coverage Type 2+ grammars All music

To parse MusicXML, LilyPond, or MIDI, a different AST would be required. This realization motivates the search for a universal musical intermediate representation — a topic for another article.

Key Takeaways

  1. 29 node types in 11 categories — from BPFile (root) to BeatSeparator (leaf)
  2. 3 containers: BPFile → GrammarBlock → Rule — the backbone of the tree
  3. 19 types of RHSElement — the core of BP3’s expressiveness
  4. 3 levels of invariants: structural (parsing), semantic (compilation), and inter-node (runtime)
  5. The triple mapping EBNF → AST → SC shows how each pattern traverses the representations
  6. This AST is BP3-specific — it cannot serve as a generic musical IR

Further Reading

  • Aho, A.V. et al. (1986): Compilers: Principles, Techniques, and Tools — the reference on ASTs and compilation. DOI:10.5555/6448
  • Bel, B. & Kippen, J. (1992): “Modelling Music with Grammars” — the formalism underlying these 29 nodes

Glossary

  • AST: Abstract Syntax Tree — tree representation of a program after parsing
  • RHSElement: Union type of the 19 node types that can appear on the right-hand side of a rule
  • NonTerminal: A symbol that can be rewritten (starts with an uppercase letter in BP3)
  • HomoApply: Homomorphism node — MASTER (=X) defines, SLAVE (:X) replicates
  • SpecialFn: BP3 special function (_tempo, _smooth, _legato, etc.) — 30+ functions
  • Lambda: Empty production (ε) — the non-terminal disappears
  • OutTimeObject: Out-of-time object <<symbol>> — triggered without occupying duration
  • SpeedRatio: Speed/scale operator (/2, *3, **3, \2)
  • IR: Intermediate Representation — intermediate representation between source and target

Links in the Series

  • L4 — What is an AST — general concepts
  • B10 — BP3’s EBNF — the grammar defining what the AST can contain
  • B7 — The transpiler — how the AST is translated into SuperCollider
  • B3 — The 7 modes — the mode field of GrammarBlock
  • B4 — Flags and weights — the Weight and Flag nodes
  • B5 — Polymetry — the Polymetric node
  • B6 — Homomorphisms — Variable, Wildcard, HomoApply

Prerequisites: L4, B7, B10
Reading time: 16 min
Tags: #ast #bp3 #intermediate-code #representation #nodes

← Back to index