SQL Tokenizer: Turning Text into Tokens

After this lesson your program reads lines of SQL and prints one KIND VALUE line per token, then END. Every later lesson in this course (CREATE TABLE, INSERT, SELECT, WHERE) starts from the token list you produce here, so the parser never touches raw characters again.

Why a separate pass

select Name FROM users and SELECT Name FROM users mean the same thing, but they are different strings: different case, different spacing. If the parser had to cope with that, every rule would be full of whitespace and case checks. A tokenizer (a lexer) removes the noise once. What comes out is a short list of (kind, text) pairs, and the parser only ever compares kinds and texts.

The six kinds

The keyword list is fixed: SELECT FROM WHERE INSERT INTO VALUES CREATE TABLE UPDATE SET DELETE AND OR NOT IS NULL INTEGER TEXT BEGIN COMMIT ROLLBACK ORDER BY LIMIT OFFSET COUNT SUM AVG MIN MAX ASC DESC INDEX ON. Anything else made of letters is an identifier.

One character decides what comes next

Scan left to right with a position. Look at the character under the cursor; it tells you which kind of token starts here, and you then consume the longest run that still belongs to it ("maximal munch").

A trace of WHERE age>=30 shows why the order of the checks matters:

WHERE   starts with a letter -> word "WHERE" -> in the keyword list -> KEYWORD WHERE
age     starts with a letter -> word "age"   -> not a keyword       -> IDENTIFIER age
>=      '>' with '=' after it -> one two-character token             -> OPERATOR >=
30      digit                  -> NUMBER 30

If you handle > alone first, >= splits into > and =, and no later stage can tell the difference between "greater or equal" and "greater, then equals". Always try the two-character operators before the one-character ones.

Words: keyword or identifier

A keyword and a table name look the same at the character level, so scan the word first and decide afterwards: upper-case a copy, and if the copy is in the keyword list the token is a KEYWORD whose text is the upper-cased copy; otherwise it is an IDENTIFIER with its original spelling. Users and users stay different names; from, From and FROM are all FROM.

A table that really is called order needs a way to say so. Double quotes do that: "order" is an IDENTIFIER whose text is order, never a keyword, and it may contain spaces.

Quotes inside quotes

SQL has no backslash escapes. To put a quote inside a string you write it twice:

source text :  'it''s'
tokens      :  STRING it's

So when you meet a quote inside a string, look one character ahead. Another quote means "a literal quote, keep going"; anything else means the string just ended. The empty string '' is legal and prints as STRING followed by nothing. The same doubling rule applies inside "...".

Errors

A line that cannot be tokenized prints a single error line, with no tokens and no END:

Common mistakes

• Splitting on spaces. a>=1 has no spaces but is three tokens, and SELECT*FROM is three as well.
• Upper-casing everything. Only keywords are normalised. STRING Alice must stay Alice, and IDENTIFIER Name must stay Name.
• Ending a string at the first closing quote. 'it''s' is one token, not it followed by garbage.
• Treating a comment as code. SELECT 1 -- note ends after the 1. But -- inside a string is just text.

Your exercise

Finish tokenize in the starter. Reading lines, printing tokens and END, skipping spaces and the four symbols are already done. The one mistake to watch for is the greedy ordering: test for the two-character operators and for -- before the single - and <.