B3) Derivation Rules

How a Grammar Generates

A grammar is a set of rules. But how are these rules applied to produce concrete results?

Where does this article fit in?

After defining the B1 (probabilities) and B2 (vocabulary) of BP3, this article details how the rules are applied. The seven derivation modes (ORD, RND, LIN, SUB, SUB1, TEM, POSLONG) are formalized in SOS (Structural Operational Semantics) in article L6.

Why is this important?

Having a grammar is not enough. You also need to know how to use it. A grammar defines the rules of the game, but not the strategy for playing.

Let’s take a culinary analogy. A recipe tells you that you can add salt “to taste” and that you can cook the dish “in the oven or in a pan.” But in what order do you do things? Do you salt before or after cooking? Do you choose the cooking method first?

Similarly, a grammar often offers several rules that can be applied simultaneously. The derivation strategy determines which one to apply first, and this strategy can radically change the system’s behavior. BP3 goes further: it offers seven different derivation modes, each adapted to a generation style.

The idea in one sentence

A derivation is a sequence of production rule applications that transforms the start symbol into a string of terminals; the strategy (order, choice) determines the result.

Let’s explain step by step

Anatomy of a production rule

A production rule (or rewrite rule) has the form:

A → α

It reads: “Symbol A can be replaced by sequence α (alpha — any string of symbols).”

Sidebar: The production rule as an instruction

Think of a production rule as a substitution instruction in a word processor:

“Replace A with xyz”

Every time you see A in your working text, you CAN replace it with xyz. You don’t have to (there may be other rules for A), but it’s a valid option.

Components:

A: the left side, called LHS (Left-Hand Side). This is what is replaced. In a context-free grammar (cf. L2), it is always A SINGLE non-terminal.
α: the right side, called RHS (Right-Hand Side). This is what it is replaced by. Can be a sequence of terminals and/or non-terminals, or even the empty string (ε).
→: the production arrow, which indicates the direction of replacement (left to right).

Examples:

S → A B           (S becomes the sequence A then B)
A → a A           (A becomes 'a' followed by A - recursion)
A → a             (A simply becomes 'a')
B → b             (B becomes 'b')

Derivation: from S to w

A derivation is a sequence of intermediate forms, each obtained by applying a rule to the previous one. It is the “path” that leads from the start symbol S to a final string w.

Notation:

Sidebar: Derivation arrows

Symbol Name Meaning Example

=> simple derivation exactly ONE step S => A B

=>* star derivation ZERO or more steps S =>* abc (S can be abc, or reach it in several steps, or S = abc directly)

=>+ plus derivation ONE or more steps S =>+ abc (at least one rule has been applied)

>
The star (*) and plus (+) are conventions borrowed from regular expressions:

Star = “zero or more”

Plus = “one or more”

Symbol	Name	Meaning	Example
`=>`	simple derivation	exactly ONE step	S => A B
`=>*`	star derivation	ZERO or more steps	S =>* abc (S can be abc, or reach it in several steps, or S = abc directly)
`=>+`	plus derivation	ONE or more steps	S =>+ abc (at least one rule has been applied)

Complete example:

Grammar:

S → A B
A → a A | a
B → b B | b

Derivation of aab:

S
=> A B        (S → A B)
=> a A B      (A → a A)
=> a a B      (A → a)
=> a a b      (B → b)

We write: S =>* aab

Example 1: leftmost vs rightmost derivation

When multiple non-terminals are present in the working string, which one should be replaced first? This is a question of derivation strategy.

Sidebar: Why strategy matters?

For an unambiguous grammar (where each string admits only one derivation tree), the final RESULT is the same regardless of the strategy. But the PATH (the order of steps) differs. This matters for:

Parsers: an LL parser (Left-to-right, Leftmost derivation) reads from left to right and uses leftmost derivation; an LR parser (Left-to-right, Rightmost derivation) uses rightmost.

Debugging: following a derivation step-by-step is easier with a consistent strategy.

Ambiguous grammars: different strategies can lead to different interpretations.

Leftmost derivation:
We ALWAYS replace the leftmost non-terminal first. It’s like reading a book: you process what comes first.

Rightmost derivation:
We ALWAYS replace the rightmost non-terminal first. It’s like unpacking a stack: you process what arrived last.

Example grammar:

S → A B
A → a
B → b

Leftmost derivation of ab:

S
=> A B        (S → A B, we have A and B, A is leftmost)
=> a B        (A → a, we replace A)
=> a b        (B → b, we replace B)

