4 ms·
> The downside is that, if you perform this as a separate pass, your parser now has to iterate over all of the source code twice. This may not be the end of the
by quietbritishjim 6y ago
> The downside is that, if you perform this as a separate pass, your parser now has to iterate over all of the source code twice. This may not be the end of the world: tokenizing isn't the most expensive operation. But it isn't ideal, so some parsers combine the two passes into a single one, saving cycles at the expense of readability.
This paragraph is a bit muddled:
* If you keep the two passes separate, then the second pass is over the token stream. So it's irrelevant that "tokenizing isn't the most expensive operation" because you're never going to do the actual tokenising a second time.
* If you combine the two passes then you're not "saving cycles" because you're still doing both of the loops - it's just that they're now happening in parrallel rather than in sequence. This confusion is repeated later when he says the combined one is "without the runtime overhead of a second loop".
* What you are saving is memory, because you don't have to keep the whole token stream in memory at once.
But really this is a nitpick on a small note. The overall article is great.
- Rotten194 6y agoNitpick^2: You are probably saving a few cycles due to loop overhead around pointer offsets and bounds checking, + not having to load the items into cache twice, if the sequence is too long to fit into cache.
- quietbritishjim 6y agoAgreed! I definitely wasn't telling the whole truth by saying the amount of cycles spent on looping is ultimately the same. Although the difference is complex enough that I could imagine it going either way (but you're right that the cache effects would probably be the clincher).
- bananabreakfast 6y agoI don't think this is a nitpick, this is a valid point that actually plays even more into the concept of Rust's fearless concurrency. You're not avoiding the runtime overhead of a second loop but being able to operate on both streams in parallel would be a far more complicated concept in C/C++. This actually reminds me of that influential Rob Pike talk about writing a concurrent parser in Go.
- quietbritishjim 6y agoAh, I wasn't sure whether to open that can of worms in my comment. The truth is I was sloppy using the word "parallel". The article describes interleaving the tasks but not actually multithreading them. Doing that in C++ would be just as easy as the article did it in Rust: you make a little iterator class (not necessarily STL iterator compliant, just that sort of idea) that hides the whole lexer behind an iterface that yields the next token each time. It wouldn't have the lifetime guarantees described in the article, but in this sort of context, if you're single threading, the object lifetimes are straightforward anyway. Maybe you could take advantage of Rust's lifetime guarantees to multithread things more easily than C++. That would potentially be a much more interesting article, if it turns out to be a lot easier than in C++.
- Joker_vD 6y agoLexers/parsers, when written together, generally interface each other either as "parser calls lexer.PeekToken()/lexer.AdvanceToken() until it's done parsing, or lexer returns EOF", or, rarer, "lexer calls parser.ConsumeToken(tok) until there is no more input left, and calls parser.Done()". IIRC, SQLite uses the second approach to parse SQL. At no point does any of these schemes require the lexer to read the whole file into memory, and chop it in one go into a huge list of ready-to-be-consumed tokens.
- quietbritishjim 6y agoSure, in practice, no one ever builds the whole list of tokens in memory, because they all use the same sort of idea described in the article (and described again in your comment). But the article author chose to compare why they don't ever do it that way, and that's what I was commenting on.