Grammars, parsing, and recursive descent

This video has a page on 0DE5 with exercises and resources

Chapters
00:00 - Intro
02:23 - Grammars
15:26 - Recursive descent
23:12 - Pushdown automata
28:44 - Outro

[zweitekonto]

It's that moment where you're casually scrolling through youtube. You see a video recommended. It intrigues you, and after 1 min in, you realise you hit an absolute goldmine. Subscribed.

[hyperplano]

You know it's going to be good when Kay starts with some historical artifact

[rafaelfreire]

I'm taking a class on compilers this semester. You have no idea how great it is to click on YouTube and see a video like this. Thanks

[codewizard]

I got a degree in computer science from Imperial College in 1979. In 1982 I wrote a 'C' compiler in Pascal using recursive descent. The book Software Tools was very useful at the time.

[corysandlin]

Dude I just started writing a compiler to learn how they work. This video couldn't have come at a more perfect time! Great vid as always

[SolathPrime]

You know ever since I found this channel and I find myself downloading videos to my archive and using them as a teaching materials
I can't just say how thankful am I to you for this great work
I wish I could do more to support but all I can do is point to your channel whenever I can

[tejasbawa]

You're cooking so hard Kay, thanks for putting out this awesome content.

[ebn]

This has become one of my favorite channels

[luizf]

This channel is exactly what I've been looking for. Thank you algorithm god 🙌🏻

[Axman]

I love that you decided to implement your parser as a Haskell style functional parser. There’s even a poem about them:

A parser for things
Is a function from strings
To list of pairs of things
and strings

Which represents the parser type String -> [(a, String)]

The Haskell Read class uses this type for parsing Haskell values, though it’s almost always using the list as empty or a single result.

This channel definitely needs more Haskell, using Python litters the example code with so much noise.

[esra_erimez]

"Crafting Interpreters" by Nystrom is a good treatment on the subject for those that would like a deeper dive

[vicdotso]

thank you. this almost made me shed a tear

[programmer]

Bonkers how appropriate, for me, this is right now. Thank you

[eichopf]

quick correction for 10:50 — context sensitive languages can be recognised by linear bounded automata, which are less powerful than turing machines. turing machine automata recognise the recursively enumerable languages, which are a superset of the context sensitive languages

[anon_y_mousse]

I don't know what a modern equivalent would be, but if you want a super simple explanation of recursive descent to just get something working without understanding any of the theory, then Crenshaw's tutorial is the best I've ever found. If it didn't use Pascal and generate 68k assembly it would still be directly usable today, but hardly anyone uses Pascal anymore and fewer still need code generated for a 68k processor and if you're just starting out learning you won't understand how to translate these.

If anyone knows of a good modern equivalent that either is written in C or generates C or both, that would probably be what I'd recommend. If not, then I'll have to add that to my project list because someone needs to write one.

[forivall]

Speaking of left recursion, the JavaScript parsers used in most tooling use recursive descent, but switch to an operator precedence parser for parsing binary operators. That's another nice thing about recursive descent, is that, compared to the specialized parser generator tools, you can switch up the parsing strategy for a subset of the grammar

[ngideo]

i literally lol'd at the example of "the grammar of a laugh". well played.

[amadzarak]

Wow! This video was so incredibly dense. Thank you

[btu]

Love the vids. I am learning the Same topic in uni right now. Nice overhaul. Thank you very much. Continue the good work pretty please!😊

[bzboii]

these videos are so great. happy i found the channel :)