Syntax Analysis

Every SQL query you write must pass through a gauntlet of validation before a single row of data is ever touched. The database system scrutinizes your query at multiple levels, and the very first checkpoint is syntax analysis—the process of ensuring your query is structurally valid according to the rules of the SQL language.

When you execute a query like SELECT name FROM employees WHERE salary > 50000, the database doesn't immediately start searching through tables. Instead, it first breaks down your query into individual tokens, checks that these tokens are arranged according to SQL's grammar rules, and constructs a structured representation suitable for further processing.

This seemingly simple step is surprisingly sophisticated. Modern database systems process millions of queries per second, and each one must pass through syntax analysis with microsecond-level efficiency while providing clear, actionable error messages when something goes wrong.

Before diving into the details of syntax analysis, let's understand where it fits in the broader query processing pipeline. When a SQL query arrives at the database engine, it undergoes a series of transformations:

The Complete Query Processing Pipeline:

1. Query Receipt — The raw SQL string arrives from a client connection
2. Lexical Analysis — The string is broken into meaningful tokens
3. Syntax Analysis — Tokens are validated against SQL grammar rules
4. Semantic Analysis — Names are resolved and types are verified
5. Query Rewriting — The query may be transformed for optimization
6. Query Optimization — Multiple execution plans are evaluated
7. Query Execution — The optimal plan is executed
8. Result Return — Data is returned to the client

Syntax analysis encompasses steps 2 and 3 in this pipeline, though some systems combine them into a single parsing phase. The output of syntax analysis is typically a parse tree (also called Abstract Syntax Tree or AST)—a hierarchical data structure that represents the query's structure in a form suitable for subsequent processing.

Lexical analysis—also called tokenization or scanning—is the process of converting a raw character stream into a sequence of tokens. Each token represents a meaningful unit in the SQL language: a keyword, an identifier, a literal value, an operator, or punctuation.

Why Tokenization Matters:

Consider this SQL query:

SELECT employee_name, salary FROM employees WHERE department_id = 10

To a human, this is clearly a query that selects employee names and salaries from employees in department 10. But to the database, it initially arrives as a stream of 54 ASCII characters including spaces. The lexer's job is to transform this character stream into structured tokens that subsequent phases can process efficiently.

The lexer component (also called a scanner or tokenizer) reads characters left-to-right, identifies token boundaries, classifies each token, and passes the token stream to the parser.

Tokenization Example:

Let's trace how the lexer processes our example query character by character:

Understanding how lexers actually work reveals important details about SQL parsing behavior. Modern database lexers are typically implemented using one of two approaches:

1. Hand-Written Lexers: Some databases (notably PostgreSQL) use carefully hand-crafted lexers written in C. These offer maximum control over tokenization behavior and can be highly optimized for specific SQL dialects.

2. Generated Lexers: Other databases use lexer generators like Lex or Flex that create lexer code from a declarative specification. This approach is faster to develop and easier to maintain.

Regardless of implementation approach, all lexers must handle several challenging aspects of SQL tokenization:

Once the lexer produces a token stream, the parser takes over. The parser's job is to verify that the tokens are arranged according to the grammar rules of SQL and to build a parse tree representing the query's structure.

What is a Grammar?

A grammar is a formal specification of what constitutes a valid statement in a language. SQL grammars are typically specified using Backus-Naur Form (BNF) or a variant like Extended BNF (EBNF). These notations define:

• Non-terminals — Abstract syntactic categories (like <select_statement> or <expression>)
• Terminals — Actual tokens from the lexer (like SELECT or IDENTIFIER)
• Production Rules — Rules showing how non-terminals expand into sequences of terminals and non-terminals

Let's look at a simplified excerpt from an SQL grammar:

Grammar Complexity:

The actual SQL grammar is vastly more complex than this excerpt. The SQL:2016 standard grammar has hundreds of production rules covering:

• All DML statements (SELECT, INSERT, UPDATE, DELETE, MERGE)
• All DDL statements (CREATE, ALTER, DROP for tables, indexes, views, procedures, etc.)
• Transaction control (COMMIT, ROLLBACK, SAVEPOINT)
• Session settings and pragmas
• Procedural extensions (CASE, IF, LOOP, etc.)
• Window functions, CTEs, lateral joins, and more

