Lesson 1.8 — Recognizing keywords: hash tables, perfect hashing, tries, switch on length¶

Techniques: a hash table of pre-interned keywords (Clang's IdentifierTable, rustc's symbol interner), perfect hashing (gperf), tries and keywords compiled into the DFA (re2c, flex), switch on length (LLVM TableGen's StringMatcher, Pebble's reference lexer) · Pebble implements: switch on length in the reference solution; tok::getKeywordKind (provided) is the linear-scan baseline · Prerequisites: Lessons 1.5, 1.6 · Time: 2–3 hours

A hand-written lexer scans while with the identifier loop and then has to ask: is this word one of Pebble's 21 keywords? The question is asked for every identifier in every file, so it must be cheap for the common answer, "no". This lesson compares four answers: look it up in the identifier hash table that also interns names; compute a hash function that is perfect for the keyword set; walk a trie (or let the lexer DFA do it); or switch on the length and compare against the few keywords of that length.

1. Problem and motivation¶

Given a fixed finite set \(K\) of keywords (Pebble: 21 words of length 2–8) and a word \(w\) produced by the identifier scanner, decide \(w \in K\) and return its token kind. Constraints: \(K\) is known at compile time; most \(w\) are not keywords; the answer must be exact.

Hash table with pre-interned keywords¶

Compilers intern every identifier: a hash table maps each distinct spelling to one object (Clang's IdentifierInfo, rustc's Symbol), so later phases compare names by pointer. If the keywords are inserted into this table at startup, with their token kind stored in the entry, keyword recognition costs nothing extra: the lookup the lexer does anyway returns the kind [Dragon2 §3.1.3, §2.7].

Perfect hashing (gperf)¶

For a fixed \(K\) a hash function can be chosen with no collisions on \(K\): a perfect hash. Cichelli [Cic80] built minimal perfect hashes for Pascal's reserved words from the length and the first and last letters; Schmidt's gperf [Sch90] generalizes the search to any key positions and generates C/C++ code. GCC's C++ front end uses gperf-generated tables for fixed name sets (C library function names, standard-library name hints), while its keywords, like Clang's, are identifiers pre-entered in the identifier hash table with a keyword code (init_reswords and C_SET_RID_CODE in gcc/cp/lex.cc, GCC 15.1).

Tries and keywords in the DFA¶

