A new Swift video series exploring functional programming and more.
#63 • Monday Jul 1, 2019 • Subscriber-only

Parser Combinators: Part 2

Let’s solve another common parsing problem using parser combinators! It’s common to want to parse multiple values off a string, and while zip gets us part of the way there, it doesn’t let us part any number of values! Luckily there’s a parser combinator that can help, and it really packs a punch.

This episode builds on concepts introduced previously:

#63 • Monday Jul 1, 2019 • Subscriber-only

Parser Combinators: Part 2

Let’s solve another common parsing problem using parser combinators! It’s common to want to parse multiple values off a string, and while zip gets us part of the way there, it doesn’t let us part any number of values! Luckily there’s a parser combinator that can help, and it really packs a punch.

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

The prefix function is an example of a “parser combinator”: it’s a function that produces brand new parsers out of thin air given a little configuration. This prefix parser combinator unlocks some extra power because we can scan off as many characters as we want off the beginning of a string, based on a predicate, and then do something later with it.

Although this is the first time we’ve called something a “parser combinator,” it’s not the first parser combinator that we’ve seen: map, zip, and flatMap are all parser combinators, because they’re functions that take parsers as input and produce parsers as output. Even the literal parser is a parser combinator because it takes some configuration up front (a literal string to parse) and returns a brand new parser that uses that configuration.

We’re beginning to see how parser combinators can enter our code and clean up things in the process: they allow us to solve more and more precise parsing problems by moving the lower-level, trickier parsing logic to these combinators. And then we can use them to build more specific kinds of parsers.

And this prefix combinator was handy enough to clean up the oneOrMoreSpaces and zeroOrMoreSpaces parsers, but it’ll definitely help us build plenty more parsers in the future. In fact, that kind of prefix checking is being done in a bunch of the parsers we’ve already defined.

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 quickly added a separatedBy argument to zeroOrMore, but it can be very useful to parse out an array of values without a separator. Give separatedBy a default parser for this behavior. Is this a parser we’ve already encountered?

  2. Add an until parser argument to zeroOrMore (and oneOrMore) that parses a number of values until the given parser succeeds.

  3. Make this until parser argument optional by providing a default parser value. Is this a parser we’ve already encountered?

  4. Define a parser combinator, oneOf, that takes an array of Parser<A>s as input and produces a single parser of Parser<A>. What can/should this parser do?


References

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

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

  • 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
Parsing multiple values
01:37
Parsing delimited values
07:05
A backtracking bug
08:50
Parsers on parsers on parsers
11:09
Next time: parsing with multiple parsers
17:35