Swift Talk # 13

## Ledger Mac App: Parsing Techniques

### This episode is freely available thanks to the support of our subscribers

We look at two different techniques to parse a simple expression language: handwritten parsers and parser combinators.

00:07 For our Ledger file, we needed to parse expressions (and parse the rest of the file). Parsers might seem like an obscure topic, but once you start thinking about it, you can use them in many cases. As such, knowing how to write a parser can really help.

00:36 For example, formulas are parsed in spreadsheet applications. And in an app like Photoshop, you can enter expressions like `100/2` into text fields and the result is evaluated.

01:00 Of course, the Swift compiler also parses our code, and understanding how parsers work helps us in understanding the entire build chain. It might seem like it's complicated to write a parser, but in this episode, we'll show that it's not. Interestingly enough, many people use regular expressions for tasks where parsers would be more appropriate (and easier). Additionally, regular expressions are strictly more limited in what they can do. Because of these things, parsers are good tools to have in your tool belt.

## Grammars

01:57 Let's start by defining a grammar for a simple expression language, which allows us to express simple arithmetic expressions like `5+2*3`. The grammar contains the rules for valid expressions in this little language, and the precedence of the operators is encoded in the grammar. The precedence ensures that the expression above is parsed as `5+(2*3)` rather than `(5+2)*3`, because `*` has a different precedence than `+`.

