performance - Scala 解析器组合器、歧义语法和解析森林

Question

我试图让解析器从不明确的语法中返回所有可能的解析结果(解析森林)，并通过根据用户上下文/历史和知识库评估它们来从解析森林中进行选择。出于性能原因，这可能应该使用 Packrat 解析器和搜索限制/上限参数来完成，以限制在应用生产规则时递归调用的数量，以避免无限循环。

作为 Scala 及其解析器组合器的新手，我无法弄清楚如何做到这一点或是否可以做到这一点。有人可以帮忙吗？非常感激。

此致，
托马斯·胡安

Answer 1

你不能用 Scala 的内置解析器组合器来做到这一点。 Packrat 组合器仅限于明确的语法。如果您尝试处理歧义，您将失去内存的能力，即使对于明确的路径，解析复杂度也会变成 O(k^n)。所以，不要那样做。

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

GLL 组合器在最坏的情况下是 O(n^3)，即使对于病理上不明确的语法也是如此。在解析路径明确的平均情况下，GLL 组合子是 O(n)。恒定时间开销目前有点过大，但优化是一个持续的项目。我们在生产中使用 GLL 组合器 Precog ，因此您可以期望库在 future 得到良好维护。