How PostgreSQL Parses Queries and Constructs the Parse Tree

When a client application connects to a PostgreSQL server and transmits an arbitrary SQL string, the engine cannot immediately execute it. The database engine must first interpret what the query asks for, validate its syntax, and translate the text into an in-memory structural representation that downstream execution stages can process.

This initial phase is known as the Query Parsing Stage. PostgreSQL handles this stage using classic compiler construction techniques: lexical analysis followed by syntactic analysis, implemented via standard Unix tools: Flex and Bison.

---

1. The PostgreSQL Query Processing Pipeline

To understand where parsing fits, consider the complete lifecycle of a query within the PostgreSQL backend (postgres process):

Raw SQL String 
     │
     ▼
┌──────────────┐
│ Query Parser │ ─── Lexer (scan.l) & Parser (gram.y)
└──────┬───────┘
       │ (Raw Parse Tree)
       ▼
┌──────────────┐
│   Analyzer   │ ─── Semantic analysis, catalog lookups, types
└──────┬───────┘
       │ (Query Tree)
       ▼
┌──────────────┐
│   Rewriter   │ ─── Views, rule systems
└──────┬───────┘
       │
       ▼
┌──────────────┐
│   Planner    │ ─── Cost estimation, execution path selection
└──────┬───────┘
       │ (Plan Tree)
       ▼
┌──────────────┐
│   Executor   │ ─── Access methods, buffer pool, disk I/O
└──────────────┘

The parser is the gateway. All grammar definitions and lexical analysis rules for PostgreSQL live inside the source tree at:

src/backend/parser/

Within this directory, two primary files drive the syntactic engine:

1. scan.l: The lexical scanner specification (input to Flex).
2. gram.y: The formal grammar specification (input to Bison).

---

2. Stage 1: Lexical Analysis (scan.l)

The lexer (scanner) takes the raw stream of characters forming the SQL string and categorizes them into discrete semantic units called tokens.

Example Query

CREATE DATABASE students WITH encoding = 'UTF8';

The lexer processes this sequence character by character, matching substrings against regular expressions and generating a stream of tokens:

• CREATE (Keyword token)
• (Whitespace token / ignored)
• DATABASE (Keyword token)
• students (Identifier token)
• WITH (Keyword token)
• encoding (Identifier token)
• = (Operator token)
• 'UTF8' (String literal token)

Inside scan.l

In src/backend/parser/scan.l, regular expressions define how tokens are recognized:

• Whitespace & Newlines: Rules defining characters like spaces, tabs (\t), carriage returns (\r), and line feeds ( ).
• Hexadecimal literals: Regular expressions starting with 0x followed by [0-9a-fA-F]+.
• String Literals & Quotes: Pattern definitions distinguishing single-quoted strings from double-quoted identifiers.
• Keywords: Predefined keyword tables distinguishing reserved terms (SELECT, CREATE, TABLE, DATABASE) from generic column or table identifiers.

The lexer does not care about whether the query makes grammatical sense. It only cares about segmenting text into known token classes.

---

3. Stage 2: Syntactic Analysis (gram.y)

The parser consumes the stream of tokens produced by the lexer and verifies whether the sequence conforms to PostgreSQL’s formal SQL grammar rules.

Defined in src/backend/parser/gram.y, the grammar is written in Backus-Naur Form (BNF) compatible with Bison (a GNU LALR(1) parser generator).

Rules and Semantic Actions

Each grammar rule defines a syntactic pattern. When the parser encounters tokens that match a pattern, it executes an associated C code block called a semantic action.

Consider the grammar rule for CREATE DATABASE:

CreatedbStmt:
    CREATE DATABASE database_name opt_with createdb_opt_list
        {
            CreatedbStmt *n = makeNode(CreatedbStmt);
            n->dbname = $3;
            n->options = $5;
            $$ = (Node *) n;
        }
;

How Positional References Work

In Bison syntax, symbols in the rule are indexed using $1, $2, $3, etc.:

Index	Rule Symbol	Value in Example
$1	CREATE	Keyword
$2	DATABASE	Keyword
$3	database_name	"students"
$4	opt_with	WITH clause
$5	createdb_opt_list	List of options

When this production rule reduces:

