Hacker News Reader

Comment by seanmcdirmid | Hacker News Reader

Hand-written recursive descent isn't that bad: it isn't that hard to implement, it gives you lots of control over error recovery, you don't have to worry about how ambiguity is handled (well, you deal with it on your own), and you don't have to worry about interfacing with the rest of your compiler/interpreter pipeline. The tradeoff is that you write some more code and parser performance is less optimized. Considering everything else that happens in a modern compiler, parser performance is in the noise anyways.

There are good reasons why most production languages are implemented with hand written parsers. Generators are a bit of a convenience, but come with too many drawbacks.

View on HN

The tradeoff is that you write some more code and parser performance is less optimized.

Performance improved when GCC switched from a generated to a handwritten parser. Additional techniques like using an operator precedence table/"precedence climbing" as described in the article can reduce the amount of code, make extending it easier, and you still don't have to learn the specific language of a parser generator nor attempt to debug what it's generated.

IMHO parser generators and parsing algorithms in general seem to have gotten a bit to heavy on the academic theory side of things while ignoring practical considerations, which is why recursive descent + precedence climbing became so popular. Big production-quality compilers use it, little toy ones use it, I don't see any drawbacks other than maybe a misguided attempt at academic purity or dogmatism.

Also, a recursive descent parser is created by modifying the language specification and so I think one gets a deeper understanding of what language spec "means" than if you just feed a spec into a parser generator - a grammar's ambiguity can become in the process, for example.

My experience is different. I've converted two or three grammars from recursive descent to LR recently. In each case, the recursive descent authors have made surprising mistakes, resolving ambiguities in ways that violate the intended spec. This isn't surprising: you can't, in general, know when you're resolving ambiguities in a recursive descent parser, so mistakes are almost inevitable.

Yeah, recursive descent is just the best. I've played with a lot of options, wrote my own parser combinator and packrat libraries and a Pratt parser. By now what I have settled on is recursive descent until I reach an expression, then switch to a Pratt parser. For me, that's the best overall tradeoff that I've found.

In absence of heavy compiler optimizations, parsing consumes about 50% of the compilation time for simple C-style languages. Source: my own experiments. Seems to agree with http://doc.cat-v.org/bell_labs/pikestyle (see last section), but note that text was written in 1989.

That's maybe true for simple C-style languages but very likely not near true for modern statically typed languages that freely allow forward declarations and have type inference.

"freely allow forward declarations" - not sure what you mean. In any case forward declarations were only ever a performance hack for single-pass compilers. Nowadays most compilers are multi-pass and have a separate symbol resolution stage that operates on an in-memory representation of the code (e.g. AST). It's not a huge extra cost to search for symbols "in both directions".

Regarding type inference, it depends on the complexity of the inference algorithm. Personally I think the right way for procedural languages is to require explicit function signatures. Only for functional languages where you have many more (smaller) functions, that is a deal breaker.

> Nowadays most compilers are multi-pass and have a separate symbol resolution stage that operates on an in-memory representation of the code (e.g. AST). It's not a huge extra cost to search for symbols "in both directions".

That's true, but treating all top-level declarations as occupying the same unordered namespace means that a change in any module can require a large amount of non-local recompilation, which makes incrementality more difficult.

> Personally I think the right way for procedural languages is to require explicit function signatures.

Even then, you still spend a lot of time doing inference inside the bodies of functions. Once you mix in inferring parameter types for lambdas, inferring generic type arguments, overload resolution, and maybe implicit conversions, there is a lot going on.

In my experience, source problems like parsing and linking are still the major costs in compiler performance. I love this article by Walter Bright on the subject: http://www.drdobbs.com/cpp/c-compilation-speed/228701711

C++ is slow for many reasons, being really hard to parse is just one of them.

Languages with recursive descent parsers are bound to have simpler syntaxes; eg many (though definitely not all) avoid ambiguity like using < and > as both operators and braces.

Reply on news.ycombinator.com