Lexical Analysis

A lexeme is the actual character sequence in the source file — the raw string while, or 3.14, or >=. A token is the classified, structured result: a pair (token_class, attribute), like (KEYWORD, "while") or (FLOATLIT, 3.14). A pattern is the rule — typically a regular expression — that describes which lexemes belong to a given token class.

Consider the source line:

if (x >= 3.14) return y;

The scanner produces a stream of tokens:

(IF, _), (LPAREN, _), (ID, "x"), (GEQ, _), (FLOATLIT, 3.14), (RPAREN, _), (KEYWORD, "return"), (ID, "y"), (SEMI, _)

Several design decisions are embedded here:

1. Whitespace and comments are usually not tokens — they are consumed and discarded by the scanner. This keeps the parser uncluttered.
2. Token classes vary by language. Most languages have classes for: keywords (if, while, return), identifiers, integer literals, float literals, string literals, operators, and punctuation.
3. Keywords vs. identifiers: Most scanners match keywords and identifiers with the same pattern (a letter followed by letters/digits), then consult a keyword table to upgrade matching lexemes. This is cleaner than writing separate patterns for every keyword.
4. Attributes: Some token classes carry a value (the integer 42, the string "hello"), others do not (LPAREN is unambiguous — no attribute needed).

The distinction between lexeme and token is subtle but important. The parser only sees token classes (and selected attributes). It does not see the original character sequence. This abstraction is deliberate: it decouples syntactic structure from surface spelling.

# Python illustration of token representation
from dataclasses import dataclass
from enum import Enum, auto

class TK(Enum):
    IF = auto(); WHILE = auto(); RETURN = auto()
    ID = auto()
    INTLIT = auto(); FLOATLIT = auto()
    PLUS = auto(); GEQ = auto()
    LPAREN = auto(); RPAREN = auto(); SEMI = auto()
    EOF = auto()

@dataclass
class Token:
    kind: TK
    lexeme: str          # original characters
    value: object = None  # parsed value for literals
    line: int = 0

# Examples:
# Token(TK.IF,      'if')
# Token(TK.ID,      'velocity')
# Token(TK.FLOATLIT,'3.14', 3.14)
# Token(TK.GEQ,     '>=')

A regular expression (regex) over an alphabet Σ is defined inductively:

• Basis: ε (empty string), ∅ (empty set), and any single character a ∈ Σ are regular expressions.
• Induction: if R and S are regular expressions, so are:
  • Concatenation: RS — match R then S
  • Union (alternation): R | S — match R or S
  • Kleene star: R* — match zero or more repetitions of R

All other operators — R+ (one or more), R? (zero or one), [a-z] (character class) — are syntactic sugar for these three primitives.

For a typical programming language, token patterns look like:

The language denoted by a regex R, written L(R), is the (possibly infinite) set of strings it matches. For example, L([0-9]+) = {"0", "1", ..., "9", "00", "01", ..., "99", "000", ...}.

Ambiguity and priority rules: Real languages have two systematic ambiguities that scanners must resolve:

1. Longest match (maximal munch): Always consume the longest possible lexeme. The input <= should produce the single token LEQ, not LT followed by EQ. Similarly, whileVar is an identifier, not the keyword while followed by Var.
2. Rule priority: When two patterns match the same lexeme, the earlier rule wins. This is how keywords beat the identifier pattern — the keyword rules are listed first.

# Formal regex primitives vs. practical notation

# Primitive:         Practical sugar:
# R | S              R | S  (same)
# RS                 RS     (same)
# R*                 R*     (same)
# ---
# R(R*)              R+
# (R | ε)            R?
# [abc]              a | b | c
# [a-z]              a | b | ... | z
# .                  any char except newline

# Example: float literal in primitive form
# digit  = 0|1|2|3|4|5|6|7|8|9
# digits = digit(digit)*               -- digit+
# sign   = (+|-|ε)
# exp    = (e|E) sign digits
# float  = digits . digits (exp | ε)   -- simplified

# In Python re:
import re
FLOAT = re.compile(r'[0-9]+\.[0-9]*(?:[eE][+-]?[0-9]+)?')
print(FLOAT.match('3.14e-2').group())  # '3.14e-2'

A deterministic finite automaton (DFA) is a 5-tuple M = (Q, Σ, δ, q₀, F) where:

• Q is a finite set of states
• Σ is the input alphabet
• δ: Q × Σ → Q is the (total) transition function
• q₀ ∈ Q is the start state
• F ⊆ Q is the set of accepting states