PostgreSQL's gram.y file (the grammar specification), for example, is over 15,000 lines of grammar rules. MySQL's grammar is similarly extensive. This complexity is why writing a complete SQL parser from scratch is a multi-month undertaking.

Database systems use various parsing algorithms, each with different tradeoffs. Understanding these helps explain why some SQL constructs parse successfully while others cause unexpected errors.

Bottom-Up Parsing (LR Parsing):

Most production database parsers use LR parsing or its variants (SLR, LALR). These parsers:

• Read tokens left-to-right
• Construct the parse tree from leaves up to root
• Use a parse table generated from the grammar
• Handle a broad class of grammars efficiently

The most common tool for generating LR parsers is Yacc (Yet Another Compiler Compiler) or its GNU equivalent Bison. PostgreSQL, MySQL, and many other databases use Bison-generated parsers.

Top-Down Parsing (LL Parsing):

Some databases and SQL parsers use LL parsing or recursive descent:

• Start from the grammar's start symbol
• Recursively expand non-terminals
• Match terminals against input tokens
• Often hand-written for more control

Recursive descent parsers are easier to understand and debug but may struggle with left-recursive grammars.

Parsing Complexity:

Both LR and LL parsing run in O(n) time where n is the number of tokens. This linear complexity is crucial—imagine if parsing complexity were O(n²) for queries with thousands of tokens. For a SELECT with 500 columns (not unusual in data warehouses), quadratic parsing would be catastrophic.

The constant factors matter too. LR parsers using optimized table-driven approaches can parse tokens with just a few memory accesses per token. Combined with efficient lexing, modern databases can parse complex queries in microseconds.

One of the most visible aspects of syntax analysis is error detection and reporting. When you write malformed SQL, the parser must:

1. Detect that the query violates grammar rules
2. Identify the location of the error as precisely as possible
3. Generate a helpful error message
4. Optionally, attempt to recover and continue parsing

Types of Syntax Errors:

Error Message Quality:

The quality of syntax error messages varies dramatically between database systems. Good error messages:

• Point to the exact location of the error (line and column number)
• Explain what was expected vs. what was found
• Suggest possible corrections when unambiguous
• Avoid cascading errors (one mistake shouldn't produce 20 error messages)

PostgreSQL is generally praised for its error messages, while some databases produce notoriously cryptic errors. This quality difference stems from how much engineering effort is invested in the parser's error-handling routines.

As the parser validates the token stream against grammar rules, it simultaneously constructs a parse tree (also called an Abstract Syntax Tree or AST). This tree is the structured representation of the query that subsequent phases—semantic analysis, optimization, execution—will operate upon.

Parse Tree Structure:

The parse tree mirrors the grammar's hierarchical structure:

• Internal nodes represent grammar non-terminals (like SELECT_STATEMENT, WHERE_CLAUSE)
• Leaf nodes represent terminals (actual tokens from the query)
• Edges represent the "contains" relationship between grammar productions

Let's trace the parse tree for a simple query:

AST vs. Concrete Syntax Tree:

Database systems typically build an Abstract Syntax Tree (AST) rather than a full Concrete Syntax Tree (CST). The difference:

• CST includes every token, including punctuation, parentheses, and formatting
• AST retains only semantically significant elements, discarding syntactic sugar

For example, the parentheses in WHERE (a = 1) might appear in a CST but would be omitted from an AST since they don't affect meaning—the grouping is already captured in the tree structure.

AST Node Types:

Typical database AST nodes include:

• SelectStmt, InsertStmt, UpdateStmt, DeleteStmt — Statement types
• ResTarget — Items in a SELECT list
• RangeVar — Table references
• JoinExpr — Join expressions with conditions
• BoolExpr — AND/OR/NOT combinations
• OpExpr — Operator expressions (comparisons, arithmetic)
• Const — Literal values
• ColumnRef — Column references
• FuncCall — Function invocations
• SubLink — Subqueries