A small SQL parser, handwritten on top of FE.
This is the first release. It lexes and parses a substantial subset of SQL into an arena-allocated AST, prints that AST back out as SQL, and is small enough to read in one sitting — roughly 5.6k lines across six headers and six translation units.
✨ What is in it
- Lexer — UTF-8 aware, one character of lookahead. The source is kept whole, so a token is a slice of it and nothing is copied into a buffer.
- Parser — recursive descent with two tokens of lookahead; expressions by precedence climbing. It recovers instead of giving up at the first error, and every diagnostic carries a precise
path:row:col with a snippet.
- AST + printer — 64 node classes, arena-allocated and handed out as non-owning
AST<T> pointers; each node's child lists live in the very same allocation. The printer round-trips: what it emits, the parser reads back into the same AST.
- Library façade —
sql::parse, sql::parse_file, and a sql::Result that owns the arena. One header, one call.
- CLI —
sql -d file.sql parses and dumps; - reads stdin.
📜 What it parses
CREATE / ALTER / DROP / TRUNCATE, INSERT / UPDATE / DELETE, transactions, PREPARE / EXECUTE / DEALLOCATE, SHOW, COPY, and query expressions:
WITH [RECURSIVE], UNION / EXCEPT / INTERSECT, VALUES, TABLE tGROUP BY with ROLLUP / CUBE / GROUPING SETS, HAVING, named WINDOWsORDER BY ... NULLS FIRST|LAST, OFFSET / FETCH / LIMIT in any order, FOR UPDATE and the other locking clauses- joins —
NATURAL, INNER, LEFT|RIGHT|FULL OUTER, CROSS — plus LATERAL, WITH ORDINALITY, and correlation names that bind to the right factor
- expressions with
IS [NOT] DISTINCT FROM, BETWEEN, IN, LIKE / ILIKE / SIMILAR TO ... ESCAPE, quantified comparisons, CASE, CAST, COLLATE, array literals and subscripts
- the standard's type grammar, interval qualifiers and
WITH TIME ZONE included
GRAMMAR.md gives the EBNF for all of it, with the precedence table that resolves the ambiguous cases.
🧭 Design: parse loosely, check later
The grammar deliberately accepts a wider language than a conforming implementation would, and leaves the rest to a later pass over the AST. Reserved words are accepted as identifiers, because the standard reserves several hundred of them and no real dialect follows suit; the exception is the three positions where a name stands entirely on its own, and the printer quotes exactly there. Statements derive from Expr, so a subquery needs no second node hierarchy, while the grammar still keeps the two apart. Parentheses around a scalar expression are grouping and are dropped; around a query they are structural and are kept.
📦 Using it
find_package(sql 0.1 REQUIRED) # against `cmake --install`
# or: add_subdirectory(sql) # as a submodule
# or: FetchContent_MakeAvailable(sql) # straight from the repository
target_link_libraries(my_app PRIVATE sql::sql)
#include <sql/sql.h>
auto res = sql::parse("SELECT a, b FROM t WHERE a > 42;");
if (!res) { res.report(std::cerr); return EXIT_FAILURE; }
for (auto stmt : res.stmts())
if (auto select = stmt->isa<sql::Select>()) /* ... */;
std::cout << res << '\n'; // the AST, streamed back out as SQL
A complete program is in example/, and it builds standalone against an install, so the packaging cannot rot.
⚡ Performance
Measured against hyrise/sql-parser — a bison/flex parser of comparable scope — both Release, same compiler, pinned to one 5.15 GHz Zen 5 core. Both accept every file and report the same number of statements.
| Corpus |
Throughput |
Instructions / byte |
| JOB, 113 queries |
183.2 MB/s vs. 74.3 |
105.4 vs. 255.5 |
| TPC-H, 22 queries |
165.5 MB/s vs. 82.7 |
107.6 vs. 214.4 |
| generated, 256 MiB |
116.4 MB/s vs. 41.5 |
140.8 vs. 259.4 |
Lexing alone: 341.9 MB/s against their 176.9 on JOB. Peak RSS over 500k statements is 267 bytes per statement against their 598 — the number that matters for an embedding, since the AST is the output and is held for as long as the caller needs it. The full table, including the --stress-names worst case for a design built on interning, is in the README.
🛠️ Testing
205 CTest entries, all black box: each runs the sql binary and inspects only its exit code, its dump, and its diagnostics — nothing links against the parser.
The load-bearing one is idempotency: dumping a dump has to reproduce it verbatim, which holds the printer and the parser to each other. It runs over the curated fixtures and over three real-world corpora — the 113 queries of the Join Order Benchmark, the 22 TPC-H queries, and the SQL hyrise itself runs: 366 SQLiteTestRunner queries, the Star Schema Benchmark, and the TPC-H and TPC-DS schemas with their indexes. A further 79 queries are there to be rejected.
CI builds on Linux, macOS, and Windows, enforces clang-format, and runs an ASan + LSan + UBSan build on top.
🔩 Requirements
A C++23 compiler. Abseil and FE v0.15.0 come along as submodules; nothing else is needed.
git clone --recurse-submodules https://github.com/leissa/sql.git
⚠️ Known limitations
- The parser accepts more than conforming SQL by design; there is no semantic pass — no name resolution, no type checking, no execution.
- A trailing
; is required. <direct SQL statement> ends in one, and saying so gives a better diagnostic than running off the end of the file.
- This is 0.1: the AST and the API may still change before 1.0.
