3 ms·
I won't say this is the explicit reason recursive descent parsers have separate lexers, but there is a major downside to folding the lexer into a recursive desc
by kerkeslager 4y ago
I won't say this is the explicit reason recursive descent parsers have separate lexers, but there is a major downside to folding the lexer into a recursive descent parser, which would occur when/if you make the leap to packrat parsing. If the parsed language develops far enough you'll often run into edge cases where backtracking can become pathological. One benefit to recursive descent is that you can often just fix this by memoizing the parser functions (called a packrat parser).
However, you really don't want to memoize calls to lexer-y parser functions because it's almost always faster and less memory-intensive to simply re-lex the source string. This gets more complicated if you're parsing a stream (but if your language is being parsed from a stream you should definitely be giving strong preference to language constructs which don't require backtracking).
- seanmcdirmid 4y agoIncremental re-Lexing works great in IDEs where you want to preserve tokens and the state associated with them. It also helps to isolate errors by attributing them to a token that contains the change rather than somewhere far off. Incremental parsing is the same: it costs more in terms of memory and even overall time, but provides better feedback for the IDE. Batch compilation is a different beast, but I haven’t written one of those for a pint time.