Lexical analysis

The scanner, or lexer, is the first phase of a compiler and the only one that looks at individual characters. Its job is to group characters into tokens, the words of the language, and to discard what the rest of the compiler does not need: whitespace, comments and line breaks. A token has a kind, such as identifier, integer literal, keyword or operator, and usually carries its text (the lexeme) and its position for error messages. Separating scanning from parsing keeps the grammar simpler, because the parser deals with a few dozen token kinds instead of individual characters, and it makes the compiler faster, because the scanner can be a tight loop over a character buffer. In large compilers, scanning is often the single most time-consuming front-end phase simply because it touches every byte of the source.

CMPUT-325 (lesson 2) showed a scanner built from Python's regular expression library. This lesson looks underneath: how regular expressions are turned into finite automata, how those automata are made deterministic and minimal, and how a production scanner is written by hand. The theory behind it, regular languages and their equivalence with finite automata, is covered rigorously in CMPUT-474; here we apply it.

Tokens, patterns and lexemes

Each kind of token is described by a pattern. Identifiers in Tern are a letter or underscore followed by letters, digits and underscores; integer literals are one or more digits; operators are fixed strings such as +, == or ->. A lexeme is the actual text matched in a program, such as count, 42 or <=. Keywords like while and return match the identifier pattern too, so the scanner needs a rule for deciding between them, usually a table lookup after an identifier has been scanned. Some languages also have tokens whose meaning depends on context, such as Python's indentation (turned into INDENT and DEDENT tokens) or C++'s >> closing two template argument lists, and these need extra care in the scanner.

Two rules resolve ambiguity in almost every scanner. The longest-match rule, also called maximal munch, says that the scanner takes the longest prefix of the remaining input that matches any pattern: <= is one token, not < followed by =, and count1 is one identifier, not count followed by 1. The priority rule says that when two patterns match the same longest lexeme, the one listed first wins; listing keywords before identifiers makes while a keyword. Maximal munch occasionally produces surprises. In C, x+++++y scans as x ++ ++ + y and is a syntax error, even though x ++ + ++ y would have been valid; the scanner does not consult the parser.

Regular expressions

Patterns are written as regular expressions, built from single characters with three operations: concatenation (rs matches r followed by s), alternation (r|s matches either) and Kleene star (r* matches zero or more repetitions of r). Convenient extras such as r+ (one or more), r? (optional) and character classes [a-z] are shorthand for these. The languages, meaning sets of strings, that regular expressions describe are exactly the regular languages, which are also exactly the languages recognized by finite automata. That equivalence, due to Stephen Kleene in 1956, is what makes fast scanners possible: any set of token patterns can be turned automatically into a finite automaton that reads each character once.

Regular expressions cannot describe everything. They cannot match balanced parentheses or nested comments of arbitrary depth, because a finite automaton has no memory beyond its current state, and counting unbounded nesting needs unbounded memory. This is why nesting is left to the parser, which uses a context-free grammar (lesson 3). The regular expression libraries in many programming languages have added features such as backreferences that go beyond regular languages, and they implement matching by backtracking, which can take exponential time on some inputs. Scanner generators deliberately stick to true regular expressions so that scanning is guaranteed to take linear time.

From regular expressions to NFAs: Thompson's construction

A nondeterministic finite automaton (NFA) is a set of states with labeled transitions, a start state and accepting states. Unlike a deterministic automaton, it may have several transitions on the same character, or transitions labeled ε that consume no input. An NFA accepts a string if some path from the start state to an accepting state spells it out. Ken Thompson's construction (1968) builds an NFA from a regular expression compositionally, with a small fragment for each operator: a character becomes two states joined by that character; concatenation joins the accept state of one fragment to the start of the next with an ε edge; alternation adds a new start state with ε edges into both alternatives and a new accept state reached from both; star adds ε edges that allow skipping the fragment or looping back. The resulting NFA has at most two states per symbol and operator, so its size is linear in the length of the expression.

From NFAs to DFAs: the subset construction

Simulating an NFA directly means tracking every state it could be in at once. The subset construction, due to Michael Rabin and Dana Scott (1959), precomputes that bookkeeping: each state of the deterministic finite automaton (DFA) stands for a set of NFA states. Two operations do the work. The ε-closure of a set of states adds every state reachable by ε edges. The move on a character a takes every state reached from the set by an a transition. The DFA's start state is the ε-closure of the NFA's start state, and from each DFA state S the transition on a goes to the ε-closure of move(S, a). Any DFA state containing an NFA accepting state is accepting. A worklist processes each new set once. In the worst case a DFA can have exponentially many states, \(2^n\) for an n-state NFA, but for token patterns this almost never happens, and the DFA can be built once when the scanner is generated.

