Prologue: Why Does a Database Need a “Parser”?

To a database, the string SELECT * FROM users WHERE age > 18; is just a sequence of characters. The database neither “reads” English nor understands what SELECT means — it must first translate the string into a structured internal representation before it can optimize and execute anything.

That translation is done by the Parser, which sits at the very front of the database as its “syntax brain”:

┌─────────────────────────────────────────────────────────┐
│                The Journey of One SQL                    │
│                                                         │
│   "SELECT * FROM t1"  (string)                          │
│          │                                              │
│          ▼  ① Lexical Analysis (Lexer)                  │
│   [SELECT] [*] [FROM] [ID:t1]  (Token stream)           │
│          │                                              │
│          ▼  ② Syntactic Analysis (Parser)               │
│      Parse tree / AST  (structured tree)                │
│          │                                              │
│          ▼  ③ Semantic Analysis                         │
│   bind tables/columns, type checking, name resolution   │
│          │                                              │
│          ▼                                             │
│   query tree → optimizer → executor                    │
└─────────────────────────────────────────────────────────┘

This article does not pile up obscure jargon. Instead, following the thread of “what you must know to build a parser,” it strings together all the theoretical foundations and engineering knowledge into a single knowledge map. By the end, you should be able to read PostgreSQL’s gram.y, SQLite’s parse.y, or any SQL grammar file and understand what it is doing.

1. Formal Languages and Grammars: The “Rules of the Language”

The essence of a parser is using a formal set of rules to decide whether a string is a valid sentence and to recover its structure. Those rules are the Formal Grammar.

1.1 The Chomsky Hierarchy

Linguist Chomsky classified formal languages into four levels by expressive power, which conveniently maps to how hard they are to parse:

Key insight: SQL’s lexing belongs to Type 3 (regular), while its syntax belongs to Type 2 (CFG). That is precisely why a lexer can be a regex engine but the syntax parser needs a more powerful algorithm — they operate on different layers of language.

1.2 The Context-Free Grammar (CFG) Quadruple

A CFG can be written strictly as G = (V, Σ, P, S):

• V: Nonterminals — syntactic categories such as <select_stmt>, <expr>. They get expanded further.
• Σ: Terminals — the Tokens produced by the lexer, such as SELECT, *, ID, NUMBER. They are the leaves of the tree and cannot be split further.
• P: Productions — rewrite rules of the form A → α.
• S: Start symbol — the entry point of a sentence, e.g. <program>.

A snippet of SQL grammar:

select_stmt : SELECT target_list FROM table_ref
            | SELECT target_list FROM table_ref WHERE expr
target_list : '*'
            | column_list
column_list : column_ref
            | column_list ',' column_ref

Here select_stmt, target_list are nonterminals; SELECT, FROM, *, , are terminals (Tokens); select_stmt is the start symbol.

1.3 Derivation and Parse Trees

Starting from the start symbol and repeatedly replacing nonterminals using productions until only terminals remain is called a derivation. The structure it leaves behind is the parse tree:

            select_stmt
            /     |    \
      SELECT  target_list  FROM ...
                |
             column_list
             /    |    \
       column_list ',' column_ref
            |
        column_ref (t1)

Ambiguity means the same sentence can derive two different parse trees. For example 1 + 2 * 3 could group + first or * first — the grammar must fix a unique structure via “precedence/associativity,” otherwise the parser reports a conflict. This is exactly why SQL defines a huge precedence table (AND below OR, multiply above add).

2. Lexical Analysis: Cutting the Character Stream into “Words”

The parser does not consume raw characters. A Lexer / Scanner first cuts the character stream into a Token stream.

2.1 Principle: Regex → NFA → DFA → Lexer

Lexical rules are essentially regular expressions (Type 3). In practice, a compiler turns them into an efficient program like this:

1. Each regex rule → an NFA (Nondeterministic Finite Automaton)
2. Multiple NFAs merged → one big NFA
3. NFA subset construction → a DFA (Deterministic Finite Automaton)
4. DFA minimization → a state-transition table; just look up the table character by character

This is why lexer generators such as Flex and re2c run extremely fast: underneath, they are just a table-driven state machine.

2.2 What Kinds of Tokens Exist

For a database, common token categories:

