Lesson 1.7 — Context-sensitive lexing: modes, feedback and the cases a DFA cannot handle

Techniques: lexer modes and start conditions (string interpolation in Pebble, Swift, Kotlin; flex %x), JavaScript's / as regex vs division, C++ >> in templates, Python's INDENT/DEDENT, raw strings, the C typedef "lexer hack" · Pebble implements: the interpolation mode stack and nested comments (E4) · Prerequisites: Lessons 1.1, 1.5, 1.6 · Time: 4–5 hours

So far a lexer has been a DFA plus maximal munch: the next token depends only on the bytes ahead. Real languages break this in six classic ways. Inside a Pebble string "a\(x)b", the ) after x is not a parenthesis but the end of an interpolation; in JavaScript /b/g is a regex after ( and two divisions after a; in C++ >> closes two templates in V<V<int>> but is a shift in 16 >> 2; in Python the amount of leading space is a token; in C++ R"x(a)" b)x" is one string although it contains "; and in C, T * x; is a declaration if T names a type and a multiplication otherwise. Each needs state that a DFA does not have: a mode, a stack, a counter, or information from the parser.

1. Problem and motivation

The token grammar of these languages is not regular, or the correct token depends on the syntactic context. The lexer must still run in one left-to-right pass, in linear time, producing tokens the parser can use. The techniques differ in where the extra state lives: in the lexer (modes, stacks, counters), in a parser–lexer protocol (the parser tells the lexer what it expects), or in the parser (split or reinterpret tokens after the fact).

Lexer modes and start conditions

Lex and flex offer start conditions: named sets of rules, one active at a time, switched by actions (BEGIN(STR)), with a stack (yy_push_state) for nesting [FLEX-Manual]. String interpolation needs the stack: in Pebble (spec §3.5), Swift, Kotlin, C# and JavaScript template literals, an interpolated expression can contain strings that contain interpolations. Pebble's lexer keeps one counter of unmatched ( per open \(: the InterpolationDepth member of pebble::Lexer.

JavaScript regex vs division

ECMAScript's lexical grammar has two goal symbols, InputElementDiv and InputElementRegExp: a / starts a regular-expression literal only where the syntactic grammar allows an expression to start [ECMA262 §12]. The lexer cannot decide alone; V8's parser asks its scanner to rescan a / as a regex when it expects a primary expression.

C++ >> in templates

Maximal munch makes >> one token, so C++98 required V<V<int> > with a space. C++11 adopted Vandevoorde's proposal N1757: inside a template argument list, the parser treats the first > of >> as the closing bracket and puts the second back [N1757]. The lexer is unchanged; the fix is in the parser.

Python INDENT/DEDENT

Python's block structure is indentation. Its tokenizer keeps a stack of indentation widths and emits INDENT when a line starts deeper, and one DEDENT per level when it starts shallower, so the grammar can treat blocks like braces [PY-Lexical]. A counter-and-stack in the lexer turns a two-dimensional layout into a context-free token stream.

Raw strings

A raw string turns off escapes, so it needs a delimiter that the content cannot contain. C++11 R"delim(…)delim" and Rust r#"…"# let the programmer choose the delimiter; the lexer must remember it and compare it at every candidate end. With an unbounded delimiter (Rust allows up to 255 #, C++ up to 16 characters) the language of raw strings is not regular, or has a very large DFA.

The C typedef lexer hack

In C, T * x; is a declaration if T is a typedef name and an expression otherwise; the grammar is ambiguous without knowing which identifiers are types. The classic fix, the lexer hack, lets the lexer consult the symbol table and return TYPE_NAME instead of IDENTIFIER. Clang moves the lookup into the parser (it annotates identifier tokens with their meaning), but the feedback loop from semantic information to token classification is the same.

2. Definitions and algorithms

Definition 1.7.1 (Moded lexer)

A moded lexer has a finite set of modes \(M\), a scanner \(\mathrm{scan}_m\) (Definition 1.5.1) for each \(m \in M\), and a mode store \(\sigma\): either a single current mode or a stack \(\sigma \in (M \times \mathbb{N})^{*}\) whose top gives the current mode and a counter. Each token kind has an action that updates \(\sigma\) (push, pop, change the top, change the counter). A moded lexer with a stack is a pushdown transducer: it can recognize nested token structure that no DFA can.

Definition 1.7.2 (Pebble interpolation state)

The Pebble lexer's store is a stack \(\sigma = [d_1, \dots, d_h]\) of natural numbers: \(h\) is the number of open interpolations and \(d_h\) the number of ( opened inside the innermost one and not yet closed (spec §3.5). Mode is "code" when outside any string piece; string pieces are scanned by a separate loop. The actions are: \( in a string piece pushes 0; ( in code increments \(d_h\) if \(h > 0\); ) in code with \(h > 0\) decrements \(d_h\) if \(d_h > 0\), and otherwise pops and resumes the string (a string_middle or string_tail follows).

Definition 1.7.3 (Lexical goal)

A lexer with goal symbols \(G\) has a scanner per goal and receives the goal from its client before each token. ECMAScript uses \(G = \{\mathrm{Div}, \mathrm{RegExp}, \mathrm{RegExpOrTemplateTail}, \dots\}\): under \(\mathrm{Div}\) a / is the division punctuator, under \(\mathrm{RegExp}\) it starts a RegularExpressionLiteral [ECMA262 §12].

