Parsing Algorithms

This is great! I'm working on designing a language right now and I'm just getting to the point where I have to parse the AST. Looking forward to taking this course, I just purchased it on Udemy.

Re: Parsing Algorithms

#5

Post by DonaldPShimoda » Mon, Oct 26, 2020, 6:18 PM UTC

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" at ICFP this year.

Hard agree that GLL is hard to follow. I've read the paper a number of times and struggle with it every time haha.

Re: Parsing Algorithms

#6

Post by samatman » Mon, Oct 26, 2020, 6:20 PM UTC

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: basically a survey of modern parsing algorithms, which frankly, LR and LL are not.

But for your own learning, I bet you could take this course, and then spend some time with Instaparse and the GLL paper, and walk away with a solid understanding of GLL in practice.

Re: Parsing Algorithms

#7

Post by DmitrySoshnikov » Mon, Oct 26, 2020, 6:34 PM UTC

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…

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.

Re: Parsing Algorithms

#8

Post by DmitrySoshnikov » Mon, Oct 26, 2020, 6:35 PM UTC

andreygrehov wrote: post #3

Very well done! I like video animations. What software do you use to make them?

Thanks for the feedback, glad you like it. For production I use combination of software: Keynote, Notability, Good notes, Camtasia, and live editing on iPad.

Re: Parsing Algorithms

#9

Post by DmitrySoshnikov » Mon, Oct 26, 2020, 6:38 PM UTC

redwoolf wrote: post #4

This is great! I'm working on designing a language right now and I'm just getting to the point where I have to parse the AST. Looking forward to taking this course, I just purchased it on Udemy.

Congrats, and hope this makes building of your parser easy and fun!

This course covers a lot of parsing theory as well, and if you're interested in pure practical (manual) parser, there will be also "Building a Recursive descent parser from scratch", which is mainly coding class and is an extension for the "Parsing Algorithms".

Re: Parsing Algorithms

#10

Post by DmitrySoshnikov » Mon, Oct 26, 2020, 6:39 PM UTC

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.