• Keyword: SELECT, FROM, WHERE, JOIN …
• Identifier: table names, column names, aliases, e.g. users, age
• Operator / Punctuation: =, <, >, +, *, (, ,
• Literal: number 18, string 'alice', boolean TRUE
• Comment / Whitespace: usually discarded during lexing

2.3 The “Pitfalls” of SQL Lexing

SQL lexing is trickier than it looks — another reason you cannot simply “write a split()”:

• Case-insensitive: select, SELECT, SeLeCt are all the same keyword.
• Reserved vs non-reserved words: ORDER is reserved, but what if a user names a table order? Quoting it as "order" disambiguates — a joint lexer/parser challenge.
• Strings and escaping: in 'O''Brien', the '' means a single quote, and the lexer must assemble it into O'Brien.
• Multi-character operators: <=, <>, !=, :: must be recognized as one unit, not split into < and =.

A concrete example: SELECT 1+2 after lexing becomes:

[SELECT] [NUMBER:1] [+] [NUMBER:2]

Note: the lexer only “splits and classifies.” It has no idea that 1+2 is an expression — that is the parser’s job.

3. Syntactic Analysis: Stringing “Words” into “Sentence Structure”

The parser (Parser) reads the token stream, decides whether the sentence is valid per the grammar, and builds the structure. This is the heart of a parser and the richest in theory. Two major schools:

3.1 Top-Down: LL(k) and Recursive Descent

The idea is to start from the start symbol and top-down try to match the input, as if guessing “which sentence pattern fits.” LL(k) means: scan Left-to-right, build the Leftmost derivation, look ahead k tokens.

Hand-written recursive descent is just one function per nonterminal:

// Pseudocode: recursive descent parsing a SELECT statement
ASTNode* parse_select_stmt() {
    expect(SELECT);
    ASTNode* targets = parse_target_list();  // recurse into target_list
    expect(FROM);
    char* table = expect_id();
    return make_select(targets, table);
}

The fatal problem — left recursion:

expr : expr '+' term    // left recursion!
     | term

Hand-written recursive descent hits expr and immediately calls expr again — infinite recursion / stack overflow. The fix is “left-recursion elimination,” but it changes associativity and ugly-fies the grammar. For SQL, where expression lists are extremely long, this is painful.

3.2 Bottom-Up: The LR Family

The other school is bottom-up: start from tokens, repeatedly reduce a “matched fragment” into a nonterminal, like playing a match-three game, until you reduce back to the start symbol.

LR means scan Left-to-right and do the reverse of a Rightmost derivation. It evolved through four tiers:

LALR(1) drives parsing with two tables:

• ACTION table: given current state and current token, Shift or Reduce
• GOTO table: which state to jump to after a reduction

Shift/Reduce conflict / Reduce/Reduce conflict: when a table cell has two actions, the grammar is ambiguous or needs precedence to disambiguate. This is exactly where writing SQL grammars costs the most effort.

3.3 Why SQL Almost Always Chooses LALR(1)

Recall the left-recursion problem from 3.1: SQL is keyword-driven and full of left recursion —

• Expressions a + b + c + ... are most naturally written with left-recursive grammar;
• SELECT lists, multi-table FROM joins, nested subqueries are all “a chain of homologous elements”;
• Keywords (SELECT/FROM/WHERE) provide an extremely strong lookahead signal, so LALR(1)‘s single-token lookahead resolves the vast majority of ambiguities.

That is why MySQL (bison), SQLite (Lemon), CockroachDB / TiDB (goyacc), DuckDB (fork of libpg_query), and PostgreSQL (bison + gram.y) all chose the LALR(1) family. For the history and trade-offs behind this, see the blog Why LALR(1)?.

3.4 Walkthrough: What Happens in the Stack for SELECT * FROM t1

From an LALR(1) bottom-up perspective, a simplified demo (stack holds “state|symbol”):

Remaining input: SELECT * FROM t1 $
Stack:                    Action
─────────────────────────────────────
[ ]                       Shift SELECT →
[0|SELECT]                Reduce: enter select start
[0|SELECT][s1]            Shift *       →
...                       Shift FROM    →
...                       Shift ID(t1)  →
[ ... | FROM | t1 ]       Reduce: table_ref → table
[ ... | FROM | table ]    Reduce: select_stmt done ✓

The intuition: the parser “eats” tokens onto the stack, and at the right moments folds a segment at the top into a higher-level syntactic structure, eventually folding everything into a complete query tree.

4. From Parse Tree to AST: Semantic Actions

The parse tree produced by syntactic analysis draws every nonterminal and every punctuation mark — very bloated. In practice we build a leaner Abstract Syntax Tree (AST) — keeping only the “meaningful skeleton”:

Parse tree (verbose)          AST (lean)
select_stmt                   SelectStmt
├ SELECT                      ├ target: Star
├ target_list                 └ from: Table(t1)
│ └ '*'
├ FROM
└ table_ref
  └ ID(t1)

In yacc/bison, semantic actions build the AST at reduction time:

select_stmt
  : SELECT target_list FROM table_ref
    { $$ = make_select($2, $4); }   /* $$ is result, $2/$4 are child nodes */
;

$$ is the attribute produced after this rule reduces (here an AST node); $1, $2… are the child nodes at each position. This is “syntax-directed translation” — parsing and tree building happen in the same pass.

5. Semantic Analysis: Parsing Must Also “Understand”

Syntactically correct ≠ semantically correct. SELECT age FROM users is syntactically fine, but if table users does not exist, or age is not its column, it is a semantic error. This stage usually follows parsing immediately, done by the semantic analyzer, which relies on two foundations:

5.1 Symbol Table and Scope

Semantic analysis needs a Symbol Table recording “currently visible tables, columns, aliases, types.” SQL scope is nested: WHERE sees table aliases introduced by FROM, and a subquery introduces its own scope.

5.2 Context-Sensitive: Same Name, Different Meaning

A CFG (Type 2) cannot express rules like “an identifier must be declared before use” — that belongs to Type 1 (context-sensitive). So parsers typically handle it this way:

• The lexer/parser swallows users as a meaningless ID;
• The semantic stage then consults the symbol table to decide whether it is a “table name,” a “column name,” or an “alias”;
• If none match → report a semantic error.

For example, a in SELECT a FROM t is perfectly valid syntactically; only by combining with table t’s schema can we know it is a column. This is Name Resolution, the core source of a parser’s “intelligence.”

5.3 Type Checking

Once age is known to be INT, age > 18 is legal; age > 'abc' is a type mismatch. Type inference and checking also happen in the semantic stage, feeding critical information to the optimizer later.

6. Error Handling and Recovery

A production parser cannot crash on the first error. It needs Error Recovery to keep going and report multiple errors at once. Classic strategies:

• Panic Mode: on error, discard tokens until a “synchronizing symbol” (e.g. ; or FROM) is found, then restart. Simple and most common.
• Error Productions: explicitly write “common wrong forms” into the grammar for friendly messages. For example, PostgreSQL’s gram.y uses the error placeholder:

insert_target_list
  : insert_target_list ',' insert_target_el
  | insert_target_el
  | /* empty */
  | insert_target_list ','   /* allow trailing comma but warn */
    { $$ = $1; ereport(WARNING, ...) }
;

• Phrase-level Recovery: locally fix (insert a missing )); more precise but harder to write.

