Parsing & Trees
From Text to Trees
Three artifacts, one pipeline: characters become tokens, tokens become a parse tree, and the parse tree is shaped into the tree your semantics will walk.
Concrete vs. Abstract Syntax Tree
A concrete syntax tree (CST) keeps every token, including punctuation; an abstract syntax tree (AST) keeps only the meaning — the “+” node, not the parentheses around it. DSLs almost always talk in ASTs.
Figure 1 — The AST encodes precedence: multiplication hangs below addition without any parentheses.
A Glimpse of IR
Some languages add a third tree, an intermediate representation (IR), optimized further before execution — the LLVM IR of Phase 3 is a mature example.
Parsing Strategies
Two families dominate, and both start from the grammar class you chose.
Recursive Descent
One function per nonterminal: each function reads its expected tokens and calls the functions of the symbols it contains. Simple, debuggable, and the only parser you can read without a table — the natural choice for DSL parse cores.
Bottom-Up / LR
The parser shifts tokens onto a stack and reduces them by productions when the right-hand side appears. Powerful and fast, but the generated tables hide the story; best kept for large or embedded grammars.
Choosing
For a DSL with fewer than thirty productions, hand-written recursive descent beats any generator on clarity and error messages. Generators win when grammar size or ambiguity risk outruns human patience.
Syntax Errors
The parser is the first place users hit failure; design it to be kind.
Location, Expectation, Recovery
Report the token offset and the phrase expected (from the grammar: “expected time after room”); then recover: skip to a synchronization token (a newline or keyword) so one error does not poison the whole file — the classic aid for batch users.
Bound the Damage
Cap error recovery (“too many errors, stopping”) to avoid a waterfall of clones after one mistake. Errors & Diagnostics, later in this phase, covers the full message design.
Example: A Mini Recursive-Descent Parser
Thirty lines of Python that parse the resolved arithmetic grammar into an AST — the same shape every later phase consumes. Python is this track’s teaching language because it is the most widely readable one, not because it is the standard for building compilers: production front ends usually start from a grammar and a generator (ANTLR) or from a language built for the job (Racket for language design, OCaml for a type-safe implementation) — covered in the DSL Implementation Languages phase.
The Parser (commented)
# parser.py — tiny recursive-descent parser: + - * / ( )
tokens = []; pos = 0 # token list from your lexer
def peek(): return tokens[pos] if pos < len(tokens) else ("EOF", "")
def eat(kn): # require the next kind, then move on
global pos
kind, val = peek()
if kind != kn:
raise SyntaxError(f"expected {kn}, found {val!r} at token {pos}")
pos += 1
return val
def expr():
node = term() # leftmost operand first
while peek()[0] in ("PLUS", "MINUS"):
op = eat(peek()[0]) # left-associative by iteration
node = (op, node, term()) # fold the tree to the left
return node
def term():
node = factor()
while peek()[0] in ("STAR", "SLASH"):
op = eat(peek()[0])
node = (op, node, factor()) # higher precedence, tighter bound
return node
def factor():
if peek()[0] == "NUMBER":
return ("num", int(eat("NUMBER")))
if peek()[0] == "LPAREN":
eat("LPAREN"); node = expr(); eat("RPAREN"); return node
raise SyntaxError(f"unexpected {peek()[1]!r}")
tokens = lex("1 + 2 * 3") # reuse the Syntax & Notation lexer
print(expr()) # ('+', ('num',1), ('*', ('num',2), ('num',3)))How to Read It
One function per nonterminal, one token of lookahead, and iteration where the grammar wrote { ... }. Precedence falls out of the call order: term binds tighter than expr, exactly as the grammar declared.
Next Steps
Continue Phase 1
With a tree in hand, meaning begins: Semantics & Scoping then Types & Values, and Phase 2 turns the tree into a running program.