Mon 24 Jun 2019 16:20 - 16:40 at 224AB - Parsing Chair(s): Qirun Zhang

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.

Mon 24 Jun

Displayed time zone: Tijuana, Baja California change

16:00 - 17:00
ParsingPLDI Research Papers at 224AB
Chair(s): Qirun Zhang Georgia Institute of Technology
16:00
20m
Talk
Lightweight Multi-Language Syntax Transformation with Parser Parser Combinators
PLDI Research Papers
Rijnard van Tonder Carnegie Mellon University, Claire Le Goues Carnegie Mellon University
DOI Pre-print Media Attached
16:20
20m
Talk
A Typed, Algebraic Approach to Parsing
PLDI Research Papers
Neel Krishnaswami Computer Laboratory, University of Cambridge, Jeremy Yallop University of Cambridge, UK
Link to publication DOI Pre-print
16:40
20m
Talk
Genie: A Generator of Natural Language Semantic Parsers for Virtual Assistant Commands
PLDI Research Papers
Giovanni Campagna Stanford University, USA, Silei Xu , Mehrad Moradshahi Stanford University, USA, Richard Socher Salesforce, USA, Monica S. Lam Stanford University, USA
Media Attached