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

31–40 of 45 posts

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

#31

Post by seanmcdirmid »

skybrian wrote: post #29
seanmcdirmid wrote: post #24

Earlier quoted context omitted.

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?

A token stream that preserves token identities. Say you have a token stream of [t0, t1] and add a new token t2 between t0 and t1 to get [t0, t2, t1]. What you want is to be able to identify t0 and t1 in the new stream as being the same tokens as in the old stream. If you simply re-lex to get new tokens, that won't happen, and if you use character offsets as your token identities, t1 in the new and old stream will have different identities.

Incremental lexing is pretty easy: just convert the tokens around the damage back into text, re-lex that text, and then work from front and back of the new partial stream to replace new tokens with old existing tokens if their lexical categories match (e.g. an old identifier's text can be updated with a new identifier's contents, but that is ok because parsing only depends on the fact that the token is an identifier). You might not win any performance awards, but those reused old tokens make very good keys into various data structures for incremental parsing, incremental type checking, and even incremental re-execution (if you are into live programming).

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

#32

Post by userbinator »

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…

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.

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

#33

Post by agumonkey »

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

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.

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

#34

Post by rab_oof »

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.

The subset LALR(1) is pretty simple. Table with states that can shift or reduce, and finally accept or error. It's not too hard to get the dragon book and write an LALR(1) parser for a calculator by hand. Plenty of lectures out there that explain it. If I can write a lexer/parser from scratch after hearing the explanation of LALR(1), anyone can.

LR(k) would be more complicated. Start with the smaller CFG subset and work up to it.

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

#36

Post by vorg »

ternaryoperator wrote: post #26
vorg wrote: post #19

Earlier quoted context omitted.

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…

I've gotten the impression over the years that Grails is written in Java and only bundles Groovy for user scripting, but I haven't checked up recently. I certainly looked through the Gradle codebase when its version 2.0 came out and there was hardly a line of Groovy code in there, only Java. It, too, only uses Groovy for user scripting. If I'm right about the Grails codebase, static-typed Groovy isn't actually used to build any systems of note. Perhaps Cedric Champeau, who wrote the static-typed Groovy codebase, will use it to build the Groovy for Android he's presently working on. It'll be interesting to see whether he uses it or uses Java because it'll show whether he has enough faith in what he built to actually use it to build something with it. Until static-typed Groovy is used to build something, Groovy will remain a dynamically-typed scripting language for testing, Gradle builds, webpages, etc.

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

#37

Post by vorg »

seanmcdirmid wrote: post #31
skybrian wrote: post #29

Earlier quoted context omitted.

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

A token stream that preserves token identities. Say you have a token stream of [t0, t1] and add a new token t2 between t0 and t1 to get [t0, t2, t1]. What you want is to be able to identify t0 and t1 in the new stream as being the same tokens as in the old stream. If you simply re-lex to get new tokens, that won't happen, and if you use character offsets as your token identities, t1 in the new and old stream will hav…

> convert the tokens around the damage back into text, re-lex that text, and then work from front and back of the new partial stream

I haven't tried it and I'm no parsing expert but it seems when a rule is specified "forwards" (i.e. beginning-to-end) then it can be used for lexing (or parsing) forwards but there'd be problems using it to lex (or parse) backwards. Hence the first "L" in "LL" and "LR" parsing.

Maybe an algorithm could use both directions running in parallel and create 2 structures/memoizations, one for the forward parse and one for the backward, hence a dual LL/RL or LR/RR parse, and access both structures to repair "damage". However, there could be another problem: if the lookahead for some lex or parse rule is 1, couldn't that translate to any lookbehind value when lexing or parsing backwards? An LL(1) grammar might require an equivalent RL(k) grammar for some very high k. Of course you'd also need to avoid right recursion as well as left recursion for topdown parsing.

I haven't tried any of this but these are the things that cross my mind whenever I think of incremental parsing!

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

#38

Post by eru »

userbinator wrote: post #32
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…

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

Funny enough, I found the dragon book way too applied and not theoretical enough. Perhaps it was just a different feeling about the same problem: the dragon book is just not very good anymore.

Something like Parsec seems like a good introduction into writing your own parsers. You can figure out formal grammars later.

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

#39

Post by rdc12 »

twic wrote: post #16
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…

That is quite intersting, at one point the main language in AI for Europe was Prolog and in America it was LISP, or so I read. I wonder what other instances this kind of cultural differences occured, and if the internet has had any effect on this.

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

#40

Post by lispm »

rdc12 wrote: post #39
twic wrote: post #16

Earlier quoted context omitted.

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…

That is quite intersting, at one point the main language in AI for Europe was Prolog and in America it was LISP, or so I read. I wonder what other instances this kind of cultural differences occured, and if the internet has had any effect on this.

> AI for Europe was Prolog and in America it was LISP,

I wouldn't say 'main language', but Prolog maybe a little more popular in Europe. The Japanese though based their 'fifth generation' project on logic programming. I once saw a Prolog Machine, a computer with the architecture optimized for Prolog and the main software written in Prolog:

http://museum.ipsj.or.jp/en/computer/other/0009.html

$119000 a piece...

Post reply on HN