The DFA reads its input one character at a time, following transitions deterministically. It accepts a string if, after reading the entire input, it is in an accepting state.

A nondeterministic finite automaton (NFA) relaxes determinism in two ways:

• The transition function δ: Q × (Σ ∪ {ε}) → 2^Q can map a (state, symbol) pair to a set of next states (including the empty set).
• ε-transitions: the NFA can change state without consuming any input.

An NFA accepts a string if any path of transitions leads to an accepting state.

Key theorems (proven in Sipser or Hopcroft/Ullman):

1. DFAs and NFAs recognize exactly the same class of languages — the regular languages.
2. Every NFA can be converted to an equivalent DFA (subset/powerset construction).
3. A language is regular iff it is recognized by some DFA iff it is described by some regex.

This equivalence is the theoretical backbone of scanner construction. We use NFAs as an intermediate form because they are easy to construct from regexes (Thompson construction), then convert to DFAs because DFAs are easy and fast to simulate.

# DFA simulation — table-driven
# States: 0=start, 1=seen digit, 2=seen dot, 3=frac digit (accept)
# Accept: {1, 3}  (integers + floats)

transitions = {
    (0, 'digit'): 1,
    (1, 'digit'): 1,
    (1, 'dot'):   2,
    (2, 'digit'): 3,
    (3, 'digit'): 3,
}
accept = {1, 3}

def classify(c):
    if c.isdigit(): return 'digit'
    if c == '.':    return 'dot'
    return c

def simulate_dfa(s):
    state = 0
    for ch in s:
        sym = classify(ch)
        key = (state, sym)
        if key not in transitions:
            return False   # dead / error state
        state = transitions[key]
    return state in accept

print(simulate_dfa('3'))     # True  (integer)
print(simulate_dfa('3.14'))  # True  (float)
print(simulate_dfa('3.'))    # False (trailing dot)

Ken Thompson (1968) gave a beautiful inductive construction that converts any regular expression to an NFA with at most 2|r| states, where |r| is the number of symbols in the regex. The construction mirrors the inductive definition of regular expressions.

Base cases:

• Empty string ε: one start state with an ε-transition to one accept state.
• Single character a: one start state with an a-transition to one accept state.

Inductive cases (given NFAs N(R) and N(S) with single accept states):

• Concatenation RS: connect the accept state of N(R) to the start state of N(S) via an ε-transition. The start of N(R) is the new start; the accept of N(S) is the new accept.
• Union R|S: add a new start state with ε-transitions to the starts of N(R) and N(S); add a new accept state with ε-transitions from the accepts of N(R) and N(S).
• Kleene star R*: add a new start/accept state; ε-transitions from it to N(R)'s start and from N(R)'s accept back to N(R)'s start (creating the loop), plus an ε-transition from the new state to the accept directly (for zero repetitions).

Properties of Thompson NFAs:

• Each NFA fragment has exactly one start state and one accept state.
• Each state has at most two outgoing transitions.
• ε-transitions connect fragments; character transitions are only within base-case fragments.
• The total number of states is O(|r|).

This economy of states is why Thompson construction is preferred over alternative constructions in tools like RE2 and the Go regexp engine.

# Structural representation of a Thompson NFA fragment

from dataclasses import dataclass, field
from typing import Optional

@dataclass
class State:
    id: int
    accept: bool = False
    # transitions: list of (label, target)
    # label = None means ε-transition
    transitions: list = field(default_factory=list)

@dataclass
class Fragment:
    start: State
    accept: State

_counter = 0
def new_state(accept=False):
    global _counter
    s = State(_counter, accept)
    _counter += 1
    return s

def nfa_char(c) -> Fragment:
    """Base case: single character."""
    s0, s1 = new_state(), new_state(accept=True)
    s0.transitions.append((c, s1))
    return Fragment(s0, s1)

def nfa_concat(f1: Fragment, f2: Fragment) -> Fragment:
    """RS: connect f1.accept to f2.start via ε."""
    f1.accept.accept = False
    f1.accept.transitions.append((None, f2.start))  # ε
    return Fragment(f1.start, f2.accept)

def nfa_union(f1: Fragment, f2: Fragment) -> Fragment:
    """R|S: new start + new accept."""
    s0, s1 = new_state(), new_state(accept=True)
    f1.accept.accept = f2.accept.accept = False
    s0.transitions += [(None, f1.start), (None, f2.start)]
    f1.accept.transitions.append((None, s1))
    f2.accept.transitions.append((None, s1))
    return Fragment(s0, s1)

