3 ms·
Honestly, while that talk is cool, I don't think you should actually write lexers or parsers that way. The best way is probably the good ol' hand-written way, u
by jchw 4y ago
Honestly, while that talk is cool, I don't think you should actually write lexers or parsers that way. The best way is probably the good ol' hand-written way, using something like recursive descent. It's ugly, tedious and repetitive, but if you don't want to accept any compromises, it's difficult to beat it. All of the JS parsers I've looked at do this, from V8 to Spidermonkey, to modern software like ESbuild (also written in Go and blindingly fast.)
The coroutine style of lexer is probably bound to not have such a bad slow down on larger stuff, but it depends. The amount of contention and locking introduced by adding a channel in such a hot path seems like it is probably not going to be worth it, especially if you are likely to do many parsing tasks in parallel and can simply make the boundary for parallelism further down the line.
edit: Somehow while writing this, I managed to forget that I also wrote a JS parser, albeit I never finished it. It uses a typical manually written lexer + parser, too, although it's probably pretty slow from being written stupidly. It lacks the ability to deal with a couple constructs due to ambiguity (most notably, I didn't get past the part where you parse fat arrow lambdas; it is ridiculously hard to tell them apart from other grammar elements.)
https://github.com/jchv/cleansheets https://github.com/jchv/cleansheets / https://cleansheets.io/parser/ https://cleansheets.io/parser/
- alex_smart 4y agoYou don't have to use a channel for coordination. Here is a lexer implementation (in C!) that very closely follows Rob Pike's talk and uses a ring buffer for coordination and is plenty fast. https://github.com/lpereira/lwan/blob/master/src/lib/lwan-template.c https://github.com/lpereira/lwan/blob/master/src/lib/lwan-te... If you watch the talk carefully, Rob Pike himself mentions this near the end of the talk.
- jchw 4y agoEven if you do this, the CPU still ultimately has to synchronize if you put the workflow across threads, so you have to get a contention hit somewhere. (Lockfree data structures still hit locks in the silicon, after all.) I could be wrong, but when it comes to performance it seems like your best option is moving the concurrency elsewhere. For design? I dunno. I find the design to be elegant for sure, but I also don’t mind handwriting parsers in general.
- alex_smart 4y agoThe lexer is entirely single-threaded, as in the original Rob Pike talk. >I find the design to be elegant for sure, but I also don’t mind handwriting parsers in general. But this is a hand-written parser! Just using function pointers to store the state instead of using an enum and switch statements.
- jchw 4y agoYep, fair enough. As a single-threaded design, I have no particular problems with it.
- johnthescott 4y agoi prefer lexers as nothing more than case statements. i recall no less than brian kernighan discussing this back in the day. keep the lexers simple. that is why we have backus-naur.