Parser combinator

In mathematics and functional programming, Higher Order functions (HOF) are defined as the functions that can take functions as their input and can also produce functions as their output. Use of a HOF as an infix operator in a function-definition is known as a ‘combinator’. When combinators are used as basic building blocks to construct a parsing technique, then they are called parser combinators and the parsing method is called combinatory-parsing (as higher-order functions ‘combine’ different parsers together). Parser combinators use a top-down parsing strategy which facilitates modular piecewise construction and testing. Parser combinators have been used extensively in the prototyping of compilers and processors for domain-specific languages such as natural language interfaces to databases, where complex and varied semantic actions are closely integrated with syntactic processing.

Basic Idea

The core idea of parser combinators (which was popularized Philip Wadler in 1985) is that the results (success or failure) of a recognizer (or a parser) can be returned as a list. Multiple entries of this list represent multiple successes; repeated entries represent ambiguous results and whereas an empty list represents a failure.

A production-rule of a context-free grammar (CFG) may have one or more ‘alternatives’ and each alternative may consist of a sequence of non-terminal(s) and/or terminal(s), or the alternative may consist of a single non-terminal or terminal or ‘empty’. In functional programming, parser combinators can be used to build basic parsers and to construct complex parsers for nonterminals from other parsers. Parser combinators allow parsers to be defined in an embedded style, in code which is similar in structure to the rules of the grammar. As such, implementations can be thought of as executable specifications with all of the associated advantages. In order to achieve this, one has to define a set of combinators or infix operators to ‘glue’ different terminals and non-terminals to form a complete rule.