Hacker News Reader

Comment by throwaway2016a | Hacker News Reader

throwaway2016a

Lexing and parsing doesn't strike me as a task that would benefit significantly from multithreading.

I always use golang.org/x/tools/cmd/goyacc to generate my lexers and parsers. It's a Go port of Lex/Yacc (Flex/Bison) that works pretty well and is very fast.

It basically works by writing your lexes and parser in a Domain Specific Language (DSL) and compiling into go. It's pretty fast.

View on HN

Multithreading and coroutines are different concepts though in practice they may end up being the same thing.

Coroutines were invented surprisingly enough, for lexing and parsing[0].

[0] http://melconway.com/Home/pdf/compiler.pdf

Edit1: added source. I'm surprised Melvin Conway is still alive

Interesting information. Thank you for the link, I'll have to take a look.

Though, the "in practice" part is the thing that gets me. I can see how the code might be easier to read but performance wise it seems like a lot of overhead since the coroutines are unlikely to be doing things like waiting for I/O.

Lexing is more-or-less regular expression searching. Most regex engines are a mix of CPU- and memory-bound when searching for complicated REs (as one would have with a lexer; lex just combines patterns into a giant hardcoded DFA).

So, there’s room on the CPU for multithreading to improve performance, but it must be done carefully to minimize both contention and cache evictions.

I don't see the advantage neither. Since tokenization is usually sequential, it only seems to add overhead. If you can identify chunks in your input at a much lower cost than actually parsing that chunk, it might be of use.

I'm glad I went to the university and learned about how to do things like lexing and parsing from my professors. I feel for people who have to substitute their education with blog posts and Rob Pike talks.

Those people wil get things done, but often in a roundabout way, reinventing the wheel multiple times along the way. Meanwhile the fortunate ones, like you, will pick the right tool, apply it, get state of the art results on their first try and move on.

personally I think the literature and academia contain great treasures that are ignored.

but your argument that the academy is center of knowledge about the pragmatics of software development falls a bit flat. if you've been around enough you know 'grad student code' when you see it.

I also went to university, where they also over-focused on lex and yacc and similar. However, most people who work on parsers where the user or developer experience matters don't use them, because they are quite restrictive and cumbersome and typically don't give nice error messages.

Academia doesn't necessarily teach you the most useful way to do things.

Would you painstaikingly handcraft a recursive descent parser because the generator doesn't give you nice error messages?

That's a fairly normal approach, yes [1]. It's not so painstaking. There are parser generators other than lex and yacc that do a better job, but making most generators produce good errors and handle your context-sensitive tokenisation is more effort overall than making an equivalent hand-written parser (be it near-Pratt, PEG, general recursive descent or anything else).

[1] https://notes.eatonphil.com/parser-generators-vs-handwritten...

Reply on news.ycombinator.com