Parser Combinators: Part 2

Episode #63 • Jul 1, 2019 • Subscriber-Only

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 parse any number of values! Luckily there’s a parser combinator that can help, and it really packs a punch.

Collection
Parser Combinators
Parser Combinators: Part 2
Locked

Unlock This Episode

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

Sign in with GitHub

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.

Parsing multiple values


References

  • Combinators
    Daniel Steinberg • Sep 14, 2018

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

    Note

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

    Note

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

  • Regexes vs Combinatorial Parsing
    Soroush Khanlou • Dec 3, 2019

    In this article, Soroush Khanlou applies parser combinators to a real world problem: parsing notation for a music app. He found that parser combinators improved on regular expressions not only in readability, but in performance!

  • Learning Parser Combinators With Rust
    Bodil Stokke • 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 • Jan 12, 2017

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

    Note

    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.

  • Parse, don’t validate
    Alexis King • 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.

  • Ledger Mac App: Parsing Techniques
    Chris Eidhof & Florian Kugler • 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.

Downloads

Get started with our free plan

Our free plan includes 1 subscriber-only episode of your choice, access to 64 free episodes with transcripts and code samples, and weekly updates from our newsletter.

View plans and pricing