9 Parser combinators

 

This chapter covers

  • Introducing parser combinators
  • Designing and using APIs without implementations

In this chapter, we’ll work through the design of a combinator library for creating parsers. We’ll use JSON parsing (http://mng.bz/DpNA) as a motivating use case. Like chapters 7 and 8, this chapter is not so much about parsing as it is about providing further insight into the process of functional design.

What is a parser?

A parser is a specialized program that takes unstructured data (e.g., text or any kind of stream of symbols, numbers, or tokens) as input, and outputs a structured representation of that data. For example, we can write a parser to turn a comma-separated file into a list of lists, where the elements of the outer list represent the records, and the elements of each inner list represent the comma-separated fields of each record. Another example is a parser that takes an XML or JSON document and turns it into a tree-like data structure.

In a parser combinator library like the one we’ll build in this chapter, a parser doesn’t have to be anything quite that complicated, and it doesn’t have to parse entire documents. It can do something as elementary as recognize a single character in the input. We then use combinators to assemble composite parsers from elementary ones and still more complex parsers from those.

9.1 Designing an algebra first

9.2 A possible algebra

9.2.1 Slicing and nonempty repetition

9.3 Handling context sensitivity

9.4 Writing a JSON parser

9.4.1 The JSON format

9.4.2 A JSON parser

9.5 Error reporting

9.5.1 A possible design

9.5.2 Error nesting

9.5.3 Controlling branching and backtracking

9.6 Implementing the algebra

9.6.1 One possible implementation