An NFA is a clean intermediate representation, but simulating it naively requires tracking all possible active states simultaneously — exponential in the worst case per step. The subset construction (also called the powerset construction) converts an NFA to an equivalent DFA once, offline, so the resulting DFA runs in O(n) time for an input of length n.

The core insight: instead of nondeterministically choosing one state, make a DFA whose states are sets of NFA states.

Algorithm:

1. Compute ε-closure(q₀): the set of all NFA states reachable from q₀ via ε-transitions only. This is the DFA start state.
2. For each DFA state T (a set of NFA states) and each input symbol a:
   • move(T, a) = ∪{δ_NFA(q, a) | q ∈ T} — all NFA states reachable on a
   • ε-closure(move(T, a)) — follow all ε-transitions from those states
   • This result is a new DFA state.
3. A DFA state T is an accepting state if any NFA state in T is accepting.
4. Repeat until no new DFA states are found.

Complexity: The resulting DFA can have up to 2^n states for an NFA with n states (worst case). In practice, for the NFAs built by Thompson construction from token rules, the DFA is much smaller. For the combined scanner NFA (union of all token NFAs), minimization is usually applied afterward to reduce DFA size.

Why union the NFAs first?: A real scanner needs to recognize which token class matched, not just whether any pattern matched. The standard approach is:

1. Build individual NFAs N(R₁), ..., N(Rₖ) for each token rule.
2. Combine them with a new start state and ε-transitions to each Nᵢ.
3. Mark each accepting state with the token class it corresponds to.
4. Apply subset construction to get the combined scanner DFA.

def epsilon_closure(states, nfa_transitions):
    """BFS/DFS to find all states reachable via ε from a set of states."""
    closure = set(states)
    worklist = list(states)
    while worklist:
        s = worklist.pop()
        for (label, target) in nfa_transitions.get(s, []):
            if label is None and target not in closure:
                closure.add(target)
                worklist.append(target)
    return frozenset(closure)

def move(states, symbol, nfa_transitions):
    """All NFA states reachable from `states` on `symbol` (not ε)."""
    result = set()
    for s in states:
        for (label, target) in nfa_transitions.get(s, []):
            if label == symbol:
                result.add(target)
    return result

def subset_construction(nfa_start, nfa_accepting, nfa_transitions, alphabet):
    start_closure = epsilon_closure({nfa_start}, nfa_transitions)
    dfa_states  = {start_closure}
    unmarked    = [start_closure]
    dfa_trans   = {}   # (dfa_state, symbol) -> dfa_state
    dfa_accept  = set()

    while unmarked:
        T = unmarked.pop()
        if T & nfa_accepting:   # any NFA accept state in T?
            dfa_accept.add(T)
        for a in alphabet:
            U = epsilon_closure(move(T, a, nfa_transitions), nfa_transitions)
            if not U:
                continue       # dead state — omit or add explicit error state
            dfa_trans[(T, a)] = U
            if U not in dfa_states:
                dfa_states.add(U)
                unmarked.append(U)

    return start_closure, dfa_accept, dfa_trans

The DFA produced by subset construction may contain redundant states — states that are indistinguishable by any input suffix. Two states p and q are equivalent if for every string w, running the DFA from p on w and from q on w give the same accept/reject result. Merging equivalent states yields the minimum-state DFA, which is unique (up to renaming states) for a given regular language.

Hopcroft's algorithm (1971) computes the minimal DFA in O(n log n) time, where n is the number of states. The key idea is partition refinement:

1. Start with two groups: accepting states A and non-accepting states Q - A.
2. Repeatedly split a group: if two states in the same group transition to different groups on some symbol a, they must be in different equivalence classes — split the group.
3. Stop when no more splits are possible. Each remaining group is a single state in the minimal DFA.

Minimization matters for scanner performance. The combined NFA for a real language (C, Java, Python) can have thousands of states before minimization and hundreds after. Since the DFA transition table is typically stored as a 2D array of size |states| × |alphabet|, minimization directly reduces memory and cache pressure.

A subtlety for scanners: token-class labels on accepting states are treated as distinguishing — states accepting ID and states accepting KEYWORD are initially in different groups even if their future behavior on the input is identical, because they produce different tokens.