Definition 1.7.4 (Indentation tokens)

For a line whose first non-blank character is at column \(c\) (after tab expansion) and an indentation stack \(I = [0 = i_0 < i_1 < \cdots < i_h]\): if \(c > i_h\), push \(c\) and emit INDENT; if \(c = i_h\), emit nothing; if \(c < i_h\), pop and emit one DEDENT for every \(i_j > c\), and it is an error unless \(c\) is then equal to the new top. Blank and comment-only lines are ignored; inside brackets, line breaks are not significant. At end of input, emit one DEDENT per stack entry above 0.

Definition 1.7.5 (Delimited raw string)

For a delimiter string \(d\) (C++: at most 16 characters from a restricted set), the C++ raw string with delimiter \(d\) is the language \(R_d = \{\, \texttt{R"}\,d\,\texttt{(}\,x\,\texttt{)}\,d\,\texttt{"} \mid x \text{ does not contain } \texttt{)}d\texttt{"} \,\}\). Rust's raw strings are \(\{\, \texttt{r}\,\#^{n}\,\texttt{"}\,x\,\texttt{"}\,\#^{n} \mid x \text{ does not contain } \texttt{"}\#^{n} \,\}\) for \(0 \le n \le 255\).

Definition 1.7.6 (Typedef-name feedback)

A lexer with semantic feedback classifies an identifier token \(t\) as \(\mathrm{TYPE\_NAME}\) if the symbol table visible at \(t\)'s position declares \(t\) as a typedef (and not shadowed by an ordinary identifier), and as \(\mathrm{IDENTIFIER}\) otherwise. The symbol table is maintained by the parser's actions, so the lexer must not run ahead of the parser by more than the parser's lookahead.

Lexer modes and start conditions

Algorithm 1.7.7 (Pebble interpolation with a mode stack)

• Input: Pebble source; the lexer state \((\mathit{pos}, \sigma)\).
• Output: the next token (kinds of spec §3.5 and TokenKinds.def).
• Precondition: \(\sigma\) is the stack of Definition 1.7.2 (empty at the start of the file).
• Postcondition: string pieces are string_literal, string_head, string_middle, string_tail exactly as in the table of spec §3.5 (Theorem 1.7.13).
• Invariant: \(\lvert\sigma\rvert\) = number of \( whose interpolation has not yet been closed; \(d_h\) = number of ( opened since the innermost \( and not yet closed.

function Lex():
    skip trivia (nested comments with a depth counter)
    if at end: if σ ≠ []: error E0107 (unterminated interpolation); σ ← []
               return eof
    c ← next byte
    if c = '"':                        return StringPiece(start, continuation = false)
    if c = '(':  if σ ≠ []: top(σ) ← top(σ) + 1
                 return l_paren
    if c = ')':  if σ ≠ [] and top(σ) = 0:
                     pop(σ);  return StringPiece(start, continuation = true)
                 if σ ≠ []: top(σ) ← top(σ) − 1
                 return r_paren
    … identifiers, numbers, punctuators as in Lesson 1.5 …

function StringPiece(start, continuation):
    value ← ""
    loop:
        if at end:           error E0102; break
        if next is '"':      consume; break
        if next is newline:  error E0108 (+ note at start); break          # recover at the line end
        if next is "\(":     consume; push(σ, 0)
                             return (string_middle if continuation else string_head, value)
        if next is '\':      value ← value + DecodeEscape()                 # E0104 on bad escapes
        else:                value ← value + next byte(s)
    return (string_tail if continuation else string_literal, value)

The same stack handles strings inside interpolations: a " in code starts a new piece, and its own \( pushes another counter.

flex start conditions with a stack, and the Pebble lexer, on nested interpolation

Reproduce (flex 2.6.4, clang 23.1.2; pebblec built from this repository with -DPEBBLE_USE_SOLUTION=lexer):

cat > interp.l <<'EOF'
%option noyywrap nodefault stack noyy_top_state
%x STR
%{
#include <stdio.h>
static int depth[64], top = -1;          /* unmatched '(' per open interpolation */
#define TOK(k) printf("%-14s '%s'\n", k, yytext)
%}
%%
<INITIAL>\"              { TOK("string_start"); yy_push_state(STR); }
<INITIAL>"("             { if (top >= 0) depth[top]++; TOK("l_paren"); }
<INITIAL>")"             { if (top >= 0 && depth[top] == 0) { top--; yy_pop_state(); TOK("interp_end"); }
                           else { if (top >= 0) depth[top]--; TOK("r_paren"); } }
<INITIAL>[a-z]+          { TOK("identifier"); }
<INITIAL>[ \t\n]+        { }
<INITIAL>.               { TOK("other"); }
<STR>\\\(                { depth[++top] = 0; TOK("interp_begin"); yy_push_state(INITIAL); }
<STR>\"                  { TOK("string_end"); yy_pop_state(); }
<STR>[^"\\]+             { TOK("string_text"); }
<STR>\\.                 { TOK("escape"); }
<STR>\n|.                { TOK("error"); }
%%
int main(void) { yylex(); return 0; }
EOF
flex -o interp.c interp.l && clang-23 -O1 -w interp.c -o interp
printf '"a\\(f(x))b\\("c\\(y)")d"\n' | ./interp
printf 'print("v=\\(f(x) + g("\\(y)"))!");\n' > interp.pbl
pebblec --emit=tokens interp.pbl

Output (complete):

string_start   '"'
string_text    'a'
interp_begin   '\('
identifier     'f'
l_paren        '('
identifier     'x'
r_paren        ')'
interp_end     ')'
string_text    'b'
interp_begin   '\('
string_start   '"'
string_text    'c'
interp_begin   '\('
identifier     'y'
interp_end     ')'
string_end     '"'
interp_end     ')'
string_text    'd'
string_end     '"'
1:1 identifier 'print'
1:6 l_paren '('
1:7 string_head '"v=\\('
1:12 identifier 'f'
1:13 l_paren '('
1:14 identifier 'x'
1:15 r_paren ')'
1:17 plus '+'
1:19 identifier 'g'
1:20 l_paren '('
1:21 string_head '"\\('
1:24 identifier 'y'
1:25 string_tail ')"'
1:27 r_paren ')'
1:28 string_tail ')!"'
1:31 r_paren ')'
1:32 semi ';'
2:1 eof ''

What to notice: flex's start-condition stack (yy_push_state) is the mode half of Definition 1.7.1 and the depth[] array the counter half; the two ) after x are told apart only by the counter (r_paren, then interp_end). Pebble folds the string text into its string_head/string_middle/string_tail tokens but makes the same decisions: in pebblec's output the ) at column 15 closes f(, the one at 25 closes the inner interpolation, 27 closes g(, and 28 closes the outer interpolation.

JavaScript regex vs division

Algorithm 1.7.8 (Parser-directed goal selection)

• Input: a parser that knows, at each point, whether an expression may start; a scanner with goals Div and RegExp.
• Output: tokens in which every / is correctly a division or the start of a regex literal.
• Precondition: the parser requests tokens one at a time (no unbounded lookahead past a /).
• Postcondition: the token stream is the one defined by ECMA-262 (Proposition 1.7.14).
• Invariant: the scanner never lexes past a / before the parser has chosen the goal for it.

function NextToken(parserState):
    goal ← RegExp if parserState expects the start of an expression (a PrimaryExpression) else Div
    return scan_goal(pos)

# V8's variant: the scanner always returns '/' (or '/='); when the parser is at a
# primary expression and sees one, it calls ScanRegExpPattern() to rescan from that '/'.
# The "previous token" heuristic (regex after '(' ',' '=' 'return' …, division after
# identifiers, literals, ')' ']') is used by highlighters and fails on ')' (§3).

The same characters /b/g, three meanings, in Node.js

Reproduce (Node.js v22.22.2; any OS):

cat > slash.js <<'EOF'
const a = 4, b = 2, g = 1, x = 1;
console.log(a /b/ g);                   // after an identifier: division
console.log(String(/b/g));              // after '(': a regular expression literal
if (x) /b/g.test("abc") && console.log("after 'if (x)': a regex");
console.log((x) /b/ g);                 // after ')' of an expression: division
EOF
node slash.js

Output (complete):

2
/b/g
after 'if (x)': a regex
0.5

What to notice: lines 4 and 5 both have ) before /b/g, yet one is a regex and the other two divisions. The previous token cannot decide; only the parser knows that if (x) ends a statement head (an expression may start) while (x) ends a parenthesized expression (an operator must follow). V8 implements Algorithm 1.7.8: the parser calls Scanner::ScanRegExpPattern (src/parsing/scanner.cc) when it wants a regex.

C++ >> in templates

Algorithm 1.7.9 (Splitting >> in the parser)

• Input: a token stream in which the lexer produced greatergreater (and >>=, >=) by maximal munch.
• Output: a parse in which a >> that ends a template argument list is treated as two >.
• Precondition: the parser tracks whether it is inside a template argument list (and not inside parentheses within it).
• Postcondition: V<V<int>> parses as nested templates; x >> 2 outside template arguments stays a shift (Proposition 1.7.15).
• Invariant: a split never changes tokens outside the current template argument list.

function ParseGreaterThanInTemplateList():
    t ← current token
    if t = '>':                  consume; return
    if t ∈ {'>>', '>=', '>>='}:
        replace t, in place, by '>' followed by the rest ('>', '=', '>=')
        consume the first '>'; return          # the rest is the next token
    error "expected '>'"

Clang lexes >> greedily and splits it in the parser (C++11), or rejects it (C++98)

Reproduce (clang 23.1.2; any OS):

cat > shift.cpp <<'EOF'
template <class T> struct V {};
V<V<int>> v;
int x = 16 >> 2;
EOF
clang++-23 -std=c++17 -fsyntax-only -Xclang -dump-tokens shift.cpp 2>&1 | sed -n '/^identifier.*V/,$p' | sed -n '5,12p'
clang++-23 -std=c++98 -fsyntax-only shift.cpp

Output (complete):

identifier       'V'                             Loc=<shift.cpp:2:1>     [StartOfLine]
less             '<'                             Loc=<shift.cpp:2:2>    
identifier       'V'                             Loc=<shift.cpp:2:3>    
less             '<'                             Loc=<shift.cpp:2:4>    
int              'int'                           Loc=<shift.cpp:2:5>    
greatergreater   '>>'                            Loc=<shift.cpp:2:8>    
identifier       'v'                             Loc=<shift.cpp:2:11>    [LeadingSpace]
semi             ';'                             Loc=<shift.cpp:2:12>   
shift.cpp:2:8: error: a space is required between consecutive right angle brackets (use '> >')
    2 | V<V<int>> v;
      |        ^~
      |        > >
1 error generated.

What to notice: in both modes the lexer produces one greatergreater token (maximal munch, Lesson 1.6). In C++17 the parser (Parser::ParseGreaterThanInTemplateList in clang/lib/Parse/ParseTemplate.cpp) splits it; in C++98 the same parser recognizes the situation and emits a fix-it instead of a confusing syntax error.

Python INDENT/DEDENT

Algorithm 1.7.10 (Indentation tokens)

• Input: the lines of a Python file; a bracket-depth counter maintained by the tokenizer.
• Output: the token stream with NEWLINE, INDENT and DEDENT inserted (Definition 1.7.4).
• Precondition: tabs expanded to the next multiple of 8 (and mixed tabs/spaces rejected where ambiguous).
• Postcondition: every INDENT is matched by a later DEDENT; blocks nest like braces (Proposition 1.7.16).
• Invariant: the stack \(I\) is strictly increasing from \(I[0] = 0\).

function Tokenize(lines):
    I ← [0];  brackets ← 0
    for line in lines:
        if brackets = 0 and line is not blank/comment-only:
            c ← column of the first non-blank character
            if c > top(I): push(I, c); emit INDENT
            else:
                while c < top(I): pop(I); emit DEDENT
                if c ≠ top(I): error "unindent does not match any outer indentation level"
        emit the tokens of the line (updating brackets on ( [ { and ) ] })
        if brackets = 0 and the line has tokens: emit NEWLINE
    while top(I) > 0: pop(I); emit DEDENT
    emit ENDMARKER

Python's tokenizer on a two-level block

Reproduce (Python 3.11.15; any OS):

printf 'if x:\n    y = 1\n    if z:\n        w = 2\nv = 3\n' > ind.py
python3 -m tokenize ind.py

Output (complete):

0,0-0,0:            ENCODING       'utf-8'        
1,0-1,2:            NAME           'if'           
1,3-1,4:            NAME           'x'            
1,4-1,5:            OP             ':'            
1,5-1,6:            NEWLINE        '\n'           
2,0-2,4:            INDENT         '    '         
2,4-2,5:            NAME           'y'            
2,6-2,7:            OP             '='            
2,8-2,9:            NUMBER         '1'            
2,9-2,10:           NEWLINE        '\n'           
3,4-3,6:            NAME           'if'           
3,7-3,8:            NAME           'z'            
3,8-3,9:            OP             ':'            
3,9-3,10:           NEWLINE        '\n'           
4,0-4,8:            INDENT         '        '     
4,8-4,9:            NAME           'w'            
4,10-4,11:          OP             '='            
4,12-4,13:          NUMBER         '2'            
4,13-4,14:          NEWLINE        '\n'           
5,0-5,0:            DEDENT         ''             
5,0-5,0:            DEDENT         ''             
5,0-5,1:            NAME           'v'            
5,2-5,3:            OP             '='            
5,4-5,5:            NUMBER         '3'            
5,5-5,6:            NEWLINE        '\n'           
6,0-6,0:            ENDMARKER      ''             

What to notice: the stack goes [0] → [0, 4] (INDENT at line 2) → [0, 4, 8] (INDENT at line 4); line 5 starts at column 0, so both 8 and 4 are popped and two DEDENT tokens, of zero width, precede v. Line 3 is at the current top (4): no token. CPython's compiler does the same in C (tok_get_normal_mode in Parser/lexer/lexer.c).

Raw strings

Algorithm 1.7.11 (Scanning a delimited raw string)

• Input: buffer positioned after R" (C++) or after r and \(n\) # and " (Rust).
• Output: the end of the raw string, or an error.
• Precondition: C++: the delimiter is at most 16 characters and ends with (.
• Postcondition: the returned end is the first occurrence of the closing sequence ()d" or "#^n) (Proposition 1.7.17).
• Invariant: no complete closing sequence occurs in the bytes consumed so far.

function RawStringCpp(p):
    d ← bytes up to the first '(' (error if longer than 16 or containing space, ')', '\', control)
    p ← after '('
    loop:
        if at end: error "unterminated raw string"
        if bytes at p are ')' d '"': return p + |d| + 2
        p ← p + 1

function RawStringRust(p, n):                   # n = number of '#' after 'r'
    loop:
        if at end: error
        if bytes at p are '"' followed by n '#': return p + n + 1
        p ← p + 1

A C++ raw string with a close-paren and quote inside is one token

Reproduce (clang 23.1.2; any OS):

printf 'const char *p = R"x(a)" b)x";\n' > raw.cpp
clang++-23 -std=c++17 -fsyntax-only -Xclang -dump-tokens raw.cpp 2>&1

Output (complete):

const            'const'                         Loc=<raw.cpp:1:1>     [StartOfLine]
char             'char'                          Loc=<raw.cpp:1:7>     [LeadingSpace]
star             '*'                             Loc=<raw.cpp:1:12>    [LeadingSpace]
identifier       'p'                             Loc=<raw.cpp:1:13>   
equal            '='                             Loc=<raw.cpp:1:15>    [LeadingSpace]
string_literal   'R\"x(a)\" b)x\"'               Loc=<raw.cpp:1:17>    [LeadingSpace]
semi             ';'                             Loc=<raw.cpp:1:29>   
eof              ''                              Loc=<raw.cpp:1:30>   

What to notice: the content a)" b contains )", which would end a raw string with an empty delimiter but not this one: the lexer remembered x and stopped only at )x" (Algorithm 1.7.11, Lexer::LexRawStringLiteral in clang/lib/Lex/Lexer.cpp). The rustc lexer's output for r#"a "quoted" b"# is in Lesson 1.10 (RawStr { n_hashes: Some(1) }).

The C typedef lexer hack

Algorithm 1.7.12 (Typedef-name classification by feedback)

• Input: an identifier token \(t\); the parser's current scope chain.
• Output: TYPE_NAME or IDENTIFIER (Definition 1.7.6).
• Precondition: the parser has processed every declaration before \(t\) (its lookahead does not pass \(t\) before classifying).
• Postcondition: the classification agrees with C's scoping rules at \(t\) (Proposition 1.7.18).
• Invariant: the symbol table reflects all declarations textually before the parser's current position.

function ClassifyIdentifier(t, scopes):
    for S in scopes from innermost to outermost:
        if t.name declared in S:
            return TYPE_NAME if that declaration is a typedef else IDENTIFIER
    return IDENTIFIER

# classic (yacc) C compilers: the lexer calls ClassifyIdentifier before returning the token
# Clang: the lexer returns identifier; Parser::TryAnnotateTypeOrScopeToken calls Sema
#        and replaces the token by an annot_typename token carrying the looked-up type

Clang: the same statement T * a; as a declaration and as an expression

Reproduce (clang 23.1.2; any OS):

cat > hack.c <<'EOF'
typedef int T;
void f(int b) { T * a; }
void g(int T, int a) { T * a; }
EOF
clang-23 -fsyntax-only -Xclang -ast-dump hack.c 2>&1 | grep -E 'FunctionDecl|DeclStmt|VarDecl|BinaryOperator|warning' | sed 's/0x[0-9a-f]*/0x…/g'

Output (complete):

hack.c:3:26: warning: expression result unused [-Wunused-value]
1 warning generated.
|-FunctionDecl 0x… <line:2:1, col:24> col:6 f 'void (int)' external-linkage
| |-ParmVarDecl 0x… <col:8, col:12> col:12 b 'int'
|   `-DeclStmt 0x… <col:17, col:22>
|     `-VarDecl 0x… <col:17, col:21> col:21 a 'T *'
`-FunctionDecl 0x… <line:3:1, col:31> col:6 g 'void (int, int)' external-linkage
  |-ParmVarDecl 0x… <col:8, col:12> col:12 used T 'int'
  |-ParmVarDecl 0x… <col:15, col:19> col:19 used a 'int'
    `-BinaryOperator 0x… <col:24, col:28> 'int' '*'

What to notice: the token sequences of the two bodies are identical (identifier * identifier ;). In f, T resolves to the typedef, so T * a; declares a of type T *; in g, the parameter T shadows the typedef, so the same text is a multiplication whose result is unused. Clang's parser asks Sema what T means (Parser::TryAnnotateTypeOrScopeToken) before choosing a grammar production: the lexer hack moved one level up.

3. Worked example

Lexer modes and start conditions

The Pebble input "o \("i \(d) e") \((1)) t" (from the unit test PebbleLexer.NestedInterpolation), token by token with the stack after each token:

#	token	kind	stack after	why
1	"o \(	string_head	[0]	\( in a string pushes 0
2	"i \(	string_head	[0, 0]	a string inside the interpolation, and its own \(
3	d	identifier	[0, 0]
4	) e"	string_tail	[0]	) with top 0: pop, resume the inner string, which ends
5	) \(	string_middle	[0]	) with top 0: pop, resume the outer string; its next \( pushes 0
6	(	l_paren	[1]	( inside an interpolation increments the top
7	1	int_literal	[1]
8	)	r_paren	[0]	top was 1: an ordinary )
9	) t"	string_tail	[]	top 0: pop; the outer string ends

Try it

./course drill lexer-modes --seed 2 --difficulty hard gives a snippet with nested interpolations, a nested comment and a maximal-munch trap, and asks for the deepest stack height.

JavaScript regex vs division

input	token before /	expression may start?	goal	tokens
a /b/ g	identifier a	no	Div	a / b / g
String(/b/g)	( of a call	yes	RegExp	/b/g
if (x) /b/g.test(…)	) ending an if head	yes (a statement starts)	RegExp	/b/g
(x) /b/ g	) ending an expression	no	Div	/ b / g

The last two rows have the same previous token; the previous-token heuristic must guess one of them wrong.

C++ >> in templates

V<V<int>> v;: the lexer emits V < V < int >> v ;. The inner argument list ends at >>: ParseGreaterThanInTemplateList rewrites the current token to > >, consumes the first, and the outer list consumes the second. In int x = 16 >> 2; no template argument list is open, so >> stays a shift.

Python INDENT/DEDENT

line	column \(c\)	stack before	action	stack after
1 if x:	0	[0]	\(c\) = top: nothing	[0]
2 y = 1	4	[0]	\(c >\) top: push, INDENT	[0, 4]
3 if z:	4	[0, 4]	equal: nothing	[0, 4]
4 w = 2	8	[0, 4]	push, INDENT	[0, 4, 8]
5 v = 3	0	[0, 4, 8]	pop 8: DEDENT; pop 4: DEDENT; \(c = 0\) = top	[0]
end	–	[0]	nothing to pop	[0]

Two INDENTs, two DEDENTs: the same counts as the real tokenizer in the box.

Raw strings

R"x(a)" b)x": delimiter x; scanning after (, positions of ): the first ) is followed by ", not x", so it is content; the second ) is followed by x": the string ends there. The content is a)" b.

The C typedef lexer hack

In void g(int T, int a) { T * a; }, when the parser reaches the body, the innermost scope (the parameters) declares T as an ordinary identifier, so ClassifyIdentifier returns IDENTIFIER even though the file scope has typedef int T: the statement is an expression.

4. Invariants and correctness

Lexer modes and start conditions

Theorem 1.7.13 (Interpolation needs a stack, and the counter stack is enough)

(i) The set of well-formed Pebble string literals with interpolation (strings inside interpolations inside strings, to any depth) is not a regular language. (ii) Algorithm 1.7.7 maintains its invariant and splits every well-formed literal as in spec §3.5.

Proof

(i) Intersect with the regular language \(\texttt{"}(\texttt{\textbackslash(}\texttt{"})^{*}(\texttt{"}\texttt{)})^{*}\texttt{"}\) (hypothetically: nothing but nested openers and closers). The well-formed members are those with \(k\) openers \(" followed by exactly \(k\) closers "), the language \(\{o^{k} c^{k}\}\) with \(o, c\) fixed strings, not regular by the argument of Corollary 1.1.17. (ii) By induction over the tokens. A \( inside a string piece opens an interpolation and pushes a zero counter: the invariant holds for the new innermost interpolation. A ( in code increments the innermost counter; a ) with a positive counter decrements it: it closes a parenthesis opened inside the interpolation, because parentheses in code are balanced inside a well-formed interpolation. A ) with counter 0 cannot close a code parenthesis (none is open since the \(), so it closes the interpolation: pop, and the bytes that follow belong to the enclosing string, scanned by StringPiece with continuation = true, which yields string_middle at the next \( or string_tail at the closing quote. A " in code starts a new string whose own \( push above the current entry, so the stack mirrors the nesting. \(\square\)

JavaScript regex vs division

Proposition 1.7.14 (No previous-token rule is correct; parser direction is)

(i) No function of the previous token alone decides whether a / starts a regex in ECMAScript. (ii) Algorithm 1.7.8 produces the tokenization of ECMA-262.

Proof

(i) The real-world box gives two programs in which the token before /b/g is ) in both, with different correct tokenizations (lines 4 and 5). (ii) ECMA-262 defines the lexical goal by the syntactic context: "The InputElementRegExp goal symbol is used in all syntactic grammar contexts where a RegularExpressionLiteral is permitted" [ECMA262 §12]. A parser that requests the goal at each token and never scans past an undecided / implements this definition literally. \(\square\)

C++ >> in templates

Proposition 1.7.15 (Splitting preserves shift expressions)

Algorithm 1.7.9 changes the tokenization only of a >>, >= or >>= token that ends a template argument list; every other >> is a shift. In particular f<(a >> b)> is parsed with >> as a shift because the parenthesis hides it from the template list.

Proof

The rewrite happens only in ParseGreaterThanInTemplateList, called only when a template argument list expects its closing >. Inside parentheses the parser is parsing an ordinary expression, where >> is an operator and no list closing is expected. [N1757] specifies exactly this rule: "the first non-nested >> is treated as two consecutive but distinct > tokens". \(\square\)

Python INDENT/DEDENT

Proposition 1.7.16 (Indentation tokens are balanced)

Algorithm 1.7.10 keeps \(I\) strictly increasing, and the numbers of INDENT and DEDENT tokens it emits are equal; between any INDENT and its matching DEDENT the tokens form a nested block.

Proof

A push happens only when \(c > \mathrm{top}(I)\), so \(I\) stays strictly increasing; pops preserve that. Each INDENT pushes exactly one entry and each DEDENT pops exactly one; at the end all entries above 0 are popped, so the counts are equal. Pushes and pops follow a stack discipline, so INDENT/DEDENT pairs nest like brackets. \(\square\)

Raw strings

Proposition 1.7.17 (Raw strings need memory; bounded delimiters give a large DFA)

(i) Rust raw strings with an unbounded number of # would not be regular. (ii) With delimiters of length at most \(D\) over an alphabet of \(s\) allowed characters, the C++ raw-string language is regular, but a DFA for it needs at least \(s^{D}\) states. (iii) Algorithm 1.7.11 returns the first closing sequence, which is the correct end.

Proof

(i) Intersect with \(\texttt{r}\#^{*}\texttt{""}\#^{*}\): the members are \(\texttt{r}\#^{n}\texttt{""}\#^{n}\), and the pumping argument of Lemma 1.1.16 applies. (ii) Regular: a finite union over delimiters of regular languages. States: after reading \(\texttt{R"}d\texttt{(}\), the automaton must remember \(d\) to recognize \(\texttt{)}d\texttt{"}\) later; two different delimiters \(d \neq d'\) of length \(D\) are distinguished by the continuation \(\texttt{)}d\texttt{"}\), so there are at least \(s^{D}\) Nerode classes (Theorem 1.4.7). With \(D = 16\) this is astronomically large, which is why lexers store the delimiter in a variable instead. (iii) By Definition 1.7.5 the content cannot contain the closing sequence, so the string ends at its first occurrence; the invariant says none occurred earlier. \(\square\)

The C typedef lexer hack

Proposition 1.7.18 (Token classes depend on declarations)

There is no function of the token sequence of a C compound statement alone that decides whether T * a; is a declaration. With Definition 1.7.6 and a parser whose lookahead never passes an unclassified identifier, the classification is correct.

Proof

The two functions of the real-world box contain the same token sequence T * a ; and require different parses; the difference lies only in earlier declarations. With feedback, the classification uses the symbol table at \(t\), which by the precondition contains exactly the declarations before \(t\); C's scope rules then determine the answer (a typedef name shadowed by an ordinary identifier is an ordinary identifier, C17 6.2.1). \(\square\)

When it breaks: lookahead. A parser that has already lexed tokens past a declaration may have classified them with a stale symbol table (the famous typedef int T; T x; on one line with an LALR parser that reads T as lookahead before reducing the typedef). Clang avoids it by annotating tokens lazily in the parser.

5. Complexity

Variables: \(n\) = input length; \(h\) = maximal nesting depth (interpolations, indentation levels); \(D\) = raw-string delimiter length.

Technique	Time	Space	Notes
Lexer modes + stack	\(O(n)\)	\(O(h)\)	each byte scanned once per mode switch; switches are \(O(1)\)
JS goal selection	\(O(n)\)	\(O(1)\) extra	V8 rescans only the regex literal: \(O(\text{its length})\)
C++ >> splitting	\(O(1)\) per split	\(O(1)\)	the token is rewritten in place
Python INDENT/DEDENT	\(O(n)\)	\(O(h)\)	DEDENTs at a line: \(O(\text{levels popped})\), amortized \(O(1)\) per INDENT
Raw strings	\(O(n \cdot D)\) naive, \(O(n)\) with KMP	\(O(D)\)	\(D \le 16\) in C++: effectively \(O(n)\)
Typedef feedback	\(O(n)\) lookups	symbol table	one scope-chain lookup per identifier (hash tables: \(O(\text{depth})\))

Pathological input for the naive raw-string scanner: a C++ raw string whose content is \(\texttt{)}x^{D-1}\texttt{)}x^{D-1}\cdots\) (almost-delimiters) costs \(\Theta(D)\) comparisons per ), \(\Theta(nD)\) total; a KMP matcher for the closing sequence makes it \(O(n)\). For modes, deeply nested interpolation costs stack depth \(h\), which Pebble bounds only by memory (SmallVector).