Rightmost derivation of ab:

S
=> A B        (S → A B, we have A and B, B is rightmost)
=> A b        (B → b, we replace B first)
=> a b        (A → a, we replace A)

Identical result, different path.

For unambiguous grammars, leftmost and rightmost produce the same result. The difference becomes important for parsers and ambiguous grammars.

Example 2: when order changes the result (non-deterministic grammars)

With alternative rules, the choice of rule (not just the symbol) affects the result.

Grammar:

S → A B
A → a | aa
B → b | bb

Possible derivations of 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"

Four different results depending on the choices. This is the non-determinism of grammars.

Sub-grammars and exhaustion

Before discussing modes, a fundamental principle: a BP3 grammar is not a monolithic block — it is divided into sub-grammars separated by dashed lines (-----).

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

-----

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

The BP3 engine derives sub-grammars in order, with an exhaustion principle: each gram#N block is derived until no non-terminal from that block can be rewritten in the work string (the string currently being derived). Only then does the engine move to the next block.

Concretely:

gram#1 applies first — it rewrites S to A B C, then A to dha dhin. As long as there is a non-terminal that gram#1 knows how to rewrite, we stay in gram#1.
When gram#1 is exhausted (nothing left to rewrite), we move to gram#2 which rewrites B and C.

This division is powerful: each sub-grammar has its own derivation mode. We can have gram#1 in ORD mode (deterministic) followed by gram#2 in RND mode (random) — the first phase sets the structure, the second fills it with variations.

ORD                          // gram#1: deterministic structure
gram#1[1] S --> Phrase Phrase

-----

RND                          // gram#2: random content
gram#2[1] Phrase --> dha dhin tirakita
gram#2[2] Phrase --> ta tin tirakita
gram#2[3] Phrase --> dha ge tirakita

In BPscript, the separator is ----- and the mode is declared by @mode:X (S5):

@mode:ord
S -> Phrase Phrase

-----

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

The seven BP3 modes: derivation strategies

BP3 does not settle for pure non-determinism. It offers seven modes that define how to choose among alternative rules within a sub-grammar. These modes transform the grammar into different types of generators.

ORD Mode: strict sequential

Principle: Rules are applied in the order they are written in the grammar file. For each non-terminal, its first available rule is used, then the next one is moved to when the first has been exhausted.

BP3 Example — a tintāl theka:

The theka is the basic pattern of a tāla (Indian rhythmic cycle), played as an ostinato by the tabla. It is the perfect example of ORD mode: the theka is always the same, deterministic, played identically in each 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

Step-by-step derivation:

Step 1: S
         → Vibhag1 Vibhag2 Vibhag3 Vibhag4      (rule 1)

Step 2: Vibhag1 -->dha dhin dhin dha                  (rule 2)
Step 3: Vibhag2 -->dha dhin dhin dha                  (rule 3)
Step 4: Vibhag3 -->dha tin tin ta                     (rule 4)
Step 5: Vibhag4 -->ta dhin dhin dha                   (rule 5)

Result: dha dhin dhin dha | dha dhin dhin dha | dha tin tin ta | ta dhin dhin dha

This is the theka of tintāl — the most common 16-beat cycle in Hindustani music. Always the same, 100% deterministic. Note the contrast between the thali sections (vibhāg 1-2, resonant bols dha/dhin) and the khali section (vibhāg 3, dry bols tin/ta).

Usage: Generating fixed sequences: thekas, scales, technical exercises, any pattern where repeatability is essential.

RND Mode: weighted random

Principle: Among all applicable rules for a non-terminal, one is chosen randomly according to the specified weights. The weight <N> indicates the relative importance of the rule.

BP3 Example:

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

Probability calculation:

For S: total weight = 3 + 1 = 4
  - P(rule 1) = 3/4 = 75% (continue)
  - P(rule 2) = 1/4 = 25% (terminate with x)

For A: total weight = 3 + 2 + 1 = 6
  - P(rule 3) = 3/6 = 50% (motif a b c — most frequent)
  - P(rule 4) = 2/6 = 33% (motif a a b)
  - P(rule 5) = 1/6 = 17% (motif c - a — rare)

Three possible executions:

Execution 1: S → x                              → "x"
Execution 2: S → a b c S → a b c x              → "a b c x"
Execution 3: S → c - a S → c - a a a b S → ...  → "c - a a a b ..."

Result: Variable with each execution. Heavier weighted patterns appear more often.

