4 ms·

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

by throwaway2016a 4y ago

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.

tgv 4y ago
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.
kubb 4y ago
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.
- convolvatron 4y ago
  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.
- ghusbands 4y ago
  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.
  - kubb 4y ago
    Would you painstaikingly handcraft a recursive descent parser because the generator doesn't give you nice error messages?
    - ghusbands 4y ago
      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-parsers-survey-2021.html https://notes.eatonphil.com/parser-generators-vs-handwritten...
chewxy 4y ago
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 http://melconway.com/Home/pdf/compiler.pdf Edit1: added source. I'm surprised Melvin Conway is still alive
- throwaway2016a 4y ago
  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.
jonstewart 4y ago
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.

tgv 4y ago

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.

kubb 4y ago

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.

convolvatron 4y ago
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.
ghusbands 4y ago
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.
- kubb 4y ago
  Would you painstaikingly handcraft a recursive descent parser because the generator doesn't give you nice error messages?
  - ghusbands 4y ago
    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-parsers-survey-2021.html https://notes.eatonphil.com/parser-generators-vs-handwritten...

chewxy 4y ago

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 http://melconway.com/Home/pdf/compiler.pdf Edit1: added source. I'm surprised Melvin Conway is still alive

throwaway2016a 4y ago
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.

jonstewart 4y ago

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.