Parser Combinators

Parsing is the act of turning a usually human-readable structured text into a data structure that can be easily processed in software. The best-known application of parsers is on compilers. A compiler frontend takes the text written by programmers, the source code, and turns it into an abstract syntax tree, which is a more convenient data structure to work with in the next stages of the compiler. Besides parsing source code, many other structured text formats are parsed, such as JSON, YMAL, and XML, which are used for all kinds of data entry, data exchange, and configuration.

To make parsing possible, the text cannot take on an arbitrary form. It needs to be structured in a particular way, and follow certain rules. Formally, the expected text structure is sometimes codified in a grammar, which serves as a non-executable specification for the parser. This formal background, together with the development of many sophisticated and intricate parsing approaches for...