SQL Tokenizer — Breaking SQL into Tokens

Every database engine starts the same way: before you can execute SELECT name FROM users WHERE age > 30, you need to turn that raw string into a sequence of meaningful chunks. That's lexing (a.k.a. tokenizing) — the same first stage you'd find in a compiler front-end, just applied to SQL instead of a programming language.

Why tokenize first?

A parser that tries to work directly on raw characters has to deal with whitespace, casing, and low-level character classification everywhere. Splitting lexing into its own pass means the parser only ever sees a clean, uniform sequence of (TYPE, VALUE) pairs, and doesn't care whether select was typed in lowercase, uppercase, or with extra spaces around it.

Token categories

Your tokenizer needs to classify each chunk of the input into one of a handful of categories:

• KEYWORD — reserved SQL words like SELECT, FROM, WHERE, INSERT. These are matched case-insensitively: select, Select, and SELECT must all normalize to KEYWORD SELECT (uppercase canonical form).
• IDENTIFIER — names that aren't keywords: table names, column names.
• NUMBER — a run of digits, e.g. 42.
• STRING — text delimited by single quotes, e.g. 'Alice'. The quotes are delimiters, not part of the value — your output drops them (STRING Alice, not STRING 'Alice').
• OPERATOR — comparison/arithmetic symbols: = < > <= >= != + - * /. Note that multi-character operators (<=, >=, !=) must be recognized greedily before falling back to their single-character prefixes (<, >) — check the two-character form first.
• SYMBOL — punctuation with no operator meaning: ( ) , ;.

The keyword-vs-identifier ambiguity

A classic lexer trick: identifiers and keywords look identical at the character level (both are just runs of letters/digits). The standard approach is to lex greedily as an "identifier-shaped" token first, then check it against a fixed set of reserved words — if it matches (case-insensitively), reclassify it as KEYWORD with the canonical uppercase spelling; otherwise it's an IDENTIFIER with its original casing preserved.

def classify(word):
    if word.upper() in KEYWORDS:
        return ("KEYWORD", word.upper())
    return ("IDENTIFIER", word)

Scanning strategy

A single left-to-right scan with a cursor works well:

1. Skip whitespace.
2. If the current character starts a quote ('), consume until the matching closing quote — this is your STRING.
3. If it's a digit, consume the full run of digits — NUMBER.
4. If it's a letter, consume the full run of letters/digits — then classify as KEYWORD or IDENTIFIER.
5. Otherwise, try to match a two-character operator (<=, >=, !=) before a one-character operator or symbol.
6. Repeat until end of input, then emit END.

Edge cases

• Adjacent tokens with no separating whitespace where possible, e.g. age>30 should still split into IDENTIFIER age, OPERATOR >, NUMBER 30 — don't assume tokens are always space-separated (though the exercise data does separate them, being defensive here mirrors how real lexers behave).
• Negative numbers: decide whether - is part of a NUMBER token or a separate OPERATOR — for this exercise, keep - as its own operator token and let the parser handle unary minus.
• Empty string literal '' should still tokenize as STRING with an empty value.

This tokenizer becomes the input stream for every later stage — the parser, and eventually the query planner, all consume the token list you produce here rather than raw SQL text.