Parsing: The Solved Problem That Isn't (2011)
1–10 of 90 posts
Re: Parsing: The Solved Problem That Isn't (2011)
#2Have there been any notable innovations in parsing since this was written?
Re: Parsing: The Solved Problem That Isn't (2011)
#3My current view of what makes parsing so difficult is that people want to jump straight over a ton of intermediate things from parsing to execution. That is, we often know what we want to happen at the end. And we know what we are given. It is hoped that it is a trivially mechanical problem to go from one to the other.
But this ignores all sorts of other steps you can take. Targeting multiple execution environments is an obvious step. Optimization is another. Trivial local optimizations like shifts over multiplications by 2 and fusing operations to take advantage of the machine that is executing it. Less trivial full program optimizations that can propagate constants across source files.
And preemptive execution is a huge consideration, of course. Very little code runs in a way that can't be interrupted for some other code to run in the meantime. To the point that we don't even think of what this implies anymore. Despite accumulators being a very basic execution unit on most every computer. (Though, I think I'm thankful that reentrancy is the norm nowadays in functions.)
Re: Parsing: The Solved Problem That Isn't (2011)
#4Have there been any notable innovations in parsing since this was written?
An extremely layman answer is that most interesting innovation in parsing in relatively modern times has happened seems to be in the context of IDE's. I.e. incremental, high-performance parsing to support syntax highlighting, refactoring, etc. etc.
(I may be talking out of my ass here.)
Re: Parsing: The Solved Problem That Isn't (2011)
#5There was an interesting discussion two years ago regarding nonobvious issues with PEGs:
https://news.ycombinator.com/item?id=30414683
https://news.ycombinator.com/item?id=30414879
I spent a year or two working with PEGs, and ran into similar issues multiple times. Adding a new production could totally screw up seemingly unrelated parses that worked fine before.
As the author points out, Earley parsing with some disambiguation rules (production precedence, etc.) has been much less finicky/annoying to work with. It's also reasonably fast for small parses even with a dumb implementation. Would suggest for prototyping/settings when runtime ambiguity is not a showstopper, despite the remaining issues described in the article re: having a separate lexer.
Re: Parsing: The Solved Problem That Isn't (2011)
#6Have there been any notable innovations in parsing since this was written?
These are not new, but my takeaways from https://tratt.net/laurie/blog/2020/which_parsing_approach.ht... and https://rust-analyzer.github.io/blog/2020/09/16/challeging-L... are to embrace various forms of LR parsing. https://github.com/igordejanovic/parglare is a very capable GLR parser, and I've been keeping a close eye on it for use in my projects.
Re: Parsing: The Solved Problem That Isn't (2011)
#7My current view of what makes parsing so difficult is that people want to jump straight over a ton of intermediate things from parsing to execution. That is, we often know what we want to happen at the end. And we know what we are given. It is hoped that it is a trivially mechanical problem to go from one to the other. But this ignores all sorts of other steps you can take. Targeting multiple execution environments i…
What have those other things got to do with parsing though? Granted, they rely on parsing having already happened, but I don't see how there's much feedback from those considerations to the way that parsers work, or are written, or - as the article discussed - can be combined?
Re: Parsing: The Solved Problem That Isn't (2011)
#8Have there been any notable innovations in parsing since this was written?
Yes. You roll your own manual parser. It's not as difficult as people make it out to be.
Re: Parsing: The Solved Problem That Isn't (2011)
#9What I find annoying about using parser generators is that it always feels messy integrating the resulting parser into your application. So you write a file that contains the grammar and generate a parser out of that. Now you build it into your app and call into it to parse some input file, but that ends up giving you some poorly typed AST that is cluttered/hard to work with.
Certain parser generators make life easier by supporting actions on parser/lexer rules. This is great and all, but it has the downside that the grammar you provide is no longer reusable. There's no way for others to import that grammar and provide custom actions for them.
I don't know. In my opinion parsing theory is already solved. Whether it's PEG, LL, LR, LALR, whatever. One of those is certainly good enough for the kind of data you're trying to parse. I think the biggest annoyance is the tooling.
Re: Parsing: The Solved Problem That Isn't (2011)
#10Have there been any notable innovations in parsing since this was written?
Aycock & Horspool came up with a 'practical' method for implementing Earley parsing (conversion to a state-machine) that has pretty humorously good performance delta over "naive" Earley, and is still reasonable to implement. Joop Leo figured out how to get the worst-case of Earley parsing down to either O(n) (left-recursive, non-ambiguous) or O(n^2) (right-recursive, non-ambiguous). That means the Earley algorithm is only O(n^3) on right-recursive, ambiguous grammars; and, if you're doing that, you're holding your language wrong.
A somewhat breathless description of all of this is in the Marpa parser documentation:
https://jeffreykegler.github.io/Marpa-web-site/
https://loup-vaillant.fr/tutorials/earley-parsing/