Crafting a parser, part 6: ambiguity, lookahead, and the lexer hack

Real grammars have corners where one token of lookahead isn't enough — or where the same token sequence has two legal readings. This post collects the classic ambiguities and the honest tricks parsers use to resolve them.

The dangling else

if a if b x else y — whose else is it? The grammar is genuinely ambiguous; the fix is a rule, not more parsing: bind else to the nearest if. In recursive descent you get this for free by greedily consuming else in the inner call.

The less-than problem

In a < b, is < less-than, or the start of generics like Vec<T>? C++ famously needs type information during parsing to decide — the original lexer hack. Modern languages dodge it with syntax (Rust's turbofish) or with bounded lookahead that tries to scan a type and backtracks.

1fn parse_lt_or_generics(&mut self) -> Expr {2    let checkpoint = self.checkpoint();      // remember the position3    if let Some(args) = self.try_generic_args() {4        return self.path_with_generics(args);5    }6    self.rewind(checkpoint);                 // it was just less-than7    self.comparison()8}

Bounded backtracking

Pure LL(1) forbids backtracking; real parsers allow a little, behind a checkpoint and rewind. The discipline: backtrack only across a bounded, local region, never the whole input, or you reinvent exponential-time parsing.

Takeaways

• Most ambiguity is resolved by a written rule (nearest-else, max-munch).
• The less-than problem is real; syntax or bounded lookahead beats type-directed parsing.
• Allow backtracking only locally, behind explicit checkpoints.

Next: resilient, incremental parsing.