droid
SQL Parser
SQL Front End · Stage 3 of 16

SQL Parser

Check that the tokens make a statement, and write down what it says

Read the token list from the lexer against a small grammar, and either produce a statement — its kind, its table, its columns, its values and its WHERE clause — or reject the line with one error that says what was expected and where.

Not run yet · 18 tests
Concepts in this stage
  • Grammar: a precise description of which token sequences are statements
  • Recursive descent: each rule of the grammar is read by its own piece of the parser, and rules reuse each other
  • One token of lookahead: the next token alone decides which way the parse goes
  • The AST: the statement as data, with no tokens, spaces or keywords left in it
  • Syntax before meaning: the grammar is what this stage requires; names and types are checked later
Where this stage sits in the engine
Talking to the user
REPL
Sessions
Printer
Server
Wire protocol
Understanding SQL
Lexer
Parser
Validator
Answering a query
Planner
Executor
Keeping changes safe
Transactions
Write-ahead log
Undo log
Lock manager
Read views
Storing rows
Row format
Slotted page
B+Tree
Reaching the disk
Pager
Database file
this stagebuilt alreadystill to comeA statement enters at the top; rows come back up.

Why this stage exists

The lexer turned a line into words. It did not care what order they came in: users from * select; was five perfectly good tokens. Now the order matters. The parser answers two questions about the token list: is this a statement? and, if it is, what does it say?

The second answer is the point. Everything after this stage — executing an INSERT, choosing a plan, walking the B+Tree — wants to know "which table, which columns, which values, which condition", and none of it wants to know that the values were in parentheses or that the keyword was typed in capitals. The parser produces that answer once, as a small structure called the abstract syntax tree: abstract because the punctuation is gone, a tree because a statement has parts and some parts have parts of their own.

The first answer is what makes the second safe. If the parser only produces a statement when the whole line fits the grammar, every later stage can trust what it is given, and none of them needs its own checks for a missing parenthesis.

The grammar

This is every statement the part accepts. Words in capitals are keywords, t and c are names, op is a comparison, v is a value.

INSERT INTO t (c, ...) VALUES (v, ...);
SELECT * | c, ... FROM t [WHERE c op v];
UPDATE t SET c = v, ... [WHERE c op v];
DELETE FROM t [WHERE c op v];
op is =, < or >
v is a NUMBER or a STRING

A few things are worth reading twice. INSERT always names its columns. , ... means one or more, never zero. The square brackets mean the WHERE clause is optional, and it is the same clause in all three statements that have it. Its comparison is always one of three symbols; the parser only records which one — comparing values is the job of whoever runs the statement. Note that SET always uses =: it assigns, it does not compare. And every statement ends with ;.

What the parser does

Each statement is a path through its rule. Here is SELECT, with the choices the parser makes by looking one token ahead:

Drawing the diagram…

Every arrow is one token the parser expects. A token that matches no arrow out of the current state is a syntax error at that token: select from users; has no arrow for from out of SelectList, so the error points at from: column 12 in ast select from users;, the ast prefix counted in.

Two arrows say not taken. The token that ends a list, or that shows there is no WHERE, is looked at but left in place for the next step to take. That is what one token of lookahead means.

The WHERE part of this picture is shared. UPDATE and DELETE reach Clause by their own path and leave it by the same one, which is why the clause is best written once.

The algorithm in words

1

Reading a statement

The parser walks the token list once, left to right, with one position that only moves forward. At each step it either accepts the token it expects and moves on, or stops with an error.

  1. 1.Tokenize the line first. If the lexer fails, report its error and stop: the parser never sees a line it cannot tokenize.
  2. 2.Look at the first token. If it is one of the keywords INSERT, SELECT, UPDATE or DELETE, read that statement's rule. If it is anything else, report error 00301 at that token.
  3. 3.Inside a rule, each step names what must come next: a particular keyword, a particular symbol, a name, or a value. If the next token is that, take it and move on. If not, report error 00302 at that token.
  4. 4.When a rule has a choice — * or a list of names, WHERE or the end — look at the next token to choose. Never take a token you have not decided to keep.
  5. 5.Every statement ends with ;. After it, the line must be over.
  6. 6.Invariants: the position never moves backwards; every token is either taken by exactly one step or is the one an error names; a statement is produced only if the whole line was taken.
