 |
| “I agree completely with the premise, which is that Parsing looks like a solved problem but really isn't.” (comment) | ||
| recommended by 1 user | 2011 | haberman on: Parsing: the solved problem that isn't | aged well | compilers | original thread | | ||
| haberman on Mar 15, 2011 | on: Parsing: the solved problem that isn't | view on HN | ||
| One user recommended this comment. What they said: |
|
samhw Jan 29, 2022 | on: Magic-trace: Diagnose tricky performance issues with Intel… | context | aged well
Hey - I wanted to say that I came across a comment of yours from more than a decade ago (https://news.ycombinator.com/item?id=2328627), and I was startled at how accurate it is as a prediction of how parsers and IDEs are combined today, about 11 years later. I'm glad you're still commenting on here (and what a criminal understatement it is for that page to characterise their tool's flaws as "timing information is less accurate" - that's bloody execution order that you're talking about!). Anyway, I wanted to say how much I appreciate your comment of 10 years ago. I'm also a parser nerd, and a performance nerd, and I feel strongly that programmers have a professional responsibility to write code in a way that expresses our intent by a logical minimum of instructions/work. I strongly suspect that this will become important again in the future, not because the ratio of software-efficiency to hardware-power decreases again, but because climate concerns will drive us to measure our code in performance-per-watt rather than performance-per-dollar (depending on what action is taken on carbon pricing, it may be a distinction without a difference). I look forward to the day when grossly inefficient software is rightly considered to be as unacceptable as grossly inefficient SUVs, and people in our profession are forced to take responsibility for the damage that their obscenely inefficient crap is doing. I hope Python 4 comes with a snorkel. |
I agree completely with the premise, which is that Parsing looks like a solved problem but really isn't.
One thing that should be a red flag is that lots of people still write parsers manually instead of using tools. GCC migrated from a yacc/bison-based parser to a hand-written recursive descent parser. I used to work in the same office as Bob Jervis who wrote Turbo C back in the day, and he said he never uses parser generators. Clearly something is wrong if the tools that have all the weight of the theory and formalisms are losing to coding parsers by hand.
I disagree that because computers are so much faster we should use less-efficient parsing algorithms that can handle all grammars (like Earley, GLR, etc). One reason I disagree is the ambiguity problem given in the article. The very process of building parse tables for a more restricted language subset like LL, LR, etc. can tell you that a grammar is not ambiguous, which is hugely beneficial. If you do not restrict yourself to such a subset, you never know whether your grammar has ambiguities or not. To me, this would be like programming in a language that doesn't give you syntax errors when you make a mistake. Sure, the syntax errors are annoying, but they are your only way of knowing you need to fix something!
(By the way, PEGs have the same issue -- by using prioritized choice, you never know when you're covering up an ambiguity. An example of this is C's famous "if/else" ambiguity. It's important to know that this ambiguity exists, because you have to tell your users about it.)
Instead of using our extra CPU power to parse with less efficient algorithms, I think we should use our extra CPU power to integrate parsing more deeply into our editors/IDEs. With a fast parsing algorithm, you could parse as a programmer types, unlike the current syntax highlighting editors which use only rough pattern matching instead of having a real parse tree. Imagine seeing syntax errors the moment you type them. Imagine having your cursor inside a struct and having a little "inspector" pane off to the side that says "sizeof(struct MyStruct) = 96". Imagine getting real, context-sensitive completion even for complex languages like C++. That's what we should be spending CPU cycles on IMO.
The biggest thing that could be improved about parsing IMO is for grammars to be reusable. There is no reason that people should have to roll their own parser for a common language. There's no way you're going to get all the edge cases right unless you spend a LOT of time on it, but why should you have to do that? IMO there should be a "grammar library" the same way that platforms like the JVM or .NET have a "class library." You should be able to take a C++ parser off-the-shelf and use it in your program, thereby saving yourself literally man-years of work.
I've been working for a long time on a project that seeks to achieve this goal. It's tabled right now because of my work on a protocol buffer implementation (the two will be related in a deep way; protocol buffers are an ideal way of specifying parse trees, which are the output of a parser), but I am extremely motivated to return to it.
http://www.reverberate.org/gazelle/ https://github.com/haberman/upb/wiki