02:48 We try not to think about precedence because we learned it in school, but with obscure operators, we sometimes have to think about it (and add parentheses if we're unsure).

03:05 Let's consider multiplication expressions first, such as `2*3`. The grammar looks like this:

``````multiplicationExpression = int "*" int
``````

03:32 To parse expressions like `5*6 + 2*3`, we can define an additional rule in our grammar:

``````additionExpression = multiplicationExpression "+" multiplicationExpression
``````

04:00 However, this grammar doesn't allow for expressions like `5+2*3`. Our multiplication expression always needs to be of the form `int*int`, and `5` doesn't have the star symbol and the second integer. We can fix that by making the final part optional:

``````multiplicationExpression = int ("*" int)?
``````

04:25 For addition, we have to do the same thing, and we end up with the following grammar:

``````additionExpression = multiplicationExpression ("+" multiplicationExpression)?
multiplicationExpression = int ("*" int)?
``````

04:36 This is the pseudo code for our grammar, and it's incomplete. We can't write expressions like `2*3*4`, but let's just stick with the current example.

04:48 To turn this pseudo grammar into a parser, we could use parser generators such as Bison, YACC, or Lemon. This approach is used by SQLite, among others.

05:26 A second approach is to write a parser manually. This is what most programming languages, such as the Swift parser, do. It gives you full control, and you can hand tune manual parsers to be very fast. The problem is that they can get very complicated; it's not easy to write them in such a way that they're understandable.

05:59 The third approach is to use parser combinators. This approach comes from functional programming, and it's a way of writing parsers by combining them out of other parsers. Because of all the operators and types, they're strange (but interesting).

## Writing a Parser by Hand

06:16 We'll ignore the parser generators for today. Instead, with the help of `NSScanner`, let's start by writing a parser for our current grammar by hand, and then we can have a look at the more obscure technique of parser combinators.

06:45 We start by creating the class `Parser` for our parser. We need to store a `String` and the current parsing location, and we can use the `Scanner` class that's in Foundation. A `Scanner` takes a `String` and a position and provides us with methods to parse simple things like an `Int`. We can create the `Scanner` in our initializer:

``````final class Parser {
let scanner: Scanner

init(_ string: String) {
scanner = Scanner(string: string)
}
}

``````

07:35 To parse a single integer, we could add a method on `Parser`, which tries to parse an integer. The result type is optional, in case it can't parse the integer. To implement that method, we can directly use `Scanner` to scan the integer. `Scanner` has an old-fashioned API in which you need to pass the result as a mutable pointer. Only if the `scanInt` returns true can we return the result; otherwise we return `nil`:

``````func int() -> Int? {
var result: Int = 0
guard scanner.scanInt(&result) else { return nil }
return result
}
``````

08:49 We can test it, and we get `23` out:

``````let parser = Parser("23")
parser.int() // 23
``````

08:58 Looking back at our grammar, we want to create the parser for a `multiplicationExpression`. We can add another method, `multiplication`, which also returns an optional integer. We start by parsing a single integer. Then we try to parse a `*` symbol, and finally, we parse the right-hand-side integer and return the multiplication of the two operands.

By the way, we currently return optional values, but in a real parser, we probably want to have more detailed information about what went wrong.

``````func multiplication() -> Int? {
if let lhs = int() {
if scanner.scanString("*", into: nil) {
if let rhs = int() {
return lhs * rhs
}
}
}
}
``````

10:44 We left out all the `else` cases. If we can't parse the first integer, we return `nil`. If we can parse the left-hand side, but not the right-hand side, we can return just the left-hand side (because the `*` and the right-hand side are optional).

In the case that we scan both the left-hand side and the `*`, but not the right-hand side, we have an invalid expression. We could choose to return `nil`, but our scanner has already increased its location, so we'd need to reset it. In order to do that, we need to store the initial location of where we started parsing the multiplication expression:

``````func multiplication() -> Int? {
let oldLocation = scanner.scanLocation
if let lhs = int() {
if scanner.scanString("*", into: nil) {
if let rhs = int() {
return lhs * rhs
} else {
scanner.scanLocation = oldLocation
return nil
}
} else {
return lhs
}
} else {
return nil
}
}
``````

## Refactoring

12:16 This gets tricky, and it's hard to see what's going on here, which is one of the problems when you handwrite a parser: it's difficult to make it correct and to encode all the behavior. When you read the `multiplication` parser we just wrote, aside from the name, it's not obvious that it reflects the `multiplicationExpression` rule in our grammar. However, we can still improve the code by using `guard` statements:

``````func multiplication() -> Int? {
let oldLocation = scanner.scanLocation
guard let lhs = int() else { return nil }
guard scanner.scanString("*", into: nil) else { return lhs }
guard let rhs = int() else {
scanner.scanLocation = oldLocation
return nil
}
return lhs * rhs
}
``````

13:53 To parse an addition expression, we can copy-paste this code. But first, we should test that everything works:

``````let parser = Parser("23*2")
parser.multiplication() // 46
``````

14:30 If we paste the definition of `multiplication` and replace the name and the operator, we end up with a parser that parses simple addition expressions:

``````func addition() -> Int? {
let oldLocation = scanner.scanLocation
guard let lhs = int() else { return nil }
guard scanner.scanString("+", into: nil) else { return lhs }
guard let rhs = int() else {
scanner.scanLocation = oldLocation
return nil
}
return lhs + rhs
}
``````

## Parsing More Complicated Expressions

14:55 However, we can't yet parse expressions such as `2*3`. This is because our `addition` method doesn't reflect the grammar. Instead of parsing with `int()`, we should be parsing a multiplication expression:

``````func addition() -> Int? {
let oldLocation = scanner.scanLocation
guard let lhs = multiplication() else { return nil }
guard scanner.scanString("+", into: nil) else { return lhs }
guard let rhs = multiplication() else {
scanner.scanLocation = oldLocation
return nil
}
return lhs + rhs
}
``````

15:29 The simple example we've shown demonstrates how tricky it is to handwrite a parser. It's easy to forget things, it's easy to write code that doesn't exactly match the grammar, and it's hard to diagnose both those things without a lot of test cases.

## Parser Combinators

16:04 Let's look at solving the same problem using parser combinators. We'll take a lot of shortcuts and write the parsers straightaway without explaining all the operators we're using. In a future episode, we'll explain how parser combinators work and really dive into that topic. But for now, we simply want to show that if you squint while reading the parser-combinator code, you'll recognize the grammar.

16:46 The first step is parsing an integer. We used the `Scanner` class for this in our handwritten parser, and we got it for free. But here, we'll write an integer parser from scratch because it's a good example of parser combinators.

17:07 First, we'll parse a single digit. We can use the `character` parser to verify the character is a member of the `decimalDigits` character set:

``````let digit = character(condition: { CharacterSet.decimalDigits.contains(\$0.unicodeScalar) })
digit.run("123")
``````

17:52 The output is a bit cryptic: it's a tuple that contains the parsed value and the remaining string to be parsed. Because we're only parsing a single digit, the next step is parsing multiple digits in a row by using the `many` combinator:

``````let digit = character(condition: { CharacterSet.decimalDigits.contains(\$0.unicodeScalar) })
let digits = digit.many

digits.run("123")
``````

18:40 If we run `digits`, we get back an array of characters rather than a single digit. The next step is combining all the digits into a string by using `map`:

``````let digit = character(condition: { CharacterSet.decimalDigits.contains(\$0.unicodeScalar) })
let digits = digit.many
let digitString = digits.map { characters in String(characters) }

digits.run("123")
``````

19:23 Finally, we want to convert the string into an integer by using `map` again. We know that we'll always pass a valid integer string into the `Int` initializer, so we can force-unwrap the result. (One caveat: we're using the `many` combinator, which also parses an empty string. For this code to be correct, we should use `many1`, which parses at least one digit.)