# Regular expression -> NFA (Thompson) -> DFA (subset construction).
# Regex syntax: letters, | for alternation, * for star, parentheses; concatenation
# is implicit. Example: (a|b)*abb, the classic textbook language.
from itertools import count
ids = count()
class Frag:                        # an NFA fragment with one start and one accept state
    def __init__(s, start, accept): s.start, s.accept = start, accept
edges = {}                         # state -> list of (symbol or None for epsilon, target)
def new(): n = next(ids); edges[n] = []; return n
def sym(c):
    a, b = new(), new(); edges[a].append((c, b)); return Frag(a, b)
def cat(f, g): edges[f.accept].append((None, g.start)); return Frag(f.start, g.accept)
def alt(f, g):
    a, b = new(), new()
    edges[a] += [(None, f.start), (None, g.start)]
    edges[f.accept].append((None, b)); edges[g.accept].append((None, b)); return Frag(a, b)
def star(f):
    a, b = new(), new()
    edges[a] += [(None, f.start), (None, b)]
    edges[f.accept] += [(None, f.start), (None, b)]; return Frag(a, b)

def regex(src):                    # recursive descent over the regex itself
    pos = 0
    def peek(): return src[pos] if pos < len(src) else None
    def alternation():
        nonlocal pos
        f = concat()
        while peek() == "|": pos += 1; f = alt(f, concat())
        return f
    def concat():
        f = repeat()
        while peek() not in (None, "|", ")"): f = cat(f, repeat())
        return f
    def repeat():
        nonlocal pos
        f = atom()
        while peek() == "*": pos += 1; f = star(f)
        return f
    def atom():
        nonlocal pos
        c = peek(); pos += 1
        if c == "(":
            f = alternation(); pos += 1; return f
        return sym(c)
    return alternation()

def closure(states):               # epsilon-closure
    stack, seen = list(states), set(states)
    while stack:
        for c, t in edges[stack.pop()]:
            if c is None and t not in seen: seen.add(t); stack.append(t)
    return frozenset(seen)

def subset(nfa, alphabet):
    start = closure({nfa.start}); names = {start: "A"}; work = [start]; delta = {}
    while work:
        S = work.pop(0)
        for a in alphabet:
            T = closure({t for s in S for c, t in edges[s] if c == a})
            if T not in names: names[T] = chr(ord("A") + len(names)); work.append(T)
            delta[names[S], a] = names[T]
    accept = {names[S] for S in names if nfa.accept in S}
    return names, delta, accept

nfa = regex("(a|b)*abb")
print("NFA states:", len(edges), " epsilon edges:", sum(c is None for e in edges.values() for c, _ in e))
names, delta, accept = subset(nfa, "ab")
print("DFA states:", len(names), " accepting:", sorted(accept))
for S, n in sorted(names.items(), key=lambda kv: kv[1]):
    print(f"  {n} = NFA set {sorted(S)}  a->{delta[n, 'a']}  b->{delta[n, 'b']}")
def accepts(w):
    q = "A"
    for ch in w: q = delta[q, ch]
    return q in accept
for w in ["abb", "aabb", "babb", "ab", "abba", ""]:
    print(f"  {w!r:8} {'accepted' if accepts(w) else 'rejected'}")

NFA states: 14  epsilon edges: 11
DFA states: 5  accepting: ['E']
  A = NFA set [0, 2, 4, 6, 7, 8]  a->B  b->C
  B = NFA set [0, 1, 2, 4, 5, 7, 8, 9, 10]  a->B  b->D
  C = NFA set [0, 2, 3, 4, 5, 7, 8]  a->B  b->C
  D = NFA set [0, 2, 3, 4, 5, 7, 8, 11, 12]  a->B  b->E
  E = NFA set [0, 2, 3, 4, 5, 7, 8, 13]  a->B  b->C
  'abb'    accepted
  'aabb'   accepted
  'babb'   accepted
  'ab'     rejected
  'abba'   rejected
  ''       rejected

The 14-state NFA collapses to a 5-state DFA whose single accepting state E is reached exactly when the input so far ends in abb. Each DFA state's NFA set records which positions of the pattern could have been reached. Running the DFA on a string is now one table lookup per character, with no backtracking and no sets: this is why generated scanners are fast.