# Hopcroft's algorithm skeleton (pedagogical)
def minimize_dfa(states, alphabet, delta, accept_states):
    # Partition: accepting vs non-accepting
    P = [frozenset(accept_states),
         frozenset(states - accept_states)]
    P = [g for g in P if g]  # drop empty groups

    W = list(P)  # worklist of "splitter" groups

    while W:
        A = W.pop()                        # choose a splitter
        for c in alphabet:
            # X = states that transition INTO A on c
            X = frozenset(s for s in states
                          if delta.get((s, c)) in A)
            if not X:
                continue
            new_P = []
            for Y in P:
                inter = Y & X
                diff  = Y - X
                if inter and diff:          # Y is split by X on c
                    new_P += [inter, diff]
                    if Y in W:
                        W.remove(Y)
                        W += [inter, diff]
                    else:
                        # Add smaller piece as splitter
                        W.append(inter if len(inter) <= len(diff) else diff)
                else:
                    new_P.append(Y)
            P = new_P
    return P   # each frozenset is a state of the minimal DFA

Once the DFA is built and minimized, the scanner simulates it on the input stream. There are two main implementation strategies:

Table-driven scanner: Store the DFA as a 2D transition table T[state][char]. The scanner loop is:

current_state = start
while char := next_input_char():
    current_state = T[current_state][char]
    if current_state == ERROR: break
    if current_state in ACCEPT: record_last_accept()
return to last recorded accept position; emit token

This is what flex generates by default. The table is compact and cache-friendly. Cache misses are the main performance concern for large alphabets — solved by using 8-bit row offsets or alphabet compression.

Direct-coded (switch-based) scanner: Each DFA state becomes a switch case or goto label in C. Transitions become direct branches rather than table lookups. This can be 30–50% faster due to branch prediction, but the generated code is much larger. flex can generate this with %option full.

The maximal munch loop: A real scanner must handle the fact that no token pattern precisely delimits where a token ends — a >= prefix could be GEQ or just GT. The scanner maintains a pointer to the last accepting state it passed through. It keeps running until it hits an error state (dead state), then backs up to the last accept position. This is why flex scanners maintain yytext (the current lexeme buffer) and sometimes back up.

Handling EOF and sentinel characters: A common optimization is to place a sentinel character (e.g., 0xFF) at the end of the input buffer that transitions every DFA state to a special EOF state. This eliminates a bounds check in the inner loop — a measurable speedup in tight scanning loops.

// Table-driven scanner inner loop — C pseudocode
int scan(char *input, Token *out) {
    int   state = START;
    char *p     = input;
    char *last_accept_end = NULL;
    int   last_accept_tok = -1;

    while (1) {
        unsigned char c = (unsigned char)*p;
        int next = T[state][(int)c];    // DFA table lookup
        if (next == DEAD) break;
        state = next;
        p++;
        if (ACCEPT[state] != NONE) {    // accepting state?
            last_accept_end = p;
            last_accept_tok = ACCEPT[state];
        }
    }
    if (last_accept_tok == -1) return ERROR;  // no token matched
    out->kind  = last_accept_tok;
    out->lexeme_end = last_accept_end;        // caller uses start pointer
    return last_accept_tok;
}

lex (1975, Lesk & Schmidt) and its free reimplementation flex (Fast LEXical analyzer, Paxson, 1987) automate scanner construction. You write a .l file with three sections separated by %%:

1. Definitions: named regex abbreviations and C header code in %{ ... %}.
2. Rules: pairs of pattern { action }. The action is C code executed when the pattern matches.
3. User code: C functions appended verbatim to the output.

flex compiles the .l file into lex.yy.c, which contains the DFA transition table and the yylex() function. Each call to yylex() scans the next token and returns its integer code.

Key flex behaviors:

• Longest match: flex always prefers the longest matching rule.
• First-rule priority: ties broken by order of rules.
• yytext: null-terminated pointer to the matched lexeme.
• yyleng: length of the matched lexeme.
• yylineno: line number tracking (with %option yylineno).
• %option noyywrap: no multi-file input (single file; omit yywrap()).
• Start conditions (%x STATE): flex supports lexer states for context-sensitive tokenization (e.g., inside strings, inside C-style comments).

Typical workflow: flex scanner.l && gcc lex.yy.c -lfl -o scanner.

Modern alternatives include ANTLR (generates lexers and parsers together, multiple target languages), RE/flex (C++ with Unicode support), and hand-rolled scanners for performance-critical applications (GCC, Clang, Go all use hand-written scanners).

