Practical Lexers: Tokenizing Real Source Text

Practical Lexers

Slides 52–55 close the lexical-analysis block: the theory of lexical-analysis-formalism answers “does this character sequence belong to lexeme class $X$?”, but a lexer must answer a different, harder question (slide 53):

1. not one lexeme class is relevant, but several, possibly overlapping ones;
2. not a delimited character sequence is given, but one long program text;
3. the relevant chunking is not known in advance, and it is not necessarily unambiguous.

Milestone warning. The practical work is milestone 1: “lexical analysis for C₀ (roughly after four weeks)“. Slide 18 is explicit: “Copying other implementations (including from LLMs) will result in disqualification. In case of doubt regarding independent work, I will ‘interview’ you.” Everything below is study material for understanding the mechanics and for the vocabulary an exam expects — not a submission to adapt.

1. Why “recognize one class” is not enough

All lexers solve the same geometric problem: given the input string $w=c_1{c}_2\dots c_n$ and a set of lexeme classes $L_1,\dots ,L_k$, produce a sequence of tokens $(t_1,x_1)(t_2,x_2)\dots$ where $x_i$ is a lexeme (the concrete text) and $t_i$ its class.

Slide 23 makes the gap concrete. What the lexer sees:

#include <stdio.h>  int main ( )  int i , n , s ;  scanf ( "%d" ,& n ) ; ...

and what it must produce:

[Keyword "#include", SpecialId "<stdio.h>",
 Keyword "int", SpecialId "main", Symbol "(", Symbol ")", Symbol "{",
 Keyword "int", Ident "i", Symbol ",", Ident "n", Symbol ",", Ident "s", Symbol ";",
 SpecialId "scanf", Symbol "(", Format "\"%d\"", Symbol ",", Symbol "&", ...]

Vocabulary that matters on the exam:

• token = the smallest unit of meaning in the language (keywords, numbers, variables, comments, parentheses, …);
• a token class represents an entire class of concrete lexemes — class number, lexeme 123;
• natural-language analogy: tokens ≈ words/parts of speech; lexical analysis ≈ spell-checking (grammar and meaning are not checked);
• side task: removing whitespace and (if required) comments — they are consumed but not passed on.

