Video #120: Parser Combinators Recap: Part 2

Episode: Video #120 Date: Oct 12, 2020 Access: Members Only 🔒 URL: https://www.pointfree.co/episodes/ep120-parser-combinators-recap-part-2

Description

We round out our parsing recap by reintroducing that functional trio of operators: map, zip, and flat-map. We’ll use them to build up some complex parsers and make a few more ergonomic improvements to our library along the way.

Video

Cloudflare Stream video ID: 3c6a9e6d37e699d2d9c7d3cc90155bd1 Local file: video_120_parser-combinators-recap-part-2.mp4 *(download with --video 120)*

References

Transcript

— 0:29

Now all of these parsers are cool and all, but the real power comes in the composability of parsers. The Parser type supports many forms of composition that unlock the ability to break large, complex problems into simpler ones. And ideally we can be very confident that the small parsers do their job correctly, like the int and double parsers, and then we can be confident that we glued all the parsers together correctly. Map, Flat-Map, and Zip

— 1:13

The first, and simplest, operator we defined on parsers is the map function: extension Parser { func map<NewOutput>( _ f: @escaping (Output) -> NewOutput ) -> Parser<NewOutput> { .init { input self.run(&input).map(f) } } }

— 1:24

This says that if we have a way to transform Output values into NewOutput values, then we can transform parsers of Output s into parsers of NewOutput s. It is the most basic way to open up a parser and apply a transformation to whatever value it holds on the inside.

— 1:53

It may seem strange to you that we are calling this map . After all, doesn’t the Swift standard library define map on arrays and optionals? How are parsers related to that?? Well, they are related, in fact intimately related, and there are even many more types out there that have map operations, including Combine publishers, random number generators, asynchronous values, and more. We’ve discussed the topic many times on Point-Free, and we highly recommend those that are interested to check out our episode on the map operation .

— 2:28

As a silly example of how to use map , we can map on our int parser to check if the integer parsed is even: let even = Parser.int.map { $0.isMultiple(of: 2) } // Parser<Bool>

— 2:56

And then when we run this parser we just get the boolean back that says whether or not the thing we parsed was even: even.run("123 Hello") // (match: false, rest: " Hello") even.run("124 Hello") // (match true, rest " Hello")

— 3:24

This may not seem like much, but it’s incredibly handy for transforming parsers in a lightweight way, as we will soon see.

— 3:33

But there are some things that we want to be able to do that map alone cannot. For example, what if the even parser didn’t want to simply parse the integer into a boolean, but instead only parse even integers and fail on odd integers.

— 3:50

We may be tempted to use map to say that even integers go through unchanged, but odd integers are mapped to nil to represent failure: let evenInt = Parser.int.map { $0.isMultiple(of: 2) ? $0 : nil } // Parser<Int?>

— 4:11

But the type of this is actually Parser<Int?> , not Parser<Int> . That is very different. This means that every operation we chain on after this has to deal with the optional integer, when all we really wanted to was a regular integer. That will be annoying. Worse, it will consume the integer! evenInt.run("123 Hello") // (match nil, rest " Hello")

— 4:50

And turns out that map can’t do this. We need the ability to inspect the value that the parser has produced so far, and then be able to influence how the next steps of parsing will happen. In particular, we want to inspect the integer parsed so far, and decide that it either produces a successful even integer, or it failed since it was odd.

— 5:13

What we are describing here is a kind of “sequencing” of parsers. We want to run one parser, and then with the output of that parser run another. The operation that expresses the essence of sequencing of computations is known as flatMap , and it can be defined on parsers like so: extension Parser { func flatMap<NewOutput>( _ f: @escaping (Output) -> Parser<NewOutput> ) -> Parser<NewOutput> { .init { input in let original = input let output = self.run(&input) let newParser = output.map(f) guard let newOutput = newParser?.run(&input) else { input = original return nil } return newOutput } } }

— 5:34

This may seem intense, but if you squint you can see the basics of sequencing. We see that we first run the self parser, and then with that result we run the next parser. We just have to do a little bit of extra work to make sure that we revert the input string if the second parser fails.

— 6:01

