Parsing: the solved problem that isn't
I agree completely with the premise, which is that Parsing looks like a solved problem but really isn't.<p>One thing that should be a red flag is that lots of people still write parsers manually instead of using tools.  GCC migrated <i>from</i> a yacc/bison-based parser <i>to</i> 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.<p>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!<p>(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.)<p>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++.  <i>That's</i> what we should be spending CPU cycles on IMO.<p>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.<p>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.<p><a href="http://www.reverberate.org/gazelle/" rel="nofollow">http://www.reverberate.org/gazelle/</a>
<a href="https://github.com/haberman/upb/wiki" rel="nofollow">https://github.com/haberman/upb/wiki</a>