Usage: Improvisation, variation, creative exploration. Weights model the relative frequency of each alternative.

LIN Mode: random leftmost derivation

Correction (March 2026)

This article initially contained an erroneous description of LIN mode as “cyclic (wrap-around)”. This is false. The correction below is based on the official BP3 documentation [Bel, BP2 Grammars] and confirmed by Bernard Bel.

Principle: Among the candidate rules, a rule that produces a leftmost derivation (the leftmost non-terminal in the work string is rewritten) is chosen randomly. In analysis mode, rightmost derivation is used (rightmost derivation, context-sensitive).

This is the random counterpart of ORD: where ORD takes the first candidate rule, LIN chooses one at random from those that apply to the leftmost position.

BP3 Example:

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

Step-by-step derivation:

S → A B                  (rule 1 — only candidate for S)

A is the leftmost non-terminal.
Candidate rules for A: rule 2 (A → a) and rule 3 (A → c)
Random choice → let's say rule 3:

A B → c B                (rule 3 — chosen randomly)

B is now the leftmost non-terminal.
Candidate rules for B: rule 4 (B → b) and rule 5 (B → d)
Random choice → let's say rule 4:

c B → c b                (rule 4 — chosen randomly)

Possible result: c b (among 4 possible results: a b, a d, c b, c d)

Difference from RND: In RND mode, rules are chosen randomly without position constraint. In LIN mode, the random choice is constrained: only rules applicable to the leftmost position are considered. This is a more disciplined non-determinism — the derivation always progresses from left to right, but with variation at each position.

Usage: When controlled non-determinism is desired: the structure progresses from left to right (as in reading), but the content varies with each execution.

SUB Mode: global substitution

Principle: When a non-terminal is expanded, ALL its occurrences in the work string are simultaneously replaced by the same expansion. This is a “Replace All.”

Correction (March 2026)

The initial version of this article illustrated SUB with a tihāī (Indian cadence). This analogy was musicologically incorrect: the tihāī uses parenthesized expressions ((= A)(= Gap)(: A)(: Gap)(: A)) and templates, not simple SUB mode. The example has been replaced with a neutral alphabet.

BP3 Example:

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

Step-by-step derivation:

Step 1: S → A - A - A                      (rule 1)

Step 2: We choose how to expand A.
         Suppose we choose rule 2 (A → a b c).
         ALL occurrences of A are replaced SIMULTANEOUSLY:

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

Result: a b c - a b c - a b c — the three A’s are identical.

In RND mode, each A would be expanded independently: the first could become a b c, the second d e f, the third a b c. SUB mode guarantees the uniformity of substitutions.

Usage: Thematic consistency (all appearances of a motif are identical), strict canons, p-substitutions (parallel substitutions) for infinite automatic sequences.

SUB1 Mode: first occurrence substitution

Principle: At each step, only the first occurrence (leftmost) of each non-terminal is replaced. Other occurrences of the same symbol await their turn. This mode is faster than SUB, usable when it is known that the first substitution directly produces terminals.

BP3 Example:

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

Step-by-step derivation:

Step 1: S → A - A - A                      (rule 1)

Step 2: We replace only the FIRST A (leftmost).
         Suppose rule 2:
         → a b - A - A

Step 3: We replace the next A (now leftmost).
         Suppose rule 3:
         → a b - c d e - A

Step 4: Last A. Suppose rule 4:
         → a b - c d e - f g

Result: a b - c d e - f g — each A is expanded independently, unlike SUB.

Crucial difference from SUB: In SUB mode, the three A’s would have been identical. In SUB1 mode, each A is expanded separately, allowing for variations — different antecedent and consequent, progressive development.

Usage: Thematic development (each occurrence evolves), asymmetric structures. Faster than SUB because it only searches for one occurrence at each step.

TEM Mode: structural templates

Principle: TEM (Templates) mode generates an exhaustive catalog of structural skeletons — all the forms that the grammar can produce, without the concrete terminals. BP3 exhaustively derives sub-grammars marked TEM and stores the results as reusable templates.

The result is stored in a TEMPLATES: section of the grammar file:

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

Each template is a skeleton: positions (_, __) indicate where motifs are placed, groups (@N ...) reference sub-grammars whose result is inserted. Ratios (*1/1, *1/2) indicate speed ratios.

Usage: In ANAL mode (recognition, cf. B8), pre-calculated templates allow for quickly testing if a sequence belongs to the language — by comparing to skeletons rather than re-deriving. If no template matches, the sequence is rejected without backtracking.

