What Is a Parser?: Part 1

Episode #56 • May 6, 2019 • Subscriber-Only

Parsing is a difficult, but surprisingly ubiquitous programming problem, and functional programming has a lot to say about it. Let’s take a moment to understand the problem space of parsing, and see what tools Swift and Apple gives us to parse complex text formats.

What Is a Parser?: Part 1
Introduction
00:05
Simple parsers in Swift/Foundation
01:53
More advanced parsing in Foundation
05:40
Parsing from scratch
10:17
Addressing edge cases
14:15

Unlock This Episode

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

Introduction

Today we are going to begin discussing a topic that was a bit of an “a ha!” moment for me when first getting into functional programming. It sets out to solve a very difficult problem, and does so in a beautiful way. And like most things in functional programming, the problem is solved with lots of tiny pieces that glue together in interesting ways allowing you to create a massively complex machine that can do really powerful things.

The topic is parsers, and in particular parser combinators. Broadly speaking, we could define parsing as trying to take a blob of nebulous data, like say a string, data, user input, or even a URL request, and turn it into a more domain-specific, first class data type, like say a user model. When said in that way you can even imagine parsing as literally a function from “nebulous blob of data” to “well-structured data”, and so functional programming probably has a lot to say about this topic. But, this function, at first, is pretty intimidating to implement because we may need to do a lot of work in order to extract out meaningful data from it.

Parser combinators aim to break this problem into a lot of very specific parsers that do one job and do it well. And then it provides all of the high-level functions that allow us to glue lots of parsers together to get big parsers that can handle more and more complex data. The way in which we are describing this is akin to how we developed our composable randomness library, which we had many episodes (#30, #31, #32, #47, #48, #49, #50) on and open sourced. It allowed us to focus on a single unit of randomness and then build up lots of complex random generators by gluing them together in interesting ways. This style of solving a problem just keeps coming up in functional programming, and it is really powerful.

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

Scanner

Apple

Official documentation for the Scanner type by Apple. Although the type hasn’t (yet) been updated to take advantage of Swift’s modern features, it is still a very powerful API that is capable of parsing complex text formats.

NSScanner

Nate Cook • Monday Mar 2, 2015

A nice, concise article covering the Scanner type, including a tip of how to extend the Scanner so that it is a bit more “Swifty”. Take note that this article was written before NSScanner was renamed to just Scanner in Swift 3.

Ledger Mac App: Parsing Techniques

Chris Eidhof & Florian Kugler • Friday Aug 26, 2016

In this free episode of Swift talk, Chris and Florian discuss various techniques for parsing strings as a means to process a ledger file. It contains a good overview of various parsing techniques, including parser grammars.

Parse, don’t validate

Alexis King • Tuesday Nov 5, 2019

This article demonstrates that parsing can be a great alternative to validating. When validating you often check for certain requirements of your values, but don’t have any record of that check in your types. Whereas parsing allows you to upgrade the types to something more restrictive so that you cannot misuse the value later on.

Downloads