DescriptionGeneralised parsing eases the design of programming languages as a language designer no longer needs to adjust the concrete syntax of the language to suit a particular parsing technique. Concrete syntax can be made more abstract if appropriate disambiguation strategies are available. Many tools exist for generating generalised parsers from a grammar specification, e.g. Bison, SDF, and Happy.
Handcrafted parsers are common in the functional programming community, thanks to the popularity of parser combinators: higher-order functions performing basic parsing operations that are composed to form more complex combinators. Advantages of the parser combinator approach are plentiful. For example, type-checked semantic actions execute semantics on the fly; the elementary combinators offer more than just terminal matching, e.g. matching terminals satisfying a certain predicate; forms of context-sensitivity are possible when using monadic parsers; and combinator libraries are easily extensible, either by the library implementer or by users of the library. In recent years, combinator libraries have emerged attempting to unite generalised parsing and combinator parsing as to benefit from the advantages of both approaches.
In this paper we discuss the difficulties generalised parsing techniques pose on defining such libraries. We adopt the standpoint of an inveterate functional programmer, writing parsers using conventional parser combinators, and impose a number of challenges to combinator libraries offering generalised parsing.
|30 Oct 2016