7. Engineering Choices: Tools and Practice

Theory meets engineering with these mainstream tools:

A quick summary of SQL parsing “gotchas”:

1. Keyword conflicts: new versions introduce keywords like WINDOW, LATERAL, which may suddenly break old queries using those words as column names — hence reserved vs non-reserved splits.
2. Grammar conflicts: every new rule must be checked with bison -v for new shift/reduce or reduce/reduce conflicts.
3. Performance: parsing is on the critical path of every SQL statement and must be fast; LALR table-driving + regex DFA are designed exactly for this.
4. Preprocessing: parameterized queries ($1, ?) need special lexing handling to avoid re-parsing.

8. Knowledge Map Summary

If you want to design a database parser from scratch, you need to build knowledge along this chain:

① Formal language theory
   ├ Chomsky hierarchy (regular / CFG / context-sensitive)
   ├ CFG quadruple (V, Σ, P, S)
   └ derivation, parse tree, ambiguity & precedence
        │
② Lexical analysis
   ├ regex → NFA → DFA
   ├ token classification (keyword/identifier/operator/literal)
   └ SQL lexing pitfalls (case, quotes, escaping, multi-char operators)
        │
③ Syntactic analysis (core)
   ├ top-down: LL(k), recursive descent, FIRST/FOLLOW, left-recursion elimination
   ├ bottom-up: LR(0)/SLR/LR(1)/LALR(1), ACTION/GOTO tables
   ├ shift/reduce, reduce/reduce conflicts
   └ why SQL picks LALR(1) (left-recursion friendly + keyword-driven)
        │
④ Semantic actions & AST
   ├ parse tree vs AST
   └ yacc semantic actions: $$ = f($1, $2...)
        │
⑤ Semantic analysis
   ├ symbol table & scope
   ├ name resolution (context-sensitive)
   └ type checking
        │
⑥ Error handling & recovery
   ├ panic mode / error productions / phrase-level
   └ PostgreSQL gram.y in practice
        │
⑦ Engineering tools
   └ Flex/Bison, Lemon, ANTLR, goyacc, hand-written

In one sentence: a parser = regular lexing (Type 3) + LALR(1) syntax (Type 2) + semantic analysis (supplying the Type 1 context). The first two layers have mature theory and tools you can apply almost mechanically; the real craft of database design shows in semantic analysis, error recovery, and those SQL-specific engineering trade-offs.

Next steps: dive into lexical analysis (Flex in practice) and LALR(1) grammar construction (debugging bison conflicts).