4 ms·
Recursive descent parsing was probably the first “real” algorithm that I learned (in the 1980s). Like most of these, I’ve never actually seen one “in the wild,
by ChrisMarshallNY 5y ago
Recursive descent parsing was probably the first “real” algorithm that I learned (in the 1980s).
Like most of these, I’ve never actually seen one “in the wild,” but it was a great example of the power of recursion.
- tempodox 5y agoI found it in the wild, in the source code of the (1980s) Unix `expr` command. I used it in my own parsers for a while, before getting started with yacc/bison. It was only many years later that I learned the technique is called “recursive descent parsing” :)
- CipherThrowaway 5y agoWhat do you mean by "in the wild"? I would have thought it was the opposite. Handwritten recursive descent is the way to build a parser if most compiler projects are to go by. OpenJDK, GCC, Clang, Rust, Spidermonkey are examples. Occasionally you see a generated lexer but generated parsers seem to be a rarity in practice while recursive descent is ubiquitous.
- ChrisMarshallNY 5y agoIn my case, I have not had occasion to write compilers and parsers. I've used parsers that others have written, frequently. But, like I said, the idea behind it was quite useful, to me. I use recursion all the time, and RDPs are a pretty "pure" form of recursion.
- CipherThrowaway 5y agoYes I agree. There is something quite elegant and fundamental about recursive descent parsing.
- eatonphil 5y agoMost SQL systems (postgres, mysql, sqlite) use generated parsers but yeah other than that handwritten is the norm. Is there a reason for that? None that I can think of. SQL systems tend to have worse error messages but I don't believe parser generators require error messages to be as bad as SQL error messages (I'm talking about how they often don't give line number or column number info). So my guess (and it sounds kind of absurd to say) is that most SQL systems just don't put much thought into parsing. And not that parser generators fit the domain better.
- eru 5y agoFor quickly writing a parser that doesn't necessarily have to have the highest performance, parser generator libraries are another neat possibility beyond rolling your own parser from scratch or using a generator.
- zabzonk 5y ago> I’ve never actually seen one “in the wild,” The original C++ compiler was (after horrible experiences with YACC, or similar) writen mostly as a recursive descent compiler. https://www.stroustrup.com/dne.html https://www.stroustrup.com/dne.html
- ChrisMarshallNY 5y agoI used a poor choice of words. I should have said "I have never needed to write one in the wild."
- duped 5y agoI've written a couple this year, and at least one last year. So it really depends on what you're doing.
- ChrisMarshallNY 5y agoYup. Also, recursion can be very bad for parallel stuff, if not done carefully. We used to have to do a lot of optimization, in my old job, involving use of GPUs, ISPs, multi-thread, etc. In that kind of environment, things can get quite crazy, and seemingly innocuous stuff, can have huge knock-on effects. For example, cache hits. If you want your code to stay in a shallow cache (which could result in 100X improvement in speed), you may do things like write something over and over, inline, instead of calling a method or subroutine.
- eatonphil 5y agoParsing in the context of databases and compilers is almost assuredly not the bottleneck.