At scale. The mode checks are one if per (/) in Pebble's lexer, invisible in the benchmark (104 MB/s with interpolation-free input; ch01-regexbench section 4).

6. Variants and refinements

Lexer modes and start conditions

• Exclusive vs inclusive start conditions (flex %x vs %s) [FLEX-Manual]: whether rules without a condition stay active in the mode.
• Scan the interpolated expression by bracket matching (Swift's skipToEndOfInterpolatedExpression first finds the end of \( … ) by counting brackets and skipping nested strings, then lexes the interior separately) vs one-pass mode stack (Pebble, Kotlin); the first gives better recovery for unterminated interpolations, the second is simpler.

JavaScript regex vs division

• Previous-token heuristics (syntax highlighters, some minifiers): cheap, occasionally wrong (§3 table).
• Parser-driven rescanning (V8 ScanRegExpPattern, Acorn, Babel): correct, requires lexer–parser coupling.

C++ >> in templates

• Split in the parser (Clang, GCC; N1757 [N1757]) vs lex > one at a time and join in the parser (some parsers never produce >> and rebuild shifts from adjacent > tokens, checking that no whitespace separates them). Java (generics) and C# have the same problem and choose one of the two.

Python INDENT/DEDENT

• Layout rule in the parser (Haskell): the layout algorithm inserts implicit braces and semicolons, and can also close a block when the parser hits an error (the "parse-error(t)" rule): more power, requires parser cooperation.
• Off-side rule in the lexer (Python, F#'s light syntax, YAML): stack in the lexer, no parser feedback.

Raw strings

• User-chosen delimiters (C++ R"d(…)d", Rust r#"…"#) vs fixed triple quotes (Python r"""…""", which cannot contain """).
• Heredocs (shell, Ruby, PHP): the delimiter is a whole line, which requires line-oriented lexing and a queue of pending heredocs.

The C typedef lexer hack

• Parser annotation (Clang's annot_typename tokens): lookups happen in the parser, and tokens are annotated in place so backtracking (tentative parsing) does not repeat them.
• Ambiguity-preserving parsing (GLR parsers for C/C++ such as Elkhound): parse both ways and disambiguate later with semantic information, avoiding feedback into the lexer.

7. In real compilers

Lexer modes and start conditions

• Pebble solutions/pebble/lib/Lex/src/Lexer.cpp — the InterpolationDepth stack in Lexer::lex and lexStringPiece.
• Swift lib/Parse/Lexer.cpp — skipToEndOfInterpolatedExpression and Lexer::lexStringLiteral (swift-6.1-RELEASE) [SWIFT-Lexer].
• flex start conditions and yy_push_state [FLEX-Manual]; box in §2.

JavaScript regex vs division

• V8 src/parsing/scanner.cc — Scanner::ScanRegExpPattern, called by the parser when it sees / or /= in primary-expression position (V8 12.9.1) [V8-Scanner]; box in §2 (Node.js 22 ships V8 12.x).

C++ >> in templates

LLVM / Clang

clang/lib/Parse/ParseTemplate.cpp — Parser::ParseGreaterThanInTemplateList handles >, >>, >=, >>= (and >>> in CUDA), splitting the token in place (LLVM 23.1.2) [CLANG-ParseTemplate]; box in §2.

Find where LLVM does it. Open clang/lib/Parse/ParseTemplate.cpp at llvmorg-23.1.2 and read ParseGreaterThanInTemplateList. Question: which token kinds does it accept as "the end of a template argument list, possibly with a remainder"? (Quiz llvm-template-greater.)

Python INDENT/DEDENT

• CPython Parser/lexer/lexer.c — tok_get_normal_mode, returning INDENT/DEDENT from the tok->indstack (v3.13.0) [CPYTHON-Lexer]; box in §2.

Raw strings

• Clang clang/lib/Lex/Lexer.cpp — Lexer::LexRawStringLiteral (LLVM 23.1.2) [CLANG-Lexer]; box in §2.
• rustc compiler/rustc_lexer/src/lib.rs — Cursor::raw_double_quoted_string, RawStr { n_hashes } (Rust 1.94.1) [RUSTC-Lexer].

The C typedef lexer hack

• Clang clang/lib/Parse/Parser.cpp — Parser::TryAnnotateTypeOrScopeToken (LLVM 23.1.2) [CLANG-Parser]; box in §2.
• GCC's C front end (gcc/c/c-parser.cc, c_lex_one_token) classifies identifiers as it lexes them, the lexer-hack arrangement.

8. Comparison

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Lexer modes and start conditions	nested structure via a stack (pushdown)	\(O(n)\), \(O(h)\) space	good: the lexer knows where an interpolation started	small–moderate	string interpolation, heredocs, nested comments
JavaScript regex vs division	exact with parser direction	\(O(n)\)	exact; heuristics mis-lex rare cases	lexer–parser coupling	JavaScript, Ruby (/), Perl
C++ >> in templates	exact	\(O(1)\) per split	fix-its possible (Clang's C++98 message)	small, in the parser	C++, Java, C# generics
Python INDENT/DEDENT	layout as tokens	\(O(n)\), \(O(h)\)	precise "unindent does not match" errors	small	Python, F# light syntax, YAML
Raw strings	delimiter memory in a variable	\(O(n)\) (\(O(nD)\) naive)	"unterminated raw string" with the delimiter	small	C++, Rust, Python
C typedef lexer hack	exact with feedback	\(O(n)\) lookups	depends on parser lookahead discipline	coupling to the symbol table	C (and C++ via parser annotation)

Choose modes for anything nested inside tokens. Choose parser direction or parser splitting when the syntactic context decides the token (regex/division, >>). Choose a lexer-level stack for layout. Store delimiters in variables rather than in the automaton. Keep semantic feedback in the parser when possible (Clang), because the lexer's lookahead makes stale classifications possible.

9. Assessment

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Lexer modes and start conditions	interp-kinds, interp-depth	./course drill lexer-modes	lexer-modes	E4
JavaScript regex vs division	js-slash, context-feedback	justification below	regex-vs-division	—
C++ >> in templates	llvm-template-greater, context-feedback	justification below	template-angle-brackets	—
Python INDENT/DEDENT	indent-dedent-count, context-feedback	justification below	indent-dedent	—
Raw strings	raw-string-end, context-feedback	justification below	raw-strings	—
The C typedef lexer hack	lexer-hack, context-feedback	justification below	lexer-hack	—

Only the interpolation stack gets a drill (lexer-modes, which also exercises maximal munch and nested comments): the other five are single decisions per token whose practice value is in understanding the context, not in repetition. The quiz asks each as a concrete instance (js-slash, indent-dedent-count, raw-string-end are computations on given inputs).

Pitfall

"The lexer is regular" is a slogan, not a property of real languages. Every mainstream language has at least one lexical construct that needs a mode, a counter or feedback; the design question is where to put that state so that errors stay understandable.

References

See the chapter references.