For an alternative take on a related topic, this is really a fantastically well-written and practical (free) book: http://craftinginterpreters.com
Not free but also very good is https://interpreterbook.com/
Parsing Algorithms
21–30 of 87 posts
Re: Parsing Algorithms
#22For an alternative take on a related topic, this is really a fantastically well-written and practical (free) book: http://craftinginterpreters.com
Not free but also very good is https://interpreterbook.com/
Both of Thorsten Ball's books in that series are phenomenal, could not recommend more. He's also got a great discussion of it on the Go Time podcast, https://changelog.com/gotime/28 and https://changelog.com/gotime/107.
Re: Parsing Algorithms
#23I'd like to see something like this for practitioners. I kind of have a feel for what's out there, but I don't know of anything that is: 1. pleasant to use 2. simple 3. scannerless 4. supports left recursion that produces a left-associative parse
Marpa meets 2.a) 2.b) 3.
1. is subjective.
Re: Parsing Algorithms
#24Earlier quoted context omitted.
I found the code for Instaparse (relatively) easy to follow. I had considered leaving a comment here like "hey could you cover combinators and PEGs?", but after thinking it over, it's important to limit the scope for a class like this. It would be pretty great to offer a "201" edition, covering ALL*, GLR, GLL, combinators/PEGs, Earley, parsing-with-derivatives, Marpa, and anything else I might have forgotten: basical…
What is GRR? Did you mean GLR?
Yep, that was a typo, fixed it
Re: Parsing Algorithms
#25Earlier quoted context omitted.
Great point on combinators, PEG, and GLL -- this potentially would be covered in 201 as suggested, since it's good having a foundation of the LL/LR, and then gradually moving to combinators if needed. LALR(1) covers a pretty wide range of the most practical languages.
To a significant degree, the arrow of causality runs LALR(1) -> practical languages, not the other direction! The languages and formats we use have been heavily shaped by the practical parsing algorithms of the 20th century. An example: you can't have a struct field called "while" in C, because once the lexer declares a token to be a keyword, that's that.
TBH, that's not a problem of LALR(1), or any of the other, more old fashioned methods. I've written an LL(1) parser generator that (generates a function that) parses modern awk, without semicolons, but with operator-less concatenation, and that can deal with tokens that can be keywords and identifiers (which is also needed for e.g. FORTRAN). As long as your language is deterministic, it can be expressed as an LR grammar, although legibility might suffer.
Re: Parsing Algorithms
#26FWIW, parsing and lexical analysis was the CS class I have used most thoroughly in my career. Sure data structures is probably the most often used, but other than hash tables and b-trees, not much of that class was useful. But lexing and parsing? Seems like every other project benefited by it either in handling configuration files, or log/sensor data, or some other need to convert what was human readable into machine manipulable.
That said, I really recommend the crafting interpreters work. It covers all the bases pretty solidly. If you want more depth and theory then get the dragon book (Ullman on compiler design) and read it afterwards :-)
Re: Parsing Algorithms
#27Earlier quoted context omitted.
Just generalized parsing algorithms in general would be good to include, I think. It looks like the course only plans to cover basic LL/LR, which are admittedly the most commonly used parsers but more would be interesting. A fun one to include might be Might's "Parsing with Derivatives", which is algorithmically novel (though not very performant). I think there was a recent innovation on this: "Parsing with Zippers"…
Thanks for mentioning "Parsing with Zippers"! I read "Parsing with Derivatives" last week and wondered if that could be taken further. The paper can be found here: https://dl.acm.org/doi/10.1145/3408990
It's always fun to spread new research around the community! I remember reading PwD and thinking it was just so cool as an algorithm, though the performance concerns were a bit of a turn-off. Still, I always like to talk to people about it because I just think it's such an elegant approach to the problem.
As for PwZ, I know one of the authors so maybe I'm a little biased, but I also thought his ICFP talk was quite good. It's here: https://youtu.be/fakSKvP9yaM?t=6180
Re: Parsing Algorithms
#28Earlier quoted context omitted.
What is GRR? Did you mean GLR?
Yep, that was a typo, fixed it
Ah okay. Note that GLR isn't exactly modern (1974). However, I would also remove "modern" as a requirement here... what really matters is how good the algorithm is, not how old it is. "Modern" algorithms easily end up being less powerful than the old ones... they just end up becoming popular due to other factors, e.g. simplicity.
Re: Parsing Algorithms
#29Apologies for the tangential question. I am currently working on a codebase that involves trying to understand code that parses and input string (that has various search parameters and values) and generates an appropriate SQL query to search the associated database. I am struggling to build a mental model of how this parsing works. Will going through one of the resources mentioned in this thread help with my understanding?
Re: Parsing Algorithms
#30For an alternative take on a related topic, this is really a fantastically well-written and practical (free) book: http://craftinginterpreters.com
Yeah, this class is specifically on parsing pipeline and syntactic analysis.
For runtime semantics (Interpreters and Virtual Machines) you can address "Essentials of Interpretation" aka "Building an Interpreter from scratch".