SQL Lexer

Read a line of SQL one character at a time and cut it into typed tokens — keywords, identifiers, numbers, strings and symbols — in the order they were typed, or reject it with one error that says where it went wrong.

Not run yet · 15 tests

Why this stage exists

Up to now a line was either a meta command or something the program could not recognise. From here on, the rest is SQL, and the first thing to do with SQL is not to understand it but to cut it up.

A line arrives as characters. select name from users where id=1; is thirty-four of them, and nothing in them says where one word stops and the next begins: sometimes a space does, sometimes an = does, and inside quotes a space does not. The parser in the next stage wants to ask questions like "is the next thing the keyword FROM?" and "is this a name?". If it had to answer them by looking at characters, every rule of the grammar would also have to know about spaces, capitals, quotes and digits. The lexer answers all of those questions once, at the door, and hands on a list of tokens: small records of a type and the text it was made from.

There is a second reason, and it shapes the error messages. The lexer is the last part of the program that sees the line as characters, so it is the one that can say where something went wrong. A parser can say "unexpected token"; only the lexer can say "column 17".

What the scanner does

The scanner is a small state machine. It starts between tokens; the first character of the next token picks a state; the state decides which characters still belong; the first one that does not ends the token and sends the scanner back to the start, without consuming that character.

Drawing the diagram…

Three things in the picture carry the whole stage. A token ends when the next character does not belong to it, not when a space appears, which is why id=1 is three tokens. The character that ended a word or a number is looked at again from Between, which is why nothing is lost between two tokens. And a string is the one state where whitespace, capitals and symbols stop meaning anything: 'Select * From' is one token.

Here is update users set name = '' where id=1; going through it:

Characters	State that read them	Token
`update`	Word	`[KEYWORD_UPDATE - update]`
`users`	Word	`[IDENTIFIER - users]`
`set`	Word	`[KEYWORD_SET - set]`
`name`	Word	`[IDENTIFIER - name]`
`=`	Between	`[SYMBOL - =]`
`''`	String	`[STRING - ]`
`where`	Word	`[KEYWORD_WHERE - where]`
`id`	Word, ended by `=`	`[IDENTIFIER - id]`
`=`	Between	`[SYMBOL - =]`
`1`	Number, ended by `;`	`[NUMBER - 1]`
`;`	Between	`[SYMBOL - ;]`

Keyword or identifier: read the whole word first

A word is classified only once it has been read to its end. selectivity begins with the letters of select, and a scanner that checks for keywords as it goes will emit a keyword and then an identifier ivity. Read the word, then compare the whole of it — ignoring case — with the nine keywords of this part. If it is one of them it is that keyword; if not, it is an identifier.

The lexer does not decide whether an identifier makes sense. users is a table, id is a column, and is neither in this part — all three are identifiers here. Whether they belong where they stand is the parser's question, and whether the table exists is asked even later.

The algorithm in words

Scanning a line

The scanner stands at a position in the line and repeats one decision until the line runs out. It never goes back, and it never looks at meaning: users from * select is tokenized as happily as a real query.

1.Skip whitespace. Whitespace separates tokens and is never part of one, except inside a string.
2.Look at the current character. It alone decides which kind of token starts here: a letter or _ starts a word, a digit starts a number, a single quote starts a string, one of the eight contract symbols is a symbol by itself.
3.Anything else is an unexpected character: report error 00202 with its column, and stop.
4.Read the token to its end, record its type and its text, and continue from the first character after it.
5.When the position reaches the end of the line, the list is complete. There is no end-of-input token to add.
6.Invariants: the tokens come out in the order their first characters appear in the line; every character is either whitespace, part of exactly one token, or the one character an error names.

Where each kind of token ends

The start is decided by one character; the end is decided by the kind. Each rule is 'keep going while the next character still belongs'.

1.A word goes on while the next character is a letter, a digit or _. A symbol, a quote, whitespace or the end of the line ends it — no space is needed, so select*from is three tokens.
2.A number goes on while the next character is a digit. This part only ever needs whole numbers; reading decimals or a leading minus as well is allowed, and not required.
3.A string goes on until the next single quote, which ends it and is not part of the text. The text is everything in between, spaces and capitals included; two quotes with nothing between them are a string of length zero.
4.If the line ends before the closing quote, report error 00201 at the column of the opening quote, and stop.
5.A symbol is always one character long.
6.Invariant: no token is ever empty, except the empty string, and no two tokens overlap.

Keyword or identifier

Only once a word has been read to its end do you ask what it is.

1.Compare the whole word, ignoring case, with the nine keywords of this part: select, insert, into, values, from, where, update, set, delete.
2.If it equals one of them, it is that keyword, and its type is KEYWORD_ followed by the keyword in capitals.
3.Otherwise it is an identifier — a table name, a column name, or a word the parser will reject later. That is not the lexer's problem.
4.In both cases the token's text is the word exactly as typed. Case-insensitive matching decides the type; it does not rewrite the text.
5.Invariant: a word that merely starts with a keyword, like selectivity or fromage, is an identifier, because the comparison is with the whole word.

Reporting

The tokenize debug command prints the list, or the error, and nothing in between.

1.Tokenize the whole line first, and print only when it succeeded: one line per token, in order.
2.On an error, print the one error line and no tokens, not even the ones read before the error.
3.The column counts from the first character of the line, tokenize included, starting at 1.
4.Invariant: after an error, the next line starts from nothing — no token of a failed line is ever printed later.

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 4.

