SQL Tokenizer — Breaking SQL into Tokens

Every database engine begins by tokenizing (also called lexing) the raw SQL string into a sequence of meaningful tokens. This is the first stage of any compiler or interpreter pipeline.

What Is a Tokenizer?

A tokenizer reads a stream of characters and groups them into tokens — the smallest meaningful units of the language. Think of it like breaking a sentence into words and punctuation.

Input:  SELECT name FROM users WHERE age > 30
Tokens: [KEYWORD:SELECT] [IDENTIFIER:name] [KEYWORD:FROM]
        [IDENTIFIER:users] [KEYWORD:WHERE] [IDENTIFIER:age]
        [OPERATOR:>] [NUMBER:30]

Token Types

Our database supports these token types:

State Machine Approach

Most tokenizers use a finite state machine (FSM). The current state determines what characters are valid next:

START → saw letter → READING_WORD → saw non-letter → emit KEYWORD or IDENTIFIER
START → saw digit  → READING_NUMBER → saw non-digit → emit NUMBER
START → saw '      → READING_STRING → saw '         → emit STRING
START → saw <      → CHECK_NEXT    → saw =          → emit OPERATOR <=

How Real Databases Do It

SQLite's tokenizer (tokenize.c) uses a giant switch statement on the first character, then branches into specific scanning routines. PostgreSQL's lexer (scan.l) uses Flex, a lexer generator that compiles regular expressions into a state machine.

For our implementation, we'll write a hand-rolled tokenizer — it gives us full control and is easier to debug than generated code.

Key Design Decisions

1. Case insensitivity: select and SELECT are the same keyword — normalize to uppercase
2. Keyword vs identifier: Check if a word matches the keyword list; if not, it's an identifier
3. Multi-character operators: >= requires looking one character ahead (peek)
4. Whitespace: Separates tokens but produces no token itself

Your Task

Build a tokenizer that reads SQL from stdin and outputs tokens in TYPE VALUE format, one per line. This tokenizer will be the foundation for everything else in this course.