Internals · Query EnginelexerparserASTrecursive descentprecedence

Tokens, Parse Tree, AST

Before a query can be planned it must become a tree. The lexer cuts text into tokens, a recursive-descent parser builds the tree by the grammar, and semantic analysis resolves every name against the catalog — the same front end every compiler has.

▶ InteractiveTry queries
Progress

Why this exists

The mechanism as the answer to a problem — read this before the name.

  1. Problem

    The engine receives SELECT name FROM users WHERE id = 42; as 42 characters. It needs to know which table, which column, which predicate — and it needs to reject SELEKT nmae FORM.

    ↓
  2. Naive solution

    Pattern-match the string: find the word after FROM, split on WHERE, split the rest on =.

    ↓
  3. Why it breaks

    Nested subqueries, AND/OR with precedence, parentheses, string literals that contain the word FROM, aliases, joins. String hacking has no notion of structure, and every new clause breaks the last hack.

    ↓
  4. Better idea

    Define the language as a grammar and build a tree that mirrors it. A tree knows that a = 1 AND b = 2 OR c = 3 groups as (a=1 AND b=2) OR c=3 because the grammar said so, once.

    ↓
  5. Internal mechanism

    A lexer produces tokens (keyword, identifier, literal, operator). A recursive-descent parser has one function per grammar rule; parseSelect calls parseFrom, which calls parseExpr, which climbs precedence levels. The result is an AST of tagged nodes. A binder then walks the AST and replaces names with catalog objects and types.

    ↓
  6. Trade-offs

    Hand-written parsers are fast and give good error messages but are large (PostgreSQL’s grammar is ~ 18,000 lines of yacc). The AST must be designed for what comes next — the planner — not for the text.

    ↓
  7. Real database

    PostgreSQL uses flex + bison (scan.l, gram.y) producing a raw parse tree, then parse_analyze() produces a bound Query. This platform’s engine is a hand-written recursive-descent parser in src/db/sql/parser.ts over a lexer in lexer.ts.

Choose your depth

The same mechanism at four altitudes. Start where you are; come back deeper.

Text becomes a tree

A query is a sentence in a small formal language. The parser is the part of the engine that reads that sentence and builds a diagram of it: SELECT at the top, the projection and the source table underneath, the predicate as a small subtree of its own.

Everything downstream — planning, optimization, execution — works on that diagram, never on the text again.

Tokens

The lexer reads the input one character at a time and emits tokens: the smallest units that mean something. SELECT name FROM users WHERE id = 42; becomes nine of them. Identifiers and keywords are the same token kind (ident) distinguished by one set lookup — select is in the keyword set, name is not — which is why keywords are reserved: the parser would otherwise have to guess whether select names a column. String literals keep their quotes stripped and their '' escapes resolved; numbers are recognised by shape; operators are matched longest-first so <= is one token, not two.

The lexer knows nothing about grammar. FROM WHERE SELECT 42 42 42 tokenises without complaint. Its only errors are characters it cannot classify (Unexpected character "@") and unterminated strings.

Token stream from this platform’s lexer
SELECT name FROM users WHERE id = 42;

kind     value     pos
ident    select    0     ← keyword (in KEYWORDS)
ident    name      7
ident    from      12    ← keyword
ident    users     17
ident    where     23    ← keyword
ident    id        29
op       =         32
number   42        34
punct    ;         36
eof                37

Recursive descent and precedence

A recursive-descent parser has one function per rule of the grammar, and each function consumes the tokens its rule describes, calling other rule functions for the parts it does not handle itself. parseStatement looks at the first token and dispatches to parseSelect; parseSelect expects SELECT, calls parseSelectList, then if it sees FROM calls parseFrom, then if it sees WHERE calls parseExpr. The call stack *is* the parse: when parseExpr is three levels deep inside parseFrom inside parseSelect, that is exactly where the expression sits in the tree.

Precedence is what makes expressions the interesting part. id = 42 AND active OR deleted must group as (id = 42 AND active) OR deleted, and price * 2 + tax as (price * 2) + tax. The parser encodes this as a ladder: parseOr parses parseAnd terms separated by OR; parseAnd parses parseNot terms separated by AND; below that comparison, then + -, then * / %, then unary minus, then primaries (literals, columns, parenthesised expressions, function calls, subqueries). Each level binds tighter than the one above it, so the tree comes out grouped correctly with no special-casing — the grammar was written once and the recursion does the rest.

