In computer programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output. In this context, a parser is a function accepting strings as input and returning some structure as output, typically a parse tree or a set of indices representing locations in the string where parsing stopped successfully. Parser combinators enable a recursive descent parsing strategy that facilitates modular piecewise construction and testing. This parsing technique is called combinatory parsing. Parsers using combinators have been used extensively in the prototyping of compilers and processors for domain-specific languages such as natural-language user interfaces to databases, where complex and varied semantic actions are closely integrated with syntactic processing. In 1989, Richard Frost and John Launchbury demonstrated use of parser combinators to construct natural-language interpreters. Graham Hutton also used higher-order functions for basic parsing in 1992 and monadic parsing in 1996. S. D. Swierstra also exhibited the practical aspects of parser combinators in 2001. In 2008, Frost, Hafiz and Callaghan described a set of parser combinators in the functional programming language Haskell that solve the long-standing problem of accommodating left recursion, and work as a complete top-down parsing tool in polynomial time and space.
Basic idea In any programming language that has first-class functions, parser combinators can be used to combine basic parsers to construct parsers for more complex rules. For example, 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 the empty string. If a simple parser is available for each of these alternatives, a parser combinator can be used to combine each of these parsers, returning a new parser which can recognise any or all of the alternatives. In languages that support operator overloading, a parser combinator can take the form of an infix operator, used to glue different parsers to form a complete rule. Parser combinators thereby enable parsers to be defined in an embedded style, in code which is similar in structure to the rules of the formal grammar. As such, implementations can be thought of as executable specifications with all the associated advantages such as readability.
The combinators To keep the discussion relatively straightforward, we discuss parser combinators in terms of recognizers only. If the input string is of length #input and its members are accessed through an index j, a recognizer is a parser which returns, as output, a set of indices representing indices at which the parser successfully finished recognizing a sequence of tokens that begin at index j. An empty result set indicates that the recognizer failed to recognize any sequence beginning at index j.
The empty recognizer recognizes the empty string. This parser always succeeds, returning a singleton set containing the input index:
e m p t y ( j ) = { j } {\displaystyle empty(j)=\{j\}}
A recognizer term x recognizes the terminal x. If the token at index j in the input string is x, this parser returns a singleton set containing j + 1; otherwise, it returns the empty set.
t e r m ( x , j ) = { { } , j ≥ # i n p u t { j + 1 } , j t h element of i n p u t = x { } , otherwise {\displaystyle term(x,j)={\begin{cases}\left\{\right\},&j\geq \#input\\\left\{j+1\right\},&j^{th}{\mbox{ element of }}input=x\\\left\{\right\},&{\mbox{otherwise}}\end{cases}}}
Given two recognizers p and q, we can define two major parser combinators, one for matching alternative rules and one for sequencing rules:
The ‘alternative’ parser combinator, ⊕, applies each of the recognizers on the same index j and returns the union of the finishing indices of the recognizers:
( p ⊕ q ) ( j ) = p ( j ) ∪ q ( j ) {\displaystyle (p\oplus q)(j)=p(j)\cup q(j)}
The 'sequence' combinator, ⊛, applies the first recognizer p to the input index j, and for each finishing index applies the second recognizer q with that as a starting index. It returns the union of the finishing indices returned from all invocations of q:
( p ⊛ q ) ( j ) = ⋃ { q ( k ) : k ∈ p ( j ) } {\displaystyle (p\circledast q)(j)=\bigcup \{q(k):k\in p(j)\}}
… excerpt ends here. Continue reading the full article.
