The difference between top-down parsing and bottom-up parsing (opens in new tab)

Parsing and compilers are an area where I think "the theory gets in the way"; I started by reading the Dragon Book, and while I (vaguely) understood what it was talking about, the feeling it gave was "parsers are complex, use a parser generator instead"... which sounds like a good idea until you actually try to debug one. I eventually realised that recursive descent was much simpler, and with things like the "Let's Build a Compiler" articles everything became so clear and it felt like all that theory I learned before was mostly useless. I think the fact that top-down parsers are theoretically less powerful doesn't make much difference in practice; and the trend of compilers (in C at least) now seems to be to move away from generated parsers and to recursive descent.

Big, "production quality" compilers like GCC and LLVM use RD, and so do small ones like (o)tcc and various others' "toy compiler" projects (e.g. https://news.ycombinator.com/item?id=8558822 and https://news.ycombinator.com/item?id=8576068) The "precedence climbing" method (http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm ), which simplifies and makes RD more efficient, is common too but I don't think I've seen it appear in any of the usual academic texts.

It is a shame that Gosu has not become more popular as a JVM language. You guys were doing things that took other languages years to catch up.

I'm a sophomore at Ohio State and context free grammars are actually a major topic in one of our early software courses. We also got to write a recursive decent parser for a very simple made up language as one of our projects. Really exciting curriculum over here.

For unrestricted CFG parsing, shift-reduce parsing does require backtracking. A modern parsing algorithm like GLR uses LR tables but has to resort to backtracking when it encounters shift-reduce conflicts (it avoids the exponential blow-up of backtracking by using dynamic programming to share results for subproblems).

You need backtracking if you have an ambiguous grammar. This comes up in natural language parsing; I'd guess that it is avoided in programming languages.

This was advocated by https://cs.brown.edu/courses/cs173/2012/lang/ too. Parsing is fun but in the end I can't disagree, syntax is rarely that much worth it.

JSON or XML would also work. Except that few people like languages based on XML, and I haven't seen anyone seriously try JSON.

Perhaps someone should try to build a JSON-like language that's close to how most programmers like to write their code?

Then again, this is just moving the burden from the language implementation to the developer.

I'm not sure why this was downvoted - it's true(ish), and interesting. Historically, American computer scientists preferred LR parsers, and Europeans preferred LL parsers. That influenced the languages they designed.

I think i read about this in Sedgewick's 'Algorithms in C', although i could be wrong. I struggle to find any online citation. This was mentioned in the Wikipedia article at one point, but disppeared in edit described as "Removed heresay":

http://en.wikipedia.org/w/index.php?title=LL_parser&directio...

I've written parsers both as top down and bottom up. Nite that neither is naturally incremental and some memoization is required, so for bottom up, you see if the parent you want to create already exists, for top down, your child. It is sort of a wash which one is better, but both are pretty trivial.

I use top down recursive descent these days backed up with memoization. When a change to the token stream comes, you simply damage the most inner tree that contains the token, or if on a boundary, damage multiple trees.

That moment when you finally get it that CFG parsers can be implemented using push-down automata... :-)

If the language is simple enough to be parsed with only regular expressions, then the language does not have context-free grammar, so bottom-up/top-down distinction does not apply. This also means that the language cannot have recursive productions, e.g. cannot support expressions.

But it depends on how the list of regexes is used. If it is used as part of a recursive paring routine, then it is a recursive-descent parser where lexing and parsing happens in the same pass.