The shape of this repo’s parser (src/db/sql/parser.ts), shortened
1class Parser {
2  private t: Token[]; private p = 0
3  constructor(sql: string) { this.t = tokenize(sql) }
4 
5  private at(value: string, kind = 'ident') { const tk = this.t[this.p]; return tk.kind === kind && tk.value === value }
6  private eat(value: string, kind = 'ident') { if (this.at(value, kind)) { this.p++; return true } return false }
7  private expect(value: string, kind = 'ident') { if (!this.at(value, kind)) this.fail(`expected "${value}"`); return this.t[this.p++] }
8 
9  parseStatement(): Statement {
10    if (this.at('select')) return this.parseSelect()
11    if (this.at('explain')) { this.p++; return { k: 'explain', analyze: this.eat('analyze'), stmt: this.parseStatement() } }
12    this.fail('expected SELECT, INSERT, UPDATE, DELETE, CREATE INDEX or EXPLAIN')
13  }
14 
15  parseSelect(): SelectStmt {
16    this.expect('select')
17    const columns = this.parseSelectList()
18    const from = this.eat('from') ? this.parseFrom() : undefined
19    const where = this.eat('where') ? this.parseExpr() : undefined
20    // GROUP BY, HAVING, ORDER BY, LIMIT follow the same pattern
21    return { k: 'select', core: { distinct: false, columns, from, where, groupBy: [] }, setOps: [], orderBy: [] }
22  }
23 
24  // precedence ladder: OR < AND < NOT < comparison < + - < * / < unary < primary
25  parseExpr(): Expr { return this.parseOr() }
26  parseOr(): Expr { let l = this.parseAnd(); while (this.eat('or')) l = { k: 'bin', op: 'or', l, r: this.parseAnd() }; return l }
27  parseAnd(): Expr { let l = this.parseNot(); while (this.eat('and')) l = { k: 'bin', op: 'and', l, r: this.parseNot() }; return l }
28  parseComparison(): Expr {
29    const l = this.parseAdditive()
30    for (const op of ['=', '<>', '<=', '>=', '<', '>'] as const) if (this.eat(op, 'op')) return { k: 'bin', op, l, r: this.parseAdditive() }
31    return l
32  }
33  parsePrimary(): Expr {
34    const tk = this.t[this.p++]
35    if (tk.kind === 'number') return { k: 'lit', v: Number(tk.value) }
36    if (tk.kind === 'string') return { k: 'lit', v: tk.value }
37    if (tk.kind === 'ident') return { k: 'col', name: tk.value }   // a.b handled with one more token of lookahead
38    this.fail('expected an expression')
39  }
40}

The AST

The output is an abstract syntax tree: abstract because it drops what the grammar needed but the meaning does not — parentheses, commas, the keyword FROM itself. What remains is structure. The root is a select node; its core holds the projection list, the source, and the predicate; the predicate is a bin node with operator = and two children, a column reference and a literal.

Every node in this platform is a tagged union with a k discriminator (src/db/sql/ast.ts), which is what lets the planner ask questions like "is this predicate col = lit on a column I have an index for?" with a two-line pattern match. The same tree, drawn the way the spec draws it:

The AST for SELECT name FROM users WHERE id = 42
SELECT
├── projection
│   └── name
├── table
│   └── users
└── predicate
    └── =
        ├── id
        └── 42

-- as this platform's parser produces it (parseOne):
select
└── core
    ├── columns[1]
    │   └── expr: col name="name"
    ├── from: table name="users"
    └── where: bin op="="
        ├── l: col name="id"
        └── r: lit v=42

Semantic analysis: the binder

The parser has produced a tree with names in it, and names are only text. Semantic analysis — the analyzer in PostgreSQL, the binder in SQL Server and most textbooks — walks the tree with the catalog and gives every name a meaning. users is looked up and becomes a table object: OID, column list, row count, indexes. name and id are looked up in that table’s columns and become attribute numbers with types. id = 42 is type-checked: int = int exists; int = text does not, and PostgreSQL says so rather than guessing (operator does not exist: integer = text).