Minimizing DFAs

The subset construction does not always produce the smallest DFA. Two states are equivalent if, from each of them, exactly the same strings lead to acceptance; equivalent states can be merged. The standard algorithm refines a partition. It starts with two blocks, accepting and non-accepting states, which certainly differ. Then it repeatedly splits any block containing two states whose transitions on some character go to different blocks, since those states can be distinguished by that character followed by whatever distinguishes the targets. When no block can be split, each block is a state of the minimal DFA. Edward Moore described this method in 1956; John Hopcroft's 1971 refinement, which always splits using the smaller half, runs in \(O(n \log n)\) time for an n-state DFA. The minimal DFA for a regular language is unique up to renaming of states, a fact that also gives a way to test whether two regular expressions describe the same language: minimize both and compare.

# Minimizing a DFA by partition refinement (Moore's algorithm, the simple
# form of Hopcroft's method). Input: the 5-state DFA for (a|b)*abb built by
# the subset construction above.
delta = {("A", "a"): "B", ("A", "b"): "C", ("B", "a"): "B", ("B", "b"): "D",
         ("C", "a"): "B", ("C", "b"): "C", ("D", "a"): "B", ("D", "b"): "E",
         ("E", "a"): "B", ("E", "b"): "C"}
states, alphabet, accept = "ABCDE", "ab", {"E"}
parts = [set(accept), set(states) - accept]          # start: accepting vs not
round_ = 0
while True:
    round_ += 1
    which = {s: i for i, p in enumerate(parts) for s in p}
    new = []
    for p in parts:                                    # split by successor blocks
        groups = {}
        for s in sorted(p):
            key = tuple(which[delta[s, a]] for a in alphabet)
            groups.setdefault(key, set()).add(s)
        new += groups.values()
    print(f"round {round_}:", [''.join(sorted(p)) for p in new])
    if len(new) == len(parts): break
    parts = new
which = {s: ''.join(sorted(p)) for p in parts for s in p}
print("minimal DFA has", len(parts), "states")
for p in sorted(parts, key=lambda p: min(p)):
    s = min(p); name = ''.join(sorted(p))
    tag = " (accepting)" if s in accept else ""
    print(f"  {name:3} a->{which[delta[s, 'a']]:3} b->{which[delta[s, 'b']]}{tag}")

round 1: ['E', 'ABC', 'D']
round 2: ['E', 'AC', 'B', 'D']
round 3: ['E', 'AC', 'B', 'D']
minimal DFA has 4 states
  AC  a->B   b->AC
  B   a->B   b->D
  D   a->B   b->E
  E   a->B   b->AC (accepting)

States A and C both mean the input so far does not end in a useful prefix of abb, so no future input can tell them apart, and they merge. The minimal DFA has four states, one for each length of matched prefix: none, a, ab and abb. This is the kind of reasoning a scanner generator performs automatically for the combined patterns of an entire language.

Scanner generators and the combined automaton

A scanner generator such as lex (Mike Lesk and Eric Schmidt, Bell Labs, 1975), its free successor flex, or re2c takes a list of patterns with actions and produces a scanner. It combines all patterns into one NFA by alternation, remembering which pattern each accepting state belongs to, converts it to a DFA, minimizes it while keeping different tokens' accepting states apart, and emits the transition table or equivalent code. To implement maximal munch, the generated scanner keeps running the DFA past an accepting state, remembering the last accepting position it passed; when the DFA gets stuck, it backs up to that position and emits the token. If two patterns accept the same lexeme, the earlier one wins, so keyword rules are listed before the identifier rule. Transition tables for 256 input characters and hundreds of states would be large, so generators compress them, for example by grouping characters that always behave the same into equivalence classes.

Many production compilers nevertheless use hand-written scanners: GCC, Clang, the Go compiler, rustc and V8 all do. Hand-written scanners are not hard to write for most languages, are easy to debug, give better error messages, handle awkward cases (string interpolation, nested comments, context-dependent tokens) directly, and can be tuned for speed. The theory still matters, because a well-written hand scanner is a DFA in disguise: each branch of its main loop corresponds to a state.

A hand-written scanner for Tern

The scanner below is the one our Tern compiler uses. It examines the first character of each token to decide which pattern applies, then consumes as long a lexeme as that pattern allows. Identifiers are checked against a keyword table, which is simpler and faster than encoding every keyword in the automaton. Two-character operators are tried before one-character ones, which is maximal munch for operators. Every token records its line and column. When the scanner meets a character that cannot start any token, it reports an error and skips the character, so one stray symbol does not hide every later error.

