← Contents

Chapter 3

Where It Sits in the Taxonomy

There is a question every compiler gets asked before any other: what kind of compiler is it? LL or LR, one-pass or multi-pass, interpreter or compiler, bytecode or native. The answer for Raku++ is that the question decomposes — the front end, the regex engine and the back end are classified on three different axes, and only when they are taken apart does the taxonomy say anything useful.

It is worth doing before the mechanisms, because most of the front end's limitations are not independent defects. They are what the box costs. A reader who knows the classification can predict the limitation list in Chapter 6 without being told it.

The one-line answer:

A hand-written, single-pass, syntax-directed recursive-descent parser with a Pratt (precedence-climbing) expression core and a dynamically extensible operator table, feeding an AST tree-walking interpreter, with an optional source-to-source back end that emits C++.

Nothing in that sentence is generated. There is no grammar file, no parser generator, no state table, and no dependency — which is the same constraint Chapter 1 opened with, seen from the compiler-theory side.

Single-pass is the load-bearing word in that sentence, and it is the one with exceptions. The parse proper reads the token vector once; the lexer scans the source once before it, two seams throw the unread tail away and lex it again, and one of those runs the user's own code to do it. They are set out under "The pass structure" below, because a reader who takes the one-liner unqualified will predict the wrong limitation list — which is the opposite of what this chapter is for.

The lexer: separate, complete, run more than once

Lexer::tokenize() is a character-level scanner that runs to completion and returns a flat std::vector<Token>. Only then is a parser built over it:

// src/Parser.cpp
Lexer lx(src);
Parser p(lx.tokenize());

The lexer therefore never asks the parser anything. That is worth stating explicitly because the opposite arrangement is so common: C compilers famously need the parser's symbol table to decide whether an identifier is a type name, and the resulting parser-to-lexer feedback loop is known in the trade as the lexer hack. Raku++ has nothing of the sort; by the time the parser exists the lexer has finished.

The other direction is not empty, though, and this chapter used to say it was. A parser that reaches a use can discard the tokens it has not read yet and lex the remaining source again: relexForQuoteWords and activateSlang in src/Parser.cpp both truncate toks_ at the cursor and splice on a freshly lexed tail. The lexer is still closed over its input and still answers no questions — it is simply run more than once. What forces that is always the same shape of event: a use teaches the lexer something, and the lexer is already past.

tokenize() also opens with a scan of its own. Before a single token exists it reads the source for sub q, sub s and sub tr declarations (scanQuoteWordSubs), because a routine of that name beats the quote form of the same name from its declaration onward, and the lexer has no scopes to ask. It is textual and deliberately narrow — a comment is skipped, quoted text is not code — but it is a pre-scan by any reasonable definition.

Raku's context-sensitivity is real, so the work has to happen somewhere; here it is resolved from the lexer's own one-token history. A bare / opens a regex in term position and divides in operator position, and regexContext() decides by inspecting the previous token alone — after most operators a term is expected, so a regex follows; after a value, a ), or a postfix ++, division does. Chapter 4 gives the rule and the keyword set that patches the identifier case.

Two consequences follow from a lexer that is closed over its input before parsing begins, and both matter later:

The operator vocabulary is static. lexOperator matches against a hand-ordered table, first match wins, entries arranged longest-first by hand rather than by a maximal-munch scanner. It tracks no user declarations. An operator spelling it does not know falls through to a single-character token — which is precisely how a user-declared operator reaches the parser at all.

Rule bodies are not Raku tokens. A token, rule or regex body is captured whole as one opaque token and re-lexed later by the regex engine (Chapter 20). The regex sub-language never enters the main token stream, which is why Part V can be read as a separate compiler.

The parser: recursive descent with a Pratt core

The parser is the classic hybrid:

The split is not a matter of taste. Raku's operator table runs to some two dozen precedence levels, and pure recursive descent spends one mutually recursive function per level to express them — the textbook expr → term → factor ladder, with twenty-odd rungs. Precedence climbing collapses the ladder into a single loop driven by sixteen named binding powers, which is why parseExpr fits on a page (Chapter 5).

