Lexing, Tokens and Lexical Rules

Before a program's grammar can be checked, its characters must be grouped into words.

Learning Objectives

Explain characters, lexemes, tokens, token types, identifiers, keywords, numeric and string literals, operators, whitespace and comments.

Apply the longest-match rule and token priority; handle lexer state, escapes, Unicode and errors with positions and spans.

Compare regex-based, handwritten and table-driven lexers; test lexers; understand buffering and incremental lexing.

Plain-Language Explanation

Before a program's grammar can be checked, its characters must be grouped into words. The lexer reads let answer = 40 + 2; and produces: the keyword let, the name answer, the symbol =, the number 40, the symbol +, the number 2, and ;. Spaces and comments disappear; every token remembers where it came from, so errors can point at the right place.

Precise Technical Explanation

Source characters and character streams The lexer consumes a sequence of characters (after decoding bytes) with one or two characters of look-ahead (= versus ==).

Lexemes and tokens A lexeme is the exact source substring ("40"); a token is the categorised unit: kind NUMBER, lexeme "40", literal value 40, position.

MiniLang's kinds: single-character punctuation (LEFT_PAREN, SEMICOLON…), one-or-two-character operators (BANG, BANG_EQUAL, LESS_EQUAL…), literals (IDENTIFIER, STRING, NUMBER), keywords (LET, PRINT…), and EOF.

Identifiers and reserved words Identifiers match [A-Za-z_][A-Za-z0-9_]*. The lexer scans the whole word, then checks a keyword table: let becomes LET, letter stays an identifier.

MiniLang: digits with an optional . followed by digits. 40. lexes as NUMBER(40) followed by an "unexpected character" error for the ., because a lone . is not a MiniLang token. Real languages add exponents, hex, binary, separators (1_000) and suffixes.

String and character literals Delimited by "; may span lines in MiniLang; escape sequences are decoded into the literal value. Many languages also have character literals ('a' in C and Java).

Operators and punctuation Recognised by looking at the current and next character: ! vs !=, = vs ==, < vs <=.

Whitespace and comments Skipped, but newlines advance the line counter. MiniLang has // line comments; C-family block comments /* */ require nesting decisions and "unterminated comment" errors.

At each position, the lexer takes the longest sequence that forms a valid token: == not = =; letter not let ter; <= not < =.

When two rules match the same longest lexeme, a priority decides: keywords beat identifiers (while is WHILE, not IDENTIFIER).

Some languages need modes: inside a string, inside a template literal (${…} in JavaScript), significant indentation (Python's lexer emits INDENT/DEDENT tokens by keeping a stack of indentation levels), or context-dependent tokens (JavaScript's / as divide or regex start).

\n, \t, \", \\ in MiniLang; an unknown escape such as \q is an error, not silently kept.

