Parsing SQL: Clause Structure and Expression Precedence

A database receives SQL as a string and must produce something a planner can reason about. The parser is the component that performs the first translation: bytes to tokens, tokens to a syntax tree. It is also the component most often misunderstood, because the tree it produces contains almost no semantics. Table names are still just strings, types are unknown, and nothing has been checked against the catalog. Everything that requires knowing what a name refers to happens after parsing.

That division of labour is forced by the language. SQL’s surface syntax depends on catalog contents in ways a context-free grammar cannot express, and its grammar is large enough that the standard’s own BNF is not usable directly as an LR grammar. The result is a parser that handles shape, plus a set of conventions about what shape means.

Lexing: keywords that are not keywords

The tokenizer has the first awkward job. SQL has hundreds of words that behave as keywords in some positions and as ordinary identifiers in others. YEAR, VALUE, NAME, TYPE, COMMENT, ACTION, and TEMP are all reserved in some products and unreserved in others; a column named year is legal in most systems, and a type named year may also be legal. The lexer therefore cannot decide token classes with a fixed table alone. Implementations keep a small set of reserved words that can never be identifiers, a larger set of type-function names and colourable keywords that the grammar resolves by context, and a fallback in which any word not reserved becomes an identifier.

Quoting cuts across this. "year" is always an identifier, never a keyword, and 'year' is always a string literal. The distinction matters because folding rules differ: unquoted identifiers are case-insensitive and are folded to lower case (or upper case, in products that follow the older convention), while quoted identifiers preserve case exactly. Two identifiers that look the same in a query can therefore refer to different objects.

Literal syntax adds more cases. A string literal may be preceded by a character-set introducer, an E prefix for backslash escapes, or a U& prefix for Unicode escapes. Numbers need a rule for the trailing-dot form: 1. is a valid numeric literal in the standard, so a lexer cannot simply require a digit after the decimal point, and the same rule determines how 1.e5 tokenizes. The exponent marker adds another decision, since 1e with no digits after it must be treated as an error rather than as the number one followed by an identifier. None of this is deep, but every one of these decisions is visible in error messages and in the behaviour of tools that split SQL statements on semicolons.

Length limits belong here too. PostgreSQL stores identifiers in a fixed-size field and truncates anything beyond 63 bytes, which is why two long generated column names can collide even though the parser accepted both. Products that allow longer identifiers still tend to impose a limit well below the theoretical maximum, and a parser that accepts an arbitrarily long name only moves the failure to the catalog.

Clause order is not evaluation order

SELECT appears first in the text and is evaluated nearly last. The grammar enforces one fixed clause sequence: WITH, then SELECT with its FROM and WHERE, then GROUP BY, HAVING, window specifications, then ORDER BY, then LIMIT or FETCH. The parse tree preserves that written order, but its meaning is defined by a different order: FROM produces rows, WHERE filters them, GROUP BY collapses them, HAVING filters groups, the select list computes output expressions, window functions run over the result, ORDER BY sorts, and the row limit truncates.

The mismatch explains several rules that otherwise look arbitrary. A select-list alias is not visible in WHERE, because the alias is defined at a stage that has not run yet. It is visible in ORDER BY in most products, because that stage is later, and the standard permits it there. HAVING may reference aggregates but WHERE may not, because aggregation has not happened when WHERE runs. A window function may not appear in WHERE for the same reason.

Some of these constraints are enforced by the parser, since they are pure syntax: an aggregate call inside WHERE can be rejected on sight, because the grammar knows the clause it is in. Others require the binder, since whether an expression is an aggregate depends on resolving the function name against the catalog.

Where the grammar is genuinely ambiguous

The most visible ambiguity is the comma in FROM. FROM a, b JOIN c ON ... could mean a cross product of a with the join of b and c, or the join of a, b with c. SQL resolves it by making JOIN bind tighter than the comma, which is a precedence rule the standard states in prose and implementations encode as grammar structure. The same issue appears with CROSS JOIN and with parentheses: (a JOIN b ON ...) JOIN c ON ... is fine, while a JOIN b JOIN c ON ... ON ... is a syntax error in most grammars because each JOIN needs its own condition.

BETWEEN has a similar trap. a BETWEEN b AND c AND d parses as (a BETWEEN b AND c) AND d only because the grammar gives BETWEEN higher precedence than AND. A grammar that treated all binary operators uniformly would make the AND inside BETWEEN compete with the trailing AND, and the expression would be ambiguous. NOT BETWEEN, IS NOT NULL, and NOT IN create a chain of prefix-operator cases that recursive-descent parsers handle with an explicit NOT prefix level.

Unary minus versus exponentiation is the classic arithmetic case. -2^2 evaluates to -(2^2) in products that give exponentiation higher precedence than unary minus, and to (-2)^2 in products that do not; the two answers differ by sign. SQL’s own grammar is silent on some of these orderings, and the standard instead constrains the result of expressions through typing rules rather than through a single precedence table.

The standard’s grammar is written in BNF with hundreds of productions and is not LALR(1) as written. Implementations either use a parser generator with precedence declarations and a handful of grammar hacks, or hand-write a recursive-descent parser. The hand-written route is more common in recent systems because it produces better error messages and allows context-sensitive decisions during parsing, such as whether a parenthesised list is a row constructor or a subquery.

Recursive descent and the expression grammar

A recursive-descent parser for expressions encodes precedence as a ladder of functions, one per level, each of which loops on operators of that level and calls the next level down for operands. This is the standard structure and it maps directly onto the precedence table.

def parse_expr(tokens, i, min_prec=0):
    left, i = parse_primary(tokens, i)          # literal, column, call, ( expr )
    while i < len(tokens) and tokens[i].kind == 'op':
        op = tokens[i]
        if op.prec < min_prec:                  # caller's level binds tighter
            break
        i += 1
        right, i = parse_expr(tokens, i, op.prec + (0 if op.right_assoc else 1))
        left = Node(op.name, left, right)
    return left, i

The min_prec parameter is what makes the ladder composable: a left-associative operator recurses with one level higher than its own, which forces a - b - c to group as (a - b) - c, while a right-associative one recurses at its own level. Parentheses simply call parse_expr with the minimum precedence and expect a closing token.

Two failure modes are worth knowing. Deeply nested parentheses or long operator chains consume stack proportional to nesting depth; a parser with no depth limit can be driven into a stack overflow by a hostile query, which is why production parsers cap expression depth. And a recursive-descent parser’s error messages are only as good as its recovery strategy: after an unexpected token, the parser must decide whether to report and stop or to skip to the next clause boundary. The first gives a precise position and no further information; the second gives more errors, some of them consequences of the first.

What the tree does not say

The output of parsing is a tree of nodes whose leaves are names and literals. SELECT name FROM t becomes a select node containing a target list with one column reference name, a from node containing one range variable t, and nothing else. Whether t is a table, a view, or a subquery; whether name exists; whether it is ambiguous; what type it has; and whether the query is legal at all are questions the tree cannot answer.

This is why the same statement can parse successfully and fail immediately afterwards. It is also why syntax errors and binding errors read so differently. The parser reports what it expected at a byte offset; the binder reports an unresolved name, usually with a hint about the closest match.

The next stage consumes this tree and produces a resolved, typed representation, which is the subject of name resolution and plan binding. Keeping the two stages separate has a cost: some errors are detected later than they could be, and the intermediate tree duplicates information the binder must reconstruct. The benefit is that the parser stays independent of the catalog, which allows it to be reused for prepared statements, for views stored as text, and for client-side tools that only need to understand statement shape. From there, the resolved tree is rewritten into relational algebra, described in logical plans and rewrite rules.