Structuring the GLL parsing algorithm for performance
Structuring the GLL parsing algorithm for performance
复制标题
构建 GLL 解析算法以提高性能
DOI：
10.1016/j.scico.2016.04.003
复制
发表时间：
2016
影响因子：
1.3
通讯作者：
Scott E
中科院分区：
文献类型：
--
作者：
Scott E
GLL（Generalised LL）解析算法提供递归下降式解析的序列化，其产生高效的、编译的解析器，其允许任何上下文无关语法，包括左递归和非左因子规则。最后得到的解析器保持了“递归地体面”的属性，即解析器的结构紧密地遵循文法的结构;在本文中，我们开发了GLL算法的两个变体，称为FGLL和RGLL，它们分别支持（i）因子分解文法的有效解析和（ii）使用简化的描述符集进行解析。与基本GLL算法相比，这两种技术在编程语言语法上都有显着的速度提高。我们还讨论了描述符处理的顺序及其对性能的影响。
GLL (Generalised LL) parsing algorithms provide a sequentialisation of recursive-descent style parsing that yields efficient, compiled parsers which admit any context free grammar, including left recursive and non-left-factored rules. The resulting parsers retain the ‘recursively decent’ property that the structure of the parser closely follows the structure of the grammar; as such it is feasible to debug grammars by tracing the corresponding GLL parser using a conventional code debugger.In this paper we develop two variants of the GLL algorithm called FGLL and RGLL which respectively support (i) efficient parsing of factorised grammars and (ii) parsing using a reduced set of descriptors. Both techniques yield significant speed up on programming language grammars compared to the base GLL algorithm. We also discuss the ordering of descriptor processing and its effects on performance.
登录
查看更多内容
DOI：
10.1016/j.scico.2012.03.005
发表时间：
2013-10
期刊：
Sci. Comput. Program.
影响因子：
--
作者：
E. Scott;A. Johnstone
通讯作者：
E. Scott;A. Johnstone
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
Ten Brink
通讯作者：
Ten Brink
GLL解析
DOI：
--
发表时间：
2010
期刊：
Workshop on Language Descriptions, Tools and Applications
影响因子：
--
作者：
E. Scott;A. Johnstone
通讯作者：
A. Johnstone
纯函数式编程
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
T. Mailund
通讯作者：
T. Mailund
使用 ART 生成翻译器
DOI：
--
发表时间：
2010
期刊：
Software Language Engineering
影响因子：
--
作者：
A. Johnstone;E. Scott
通讯作者：
E. Scott