Week 8: What a pattern is made of

ANY, NOTANY, SPAN, BREAK, LEN, ARB, ARBNO, and BAL — the primitive vocabulary that concatenation and alternation compose

12 April 2027

Outline

Five ways to describe a run of characters

Most of this week’s primitives describe a run of subject characters purely in terms of a target character set, with no retry logic of their own:

These four differ from each other only in which characters they accept and whether they insist on at least one, but they share a shape: given a cursor and a target set, there is exactly one longest (or exactly n-long) answer, so in the ordinary case none of them offers up a second, shorter answer to retry if something later in the pattern fails — SPAN and BREAK have already committed to the longest run they found. REM, the “everything left” shorthand, is not even its own case: the reference manual defines it as exactly RTAB(0), reusing the “match from the cursor to a target position counted from the right” primitive rather than adding a bespoke one.

ARB and ARBNO: patterns that grow

ARB and ARBNO are different in kind from the primitives above: they are the ones that genuinely need backtracking’s retry mechanism, because there is no single right-sized answer to try first.

ARB matches the shortest possible run of characters — starting at the null string — and, if what follows it in the pattern fails, extends by exactly one more character and tries again. The Green Book states this with a literally recursive definition, ARB = NULL | LEN(1) *ARB: either match nothing, or match one character and then — via the unevaluated- expression operator *, which defers evaluation so a definition can refer to itself before it is finished being written — try ARB again from the new cursor position. ARBNO(p) generalizes the same idea to a whole subpattern: it matches zero or more repetitions of p, retried by adding one more repetition each time it is asked to try again — ARBNO(p) = NULL | p *ARBNO(p), the same recursive shape with p standing in for “exactly one character.”

Both of these are, in effect, small backtracking loops nested inside the outer search: “shortest first, extend by one unit on failure” is exactly what Griswold’s cursor model calls c_arb — an operation that yields the cursor unchanged the first time, and cursor+1, cursor+2, … on each subsequent retry. Nothing new is needed to implement it beyond the search machinery week 7 already built; ARB is that machinery, applied to itself one character at a time.

BAL: built, not special-cased

BAL matches the shortest nonnull string that is balanced with respect to parentheses — a string with no parentheses at all counts as balanced too. It would be reasonable to expect BAL to need its own hand-written matching procedure, tracking a paren-depth counter the way a parser might. It doesn’t. The Green Book defines it entirely out of primitives already on the table this week:

BALEXP = NOTANY('()') | '(' ARBNO(*BALEXP) ')'
BAL    = BALEXP ARBNO(BALEXP)

A BALEXP is one non-paren character, or a ( followed by zero or more balanced expressions followed by a ) — again using * to let the definition refer to itself before it is complete. BAL itself is one BALEXP followed by zero or more more. Implementing BAL needs no new matching machinery beyond NOTANY, ARBNO, and the recursive-definition trick ARB already used above: it is a genuine composition, not a primitive that quietly gets its own escape hatch.

Efficiency is a vocabulary choice

Once there’s a vocabulary to choose between, the Green Book’s own advice to programmers amounts to a short list of “this primitive is cheaper than that equivalent one”: prefer BREAK (or its extension BREAKX) over ARB when the stopping character is already known — ARB searches blindly, one character at a time, where BREAK can jump straight to the boundary; prefer ANY over spelling out an alternation of single- character literals; avoid ARBNO where a more specific primitive such as SPAN already says what is needed. None of this changes what a pattern matches — it changes how much backtracking the matcher has to do to find that answer out, which is exactly the kind of choice a compiler- construction course should make visible rather than leave to instinct.

Further reading

Teaching team