A trie [Fre60] stores the keywords as paths of characters; recognition walks one node per character and fails at the first mismatch. A lexer DFA built from rules if, int, …, [a-z]+ contains the trie of the keywords automatically (Lesson 1.5's re2c output), so generated lexers need no separate lookup.

Switch on length¶

Group the keywords by length, switch on the length of \(w\), then compare characters (or whole strings) within the group. The length is known for free after scanning, and most groups are tiny. LLVM's TableGen emits string matchers this way (StringMatcher), and Pebble's reference lexer uses it.

2. Definitions and algorithms¶

Definition 1.8.1 (Keyword recognizer)

For a finite \(K \subseteq \Sigma^{*}\) and a kind map \(\kappa : K \to \mathrm{Kinds}\), a keyword recognizer is a function \(\mathrm{kw}(w) = \kappa(w)\) if \(w \in K\) and identifier otherwise. Its cost is the number of character comparisons and table accesses it makes on \(w\).

Definition 1.8.2 (Perfect and minimal perfect hash)

A function \(h : \Sigma^{*} \to \{0, \dots, m-1\}\) is perfect for \(K\) if it is injective on \(K\), and minimal perfect if moreover \(m = \lvert K \rvert\). gperf searches functions of the form \(h(w) = \lvert w \rvert + \sum_{j \in P} a[w_j]\) (optionally with \(a[w_{\lvert w\rvert}]\) for the last character) for a set \(P\) of key positions and an associated value table \(a : \Sigma \to \mathbb{N}\).

Definition 1.8.3 (Trie)

The trie of \(K\) is the rooted tree whose nodes are the prefixes of words of \(K\), with an edge labelled \(c\) from \(u\) to \(uc\), and a node marked final (with \(\kappa(u)\)) iff \(u \in K\). It is the minimal deterministic acyclic automaton for \(K\) only after merging equal subtrees (Revuz; Lesson 1.4 §6); the plain trie is a DFA that is minimal up to shared suffixes.

Definition 1.8.4 (Interning)

An interning table maps each string \(s\) to a unique object \(\iota(s)\) with \(\iota(s) = \iota(s') \iff s = s'\). A keyword-aware table stores \(\kappa(s)\) in \(\iota(s)\) for \(s \in K\) (inserted before lexing starts) and identifier for every other string.

Hash table with pre-interned keywords¶

Algorithm 1.8.5 (Lookup in a keyword-seeded interning table)

Input: the identifier text \(w\); an open-addressing hash table \(H\) with hash function \(g\).
Output: \(\iota(w)\) and its kind.
Precondition: every \(k \in K\) was inserted with kind \(\kappa(k)\) before lexing.
Postcondition: the kind is \(\mathrm{kw}(w)\) (Proposition 1.8.9); \(w\) is now interned.
Invariant: \(H\) contains each interned string exactly once.

function Intern(w):
    i ← g(w) mod |H|
    while H[i] ≠ empty:
        if H[i].hash = g(w) and H[i].text = w: return H[i]         # found: keyword or known identifier
        i ← (i + 1) mod |H|                                        # linear probing
    H[i] ← new entry {text: w, hash: g(w), kind: identifier}       # grow H when it is too full
    return H[i]

function Setup(K): for k in K: Intern(k).kind ← κ(k)

Clang seeds its identifier table with keywords; rustc pre-interns them as symbols

Reproduce (Clang/LLVM llvmorg-23.1.2, Rust 1.94.1; any OS with curl):

curl -sSfL https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/clang/lib/Basic/IdentifierTable.cpp -o IdentifierTable.cpp
grep -n 'static void AddKeyword(StringRef Keyword,\|^void IdentifierTable::AddKeywords\|  AddKeyword(StringRef(#NAME), tok::kw_ ## NAME' IdentifierTable.cpp
curl -sSfL https://raw.githubusercontent.com/rust-lang/rust/1.94.1/compiler/rustc_span/src/symbol.rs -o symbol.rs
sed -n '33p;44,50p' symbol.rs

Output (complete):

216:static void AddKeyword(StringRef Keyword,
269:void IdentifierTable::AddKeywords(const LangOptions &LangOpts) {
272:  AddKeyword(StringRef(#NAME), tok::kw_ ## NAME,  \
    Keywords {
        // Keywords that are used in stable Rust.
        // Matching predicates: `is_used_keyword_always`/`is_reserved`
        // tidy-alphabetical-start
        As:                 "as",
        Break:              "break",
        Const:              "const",
        Continue:           "continue",

What to notice: Clang's IdentifierTable constructor calls AddKeywords, which expands TokenKinds.def into one AddKeyword per keyword; each creates the IdentifierInfo for the spelling and stores its token kind, so the lexer's single lookup per identifier (Preprocessor::LookUpIdentifierInfo, called from Lexer::LexIdentifierContinue) also classifies keywords (Algorithm 1.8.5). rustc's symbols! macro pre-interns keywords as the first Symbols (kw::As, kw::Break, …): its lexer (rustc_lexer) returns every word as Ident, and later code compares the interned symbol against kw::… by index.

Perfect hashing (gperf)¶

Algorithm 1.8.6 (gperf-style perfect hash lookup, and the search that builds it)

Input: \(w\); generated tables \(a[\cdot]\) and \(\mathit{wordlist}[0..m-1]\) (empty slots hold "").
Output: \(\mathrm{kw}(w)\).
Precondition: \(h\) (Definition 1.8.2) is perfect for \(K\) and \(\mathit{wordlist}[h(k)] = k\) for \(k \in K\).
Postcondition: exact answer (Proposition 1.8.10).
Invariant (search): the partial assignment of \(a\) keeps the hash values of already-placed keywords distinct.

function Lookup(w):
    if |w| < MIN_WORD_LENGTH or |w| > MAX_WORD_LENGTH: return identifier
    k ← |w| + Σ_{j ∈ P} a[w_j]
    if k ≤ MAX_HASH_VALUE and wordlist[k] ≠ "" and wordlist[k] = w: return κ(w)   # one string compare
    return identifier

function Search(K, P):                               # simplified gperf/Cichelli backtracking search
    order the keywords so that frequent key characters are assigned first
    Assign(0)
function Assign(i):
    if i = |K|: return success
    for every unassigned character c among K[i]'s key positions, for v in 0..limit:
        a[c] ← v
        if h(K[i]) differs from h(K[0..i−1]) and Assign(i + 1): return success
    unassign; return failure                         # backtrack

gperf on Pebble's 21 keywords

Reproduce (GNU gperf 3.1; any OS):

cat > kw.gperf <<'EOF'
%struct-type
%language=C++
%define class-name PebbleKeywords
struct Keyword { const char *name; int kind; };
%%
as, 1
bool, 2
break, 3
continue, 4
else, 5
extern, 6
false, 7
float, 8
fn, 9
for, 10
if, 11
in, 12
int, 13
let, 14
mut, 15
return, 16
str, 17
struct, 18
true, 19
var, 20
while, 21
%%
EOF
gperf kw.gperf > kw.hpp
grep -n 'define TOTAL_KEYWORDS\|define MIN_WORD_LENGTH\|define MAX_WORD_LENGTH\|define MIN_HASH_VALUE\|define MAX_HASH_VALUE\|return len + asso_values\|if (\*str == \*s && !strcmp' kw.hpp

Output (complete):

35:#define TOTAL_KEYWORDS 21
36:#define MIN_WORD_LENGTH 2
37:#define MAX_WORD_LENGTH 8
38:#define MIN_HASH_VALUE 3
39:#define MAX_HASH_VALUE 33
82:  return len + asso_values[static_cast<unsigned char>(str[1])] + asso_values[static_cast<unsigned char>(str[0])];
147:          if (*str == *s && !strcmp (str + 1, s + 1))

What to notice: gperf chose key positions \(P = \{1, 2\}\) (the first two characters) and found associated values that make \(h(w) = \lvert w \rvert + a[w_2] + a[w_1]\) injective on the 21 keywords, with values in \(3..33\): 31 slots, perfect but not minimal. A lookup is one addition, two table reads, a length check, a first-character check, and one strcmp (line 147): the final comparison is what rejects non-keywords that collide with a keyword's slot.

Tries and keywords in the DFA¶

Algorithm 1.8.7 (Trie lookup, and keywords in the lexer DFA)

Input: \(w\); the trie of \(K\) (Definition 1.8.3) as nodes with child maps.
Output: \(\mathrm{kw}(w)\).
Precondition: none.
Postcondition: exact (Proposition 1.8.11).
Invariant: after reading \(w_1 \cdots w_i\), the current node is the prefix \(w_1 \cdots w_i\) (or "none" if it is not a prefix of any keyword).

function TrieLookup(w):
    node ← root
    for c in w:
        node ← node.child[c] if it exists else return identifier     # first mismatch: done
    return node.kind if node is final else identifier

# In a generated lexer: add one rule per keyword before the identifier rule; the subset
# construction merges the keyword trie into the identifier DFA, and priority (Lesson 1.6)
# gives the keyword kind to the final trie states.

re2c compiles the keywords into the identifier DFA

Reproduce (re2c 3.1; kwid.re is the file of Lesson 1.5's re2c box, rules if, int, [a-z]+):

re2c -W -i --case-ranges -o kwid.re.c kwid.re
sed -n '/^yy5:/,/^yy10:/p' kwid.re.c

Output (complete):

yy5:
    yych = *++YYCURSOR;
    switch (yych) {
        case 'f': goto yy6;
        case 'n': goto yy8;
        default: goto yy3;
    }
yy6:
    yych = *++YYCURSOR;
    switch (yych) {
        case 'a' ... 'z': goto yy2;
        default: goto yy7;
    }
yy7:
    { return 1; }
yy8:
    yych = *++YYCURSOR;
    switch (yych) {
        case 't': goto yy9;
        default: goto yy3;
    }
yy9:
    yych = *++YYCURSOR;
    switch (yych) {
        case 'a' ... 'z': goto yy2;
        default: goto yy10;
    }
yy10:

What to notice: yy5 is the trie node for i, with children f (yy6) and n (yy8), and yy8 → t → yy9 spells int; every mismatch falls back into the identifier states (yy2/yy3). yy6 (after if) and yy9 (after int) accept only if the next character ends the word; otherwise they continue as identifiers (iff, integer). The trie is embedded in the DFA, so the keyword test costs nothing beyond scanning the identifier.

Switch on length¶

Algorithm 1.8.8 (Switch on length, then compare)

Input: \(w\) and its length \(\ell\) (known from the scan).
Output: \(\mathrm{kw}(w)\).
Precondition: the keyword groups \(K_\ell = \{\, k \in K \mid \lvert k \rvert = \ell \,\}\) are known at build time.
Postcondition: exact.
Invariant: only keywords of length \(\ell\) are compared.

function SwitchOnLength(w):
    switch |w|:
        case ℓ for each nonempty K_ℓ:
            for k in K_ℓ: if w = k: return κ(k)        # or: switch on w[j] for a distinguishing j
        default: break
    return identifier

# TableGen's StringMatcher goes further: inside a length group it switches on the first
# character position where the remaining candidates differ, recursively (a trie over
# the group), and compares the common remaining bytes with memcmp.

LLVM TableGen emits string matchers as a switch on the length

Reproduce (LLVM llvmorg-23.1.2; any OS with curl):

curl -sSfL https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/lib/TableGen/StringMatcher.cpp | sed -n '129,150p'

Output (complete):

void StringMatcher::Emit(unsigned Indent, bool IgnoreDuplicates) const {
  // If nothing to match, just fall through.
  if (Matches.empty()) return;

  // First level categorization: group strings by length.
  std::map<unsigned, std::vector<const StringPair*>> MatchesByLength;

  for (const StringPair &Match : Matches)
    MatchesByLength[Match.first.size()].push_back(&Match);

  // Output a switch statement on length and categorize the elements within each
  // bin.
  OS.indent(Indent*2+2) << "switch (" << StrVariableName << ".size()) {\n";
  OS.indent(Indent*2+2) << "default: break;\n";

  for (const auto &[Length, Matches] : MatchesByLength) {
    OS.indent(Indent * 2 + 2)
        << "case " << Length << ":\t // " << Matches.size() << " string"
        << (Matches.size() == 1 ? "" : "s") << " to match.\n";
    if (EmitStringMatcherForChar(Matches, 0, Indent, IgnoreDuplicates))
      OS.indent(Indent*2+4) << "break;\n";
  }

What to notice: Emit groups the strings by length and prints switch (Str.size()) with one case per length (Algorithm 1.8.8), then EmitStringMatcherForChar builds the per-length trie of nested switches. TableGen uses it for assembler mnemonic and register-name matchers in every LLVM backend.

3. Worked example¶

Hash table with pre-interned keywords¶

Suppose the table has 64 slots and (for illustration) \(g\) maps while to slot 17 and whilst to slot 17 too. Setup inserts while (kind kw_while) at 17. Lexing whilst: slot 17 holds while, the hash values differ or the texts differ, so probe 18: empty, insert whilst as an identifier. Lexing while later: slot 17, same hash, same text: kind kw_while, and the identifier object is shared with every other occurrence. One hash computation per identifier token, which the compiler needs anyway for interning.

Perfect hashing (gperf)¶

With gperf's associated values (\(a[\texttt{a}] = 20\), \(a[\texttt{b}] = 0\), \(a[\texttt{e}] = a[\texttt{f}] = 5\), \(a[\texttt{h}] = 5\), \(a[\texttt{i}] = 10\), \(a[\texttt{l}] = 0\), \(a[\texttt{m}] = 15\), \(a[\texttt{n}] = 0\), \(a[\texttt{o}] = 10\), \(a[\texttt{r}] = a[\texttt{s}] = a[\texttt{t}] = 0\), \(a[\texttt{u}] = 10\), \(a[\texttt{v}] = 0\), \(a[\texttt{w}] = 5\), \(a[\texttt{x}] = 5\), \(a[\texttt{c}] = 15\), read from asso_values in kw.hpp), \(h(w) = \lvert w \rvert + a[w_2] + a[w_1]\):

keyword	\(\lvert w\rvert\)	\(a[w_1]\)	\(a[w_2]\)	\(h\)	keyword	\(\lvert w\rvert\)	\(a[w_1]\)	\(a[w_2]\)	\(h\)
str	3	0	0	3	int	3	10	0	13
true	4	0	0	4	bool	4	0	10	14
break	5	0	0	5	while	5	5	5	15
struct	6	0	0	6	extern	6	5	5	16
fn	2	5	0	7	if	2	10	5	17
let	3	0	5	8	for	3	5	10	18
else	4	5	0	9	as	2	20	0	22
float	5	5	0	10	var	3	0	20	23
return	6	0	5	11	mut	3	15	10	28
in	2	10	0	12	false	5	5	20	30
					continue	8	15	10	33

All 21 values are distinct. Non-keywords: fnord hashes to \(5 + 0 + 5 = 10\), the slot of float; the first characters agree (f) and strcmp("nord", "loat") rejects it. wh hashes to \(2 + 5 + 5 = 12\), the slot of in: the first-character check (w vs i) rejects it without strcmp.

Tries and keywords in the DFA¶

The trie of Pebble's keywords has 74 nodes (the 84 characters of the 21 keywords, minus shared prefixes such as f in false, float, fn, for, st in str/struct, in in in/int, plus the root). Looking up integer: root →i →n (final: in) →t (final: int) →e: no child, return identifier after four comparisons. Looking up x: no child of the root: one comparison.

Switch on length¶

Pebble's reference lexer (solutions/pebble/lib/Lex/src/Lexer.cpp, keywordKind) groups by length:

length	keywords	comparisons for a non-keyword of that length (worst)
2	as, fn, if, in	4
3	for, int, let, mut, str, var	6
4	bool, else, true	3
5	break, false, float, while	4
6	extern, return, struct	3
8	continue	1
other	–	0

integer (length 7) is rejected by the switch alone. Most comparisons fail on the first byte (std::string_view::operator== compares lengths first, then bytes).

Try it

Change labs/ch01-regex/inputs/pebble.lexspec so that identifier comes before the keywords and run ch01-regexbench: every keyword is now lexed as an identifier (Lesson 1.6's priority rule) and the ★ lab test TableLexer.AgreesWithTheHandWrittenPebbleLexer fails.

4. Invariants and correctness¶

Hash table with pre-interned keywords¶

Proposition 1.8.9 (Seeded interning recognizes keywords)

After Setup(K), Intern(w).kind \(= \mathrm{kw}(w)\) for every \(w\).

Proof

Linear probing with full-text comparison returns the unique entry whose text equals \(w\) if one exists (the probe sequence for \(g(w)\) passes every slot that \(w\) could have been inserted into before reaching an empty slot, because entries are never deleted). Keywords were inserted first with their kinds; an identifier inserted later cannot equal a keyword's text, or the lookup would have found the keyword's entry. So the entry for \(w\) has kind \(\kappa(w)\) if \(w \in K\) and identifier otherwise. \(\square\)

Perfect hashing (gperf)¶

Proposition 1.8.10 (Perfect-hash lookup is exact)

If \(h\) is perfect for \(K\) and \(\mathit{wordlist}[h(k)] = k\) for every \(k \in K\), then Lookup(w) returns \(\kappa(w)\) if \(w \in K\) and identifier otherwise.

Proof

If \(w \in K\), the length checks pass, \(h(w) \le\) MAX_HASH_VALUE, and \(\mathit{wordlist}[h(w)] = w\), so the comparison succeeds. If \(w \notin K\), any slot it reaches holds either "" or some \(k \neq w\), and the final string comparison fails. Perfectness is what guarantees that one comparison suffices for keywords: no two keywords share a slot. \(\square\)

Tries and keywords in the DFA¶

Proposition 1.8.11 (Trie lookup is exact; keywords in the DFA get their kind)

TrieLookup returns \(\mathrm{kw}(w)\). In a lexer DFA with keyword rules before the identifier rule, the state reached on a keyword \(k\) has tag \(\kappa(k)\).

Proof

By induction on \(i\), the node after \(i\) characters is the prefix \(w_1 \cdots w_i\) (the invariant), or the walk stopped because no keyword has that prefix. At the end the node is \(w\) itself and is final iff \(w \in K\). The DFA claim is Proposition 1.6.9 (tags = minimum rule index), since each keyword rule precedes the identifier rule. \(\square\)

Switch on length¶

Proposition 1.8.12 (Switch on length is exact, and every exact recognizer must read all of \(w\) when \(w\) is a keyword)

(i) SwitchOnLength returns \(\mathrm{kw}(w)\). (ii) Any keyword recognizer that answers correctly must examine every character of \(w\) when \(w \in K\) (or know it from an equivalent source such as a hash of all characters).

Proof

(i) A keyword equal to \(w\) has length \(\lvert w \rvert\), so it lies in the group that is searched, and every member of the group is compared. (ii) Adversary argument. Let \(w \in K\) and suppose that for some position \(j\) there is a character \(c\) such that \(w' = w_1 \cdots w_{j-1}\, c\, w_{j+1} \cdots w_\ell \notin K\) (true for Pebble: take \(c\) = _). If a correct recognizer never examined position \(j\) on input \(w\), it would make exactly the same accesses and return the same answer on \(w'\), which differ only there; but \(\mathrm{kw}(w) \neq \mathrm{kw}(w')\). So it examines every such position. \(\square\)

5. Complexity¶

Variables: \(\ell = \lvert w \rvert\); \(\lvert K \rvert\) keywords; \(L\) = maximal keyword length; \(\sigma\) = alphabet size.

Technique	Lookup time (worst)	Typical	Space	Build
Linear scan (`tok::getKeywordKind`)	\(O(\lvert K \rvert \cdot \ell)\)	\(\lvert K\rvert\) first-byte compares	none	none
Seeded interning hash table	\(O(\ell)\) hash + expected \(O(1)\) probes	shared with interning: ~free	table for all identifiers	\(O(\lvert K \rvert)\) inserts
gperf perfect hash	\(O(\lvert P \rvert + \ell)\)	a few adds + one `strcmp`	\(O(\sigma + \max h)\)	search: exponential worst case, fast in practice
Trie / DFA-embedded	\(O(\ell)\)	stops at first mismatch	\(O(\sum_{k}\lvert k \rvert)\) nodes	\(O(\sum_{k}\lvert k\rvert)\)
Switch on length	\(O(\lvert K_\ell \rvert \cdot \ell)\)	0 compares for unused lengths	code only	none

The interning table's \(O(1)\) probes are expected under a good hash function (a universal family [CLRS4 §11.3]); adversarial identifiers can force collisions, which is why compilers use seeded or strong hash functions for their identifier tables.

Pathological input for the linear scan: an identifier of a keyword length that shares a long prefix with many keywords (whilf, returm) costs a full comparison against each same-length keyword; for gperf, a non-keyword that lands on an occupied slot costs one strcmp of up to \(L\) bytes.

At scale. In the lab benchmark Pebble's switch-on-length lexer runs at 104 MB/s including keyword recognition; keywords are about a quarter of all tokens in typical code, so the choice among these techniques moves the total by a few percent at most.

Hash table with pre-interned keywords¶

Keyword status per language mode (Clang's getKeywordStatus): the same table serves C, C++, OpenCL…; a keyword not enabled in the current mode stays an identifier.
Symbol indices instead of pointers (rustc's Symbol is a u32; keywords get the smallest indices, so "is a keyword" is an integer range check).

Perfect hashing (gperf)¶

Minimal perfect hashing (Cichelli [Cic80]; gperf with -m): fewer empty slots; the search is harder.
Hash-and-displace / CHD and FKS [FKS84]: perfect hashing for large key sets in \(O(1)\) worst-case lookup; overkill for 21 keywords, standard for large static dictionaries.

Tries and keywords in the DFA¶

Merged-suffix tries (DAWGs): minimize the trie as an acyclic DFA (Revuz's linear algorithm, Lesson 1.4 §6).
Ternary search trees / compressed (Patricia) tries: less memory per node for large alphabets.

Switch on length¶

Switch on length, then on a distinguishing position (LLVM StringMatcher): a decision tree per length group.
Compare as integers: load 2, 4 or 8 bytes and compare against constant integers (common in hand-tuned lexers), which turns short string comparisons into one instruction.

7. In real compilers¶

Hash table with pre-interned keywords¶

LLVM / Clang

clang/lib/Basic/IdentifierTable.cpp — IdentifierTable::AddKeywords and AddKeyword seed the table from TokenKinds.def; clang/lib/Lex/Lexer.cpp / Preprocessor::LookUpIdentifierInfo does the one lookup per identifier (LLVM 23.1.2) [CLANG-IdentifierTable]; box in §2.

rustc compiler/rustc_span/src/symbol.rs — the symbols! macro's Keywords section; Symbol::intern (Rust 1.94.1) [RUSTC-Symbol]; box in §2.

Find where LLVM does it. Open clang/lib/Basic/IdentifierTable.cpp at llvmorg-23.1.2. Question: which function decides whether a keyword such as constexpr is a keyword in the current language mode, and what does it return for "not a keyword here"? (Quiz llvm-keyword-status.)

Perfect hashing (gperf)¶

GCC keeps gperf inputs in its C++ front end, gcc/cp/cfns.gperf and gcc/cp/std-name-hint.gperf (GCC 15.1), and checks the generated files into the tree [GPERF-Manual]; box in §2.

Tries and keywords in the DFA¶

re2c / flex: keywords as rules before the identifier rule; box in §2 (re2c 3.1) [RE2C-Manual].

Switch on length¶

LLVM llvm/lib/TableGen/StringMatcher.cpp — StringMatcher::Emit, EmitStringMatcherForChar (LLVM 23.1.2) [LLVM-StringMatcher]; box in §2.
Pebble reference lexer, keywordKind in solutions/pebble/lib/Lex/src/Lexer.cpp.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Hash table with pre-interned keywords	exact; any set, changeable at run time (language modes)	one hash per identifier, shared with interning	–	small (the table exists anyway)	Clang, rustc, most compilers
Perfect hashing (gperf)	exact for a fixed set	one hash + one `strcmp`	–	a build step	GCC, interpreters, protocol parsers
Tries and keywords in the DFA	exact	free inside a generated lexer; \(O(\ell)\) standalone	–	none with a generator	flex, re2c, ml-ulex lexers
Switch on length	exact for a fixed set	very fast for small sets	–	trivial	Pebble, TableGen-generated matchers

Choose the interning table when the compiler interns identifiers (almost always). Choose gperf when you need a standalone, fixed, fast recognizer without interning. Let the DFA do it when the lexer is generated. Choose switch on length when the set is small and you want no tables and no build step.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Hash table with pre-interned keywords	`llvm-keyword-status`, `keyword-choice`	justification below	`keyword-hash-table`	E1 (any method)
Perfect hashing (gperf)	`gperf-hash-value`, `keyword-choice`	justification below	`perfect-hashing`	—
Tries and keywords in the DFA	`trie-nodes`, `keyword-choice`	`./course drill maximal-munch --difficulty easy` (keyword rules vs identifier rules)	`keyword-trie`	—
Switch on length	`switch-length-compares`, `keyword-choice`	justification below	`switch-on-length`	E1

Keyword recognition has no drill of its own: each technique is a single lookup whose practice is a one-line computation, which the quiz asks for concrete inputs (gperf-hash-value computes a hash, trie-nodes counts nodes, switch-length-compares counts comparisons).

Pitfall

A perfect hash is perfect only on the keyword set. Without the final string comparison every identifier that collides with a keyword's slot would be lexed as that keyword (fnord as float in §3).

References¶

See the chapter references.

Lesson 1.8 — Recognizing keywords: hash tables, perfect hashing, tries, switch on length¶

1. Problem and motivation¶

Hash table with pre-interned keywords¶

Perfect hashing (gperf)¶

Tries and keywords in the DFA¶

Switch on length¶

2. Definitions and algorithms¶

Hash table with pre-interned keywords¶

Perfect hashing (gperf)¶

Tries and keywords in the DFA¶

Switch on length¶

3. Worked example¶

Hash table with pre-interned keywords¶

Perfect hashing (gperf)¶

Tries and keywords in the DFA¶

Switch on length¶

4. Invariants and correctness¶

Hash table with pre-interned keywords¶

Perfect hashing (gperf)¶

Tries and keywords in the DFA¶

Switch on length¶

5. Complexity¶

6. Variants and refinements¶

Hash table with pre-interned keywords¶

Perfect hashing (gperf)¶

Tries and keywords in the DFA¶

Switch on length¶

7. In real compilers¶

Hash table with pre-interned keywords¶

Perfect hashing (gperf)¶

Tries and keywords in the DFA¶

Switch on length¶

8. Comparison¶

9. Assessment¶

References¶