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

Automatically transforming programs is hard, yet critical for automated program refactoring, rewriting, and repair. Multi-language syntax transformation is especially hard due to heterogeneous representations in syntax, parse trees, and abstract syntax trees (ASTs). Our insight is that the problem can be decomposed such that (1) a common grammar expresses the central context-free language (CFL) properties shared by many contemporary languages and (2) open extension points in the grammar allow customizing syntax (e.g., for balanced delimiters) and hooks in smaller parsers to handle language-specific syntax (e.g., for comments). Our key contribution operationalizes this decomposition using a Parser Parser combinator (PPC), a mechanism that generates parsers for matching syntactic fragments in source code by parsing declarative user-supplied templates. This allows our approach to detach from translating input programs to any particular abstract syntax tree representation, and lifts syntax rewriting to a modularly-defined parsing problem. A notable effect is that we skirt the complexity and burden of defining additional translation layers between concrete user input templates and an underlying abstract syntax representation. We demonstrate that these ideas admit efficient and declarative rewrite templates across 12 languages, and validate effectiveness of our approach by producing correct and desirable lightweight transformations on popular real-world projects (over 50 syntactic changes produced by our approach have been merged into 40+). Our declarative rewrite patterns require an order of magnitude less code compared to analog implementations in existing, language-specific tools.

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