Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

qntm.org

Post reply on HN
Print view View original

21–30 of 45 posts

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

#21

Post by seanmcdirmid »

vorg wrote: post #20

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…

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.

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

#22

Post by phyzome »

slashnull wrote: post #4

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. But while fun it was pretty much useless because recursive descents and combinators are so much easier.

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

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

#23

Post by vorg »

seanmcdirmid wrote: post #21
vorg wrote: post #20

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…

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

Thanks. I've been writing and using recursive descent parsers a little lately, both Parsec-style and Packrat-style. If it's possible to do decent incremental parsing without wrapping my head around LR-parsing, then I'll give it a try sometime.

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

#24

Post by seanmcdirmid »

vorg wrote: post #23
seanmcdirmid wrote: post #21

Earlier quoted context omitted.

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

Thanks. I've been writing and using recursive descent parsers a little lately, both Parsec-style and Packrat-style. If it's possible to do decent incremental parsing without wrapping my head around LR-parsing, then I'll give it a try sometime.

It is actually quite easy if you have a memoized token stream to work on. Just store your trees based on their first token. When you do a parse, check to see if a tree of that type already exists for that token. If it does, just reuse it, and if there is any context to consider, dirty the tree if the context of its creation has changed.

There are more advanced incremental parsing algorithms that do not require memoization, but they really aren't worth it (the ability to parse incrementally is not really a performance concern, but in keeping around state associated with the tree and in doing better error recovery).

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

#26

Post by ternaryoperator »

vorg wrote: post #19
zura wrote: post #8

Earlier quoted context omitted.

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.

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

This is all wrong. Groovy predates Grails, as Grails was written in Groovy. Gosu and Groovy came out at roughly the same time, and IIRC, Groovy had closures and features like the Elvis operator before Gosu did.

You apparently don't like Groovy's current owners, but slamming Groovy for implementing static typing and qualifying them as takers for doing so makes no sense at all.

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

#28

Post by skybrian »

Guthur wrote: post #27

(facetious-comment "It's a tragedy how much brilliance is wasted on grammar parsing when it's a solved problem; just use a Lisp")

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?

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

#29

Post by skybrian »

seanmcdirmid wrote: post #24
vorg wrote: post #23

Earlier quoted context omitted.

Thanks. I've been writing and using recursive descent parsers a little lately, both Parsec-style and Packrat-style. If it's possible to do decent incremental parsing without wrapping my head around LR-parsing, then I'll give it a try sometime.

It is actually quite easy if you have a memoized token stream to work on. Just store your trees based on their first token. When you do a parse, check to see if a tree of that type already exists for that token. If it does, just reuse it, and if there is any context to consider, dirty the tree if the context of its creation has changed. There are more advanced incremental parsing algorithms that do not require memoiz…

Could you expand on this? What's a memoized token stream?

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

#30

Post by kyllo »

skybrian wrote: post #28
Guthur wrote: post #27

(facetious-comment "It's a tragedy how much brilliance is wasted on grammar parsing when it's a solved problem; just use a Lisp")

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?

Yeah, this is why no one likes languages based on XML: http://thedailywtf.com/articles/We-Use-BobX

If you were going to do it, I'm certain you'd want to use a more human-writable format such as YAML or TOML instead of JSON or XML.

But doing so means you're living out Greenspun's Tenth Rule. Again, just use a Lisp. http://www.defmacro.org/ramblings/lisp.html

Post reply on HN