tokenize <sql> prints one line per token, [<TYPE> - <text>], in the order the tokens appear in the line:

Type	What it matches	Example
`KEYWORD_<WORD>`	one of `select insert into values from where update set delete`, any case	`[KEYWORD_SELECT - SELECT]`
`IDENTIFIER`	a letter or `_`, then letters, digits and `_`	`[IDENTIFIER - user_1]`
`NUMBER`	one or more digits, nothing else	`[NUMBER - 42]`
`STRING`	`'...'` on one line, no escape sequences; the text is what is between the quotes	`[STRING - Dan Mar]`
`SYMBOL`	exactly one of `, ( ) ; = * < >`	`[SYMBOL - <]`

The text is always the token as typed. A keyword keeps its case: the type is in capitals, the text is not rewritten. A string's text leaves the quotes out, so the empty string prints as [STRING - ].

Some edges, because the tests visit them:

Whole numbers are enough. Nothing in this part uses decimals or negative literals, and no test sends them. If your lexer reads 1.5 or -1 as a number, that is fine; if it reports 00202 at the . or the -, that is fine too. Decide what 1.2.3 means before you accept dots at all.
Digits then letters are two tokens. 1abc is [NUMBER - 1] then [IDENTIFIER - abc]. A number ends at the first character that is not a digit.
A string ends at the first quote. There is no way to put a quote inside a string yet: 'it''s' is the two strings it and s.
No end-of-input token. tokenize with nothing after it prints nothing at all.

Two conditions are errors, each with its own code. An error is one line and a lexer error ends with at col N, the 1-based column counted from the start of the line — tokenize included:

Condition	Output	The column points at
a string with no closing quote	`[ERROR:00201] <message> at col N`	the opening quote
a character no token can start with	`[ERROR:00202] <message> at col N`	the character itself

The message between the code and at col is yours to word. A failed tokenize prints the error line and no tokens, not even those it read before the error, and the session carries on.

What you should see when done

droid session

Welcome to droid!
>tokenize select * from users where id = 1;
[KEYWORD_SELECT - select]
[SYMBOL - *]
[KEYWORD_FROM - from]
[IDENTIFIER - users]
[KEYWORD_WHERE - where]
[IDENTIFIER - id]
[SYMBOL - =]
[NUMBER - 1]
[SYMBOL - ;]
>tokenize UPDATE users SET name = 'Dan Mar' WHERE id=1;
[KEYWORD_UPDATE - UPDATE]
[IDENTIFIER - users]
[KEYWORD_SET - SET]
[IDENTIFIER - name]
[SYMBOL - =]
[STRING - Dan Mar]
[KEYWORD_WHERE - WHERE]
[IDENTIFIER - id]
[SYMBOL - =]
[NUMBER - 1]
[SYMBOL - ;]
>tokenize select selectivity from users;
[KEYWORD_SELECT - select]
[IDENTIFIER - selectivity]
[KEYWORD_FROM - from]
[IDENTIFIER - users]
[SYMBOL - ;]
>tokenize insert into users values (1, 'danimar);
[ERROR:00201] Unterminated string literal at col 39
>tokenize select # from users;
[ERROR:00202] Unexpected character: # at col 17
>.exit
exiting.. good bye!

Things to notice. UPDATE and SET kept their capitals, and id=1 came apart without a space. selectivity stayed one identifier. The unterminated string is reported at column 39, where its quote opened, and the first three tokens of that line were never printed. And two errors in a row did not end the session.

Common bugs in this stage

Keywords matched as prefixes. selectivity comes out as [KEYWORD_SELECT - select] and [IDENTIFIER - ivity]. Read the whole word, then compare.
The keyword's text is rewritten. Lowercasing the word to compare it and then printing the lowercased copy turns UPDATE into update. Compare a copy, print the original.
The character that ended a token is lost. In id=1, the = ends the identifier. If the scanner steps past it while finishing id, the = never becomes a token. The character that ends a word or a number is the start of whatever comes next.
Tokens only split on whitespace. Splitting the line on spaces first and classifying the pieces makes select*from one unknown word. Spaces are one way a token ends, not the only one.
Tokens printed as they are found. The tokens before an error then appear above the error line. Finish the line, then print the list or the error.
The empty string disappears. A string whose text has length zero is still a token; '' must print [STRING - ], with the space after the dash.
The column is off by the prefix or by one. It counts from the first character of the line, tokenize included, and the first character is column 1. For an unterminated string it is the column of the opening quote, not the end of the line.
A failed line leaks into the next. A token list that is not emptied after an error prints the old tokens with the next statement's.
Output depends on how the tokens are stored. If tokens go into a structure that does not keep insertion order, they come out in the wrong order. A list, in the order they were read.

Language notes

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

C: isalpha, isdigit and isspace take an int that must be representable as unsigned char; cast a plain char before passing it. strncasecmp compares without case, but compare lengths first, or select will match the start of selectivity.
C++: std::string_view lets a token point into the line without copying; the line has to outlive the list. The same unsigned char cast applies to std::isalpha.
Rust: iterate over char_indices() or bytes rather than indexing a &str by position. eq_ignore_ascii_case compares a word with a keyword without allocating a lowercased copy.
Zig: std.ascii.isAlphabetic, std.ascii.isDigit and std.ascii.eqlIgnoreCase cover the whole character check. Slices into the line need no allocation, as long as the line lives as long as the tokens.

Loading starter code…

No run yet

15 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.