Lexical Analysis (Tokenizer)
Turning raw SQL text into a stream of classified tokens
Build a Tokenizer (Lexer) that scans a SQL string character by character and produces a list of typed tokens — keywords, identifiers, numbers, strings, and symbols.
Video Walkthrough
Core Concepts
- Lexical Analysis (Tokenizer / Scanner)
- Token types: Keywords, Identifiers, Numbers (integer/float), String literals, Symbols
- Character-by-character scanning with lookahead
- Error detection for invalid characters and unterminated strings
What is a Lexer?
A Lexer (also called Tokenizer or Scanner) is the architectural front door of any database syntax compiler. It takes a raw string of ASCII characters and groups them into sequential, structured computational units called tokens.
When a human inputs a query, the computer initially only sees a generic array of bytes. Before we can validate semantic correctness or execution logic, we must isolate where individual terms begin and end, stripping out extraneous whitespace and identifying grammatical intent.
For example, given the raw input statement:
SELECT * FROM users WHERE id = 1;
Your lexical analysis stage converts this string byte-by-byte into a clean stream:
[KEYWORD_SELECT - select]
[SYMBOL - *]
[KEYWORD_FROM - from]
[IDENTIFIER - users]
[KEYWORD_WHERE - where]
[IDENTIFIER - id]
[SYMBOL - =]
[NUMBER - 1]
[SYMBOL - ;]
Each emitted token is paired with a strict type classification (KEYWORD, IDENTIFIER, NUMBER, STRING, SYMBOL) and its preserved ASCII value.
Why Tokenize First?
Separation of concerns is critical in systems engineering. Without an isolated tokenization pass, every downstream pipeline stage (syntax parsing, query planning, B-Tree execution) would carry the enormous technical burden of raw character inspection—handling variable spacing, distinguishing between SELECT (keyword) and selectivity (table column identifier), and converting digit char sequences into numeric types. The Lexer resolves all character-level chaos once at the boundary.
Conceptual Execution Algorithms
Character-by-Character Token Scanner
The tokenizer walks through the input string one character at a time. At each position it decides what kind of token starts here, scans ahead to find the end of that token, classifies it, and moves on.
- [1]Start at position 0. Skip any whitespace characters.
- [2]Check the current character to decide which type of token to scan.
- [3]If the character is a letter (a-z, A-Z): scan ahead while characters are alphanumeric or underscore. The resulting word is either a KEYWORD (if it matches SELECT, INSERT, FROM, etc.) or an IDENTIFIER (a column/table name).
- [4]If the character is a digit (0-9): scan ahead while characters are digits or a dot. Classify the result as a NUMBER token (which can be integer or float).
- [5]If the character is a single quote ('): scan ahead until the closing quote is found. Extract the content between quotes as a STRING token. If no closing quote is found, report an error.
- [6]If the character is a known symbol (comma, semicolon, parenthesis, asterisk, equals): emit a single-character SYMBOL token.
- [7]If the character doesn't match any of the above: emit an error — the character is not valid in SQL.
- [8]After emitting the token, advance past it and repeat from step 1 until end of input.
Keyword vs Identifier Classification
When the scanner finds a word (sequence of letters), it needs to decide if it's a reserved SQL keyword or a user-defined identifier like a table/column name.
- [1]After scanning a word, convert it to lowercase for comparison.
- [2]Check if the word matches any known keyword: SELECT, INSERT, INTO, FROM, WHERE, UPDATE, SET, DELETE, VALUES.
- [3]If it matches, classify the token as the specific keyword type (TOKEN_KEYWORD_SELECT, TOKEN_KEYWORD_INSERT, etc.).
- [4]If it doesn't match any keyword, classify it as TOKEN_IDENTIFIER — it's a table name, column name, or other user-defined name.