Again, you may be thinking “why is this called flatMap ?” The standard library defines a flatMap for arrays and optionals, but surely this operation has not relation to those right?? Well, again, this flatMap is deeply related to those operations, as is the flatMap operator in Combine, and there are even many more types with a flatMap operation. It defines the essence of what it means to sequence computations together. If you are interested in learning more you can check out our 5 part series dedicated to the flatMap operator.

— 6:33

With this operation defined we can now properly define the even integer parser. When the parsed integer is even we will return a parser that always succeeds with the integer, and when it’s odd we will return a parser that never succeeds and just returns nil : let evenInt = Parser.int.flatMap { n in n.isMultiple(of: 2) ? Parser { _ in n } : Parser { _ in nil } ) evenInt.run("123 Hello") // (match nil, rest "123 Hello") evenInt.run("124 Hello") // (match 124, rest " Hello")

— 7:45

This is a little verbose, and in fact it motivated us to define a few helpers for the parsers that either always or never succeed: extension Parser { static func always(_ output: Output) -> Self { Self { _ in output } } static var never: Self { Self { _ in nil } } }

— 8:12

With these helpers we can more succinctly describe the even integer parser with: let evenInt = Parser.int.flatMap { n in n.isMultiple(of: 2) ? .always(n) : .never }

— 8:19

Now this reads very nicely: first parse off an integer, and if that succeeds, check to see if it’s even, and if it’s even, we will succeed, or otherwise we will fail, reverting the input back to its original state. This is the special behavior that flatMap has baked in. We get to try another parser after running one, and if it fails then we revert all the changes and go back to the original string. This is incredible important. It means our compositional operators, the things that provide the glue for forming more complex parsers, are well-behaved and have reasonable behavior. This gives us the confidence to build truly complex parsers from simple ones.

— 9:17

But still, even map and flatMap aren’t powerful enough to do all the things we want to be able to do with parsers. While flatMap allows us to run one parser after another by using the output of the first parser, sometimes we just want to run a bunch of parsers, one after the other independent of each other, and then collect all of their outputs together. It may be hard to see right now, but this latter computation that we are describing is completely distinct from flatMap and map .

— 9:48

This operation is called zip , and it adds a whole new layer of functionality to our parsing tool belt. It allows us to run two independent parsers on the input string, and if they both succeed we get their results delivered to us in a tuple. Let’s paste in the implementation: func zip<Output1, Output2>( _ p1: Parser<Output1>, _ p2: Parser<Output2> ) -> Parser<(Output1, Output2)> { .init { input -> (Output1, Output2)? in let original = input guard let output1 = p1.run(&input) else { return nil } guard let output2 = p2.run(&input) else { input = original return nil } return (output1, output2) } }

— 10:09

