Parser Combinators Recap: Part 1

Episode #119 • Oct 5, 2020 • Subscriber-Only

It’s time to revisit one of our favorite topics: parsing! We want to discuss lots of new parsing topics, such as generalized parsing, performance, reversible parsing and more, but before all of that we will start with a recap of what we have covered previously, and make a few improvements along the way.

Part 1
Introduction
00:05
What is a parser?
02:46
Defining the problem of parsing
06:39
Defining a parser
10:04
Defining a parser’s home
18:48
Next time: parser composition recap
24:38

Unlock This Episode

Our Free plan includes 1 subscriber-only episode of your choice, plus weekly updates from our newsletter.

Introduction

Today we will pick up a topic that we last covered over a year ago, and it’s one of the most popular series of episodes we have ever done. And that’s parsing.

We spent 9 episodes exploring the problem space of parsing. First we gave a concise definition of what it means to parse something in general, including what tools Apple gives us in their frameworks for parsing. Then we gave a proper functional programming definition of a parser, and of course it basically boils down to just one single function signature. And with that function signature we were able to define all the usual functional operators on it that we have grown to love, such as map, zip and flatMap, and each one had a very precise job of how to break down a large, complex problem into smaller ones. And then finally we discussed “parser combinators”, which are custom little functions that take parsers as input and produce parsers as output, and these things allowed us to take parsing to the next level.

However, even though the things we covered previously were quite powerful, it doesn’t even begin to scratch the surface of parsing. There is so much we want to cover.

  • First, we want to improve the ergonomics of the parsers that we have defined so far, because we haven’t given much attention to that yet and there are a few sharp edges right now.
  • Next, we want to show how to generalize parsing so that we can parse more than just strings. We’d like to be able to parse any kind of data type.
  • And then, amazingly, the very act of generalizing our parser will give just the tools we need to finely tune the performance of our parsers. If done correctly they can be nearly as efficient as hand rolled parsers, which is pretty amazing.
  • And then finally, we want to show how to flip parsing on its head by describe what it means to “unparse” something. That is, if you were to “unparse” a parsed result, and then re-parse it, you should get back to where you started. That may not sound very interesting, but trust us, it’s surprising and amazing to see, but we don’t want to give away any spoilers right now.

So, there’s still a ton to cover, and we’ll get there in the coming months, but right now we want to take a step back and give a little recap on everything we covered before. There are a lot of people out there that haven’t watched our parser episodes, though we highly encourage you to, and others that have watched may have gotten a bit rusty. This episode will quickly summarize everything we covered in the past 9 episodes to get us all on the same foundation from which we can build much bigger concepts. It won’t have a ton of new content for those who are already familiar with parsing, but we will make a few tweaks to the previous code in order to improve its ergonomics along the way, so hopefully everyone will get at least something from this episode.

So let’s get started!

This episode is for subscribers only.

Subscribe to Point-Free

Access this episode, plus all past and future episodes when you become a subscriber.

See plans and pricing

Already a subscriber? Log in

References

Collection: Parsing

Brandon Williams & Stephen Celis

New to parsing? Start our collection from the beginning!

Parsing is a surprisingly ubiquitous problem in programming. Every time we construct an integer or a URL from a string, we are technically doing parsing. After demonstrating the many types of parsing that Apple gives us access to, we will take a step back and define the essence of parsing in a single type. That type supports many wonderful types of compositions, and allows us to break large, complex parsing problems into small, understandable units.

Downloads