Learn from LL(1) to PEG parser the hard way

Kir Chou

CPython Compiler and Interpreters Python 3

See in schedule: Thu, Jul 29, 10:30-11:15 CEST (45 min) Download/View Slides

Detailed description
In late 2019, Guido van Rossum wrote a series of articles about PEG parser and gave the talk "Writing a PEG parser for fun and profit" in a couple of conferences, such as North Bay Python, mentioned the motivation of his research and prototype of PEG parser. In late 2020, other authors of PEP 617, Pablo Galindo and Lysandros Nikolaou, (created around mid of 2020) were interviewed on Podcast.__init__ to talk about the result of the new PEG parser in CPython.
Above contents assume the audience with solid compiler fundamental knowledge, but the fact is most People, including this talk's speaker, are not specialized in compiler. And another fact is most of the compiler class in school around the world only covers traditional top-down and bottom-up parsing techniques, not to mention PEG parser that appeared in the early 2000s.
For the above reasons, the speaker will stand on the shoulders of giants and share his hard way after a few months of study. He will talk about the fundamentals of Parser (part of compiler frontend), including CFG, traditional parsing techniques, PEG, Packrat parser, and PEG parser in CPython.

Objective
If you have zero compiler background, you can at least learn the frontend compiler knowledge and how it is used in Python. If you have learned fundamental compiler knowledge in university, this talk will make you recall the traditional top-down and bottom-up parser in the class, and additionally add some relatively new ideas that appear in the early 2000s. If you are a compiler master and know the Packrat parsing research done by Bryan Ford, this talk may still provide you a brief idea about the reason why Guido van Rossum picked LL(1) initially, and PEG parser later.

Outline
- Opening + Self-intro
- Motivation
- What is parser in CPython?
- Parser 101 - CFG
- Parser 101 - Traditional top-down/bottom-up parser
- Parser 102 - PEG and PEG parser
- Parser 102 - Packrat parser
- CPython’s PEG parser
- Take Away

Type: Talk (45 mins); Python level: Intermediate; Domain level: Intermediate