Lightweight multi-language syntax transformation with parser parser combinators
Lightweight multi-language syntax transformation with parser parser combinators
复制标题
使用解析器解析器组合器进行轻量级多语言语法转换
DOI：
10.1145/3314221.3314589
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Le Goues, Claire
中科院分区：
文献类型：
--
作者：
van Tonder, Rijnard;Le Goues, Claire
自动转换程序是困难的，但对于自动程序重构，重写和修复至关重要。由于语法、解析树和抽象语法树（AST）的异构表示，多语言语法转换特别困难。我们的观点是，问题可以分解为：（1）一个通用语法表达了许多当代语言共享的中心上下文无关语言（CFL）属性，以及（2）语法中的开放扩展点允许定制语法（例如，用于平衡定界符）和较小解析器中的钩子来处理语言特定的语法（例如，供评论）。我们的主要贡献可操作的这种分解使用的解析器解析器组合器（PPC），一种机制，生成解析器匹配语法片段的源代码，通过解析声明性用户提供的模板。这使得我们的方法，以脱离翻译输入程序的任何特定的抽象语法树表示，并解除语法重写模块定义的解析问题。一个显著的效果是，我们绕过了在具体的用户输入模板和底层抽象语法表示之间定义额外的翻译层的复杂性和负担。我们证明，这些想法承认有效的和声明性的重写模板在12种语言，并验证我们的方法的有效性，产生正确的和理想的轻量级转换流行的现实世界的项目（超过50个语法变化产生的方法已合并成40+）。我们的声明式重写模式需要一个数量级的代码相比，现有的模拟实现，语言特定的工具。
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.
登录
查看更多内容
用于解析的高阶函数
影响因子：
1.1
作者：
Graham Hutton
通讯作者：
Graham Hutton
引用的分阶段重写：库定义优化的实用方法
DOI：
--
发表时间：
2017
期刊：
International Conference on Generative Programming: Concepts and Experiences
影响因子：
--
作者：
L. Parreaux;A. Shaikhha;Christoph E. Koch
通讯作者：
Christoph E. Koch
程序操作的语言设计
DOI：
--
发表时间：
1992
期刊：
IEEE Trans. Software Eng.
影响因子：
--
作者：
Ed Merks;J. Dyck;R. Cameron
通讯作者：
R. Cameron
方案中的句法抽象
DOI：
--
发表时间：
1992
期刊：
LISP and Symbolic Computation
影响因子：
--
作者：
R. Dybvig;Robert Hieb;Carl Bruggeman
通讯作者：
Carl Bruggeman
通过模块化语法实现更好的可扩展性
DOI：
--
发表时间：
2006
期刊：
ACM-SIGPLAN Symposium on Programming Language Design and Implementation
影响因子：
--
作者：
R. Grimm
通讯作者：
R. Grimm