Lesson 1.9 — Unicode in the lexer: UTF-8, identifier syntax, normalization¶

Techniques: strict UTF-8 decoding with error recovery, identifier syntax by UAX #31 (XID_Start / XID_Continue), normalization (NFC, NFKC) and confusable detection · Pebble implements: strict UTF-8 decoding everywhere, UTF-8 in strings and comments, and UAX #31 classes to diagnose non-ASCII identifiers (E0109, E0110; E5) · Prerequisites: Lesson 1.5 · Time: 3–4 hours

Pebble source is UTF-8. Its identifiers are ASCII (spec §3), but a lexer still meets Unicode everywhere: in strings ("héllo 🎉"), in comments, in escapes (\u{1F600}), and in mistakes (let café = 1;, a pasted ∑, a stray byte 0xFF). Swift, Rust, C++23, Python, Java and JavaScript go further and allow Unicode identifiers. This lesson covers the three layers: decoding bytes into code points safely, deciding which code points may form identifiers, and deciding when two different byte sequences are "the same identifier".

1. Problem and motivation¶

Input: bytes. Output: tokens whose spellings are valid UTF-8, identifiers that follow a stable, standard definition, and diagnostics that name the offending character, not a byte. Security matters too: malformed UTF-8 and look-alike characters have been used to hide code from reviewers ("Trojan Source").

UTF-8 decoding¶

UTF-8 (Thompson and Pike, 1992; standardized in RFC 3629 [RFC3629]) encodes each Unicode scalar value in 1–4 bytes, is ASCII-compatible and self-synchronizing. A lexer must decode it strictly: reject overlong encodings (C0 AF for /), surrogates and values above U+10FFFF, because lenient decoders let an attacker smuggle a / or a quote past a byte-level check. The Unicode standard also defines how to recover: replace each maximal ill-formed subpart by one U+FFFD [Unicode16 §3.9].

