I don't mind paying for quality content (and I mind paying in cash a lot less than paying with personal data), but if someone wants a free alternative to this, I recommend https://craftinginterpreters.com/ . Bit lighter on the theory side, but exactly what you need if you want to write a parser in practice.
Parsing Algorithms
71–80 of 87 posts
Re: Parsing Algorithms
#72Funny, I used to dig into everything about parsing that I could get my grubby fingers on, and now I don't even care anymore.
Use recursive descent + TDOP for expressions!
Re: Parsing Algorithms
#73For an alternative take on a related topic, this is really a fantastically well-written and practical (free) book: http://craftinginterpreters.com
I a big fan of the way Bob Nystrom skips the LR and LL theory and goes straight to recursive descent parsing plus the precedence-climbing trick. I'm of the opinion that if you have to learn ONE thing about parsing then it should be how to write a recursive descent parser by hand. It is the parsing technique that you are most likely to use in a real project if someone throws a parsing hot potato in your direction. Tha…
Absolutely with you on recursive descent!
And looking back, from a purely practical perspective, I think the second thing should be TDOP/Pratt parsing. When your RD-parser hits an expression, simply call the TDOP subroutine and let that sort it out. It's just a beautiful (and fast) combination!
Re: Parsing Algorithms
#74Funny, I used to dig into everything about parsing that I could get my grubby fingers on, and now I don't even care anymore. Use recursive descent + TDOP for expressions!
TDOP / Pratt parsing is basically the same as recursive descent, it's just an optimization where rules with the same or lower precedence are matched iteratively rather than recursively.
I can't find the link now but I found a great page once where this was shown, and it made all the complexity vanish for me.
Re: Parsing Algorithms
#75Funny, I used to dig into everything about parsing that I could get my grubby fingers on, and now I don't even care anymore. Use recursive descent + TDOP for expressions!
TDOP / Pratt parsing is basically the same as recursive descent, it's just an optimization where rules with the same or lower precedence are matched iteratively rather than recursively. I can't find the link now but I found a great page once where this was shown, and it made all the complexity vanish for me.
Yeah, the advantage here is that once you wrote your Pratt parser it's a nice, quite generic piece of code that you can just drop into any new project, reconfigure a bit and it does it's job.
Don't know what page you mean, but personally I first stumbled upon it on Douglas Crockford's page [1]. A couple of years later Eli Bendersky did a nice writeup for Python [2].
I wrote my first Pratt parser in D, based on Crockford's. It was a learning project that ended up as a Javascript interpreter. I parsed JS into a Lispy syntax tree and added a simple Lisp interpreter based on Norvig's [3].
In the meantime I've switched my default language (to Nim [4]), but I've since never used anything but RD and/or Pratt for any parsing job.
[1] https://crockford.com/javascript/tdop/tdop.html
[2] https://eli.thegreenplace.net/2010/01/02/top-down-operator-p...
Re: Parsing Algorithms
#76Earlier quoted context omitted.
TDOP / Pratt parsing is basically the same as recursive descent, it's just an optimization where rules with the same or lower precedence are matched iteratively rather than recursively. I can't find the link now but I found a great page once where this was shown, and it made all the complexity vanish for me.
Yeah, the advantage here is that once you wrote your Pratt parser it's a nice, quite generic piece of code that you can just drop into any new project, reconfigure a bit and it does it's job. Don't know what page you mean, but personally I first stumbled upon it on Douglas Crockford's page [1]. A couple of years later Eli Bendersky did a nice writeup for Python [2]. I wrote my first Pratt parser in D, based on Crockf…
I found it : https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#more_clim...
It shows the transformations that get you from recursive descent to table driven precedence climbing
Pratt/TDOP and precedence climbing are actually the same algorithm: https://www.oilshell.org/blog/2016/11/01.html
...so basically everything can be derived from simple, straightforward predictive recursive descent.
Re: Parsing Algorithms
#77Does anyone know if there are any good resources on "tolerant parsing," if that is the correct terminology? For example, when I write C# in Visual Studio, the IDE remains amazingly helpful even when the code is incomplete and would be rejected by a traditional parser. I'd guess that Microsoft simply has the budget to have the VS/C# dev teams grind out hundreds or thousands of special cases that are specific to C#...…
It's fairly straightforward to offer some functionality in this area with hand-written recursive descent parsers. For example, a language with a C-like syntax, you'll often be parsing a sequence of statements separated by semi-colons (a block). If a statement fails to parse, you can just consume tokens until you hit the next semi-colon and then try to continue to parse statements from there. Fairly crude approaches l…
You can probably make your heuristic even more robust, by looking at hints from indentation and parens and braces in addition to just semicolons.
Re: Parsing Algorithms
#78Any chance of also including GLL (generalized LL)? I found the paper ( http://dotat.at/tmp/gll.pdf ) quite hard to follow, and haven't been able to find a good explanation anywhere else.
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"…
Parsing with derivatives has been around for a long time, at least for regular languages.
Re: Parsing Algorithms
#79This course follows the traditional approach to writing parsers. These traditional approaches were developed in times when memory was scarce and where back-tracking was impossible, simply because files were too large to be stored in RAM. Back-tracking parsers are much easier to write and in most cases performance can be brought to acceptable levels by applying caching. I have experimented with developing interpreting…
Yes, backtracking still might be an option although has its known limitations in terms of parallel paths. We describe backtracking in this class too.
The LL in the the view of manual Recursive descent is the most used on practice along with combinators and LALR(1).
Re: Parsing Algorithms
#80Seems the place to ask: what do folks make of the IELR algorithm? [0] Apparently GNU Bison supports it these days. [1] [0] https://cs.stackexchange.com/a/99463/ [1] https://en.wikipedia.org/wiki/GNU_Bison
I think its great. IELR is a straightforward optimization that just makes sense to use when building an LR family parser.
You can think of LALR(1) as just taking an LR(1) state graph and merging together nodes that are compatible (in that they are essentially the same parsing state, but differ in which "lookahead" tokens are valid). A grammar is consider to be LALR(1) if combining states in this way still results in a correct parser.
IELR, which is derived from David Pager's PGM and Lane Tracing "Minimal LR" techniques from the 1970s, applies a stricter compatibility test for nodes. This check usually allows a large majority of merges while rejecting the ones that will lead to parsing errors. In this way, a more sophisticated grammar, all the way up to LR(1) can still be processed correctly using a table size much closer to what you get with LALR.
You essentially get the best of both worlds and its tragic that this fairly simple technique is so obscure. I believe the reason for the obscurity of these techniques is that Pager's PGM and lane tracing papers are extremely terse, somewhat confusing, and lacking in sufficient detail in certain areas. For example, the PGM paper on p.256 crucially notes that successors may need to be "regenerated as a distinct state" without further explanation. (Until his protege Chen provided some pseudo-code 34 years later in his dissertation of 2009. BTW, I have verified that the Wisent and Menhir parsers and others implement PGM correctly, if anyone is looking for actual details.)
Note that there is some additional time and complexity required to detect conflicts and regenerate/split nodes and so the benefits or IELR are not entirely free.
More obscurely, it should be noted that IELR suffers the same problem as LALR in that combining states can introduce conflicts between tokens when context aware lexing [Nawrocki 1991] is being utilized. (BTW, Tree Sitter uses context aware lexing but its not very common otherwise - yacc/bison doesn't AFAIK). Suddenly tokens are eligible for matching alongside other tokens that normally would not be matched together. Unless your tokens are globally conflict-free or you've got a priority scheme that always resolves conflicts properly (but then you wouldn't need context-aware-lexing would you?), you'll start matching tokens that shouldn't be matched in a particular parsing state. There are ways to avoid those conflics as well (see PSLR - also from IELR author Joel Denny) but it is a lot more work. Even if you avoid conflicts, invalid content can match tokens that shouldn't be matched which complicates error reporting because you get a confusing parse error instead of a correct tokenization error. So this is one case where the full LR(1) may be preferred over IELR.
But I can't think of a convincing argument for preferring LALR over IELR.