2 ms·
Most of the time when someone talks about "easy recursive-descent parser" it is not even strictly speaking a real recursive descent parser. It is usually some k
by mynegation 16y ago
Most of the time when someone talks about "easy recursive-descent parser" it is not even strictly speaking a real recursive descent parser. It is usually some kind of top-down parser with horrendous tricks thrown in.
Is it easier to write parsers like that? Definitely, I did my fair share of this exercise too. Is it a good thing to do? Not if you want a fast, reliable and maintainable parser. Yes, using LALR(0) (or LALR(k) or whatever) parser generator requires much more effort and disciplined thinking but in exchange you get time and memory constraint guarantees, error reporting and (sometimes) error recovery for free and may be even the tool-chain for subsequent stages (AST, attributed grammars, IR).
So if I see a phrase "let it be a hack" in the text about parsing, there is a good chance that parsers written with this mindset run in exponential time.
I am not saying that "recursive-descent" or any other ad hoc approach is bad. Sometimes you do have to resort to various hacks. Even original C is not, strictly speaking, a context-free language: parser has to consult a symbol table to recognize identifier class to parse source code properly. C++ (which is a textbook example of how NOT to design programming languages) made things 100x worse. But, for obvious reasons, you still need to parse those languages. So, at some point gcc developers just rewrote C++ frontend from scratch using recursive descent techniques, because it is so much easier to intervene and introduce hacks in this framework than in the rules for LALR parser generator like yacc or bison.
TL;DR version of my response: use recursive descent if you have to, but using it for everything is just a demonstration of ignorance and may significantly hurt performance and maintainability.
- Rusky 16y agoI would actually say recursive descent is better for more complicated projects. Good error reporting in something like Bison is difficult, and that style of parser is also not necessarily any faster. IIRC, GCC uses recursive descent for (at least partially) those reasons. However, parser combinators make things even better. You get a program that looks like a grammar, just like with a parser generator, but error reporting is much easier and because you're really writing everything in the full programming language you can be much more expressive.