Context-Dependent Lexing: Typedef Names, Layout, and Lexer Modes

The clean separation between lexer and parser assumes that a token’s kind depends only on the characters at its position. Several widely used languages violate that assumption, and the workarounds are instructive because each one is a different answer to the same question: where can context legitimately enter the token stream?

There are three distinct mechanisms. A lexer can carry modes that other parts of the front end switch. A lexer can consult a symbol table that the parser fills. Or the lexer can emit structured tokens that contain nested token sequences, which pushes the context into the token’s payload.

The typedef ambiguity, precisely

In C, T * x; declares a pointer if T is a type name, and multiplies if T is a variable. The characters are identical, the token sequence is identical, and the parse differs. No grammar over a context-free token alphabet resolves it, because the token kinds themselves differ: one reading needs T to be a TYPE_NAME and the other needs it to be an IDENTIFIER.

The standard’s grammar acknowledges this with a rule about how the tokens are typed: an identifier is lexed as a typedef name if a declaration has made it one and that declaration is visible at that point, so shadowing by an inner declaration of the same name removes the typedef reading. The rule is stated in terms of declarations, not the character stream.

Three implementations exist.

The first keeps a set of active typedef names in the lexer and updates it from the parser. When the parser reduces a declaration of a typedef, it calls into the lexer to add the name; when a scope ends, it removes names declared in that scope. This is the classic “lexer hack”, and it is correct as long as the parser’s view of scopes matches the lexer’s set exactly. Any divergence produces a token of the wrong kind and a parse error far from the cause.

The second moves the decision into the parser: the lexer emits IDENTIFIER for everything, and the parser’s declaration rules accept an identifier where a type name is expected, consulting its own symbol table. This avoids the shared mutable state and is what several modern C front ends do. The cost is a grammar with more alternatives, and a parser that must look up names during parsing rather than after.

The third defers: parse both readings and resolve later. That requires a parser that can hold ambiguity, which is the GLR approach described in GLR Parsing and the Graph-Structured Stack. It is the only option that needs no synchronisation between lexer and parser, and it is the most expensive.

Why the lexer cannot decide alone

The information needed is whether a name is currently a type. That depends on declarations that appear earlier in the file and on the scope structure, which is exactly what the parser is computing. The lexer sees a linear stream and has no notion of scope.

A lexer could be given its own scope tracking, but then two components independently implement C’s scope rules, and the two must agree on every edge case: function prototypes, block scopes, labels, struct members, and the point at which a declaration takes effect. Keeping one implementation is the reason the first approach above is popular despite the coupling.

The coupling has a measurable shape: the lexer must be callable from the parser at reduction points, which means the two cannot be pipelined. A design that tokenizes a whole file before parsing cannot support typedef names at all.

Layout: turning indentation into structure

Python and Haskell both use layout to delimit blocks. Python’s lexical rules generate INDENT and DEDENT tokens, plus NEWLINE, from the column positions of line starts. The lexer keeps a stack of indentation levels; when a line begins at a column greater than the top of the stack, it pushes and emits INDENT; when less, it pops until the column matches and emits one DEDENT per pop; when it matches no level, it reports an inconsistent indentation error.

The stack is a lexer-level structure, but it is context in a different sense: it depends on the token sequence’s line structure, not on the parser’s state. That makes it implementable inside the lexer without any parser feedback, which is why Python’s tokenization is a well-defined function of the source text.

Haskell’s layout rule is harder because it is inserted at specific points in the grammar rather than at line starts generally. The rule applies after the keywords where, let, do, and of: each opens a layout context at the column of the next token, and subsequent lines at that column are treated as a new item. If a line begins at a smaller column, the context closes with a virtual closing brace.

Implementations either preprocess the token stream, inserting virtual braces and semicolons according to the rule, or let the parser apply the rule at the grammar points where it triggers. The preprocessing approach keeps the parser simple but must know which keywords open contexts; the parser approach knows the grammar position but spreads the rule across many rules.

Both approaches share a failure mode: an explicit brace in the source interacts with the virtual one, and the rule that a virtual block is not opened when an explicit brace follows is easy to omit. Getting it wrong accepts input the report rejects, and the discrepancy appears only in files that mix styles.

Interpolation and the nested token stream

String interpolation is the third case. In a string like "sum is {a + b}", the characters inside the braces are not string contents; they are an expression. A lexer that emits one STRING token has thrown away the structure, and a later pass must re-lex the interior, which duplicates the lexer and loses position information.

The usual design is for the lexer to emit a sequence: STRING_START, the literal fragment, INTERP_START, the tokens of the expression, INTERP_END, and so on until STRING_END. The lexer then needs a mode stack, because inside the interpolation it is lexing normal code, and on the closing brace it returns to string mode. Nested interpolations push the stack again.

The mode stack is the same mechanism as start conditions in a generated lexer: a set of automata plus an explicit push and pop. What makes interpolation harder than a start condition is that the pop point is determined by the parser’s bracket matching, not by a character. A } that closes a nested block is not the } that ends the interpolation, so the lexer must count braces or the parser must tell it when the expression ends.

Counting braces inside the lexer works if the lexed tokens are only braces and parentheses; it fails as soon as a brace appears inside a nested string or a comment, both of which are lexer states that already suppress brace counting. The mode stack handles this correctly if comments and nested strings are states on the same stack.

The mode machine, in code

The mode stack is small enough to state directly, and stating it makes the brace-counting requirement explicit.

#[derive(Clone, Copy, PartialEq)]
enum Mode { Code, Str, Interp { depth: u32 } }

fn next_token(&mut self) -> Token {
    match self.modes.last().copied().unwrap_or(Mode::Code) {
        Mode::Str => {
            // Scan literal text until '"' or '{'.
            match self.scan_string_body() {
                StringBody::End => { self.modes.pop(); Token::StrEnd }
                StringBody::Interp => {
                    self.modes.push(Mode::Interp { depth: 0 });
                    Token::InterpStart
                }
                StringBody::Chunk(s) => Token::StrChunk(s),
            }
        }
        Mode::Interp { depth } => {
            let t = self.scan_code_token();
            // Only an unmatched '}' leaves interpolation; nested braces
            // adjust the depth so that a block's brace is not mistaken for it.
            match t.kind {
                Kind::LBrace => self.set_depth(depth + 1),
                Kind::RBrace if depth == 0 => { self.modes.pop(); }
                Kind::RBrace => self.set_depth(depth - 1),
                _ => {}
            }
            t
        }
        Mode::Code => self.scan_code_token(),
    }
}

The depth field is the whole of the correctness argument, and it is per-mode rather than global, so nested interpolations each carry their own count.

What the coupling costs

Every mechanism here breaks the property that a lexer can run to completion before the parser starts. A front end with typedef names must interleave the two; a front end with interpolation must let the parser’s bracket structure influence when the lexer returns to string mode.

The benefit of keeping those phases separate is real: a lexer that runs independently can be tested against a token dump, parallelised across files, and reused by a syntax highlighter that has no parser. Languages with context-dependent lexing lose all three, which is why their tooling tends to reuse the parser for highlighting rather than the lexer.

The alternative that preserves the separation is to keep the token stream context-free and resolve the ambiguity in the grammar. C’s declaration syntax can be parsed with an identifier token and a symbol table in the parser; interpolation can be handled by making the string literal a grammar construct whose interior is parsed as an expression. Both move the work rather than removing it, but they leave the lexer a pure function of the text.

The token-level machinery that the mode stack extends is described in From Regular Expression to DFA Table. The parser-side consequences for error messages are in Error Recovery in Recursive Descent Parsers.