Identifier syntax (UAX #31)¶

Which characters may appear in identifiers? Early languages said "ASCII letters". Unicode Standard Annex #31 [UAX31] defines the Default Identifier Syntax: a start character from XID_Start, then characters from XID_Continue. These properties are stable (a character never leaves them) and closed under NFKC normalization. C++23 (P1949 [P1949]), Rust, Python 3 and Swift use UAX #31 profiles; C99/C11 used fixed lists of allowed ranges, which Clang still keeps for C.

Normalization and confusables¶

é can be one code point (U+00E9) or two (e + U+0301 COMBINING ACUTE ACCENT). Without normalization, two identifiers that look identical are different names. UAX #15 [UAX15] defines canonical composition (NFC) and compatibility composition (NFKC); Rust compares identifiers in NFC, Python in NFKC. Even normalized, Latin a and Cyrillic а differ: Unicode's security mechanisms (UTS #39) define confusable skeletons, and rustc warns about mixed-script confusables.

2. Definitions and algorithms¶

Definition 1.9.1 (Unicode scalar values)

A code point is an integer in $[0, \mathrm{10FFFF}_{16}]$. The surrogates are $[\mathrm{D800}_{16}, \mathrm{DFFF}_{16}]$. A Unicode scalar value is a code point that is not a surrogate. Text is a sequence of scalar values.

Definition 1.9.2 (UTF-8 encoding)

$\mathrm{enc}(c)$ for a scalar value $c$ with binary digits $x$:

range of $c$	bytes
$0 \dots 7\mathrm{F}$	`0xxxxxxx`
$80 \dots 7\mathrm{FF}$	`110xxxxx 10xxxxxx`
$800 \dots \mathrm{FFFF}$ (no surrogates)	`1110xxxx 10xxxxxx 10xxxxxx`
$10000 \dots 10\mathrm{FFFF}$	`11110xxx 10xxxxxx 10xxxxxx 10xxxxxx`

filling the x bits with $c$'s binary digits, most significant first. A byte 10xxxxxx is a continuation byte; the others are lead bytes.

Definition 1.9.3 (Well-formed UTF-8)

A byte sequence is well-formed iff it is a concatenation of $\mathrm{enc}(c_i)$ for scalar values $c_i$. Equivalently (Unicode Table 3-7 [Unicode16 §3.9]), every character's bytes fall in one of these rows:

first byte	second	third	fourth
00–7F
C2–DF	80–BF
E0	A0–BF	80–BF
E1–EC, EE–EF	80–BF	80–BF
ED	80–9F	80–BF
F0	90–BF	80–BF	80–BF
F1–F3	80–BF	80–BF	80–BF
F4	80–8F	80–BF	80–BF

C0, C1 and F5–FF never occur. The narrowed second-byte ranges exclude overlong forms (E0, F0), surrogates (ED) and values above U+10FFFF (F4).

Definition 1.9.4 (Maximal subpart and replacement)

At a position where the bytes are not a well-formed character, the maximal subpart is the longest prefix that is a prefix of some well-formed sequence (at least one byte). The U+FFFD substitution of maximal subparts replaces each maximal subpart by one U+FFFD and continues after it [Unicode16 §3.9].

Definition 1.9.5 (UAX #31 default identifiers)

$\mathrm{XID\_Start}$ and $\mathrm{XID\_Continue}$ are derived Unicode properties: roughly, letters (L*) and letter numbers (Nl) for Start; Start plus combining marks (Mn, Mc), decimal digits (Nd) and connector punctuation (Pc) for Continue, adjusted so that both are closed under NFKC [UAX31]. A default identifier is $s\,c^{*}$ with $s \in \mathrm{XID\_Start}$ and each $c \in \mathrm{XID\_Continue}$. A profile adds or removes characters (C++, Rust and Python add _ to Start).

Definition 1.9.6 (Canonical equivalence, NFC, NFKC)

Two strings are canonically equivalent if they represent the same abstract characters (e + U+0301 ≡ U+00E9); compatibility equivalence also identifies formatting variants (U+FB01 ﬁ ≡ fi, U+2115 ℕ ≡ N). NFC and NFKC are the fully composed canonical forms: $s \equiv t \iff \mathrm{NFC}(s) = \mathrm{NFC}(t)$, and likewise for compatibility with NFKC [UAX15].

Definition 1.9.7 (Confusable skeleton)

UTS #39 maps each string to a skeleton by replacing every character with a prototype of its confusability class (Cyrillic а U+0430 ↦ Latin a) and normalizing with NFD. Two identifiers are confusable if their skeletons are equal but they differ.

UTF-8 decoding¶

Algorithm 1.9.8 (Strict UTF-8 decoder with maximal-subpart recovery)

Input: bytes $b_i, \dots, b_{\mathit{end}-1}$ with $i < \mathit{end}$.
Output: (scalar value, length) for a well-formed character at $i$, or (invalid, $k$) where $k \in \{1, 2, 3\}$ is the length of the maximal subpart at $i$ (Definition 1.9.4).
Precondition: none (any bytes).
Postcondition: valid iff the bytes at $i$ start with a row of Definition 1.9.3; the returned value is the one $\mathrm{enc}$ maps to those bytes (Proposition 1.9.11). If invalid, $b_i \cdots b_{i+k-1}$ is the maximal subpart.
Invariant: at the top of iteration $j$, $b_i \cdots b_{i+j-1}$ is a prefix of some row of Table 3-7, and cp holds the payload bits read so far.

function Decode(b, i, end):
    b0 ← b[i]
    if b0 < 0x80: return (b0, 1)
    if 0xC2 ≤ b0 ≤ 0xDF: n ← 2; cp ← b0 & 0x1F; lo, hi ← 0x80, 0xBF
    else if 0xE0 ≤ b0 ≤ 0xEF: n ← 3; cp ← b0 & 0x0F
                              lo ← 0xA0 if b0 = 0xE0 else 0x80
                              hi ← 0x9F if b0 = 0xED else 0xBF
    else if 0xF0 ≤ b0 ≤ 0xF4: n ← 4; cp ← b0 & 0x07
                              lo ← 0x90 if b0 = 0xF0 else 0x80
                              hi ← 0x8F if b0 = 0xF4 else 0xBF
    else: return (invalid, 1)                      # 80–BF, C0, C1, F5–FF
    for j from 1 to n − 1:
        if i + j = end: return (invalid, j)        # truncated
        (l, h) ← (lo, hi) if j = 1 else (0x80, 0xBF)
        if not l ≤ b[i + j] ≤ h: return (invalid, j)
        cp ← (cp << 6) | (b[i + j] & 0x3F)
    return (cp, n)

Pebble's lexer calls Decode only when it sees a byte ≥ 0x80: in a string (keep the bytes, or report E0109 and skip the $k$ bytes of the maximal subpart), at a token start (E0101/E0110/E0109; an invalid subpart becomes one unknown token), or after an identifier. By the invariant, when iteration $j$ fails, $b_i \cdots b_{i+j-1}$ extends to a well-formed sequence but $b_i \cdots b_{i+j}$ does not, so $j$ is exactly the maximal subpart length: the decoder that validates also does the recovery. Comments are skipped without decoding (spec §3.1 allows any bytes there).

Invalid UTF-8: Python's decoder and Clang's warning

Reproduce (Python 3.11.15, clang 23.1.2; any OS):

printf 'caf\xc3\xa9 \xed\xa0\x80 \xc0\xaf \xf0\x9f\x8e\x89' | python3 -c "
import sys
data = sys.stdin.buffer.read()
print(data.hex(' '))
print(data.decode('utf-8', 'replace'))
try:
    data.decode('utf-8')
except UnicodeDecodeError as e:
    print(e)
"
printf 'int x; // caf\xc3\xa9 ok, bad \xff\n' > bad8.c
clang-23 -fsyntax-only -Winvalid-utf8 bad8.c

Output (complete):

63 61 66 c3 a9 20 ed a0 80 20 c0 af 20 f0 9f 8e 89
café ��� �� 🎉
'utf-8' codec can't decode byte 0xed in position 6: invalid continuation byte
bad8.c:1:25: warning: invalid UTF-8 in comment [-Winvalid-utf8]
    1 | int x; // café ok, bad <FF>
      |                        ^
1 warning generated.

What to notice: ED A0 80 would encode the surrogate U+D800; ED's second byte must be 80–9F (Definition 1.9.3), so ED alone is the maximal subpart, and the stray A0 and 80 are two more: three U+FFFD. C0 AF is the overlong /: C0 can never appear, so two replacements. Python follows Definition 1.9.4 exactly, and so does Pebble's lexer, which reports one E0109 per such subpart (test PebbleLexer.InvalidUTF8). Clang warns but keeps going; Pebble accepts any bytes in comments without a warning.

Identifier syntax (UAX #31)¶

Algorithm 1.9.9 (Identifier continuation with XID tables)

Input: position after an identifier's first character; sorted disjoint range tables for XID_Start and XID_Continue (non-ASCII part).
Output: the end of the identifier.
Precondition: the tables are sorted by lower bound (generated from the Unicode Character Database).
Postcondition: the identifier is the longest run of ASCII identifier characters and XID_Continue scalars (Proposition 1.9.12).
Invariant: every scalar consumed so far is in XID_Continue (or ASCII [A-Za-z0-9_]).

function InRanges(T, cp):                        # binary search: first range with hi ≥ cp
    lo ← 0; hi ← |T|
    while lo < hi:
        mid ← (lo + hi) / 2
        if T[mid].hi < cp: lo ← mid + 1 else hi ← mid
    return lo < |T| and T[lo].lo ≤ cp

function IdentTail(b, i):
    loop:
        if b[i] is ASCII: if b[i] ∈ [A-Za-z0-9_]: i ← i + 1; continue else return i
        (cp, n) ← Decode(b, i, end)
        if invalid or not InRanges(XIDContinue, cp): return i
        i ← i + n                                 # Pebble: report E0110 once, keep going (recovery)

Pebble identifiers are ASCII (spec §3.2), so the reference lexer uses these tables for diagnostics and recovery: café becomes one identifier token with one E0110 at é, instead of caf, an invalid character and a cascade of parser errors. The tables (653 Start ranges, 759 Continue ranges, Unicode 14.0) are generated by solutions/pebble/lib/Lex/tools/gen_xid_tables.py.

Clang (C++23) accepts UAX #31 identifiers and rejects a math symbol

Reproduce (clang 23.1.2; any OS):

printf 'int caf\xc3\xa9 = 1;\nint \xe2\x88\x91 = 2;\nint x\xcc\x81 = 3;\n' > uni.cpp
clang++-23 -std=c++23 -fsyntax-only uni.cpp

Output (complete):

uni.cpp:2:5: error: unexpected character <U+2211>
    2 | int ∑ = 2;
      |     ^
uni.cpp:2:9: error: expected unqualified-id
    2 | int ∑ = 2;
      |       ^
2 errors generated.

What to notice: café (é is XID_Start/Continue) and x́ (x + U+0301, a combining mark: XID_Continue but not XID_Start) are accepted silently; ∑ (U+2211, category Sm) is in neither class, so Clang reports an unexpected character, and the parser then cascades (second error). Pebble avoids the cascade for identifier-like characters by keeping them in the identifier token (E0110) and turns non-identifier characters into a single unknown token (E0101).

Normalization and confusables¶

Algorithm 1.9.10 (Normalized identifier comparison and confusable check)

Input: identifier spellings as scalar sequences; normalization data (decompositions, combining classes, compositions); a confusables table.
Output: the interned key of each identifier; warnings for confusable pairs.
Precondition: each identifier satisfies Definition 1.9.5.
Postcondition: canonically (or compatibly, for NFKC) equivalent spellings intern to the same name (Proposition 1.9.13).
Invariant: the interning table's keys are in normal form.

function NormalizeNFC(s):
    if QuickCheckNFC(s) = YES: return s                  # all ASCII, or no candidates: the common case
    d ← recursively decompose every character (canonical decompositions)
    stable-sort each run of non-starters by canonical combining class
    compose: for each starter, combine following characters with it when a primary composite exists
    return the result

function InternIdentifier(s):
    key ← NormalizeNFC(s)          # Rust; Python uses NFKC
    return Intern(key)             # Lesson 1.8

function CheckConfusables(identifiers):
    for each pair with Skeleton(a) = Skeleton(b) and a ≠ b: warn        # UTS #39
    for each identifier mixing scripts whose characters all have confusable prototypes: warn

Rust normalizes identifiers to NFC and warns about confusables; Python uses NFKC

Reproduce (rustc 1.94.1, Python 3.11.15; any OS):

printf 'fn main() {\n    let caf\xc3\xa9 = 1;\n    println!("{}", cafe\xcc\x81);\n    let \xd0\xb0 = 2;\n    println!("{}", \xd0\xb0);\n}\n' > nfc.rs
rustc --edition 2021 -o nfc nfc.rs && ./nfc
printf '\xef\xac\x81 = 42\nprint(fi)\nimport unicodedata\nprint(unicodedata.normalize("NFKC", "\\ufb01"), unicodedata.normalize("NFC", "e\\u0301") == "\\u00e9")\n' > nfkc.py
python3 nfkc.py

Output (complete):

warning: the usage of Script Group `Cyrillic` in this crate consists solely of mixed script confusables
 --> nfc.rs:4:9
  |
4 |     let а = 2;
  |         ^
  |
  = note: the usage includes 'а' (U+0430)
  = note: please recheck to make sure their usages are indeed what you want
  = note: `#[warn(mixed_script_confusables)]` on by default

warning: 1 warning emitted

1
2
42
fi True

What to notice: the Rust file declares café with the precomposed é (U+00E9) and uses it with e + U+0301; it compiles and prints 1, because rustc interns identifiers in NFC (Algorithm 1.9.10). The Cyrillic а is a valid identifier but draws the mixed_script_confusables lint (Definition 1.9.7). Python assigns to ﬁ (U+FB01, one ligature character) and reads fi (two letters): under NFKC they are the same name, so it prints 42.

3. Worked example¶

UTF-8 decoding¶

Encoding (Definition 1.9.2), payload bits in brackets:

character	scalar	binary	bytes
`A`	U+0041	1000001	`0[1000001]` = 41
`é`	U+00E9	00011 101001	`110[00011] 10[101001]` = C3 A9
`€`	U+20AC	0010 000010 101100	`1110[0010] 10[000010] 10[101100]` = E2 82 AC
`🎉`	U+1F389	000 011111 001110 001001	`11110[000] 10[011111] 10[001110] 10[001001]` = F0 9F 8E 89

Decoding 63 C3 A9 ED A0 80 C0 AF F0 9F 8E 89 with Algorithm 1.9.8:

offset	bytes examined	row / reason	result	next offset
0	63	ASCII	U+0063 `c`	1
1	C3 A9	C2–DF, 80–BF	U+00E9 `é`	3
3	ED A0	ED needs 80–9F; A0 is out	invalid (E0109 0xED)	4
4	A0	continuation byte as lead	invalid	5
5	80	continuation byte as lead	invalid	6
6	C0	never valid	invalid	7
7	AF	continuation byte as lead	invalid	8
8	F0 9F 8E 89	F0, 90–BF, 80–BF, 80–BF	U+1F389 `🎉`	12

Five E0109 diagnostics, matching Python's five U+FFFD in the real-world box. Every invalid subpart here is one byte long; a truncated sequence is the case with a longer one: in E2 82 3B (a € missing its last byte, then ;), the loop fails at $j = 2$ on 3B, so E2 82 is one maximal subpart, one E0109 and one unknown token, and lexing resumes at ; (the corpus golden tests/ch01/Inputs/err-utf8.tokens has exactly this).

Try it

./course drill utf8 --seed 2 --difficulty hard asks for encodings, a decoding and the offsets of the maximal subparts of ill-formed bytes (one error each).

Identifier syntax (UAX #31)¶

character	category	XID_Start	XID_Continue	Pebble result at token start
`é` U+00E9	Ll	yes	yes	identifier + E0110
`π` U+03C0	Ll	yes	yes	identifier + E0110
U+0301 (combining acute)	Mn	no	yes	E0101 (cannot start); after a letter: continues the identifier + E0110
`٣` U+0663 (Arabic-Indic three)	Nd	no	yes	E0101 at start; continues an identifier
`ℕ` U+2115	Lu	yes	yes	identifier + E0110 (NFKC: `N`)
`∑` U+2211	Sm	no	no	`unknown` + E0101
`€` U+20AC	Sc	no	no	`unknown` + E0101
U+200D (zero-width joiner)	Cf	no	no	`unknown` + E0101

(Properties from Python 3.11's str.isidentifier, Unicode 14.0, which the generator script uses.) Compare the corpus golden tests/ch01/Inputs/err-chars.tokens: café and π are identifiers with E0110, ∑ is an unknown token with E0101.

Normalization and confusables¶

café in NFC is 63 61 66 C3 A9; in NFD it is 63 61 66 65 CC 81 (e + U+0301). NFC composes 65 CC 81 back to C3 A9, so both spellings intern to the same key. NFKC additionally maps ﬁ (U+FB01) to fi and ℕ to N. Skeletons: а (U+0430) and a (U+0061) have the same skeleton a, so an identifier made only of Cyrillic look-alikes in a Latin-script crate is flagged.

4. Invariants and correctness¶

UTF-8 decoding¶

Proposition 1.9.11 (UTF-8 is uniquely decodable, and the decoder is exact)

(i) $\mathrm{enc}$ is injective and its image is prefix-free: no encoding of one character is a proper prefix of another's. (ii) A lead byte determines the length; a continuation byte is never a lead byte (self-synchronization). (iii) Algorithm 1.9.8 returns $(c, n)$ iff the bytes at $i$ are exactly $\mathrm{enc}(c)$ with $\lvert \mathrm{enc}(c) \rvert = n$, and "invalid" otherwise.

Proof

(i)(ii) The lead byte's high bits (0, 110, 1110, 11110) fix $n$, and continuation bytes start with 10, distinct from every lead pattern; so the first byte determines $n$ and no encoding is a prefix of a different one. Within one length the payload bits determine $c$, so $\mathrm{enc}$ is injective. (iii) The decoder accepts exactly the rows of Table 3-7 (Definition 1.9.3): the lead-byte ranges and the narrowed second-byte ranges are copied from it. Each row consists exactly of the encodings of one range of scalar values: E0 A0–BF covers U+0800–U+0FFF (E0 80–9F would be overlong, i.e. a value below U+0800 in three bytes), ED 80–9F covers U+D000–U+D7FF (A0–BF would be surrogates), F0 90–BF starts at U+10000, F4 80–8F ends at U+10FFFF. By the invariant, cp accumulates the payload bits in order, so the returned value is $c$. $\square$

Identifier syntax (UAX #31)¶

Proposition 1.9.12 (Range lookup is exact; identifier tails are maximal)

InRanges(T, cp) returns true iff $cp$ lies in one of the (sorted, disjoint) ranges of $T$. IdentTail returns the end of the longest run of identifier characters starting at $i$.

Proof

Sorted disjoint ranges have increasing upper bounds, so the predicate "$T[k].hi \ge cp$" is monotone in $k$, and the binary search returns the first index $k$ with $T[k].hi \ge cp$ (or $\lvert T \rvert$). Ranges before $k$ end below $cp$, so they do not contain it. Ranges after $k$ start above $T[k].hi \ge cp$ (disjointness and sorting), so they do not contain it either. Hence $cp$ lies in some range iff it lies in $T[k]$, iff $T[k].lo \le cp$, which is what InRanges tests. IdentTail consumes characters while the invariant can be maintained and stops at the first character that is not an identifier character, so the run is maximal (maximal munch for identifiers, Definition 1.6.2). $\square$

Normalization and confusables¶

Proposition 1.9.13 (Normalized interning identifies equivalent spellings)

With keys in NFC, two identifier spellings intern to the same object iff they are canonically equivalent; with NFKC, iff they are compatibility equivalent. XID_Start/XID_Continue identifiers stay identifiers after NFKC normalization.

Proof sketch (full statement: [UAX15, §1.2]; closure: [UAX31, §5.1])

UAX #15 defines NFC so that $s \equiv t \iff \mathrm{NFC}(s) = \mathrm{NFC}(t)$ (the normal form is unique per equivalence class: decomposition and canonical ordering produce a unique representative, and composition is a function of it); likewise NFKC for compatibility equivalence. Interning by the normal form therefore merges exactly the equivalence classes (Proposition 1.8.9 on the normalized keys). UAX #31 derives XID_Start and XID_Continue from ID_Start/ID_Continue by removing the characters that would make the sets non-closed under NFKC, precisely so that normalizing an identifier yields an identifier.

5. Complexity¶

Variables: $n$ = bytes; $R$ = number of ranges in an XID table ($\approx 700$); $d$ = maximal decomposition length (bounded, $\le 18$ in Unicode).

Technique	Time	Space	Notes
Strict UTF-8 decoding	$O(1)$ per character, $O(n)$ total	none	ASCII fast path: one compare per byte
XID classification	$O(\log R)$ per non-ASCII character	$O(R)$ table	a two-level lookup table makes it $O(1)$
NFC/NFKC normalization	$O(n \cdot d)$ with canonical reordering (a bounded sort per run of marks)	Unicode tables (~tens of KB)	quick check avoids work for most identifiers
Confusable check	$O(n)$ skeletons + hashing	confusables table	per crate/module, not per token

Pathological input. Normalization's canonical reordering sorts runs of combining marks; a long run of marks on one base character (a "Zalgo" identifier) makes the per-character cost grow with the run length. Implementations cap run lengths (UAX #15's stream-safe format limits runs to 30 non-starters).

At scale. Pebble's lexer decodes only bytes ≥ 0x80, so ASCII-only input (the benchmark) never enters the decoder; strings with UTF-8 cost one decode per non-ASCII character.

UTF-8 decoding¶

DFA-based decoders (Höhrmann's table-driven decoder [Hoe10]): the validity rules of Table 3-7 as a 9-state DFA over byte classes, branch-free.
SIMD validation (simdjson's UTF-8 validator [KL21]): validate 32–64 bytes per step with nibble lookups (Lesson 1.5).
Lenient vs strict recovery: reject the file (Rust), replace each maximal subpart by U+FFFD (Python's replace handler; Pebble's recovery, with one E0109 each), or replace each bad byte separately (simpler, but reports more errors than the standard's recommended practice).

Identifier syntax (UAX #31)¶

Fixed allowed-range lists (C99 Annex D, C11 Annex D; Clang's C99AllowedIDCharRanges, C11AllowedIDCharRanges) vs XID properties (C++23, Rust, Swift): the lists are frozen, XID follows Unicode versions.
Profiles: adding _ or $ to Start (C++, JavaScript), restricting to recommended scripts (UTS #39 "identifier restriction levels").

Normalization and confusables¶

Reject non-NFC identifiers (C++23 requires identifiers to be in NFC, a diagnostic otherwise) vs normalize silently (Rust, Python).
Lints instead of errors: rustc's uncommon_codepoints, confusable_idents, mixed_script_confusables; the Trojan-Source bidi-override checks (-Wbidi-chars in GCC, text_direction_codepoint_in_literal in rustc).

7. In real compilers¶

UTF-8 decoding¶

LLVM

llvm/lib/Support/ConvertUTF.cpp — isLegalUTF8Sequence, getNumBytesForUTF8, ConvertUTF8toUTF32 (LLVM 23.1.2) [LLVM-ConvertUTF]; Clang's lexer calls them when it meets a byte ≥ 0x80 (Lexer::tryConsumeIdentifierUTF8Char).

Pebble solutions/pebble/lib/Lex/src/Unicode.cpp — unicode::decodeUTF8.
CPython Objects/unicodeobject.c, the UTF-8 decoder with the replace error handler; box in §2.

Find where LLVM does it. Open llvm/lib/Support/ConvertUTF.cpp at llvmorg-23.1.2 and find isLegalUTF8Sequence. Question: what does getNumBytesForUTF8 return for the byte 0xF4, and does it by itself reject 0xF5? (Quiz llvm-utf8-length.)

Identifier syntax (UAX #31)¶

Clang clang/lib/Lex/UnicodeCharSets.h — XIDStartRanges, XIDContinueRanges, C11AllowedIDCharRanges, C99AllowedIDCharRanges; isAllowedIDChar in Lexer.cpp picks the table by language (LLVM 23.1.2) [CLANG-Unicode]; box in §2.
rustc compiler/rustc_lexer/src/lib.rs — is_id_start, is_id_continue (via the unicode_ident crate's tables; Rust 1.94.1) [RUSTC-Lexer].

Normalization and confusables¶

rustc normalizes identifiers to NFC when interning (nfc_normalize in compiler/rustc_parse), and compiler/rustc_lint/src/non_ascii_idents.rs implements the confusable lints [RUSTC-Lexer]; box in §2.
CPython: identifiers are NFKC-normalized by the parser (PEP 3131) [PY-Lexical]; box in §2.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
UTF-8 decoding (strict)	rejects every ill-formed sequence	$O(1)$ per character; ASCII fast path	can name the offending byte and recover per maximal subpart	small (Table 3-7)	every lexer that reads UTF-8
Identifier syntax (UAX #31)	standard, stable identifier sets	$O(\log R)$ per non-ASCII char	"character X not allowed in an identifier"	table generation from the UCD	C++23, Rust, Swift, Python, Pebble diagnostics
Normalization and confusables	identifies equivalent spellings; flags look-alikes	normalization only when needed (quick check)	lints with code points (rustc)	large tables; use a library	Rust (NFC), Python (NFKC), rustc lints

Always decode strictly and recover by maximal subparts. Use XID (with a documented profile) if identifiers may be non-ASCII; keep the tables for diagnostics even if they may not (Pebble). Normalize at interning time if you allow Unicode identifiers, choosing NFC (preserve distinctions like ℕ vs N) or NFKC (merge them), and add confusable lints.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
UTF-8 decoding	`utf8-invalid-count`, `llvm-utf8-length`	`./course drill utf8`	`utf8`	E5
Identifier syntax (UAX #31)	`xid-classes`, `unicode-policy`	`./course drill utf8` (encode identifier characters) + the corpus goldens	`xid-identifiers`	E5
Normalization and confusables	`nfc-nfkc`, `unicode-policy`	justification below	`unicode-normalization`	—

Normalization has no drill: computing NFC by hand means consulting the Unicode tables, which teaches the tables rather than the idea; the quiz asks the decisions (nfc-nfkc: which pairs are equal under NFC vs NFKC).

Pitfall

"Decode UTF-8 with a mask and a shift" without the Table 3-7 range checks accepts overlong forms: C0 AF decodes to /. A lexer that validates bytes for / or " before decoding and a later stage that decodes leniently can disagree about where a comment or string ends: the classic smuggling bug.

References¶

See the chapter references.

range of \(c\)	bytes
\(0 \dots 7\mathrm{F}\)	`0xxxxxxx`
\(80 \dots 7\mathrm{FF}\)	`110xxxxx 10xxxxxx`
\(800 \dots \mathrm{FFFF}\) (no surrogates)	`1110xxxx 10xxxxxx 10xxxxxx`
\(10000 \dots 10\mathrm{FFFF}\)	`11110xxx 10xxxxxx 10xxxxxx 10xxxxxx`

Technique	Time	Space	Notes
Strict UTF-8 decoding	\(O(1)\) per character, \(O(n)\) total	none	ASCII fast path: one compare per byte
XID classification	\(O(\log R)\) per non-ASCII character	\(O(R)\) table	a two-level lookup table makes it \(O(1)\)
NFC/NFKC normalization	\(O(n \cdot d)\) with canonical reordering (a bounded sort per run of marks)	Unicode tables (~tens of KB)	quick check avoids work for most identifiers
Confusable check	\(O(n)\) skeletons + hashing	confusables table	per crate/module, not per token

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
UTF-8 decoding (strict)	rejects every ill-formed sequence	\(O(1)\) per character; ASCII fast path	can name the offending byte and recover per maximal subpart	small (Table 3-7)	every lexer that reads UTF-8
Identifier syntax (UAX #31)	standard, stable identifier sets	\(O(\log R)\) per non-ASCII char	"character X not allowed in an identifier"	table generation from the UCD	C++23, Rust, Swift, Python, Pebble diagnostics
Normalization and confusables	identifies equivalent spellings; flags look-alikes	normalization only when needed (quick check)	lints with code points (rustc)	large tables; use a library	Rust (NFC), Python (NFKC), rustc lints

Lesson 1.9 — Unicode in the lexer: UTF-8, identifier syntax, normalization¶

1. Problem and motivation¶

UTF-8 decoding¶

Identifier syntax (UAX #31)¶

Normalization and confusables¶

2. Definitions and algorithms¶

UTF-8 decoding¶

Identifier syntax (UAX #31)¶

Normalization and confusables¶

3. Worked example¶

UTF-8 decoding¶

Identifier syntax (UAX #31)¶

Normalization and confusables¶

4. Invariants and correctness¶

UTF-8 decoding¶

Identifier syntax (UAX #31)¶

Normalization and confusables¶

5. Complexity¶

6. Variants and refinements¶

UTF-8 decoding¶

Identifier syntax (UAX #31)¶

Normalization and confusables¶

7. In real compilers¶

UTF-8 decoding¶

Identifier syntax (UAX #31)¶

Normalization and confusables¶

8. Comparison¶

9. Assessment¶

References¶