GLL parse-tree generation
GLL parse-tree generation
复制标题
DOI：
10.1016/j.scico.2012.03.005
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
E. Scott;A. Johnstone
中科院分区：
文献类型：
--
作者：
E. Scott;A. Johnstone
通常用于扩展递归下降 (RD) 解析器的回溯技术可能具有爆炸性的运行时间，并且无法处理左递归语法。 GLL 解析器是完全通用的、最坏情况的三次解析器，它们具有类似递归下降的属性，易于编写和用于语法调试。它们与 RD 解析器的语法有直接关系。在本文中，我们给出了一种生成 GLL 解析器的算法，该算法构建了输入推导的 SPPF 表示，补充了我们现有的 GLL 识别算法，并且我们表明这种解析器和识别器是最坏情况的三次方。
Backtracking techniques which are often used to extend recursive descent (RD) parsers can have explosive run-times and cannot deal with grammars with left recursion. GLL parsers are fully general, worst-case cubic parsers which have the recursive descent-like property that they are easy to write and to use for grammar debugging. They have the direct relationship with the grammar that an RD parser has. In this paper we give an algorithm for generating GLL parsers which build an SPPF representation of the derivations of the input, complementing our existing GLL recognition algorithm, and we show that such parsers and recognisers are worst-case cubic.