POSLONG Mode: position + longest match

Principle: POSLONG (Position + Longest) is a variant of SUB1 with an additional disambiguation criterion. Like SUB1, it replaces only one occurrence at a time (the leftmost). But when several rules are candidates for the same position, POSLONG selects the one that produces the longest derivation.

The algorithm, visible in Compute.c:1375-1399, proceeds in three steps:

Find the minimal position (leftmost): among all candidate rules, those that match the leftmost position are retained.
Select the maximal length (longest): among the candidates at the same position, the one that produces the longest derivation is retained.
Apply: the selected rule replaces the first occurrence.

This is the leftmost-longest match strategy — the same heuristic that POSIX regular expressions use for pattern matching.

Difference from SUB1:

Criterion	SUB1	POSLONG
Occurrences replaced	One (leftmost)	One (leftmost)
Choice among candidate rules	According to weights (RND) or order (ORD)	The longest derivation
Determinism	Variable (depending on choice mode)	Yes (length criterion decides)

Restrictions: The same as SUB and SUB1 — no flags (/flags/), no _goto, no “Produce all items” (CompileGrammar.c:613-695, ProduceItems.c:757).

Usage: Useful when the grammar contains rules of different lengths and one systematically wants the most developed pattern — for example, for transliteration where the longest match is the most specific.

Sidebar: The seven modes and tabla practice

Each BP3 derivation mode naturally corresponds to an aspect of tabla performance, which is no coincidence: BP was designed to model these practices exactly [BelKippen1992a]:

Mode Tabla Practice Description

ORD Theka (ostinato) The basic pattern of the tāla, always identical, played mechanically

RND Improvisation The tablist chooses from a repertoire of motifs, some more frequent than others

LIN Positional Variation Each position receives random content, but progression remains left→right

SUB Global Substitution All occurrences of a non-terminal replaced simultaneously

SUB1 Progressive Development Each occurrence of a motif is developed independently

TEM Structural Skeletons Exhaustive catalog of possible forms

POSLONG Transliteration Longest match at the leftmost position

>
The first five modes emerge directly from the observation of real music [Bel1998]. TEM and POSLONG are extensions for specialized uses — structural exploration and deterministic pattern matching.

Mode	Tabla Practice	Description
ORD	Theka (ostinato)	The basic pattern of the tāla, always identical, played mechanically
RND	Improvisation	The tablist chooses from a repertoire of motifs, some more frequent than others
LIN	Positional Variation	Each position receives random content, but progression remains left→right
SUB	Global Substitution	All occurrences of a non-terminal replaced simultaneously
SUB1	Progressive Development	Each occurrence of a motif is developed independently
TEM	Structural Skeletons	Exhaustive catalog of possible forms
POSLONG	Transliteration	Longest match at the leftmost position

Summary table of modes

Mode	Meaning	Rule Choice	Multiple Occurrences	Determinism
ORD	Ordered	Sequential, in file order	Independent	Yes, 100%
RND	Random	Random according to weights	Independent	No
LIN	Linear (leftmost)	Random among leftmost	Independent	Yes, leftmost
SUB	Substitution	Random or sequential	All identical	Variable
SUB1	Substitution 1	Random or sequential	One at a time	Variable
TEM	Templates	Exhaustive (all derivations)	—	Yes (exhaustive)
POSLONG	Position + Longest	Leftmost + longest match	One at a time	Yes

Sidebar: Choosing the right mode

Do you want a fixed and reproducible sequence? → ORD

Do you want controlled variety? → RND with adjusted weights

Do you want non-determinism that progresses from left to right? → LIN

Do you want repetitions to be identical? → SUB

Do you want progressive development where each repetition can evolve? → SUB1

Do you want to catalog all possible structural forms? → TEM

Do you want the longest match at each position? → POSLONG

Visualizing a derivation: the syntax tree

A derivation can be represented as a syntax tree (see also L4):

The root is the start symbol
Each non-terminal node has the symbols of its expansion as children
The leaves are the terminals

Example:

Grammar:

S → A B
A → a a
B → b

Tree for aab:

TikZ diagram

Figure 1 — Syntax tree for the derivation of aab (S \(\to\) A B, A \(\to\) a a, B \(\to\) b). Non-terminals are in blue, terminals in orange.

Reading the leaves from left to right: a a b

Parsers build these trees to analyze code or text.

Key takeaways

