Better extensibility through modular syntax
Better extensibility through modular syntax
复制标题
通过模块化语法实现更好的可扩展性
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
R. Grimm
中科院分区：
文献类型：
--
作者：
R. Grimm
我们探讨如何使模块化的好处可用于语法规范和目前的老鼠！，一个用于Java的解析器生成器，支持易于扩展的语法。我们的解析器生成器建立在最近的研究解析表达式语法（PEG），其中，被关闭下组成，优先选择，支持无限的前瞻性，并集成词法分析和解析，提供了一个有吸引力的替代上下文无关的语法。PEG由所谓的packrat解析器实现，这是一种递归下降解析器，它存储所有中间结果（因此得名）。记忆化确保了在存在无限前瞻时的线性时间性能，但也导致了本质上懒惰的函数式解析技术。在本文中，我们将探讨如何利用PEG和packrat解析器作为可扩展语法的基础。特别是，我们将展示如何使packrat解析更广泛地适用于实现这种懒惰的，功能性的技术，在一个严格的，命令式的语言，同时也产生更好的性能分析器，通过积极的优化。接下来，我们开发了一个模块系统，用于组织，修改和组成大规模的语法规范。最后，我们描述了一种新的技术，用于管理（全局）解析状态的功能解析器。我们的实验评估表明，由此产生的解析器生成器成功地提供可扩展的语法。尤其是老鼠！使其他语法编写者能够在很短的时间和代码内实现真实世界的语言扩展，并且它生成的解析器始终优于由两个GLR解析器生成器创建的解析器。
We explore how to make the benefits of modularity available for syntactic specifications and present Rats!, a parser generator for Java that supports easily extensible syntax. Our parser generator builds on recent research on parsing expression grammars (PEGs), which, by being closed under composition, prioritizing choices, supporting unlimited lookahead, and integrating lexing and parsing, offer an attractive alternative to context-free grammars. PEGs are implemented by so-called packrat parsers, which are recursive descent parsers that memoize all intermediate results (hence their name). Memoization ensures linear-time performance in the presence of unlimited lookahead, but also results in an essentially lazy, functional parsing technique. In this paper, we explore how to leverage PEGs and packrat parsers as the foundation for extensible syntax. In particular, we show how make packrat parsing more widely applicable by implementing this lazy, functional technique in a strict, imperative language, while also generating better performing parsers through aggressive optimizations. Next, we develop a module system for organizing, modifying, and composing large-scale syntactic specifications. Finally, we describe a new technique for managing (global) parsing state in functional parsers. Our experimental evaluation demonstrates that the resulting parser generator succeeds at providing extensible syntax. In particular, Rats! enables other grammar writers to realize real-world language extensions in little time and code, and it generates parsers that consistently out-perform parsers created by two GLR parser generators.