Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Parser combinator
open-in-new
<p>In <a href="/facts/Computer_programming/QmSsFnu0">computer programming</a>, a parser combinator is a <a href="/facts/Higher-order_function/VjnjGbpt">higher-order function</a> that accepts several parsers as input and returns a new parser as its output. In this context, a <a href="/facts/Parser/nRKB01S3">parser</a> is a function accepting strings as input and returning some structure as output, typically a <a href="/facts/Parse_tree/FeBEtXcz">parse tree</a> or a set of indices representing locations in the string where <a href="/facts/Parsing/nRKB01S3">parsing</a> stopped successfully. Parser combinators enable a <a href="/facts/Recursive_descent_parser/ARhcuAv1">recursive descent parsing</a> strategy that facilitates modular piecewise construction and testing. This parsing technique is called combinatory parsing. </p><p>Parsers using combinators have been used extensively in the prototyping of compilers and processors for <a href="/facts/Domain-specific_language/n18H1foD">domain-specific languages</a> such as <a href="/facts/Natural-language_user_interface/TSsXHy2V">natural-language user interfaces</a> 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 <a href="/facts/Natural_language_processing/1hjMKsSN">natural-language</a> 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 <a href="/facts/Functional_programming/cdxqPEIM">functional programming</a> language <a href="/facts/Haskell/ydEsHuGy">Haskell</a> that solve the long-standing problem of accommodating <a href="/facts/Left_recursion/QNtQvgPr">left recursion</a>, and work as a complete <a href="/facts/Top-down_parsing/VVqphs5y">top-down parsing</a> tool in <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> time and space. </p>