/* A minimal flex scanner for a calculator language */
%{
#include "tokens.h"
%}
%option noyywrap yylineno

DIGIT   [0-9]
LETTER  [a-zA-Z_]

%%

[ \t\n]+          { /* skip whitespace */ }
"/""*"([^*]|"*"[^/])*"*""/"  { /* skip block comment */ }

"if"              { return IF;     }
"else"            { return ELSE;   }
"while"           { return WHILE;  }
"return"          { return RETURN; }

{LETTER}({LETTER}|{DIGIT})*  {
    yylval.str = strdup(yytext);
    return ID;
}

{DIGIT}+"."({DIGIT}*)? {
    yylval.fval = atof(yytext);
    return FLOATLIT;
}

{DIGIT}+          { yylval.ival = atoi(yytext); return INTLIT; }

"<="              { return LEQ; }
">="              { return GEQ; }
"=="              { return EQ;  }
"!="              { return NEQ; }
[+\-*/=<>!();,{}] { return yytext[0]; }  /* single-char ops */

.                 {
    fprintf(stderr, "unexpected char '%c' at line %d\n",
            yytext[0], yylineno);
}

%%

Real languages push against the limits of pure regular-expression scanning in several ways:

1. String and character literals: A string like "hello\"world" contains an escaped quote. The pattern "([^"\\]|\\.)*" handles this: the content is either a non-quote/non-backslash character, or a backslash followed by anything. Processing escape sequences (\n → newline, \xHH → hex byte) happens in the action, not the pattern.

2. Nested comments: Languages like ML and Haskell support (* (* nested *) *). This is not regular — it requires counting nesting depth. The standard solution is a flex start condition that counts nesting depth in a global variable, transitioning back to the initial state when the depth hits zero. Strictly speaking, this makes the scanner context-sensitive for that one construct, but the rest of the language remains regular.

3. Here-documents: In bash or Ruby, <<EOF ... EOF — the delimiter is determined at runtime and cannot be encoded in a static regex. Again, the solution is start conditions with dynamic state.

4. Significant whitespace (Python, YAML): Python uses indentation as syntax. The scanner maintains a stack of indentation levels and emits synthetic INDENT and DEDENT tokens when the indentation changes. This is purely a scanner-level concern — the parser sees a token stream with explicit structure.

5. Maximal munch pitfalls: a---b in C is lexed as a -- - b (postfix decrement of a, then minus b), not a - -- b. This follows from the maximal munch rule, applied left to right.

6. Unicode: Modern lexers must handle UTF-8 identifiers (Java, Python 3, Rust all allow Unicode letters in identifiers). The efficient approach is to decode UTF-8 byte sequences and categorize code points using Unicode general categories (Letter, Digit, etc.), either via DFA states or a supplementary lookup table for code points > 127.

/* flex start conditions for nested C-style block comments */
%x COMMENT
%{
int comment_depth = 0;
%}
%%
"/*"               { comment_depth = 1; BEGIN(COMMENT); }
<COMMENT>"/*"      { comment_depth++;                   }
<COMMENT>"*/"      { if (--comment_depth == 0) BEGIN(INITIAL); }
<COMMENT>\n        { /* track line number if needed */ }
<COMMENT>.         { /* consume any other char        */ }
<COMMENT><<EOF>>   { error("unterminated comment");    }

What should a scanner do when it encounters a character sequence that matches no token pattern? There are two broad strategies:

Panic mode: Report the error, skip the offending character, and continue scanning from the next position. flex does this by default — the . (dot) rule at the end catches any unmatched character. This allows the compiler to report multiple errors in one pass rather than stopping at the first.

Error tokens: Emit a special ERROR token (carrying the offending character or sequence) and let the parser decide how to recover. This separates concerns cleanly — the scanner is not making parsing decisions.

Location tracking: A critical part of error reporting is accurate source locations. Good compilers report error at line 42, column 17. The scanner must maintain (line, column) as it advances through the input. In flex, yylineno tracks lines; columns require manual tracking in actions.

End-of-file handling: The scanner must emit a special EOF token when the input is exhausted so the parser can cleanly terminate. flex's default yywrap() returns 1 (no more input), causing yylex() to return 0 (which the parser convention treats as EOF).

A production-quality scanner almost always wraps the raw yylex() in a thin adapter that:

• Skips whitespace/comment tokens internally
• Attaches source location to every token
• Handles multiple input files
• Provides a one-token lookahead (peek) for the parser