Out of curiosity, where would one find an explanation (potentially dry, long, and complicated) of the algos you mention here?
In other words - how did you get to know them?
In other words - how did you get to know them?
Build a parse tree in a recursive descent parser, and you'll notice that you build it from the top down - even if you actually construct from the bottom up, the stack frames that construct the parent nodes are already on the stack when the bottom is constructed.
Once you understand LL, LR can be explained by looking at it the other way around: building the parse tree from the bottom up without any higher-up context. Simply states and transitions based on the token stream. The details of state machine is generally best left to a parser generator though, unless you want to write your own.
Once you understand the idea of LR, GLR is easy to understand: instead of a single tree, GLR parses a forest of trees, which it can thin out as it eliminates possibilities with more context. This gives GLR parsing a lot of power, at the cost of higher algorithmic complexity (how bad depends on the grammar).
And so on. The details of other algorithm variants can mostly be understood in relation to these core approaches.
This will indeed tell you how top-down parsers work. But this doesn't tell you very much about LL specifically.
The trickiest part of parsing is deciding what path to take. When you hand-write a recursive descent parser, your code for deciding between alternatives is ad hoc. For example if you are parsing JSON you'll have some code that looks like this:
if next_token == "{":
parse_object()
elif next_token == '[':
parse_array()
elif next_token == 'null':
parse_null()
elif next_token == 'true' or next_token == 'false':
parse_boolean()
elif next_token == '"':
parse_string()
else:
parse_number()
Almost all of the "secret sauce" in LL, LR, etc. is how to construct these tables of if/then in a way that is rigorous and provably correct.
It's true that understanding generally how top-down and bottom-up parsers work is a great step towards understanding parsers.
You'll quickly learn there's a mechanical transformation from LL(1) grammars to recursive descent. And if you write a recursive descent parser with one token of lookahead, no backtracking, and straightforward syntax actions, it has a mechanical translation into LL(1).
Anyway, I described the journey I went through learning compiler theory before I went to college. I covered undergrad compiler course content long before I left secondary school, and understood it at a much deeper level. I got a job at Borland working on the Delphi compiler (6 years I put in) on the back of the same knowledge. It worked for me.
How did you like working on Delphi? I wish I had been studying this stuff that early!
More generally I learned how to tackle very complex problems under my own steam, even more so than I had as an autodidact. I have no difficulty drilling down to the next level, all the way to the CPU if necessary, if I have a problem, even if I'm starting out at the level of an interpreted language. I currently work on a web app written in Rails / Coffeescript combo; but I can debug MRI if we get an Ruby issue, and I can and have debugged MySQL when we had crashing issues.
Here is my Amazon review of the book: https://www.amazon.com/gp/customer-reviews/R17E19PSPM2UO9
> In other words - how did you get to know them?
My book recommendation: Dick Grune, Ceriel J.H. Jacobs - Parsing Techniques: A Practical Guide (Second Edition). Many people will also recommend the "dragon book" (Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman - Compilers: Principles, Techniques, and Tools (Second edition)), which is not a bad book.
If you want to dive deeply into parsing and want to read about all the details over hundreds of pages, the Grune-Jacobs book is clearly the recommdendation. On the other hand, if you just want to understand the theory behind the parsing stage of a compiler (as one part of a compiler - and there are lots of other parts, too), you will probably prefer the dragon book.