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

Parsing Algorithms

dmitrysoshnikov.com

Post reply on HN
Print view View original

11–20 of 87 posts

Re: Parsing Algorithms

#11

Post by giraj »

DonaldPShimoda wrote: post #5
wtetzner wrote: post #2

Any chance of also including GLL (generalized LL)? I found the paper ( http://dotat.at/tmp/gll.pdf ) quite hard to follow, and haven't been able to find a good explanation anywhere else.

Just generalized parsing algorithms in general would be good to include, I think. It looks like the course only plans to cover basic LL/LR, which are admittedly the most commonly used parsers but more would be interesting. A fun one to include might be Might's "Parsing with Derivatives", which is algorithmically novel (though not very performant). I think there was a recent innovation on this: "Parsing with Zippers"…

Thanks for mentioning "Parsing with Zippers"! I read "Parsing with Derivatives" last week and wondered if that could be taken further. The paper can be found here: https://dl.acm.org/doi/10.1145/3408990

Re: Parsing Algorithms

#13

Post by samatman »

DmitrySoshnikov wrote: post #7
samatman wrote: post #6

Earlier quoted context omitted.

I found the code for Instaparse (relatively) easy to follow. I had considered leaving a comment here like "hey could you cover combinators and PEGs?", but after thinking it over, it's important to limit the scope for a class like this. It would be pretty great to offer a "201" edition, covering ALL*, GLR, GLL, combinators/PEGs, Earley, parsing-with-derivatives, Marpa, and anything else I might have forgotten: basical…

Great point on combinators, PEG, and GLL -- this potentially would be covered in 201 as suggested, since it's good having a foundation of the LL/LR, and then gradually moving to combinators if needed. LALR(1) covers a pretty wide range of the most practical languages.

To a significant degree, the arrow of causality runs LALR(1) -> practical languages, not the other direction!

The languages and formats we use have been heavily shaped by the practical parsing algorithms of the 20th century. An example: you can't have a struct field called "while" in C, because once the lexer declares a token to be a keyword, that's that.

Re: Parsing Algorithms

#14

Post by davidkellis »

I'd like to see something like this for practitioners. I kind of have a feel for what's out there, but I don't know of anything that is: 1. pleasant to use 2. simple 3. scannerless 4. supports left recursion that produces a left-associative parse

Re: Parsing Algorithms

#16

Post by jcranmer »

samatman wrote: post #13
DmitrySoshnikov wrote: post #7

Earlier quoted context omitted.

Great point on combinators, PEG, and GLL -- this potentially would be covered in 201 as suggested, since it's good having a foundation of the LL/LR, and then gradually moving to combinators if needed. LALR(1) covers a pretty wide range of the most practical languages.

To a significant degree, the arrow of causality runs LALR(1) -> practical languages, not the other direction! The languages and formats we use have been heavily shaped by the practical parsing algorithms of the 20th century. An example: you can't have a struct field called "while" in C, because once the lexer declares a token to be a keyword, that's that.

Contextual keywords are a growing thing in modern languages. Modern compilers don't tend to have strictly separated lexers and parsers, but instead use a combined lexer/parser model that feeds information back and forth between them. If your language is designed such that you aren't often in multiple potential parse states, then it's easy to feed into the lexer "get me the next token, and by the way, expect function attributes to be keywords right now."

Note that the requirement to not be in multiple potential parse states also tends to boil down to "build a language that's usually LL(1) or LALR(1)."

Re: Parsing Algorithms

#18

Post by wtetzner »

DmitrySoshnikov wrote: post #10
wtetzner wrote: post #2

Any chance of also including GLL (generalized LL)? I found the paper ( http://dotat.at/tmp/gll.pdf ) quite hard to follow, and haven't been able to find a good explanation anywhere else.

Yes, GLL is a good algorithm and I potentially going to publish it separately as a single public video.

That would be fantastic!

Re: Parsing Algorithms

#19

Post by mehrdadn »

samatman wrote: post #6
wtetzner wrote: post #2

Any chance of also including GLL (generalized LL)? I found the paper ( http://dotat.at/tmp/gll.pdf ) quite hard to follow, and haven't been able to find a good explanation anywhere else.

I found the code for Instaparse (relatively) easy to follow. I had considered leaving a comment here like "hey could you cover combinators and PEGs?", but after thinking it over, it's important to limit the scope for a class like this. It would be pretty great to offer a "201" edition, covering ALL*, GLR, GLL, combinators/PEGs, Earley, parsing-with-derivatives, Marpa, and anything else I might have forgotten: basical…

What is GRR? Did you mean GLR?
Post reply on HN