Placing it in the LL/LR hierarchy: it is top-down, LL family, and neither LL(1) nor any fixed LL(k). The honest description is recursive descent with bounded local backtracking. The parser walks the token vector once, left to right, and rewinds at exactly four places in ten and a half thousand lines, each a short speculative probe that restores the position on failure. Because it memoizes nothing, it is not a packrat or PEG parser; because it builds no parse forest, it is not GLR or Earley. Ambiguity is resolved where it is met, not afterwards.

The pass structure

The staging is mostly as plain as the one-liner suggests. BEGIN, constant, use and no all become AST nodes that the interpreter acts on later; named subs are hoisted, but by the interpreter, which is the reason a sub needs no forward declaration while an operator does. Nothing is memoized, nothing is revisited, and the AST that comes out is the only representation there will ever be.

Three things qualify that, and together they are the honest answer to is it one-pass?

The lexer pre-scans. Lexer::tokenize() reads the source for quote-word sub declarations before it tokenizes, as above. Nothing pre-scans it for operators — that is the pre-scan the limitation list further down is about, and the two are easy to conflate.

Two seams re-lex the tail. A use of a module that declares sub tr, or of a slang, rebuilds the token stream from the cursor on. The parse is still a single left-to-right walk; the tape under it was replaced mid-walk.

A slang runs user code during the parse. This is the one that changed. rakuppActivateSlang (src/MethodCallPart3.cpp) builds a scratch Interpreter with a compile-time $*LANG, runs the slang module for real, and keeps it alive alongside the parse; the grammar productions its roles override come back as seams, and the lexer then runs the slang's own token at the position it would itself have started a number, a value, an identifier, a sigilless variable, a pointy block or a routine declarator. src/Slang.h is the enumeration. Until September 2026 this chapter said flatly that no user code runs during the parse; for everything that is not a slang, it still does not.

One further pass sits between the parser and every back end, and it is not part of the parse at all: DeclCheck (Chapter 38) asks whether each variable the unit mentions is declared anywhere in its lexical chain, and refuses the program before it starts. It is a gate rather than an analysis — it computes nothing a later stage consumes, beyond the list of no strict names the native back end needs in order to emit no local for them.

The part with no textbook box

The central case is the operator table, mutated while parsing. Declaring sub postfix:<!> registers a new operator with its own precedence and associativity, taken from is tighter, is looser and is equiv, and tokens after that point parse differently from tokens before it.

That single fact puts the front end outside the LL/LR classification entirely. Both presuppose a grammar fixed before parsing starts; no static table can be built for a grammar that is not fully known until the program has been read. The nearest term in the literature is an adaptive, or extensible, grammar.

In practice, top-down parsing with a live operator table is the only tractable way to implement one, which is why every language that lets users declare operators — Raku, Haskell, Prolog, Agda — has a top-down front end. The choice of recursive descent here was not made in spite of Raku's grammar. It was made because of it.

The extension mechanism is deliberately narrow, and Chapter 6 is about exactly how narrow. use Foo does not parse the module at compile time: the parser text-scans the module source for declarations of infix:<…> and its relatives, and registers those names so the importing file can parse them. That is lexical bookkeeping, not execution — the distinction Chapter 32 returns to.

One kind of module is the exception. If the source registers a slang — use Slangify, or a direct define_slang — bookkeeping cannot answer what it registered, so the module is run, in an interpreter of its own, to find out. That is a second adaptive mechanism sitting beside the operator table, and it is narrower than Rakudo's in a specific way. Rakudo mixes a role into the grammar and every production in it is fair game; here only a production with a seam can be overridden at all, and a slang that reaches past them — one that overrides a host production, or that changes only the actions — is refused by name rather than silently half-applied.

The regex engine, classified separately

Part V is a second compiler inside the first, and it belongs in a different box.

The matcher is a backtracking recursive-descent walker over a compiled node tree — the Perl and PCRE lineage, not the Thompson and RE2 lineage. It has to be. Raku regexes carry captures, embedded code blocks, assertions and recursive subrule calls, none of which a pure DFA can express, and a grammar is a class whose methods are regexes. Chapter 21 is the matcher; Chapter 22 is what a grammar adds on top of it.

