> I've seen interleaved lexing and parsing, where the recursive descent parser asks for the next token, which is computed on demand.

This is how I implemented it in my language. Evaluator asks parser for a value, parser asks lexer for one or more tokens, lexer asks the I/O layer for characters. It's nice.