2

Lists

Column lists, value lists and SET assignments are all the same shape: one item, then as many times as you like a comma and another item.

  1. 1.Read one item. A list is never empty, so a missing first item is an error at the token found instead.
  2. 2.While the next token is a comma, take it and read another item. A comma must be followed by an item.
  3. 3.The first token that is not a comma ends the list. It is not taken: the rule that called the list decides what must come next.
  4. 4.Keep the items in the order they were read.
3

WHERE, once, for three statements

SELECT, UPDATE and DELETE all end the same way: an optional WHERE clause, then ;. Write the clause once and have all three use it.

  1. 1.If the next token is not WHERE, the statement has no clause. That is not an error.
  2. 2.Otherwise take WHERE, then a column name, then an operator — =, < or > — then a value: a number or a string.
  3. 3.The clause stores its three parts. It never looks at whether the column exists.
  4. 4.Invariant: a statement with no WHERE clause produces no Where line — not an empty one.
4

Beyond the shape

The grammar is all this stage requires. One more check needs nothing but the statement itself.

  1. 1.In INSERT, the number of values must equal the number of columns. If not, report error 00303 at the ) that closes the value list.
  2. 2.Checks that need to know the table — its name, its columns, the type and range of each value — are required by later stages. Doing them here already is allowed; nothing in this stage tests them.
5

Build it in this order

Four steps, each reusing what the one before it built. Get one working end to end, with its ast output, before starting the next.

  1. 1.INSERT. No choices at all, only a fixed sequence and two lists. It is the easiest rule to get right and it exercises everything a list needs.
  2. 2.SELECT without WHERE. The first choice: * or a list.
  3. 3.WHERE, on SELECT. The first optional part.
  4. 4.UPDATE and DELETE, reusing WHERE and the list you already have. SET is a list whose items are c = v instead of a single name.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 3 and 5.

ast <sql> prints up to five lines, always in this order:

LineWhenHolds
Statement: INSERTalwaysINSERT, SELECT, UPDATE or DELETE
Table: usersalwaysthe table name as typed
Columns: [id, name]INSERT, SELECT, UPDATEINSERT: the column list. SELECT: the select list, [*] for *. UPDATE: the assigned columns
Values: [1, 'dan']INSERT, UPDATEthe values in the same positions as their columns
Where: id < 5only with a WHERE clausecolumn, operator (=, < or >) and value

A line is absent when the statement has no such part. Lists are separated by a comma and a space, inside square brackets. Strings are printed in single quotes and numbers as their digits, in Values: and in Where:. Names are printed as typed, and nothing is reordered.

Three codes belong to the parser. Like the lexer's, each error is one line ending with at col N, where N is the first character of the token the parser could not accept, counted from the start of the line with ast included; if the line ran out, it is one past the last character.

Error format
00301The first word is not INSERT, SELECT, UPDATE or DELETE — the column points at that word
00302Any other syntax error — the column points at the token found instead of the one expected
00303INSERT has a different number of columns and values — the column points at the ) that closes the value list

The message is yours to word. A failed parse prints the error line and no AST. A line the lexer rejects prints the lexer's error, with its code, and the parser does not run.

What you should see when done

