Bootstrapping
In compiler and parser theory, bootstrapping is the property where a tool can process its own input format — or, in the strongest form, where a compiler is used to compile itself.
rdp.js and self-description
rdp-gen reads grammar files (EBNF or ABNF) and generates TypeScript
recursive-descent parsers. The parsers it generates extend RDParser — and
so does the EBNF parser inside rdp-gen that reads those grammar files.
In other words: the grammar-file reader and the generated parsers are the same kind of object, built on the same base class. This means the EBNF format can be described using EBNF itself — the tool can describe its own input.
The EBNF meta-grammar
The EBNF format accepted by rdp-gen can be expressed as an ABNF grammar
(src/grammars/ebnf-meta.abnf):
; ISO 14977 EBNF meta-grammar written in ABNF.
; Describes the EBNF syntax accepted by rdp-gen (ISO 14977).
;
; Rules are terminated by ";". Concatenation uses ",". Alternation uses "|".
; Grouping uses "()", optional uses "[]", repetition uses "{}".
; n * P is counted repetition. A - B is the exception operator.
; Block comments (parenthesis-asterisk delimiters) are covered but do not nest.
;
; Test input: any valid ISO EBNF grammar, e.g.:
; Greeting = 'hello' | 'world';
Grammar = 1*Rule *ws
Rule = *ws Name *ws "=" *ws Body *ws ";"
Body = Sequence *(*ws "|" *ws Sequence)
Sequence = Term *(*ws "," *ws Term)
Term = Primary [*ws "-" *ws Primary]
Primary = "{" *ws Body *ws "}"
/ "[" *ws Body *ws "]"
/ "(" *ws Body *ws ")"
/ Integer *ws "*" *ws Primary
/ Literal
/ Name
Integer = 1*DIGIT
Literal = %x27 *SqChar %x27 / %x22 *DqChar %x22
SqChar = EscSeq / %x20-26 / %x28-5B / %x5D-7E
DqChar = EscSeq / %x20-21 / %x23-5B / %x5D-7E
EscSeq = %x5C (%x6E / %x74 / %x72 / %x5C / %x27 / %x22)
Name = NameF *NameR
NameF = ALPHA / "_"
NameR = ALPHA / DIGIT / "_" / "-"
ws = %x20 / %x09 / %x0A / %x0D / comment
comment = "(*" *nostar *( stars nostarparen *nostar ) stars ")"
stars = 1*"*"
nostar = %x09 / %x0A / %x0D / %x20-29 / %x2B-7E
nostarparen = %x09 / %x0A / %x0D / %x20-28 / %x2B-7E
This grammar validates the syntax of an EBNF grammar file, including (* ... *)
block comments and a trailing newline. Load it in the
playground via Load example → EBNF meta-grammar (bootstrapping),
compile it, then paste a small EBNF grammar into the test input to verify it
parses correctly:
A = 'hello' | 'world';
The ABNF meta-grammar
The ABNF format is self-describing — the grammar for ABNF can itself be written
in ABNF (src/grammars/abnf-meta.abnf):
; ABNF meta-grammar written in ABNF - self-describing
; Describes the subset of ABNF syntax used by rdp-gen.
;
; Covers: rule definitions (=), alternation (/), double-quoted string literals,
; zero-or-more (*X), one-or-more (1*X), optional groups ([...]), the DQUOTE core
; rule, and character-value rules (%xNN, %xNN-MM, %xNN.MM, %dNN, %bNN and their
; range/concatenation forms), ";" comments, and rules continued over several lines.
; A rule starts in column 0 (RFC 5234); a line that begins with whitespace continues
; the previous rule. Does not cover prose-val, "=/" or general n*m repetition.
;
; Because this grammar is itself written in ABNF and describes ABNF, it
; demonstrates the "self-describing" property of the grammar format.
; Feed this file to rdp-gen to produce a TypeScript parser that reads ABNF.
;
; Test input: any valid ABNF rule, e.g.:
; Greeting = "hello" / "world"
Grammar = *ws Rule *(*ws Rule) *ws
Rule = RuleName sep "=" sep Body
Body = Sequence *(sep "/" sep Sequence)
Sequence = Term *(sep Term)
Term = Rep Element / Element
Rep = ("1" "*") / "*"
Element = Group / OptGrp / CharVal / Str / RuleName
Group = "(" sep Body sep ")"
OptGrp = "[" sep Body sep "]"
CharVal = "%" ( HexVal / DecVal / BinVal )
HexVal = "x" HexCpnt ( "-" HexCpnt / *( "." HexCpnt ) )
DecVal = "d" DecCpnt ( "-" DecCpnt / *( "." DecCpnt ) )
BinVal = "b" BinCpnt ( "-" BinCpnt / *( "." BinCpnt ) )
HexCpnt = HEXDIG *HEXDIG
DecCpnt = DIGIT *DIGIT
BinCpnt = BIT *BIT
Str = DQUOTE *DChar DQUOTE
DChar = %x20-21 / %x23-7E
RuleName = ALPHA *( ALPHA / DIGIT / "-" / "_" )
ws = %x20 / %x09 / %x0A / %x0D / comment
comment = ";" *( %x09 / %x20-7E )
hch = %x20 / %x09
newline = [%x0D] %x0A
cnl = [comment] newline
sep = *hch *( cnl 1*hch )
What the meta-grammars cover
All four meta-grammars read real grammar files — their own source text included —
not just comment-free samples. They deliberately cover a subset of each format, and
differ from the hand-written EBNFParser / ABNFParser in two ways:
- Comments (
(* ... *)in EBNF,;in ABNF) are accepted, but EBNF comments do not nest. - ABNF rules follow RFC 5234 line structure: a line break followed by whitespace continues the rule, so an alternation can span several lines, and a rule starts in column 0. An indented rule after another rule is therefore read as a continuation of it, where the hand-written parser accepts it as a new rule.
ABNF's prose values, =/, and general n*m repetition are outside the subset.
Generating a grammar-file parser with rdp-gen
Because the meta-grammars above are valid grammar files, you can feed them directly
to rdp-gen. The repository includes a convenience script that generates all four
parsers in one step:
npm run build && npm run generate:metaThis writes four files into src/parsers/generated/ (which is git-ignored —
the files are generated artefacts, not source), covering all combinations of
"which format is described" × "which format the description is written in":
| Output file | Parser class | Grammar source | Written in |
|---|---|---|---|
ebnf-in-ebnf-parser.ts | EBNFInEBNFParser | ebnf-meta.ebnf | EBNF (self-describing) |
ebnf-in-abnf-parser.ts | EBNFInABNFParser | ebnf-meta.abnf | ABNF |
abnf-in-ebnf-parser.ts | ABNFInEBNFParser | abnf-meta.ebnf | EBNF |
abnf-in-abnf-parser.ts | ABNFInABNFParser | abnf-meta.abnf | ABNF (self-describing) |
These files are compiled to dist/ as part of the normal npm run build step —
they are picked up automatically because tsconfig includes all of src/**/*.ts.
To generate a single parser manually (for example, with --observable for
tracing support):
rdp-gen src/grammars/ebnf-meta.abnf \
--parser-name EBNFInABNFParser \
--observable \
> src/parsers/generated/ebnf-in-abnf-parser.tsThe resulting EBNFInABNFParser class is an RD parser that reads EBNF grammar
files — generated by the very tool whose input format it describes.
The bootstrapping loop
- Stage 0 —
rdp-genships with a hand-writtenEBNFParserthat reads EBNF files. - Stage 1 — You use
rdp-gento compileebnf-meta.abnf, producing a generatedEBNFMetaParser. - Stage 2 —
EBNFMetaParsercan read EBNF grammar files. If you wired it intordp-genin place of the hand-written parser,rdp-genwould now be (partially) self-hosted.
The loop is closed in the test suite rather than in the CLI: rdp-gen itself still
uses the hand-written parsers. For each meta-grammar the tests run the loop end to end:
- Generate a parser from the meta-grammar.
- Have it read every grammar in the repository — itself included — as raw text.
- Convert the resulting parse tree into a
GrammarASTand check that it equals the AST the hand-written parser produces. - Generate a parser from that AST with
generateParserFromASTand check that the source is byte-for-byte whatgenerateParseremits when it reads the grammar directly.
Step 4 is a fixpoint: a grammar read by a generated parser rebuilds exactly the same parser.
Why this matters
The bootstrapping property is not just a curiosity — it validates the expressiveness of the grammar language. If EBNF can describe itself, it can describe any context-free language whose structure fits the LL(1) model.
It also makes the parser generator easier to test: any valid EBNF grammar string that passes the meta-grammar can be assumed to have correct syntax before being compiled, giving you an early validation layer.
The bootstrap tests verify all four combinations (EBNF-in-EBNF, EBNF-in-ABNF,
ABNF-in-EBNF, ABNF-in-ABNF) using generateParser directly — no interpreter involved.
src/__tests__/bootstrap.test.ts checks that each generated parser accepts and rejects
small samples; src/__tests__/bootstrap-loop.test.ts runs the full loop described
above.
Try it in the playground
- Open the playground.
- In the Grammar editor, choose Load example → EBNF meta-grammar (bootstrapping) and click Compile.
- In the Test input box, type a small EBNF grammar — for example:
Greeting = 'hello' | 'hi'; Name = Letter, {Letter}; Letter = 'a' | 'b' | 'c'; - The interpreter confirms the grammar text is syntactically valid EBNF.
- Click Debug to step through the parse trace and watch each production match character by character.