I really didn't understand grammars until I started doing hand-rolled top-down recursive descent parsing for Gosu.<p>It's a shame that parsing in CS schools is taught using theory and lex/yacc type tools when a basic lexer and recursive descent parser can be written from first principles in a few months. It is more incremental, and it gives you a much deeper feel for the concepts, plus it lets you learn a bit about software engineering and organization as well.
Bottom up parsing - "If not, it's necessary to backtrack and try combining tokens in different ways"
I feel the way it is put along with shift reduce parsing is misleading. Backtracking is essentially an aspect avoided (more like solved) by shift-reduce parsing. They don't go together in bottom up parsing. Shift reduce parsers posses the potential to predict the handle to use by looking at the contents on top of the stack.<p>Good job BTW, there are very few people who write about compiler/language theory :)
I was so happy when I finally grokked LR parsers: it's just a big state machine! _if_ that token found, push on stack, go to _that_ other state. Consume token, check the next state transition.<p>But while fun it was pretty much useless because recursive descents and combinators are so much easier.
Another good write-up on this topic is <a href="http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html?m=1" rel="nofollow">http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demyst...</a>
I think I read somewhere incremental parsers are better off being written with bottomup parsers rather than topdown parsers. The reason was that when a small edit is made to the code being parsed, the artifact from a bottomup parser often only needs a minor change that ripples only as far as it needs to, whereas the topdown parser needs to be completely rerun because it can't tell whether the effect of one small edit is large or localized. Anyone out there who can verify or refute this?