A video series exploring functional programming and Swift.
#62 • Monday Jun 24, 2019 • Subscriber-only

Parser Combinators: Part 1

Even though map, flatMap and zip pack a punch, there are still many parsing operations that can’t be done using them alone. This is where “parser combinators” come into play. Let’s look at a few common parsing problems and solve them using parser combinators!

This episode builds on concepts introduced previously:

#62 • Monday Jun 24, 2019 • Subscriber-only

Parser Combinators: Part 1

Even though map, flatMap and zip pack a punch, there are still many parsing operations that can’t be done using them alone. This is where “parser combinators” come into play. Let’s look at a few common parsing problems and solve them using parser combinators!

This episode builds on concepts introduced previously:


Subscribe to Point‑Free

This episode is for subscribers only. To access it, and all past and future episodes, become a subscriber today!

See subscription optionsorLog in

Sign up for our weekly newsletter to be notified of new episodes, and unlock access to any subscriber-only episode of your choosing!

Sign up for free episode

Introduction

In the last three episodes of Point-Free we explored the compositional properties of parsers by defining map, flatMap and zip operations on them. Each operation carried with it precise semantic meaning, and that meaning is shared with many other types such as arrays, optionals, results, promises and more, and each one was a little more powerful than the last.

With those three operations we were able to cook up complex parsers by piecing together lots of tiny, easy-to-understand parsers. The example we developed was that of a latitude/longitude coordinate parser, which was built from many small parsers. But even though these three operations pack a punch, there are still some things that they cannot accomplish. For example, we cannot currently parse any number of values from some input string, like say a string that has a bunch of coordinates that are separated by newlines. Nor can we attempt to run a bunch of parsers against an input string till one succeeds, say if we support more than one format for a data type. Doing so with map, flatMap, and zip alone is just not possible, so we need to figure out a way to take our parsers to the next level.

The key to this leveling up is none other than functions. Just plain functions. It’s an idea we’ve seen time and time again on Point-Free. By using functions that return parsers as output, or even better, take parsers as input and return parsers as output, we will unlock a whole new world of possibilities with our parsers. These functions are called “parser combinators”, but they could maybe even be called “higher-order parsers” to draw an analogy with “higher-order functions”.

Subscribe to Point-Free

👋 Hey there! Does this episode sound interesting? Well, then you may want to subscribe so that you get access to this episodes and more!


Exercises

  1. We defined prefix(while:) to parse off a substring while characters matched a predicate. It can be just as useful to skip characters. Define a drop(while:) parser that skips characters that match a given predicate. What type of parser should drop(while:) return?

  2. Define a parser combinator, zeroOrMore, that takes a parser of As as input and produces a parser of Array<A>s by running the existing parser as many times as it can.

  3. Define a parser combinator, oneOrMore, that takes a parser of As as input and produces a parser of Array<A>s that must include at least one value.

  4. Because oneOrMore guarantees at least one value, let’s enforce it in the type system! Update oneOrMore to return Parser<NonEmptyArray<A>> instead of Parser<[A]>.

  5. Enhance the zeroOrMore and oneOrMore parsers to take a separatedBy argument in order to parse a comma-separated list. Ensure that only separators between parsed values are consumed.

  6. Redefine the zeroOrMoreSpaces and oneOrMoreSpaces parsers in terms of zeroOrMore and oneOrMore.


References

  • Combinators

    Daniel Steinberg • Friday Sep 14, 2018

    Daniel gives a wonderful overview of how the idea of “combinators” infiltrates many common programming tasks.

    Just as with OO, one of the keys to a functional style of programming is to write very small bits of functionality that can be combined to create powerful results. The glue that combines the small bits are called Combinators. In this talk we’ll motivate the topic with a look at Swift Sets before moving on to infinite sets, random number generators, parser combinators, and Peter Henderson’s Picture Language. Combinators allow you to provide APIs that are friendly to non-functional programmers.

  • Parser Combinators in Swift

    Yasuhiro Inami • Monday May 2, 2016

    In the first ever try! Swift conference, Yasuhiro Inami gives a broad overview of parsers and parser combinators, and shows how they can accomplish very complex parsing.

    Parser combinators are one of the most awesome functional techniques for parsing strings into trees, like constructing JSON. In this talk from try! Swift, Yasuhiro Inami describes how they work by combining small parsers together to form more complex and practical ones.

  • Regex

    Alexander Grebenyuk • Saturday Aug 10, 2019

    This library for parsing regular expression strings into a Swift data type uses many of the ideas developed in our series of episodes on parsers. It’s a great example of how to break a very large, complex problem into many tiny parsers that glue back together.

  • Learning Parser Combinators With Rust

    Bodil Stokke • Thursday Apr 18, 2019

    A wonderful article that explains parser combinators from start to finish. The article assumes you are already familiar with Rust, but it is possible to look past the syntax and see that there are many shapes in the code that are similar to what we have covered in our episodes on parsers.

  • Sparse

    John Patrick Morgan • Thursday Jan 12, 2017

    A parser library built in Swift that uses many of the concepts we cover in our series of episodes on parsers.

    Sparse is a simple parser-combinator library written in Swift.

  • parsec

    Daan Leijen, Paolo Martini, Antoine Latter

    Parsec is one of the first and most widely used parsing libraries, built in Haskell. It’s built on many of the same ideas we have covered in our series of episodes on parsers, but using some of Haskell’s most powerful type-level features.

  • 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.

Chapters
Introduction
00:05
Recap
01:50
More forgiving parsing
03:48
Extracting common parsers
11:17
Next time: parsing multiple values
18:57