``````let digit = character(condition: { CharacterSet.decimalDigits.contains(\$0.unicodeScalar) })
let digits = digit.many
let digitString = digits.map { characters in String(characters) }
let int = digitString.map { Int(\$0)! }

int.run("123")
``````

20:08 We can make the code much shorter by inlining the intermediate steps:

``````let digit = character(condition: { CharacterSet.decimalDigits.contains(\$0.unicodeScalar) })
let int = digit.many.map { characters in Int(String(characters))! }
``````

## Multiplication Expressions

20:49 Looking at our grammar again, the next step is a multiplication expression. There's a lot of magic involved here, and if you're not used to parser combinators, the code will be hard to understand at first.

21:14 A multiplication expression is an integer, followed by a `*`, followed by another integer. To combine the parts into a result, we can use the `<^>` operator and the `curry` function. The actual calculation is simple: it's a function that multiplies its two arguments. The code below almost works:

``````let multiplication = curry({ x, y in x*y }) <^> int <*> (string("*") <*> int)

``````

22:15 We need to ignore the result of parsing the `*` string. To do that, we can use the `*>` operator, which parses but ignores the left-hand side. Finally, we can run our parser:

``````let multiplication = curry({ x, y in x*y }) <^> int <*> (string("*") *> int)
multiplication.run("2*3") // 6
``````

22:54 We can no longer parse a single integer using our multiplication parser because we didn't make the second part of our parser optional. We fix this by using the `optional` combinator and providing a default value in case the second parser returns `nil`.

``````let multiplication = curry({ x, y in x * (y ?? 1) }) <^> int <*> (string("*") *> int).optional
``````

23:34 To add addition, we'll copy and paste the `multiplication` parser and replace the name and operators:

``````let addition = curry({ x, y in x + (y ?? 0) }) <^> int <*> (string("+") *> int).optional
``````

23:58 We can test it to verify that it works. However, just like before, we can only parse integer operands. To fix this, we need to use the `multiplication` parser from within `addition`:

``````let addition = curry({ x, y in x + (y ?? 0) }) <^> multiplication <*> (string("+") *> multiplication).optional
``````

24:26 If you look to the right-hand side of the `<^>` operator, you can see the grammar — an int, followed by an optional string and an int — and you can see the operator string gets ignored. In a way, it's very readable, and at the same time, it's very unreadable if you're not used to these operators.

24:48 This demonstrates that you can write a parser with very little code by using parser combinators. The parsers are very close to the grammar. If you're not used to them, they're also very magical, and in a future episode, we'll have a look at how this works. It'll be a challenge for those of us who are used to object-oriented design rather than functional programming.

### Resources

• #### Playground

Written in Swift 3

See All
SwiftUI

### Building a Shopping Cart: Cleanup & Refactoring

Episode 179 · Nov 22

SwiftUI

### Building a Shopping Cart: Drag & Drop (Part 2)

Episode 178 · Nov 15

SwiftUI

### Building a Shopping Cart: Drag & Drop (Part 1)

Episode 177 · Nov 08

SwiftUI

### Building a Shopping Cart: Transitions with View Modifiers

Episode 176 · Nov 01

SwiftUI

### Building a Shopping Cart Animation

Episode 175 · Oct 25

SwiftUI

### Animation Curves

Episode 174 · Oct 18

Unlock Full Access

## Subscribe to Swift Talk

• ### Watch All Episodes

A new episode every week