Reference. The semantics of parsing with semantic actions

Robert Atkey · · parsing · Web
The recovery of structure from flat sequences of input data is a problem that almost all programs need to solve. Computer Science has developed a wide array of declarative languages for describing the structure of languages, usually based on the context-free grammar formalism, and there exist parser generators that produce efficient parsers for these descriptions. However, when faced with a problem involving parsing, most programmers opt for ad-hoc hand-coded solutions, or use parser combinator libraries to construct parsing functions. This paper develops a hybrid approach, treating grammars as collections of active right-hand sides, indexed by a set of non-terminals. Active right-hand sides are built using the standard monadic parser combinators and allow the consumed input to affect the language being parsed, thus allowing for the precise description of the realistic languages that arise in programming. We carefully investigate the semantics of grammars with active right-hand sides, not just from the point of view of language acceptance but also in terms of the generation of parse results. Ambiguous grammars may generate exponentially, or even infinitely, many parse results and these must be efficiently represented using Shared Packed Parse Forests (SPPFs). A particular feature of our approach is the use of Reynolds-style parametricity to ensure that the language that grammars describe cannot be affected by the representation of parse results.

Cite

Cite as @atkey_2012 (helia, typst) · \cite{atkey_2012} (LaTeX)
BibTeX
bibtex · 7 lines
@inproceedings{atkey_2012,
 title = {The semantics of parsing with semantic actions},
 author = {Atkey, Robert},
 year = {2012},
 booktitle = {27th Annual IEEE Symposium on Logic in Computer Science (LICS)},
 url = {https://bentnib.org/semantic-actions.pdf}
}
hayagriva YAML (typst)
yaml · 9 lines
atkey_2012:
  type: article
  title: The semantics of parsing with semantic actions
  author: Atkey, Robert
  date: 2012
  url: https://bentnib.org/semantic-actions.pdf
  parent:
    type: proceedings
    title: 27th Annual IEEE Symposium on Logic in Computer Science (LICS)
Cites 18 works (2 here)
With notes (2)

Applicative programming with effects mcbride-2008-applicative

In this article, we introduce Applicative functors – an abstract characterisation of an applicative style of effectful programming, weaker than Monads and hence more widespread. Indeed, it is the ubiquity of this programming pattern that drew us to the abstraction. We retrace our steps in this article, introducing the applicative pattern by diverse examples, then abstracting it to define the Applicative type class and introducing a bracket notation that interprets the normal application syntax in the idiom of an Applicative functor. Furthermore, we develop the properties of applicative functors and the generic operations they support. We close by identifying the categorical structure of applicative functors and examining their relationship both with Monads and with Arrow.
PDF · DOI · pldb

An efficient context-free parsing algorithm Earley1970

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth’s LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to n3 (where n is the length of the string being parsed) in general; it has an n2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.
DOI
External (16)
  • A New Method for Dependent Parsing (2011)
  • Delayed semantic actions in Yakker (2011)
  • Semantics and algorithms for data-dependent grammars (2010)
  • Recognition is not Parsing – SPPF-style parsing from cubic recognisers (2010)
  • Parser combinators for ambiguous left-recursive grammars (2008)
  • SPPF-Style Parsing from Earley Recognisers (2008)
  • Combinator parsing: A short tutorial (2008)
  • Parsing expression grammars: a recognition-based syntactic foundation (2004)
  • BRN-table based GLR Parsers (Draft) (2003)
  • Elkhound: A Fast, Practical GLR Parser Generator (2002)
  • Parsec: Direct style monadic parser combinators for the real world (2001)
  • Monadic Parsing in Haskell (1998)
  • Categories for the Working Mathematician (1998)
  • The computational complexity of GLR parsing (1991)
  • Efficient Parsing for Natural Language (1986)
  • Types, Abstraction and Parametric Polymorphism (1983)
atkey_2012 reference entries/refs/atkey_2012/atkey_2012.hel