A production rule A → α indicates that A can be replaced by α.
A derivation is a sequence of replacements from the start symbol to the terminals.
Leftmost and rightmost are two strategies for choosing which non-terminal to replace first.
BP3 offers seven modes that go far beyond:

– ORD: fixed order of rules
– RND: weighted random choice
– LIN: leftmost, random choice
– SUB: global substitution (consistency)
– SUB1: one occurrence substitution at a time
– TEM: exhaustive derivation to generate a catalog of structural skeletons (TEMPLATES:)
– POSLONG: like SUB1, but selects the longest derivation (leftmost-longest match)

The chosen mode radically transforms the generative behavior of the same grammar.
Modes vs directions: the seven modes above define the derivation strategy of an individual sub-grammar. BP3 also has three directions that determine the overall use of the grammar: PROD (production), ANAL (recognition), and TEMP (templates). See B8.

To go further

Reference book: Aho, Lam, Sethi & Ullman, Compilers: Principles, Techniques, and Tools (the “Dragon Book”), chapter 4
BP3 Documentation: Bol Processor – Produce All Items
BP3 Modes: Bol Processor – Grammar Control
Visualization: Syntax Tree Generator
The modes in their original context: Bel, B. & Kippen, J. (1992), “Modelling Music with Grammars: Formal Language Representation in the Bol Processor” — description of ORD, RND, SUB modes applied to tabla
Overview: Bel, B. (1998), “Migrating Musical Concepts — An Overview of the Bol Processor”, Computer Music Journal 22(2)
Beyond production: B8 — BP3’s ANAL (recognition) and TEMP (exhaustive structural exploration) modes. QAVAID (grammar inference) was a separate Prolog II program, not integrated into BP3.

Glossary

Syntax tree: Tree representation of a derivation, with the start symbol at the root and terminals at the leaves.
Kayda: Tabla composition with a fixed theme (mukhra) and systematic variations. Uses complex grammatical structures (sub-grammars, templates), not simply SUB1 mode.
Khali: “Empty” or “non-resonant” section of a tāla cycle, where dry bols (tin, ta) dominate.
Derivation: Sequence of rule applications transforming the start symbol into a string of terminals.
Leftmost derivation: Strategy that always replaces the leftmost non-terminal.
LHS (Left-Hand Side): Left part of a production rule, i.e., the symbol being replaced.
LIN (BP3 mode): Linear mode — the candidate rule is chosen randomly from those that produce a leftmost derivation (the leftmost non-terminal in the work string is rewritten first).
Derivation mode: In BP3, a sub-grammar strategy for choosing and applying rules (ORD, RND, LIN, SUB, SUB1, TEM, POSLONG).
ORD (BP3 mode): Ordered mode, where rules are applied in the sequential order of the file.
POSLONG (BP3 mode): Position + Longest mode, a variant of SUB1 that selects the longest derivation among candidate rules at the leftmost position. Leftmost-longest match strategy.
Ostinato: Short musical motif stubbornly repeated throughout a passage or piece.
Sam: First beat of the tāla cycle — the point of resolution for Indian cadences.
Theka: Basic pattern of a tāla, played by the tabla as an ostinato. Corresponds to BP3’s ORD mode.
Tihāī: Indian cadence where a motif is repeated exactly three times to land on sam. Corresponds to BP3’s SUB mode.
Tintāl: The most common tāla in Hindustani music: 16 beats in 4 vibhāg of 4 beats.
Vibhāg: Section of a tāla (e.g., tintāl has 4 vibhāg).
RHS (Right-Hand Side): Right part of a production rule, i.e., what it is replaced by.
Rightmost derivation: Strategy that always replaces the rightmost non-terminal.
RND (BP3 mode): Random mode, where rules are chosen randomly according to their weights.
Production rule: Instruction of the form A → α indicating that A can be rewritten as α.
SUB (BP3 mode): Substitution mode, where all occurrences of the same non-terminal are replaced identically.
SUB1 (BP3 mode): Substitution 1 mode, where only the first occurrence of a non-terminal is replaced at each step.
TEM (BP3 mode): Templates mode, which exhaustively derives a sub-grammar to generate a catalog of structural skeletons (TEMPLATES: section).
Leftmost derivation: Derivation strategy that always rewrites the leftmost non-terminal in the work string. In BP3’s LIN mode, the choice among applicable rules at this position is random.

Prerequisites: B1 (PCFG), B2 (Alphabets), L6 (SOS)
Reading time: 8 min
Tags: #derivation #grammars #BP3 #modes #generation #parsing

← Back to index