Unicode identifiers and source encoding Many languages allow Unicode letters in identifiers (Python, Java, JavaScript, C#) following Unicode's identifier rules, and normalise or compare by code points. MiniLang deliberately allows only ASCII identifiers; strings may contain any characters.

Lexical errors and diagnostics Unexpected characters and unterminated strings are reported with line and column; the lexer continues so several errors appear at once. Silently discarding input would hide mistakes and could change program meaning.

Token positions, lines, columns, and spans Each token stores start and end offsets (a span) plus line and column of its start. Spans let tools underline the exact source range; IDEs and source maps depend on them.

Regular expressions in lexers Token classes are regular languages, so lexers can be written as an alternation of regexes tried with longest-match semantics — convenient, but beware pathological backtracking and ordering mistakes.

A loop with a switch on the current character (MiniLang, clang, V8): fast, flexible, excellent error messages.

Generated from token regexes (lex, flex, re2c): the regexes become a deterministic finite automaton stored as tables; the lexer is a small table-walking loop.

Lexer performance and buffering Lexers read large buffers, avoid allocating a string per token (store spans), intern identifiers, and use fast character classification.

Incremental lexing overview for editors Editors re-lex only the region around an edit, restarting from a known state (for example the start of the line) and stopping once tokens match the previous version again.

Testing a lexer Golden tests (input → expected token list), round-trip tests (concatenated lexemes plus skipped text reproduce the input), error tests, and fuzzing with random input to ensure the lexer never crashes or loops.

Tiny language example. For a possible token sequence is LET IDENTIFIER("answer") EQUAL NUMBER(40) PLUS NUMBER(2) SEMICOLON PRINT LEFT_PAREN IDENTIFIER("answer") RIGHT_PAREN SEMICOLON — the real one, with positions, is below.

let answer = 40 + 2;
print(answer);

while not atEnd():
    skipWhitespaceAndComments()
    start = currentPosition()
    token = scanNextToken()
    emit(token, start, currentPosition())

Why It Matters in Real Systems

Every compiler, interpreter, syntax highlighter, formatter, linter and language server starts with a lexer. Lexer bugs produce confusing errors far from the real problem.

Key Terms

Exact source text of a token Category of a token Start and end offsets of a token in the source

Prefer the longest valid token at each position Reserved word recognised as its own kind

Syntax or Instruction Format

Lexical grammar of MiniLang (regular expressions):

IDENTIFIER  = [A-Za-z_][A-Za-z0-9_]*          (keywords excluded)
NUMBER      = [0-9]+ ( "." [0-9]+ )?
STRING      = '"' ( [^"\\] | '\' [nt"\\] )* '"'
COMMENT     = "//" [^\n]*                      (skipped)
WHITESPACE  = [ \t\r\n]+                       (skipped; \n advances the line)

Complete Example

The course's MiniLang lexer on the tiny example, a string with an escape, a comment and two-character operators:

Output (MiniLang reference implementation — line:column, kind, lexeme, literal):

Malformed input — the lexer reports every problem with its position and keeps going:

A complete handwritten lexer in Python, independent of the course implementation (CPython 3.13.1):

let answer = 40 + 2;   // the answer
print(answer >= 42);
print("a \"quoted\" word");

1:1   LET            "let"
 1:5   IDENTIFIER     "answer"
 1:12  EQUAL          "="
 1:14  NUMBER         "40"         literal=40
 1:17  PLUS           "+"
 1:19  NUMBER         "2"          literal=2
 1:20  SEMICOLON      ";"
 2:1   PRINT          "print"
 2:6   LEFT_PAREN     "("
 2:7   IDENTIFIER     "answer"
 2:14  GREATER_EQUAL  ">="
 2:17  NUMBER         "42"         literal=42
 2:19  RIGHT_PAREN    ")"
 2:20  SEMICOLON      ";"
 3:1   PRINT          "print"
 3:6   LEFT_PAREN     "("
 3:7   STRING         "\"a \\\"quoted\\\" word\"" literal="a \"quoted\" word"
 3:26  RIGHT_PAREN    ")"
 3:27  SEMICOLON      ";"
 4:1   EOF            ""

let price = 9.5 @ 2;
let name = "unterminated;

1:1   LET            "let"
 1:5   IDENTIFIER     "price"
 1:11  EQUAL          "="
 1:13  NUMBER         "9.5"        literal=9.5
 1:17  ERROR          "@"
 1:19  NUMBER         "2"          literal=2
 1:20  SEMICOLON      ";"
 2:1   LET            "let"
 2:5   IDENTIFIER     "name"
 2:10  EQUAL          "="
 2:12  ERROR          "\"unterminated;\n"
 3:1   EOF            ""
Lexical error [line 1:17]: Unexpected character '@'.
Lexical error [line 2:12]: Unterminated string.

KEYWORDS = {"let", "print"}
SINGLE = {"+": "PLUS", "-": "MINUS", "*": "STAR", "/": "SLASH", "(": "LEFT_PAREN", ")": "RIGHT_PAREN", ";": "SEMICOLON"}


def tokenize(src):
    tokens, errors = [], []
    i, line, line_start = 0, 1, 0
    while i < len(src):
        c = src[i]
        col = i - line_start + 1
        if c == "\n":
            i, line, line_start = i + 1, line + 1, i + 1
        elif c in " \t\r":
            i += 1
        elif c.isdigit():
            j = i
            while j < len(src) and src[j].isdigit():
                j += 1
            tokens.append(("NUMBER", src[i:j], int(src[i:j]), line, col))
            i = j
        elif c.isalpha() or c == "_":
            j = i
            while j < len(src) and (src[j].isalnum() or src[j] == "_"):
                j += 1
            word = src[i:j]
            tokens.append((word.upper() if word in KEYWORDS else "IDENTIFIER", word, None, line, col))
            i = j
        elif c == "=":
            two = src[i:i + 2] == "=="                     # longest match
            tokens.append(("EQUAL_EQUAL" if two else "EQUAL", src[i:i + 1 + two], None, line, col))
            i += 1 + two
        elif c in SINGLE:
      
…

1:1   LET          'let'
1:5   IDENTIFIER   'answer'
1:12  EQUAL        '='
1:14  NUMBER       '40' literal=40
1:17  PLUS         '+'
1:19  NUMBER       '2' literal=2
1:20  SEMICOLON    ';'
2:1   PRINT        'print'
2:6   LEFT_PAREN   '('
2:7   IDENTIFIER   'answer'
2:14  EQUAL_EQUAL  '=='
2:17  NUMBER       '42' literal=42
2:19  RIGHT_PAREN  ')'
2:22  EOF          ''
["line 2:21: unexpected character '$'"]

Line-by-Line Explanation

MiniLang: >= is one token (longest match); the comment produces no token; the string's literal value has the escapes decoded while the lexeme keeps them.

Errors: @ is reported at its exact column and lexing continues; the unterminated string is reported at its start.

Python lexer: one branch per token class; identifiers are scanned fully and *then* checked against keywords (token priority); == versus = uses one character of look-ahead; unexpected characters are collected, not discarded silently.

Step-by-Step Runtime Behavior

The lexer is a state machine: in the initial state it inspects one character, transitions into "in number", "in identifier", "in string" or "operator" states, and returns to the initial state after emitting a token.

Common Misconceptions

"Whitespace never matters." It separates tokens (let x vs letx) and is significant in Python's indentation.

"Regex lexers are always slower." Generated DFA lexers are very fast; backtracking regexes can be slow.

"Keywords need separate scanning." Scan an identifier, then look it up.

Common Bugs and Failure Modes

Off-by-one columns; forgetting to count newlines inside strings; swallowing invalid characters; treating letter as let + ter; infinite loops when no rule consumes input; quadratic behaviour from repeated string slicing.

Corrected or Safer Patterns

Always advance at least one character per iteration; store spans instead of copying text; report errors with positions; test the round-trip property.

Debugging and Inspection Techniques

Dump the token stream (the course's lexer visualizer, python -m tokenize file.py); compare spans against the source.

Performance Considerations

Lexing is linear in input size; constant factors come from per-character branching and allocation. Interning identifiers speeds later symbol lookups.

Security Considerations

Lexers process untrusted input in IDEs, web services and interpreters: they must never crash, hang or allocate unboundedly. Unicode confusables and bidirectional control characters ("Trojan Source") can make code display differently from how it lexes — warn about them.

Portability and Version Caveats

Lexical rules differ per language and version (Python 3.12 changed f-string tokenisation; Java added text blocks). Use the language's own lexer when processing real code.

Real-World Use Cases

Syntax highlighters, minifiers, template engines, configuration formats, log parsers, query languages.

Best Practices

Keep positions, report all errors, separate token kinds from lexemes, fuzz the lexer.

Exercises

E1 · Beginner. Write the token sequence for print(1 <= 2);.

Answer: PRINT LEFT_PAREN NUMBER(1) LESS_EQUAL NUMBER(2) RIGHT_PAREN SEMICOLON EOF.

E2 · Intermediate. Add /* … */ block comments to the Python lexer. What new error must it report?

Answer: On /*, scan until */, counting newlines; if the input ends first, report "unterminated block comment" with the comment's start position.

E3 · Advanced challenge. How would you lex Python-style indentation?

Answer: Track a stack of indentation widths. At the start of each logical line, measure leading whitespace: greater than the top → push and emit INDENT; smaller → pop and emit DEDENT until equal (error if it matches no level); ignore blank and comment-only lines; emit remaining DEDENTs at EOF.

Quiz

? How should `letter` be tokenized in MiniLang?
+ One IDENTIFIER :: Longest match first, then the keyword check fails.
- LET then IDENTIFIER(ter) :: That violates longest match.
- An error :: It is a valid identifier.
- KEYWORD(letter) :: It is not a keyword.

? Why do tokens store spans?
+ So diagnostics and tools can point at exact source ranges. :: Errors, highlighting and source maps need them.
- To make tokens smaller. :: Spans add data.
- Because the parser needs whitespace. :: Whitespace is skipped.
- For garbage collection. :: Unrelated.

? Which should a lexer do with an unexpected character? (select all that apply)
+ Report it with line and column :: So the user can fix it.
+ Continue scanning to find further errors :: Better diagnostics.
- Silently discard it :: That hides mistakes and can change meaning.
- Crash the process :: Untrusted input must never crash the tool.

Summary and Key Takeaways

Lexers turn characters into positioned tokens using longest match and keyword priority, skip whitespace and comments, decode literals, and report every lexical error without stopping. They must be fast, robust and thoroughly tested.