# A hand-written scanner for Tern: maximal munch, keywords versus identifiers,
# line and column tracking, comments, and error recovery that keeps scanning.
KEYWORDS = {"fn", "var", "if", "else", "while", "return", "true", "false", "int", "bool"}
TWO = {"==", "!=", "<=", ">=", "&&", "||", "->"}
ONE = set("+-*/%<>=!(){}[],;:")

def scan(src):
    toks, errors, i, line, col = [], [], 0, 1, 1
    while i < len(src):
        c = src[i]
        if c == "\n": i += 1; line += 1; col = 1; continue
        if c in " \t\r": i += 1; col += 1; continue
        if src.startswith("//", i):                       # comment to end of line
            while i < len(src) and src[i] != "\n": i += 1
            continue
        start = i
        if c.isalpha() or c == "_":                       # identifier or keyword
            while i < len(src) and (src[i].isalnum() or src[i] == "_"): i += 1
            text = src[start:i]
            kind = text if text in KEYWORDS else "ID"   # a keyword is its own kind
        elif c.isdigit():
            while i < len(src) and src[i].isdigit(): i += 1
            text = src[start:i]; kind = "NUM"
            if i < len(src) and (src[i].isalpha() or src[i] == "_"):   # 12abc
                while i < len(src) and src[i].isalnum(): i += 1
                errors.append(f"{line}:{col}: malformed number {src[start:i]!r}")
                col += i - start; continue
        elif src[i:i + 2] in TWO: i += 2; text = src[start:i]; kind = text
        elif c in ONE: i += 1; text = c; kind = c
        else:
            errors.append(f"{line}:{col}: unexpected character {c!r}")
            i += 1; col += 1; continue                    # skip it and carry on
        toks.append((kind, text, line, col)); col += i - start
    toks.append(("EOF", "", line, col))
    return toks, errors

src = """fn max(a: int, b: int) -> int {
    if a >= b { return a; }   // ties go to a
    return b;
}
var x = 12ab + y @ 3;"""
toks, errors = scan(src)
for kind, text, ln, cl in toks[:13]:
    print(f"{ln}:{cl:<3} {kind:7} {text}")
print("...", len(toks), "tokens in total")
for e in errors: print("error:", e)

1:1   fn      fn
1:4   ID      max
1:7   (       (
1:8   ID      a
1:9   :       :
1:11  int     int
1:14  ,       ,
1:16  ID      b
1:17  :       :
1:19  int     int
1:22  )       )
1:24  ->      ->
1:27  int     int
... 35 tokens in total
error: 5:9: malformed number '12ab'
error: 5:18: unexpected character '@'

The scanner reports two errors in the last line and still produces tokens for everything else. The malformed number 12ab is diagnosed as a single error rather than as the integer 12 followed by the identifier ab, a judgment call that produces a clearer message. The arrow -> is a single token, the keyword int is its own token kind rather than an identifier, and the comment in the second line produces no token at all. Production scanners add escape sequences in string literals, Unicode identifiers (Rust and Swift allow them, following the Unicode identifier rules in UAX 31), numeric literals in several bases with separators such as 1_000_000, and nested block comments.

Error handling in scanners

Lexical errors are rare compared with syntax and type errors, but they need sensible handling. The usual strategy is panic mode: report the error, discard characters until something that can start a token appears, and continue. An unterminated string literal is a classic problem because the rest of the file then looks like the inside of a string; good scanners stop the literal at the end of the line and report it there. Some errors are better reported by later phases: an integer literal too large for its type, for example, is easier to diagnose once the type is known. A scanner should also be robust to unusual input, because it is the first code to see untrusted text in tools such as editors and web services. Fuzzing scanners with random input (lesson 12) is a cheap way to find crashes.

Performance

A scanner runs in time linear in the input: each character is examined a constant number of times, apart from the bounded backing up required by maximal munch. Practical speed then depends on constant factors: reading the file in large blocks, avoiding a function call per character, using a sentinel character at the end of the buffer so the main loop needs no separate end-of-input test, and interning identifier strings in a hash table so that later phases compare names by pointer. Clang's lexer, for example, scans raw memory buffers with switch statements on the first character, and SIMD instructions are used in some tools to skip whitespace and comments sixteen or more bytes at a time.

Worked examples