SQL Lexer

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.

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:

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.

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:

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:

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

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.