Scala的解析器组合，二义性文法与剖析林

Question

我试图让解析器通过评估它们对用户上下文/历史和知识，从一个模糊的语法返回所有可能的分析结果（剖析林），然后从剖析林基础。出于性能原因，这可能应该使用packrat解析器和搜索限制/上限参数来限制应用生产规则中递归调用的次数以避免无限循环。

作为新Scala和它的解析器组合，我无法弄清楚如何做到这一点，或者是否可以在全部完成。有人可以帮忙吗？非常感激。

最好的问候， 托马斯·胡安

Answer 1

你不能做到这一点Scala的内置解析器组合。 Packrat组合器仅限于无歧义的语法。如果尝试解决模糊问题，即使对于明确的路径，您也会失去记忆功能并且分析复杂度变为O（k^n）。所以，不要这样做。

你想要的是一个正确处理歧义的解析器组合框架。据我所知，唯一的Scala框架是我的GLL combinators。语法几乎是相同的Scala的解析器组合（其主要区别在于较高的arity功能工作正确），但输出的是Stream[A]，其中A是的结果类型。因此，你会得到一个解析森林。请注意，结果实际上不是SPPF（共享打包解析林），所以如果您生成指数数量的结果，则该流将具有成比例的大小。这样做是为了保持结果类型的最大灵活性。

GLL组合子在最差的情况下为O（n^3），即使对于病态歧义语法也是如此。在平均情况下，在解析轨迹明确的情况下，GLL组合器是O（n）。恒定的时间开销目前有点过分，但优化是一个正在进行的项目。我们在生产中使用GLL组合器，编号为Precog，所以您可以预期图书馆将继续保持良好状态。