PEGs, Packrats and Parser Combinators

Guest lecture, University of Bern, 2023

This was a guest lecture held on April 6, 2023, and again on April 9, 2024 for the Masters course on Compiler Construction offered by Timo Kehrer at the University of Bern. The lecture provides an introduction to Parsing Expression Grammars, as a well as a live demo using the PetitParser framework to build an interpreter for a toy programming language.

Part 1 — Introduction to PEGs and PetitParser

Part 1 consists of a regular lecture consisting of an introduction to Parsing Expression Grammars and related parsing frameworks. It includes simple example of a hand-crafted PEG written in Java, and an optimized packrat version that caches intermediate results to avoid reparsing during backtracking.

PDF | Keynote | Java | YouTube video

Part 2 — Implementing SPL in PetitParser

Part 2 consists of a live demo showing the development of an interpreter for SPL, the Simple Programming language used in exercises in the course, using PetitParser 2, the PEG framework integrated in the Glamorous Toolkit environment.

The demo can be run by downloading Glamorous Toolkit and running the following code in a Playground:

SPLPetitParserSlideshow show 

NB: There is also extensive documentation of the SPL case study in the Glamorous Toolkit book. Just look for the page called “PetitParser SPL case study” in the table of contents, or search for it with the Spotter search tool.

PDF | YouTube video