Skip to content

Latest commit

 

History

History
62 lines (58 loc) · 3.04 KB

a-typed-algebraic-approach-to-parsing.md

File metadata and controls

62 lines (58 loc) · 3.04 KB

A typed, algebraic approach to parsing

  • Authors: Neel Krishnaswami and Jeremy Yallop
  • Conference: PLDI 2019
  • Published: 08 June 2019
  • DOI: 10.1145/3314221.3314625
  • PDF: https://www.cl.cam.ac.uk/~nk480/parsing.pdf
  • Source: github:yallop/ocaml-asp
  • Abstract:

    In this paper, we recall the definition of the context-free expressions (or µ-regular expressions), an algebraic presentation of the context-free languages. Then, we define a core type system for the context-free expressions which gives a compositional criterion for identifying those context-free expressions which can be parsed unambiguously by predictive algorithms in the style of recursive descent or LL(1).

    Next, we show how these typed grammar expressions can be used to derive a parser combinator library which both guarantees linear-time parsing with no backtracking and single-token lookahead, and which respects the natural denotational semantics of context-free expressions. Finally, we show how to exploit the type information to write a staged version of this library, which produces dramatic increases in performance, even outperforming code generated by the standard parser generator tool ocamlyacc.

BibTeX 
@inproceedings{10.1145/3314221.3314625,
  author = {Krishnaswami, Neelakantan R. and Yallop, Jeremy},
  title = {A typed, algebraic approach to parsing},
  year = {2019},
  isbn = {9781450367127},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/3314221.3314625},
  doi = {10.1145/3314221.3314625},
  abstract = {In this paper, we recall the definition of the context-free
  expressions (or µ-regular expressions), an algebraic presentation of the
  context-free languages. Then, we define a core type system for the context-free
  expressions which gives a compositional criterion for identifying those
  context-free expressions which can be parsed unambiguously by predictive
  algorithms in the style of recursive descent or LL(1). Next, we show how these
  typed grammar expressions can be used to derive a parser combinator library
  which both guarantees linear-time parsing with no backtracking and single-token
  lookahead, and which respects the natural denotational semantics of context-free
  expressions. Finally, we show how to exploit the type information to write a
  staged version of this library, which produces dramatic increases in
  performance, even outperforming code generated by the standard parser generator
  tool ocamlyacc.},
  booktitle = {Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation},
  pages = {379–393},
  numpages = {15},
  keywords = {Kleene algebra, context-free languages, parsing, type theory},
  location = {Phoenix, AZ, USA},
  series = {PLDI 2019}
}