9 Parser combinators

 

This chapter covers

  • An algebraic design approach to libraries
  • Primitives vs. higher-level combinators
  • Using combinators to achieve design goals
  • Improving library ease of use with syntactic sugar
  • Postponing combinator implementation by first focusing on algebra design

In this chapter, we work through the design of a combinator library for creating parsers. We’ll use JSON parsing 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 (such as text or a 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. 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 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 recognizing 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

9.1.1 A parser to recognize single characters

9.1.2 A parser to recognize entire strings

9.1.3 A parser to recognize repetition

9.2 One possible approach to designing an algebra

9.2.1 Counting character repetition

9.2.2 Slicing and nonempty repetition

9.3 Handling context sensitivity

9.4 Writing a JSON parser

9.4.1 Defining expectations of a JSON parser

9.4.2 Reviewing the JSON format