Note the C₀-specific classes in that token stream: SpecialId and Format. SpecialId covers text that would otherwise lex as an operator (the #include target <stdio.h>) — a class that only exists because of #include’s </> syntax, and one of the first places where a naive lexer breaks. Format is the "%d" literal form, kept distinct so the later phases can special-case it.

2. Resolving ambiguity: longest match and first match

The lecture names two principles (“To resolve ambiguities”, slide 54):

2.1 Principle of Longest Match (“maximal munch”)

Take the longest prefix of the remaining input that is a lexeme of any class.

2.2 Principle of First Match

Among the candidates, take the one belonging to the earlier rule in the specification.

Production tools use both, in that order of precedence. The flex manual states it exactly ¹:

“If it finds more than one match, it takes the one matching the most text (for trailing context rules, this includes the length of the trailing part, even though it will then be returned to the input). If it finds two or more matches of the same length, the rule listed first in the flex input file is chosen.”

Alex (the Haskell lexer generator — relevant here, see §6.3) behaves the same way: maximal munch first, then earliest rule ².

2.3 Worked example

Input i1 = 1.5e11; with classes

class	regex (tool notation)
IDENT	[A-Za-z][A-Za-z0-9_]*
FLOAT	[0-9]+ "." [0-9]* ([eE][+-]?[0-9]+)?
INT	[0-9]+
SYMBOL	=, ;, (, ), ,, … (one class per punctuation mark, or one class for all)
WS	[ \t\n]+ (consumed, no token)

Trace of maximal munch: at position 0 both IDENT (i1) and the one-character IDENT (i) match; longest wins → IDENT("i1"). At = only SYMBOL matches, length 1. At 1.5e11 both INT (1) and FLOAT (1.5e11) match; longest wins → FLOAT. The ; closes the statement.

Note what maximal munch automatically fixes: 1.5e11 is not lexed as 1 . 5e11, and e11 is not mistaken for an identifier — because “longest” is applied before class choice, not per class.

2.4 Where longest match surprises people

input	maximal munch gives	note
a+++b	a, ++, +, b	not a, +, ++, b — greedy from the left; famous in C
x=y; vs. x==y	== wins over = then =	compound operators must be handled only by longest match, never by “parse = then peek” in an ad-hoc way
if vs. i1	if (2 chars) beats i (1 char)	keywords only work as a tie-break: see §2.5
1..2 (Pascal/Ada range)	1, .., 2 — or 1., .2 in a language with 1. floats	the class set decides; this is why [0-9]+ "." [0-9]* (allowing a trailing dot) is dangerous
/* comment */	whole comment	requires the comment class to be declared before the division operator, or exact tie-break luck
<stdio.h> after #include	<, stdio, ., h, > — not a single lexeme	the reason C₀ has the class SpecialId, handled by context (§6.5)

2.5 Keywords vs. identifiers

Standard delimiters don’t exist, so whilex must be one identifier while while is a keyword. Two ways:

• declare keywords as their own classes and rely on maximal munch (while matches len 5 as keyword, len 5 as identifier → tie → first rule wins → put keyword rules first);
• or lex everything as IDENT and reclassify via a hash lookup in the scanner action (the usual hand-written-lexer approach, and what most compilers do because it scales to hundreds of keywords).

Both give the same result; the tie-break order in the tool input file is what actually decides.

3. Escaping and quoting: meta vs. object symbols

Lexer specifications are meta languages describing an object language over the same characters, so symbols play double roles. Slide 55 lists the resulting needs:

• notation for excluded symbols — [^...] (flex, Alex), i.e. the object-language complement, which is not expressible in the pure regex core of the lecture (it needs an alphabet-sized union);
• escaping or quoting to distinguish object from meta symbols: \. = a literal dot, \* = a literal star, "if" = the word if even though it could be read as operations;
• whitespace, line beginnings and endings, and contexts in general get special treatment — ^, $, \n, start conditions.

Concretely: to match the C division operator you write /; to match a C comment you write /\* … \*/; to match the C source line x = a/b; as text you’d have to escape the /. Getting this wrong is the most common “my lexer works on the test input but not on the real one” bug.

4. Implementation: one automaton instead of many

4.1 The construction (slide 54)

1. Build a separate NFA for each lexeme class.
2. Mark each final state with the name of the respective lexeme class.
3. Merge everything into a single NFA — via $\epsilon$-transitions from a new, single initial state.
4. Convert the whole NFA into a DFA (and potentially minimize it).
5. Emit a transition table; the scanner is a loop over that table.

This is the payoff of everything in lexical-analysis-formalism: steps 4 and 5 are the powerset construction and minimization, applied once to the union automaton. No per-class scanning, no regex matching at run time — a single linear pass.

flowchart LR
    A["regex per class<br/>(IDENT, FLOAT, SYMBOL, …)"] --> B["NFA per class<br/>final states labelled"]
    B --> C["one NFA<br/>via ε from new start"]
    C --> D["DFA<br/>powerset construction"]
    D --> E["minimal DFA<br/>partition refinement"]
    E --> F["transition table"]
    F --> G["scanner loop<br/>+ maximal munch"]

Since final states of the merged NFA are labelled, the powerset construction needs one addition to the lecture’s $F^{\prime }=\{s^{\prime }\mid s^{\prime }\cap F\ne \varnothing \}$: a DFA state containing several labelled NFA-final states encodes several candidate classes at once. That collision is exactly the ambiguity of §2, and it is resolved by

$$\text{accepting class of }{s}^{\prime }=\min \{i\mid i\in \text{labels}(s^{\prime }\cap F)\}\text{(first match rule)}$$

while the longest match rule is resolved one level up, in the driver loop (§4.3). This split — “longest match = driver, first match = label order” — is worth remembering, because it explains why the rule order in a tool input file matters and why renaming/reordering rules can silently change the token stream.

4.2 The scanner driver (maximal munch with backtracking)

The DFA gives, for a fixed start position, the set of all prefixes that end in an accepting state. Maximal munch = keep going and remember the last accepting position:

scan(pos):
    state   = s0'
    last_acc = none            # (position, class)
    i        = pos
    while i < len(input) and sigma'(state, input[i]) is defined:
        state = sigma'(state, input[i])
        i     = i + 1
        if state is accepting:
            last_acc = (i, label(state))       # remember, do not stop
    if last_acc = none:
        error(pos)                              # no lexeme starts here
    (end, cls) = last_acc
    return TOKEN(cls, input[pos:end], pos, end)   # resume scanning at end

Properties:

• linear time in the input length per token, no backtracking in the regex sense — the “backtracking” above is just retiring to the last accepting position, at most one per token;
• the maximal-munch rule and the first-match rule both live in this ~15-line loop;
• if you want to hand-write the C₀ lexer, this loop plus a case per token class is the entire architecture. (Which is a legitimate design for the milestone — the lecture’s tooling route is Haskell plus generated lexers, see §6.3.)

Note on picking the language for the milestone. The course implements C₀ in Haskell, largely with DSLs from which Haskell code is generated (“live programming, no sample solutions”). A 20-line table-driven loop and a 400-line pattern match are both fine designs; what the milestone checks is that the token stream is right, not which style you used.

4.3 Table layout

Minimized DFA → one row per state, one column per symbol class, one extra column for “accepting class or none”:

state	a–z, A–Z, _	0–9	.	+ - * / ; , ( ) { }	"	…	accept
0	1	2	–	4	5		–
1	1	1	–	–	–		IDENT
2	–	2	3	–	–		INT
…

Compressing the alphabet into classes (letters, digits, everything else) is the standard trick; on a full 256-character table the memory per state is 1 KB, which is why real scanners either compress rows or switch on character classes first.

5. What a lexer cannot do with regular expressions alone

Slide 53’s “not necessarily unambiguous” and the regex limits from lexical-analysis-formalism §2.5 combine into a short list of things no regular expression can express — and the standard workarounds:

Problem	Why not regular	Standard workaround
nested comments ({- {- -} -}, Rust /* /* */ */)	needs a counter → not regular	hand-written code with a depth counter; tools use start states (flex) or a bespoke wrapper (GHC’s own lexer is hand-written for this and other reasons)
Python indentation	layout depends on a stack of indent levels	lexer keeps an explicit indent stack and synthesises INDENT/DEDENT tokens
C’s typedef ambiguity (T * x; — declaration or multiplication?)	depends on symbol-table context	the classic “lexer hack”: feed the parser’s symbol table back into the lexer, or parse ambiguously and decide later
Haskell layout rule (offside rule)	contextual	implemented in the lexer as a state machine over an indent stack (GHC: Layout module)
string interpolation with nesting ("${ {..} }")	needs balanced delimiters	lexer mode stack / recursive scanning
#include-style context (<stdio.h> only right after #)	needs one token of lookbehind	start conditions or an explicit mode switch (C₀: SpecialId)

The general lesson: regular expressions are the right tool for the token shape, not for the token context. Everything context-dependent is either a lexer mode (finite state, still regular-but-with-many-states) or a job for later phases.

6. Lexer generators

Slide 55: generators are

• practically always based on the regex notation 0[xX][0-9a-fA-F]+;
• sometimes extended: excluded symbols, ranges, $, contexts, inline code predicates;
• in need of escaping/quoting to separate meta from object symbols;
• fed with a list of regular expressions, each combined with a token type or an action;
• special-cased for whitespace, and often for line beginnings/endings or contexts.

6.1 What the generator does with the input

flowchart LR
    S["spec: ordered rule list<br/>regex + action"] --> P["parse to RE trees"]
    P --> N["NFA per rule<br/>(Thompson)"]
    N --> U["merged NFA<br/>accepting labels = rule index"]
    U --> D["DFA (powerset)"]
    D --> M["minimize"]
    M --> T["tables + driver<br/>(host-language code)"]

Everything in this pipeline is the lecture’s material; the generator only adds rule ordering, actions, and error/position bookkeeping.

6.2 Tool landscape

Tool	Host language	Notes
lex (POSIX), flex	C	the reference implementation of the whole pipeline; longest match + rule order; trailing context r/s; start conditions %x/%s; yyless(n), REJECT, yymore() for the rare non-regular corner
re2c	C/C++	no runtime library, generates a pure DFA in the source; popular for speed-critical scanners (PHP, Ninja)
JFlex	Java	regex-driven, long-standing standard for JVM lexers
ocamllex	OCaml	rule/parse, longest match, as bindings
Alex	Haskell	maximal munch, earliest rule wins, trailing context token / context (context not consumed), $ = newline context, Haskell predicates as context; wraps a state machine as alexScan 2
ANTLR	Java/…	combined lexer+parser from one grammar (an ANTLR4 lexer is still DFA-based)
hand-written	any	what clang, rustc, Go, GHC, and most production compilers actually do: full control over error messages, context-sensitivity and performance; more code, more bugs

Two selection criteria worth remembering: generated wins when the token classes are stable and regular (config formats, protocols, small languages); hand-written wins when context-sensitivity, error recovery, or lexical quirks dominate. C₀ is small enough that either is defensible — which is presumably why the milestone leaves the design open.

6.3 flex specifics that leak into the theory

Because the lecture’s “practical lexers” is tool-oriented, these are the parts of flex/Alex behaviour worth knowing by name:

• rule order matters — first match breaks ties of equal length (§2.2), so if must precede the identifier rule;
• trailing context r/s — matches r only when followed by s; the matched text is r (length counted including s for the longest-match decision, per the flex manual). This is how you lex “a * that is not */”-style cases without a full state machine;
• $ = “end of line” shorthand for a trailing \n context;
• start conditions — <COMMENT>… rules active only in a lexer mode: this is how comments, strings, and #include targets are usually handled;
• yyless(n) / REJECT — give back input / try the next-best rule: escape hatches for the handful of cases where longest-match-then-first-rule is wrong;
• action code — arbitrary host-language code per rule; this is where keywords are reclassified and where symbol tables are touched (the “lexer hack”).

6.4 Unicode

Real source text is UTF-8. Two pragmatic options: treat the input as bytes (a token class per byte class — wrong for identifiers outside ASCII) or decode to code points first and let classes range over code points. Most generators operate on the host’s character type; for a course language ASCII is fine, but know that “alphabet $\Sigma$” in the theory is an arbitrary finite set, so nothing breaks — the table just gets bigger.

6.5 Error handling and positions

Not exam material in this lecture (“pragmatical: no focus on good error messages”, slide 14), but unavoidable in the milestone:

• no rule matches at the current position → the scanner must report position + offending character, and either abort or skip one character as an ERROR token;
• position tracking: keep line/column counters in the driver, not in the actions, so every token carries a span (needed by every later phase’s error messages);
• unterminated string/comment at end of input → a distinct error, not “no match”;
• lexeme length limits — none in theory, arbitrary in practice (identifier length, integer overflow at token→value conversion: that conversion is the lexer’s job, and it is where numeric literals become actual Haskell/C values).

7. Checklist for the C₀ lexer milestone

Derived from the token stream on slide 23 — the classes a C₀ lexer must distinguish:

class	examples	gotcha
keywords	int, while, if, return, #include	must beat the identifier rule by rule order
SpecialId	main, scanf, printf, <stdio.h>	the #, the <…> and the “only in include context” part are all context-dependent (§5)
identifiers	i, n, s	maximal munch: while1, i1
numbers	0, 1, 123	longest match vs. a future float class; leading zeros
format strings	"%d"	escapes inside strings; unterminated at EOF
string literals	"…" (if C₀ has them)	escape sequences: the scanner unescapes, the lexeme keeps the raw text
symbols	( ) { } , ; = < <= > >= == != + - * / & ! % and the rest of the operator set	multi-character symbols need longest match; <= vs. < =
operators/keywords divergence	& in scanf("%d",&n)	& is a symbol, not “address-of” — the lexer does not know semantics
comments	/* … */	longest match beats /; unterminated at EOF
whitespace	spaces, tabs, newlines	consumed silently, but must still advance line counters

And the invariant the lexer must guarantee to the next phase: a well-formed token sequence with spans, where every token is a valid lexeme of its class, and the concatenation of all consumed text plus whitespace/comments reconstructs the input exactly (this last property is what a lexer test suite should check first).

8. Sources

Source	Used for
slides 52–55 (raw/compilerbau/compilerbau-slides-55.md)	problem statement, longest/first match, merge-to-one-DFA construction, generator requirements
slide 23 (token stream example)	the C₀ class checklist in §7
flex manual, Matching	exact longest-match / first-rule tie-break wording, trailing context length accounting
Alex manual	maximal-munch + earliest-rule behaviour, / trailing context, $, predicate contexts, performance warning
Mogensen, Introduction to Compiler Design, Springer 2017 — ch. 2	the book’s lexer-generator chapter, aligned with the lecture

Related: lexical-analysis-formalism (the theory behind §4), Compiler Construction course page, concept map.

Footnotes

1. Lexical Analysis With Flex, for Flex 2.6.2 — Matching, https://westes.github.io/flex/manual/Matching.html ↩

2. Alex manual, https://haskell-alex.readthedocs.io — “the longest match wins; if two rules match the same length, the earlier one in the file wins”, trailing context via /. ↩ ↩²