The difference between top-down parsing and bottom-up parsing
1–10 of 45 posts
Re: The difference between top-down parsing and bottom-up parsing
#2I really didn't understand grammars until I started doing hand-rolled top-down recursive descent parsing for Gosu.
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.
Re: The difference between top-down parsing and bottom-up parsing
#3I really didn't understand grammars until I started doing hand-rolled top-down recursive descent parsing for Gosu. 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 sof…
[deleted]
Re: The difference between top-down parsing and bottom-up parsing
#4I 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.
But while fun it was pretty much useless because recursive descents and combinators are so much easier.
Re: The difference between top-down parsing and bottom-up parsing
#5Bottom 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.
Good job BTW, there are very few people who write about compiler/language theory :)
Re: The difference between top-down parsing and bottom-up parsing
#6I really didn't understand grammars until I started doing hand-rolled top-down recursive descent parsing for Gosu. 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 sof…
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.
Re: The difference between top-down parsing and bottom-up parsing
#7One more difference: top-down parsing is European and bottom-up - American :)
Re: The difference between top-down parsing and bottom-up parsing
#8I really didn't understand grammars until I started doing hand-rolled top-down recursive descent parsing for Gosu. 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 sof…
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.
Indeed. Also Groovy++ (aka Groovy with static typing) is worth mentioning.
Re: The difference between top-down parsing and bottom-up parsing
#9I really didn't understand grammars until I started doing hand-rolled top-down recursive descent parsing for Gosu. 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 sof…
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.
Yep, them's the breaks...
We are still working on it and it has a long life ahead of it, since it is crucial to many very large, un-sexy companies.
Re: The difference between top-down parsing and bottom-up parsing
#10Bottom 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…
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).