A Thompson NFA appears in exactly one role. Longest-token matching has to answer "how far can each alternation branch's declarative prefix reach?", and the NFA answers it in one linear, execution-free scan of the input. It never matches on behalf of the engine — the real backtracking matcher then runs on the branches it ranked. It is also not yet the default: the shipped ranker probes each branch for its greedy full-match end, and the NFA ranker is behind an environment variable, for reasons Chapter 23 sets out along with the phase plan for flipping it.

So the engine is a backtracking matcher that borrows one automaton for one question. Describing it as "an NFA engine" would be wrong in both directions.

The back end: there is no IR

Here the classification is unusually short, because a whole layer is missing. There is no intermediate representation: no bytecode, no three-address code, no SSA, no control-flow graph, no register allocation, no lowering pass. The AST is the sole representation the whole way through. That is what makes this an AST interpreter rather than a compiler in the Dragon-Book sense, for three of its four modes:

Only --exe is a compiler proper, and even there the optimizer is AST-level pattern matching at emit time: direct-arity calls, inlined int64 arithmetic, guarded native-int expression lanes. Those are local, peephole-class transformations by any standard classification (Chapter 27). Everything classical — inlining, constant propagation, loop transforms, instruction scheduling, register allocation — is delegated to the host C++ compiler, which is the whole point of emitting C++ instead of machine code. Chapter 26 is about what that delegation buys and what it costs.

The interpreter's own speed work sits in the same place on the map. Node specialisation (Chapter 19) caches a decision on the syntactic shape of a node; it is a fast path on a tree walk, not a compilation step, and no amount of it turns the tree walk into something with an instruction stream.

Since this chapter was written, one exception has landed, and the paragraph above has to be qualified. Two opt-in backends compile hot loops during the run: --jit, through the same C++ emission --exe uses, and --cnp, by copying machine-code snippets out of the binary and patching them. The second lowers the loop to a flat list of register ops first — an intermediate representation, one loop wide, built and thrown away in about 15 µs, with no pass of any kind run over it. The rest of the classification stands: the AST is still the sole representation of your program, and neither back end is reached unless it is asked for. Chapter 44 is both of them end to end.

What it is not

Stated plainly, since these are the usual guesses:

Compared with three others

Two rows of that table are worth a sentence each.

Raku++ shares its front end row with a production C++ compiler. Hand-written recursive descent is not a shortcut taken by small projects; it is what industrial compilers for languages with real syntax actually use, because generated parsers are hard to give good errors and impossible to give context-sensitivity.

And it shares its grammar not fixed column with Rakudo alone — which is a property of the Raku language rather than a choice either implementation made. Any Raku implementation has to solve it. The two solved it differently, and the difference explains most of what Chapter 6 says is missing here: Rakudo's front end is a Raku grammar, so running the program's own code during the parse is its ordinary case. Here it is the exception, bought at six named seams and two modes, and everything outside them parses with no user code running at all.

Honest limitations

Nearly every front-end limitation in this book is downstream of the classification above, and worth reading as a consequence rather than a bug list:

• Operators must be declared before use. The only way the parser learns of one is by reaching its declaration, and nothing pre-scans the file for operators — the lexer's own pre-scan looks for quote-word subs and nothing else. Subs are exempt only because the interpreter hoists them.
• No macros, and slangs only where there is a seam. A macro needs user code to run during the parse and to yield the AST that replaces the call; the first half now exists and the second does not. A slang works only at the productions src/Slang.h enumerates: the eight self-contained ones run their own tokens, Tuxic runs as a pair of parser modes, and one that reaches past both is refused by name.
• Block versus hash stays a heuristic. It follows Raku's documented rules, but a case a backtracking full grammar would settle by trying both can still be decided wrongly here.
• No whole-program analysis. DeclCheck does walk the tree before execution, but it answers one question and hands the back end nothing to optimize with; with no IR, an --exe optimization still has to be expressible as a local rewrite during emission.

The other side of the ledger is the reason the design holds. One AST serves all five run modes with no lowering step between them, so a language feature is implemented once (Chapter 25). A parse error can point straight at a token, because there is no table-driven state to translate back into source. And there is exactly one implementation of the semantics — librakupp_rt.a — shared by the interpreter and by every binary it compiles.