The binder is where most "SQL errors" actually come from: relation "user" does not exist, column "nmae" does not exist, column reference "id" is ambiguous (two tables in FROM both have one), missing FROM-clause entry for table "o". Each is a lookup that failed. The binder also handles scope: a correlated subquery may reference columns of the outer query, so scopes form a chain and lookup walks outward, innermost first.

After binding, the tree is no longer about text. Every expression has a type; every column is a number; every table is an object with statistics attached. That is the input the planner needs — The Planner: Enumerating Ways to Answer starts from here.

Binding SELECT u.name, o.total FROM users u JOIN orders o ON o.user_id = u.id WHERE u.id = 42
scope (FROM):   u → users   (oid 16391, 900 rows, 8 columns)
                o → orders  (oid 16402, 3,200 rows, 6 columns)

u.name     → users.name    attnum 3  text
o.total    → orders.total  attnum 4  numeric
o.user_id  → orders.user_id attnum 2 int
u.id       → users.id      attnum 1  int
u.id = 42  → int = int  ✓  (operator oid 96)

errors this stage would raise:
  o.totl      column "o.totl" does not exist
  x.y         missing FROM-clause entry for table "x"
  id (bare)   column reference "id" is ambiguous

Key points

  • Lexer, parser, binder: three passes with three concerns — characters, grammar, meaning. Each catches only the errors its artefact can express.
  • Recursive descent maps grammar rules to functions; the call stack is the parse. Precedence is a ladder of functions, one per level, so grouping comes out right without special cases.
  • The AST drops syntax and keeps structure. Tagged nodes (k: 'bin', k: 'col') let the planner pattern-match predicates instead of parsing text.
  • The binder turns names into catalog objects and types. "Column does not exist" is a binder error, not a parse error — the text was grammatical.
  • This is the same front end every compiler has; the only difference is the target: a plan tree instead of machine code.

Tokens, parse tree, AST

Tokens, parse tree, AST
Edit the SQL. The lexer, the recursive-descent parser and the binder are the ones this platform's playground runs — the same machinery every language front end is built from.
SELECTkeywordnameidentFROMkeywordusersidentWHEREkeywordidident=op42number;punct

The lexer reads characters and emits tokens: keywords and identifiers (both lower-cased, one set-membership test apart), string and number literals, operators, punctuation. It knows nothing about grammar — FROM WHERE SELECT tokenises without complaint.

Tokens and AST are produced by this repo's lexer and parser. The binder here checks tables, columns, ambiguity and one type rule; a production binder also resolves functions, operators, collations and privileges.

Try it in the playground

SELECT name FROM users WHERE id = 42;
The lesson’s query. Then change name to nmae and read which stage rejects it — the binder, not the parser. →
EXPLAIN
SELECT u.name, o.total
FROM users u JOIN orders o ON o.user_id = u.id
WHERE u.id = 42;
Two scopes bound (u, o). Delete the final 42 to see a parse error with a position. →

When to use — and when not

Use it when
  • A hand-written recursive-descent parser fits when you own the grammar, want precise error messages, and the language is stable — SQL dialects, configuration languages, query DSLs.
  • A separate binder fits whenever names can be resolved only with external state (a catalog, a symbol table).
Avoid it when
  • A parser generator (yacc/bison, ANTLR) fits better when the grammar is huge and changes often — PostgreSQL’s 18,000-line grammar would be unmaintainable by hand.
  • A tree is overkill for a fixed-shape command language (GET key, SET key value): Redis parses with a few string operations and needs no AST.

Failure modes

  • Reserved words as identifiers: SELECT user FROM … fails because user is a keyword; quoting ("user") is the escape hatch.
  • Precedence surprises: WHERE a = 1 OR b = 2 AND c = 3 groups AND first; without parentheses the result is not what the author meant.
  • Implicit casts hiding type errors: WHERE id = '42' works in engines that coerce and silently disables index use in some others.
  • Ambiguous column after adding a column to a joined table: a query that bound fine yesterday fails today with "column reference is ambiguous".

Where you meet this

Back up to the practical layer, and across to the rest of Engineer Atlas.

Cross-domain bridges
← Inside the Query EngineThe Planner: Enumerating Ways to Answer →