Understanding parser combinators: a deep dive - Scott Wlaschin

Scott Lotion introduces the concept of parser combinators, emphasizing their role in simplifying the process of writing parsers. He mentions his website and the availability of code and slides, setting the stage for a fast-paced talk covering a lot of ground in a short time. The goal is to demystify the intimidating code often associated with parser combinators and to show how they can be used in any programming language, except for COBOL. The talk will cover building a simple parser, understanding combinator libraries, and eventually creating a JSON parser using these techniques.

The speaker delves into the basics of parser combinators, explaining them as recipes for creating parsers. He discusses the advantages of using parser combinators, such as writing parsers in your favorite programming language and the absence of a need for pre-processing. The talk introduces the concept of composition in functional programming and how it applies to building parsers from smaller components. The speaker also demonstrates a simple parser for matching a character and discusses the importance of immutability in functional programming.

Scott Lotion demonstrates how to build a basic parser that matches a specific character, explaining the process of creating a function that returns true or false based on whether the character matches. He then enhances the parser to be more flexible by allowing any character to be matched and discusses the importance of error messages in parsing. The speaker introduces the concept of union types to handle different return types in functional programming and shows how to compile a parser that returns a character and the remaining input or an error message.

The speaker introduces advanced techniques for building parsers, such as returning a function from a function to handle unknown input. He explains how to create a parser that returns another function, which can then be run with an input stream to perform the actual parsing. This approach allows for the creation of more complex parsers by combining simpler ones. The speaker also demonstrates how to run a parser with an input and how to handle the success or failure of the parsing process.

Scott Lotion discusses the concept of combinators, which are functions that combine parsers to create new ones. He introduces three basic combinators: 'and then', 'or else', and 'map'. The 'and then' combinator chains parsers in sequence, the 'or else' allows for alternative parsing options, and the 'map' transforms the output of a parser. The speaker provides code examples and demonstrates how these combinators can be used to build more complex parsing logic, such as parsing strings and integers.

The speaker demonstrates how to construct more complex parsers by combining basic ones. He introduces the concept of reducing a list of parsers using an operator, such as 'and then' or 'or else', to create a single parser. This allows for the creation of parsers that can match a sequence of characters or choose between multiple options. The speaker also shows how to create a parser for strings by mapping each character to a parser and using the 'sequence' combinator to combine them.

Scott Lotion discusses how to improve parser error messages by labeling parsers, which helps in providing more descriptive error messages when parsing fails. He also introduces the concept of tracking line and column numbers to enhance error reporting. The speaker demonstrates how to modify the input object to include line and column information, which can then be used to provide more detailed error messages, making it easier for users to understand where parsing errors occur.

The speaker begins building a JSON parser by defining the structure of a JSON value using a choice type in F#. He then starts parsing simple JSON literals like 'null', 'true', and 'false'. The speaker uses helper operators and symbols to create parsers for these literals and discusses the importance of labels for improving error messages. The talk moves on to parsing strings, breaking down the process into smaller components and combining them to form a complete parser for JSON strings.

Scott Lotion continues building the JSON parser by tackling the parsing of numbers. He breaks down the number parsing into components such as an optional sign, an integer part, a fractional part, and an exponent part. The speaker demonstrates how to combine these components using combinators to create a parser for JSON numbers. He also discusses the parsing of JSON objects, showing how to handle nested structures and the use of labels to improve error messages.

The speaker finalizes the JSON parser by combining all the individual parsers for different JSON value types into a single parser. He demonstrates the parser's ability to handle complex JSON structures, including strings, numbers, objects, arrays, booleans, and null values. The speaker also shows how the parser provides helpful error messages when encountering unexpected characters or structures. The talk concludes with a summary of the power of parser combinators and their role in functional programming.

In conclusion, Scott Lotion emphasizes the power of treating functions as objects and the benefits of using parser combinators in functional programming. He highlights the ability to build complex parsers from simple ones and the ease of combining them into larger programs. The speaker provides information on where to find the code and offers assistance for those interested in F# consulting. He encourages attendees to approach him with any questions and reminds them to fill out feedback forms.