The difference between top-down parsing and bottom-up parsing • Hacker News Board

Re: The difference between top-down parsing and bottom-up parsing

#11

Post by canjobear » Sun, Jan 04, 2015, 8:00 PM UTC

nachivpn wrote: post #5

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…

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.

Re: The difference between top-down parsing and bottom-up parsing

#12

Post by nachivpn » Sun, Jan 04, 2015, 8:04 PM UTC

canjobear wrote: post #11

nachivpn wrote: post #5

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…

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.

I totally agree with this. I was assuming the case of a default behavior like shift or reduce force fully for unambiguous grammars, which I should have mentioned. Thanks.

Re: The difference between top-down parsing and bottom-up parsing

#13

Post by nachivpn » Sun, Jan 04, 2015, 8:06 PM UTC

psykotic wrote: post #10

nachivpn wrote: post #5

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…

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).

Like in my other comment, I agree with this. I missed mentioning mentioning my assumption of a forceful shift or reduce action in case of an ambiguous grammar.

Re: The difference between top-down parsing and bottom-up parsing

#14

Post by psykotic » Sun, Jan 04, 2015, 8:10 PM UTC

nachivpn wrote: post #13

psykotic wrote: post #10

Earlier quoted context omitted.

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).

Like in my other comment, I agree with this. I missed mentioning mentioning my assumption of a forceful shift or reduce action in case of an ambiguous grammar.

Not a fan of handling it that way. Shift-reduce conflicts don't correspond to people's intuitive understanding of the grammar because good shift-reduce parser tables are highly non-local as they're constructed from fixed-point dataflow iteration over the whole grammar. It's not like top-down parsing where it's easy to understand the compromise of making a non-backtrackable decision based on k-token lookahead. If you force them to manually resolve shift-reduce conflicts in the grammar, it's likely they will be surprised by what happens, and not in a good way.

Re: The difference between top-down parsing and bottom-up parsing

#15

Post by nachivpn » Sun, Jan 04, 2015, 8:20 PM UTC

psykotic wrote: post #14

nachivpn wrote: post #13

Earlier quoted context omitted.

Like in my other comment, I agree with this. I missed mentioning mentioning my assumption of a forceful shift or reduce action in case of an ambiguous grammar.

Not a fan of handling it that way. Shift-reduce conflicts don't correspond to people's intuitive understanding of the grammar because good shift-reduce parser tables are highly non-local as they're constructed from fixed-point dataflow iteration over the whole grammar. It's not like top-down parsing where it's easy to understand the compromise of making a non-backtrackable decision based on k-token lookahead. If you…

Yes, it definitely isn't the right way to handle ambiguous grammars. My assumption was caused by extensive usage of YACC for writing parsers in the past. To avoid it's default action, generally ambiguous grammars are avoided (since it is used only to write programming language parsers anyway)

Re: The difference between top-down parsing and bottom-up parsing

#16

Post by twic » Sun, Jan 04, 2015, 8:38 PM UTC

zura wrote: post #7

One more difference: top-down parsing is European and bottom-up - American :)

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...

Re: The difference between top-down parsing and bottom-up parsing

#17

Post by aardvark179 » Sun, Jan 04, 2015, 9:06 PM UTC

canjobear wrote: post #11

nachivpn wrote: post #5

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…

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.

Actually, many languages which started with hand written parsers do have ambiguous grammars, or have an unambiguous grammar so hideously unwieldy it is best ignored.

This sort of thing can be fixed up with predicates added to the grammar but it always feels like a bodge.

Re: The difference between top-down parsing and bottom-up parsing

#18

Post by meow_mix » Sun, Jan 04, 2015, 9:43 PM UTC

carsongross wrote: post #2

I 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…

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.

Re: The difference between top-down parsing and bottom-up parsing

#19

Post by vorg » Sun, Jan 04, 2015, 9:45 PM UTC

zura wrote: post #8

ternaryoperator wrote: post #6

Earlier quoted context omitted.

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.

Or even Beanshell. In fact, the ideas behind Beanshell (i.e. closures on the JVM) and Groovy++ (i.e. static typing) were scooped up and copied into Groovy, that kitchen sink language, which was bundled as part of Grails, that knock-off of Rails for the JVM.

The software industry is divided into "Makers" and "Takers". The people behind Gosu are obviously Makers, whereas those presently behind Groovy are Takers.

Re: The difference between top-down parsing and bottom-up parsing

#20

Post by vorg » Sun, Jan 04, 2015, 9:56 PM UTC

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?