droid session
Welcome to droid!
>ast insert into users (email, id) values ('[email protected]', 7);
Statement: INSERT
Table: users
Columns: [email, id]
Values: ['[email protected]', 7]
>ast select name, email from users where name = 'alice';
Statement: SELECT
Table: users
Columns: [name, email]
Where: name = 'alice'
>ast update users set name = 'a', email = 'b' where id = 3;
Statement: UPDATE
Table: users
Columns: [name, email]
Values: ['a', 'b']
Where: id = 3
>ast delete from users;
Statement: DELETE
Table: users
>ast launch from users;
[ERROR:00301] Unrecognized statement: launch at col 5
>ast select from users;
[ERROR:00302] Expected column list at col 12
>ast insert into users (id, name, email) values (1, 'danimar');
[ERROR:00303] Column count and value count must match at col 61
>ast select # from users;
[ERROR:00202] Unexpected character: # at col 12
>.exit
exiting.. good bye!

Things to notice. The INSERT kept email before id, because that is how it was typed. The DELETE printed two lines and nothing else — no empty Where:. The error for select from users; points at from, the token that was there instead of a column. And the last line never reached the parser: the lexer stopped it at #.

Common bugs in this stage

  • A statement is produced from part of the line. The parser reads select * from users and prints an AST without ever checking for ;. A statement ends at ;, and nothing may follow it.
  • The lookahead token is taken by accident. Reading the token that ends a list, or that turned out not to be WHERE, and then moving past it loses a token. Look first, take only what you keep.
  • An empty Where line. Printing Where: with nothing after it for a statement with no clause. The line is absent, not empty.
  • The count check lands in the wrong place. Columns and values are different lengths, but the error is reported at the ;, or the first mismatched value, or not at all. It is 00303, at the ) that closes the value list.
  • Two errors for one line. The lexer fails, and the parser then runs on what it has and reports an error of its own. The lexer's error ends the line.
  • Values lose their kind. 1 and '1' must print differently: the number bare, the string in quotes. Keep whether each value was a NUMBER or a STRING token.
  • The error column is the character, not the token. The column is where the unexpected token starts, not where the parser happened to be scanning, and it counts ast in.

Language notes

The page above is the same for every language. These are the only language-specific hints.

  • C: a statement holds lists of names and values of unknown length; either grow them with realloc or give them a fixed maximum and report an error beyond it, never write past the end. Decide who frees the token list and the statement, and free both on the error path too.
  • C++: a std::variant or a small struct with a kind field holds a value that is either a number or a string. std::vector for the lists.
  • Rust: an enum for the statement kinds and another for values makes the "no Where line" rule an Option. Result carries the error, code and column, out of every rule, and ? passes it up.
  • Zig: a tagged union(enum) for values and statements, and an error union for the rules. An ArrayList for each list; pass the allocator in and free on every path.

Checklist

One line per thing the tests check. The tags name the test cases.

  • INSERT prints Statement, Table, Columns and Values in the order typed
    ast-insert-valid · ast-insert-column-order
  • SELECT * prints Columns: [*] and no Where line
    ast-select-valid
  • SELECT with a column list and WHERE prints both, the string value in quotes
    ast-select-where
  • WHERE accepts < and > as well as =, and prints the operator as typed
    ast-where-comparison
  • Keywords match in any case, names print as typed
    ast-names-as-typed
  • UPDATE prints each assigned column in Columns and its value in Values, one or several
    ast-update-where · ast-update-multi-assign
  • UPDATE and DELETE without WHERE print no Where line; DELETE prints no Columns or Values
    ast-update-no-where · ast-delete-where · ast-delete-no-where
  • A statement that starts with an unknown word is 00301 at that word
    ast-unrecognized-sql
  • A missing ; is 00302 one past the end of the line
    ast-missing-semicolon
  • A missing select list, a missing WHERE value and a name in a value list are 00302 at the token found instead
    ast-select-missing-columns · ast-where-needs-a-value · ast-insert-invalid-id
  • Different numbers of columns and values is 00303 at the closing )
    ast-insert-missing-args
  • A line the lexer rejects prints the lexer's error and nothing from the parser
    ast-lexer-error-propagates
PreviousSQL LexerNextErrors as a System