intermediateLexing

A lexer sees `x+++y`. What does it produce, and why?

Whether the candidate knows that lexing is greedy by rule rather than by intent, and can predict the consequence when the greedy choice is the wrong one. It also separates people who have written a lexer from people who have read about one.

What a strong answer covers

  • Under maximal munch — take the longest lexeme that forms a valid token at the current position — the lexer emits x, ++, +, y. The lexer does not know or care that x + (++y) might be what the author meant; it is a finite automaton with no view of the grammar.
  • That rule is what makes lexing a regular-language problem and therefore fast and simple: a DFA, one pass, no backtracking, no parser feedback. The cost is a class of surprises that all have the same shape — >> in old C++ template syntax, 1..2 in a language with both a float literal and a range operator, <!-- inside JavaScript, and the classic 123abc, which is not a number followed by an identifier but an invalid numeric literal, because the number rule munches as far as it can and then finds letters.
  • Languages either accept this and document it, or they push the resolution up: a lexer hack where the parser tells the lexer what a name means, a scannerless parser, or a lexer whose token rules are context-sensitive in a controlled way — significant indentation, string interpolation and template literals all require some form of mode stack.
  • The practical consequence is diagnostic quality. A maximal-munch failure usually surfaces as a parse error one token later, or on the next line, because the lexer produced tokens that were individually valid and jointly nonsense.
✓ Green flags
  • Names maximal munch and applies it mechanically rather than guessing at intent.
  • Explains why the rule exists — regularity, one pass, no parser feedback.
  • Gives a second example from a real language.
  • Connects it to where the error will actually appear, which is not where the problem is.
  • Mentions the modes and hacks languages use when a pure lexer is not enough.
✗ Red flags
  • "The lexer looks ahead to see what makes sense." It looks ahead within the token rules only; nothing about "sense" is available to it.
  • "The parser will fix it." The parser can only work with the tokens it was handed; it cannot re-split ++ into two +.
  • "Whitespace does not matter, so x+++y and x++ +y are identical." They are — that is the point, and it is why the author's intent is unrecoverable.
  • "123abc lexes as 123 then abc." Only in a lexer that does not munch maximally; in most real ones it is a malformed numeric literal, and the difference is exactly what the error message will be about.

Follow-up

Your language has both a range operator .. and float literals like 1.5. What does 1..5 lex as, and what would you do about it?

Implementation challenge

What to ask them to write or trace on a whiteboard.

Write the state machine for a lexer that handles +, ++ and +=. Then add +++ as a token and say what breaks.

The lessons behind it

Lexical Analysis →Lexer Hazards →Token Kinds →Regular Languages →Implementing a Lexer →NFA vs DFA →
← All questions