1. makeNode(CreatedbStmt) allocates an in-memory C structure representing a CREATE DATABASE statement.
2. n->dbname = $3; binds the database name ("students").
3. n->options = $5; binds the parsed options list.
4. $$ = (Node *) n; returns the newly created AST node up to the parent rule.

---

4. Constructing Parse Tree Nodes (DefElem)

A grammar rule is often composed of smaller recursive sub-rules. For example, createdb_opt_list can expand into one or more option items:

createdb_opt_list:
    createdb_opt_items                      { $$ = $1; }
    | /* EMPTY */                           { $$ = NIL; }
;

createdb_opt_item:
    IDENT opt_equal DefArg
        {
            $$ = makeDefElem($1, $3, @1);
        }
;

When parsing encoding = 'UTF8':

1. IDENT matches encoding.
2. DefArg matches 'UTF8'.
3. makeDefElem() creates a DefElem (Definition Element) node containing a key-value pair (defname = "encoding", arg = "UTF8").
4. Multiple DefElem structures are collected into a PostgreSQL List structure and attached to the parent CreatedbStmt.

Resulting Parse Tree Structure

          ┌─────────────────────────┐
          │      CreatedbStmt       │
          ├─────────────────────────┤
          │ dbname: "students"      │
          │ options: [List]         │
          └────────────┬────────────┘
                       │
                       ▼
          ┌─────────────────────────┐
          │         DefElem         │
          ├─────────────────────────┤
          │ defname: "encoding"     │
          │ arg:     "UTF8"         │
          └─────────────────────────┘

The resulting tree is a raw Parse Tree (or Abstract Syntax Tree). At this stage, PostgreSQL has confirmed syntactic validity, but semantic validity has not yet been verified (e.g., whether the database already exists or whether UTF8 is a supported encoding).

---

5. From Flex/Bison to the Final Binary

Because PostgreSQL is written in C, the .l and .y domain-specific files cannot be compiled directly by standard C compilers like gcc or clang. They must first be transpiled into C source code.

scan.l  ──────( Flex )──────▶  scan.c
gram.y  ─────( Bison )──────▶  gram.c & gram.h

Inside src/backend/parser/Makefile, build recipes automate this translation:

gram.c gram.h: BISONFLAGS += -d
gram.c gram.h: gram.y
ifdef BISON
	$(BISON) $(BISONFLAGS) -o gram.c $< 
endif

scan.c: scan.l
ifdef FLEX
	$(FLEX) $(FLEXFLAGS) -o'$@' $<
endif

Build Flow

1. Flex reads scan.l and outputs scan.c (a deterministic finite automaton for token matching).
2. Bison reads gram.y and outputs gram.c (the parser state machine) and gram.h (the token definitions and symbol declarations).
3. The standard C compiler compiles scan.c, gram.c, and all other backend source files into object files (.o).
4. The linker bundles these objects into the final postgres server binary.

---

6. What Happens Next?

Once the parser completes its work, the raw parse tree is handed off to downstream subsystems:

1. Semantic Analysis (parse_analyze): Validates identifiers against system catalogs (e.g., verifying if referenced tables, columns, and types exist, and checking privileges).
2. Query Rewriter: Expands database views, handles security policies, and applies user-defined rewrite rules.
3. Query Planner / Optimizer: Evaluates physical access paths (index scans vs. sequential scans), calculates estimated costs, and produces a physical PlanTree.
4. Executor: Walks the plan tree and calls the storage engine to fetch, insert, or modify data.

---

7. Summary & Source Code Navigation

Understanding PostgreSQL internals becomes approachable once you know where to look:

Concept	Source File Location	Primary Tool
Lexical Rules	src/backend/parser/scan.l	Flex
Grammar & Productions	src/backend/parser/gram.y	Bison
AST Node Definitions	src/include/nodes/parsenodes.h	C Header
AST Node Allocation	src/backend/nodes/makefuncs.c	C Source
Parser Build Recipes	src/backend/parser/Makefile	Make

Whenever you want to understand how a specific SQL keyword, clause, or statement works in PostgreSQL, inspect gram.y to locate the production rule, see the corresponding AST node, and follow the node’s pointer down through the planner and executor.