This takes two parsers, each working to produce different types, and returns a parser of the tuple of the two types. It works by simply running one after the other and then return the output from each. Notice that they are run completely independently of each other: guard let matchA = a.run(&str) else { return nil } guard let matchB = b.run(&str) else { The output of the first parser does not, and cannot, influence how the second parses. This is in stark contrast with how flatMap works, where the second parser is derived from the value produced from the first parser: let matchA = self.run(&str) let parserB = matchA.map(f) guard let matchB = parserB?.run(&str) else {

— 10:52

This operator allows us to piece together multiple parsers so that we can incrementally attack more and more of the input string. As a simple example, suppose we wanted to parse the temperature from a string that has the degree sign and Fahrenheit symbol in it: "100°F"

— 11:12

Well, we can break this problem down into two parts: parsing the double off the front, and then parsing the literal degree sign and “F” after that: let temperature = zip(Parser.int, Parser.prefix("°F"))

— 11:48

Here we are able to leverage type inference to get access to the static parser in each case. This what we mean when we say that moving our reusable parsers to be static does not clutter the call site typically. let temperature = zip(.int, .prefix("°F")) // Parser<(Int, Void)>

— 12:20

Currently this is a parser of a tuple, (Int, Void) , because the literal parser is a parser of Void values. We can map on this parser in order to discard the void value: let temperature = zip(.int, .prefix("°F")) .map { temperature, _ in temperature } // Parser<Int>

— 12:52

And using the parser shows that it behaves how we expect: temperature.run("100°F") // (match 100, rest "") temperature.run("-100°F") // (match -100, rest "") Parsing many values

— 13:20

So that’s the functional “trio” of operators that we can define on the parser type. There are many generic types out there that support these three operations, and as soon as you have them, you have a powerful toolset for breaking large, complex problems down into smaller, simpler ones.

— 13:53

But often we need to zip together more than just two parsers. The example we considered in our parser episodes was that of latitude or longitude coordinates. A latitude coordinate might look something like this: "40.446° N"

— 14:28

Or it could look like this: "40.446° S"

— 14:33

The “N” corresponds to north of the equator, and it represents a positive value, whereas “S” is south and represents a negative value. So, there are three things to parser here, first the coordinate double, then the literal of the degree sign and space, and then the “N” or “S”, which multiples the coordinate value by plus or minus one.

— 14:57

Let’s first attack parsing the “N” or “S” and transforming it into a plus or minus one. We can do this using the char parser and flatMap ing onto it in order to decide how we want to transform the character: let northSouth = Parser.char .flatMap { $0 == "N" ? .always(1.0) : $0 == "S" ? .always(-1) : .never } // Parser<Double>

— 15:38

And we can go ahead and do the same for the east/west parsing for longitude: let eastWest = Parser.char .flatMap { $0 == "E" ? .always(1.0) : $0 == "W" ? .always(-1) : .never }

— 15:53

Then what we’d like to do is zip together a few parsers. To parser a latitude coordinate we will first parser a double, then the degree sign with a space, then the north/south character: let latitude = zip( .double, .prefix("° "), northSouth )

— 16:18

However, this doesn’t work because we can’t zip together three parsers at once. We could nest the zip s by doing a zip of a zip , but better would be just to define another overload of zip for 3 parsers: func zip<Output1, Output2, Output3>( _ p1: Parser<Output1>, _ p2: Parser<Output2>, _ p3: Parser<Output3> ) -> Parser<(Output1, Output2, Output3)> { zip(p1, zip(p2, p3)) .map { output1, output23 in (output1, output23.0, output23.1) } }

— 16:43

Now this code compiles: let latitude = zip( .double, .prefix("° "), northSouth ) // Parser<(Double, Void, Double)>

— 16:43

Which means we can map the parser in order to multiply the doubles together. let latitude = zip( .double, .prefix("° "), northSouth ) .map { latitude, _, latSign in latitude * latSign }

— 17:07

We can create the longitude one in a similar fashion: let longitude = zip( .double, .prefix("° "), eastWest ) .map { longitude, _, longSign in long * longSign }

— 17:20

Now that we can parse a latitude or longitude, let’s parse a full geographic coordinate of the form: "40.446° N, 79.982° W"

— 17:31

To do this we can first define a proper data type to hold the coordinate: struct Coordinate { let latitude: Double let longitude: Double }

— 17:37

Then we can construct one of these values from the parser by first parsing a latitude, then the comma with a space, and then the longitude, and finally mapping it into the coordinate data type: let coord = zip( latitude, .prefix(", "), longitude ) .map { lat, _, long in Coordinate(latitude: lat, longitude: long) }

— 18:24

This is pretty cool. This last parser doesn’t even reference any of those low-level, hard-to-implement parsers like the double parser. It is working at a really high level, piecing together other parsers, and its even quite easy to read.

— 18:38

Next, we considered what it would mean to try running multiple parsers on the same input string, and taking the result of the first one that succeeds. This has many uses, such as parsing into enums. For example, say we had an enum with a few currencies: enum Currency { case eur, gbp, usd }

— 18:53

And we want to parse a string representing the currency symbol into one of these values. We can construct a parser for each of the currencies: Parser.prefix("€").map { Currency.eur } Parser.prefix("£").map { Currency.gbp } Parser.prefix("$").map { Currency.usd }

— 19:06

And then ideally we’d like to have some kind of parser operator that can combine them all into a single parser that just takes the first successful one. It might look something like this: let currency = oneOf( Parser.prefix("€").map { Currency.eur }, Parser.prefix("£").map { .gbp }, Parser.prefix("$").map { .usd } )

— 19:21

In our previous episodes we defined this as a free function, but now we can upgrade it to a static: extension Parser { static func oneOf(_ ps: [Self]) -> Self { .init { input in for p in ps { if let match = p.run(&str) { return match } } return nil } } }

— 19:27

One nice ergonomic improvement we can make is to create an overload for this function that works with variadics: extension Parser { static func oneOf(_ ps: Self...) -> Self { self.oneOf(parsers) } } let currency = Parser.oneOf( Parser.prefix("€").map { Currency.eur }, Parser.prefix("£").map { .gbp }, Parser.prefix("$").map { .usd } ) // Parser<Currency>

— 19:56

It simply iterates over the parsers, running each one, and as soon as we find one that succeeds we short circuit and stop running parsers.

— 20:06

Now, you may be wondering why did we move oneOf to be a static but we didn’t do the same for zip ? Well, zip is subtly different, and explaining why turns out to be a deep topic, so we are going to save that discussion for a future episode.

— 20:17

And with this new currency parser we can also define a money parser: "$100" struct Money { let currency: Currency let value: Double } let money = zip(currency, .double) .map(Money.init(currency:value:) money.run("$100") // (match (usd, value 100), rest "") money.run("£100") // (match (gbp, value 100), rest "") money.run("€100") // (match (eur, value 100), rest "") Parsing a value many times

— 21:50

So this is all very cool and powerful, but then we brought all of this together to parse one very large, complex string. We considered the following data set of marathon races: let upcomingRaces = """ New York City, $300 40.60248° N, 74.06433° W 40.61807° N, 74.02966° W 40.64953° N, 74.00929° W 40.67884° N, 73.98198° W 40.69894° N, 73.95701° W 40.72791° N, 73.95314° W 40.74882° N, 73.94221° W 40.75740° N, 73.95309° W 40.76149° N, 73.96142° W 40.77111° N, 73.95362° W 40.80260° N, 73.93061° W 40.80409° N, 73.92893° W 40.81432° N, 73.93292° W 40.80325° N, 73.94472° W 40.77392° N, 73.96917° W 40.77293° N, 73.97671° W --- Berlin, €100 13.36015° N, 52.51516° E 13.33999° N, 52.51381° E 13.32539° N, 52.51797° E 13.33696° N, 52.52507° E 13.36454° N, 52.52278° E 13.38152° N, 52.52295° E 13.40072° N, 52.52969° E 13.42555° N, 52.51508° E 13.41858° N, 52.49862° E 13.40929° N, 52.48882° E 13.37968° N, 52.49247° E 13.34898° N, 52.48942° E 13.34103° N, 52.47626° E 13.32851° N, 52.47122° E 13.30852° N, 52.46797° E 13.28742° N, 52.47214° E 13.29091° N, 52.48270° E 13.31084° N, 52.49275° E 13.32052° N, 52.50190° E 13.34577° N, 52.50134° E 13.36903° N, 52.50701° E 13.39155° N, 52.51046° E 13.37256° N, 52.51598° E --- London, £500 51.48205° N, 0.04283° E 51.47439° N, 0.02170° E 51.47618° N, 0.02199° E 51.49295° N, 0.05658° E 51.47542° N, 0.03019° E 51.47537° N, 0.03015° E 51.47435° N, 0.03733° E 51.47954° N, 0.04866° E 51.48604° N, 0.06293° E 51.49314° N, 0.06104° E 51.49248° N, 0.04740° E 51.48888° N, 0.03564° E 51.48655° N, 0.01830° E 51.48085° N, 0.02223° W 51.49210° N, 0.04510° W 51.49324° N, 0.04699° W 51.50959° N, 0.05491° W 51.50961° N, 0.05390° W 51.49950° N, 0.01356° W 51.50898° N, 0.02341° W 51.51069° N, 0.04225° W 51.51056° N, 0.04353° W 51.50946° N, 0.07810° W 51.51121° N, 0.09786° W 51.50964° N, 0.11870° W 51.50273° N, 0.13850° W 51.50095° N, 0.12411° W """

— 22:19

Each race is separated by three dashes “—”, and each race contains the name of the location of the race, the entrance fee, and a list of coordinates for the route.

— 22:53

The parser we ultimately want to end up with is of the form: struct Race { let location: String let entranceFee: Money let path: [Coordinate] } let races: Parser<[Race]> = .never

— 23:21

But it would be difficult to construct this all at once. Instead we want to focus on smaller parts, and then slowly build up to this large parser.

— 23:32

So, maybe it’s easier to just make a parser for a single race: let race: Parser<Race> = .never

— 23:51

To do that we want to parse off the location, then a comma and space, then the money for the entrance fee, and then finally a list of coordinates.

— 24:00

To parse the location name we want to consume everything up until the comma. We can construct this parser from scratch: let locationName = Parser<Substring> { input in let name = input.prefix(while: { $0 != "," }) input.removeFirst(name.count) return name }

— 24:44

And then we just have to zip together a bunch of parsers: zip( locationName, .prefix(", "), money, .prefix("\n") // coordinates )

— 25:13

We don’t have the ability to parse the coordinates yet, but before even getting to that we also don’t have the ability to zip four parsers together. And soon we’ll need to zip five. So let’s paste in a few more overloads for zip : func zip<A, B, C, D>( _ a: Parser<A>, _ b: Parser<B>, _ c: Parser<C>, _ d: Parser<D> ) -> Parser<(A, B, C, D)> { zip(a, zip(b, c, d)) .map { a, bcd in (a, bcd.0, bcd.1, bcd.2) } } func zip<A, B, C, D, E>( _ a: Parser<A>, _ b: Parser<B>, _ c: Parser<C>, _ d: Parser<D>, _ e: Parser<E> ) -> Parser<(A, B, C, D, E)> { zip(a, zip(b, c, d, e)) .map { a, bcde in (a, bcde.0, bcde.1, bcde.2, bcde.3) } }

— 25:42

These overloads may seem a little annoying, and they kinda are, but remember that this is library-level code. The user of this parser library doesn’t have to think about these overloads, they just use zip .

— 25:53

Now our parser is compiling, but I think we can take the opportunity to generalize some parsing logic. The parsing we are doing for the location name is probably a very common task. Basically parsing from the beginning of a string until we reach a particular character.

— 26:21

Let’s create a custom parser that does just that logic: extension Parser where Output == Substring { static func prefix(while p: @escaping (Character) -> Bool) -> Self { Self { input in let output = input.prefix(while: p) input.removeFirst(output.count) return output } } }

— 27:18

And now our parser looks like: let locationName = Parser.prefix(while: { $0 != "," })

— 27:29

But maybe it’s so simple now that we can just inline it: zip( .prefix(while: { $0 != "," }), .prefix(", "), money, .prefix("\n") )

— 27:53

This is reading nicely, but we still aren’t parsing the coordinates. To do this we need to use yet another parser combinator that we developed last time. It’s called zeroOrMore , and it allows you to repeatedly run a parser on a string, consuming more and more of it until it fails, at which point we get back an array of all the things it parsed. It’s implementation looked like this: extension Parser { func zeroOrMore( separatedBy separator: Parser<Void> ) -> Parser<[Output]> { Parser<[Output]> { input in var rest = input var matches: [Output] = [] while let match = self.run(&input) { rest = input matches.append(match) if separator.run(&input) == nil { return matches } } input = rest return matches } } }

— 28:31

It’s pretty complex, but like our other complex parsers this one does one job and does it well. We can have a lot of confidence this works correctly, which empowers us to use it in higher-level parsers. In our previous episodes we defined this as a free function, but perhaps it would be more ergonomic as a method.

— 29:22

In particular we can use this to parse a bunch of coordinates that are separated by newlines: coord.zeroOrMore(separatedBy: .literal("\n"))

— 30:10

And this is the parser we can use in our mega-zipped reducer to finally parse a single race: let race = zip( .prefix(while: { $0 != "." }), .prefix(", "), money, .prefix("\n"), coord.zeroOrMore(separatedBy: .prefix("\n")) ) .map { location, _, entranceFee, _, coordinates in Race( location: String(location), entranceFee: entranceFee, path: coordinates ) } // Parser<Race>

— 31:14

And finally we can us zeroOrMore one more time in order to parse the list of races: let races = race.zeroOrMore(separatedBy: .prefix("\n---\n")) // Parser<[Race]>

— 31:55

When we run this parser on the input string we will get an array of races: races.run(upcomingRaces) // (match [{...}, {...}, {...}], rest "") Even more ergonomic parsing

— 32:43

And so this is pretty incredible. We are showing just how easy it is to parse complex text formats by incrementally breaking the problem down into smaller and smaller units, and then piecing it all together to solve the original problem. It doesn’t matter how many times I do functional parsing like this, I always think it’s amazing to see.

— 33:06

But let’s improve one last bit of ergonomics before finishing off this recap. Right now we have quite a few references to the prefix parser that simply parsers a string off the front of the input string. What if instead we could automatically have string literals be upgraded to this prefix parser under the hood, which would allow us to write things like: let coord = zip(latitude, ", ", longitude) .map { lat, _, long in Coordinate(latitude: lat, longitude: long) }

— 33:48

And now that reads really nicely!

— 33:53

In order to do this we need to conform the Parser type to conform to the ExpressibleByStringLiteral protocol, which will allow this conversion from string literal to parser happen automatically. We don’t want to conform any parser to this protocol because it only makes sense for parsers that don’t produce any output, like the prefix parser: extension Parser: ExpressibleByStringLiteral where Output == Void { }

— 34:27

As soon as we do this we get lots of compiler errors telling us exactly what we need to implement in order to conform to this protocol. One problem is that this protocol inherits from a few others, but we can tell the compiler to stub those extensions for us with the same constraint: extension Parser: ExpressibleByUnicodeScalarLiteral where Output == Void { } extension Parser: ExpressibleByExtendedGraphemeClusterLiteral where Output == Void { }

— 34:53

Next we need to fill in some stubs and let the compiler guide us along the way. extension Parser: ExpressibleByStringLiteral where Output == Void { typealias StringLiteralType = String init(stringLiteral value: String) { self = .prefix(value) } }

— 35:15

And finally, we need to let the conformances it inherits from to use the same literal types. extension Parser: ExpressibleByUnicodeScalarLiteral where Output == Void { typealias UnicodeScalarLiteralType = StringLiteralType } extension Parser: ExpressibleByExtendedGraphemeClusterLiteral where Output == Void { typealias ExtendedGraphemeClusterLiteralType = StringLiteralType }

— 35:34

And now we can update a lot of parsers to leverage these new literal syntax to clean up some syntactic noise: let temperature = zip(.double, "°F") .map { temperature, _ in temperature } … let latitude = zip(.double, "° ", northSouth) … let longitude = zip(.double, "° ", eastWest) … let coord = zip(latitude, ", ", longitude) … let race = zip( .prefix(while: { $0 != "," }), ", ", money, "\n", coord.zeroOrMore(separatedBy: "\n") ) … let races = race.zeroOrMore(separatedBy: "\n---\n")

— 36:38

Very nice! One final improvement we could make is in the zeroOrMore parser. It currently requires you to pass in a separator parser, but sometimes you want to run a parser zero or more times without a separator. I think we could provide a nice default here, a parser of an empty string, which is similar to the default separator on Swift’s split method on collections. extension Parser { func zeroOrMore( separatedBy separator: Parser<Void> = "" ) -> Parser<[Output]> { … } } Next time: XCTest log parsing

— 37:29

And so that’s our recap of parsers and parser combinators. We can already see the power in them, but as we said before, this is only the tip of the iceberg. There is so much left to explore, including generalization, performance, and invertibility. And we will get to all of that, but we want to do one more thing before ending the recap. So far we haven’t shown too much new stuff to those who were already caught up on our past episodes on parsing, so we’d like to show off something that everyone can get benefit from.

— 37:58

We will create a whole new complex parser from scratch, and it will push our current knowledge of parsers even further. We are going to write a parser that will process all of the logs that Swift spits out when running tests…next time! 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. https://vimeo.com/290272240 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. https://academy.realm.io/posts/tryswift-yasuhiro-inami-parser-combinator/ 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. https://github.com/kean/Regex 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! http://khanlou.com/2019/12/regex-vs-combinatorial-parsing/ 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. https://bodil.lol/parser-combinators/ 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. https://github.com/johnpatrickmorgan/Sparse 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. http://hackage.haskell.org/package/parsec 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. https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/ 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. https://talk.objc.io/episodes/S01E13-parsing-techniques Downloads Sample code 0120-parsers-recap-pt2 Point-Free A hub for advanced Swift programming. Brought to you by Brandon Williams and Stephen Celis . Content Become a member The Point-Free Way Beta previews Gifts Videos Collections Free clips Blog More About Us Community Slack Mastodon Twitter BlueSky GitHub Contact Us Privacy Policy © 2026 Point-Free, Inc. All rights are reserved for the videos and transcripts on this site. All other content is licensed under CC BY-NC-SA 4.0 , and the underlying source code to run this site is licensed under the MIT License .